Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


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


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
14 replies to this topic

#1 brainydexter   Members   -  Reputation: 158

Like
1Likes
Like

Posted 05 April 2010 - 03:12 PM

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

Sponsor:

#2 sinalta   Members   -  Reputation: 257

Like
0Likes
Like

Posted 05 April 2010 - 04:09 PM

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]

#3 brainydexter   Members   -  Reputation: 158

Like
0Likes
Like

Posted 05 April 2010 - 06:02 PM

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.

#4 sinalta   Members   -  Reputation: 257

Like
0Likes
Like

Posted 05 April 2010 - 06:50 PM

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]

#5 brainydexter   Members   -  Reputation: 158

Like
0Likes
Like

Posted 05 April 2010 - 07:29 PM

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 ??

#6 sinalta   Members   -  Reputation: 257

Like
0Likes
Like

Posted 05 April 2010 - 07:52 PM

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]

#7 EJH   Members   -  Reputation: 315

Like
0Likes
Like

Posted 06 April 2010 - 12:53 AM

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);





#8 thefries   Members   -  Reputation: 103

Like
0Likes
Like

Posted 08 April 2010 - 11:06 PM

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.

#9 brainydexter   Members   -  Reputation: 158

Like
0Likes
Like

Posted 09 April 2010 - 08:04 PM

@ 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!


#10 thefries   Members   -  Reputation: 103

Like
0Likes
Like

Posted 10 April 2010 - 03:30 AM

That looks a lot more like a conversion from a 3d array index into a 1d array index than a hash key.

#11 brainydexter   Members   -  Reputation: 158

Like
0Likes
Like

Posted 10 April 2010 - 07:27 AM

@theFries: Which I think makes up a candidate for a good hash key :) ?

#12 kloffy   Members   -  Reputation: 960

Like
0Likes
Like

Posted 10 April 2010 - 07:40 AM

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.

#13 Valkoran   Members   -  Reputation: 108

Like
0Likes
Like

Posted 11 April 2010 - 03:59 AM

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.

#14 sinalta   Members   -  Reputation: 257

Like
0Likes
Like

Posted 11 April 2010 - 05:56 AM

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]

#15 brainydexter   Members   -  Reputation: 158

Like
0Likes
Like

Posted 11 April 2010 - 05:59 AM

@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.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS