Sign in to follow this  
Days

Hashing cross products

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
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[i];
}

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[i];
};

bool operator < ( const comp_array& a ) {
static int i;
for ( i = 0; i < N; ++i )
if ( this->data[i] < a.data[i] ) return true;
return false;
};

bool operator == ( const comp_array& a ) {
static int i;
for ( i = 0; i < N; ++i )
if ( this->data[i] != a.data[i] ) 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[i] );
// 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[i] = new comp_array< 6, float >( data[i] );

// test the subscript operator
cout << "data_array[0] -> { ";
for ( int i = 0; i < 5; ++i )
cout << (*data_array[0])[i] << ", ";
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[i] < *data_array[j] )
cout << setw(2) << j << ", ";
}
cout << endl;
}

// clean up the float_arrays
for ( int i = 0; i < 13; ++i )
delete data_array[i];

system("pause");
return EXIT_SUCCESS;
}



Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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)?


Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this