How do I find hash value of a 3D vector ?
Author
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
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:
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]
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 = ...;// encodesize_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 );// decodex = 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]
Author
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.
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.
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]
Author
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 ??
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 ??
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]
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 functionfloat 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 pointVector2 point;int cellX = (int)((position.X + max) * conversionFactor);int cellY = (int)((position.Y + max) * conversionFactor);
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.
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.
Author
@ 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.
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!
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 boxfloat invMaxRadius = 1 / (2.0f * Player::MaxRadius);glm::vector::uvec3 gridPosn = (glm::vector::uvec3)(worldPosn * invMaxRadius);// translating gridPosn from -XTents to XTentsgridPosn.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!
That looks a lot more like a conversion from a 3d array index into a 1d array index than a hash key.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
