Skip to main content
gamedev.net
🔒 Locked

grid or octree for collision?

Started by staticVoid2 14 replies 12.8k views
Original Post
staticVoid2
staticVoid2
hi there, I was wondering if a 3d axis aligned grid is better/faster than an octree for general collision detection? I'm currently using the grid approach where I separate all triangles into grid cells and then, for e.g. if the player moves I get the bounding box of the path, grab all the intersecting cells and check for a collision. would an octree offer anything more than this and where can I find articles about octree construction / usage?
Nanoha
Nanoha
It would just allow you to cull things faster.

If you have a volume, 8*8*8 (divided into 1*1*1* small volumes) then thats 512 nodes you would have to check each time. If your player is in the topmost, lefftmost, farmost sub volume of the volume then by checking the first 8 nodes (which would be of size 4*4*4) in an octree you eliminate 7 of those nodes from further checking, thats 448 nodes cull away at the cost of checking just 8.
Interested in Fractals? Check out my App, Fractal Scout, free on the Google Play store.
zedz
zedz
if its a space/flight sim etc then use an octree
else something on a terrain use a quadtree (perhaps stacked 2 high)

hmmm I think I understand what you want now
the grid approach in 99% of cases is gonna be quicker, the only cases where its not gonna be is for checking large volumes against the grid

personally I use both a Xtree and also a *grid[x][y] that access the xtrees leaves
oliii
oliii
Quote:
Original post by Nanoha
It would just allow you to cull things faster.

If you have a volume, 8*8*8 (divided into 1*1*1* small volumes) then thats 512 nodes you would have to check each time. If your player is in the topmost, lefftmost, farmost sub volume of the volume then by checking the first 8 nodes (which would be of size 4*4*4) in an octree you eliminate 7 of those nodes from further checking, thats 448 nodes cull away at the cost of checking just 8.


hmmm The advantage of a regular grid is that it is regular. You can index the cells directly using float-to-int consversions and floor/ceil maths.

I'll add another solution, the binary AABB tree.

That particular tree is pretty basic, and like all space partitioning techniques, the efficiency depends on how even the mesh is (large triangles vs small triangles, small dense areas, ect...). The trees are optimised by finding the best split planes but it can be costly and difficult.

Note that the tree is binary, but it could be made a quadtree (4 subdivisions) or an octree.

for a regular terrain, you don't actually need spatial subdivision. The terrain itself and the regularity can be used again to index the triangles you need directly.
Everything is better with Metal.
ttvd
ttvd
Hi, a while back for one of my courses I implemented and benchmarked most of datastructures mentioned in Christer Ericson's 'Real-time collision detection' book.

Kd-tree listed in the diagrams is SAH Kd-tree. Brute-force was done for reference and is O(N^2 / 2). Uniform / Hierarchical grids use hashing.

All testing was done in the context of cell simulation (a lot of small, highly dynamic particles).

Here are the results when objects have roughly the same size (horizontal is # of objects, vertical is score):






Here are the results when objects strongly differ in size:





Hope this helps.

ttvd
staticVoid2
staticVoid2
Quote:

hmmm The advantage of a regular grid is that it is regular. You can index the cells directly using float-to-int consversions and floor/ceil maths.


this is exactly what I'm doing.

I remember reading somewhere that one of the downsides to using a grid for collision was the memory overhead, but I don't see how it would be much of a problem - I store all the triangles in one array and then for each grid cell I have an array of 32-bit indices into this array.
BlackSeeds
BlackSeeds
Quote:
Original post by staticVoid2
Quote:

hmmm The advantage of a regular grid is that it is regular. You can index the cells directly using float-to-int consversions and floor/ceil maths.


this is exactly what I'm doing.

I remember reading somewhere that one of the downsides to using a grid for collision was the memory overhead, but I don't see how it would be much of a problem - I store all the triangles in one array and then for each grid cell I have an array of 32-bit indices into this array.


you can achieve a similar effect using a quadtree or octree by using a balanced tree and index directly using float-to-int and a conversion to Morton order the link shows how to do it for a quad tree this is easily extendable into 3 dimesnisons.

If your tree is balanced then you have the benefits of a regular grid and branches with no objects in can be flagged and discarded so it behaves much like an unbalanced tree, the empty nodes are then just there to be used if objects move into them.

This approach was really useful when needing a solution which had a tiny memory footprint.
phresnel
phresnel
Quote:
Original post by oliii
I'll add another solution, the binary AABB tree.


How exactly is your aabb tree different from regular kd-trees? I can only guess that you store full bounding boxes, which upon traversal may impact performance (compare to 8 byte kd-tree nodes, think of caches and bandwidth). I think if that's the point, it is still called a kd-tree, with some precalculated data (which imho doesn't make that structure novel, as precalculation is a well known technique) ;)


Quote:
The trees are optimised by finding the best split planes but it can be costly and difficult.

I guess you used surface area heuristics?


Sidenote: I once combined kd-tree traversal with a quadtree data structure, which I called "q/kd-tree".
oliii
oliii
That's why the file is called kd-tree and the implementation is an aabb tree :) I switch from one to the other mid-way. For 3 hours work, I didn't have time to mess about.

I've added a raycast query, and debug rendering, it was simpler with storing boxes :) There is an implementation of a compressed AABB tree in one of the games programming gems. The size isn't too bad.

Quote:

I guess you used surface area heuristics?


I didn't bother with too complicated things. It's taking the bounding box of the centroids, finds the longest axis, split the triangle list in the middle so each side has the same amount of triangles. Not sure what the most efficient method would be actually.

BTW, great graphs.
Everything is better with Metal.
phresnel
phresnel
Quote:
Original post by oliii
That's why the file is called kd-tree and the implementation is an aabb tree :)
[smile]


Quote:
I've added a raycast query, and debug rendering, it was simpler with storing boxes :) There is an implementation of a compressed AABB tree in one of the games programming gems. The size isn't too bad.
Optimal kd-tree traversal does not even need bounding boxes, you only need a single AABB for preparing traversal. Actually, you only intersect a single, axis aligned plane and work with intervals on the ray; not even the intersection point of the ray/plane is needed.

In Ingo Wald's Thesis, (Chapter 7, page 89ff), or more specifically 7.2 (p. 104ff), he gives this recursive algorithm:

void Traverse(){        ( t_near,t_far ) = ( Epsilon, ray.t_max );        ( t_near,t_far ) = Clip(t_near,t_far);        if (t_near > t_far)                // ray misses bounding box of object                return;        RecTraverse( bspRoot, t_near, t_far );}float RecTraverse(node,t_near,t_far)// returns distance to closest hit point{        if (IsLeaf(node)) {                IntersectAllTrianglesInLeaf(node);                return ray.t_closest_hit;                // t_closest_hit initialized to t_max before traversal        }        d = (node.split - ray.org[node.dim] / ray.dir[node.dim];        if (d <= t_near) {                // case one, d <= t_near <= t_far -> cull front side                return RecTraverse(BackSideSon(node),t_near,t_far);        } else if (d >= t_far) {                // case two, t_near <= t_far <= d -> cull back side                return RecTraverse(FrontSideSon(node),t_near,t_far);        } else {                // case three: traverse both sides in turn                t_hit = RecTraverse(FrontSideSon(node),t_near,d);                if (t_hit <= d) return t_hit; // early ray termination                return RecTraverse(BackSideSon(node),d,t_far);        }}


Traverse() prepares traversal by clipping the ray against the only bounding box and producing an interval on the ray.

The most costly operation being a single division. The iterative (non-recursive) version is even faster, and you can make it branch free for packet traversal. Note that IsLeaf() covers a cheap bitwise operation, and nodes are layed out to not produce cache misses in at least 50% of cases (actually, thanks to the nodes being only 8bytes big, you have even lesser misses; imagine how can store 128 nodes / KiB, or 131072 / MiB).



Quote:
Quote:
I guess you used surface area heuristics?

I didn't bother with too complicated things. It's taking the bounding box of the centroids, finds the longest axis, split the triangle list in the middle so each side has the same amount of triangles. Not sure what the most efficient method would be actually.
In ray tracing (or anything related to ray tracing), the meat of SAH is that it produces large empty spaces, that is, leaf nodes that don't contain anything, but are as big as possible. This makes it possible for traversal to termiate soon because you know theres a big volume with nothing to intersect, and concentrate on actual area to intersect. Equidistribution of triangles can be largely sub optimal for scenes like Sponza, where you have a mix of large and small triangles, and a lot of dense space, but at the same time a lot of empty space.

Unfortunately SAH is not easy to implement (I can assure you it's a good feeling once you made it), and afair, even multicore implementations build in N log(N).

Btw, here are some visualizations of SAH with MLRTA (where you search for common traversal entry points for groups of coherent rays, even more pain than SAH :)). The darker the areas, the lesser nodes have been traversed, or, the brighter, the more traversal steps:


Not sure which is the better method for relatively flat terrain, but for my q/kd-implementation I chose median split because building SAH with 130 triangles would have taken days.

Btw, in Walds thesis on page 113, you find a nice image which clarifies the benefits of large empty spaces vs. naive layouts (it's canonically called "naive", not targeted at you specifically ;)).


Quote:
BTW, great graphs.

Merci beaucoup.
NiGoea
NiGoea
Original post by oliii
Quote:

I'll add another solution, the binary AABB tree.


It sounds to me that AABB trees are nothing more special than octrees. Am I wrong ?

Quote:
Original post by ttvd
Hi, a while back for one of my courses I implemented and benchmarked most of datastructures mentioned in Christer Ericson's 'Real-time collision detection' book.


Sorry, what do you mean with "sort and sweep" ?


thanks !
Lord_Evil
Lord_Evil
"Sort and sweep" means that the objects are sorted on a primary axis (generally one of x,y and z but you can use an arbitrary one) and then are checked further if their projections on that axis overlap.

Example:
  _1_ |  _|2_    _3_ | | |  |  |   |-|-|-|--|--|---|- axis

Objects 1 and 2 overlap and thus potentially collide. Object 3 doesn't need to be checked further.
If I was helpful, feel free to rate me up ;)If I wasn't and you feel to rate me down, please let me know why!
EJH
EJH
If your game is generally on a 2D plane (like an RTS or 2D game) then a grid is probably the optimal choice, especially with a top-down camera. But for a 3D FPS or flight sim, probably go with the tree-based solutions.

The biggest benefit of grids is that proximity detection for any number of objects is O(1), e.g. "what objects are near me?" is handled by simply looking at what objects are in the same cell and adjacent cells. This helps not only for collision but also:

- proximity based AI decisions: only consider units in nearby grid cells (AI can be more computationally expensive than collision)

- picking optimization: find the grid cell picked, only consider units in that cell

- sound optimization: only sounds emanating from nearby grid cells to the camera are played

- network optimization: only need full updates on units in nearby cells

- special effects optimization: for transient aesthetic effects (like smoke, explosions, impacts, floating text) only create them if they occur in nearby cells to the camera (can be huge optimization here, especially in games with many units)

- top-down camera frustum culling: just draw stuff in nearby cells to the camera

You get all that for the cost of a single O(n) partitioning pass that places all objects into grid cells. Only Mark and sweep seems slightly better for collision only, but you lose the rest of those optimizations.
rouncED
rouncED
I would always use a grid, i only use octrees if i have to.

collision detection, what youve got already is fine, id just use a 2d one myself and count everything above each other the same cell
ttvd
ttvd
@phresnel, oliii

For collision detection purposes you can approximate SAH. There's no point in building expensive since you are highly likely to rebuild your Kd-tree often anyway. Same goes for dynamic ray-tracing scenes. One good method is to use surface min-max binning to approximate split planes (runs in linear time). And also only rebuild parts of the tree, which become "invalid" (according to some metric, child ratio of object counts in left:right subtrees works good). There's a good paper called "Highly Parallel Fast KD-tree Construction for Interactive Ray Tracing of Dynamic Scenes" from Intel guys on this subject.

@NiGoea

Sort and sweep is also called sweep and prune. Main idea of this method is to sort all objects along a certain axis, then do a linear pass over the sorted object sequence and check each object for collision with its neighbors. As you do a linear pass you also compute variances of object centers. In next frame you pick axis with highest variance for sorting. This method could potentially perform a worst-case O(N^2), if your objects are grouped heavily together. However if your objects are dispersed it's expected to run in O(NlogN).

Edit: added response to NiGoea.

[Edited by - ttvd on August 26, 2009 3:05:32 PM]
phresnel
phresnel
Quote:
Original post by ttvd
@phresnel, oliii

For collision detection purposes you can approximate SAH. There's no point in building expensive since you are highly likely to rebuild your Kd-tree often anyway. Same goes for dynamic ray-tracing scenes.


If you have to rebuild often, then I'd recommend another datastructure like the highly performant (both upon building and querying) bounding interval hierarchy, a newcomer. On ompf.org, you'll find tons of information, toxie there is an initiator of BIH, and you'll find a download on his site: Instant Ray Tracing: The Bounding Interval Hierarchy. From my experience, even with a basic non-optimized implementation, you can rebuild scenes of several hundreds of thousands of triangles several times per second. But as said, have a look at ompf for bleeding edge implementations.

You could use two acceleration structures, one which is optimized for static data, and one which is optimized for dynamic data. That approach is common in real time ray tracing systems like Jacco Bikkers (a.k.a. phantom on ompf and flipcode, phantomus here on gd.net) Arauna (have a look at their games list [smile]).

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.