How do I find hash value of a 3D vector?

问题:

I am trying to perform broad-phase collision detection with a fixed-grid size approach. Thus, for each entity's position: (x,y,z) (each of type float), I need to find which cell does the entity lie in. I then intend to store all the cells in a hash-table and then iterate through to report (if any) collisions.

So, here is what I am doing: Grid-cell's position: (int type) (Gx, Gy, Gz) => (x / M, y / M, z / M) where M is the size of the grid.

Once, I have a cell, I'd like to add it to a hash-table with its key being a unique hash based on (Gx, Gy, Gz) and the value being the cell itself. Now, I cannot think of a good hash function and I need some help with that.

Can someone please suggest me a good hash function?

Thanks

回答1:

If someone is still interested in this, I figured out a solution that works over here:

http://www.gamedev.net/community/forums/topic.asp?topic_id=567378

回答2:

The grid approach is going to have problems near the boundaries of the grid boxes. Why not use BSP trees instead?

回答3:

My preferred hashing function for this kind of vector is to rotate the bits of each component by a different constant and XOR them together.

It's very fast, and the bit rotations are helpful to reduce collisions and ensure as much of the key space as possible is used.

回答4:

here are a few references you could look at. Warren's papers discuss the hash algorithm in detail:

A parallel hashed Oct-Tree N-body algorithm

A portable parallel particle program