Sign in to follow this  
brainydexter

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

Recommended Posts

brainydexter    158
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

Share this post


Link to post
Share on other sites
diablos_blade    257
The simplest option I can think of the same idea as how you determine the index for a 1D array that you are treating as 3D array (which I worked out the other day handily enough [grin]).

I probably didn't explain that very well, so something like this:


size_t gridCellsWide = ...;
size_t gridCellsHigh = ...;
size_t gridCellsDeep = ...;
float gridSize = ...;
Vector3f position = ...;

// encode
size_t x = static_cast<size_t>( position.x / gridSize );
size_t y = static_cast<size_t>( position.y / gridSize );
size_t z = static_cast<size_t>( position.z / gridSize );

size_t hash = x + ( y * gridCellsWide ) + ( z * gridCellsWide * gridCellsHigh );

// decode
x = hash % ( gridCellsWide * gridCellsHigh ) % gridCellsWide
y = ( hash % ( gridCellsWide * gridCellsHigh ) ) / gridCellsWide
z = hash / ( gridCellsWide * gridCellsHigh )

Vector3f cellCenterPoint;
cellCenterPoint.x = ( x * gridSize ) + ( gridSize * 0.5f );
cellCenterPoint.y = ( y * gridSize ) + ( gridSize * 0.5f );
cellCenterPoint.z = ( z * gridSize ) + ( gridSize * 0.5f );



That hash value would actually be the position of your grid cell if you stored the grids as a 1D array. You probably don't if you have a predetermined grid size, but I often don't or I'm dealing with image data or something similar, meaning I have to decode from 1D to 2D/3D and back again.

Because the hash value is just the 1D index of the cell it will be unique per cell. Not per object, but since you're using this for determining collision pairs it shouldn't be anyway.

Hope that helps [smile]

Share this post


Link to post
Share on other sites
brainydexter    158
Thanks a lot for the reply diablos_blade. I appreciate you posting some code as well.

I understand what you are saying and it is I think a simple yet effective technique. However, here is what concerns me.. I've assumed the world to be of infinite length and width. So, I really don't know how many cells would there be along the length/width.

Thus, how do you recommend coming up with values for gridCellsWide, gridCellsDeep ?

Thanks for the reply.

Share this post


Link to post
Share on other sites
diablos_blade    257
Quote:
Original post by brainydexter
I understand what you are saying and it is I think a simple yet effective technique. However, here is what concerns me.. I've assumed the world to be of infinite length and width. So, I really don't know how many cells would there be along the length/width.


Ah, now that does pose a problem for a a simple grid system =P, and not one I've tackled myself. It depends on the type of game of course but it seems to be solved by more of a heirarchical system.

Abusing the fact that "infinite" is technically impossible, the world is first split up into a (very) large grid, maybe thousands of meters in size for each cell, then these grids are split down into the fine grid system that we're talking about here, they can also be streamed in and out of memory as the player moves around. But that technique is pretty much an open-world game only idea.

On the other hand you could do something hacky like:
update all entity positions
find minimum and maximum entity positions
define grid bounds (width, height, depth) from the range of positions
hash all entities

The reasons I say thats a hacky options is because it means you can't cache the hash values between frames, because the grid could be a completely different size from one frame to the next. It also means constantly re-hashing static objects, which is just unnecessary work. As well as potentially a bunch of extra work depending on the number of entities. You could do a couple of things to ease the work load of such a system, but all in all, not nice at all =P

What type of game are you making? Spatial hashing is rather difficult in general without having some limit on the world, so knowing that would be a lot of help in helping you figure out a solution, even though I'll admit I'm pretty much out of my area of experience if you're planning a psuedo infinite open-world game. [wink]

Share this post


Link to post
Share on other sites
brainydexter    158
Ah, thanks for pointing that out. I was actually thinking infinite only from a theoretical perspective.

Now, I am making a FPS genre game which will not have a really large infinite world. It will have a finite-level, much like you had in Quake/Unreal Tournament. But, I don't have that in the game yet. In fact, all I am trying to do is a broad-phase for players and the bullets they fire.

So, lets keep the level out of this for now.. To answer my question about infinite length/width, what if we assume (for now) a large number..say 100 (in grid units, i.e. 100 grid units long and 100 grid units deep). Now, what you suggested earlier can be applied with this assumption. This assumption would no doubt break, if any of the players run outside this huge world space (i.e. 100 * GridcellSize). But, if that would happen, players would really be far far away from each other and I don't think that would happen (atleast for now).

If all fails, I will choose my world bounds one cell less than the max world size (i.e. 99 * GridCellsize), and put a check in there which will not let them move beyond it!

Once, I have the level-geometry, I can query the extents of that and use those to calculate the grid length/depth.

What do you think about this ?

One more thing, how did you handle negative position values ??

Share this post


Link to post
Share on other sites
diablos_blade    257
Quote:
Original post by brainydexter
Ah, thanks for pointing that out. I was actually thinking infinite only from a theoretical perspective.

Now, I am making a FPS genre game which will not have a really large infinite world. It will have a finite-level, much like you had in Quake/Unreal Tournament. But, I don't have that in the game yet. In fact, all I am trying to do is a broad-phase for players and the bullets they fire.

