Hashing cross products
Author
This is going to be a little out of the ordinary, but I am going to ask anyway.
Basically, what I am trying to do is build a hash table that stores cross products. The reason is, I have a highly tesselated mesh that I am going to be deforming every frame, and to calculate correct lighting on it, I would have to find cross products and normalise for every face (thousands).. I am trying to cut every corner I can to speed up these operations.
I am planning on using precision to the thousandth (0.001) digit, and go from 0-10. This will keep the hash table managable, yet still give lighting that will be correct enough to fool anybody.
The problem I am having is, creating a hash function that will make a unique number out of 6 floats. Everything I have come up with so far has been entirely too big.
Any insight?
couldn't you just concat all the floats? The only way you would then hit a collision in the table is if you used the same 6 floats, in which case I would assume you want to overwrite it. You could probably truncate them at some point. Maybe one or two decimals.
Maybe I am misunderstanding. Most of what you said was gibberish to me anyway =D
Maybe I am misunderstanding. Most of what you said was gibberish to me anyway =D
Author
Okay I'll start with what I have so far, and why.
Vert1.x is the first float.. and its a full sized float, say, 0.1234567
now, I could multiply that out to get a whole number, but multiply takes what, 16 cycles during runtime? much better than a cross product, but there is an easier way.
int Vert1x = *(long*)&Vert1.x
that drops the decimal out of the float, and stores it into an int, with 2 typecasts. Yes, I realise we have also eliminated the possibility of negative floats, this is fine with me. this gives us a 9 digit number, so an int would be the smallest type we could possibly store it in.
now we repeat for all 6 vectors.
I could then concat all of them together, but what do I store it in? even an unsigned long long wouldn't have enough bits.
I hope this clears it up.
Vert1.x is the first float.. and its a full sized float, say, 0.1234567
now, I could multiply that out to get a whole number, but multiply takes what, 16 cycles during runtime? much better than a cross product, but there is an easier way.
int Vert1x = *(long*)&Vert1.x
that drops the decimal out of the float, and stores it into an int, with 2 typecasts. Yes, I realise we have also eliminated the possibility of negative floats, this is fine with me. this gives us a 9 digit number, so an int would be the smallest type we could possibly store it in.
now we repeat for all 6 vectors.
I could then concat all of them together, but what do I store it in? even an unsigned long long wouldn't have enough bits.
I hope this clears it up.
If you can find a way to define whether or not a 6 float object is lesser than another 6 float object, using the < operator, then the std::set would be a good option for you. In the past I've used it for indexing vertices for extremely fast welding and edge-sharing search operations on triangles.
If you can't, this page has source code for various trivial hashing algorithms (look toward the bottom of the page):
http://www.partow.net/programming/hashfunctions/
If you do go with one of those hashing algorithms, but don't want to roll your own hash table, some C++ implementations support the non-standard hash_set container class, which works by using a user defined hash function instead of the < operator. A perfect fit IMHO.
If you can't, this page has source code for various trivial hashing algorithms (look toward the bottom of the page):
http://www.partow.net/programming/hashfunctions/
If you do go with one of those hashing algorithms, but don't want to roll your own hash table, some C++ implementations support the non-standard hash_set container class, which works by using a user defined hash function instead of the < operator. A perfect fit IMHO.
Ok, I was really bored (and this is kinda interesting) so I wrote up a little program. It has simple tests for a couple of the suggestions (the hash algorithm itself could probably definitely be improved...I just made it up [embarrass])...anyway, it might be useful and it might not but here it is...
#include <cstdlib>#include <iostream>#include <iomanip>using namespace std;typedef unsigned int hashed_t;template < int N, typename HashedType >HashedType hash_floats( const float* const data ) { static HashedType hash; static int i; for ( i = 0, hash = 0; i < N; ++i ) { hash = ( hash << (sizeof( HashedType )*4) ) | (hash >> sizeof( HashedType )*4); hash ^= *(HashedType*)&data; } return hash;};template < int N, typename DataType >struct comp_array { DataType data[6]; comp_array( float* const a ) { memcpy( this->data, a, sizeof( data ) ); }; DataType operator [] ( size_t i ) { return this->data; }; bool operator < ( const comp_array& a ) { static int i; for ( i = 0; i < N; ++i ) if ( this->data < a.data ) return true; return false; }; bool operator == ( const comp_array& a ) { static int i; for ( i = 0; i < N; ++i ) if ( this->data != a.data ) return false; return true; }; // etc...};int main(int argc, char *argv[]){ // avoid unused parameter warning (void) argc; (void) argv; // test data to hash float data[][6] = { { 0.1245f, 0.0545642335f, 0.5f, 0.25f, 0.00001f, 1.0f }, // 1 { 0.1246f, 0.0545642335f, 0.5f, 0.25f, 0.00001f, 1.0f }, // 2 { 0.1245f, 0.0545642335f, 0.5f, 0.25f, 0.00001f, 0.0f }, // 3 { 0.1245f, 0.0545642335f, 0.5f, 0.25f, 0.0f, 0.0f }, // 4 { 0.1245f, 0.0545642335f, 0.5f, 0.0f, 0.0f, 0.0f }, // 5 { 0.1247f, 0.0545642335f, 0.5f, 0.25f, 0.00001f, 1.0f }, // 6 { 0.1244f, 0.0545642335f, 0.5f, 0.25f, 0.00001f, 1.0f }, // 7 { 0.1243f, 0.0545642335f, 0.5f, 0.25f, 0.00001f, 1.0f }, // 8 {-0.1245f, 0.0545642335f, 0.5f, 0.25f, 0.00001f, 1.0f }, // 9 { 0.1245f, 0.0545642335f,-0.5f,-0.25f,-0.00001f,-1.0f }, // 10 {-0.1245f,-0.0545642335f,-0.5f,-0.25f,-0.00001f,-1.0f }, // 11 { 0.1245f,-0.0545642335f, 0.5f, 0.25f, 0.00001f, 1.0f }, // 12 { 0.1245f,-0.0545642335f,-0.5f,-0.25f,-0.00001f,-1.0f }}; // 13 // space for hash result hashed_t hash; // loop through data sets for ( int i = 0; i < 13; ++i ) { // hash data set i hash = ::hash_floats< 6, hashed_t >( data ); // display result cout << hash << endl; } cout << "---------------------" << endl; // allocate float_arrays from the data arrays (so I don't have to type out the data twice :) comp_array< 6, float >* data_array[13]; for ( int i = 0; i < 13; ++i ) data_array = new comp_array< 6, float >( data ); // test the subscript operator cout << "data_array[0] -> { "; for ( int i = 0; i < 5; ++i ) cout << (*data_array[0]) << ", "; cout << (*data_array[0])[5] << " }" << endl; // test out the < operator for ( int i = 0; i < 13; ++i ) { cout << "data_array[" << setw(2) << i << "] < "; for ( int j = 0; j < 13; ++j ) { if ( i != j ) if ( *data_array < *data_array[j] ) cout << setw(2) << j << ", "; } cout << endl; } // clean up the float_arrays for ( int i = 0; i < 13; ++i ) delete data_array; system("pause"); return EXIT_SUCCESS;}
I don't understand why you are storing cross-products in a hash table. Are you doing a table lookup rather than computing the value? Then why a hash table?
Author
I am only approximating the values, to make it good enough to fool the eye, but faster than doing the cross product itself. This is highly experimental, and so far, looking like its going to fail dismally.. but I am chaulking it up to research.
Yes , but ur making a lookup table. That means u have a 1 to 1 relationship between ur 6 capped floats and positions in the table. Meaning , your table has as many positions as there are combinations of your six floats(capped to .001), meaning your 6 floats are already a table key themselves. So, wats the point of a hash function (its gonna give you the same number of hash keys as there are 6 float combinations, its not gonna reduce ur table)?
Let's say that each component is reduced to 1 of 16 values (4 bits of resolution per component). That gives you a 24-bit index which translates to 16 million elements. Now assuming that each value in the table has 30 bits (or 4 bytes) per element, your table is 64 MB. You could spend a few CPU cycles and take advantage of rotation and reflection to cut the size by a factor of 8 (perhaps 16 or 32?), giving you a 8 MB table. That's not too bad. However, there are two potentially major problems.
4 bits per component is really really low resolution. It can only represent the integers from -8 to 7. But maybe that's ok with you.
With a lookup table this size, you will be thrashing the data cache and it will probably be faster to do just do the math than to do a lookup. But, you might want to profile the two and compare.
4 bits per component is really really low resolution. It can only represent the integers from -8 to 7. But maybe that's ok with you.
With a lookup table this size, you will be thrashing the data cache and it will probably be faster to do just do the math than to do a lookup. But, you might want to profile the two and compare.
Quote:Original post by JohnBolton
With a lookup table this size, you will be thrashing the data cache and it will probably be faster to do just do the math than to do a lookup. But, you might want to profile the two and compare.
I agree with John, this hashing scheme sounds like a bad idea that would end up more expensive than the naive approach.
First, have you profiled that computing the normals really is your bottleneck? Second, have you tried compressing your data or changing your access pattern so you're touching less memory in a more cache-friendly way? Third, have you tried moving some of your calculations from the CPU into a vertex shader in an attempt to speed it up that way? Just some thoughts.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement