Sorting objects by position in a 3d grid
Author
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
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.
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.
Author
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)
I was looking for a tutorial or sample implementation as well. (SO I can code mine as efficiently as possible)
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.
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.
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.
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.
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.
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 :-)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
