Sign in to follow this  
try_catch_this

Sorting objects by position in a 3d grid

Recommended Posts

try_catch_this    373
I am looking of a tutorial or example implementation of a way to sort objects based on their position in a 3d grid so i only have to check for collisions on objects in the same cell. I have heard of something called voxels but I only find this in relation to ray tracing and other visual pprocessing. any help would be great

Share this post


Link to post
Share on other sites
jyk    2094
As mentioned above, octrees are an option. However, from your post it sounds like perhaps a uniform grid is what you're looking for.

One common way to sort objects in a uniform grid is to put them in the cell that contains one of the corners of the object's axis-aligned bounding box. If the object can be no larger than a cell, then you need only test that cell and 7 of its 26 neighbors for potential colliders, which is fairly efficient.

There are other options - the aforementioned octrees, loose octrees, and other hierarchical structures - but for certain situations a uniform grid is perfectly adequate, and is generally easier to code and update from frame to frame.

Share this post


Link to post
Share on other sites
try_catch_this    373
The uniform grid sounds like what I am looking for currently.

I was looking for a tutorial or sample implementation as well. (SO I can code mine as efficiently as possible)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Sounds like you are looking for Sweep-and-Prune. Basic idea is you sort the objects on each axis.

For each object take the AABB. Then insert the extremes of each axis of the AABB into their corresponding list. So basically for the X axis you do something like.

for all objects in scene...
{
XList.Add(obj.minX);
XList.Add(obj.maxX);

}
XList.sort();
YList.sort();
ZList.sort();


each frame you need to resort the lists, but the sorts will be pretty quick since usually only a few objects will move.

To check for collisions simply loop from min to max on each axis of an object, for object A to collide with object B it needs to have an entry between obj.min and obj.max.

Anyways, sorry I couldnt explain better, I have to head out the door right now.

Share this post


Link to post
Share on other sites
jyk    2094
If you're in a position to get a hold of a book or two, I can make a couple of suggestions. In his book 'Real-time Collision Detection', Christer Ericson covers many broad-phase methods (grids, trees, sweep and prune) in considerable detail. And, if you're particularly interested in sweep and prune, Gino van den Bergen covers it in detail in 'Collision Detection in Interactive 3D Environments'. Both references include source code samples, and address practical issues of implementation and efficiency.

Share this post


Link to post
Share on other sites
Thanks for the plug, jyk! (But I thought I covered sort and sweep methods in more detail than Gino? Anyway, not important.)

Like jyk suggests, a uniform grid is probably what the original poster is looking for. There are many flavors, but there should be quite a lot information available out there on at least some flavors.


Also, I figured I'd take this opportunity to step up on the soapbox to try to address a long-time pet peeve of mine. I'd like to try to make the (probably fruitless) case for abolishing the "sweep and prune" term in preference of "sort and sweep" as the generic term.

"Sweep and prune" is from Cohen et al's 1995 paper, but David Baraff had already described the general method in his 1992 thesis under the term "sort and sweep." Customarily we name things after the person who described them first, thus my preference for "sort and sweep" over "sweep and prune."

If others think this make sense, please start using "sort and sweep" to describe the various sort-based algorithms to collision detection instead of "that other" term.

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
(But I thought I covered sort and sweep methods in more detail than Gino? Anyway, not important.)
Oops, sorry about that! I think my post was just poorly worded, as I didn't really intend to compare the two treatments. My mistake :-|
Quote:
If others think this make sense, please start using "sort and sweep" to describe the various sort-based algorithms to collision detection instead of "that other" term.
Will do :-)

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