Jump to content
  • Advertisement
Angelic Ice

How do you maintain Spatial Hashing?

This topic is 370 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello forum!

I would like to know how you handle spatial hashing in terms of updating elements.

First of all, I would like to point out, I'm talking about a spatial hash where one object can be referenced in multiple hash-buckets, as it could cross the border from bucket 1 to 2.

Next would be a game-object's position being updated, what do or would you do? Rebuild the entire spatial hashing (as its done with octree etc.)? Or would you maybe give each game-object a reference to its hash-buckets to make the game-object instruct deleting your game-object from its list/vector/... inside each hash-bucket referenced? 

If you decide to remove and then insert again - as just mentioned - I would be really interested in the way you tidy up all hash-buckets that used to have that particular object - since one object could potentially be referenced in multiple buckets (hit box being on a corner where e.g. 4 buckets meet, as stated in the beginning above).

If you have any particular language-specific tricks, I would be interested in C++ ways of doing. Maybe some weak-pointer-trickery..?

Thanks for your time!

Share this post


Link to post
Share on other sites
Advertisement

Much of that would depend on what you are using the hashing for.  If many things have changed, such as a once-per-frame update, then throw it all away each time.  If you get updates live and they are infrequent, maintaining it makes more sense.

Use of weak pointers seems wasteful due to all those validity checks. You should know the object lifetimes, and know when they are destroyed. There should be no way that the objects are destroyed without your knowledge.

Spatial hashing works well if you know everything falls neatly into the buckets.  When they span buckets as you describe, a quadtree or octree is often better.  When you need to have items move around frequently, a loose quadtree/octree variant is often better as they can drift into a neighboring cell without causing a shuffle.

Share this post


Link to post
Share on other sites

If you're finding it hard to remove objects because they span buckets, then surely you just need a method that returns all buckets for a given object? You must have that logic to be able to put the object in multiple buckets in the first place, so just put that in your update/remove method as well.

Share this post


Link to post
Share on other sites

By spanning buckets I was referring to one object transitioning from grid a to grid b. For the sake of collision, it would be required for other objects to know on what buckets there are currently on. I thought using one hashed bucket per grid would be quite neat and not reconstructing the entire spatial-hashing would make it a bit more efficient, since we are not talking about thousand of objects, hence alignment in RAM is probably not that crucial.

Oh, I could do the following: Keep old and new coordinates and then in order to update...

- If old hash-buckets are also reachable via the new/transformed coordinates, keep them.

- If old hash-buckets are not reachable via the new/transformed coordinates, remove references to the object in those buckets.

- Assign every new grid that was not already reachable via the new/transformed coordinates with old coordinates.

Is this a legit way of dealing with it? I never really thought about just simply using the old coordinates which made the thought-process for me quite difficult of finding the old hash-buckets.

Share this post


Link to post
Share on other sites

I suggest you take a look at the Icoseptree.

In this paper (https://www.cs.nmsu.edu/~joshagam/Solace/papers/master-writeup-print.pdf) you'll find a  good explanation and implementation of it.

Quote: "Each axis is divided into three regions, two of which are for objects entirely on one side of the split, and the third for objects whose bounding volumes intersect the split for that axis. The three regions on the three dimensions combine to provide 27 regions, each one representing a child node for objects to be inserted into"

I've been using the Icoseptree (straight from the paper above) for frustum culling, content streaming, even a physics broadphase for a decade and it always outperformed all other octrees, grid hashing, etc in my projects.

Share this post


Link to post
Share on other sites

Thanks for the link Chris! Icoseptree data structure looks interesting. Do you know if it widely used?

Share this post


Link to post
Share on other sites
18 minutes ago, tuket said:

Thanks for the link Chris! Icoseptree data structure looks interesting. Do you know if it widely used?

Frankly i have no idea if its widely used or not. That wouldn't really mean anything to me after all.
I evaluate every technique myself and as said this specific variant of an octree consistently outperformed any other tree structure in my projects (with one exception, which is the DynamicBVH used in Bullet Physics. but that implementation has its own limitations) 

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!