So, lets keep the level out of this for now.. To answer my question about infinite length/width, what if we assume (for now) a large number..say 100 (in grid units, i.e. 100 grid units long and 100 grid units deep). Now, what you suggested earlier can be applied with this assumption. This assumption would no doubt break, if any of the players run outside this huge world space (i.e. 100 * GridcellSize). But, if that would happen, players would really be far far away from each other and I don't think that would happen (atleast for now).

If all fails, I will choose my world bounds one cell less than the max world size (i.e. 99 * GridCellsize), and put a check in there which will not let them move beyond it!


Also known as invisible walls =P
Keeping players within level bounds is pretty much a solved problem. Outdoor levels you put an invisible wall somewhere, keeping players away from the edges by designing the level so the main focus points are nowhere near them. With indoor levels... you have actual walls =P

Quote:
Original post by brainydexter
Once, I have the level-geometry, I can query the extents of that and use those to calculate the grid length/depth.

What do you think about this ?


Sounds like the right idea to me [smile]

Quote:
Original post by brainydexter
One more thing, how did you handle negative position values ??


Easily:


Entity entity = ...;
Vector3f gridMinimumBounds = ...; // most likely a -ve value for each axis, assuming the grid is centered around 0,0,0. But any value would be fine.

Vector3f offsetPosition = entity.Position( ) - gridMinimumBounds;
size_t hash = PositionHash( offsetPosition );
StoreEntity( hash, entity );



As you can see, the actual position value you hash is the offset from the minimum bounds of the grid, which is one of the things you can query when loading in the level data. This offset should always be positive since it should be impossible to leave your level [smile]

Share this post


Link to post
Share on other sites
EJH    315
Here's another way to convert a position to a grid cell. Works for positive or negative numbers without division or mod.


// sector size: size of a square grid cell
// min and max: define the min and max points of the grid
// e.g. min:-10 max:10 defines a grid from -10,-10 to 10,10
// gridWidth: number of cells across the grid
// conversionFactor: to avoid division in the hash function
float sectorSize = 1000f;
float min = -10000f;
float max = 10000f;
int gridWidth = (int)((max - min) / sectorSize);
float conversionFactor = 1f / sectorSize;


// how to get x,y grid cell of a given point
Vector2 point;
int cellX = (int)((position.X + max) * conversionFactor);
int cellY = (int)((position.Y + max) * conversionFactor);



Share this post


Link to post
Share on other sites
thefries    103
First i discretize x, y and z by dividing them by the cell size and casting them to integers. Then i apply this hash function:

uint32 hash = (((uint32)pos.x) * 73856093) ^ (((uint32)pos.y) * 19349663) ^ (((uint32)pos.z) * 83492791);

so x, y and z cast to unsigned, i don't care about the wrap around, then they are multiplied by a large prime number and then XORed together. This gives a relatively nice distribution.

Share this post


Link to post
Share on other sites
brainydexter    158
@ Everyone: Thanks a lot for your replies. I appreciate all the help. This is what I ended up using:

I assume that is the world is bounded by -Extents to Extents (in Grid units); => Array is essentially of length 2 * Extents.

So, after I find the Grid Position, I move the coordinate system from (-Extent == +Extents) to (0 to 2 * Extents). Thus the hash key has the added multiplying factor of 2.


glm::vec3 worldPosn = l_Corners[k]; // corner of the bounding box

float invMaxRadius = 1 / (2.0f * Player::MaxRadius);
glm::vector::uvec3 gridPosn = (glm::vector::uvec3)(worldPosn * invMaxRadius);

// translating gridPosn from -XTents to XTents
gridPosn.x += GridCellsWide;
gridPosn.y += GridCellsHigh;
gridPosn.z += GridCellsDeep;

std::size_t hashKey = gridPosn.x + (gridPosn.y * (2 * GridCellsWide) ) + (gridPosn.z * GridCellsWide * GridCellsHigh * 4);




I think this should work.. At the moment, I'm I am getting a weird error with object being deleted and I'm trying to fix that, so I have no way to see if this is working or not. So, what do you guys think about this ??

Thanks!

Share this post


Link to post
Share on other sites
kloffy    1318
I can't really comment on whether your approach gives good hash values. However, the primary concern when generating hashes should be to minimize hash collisions. This is usually accomplished with a uniform distribution of hash values, e.g. as suggested by thefries.

Share this post


Link to post
Share on other sites
Valkoran    108
You guys are blowing this out of proportion. Minimize collisions? Give me a break. The only time you will get a collision with the presented method is when you have two of the same coordinates, or you try to mix and match different grids together.

Share this post


Link to post
Share on other sites
diablos_blade    257
I'll agree the method I provided isn't a typical hashing function. I did infact say that it is just a method of converting a 3D index into a 1D index.

The reason I suggested it as a solution is because the only time you will get a hash collision is when two objects are in the same grid cell, which is what I understood was wanted. Using this you could now iterate over your hash table and only check for collisions between objects which have the same hash value. Depending on how the hash table is structured it could end up being faster than iterating over all grid cells and testing collisions or iterating over each object, getting the grid cell it is in and then iterating over those.

Of course if this isn't what you wanted to use the hash value for, then you should probably ignore my idea and go for something similar to thefries method. [smile]

Share this post


Link to post
Share on other sites
brainydexter    158
@diablos: Nope, this is exactly what I wanted and it is proving out to be quite useful. I've got it working with players already! Time to get the bullets also integrated!!

Thanks for all the comments guys.

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