4
\$\begingroup\$

I've been reading Real-Time Collision Detection and for loose octrees it recommends expanding each node's AABB length by a factor of 2, making its expanded volume 8 times as large. I am surprised that it needs to be this large, and there must be quite a lot of overlap and unnecessary child node traversals due to this large size. Within the top few levels of the octree, triangles are generally very small compared to the node's volume so I don't see any problem with making their scaling factor much less than 2, perhaps even 1.1 (And then ramping it back up to 2 after a certain depth.)

This is for an octree holding static background geometry so I'm not concerned with how long building it takes.

Is there a mathematical reason for the radius ratio being two?

\$\endgroup\$

1 Answer 1

Reset to default
8
\$\begingroup\$

The reason that the scaling factor is two is because this is the absolute minimum scaling factor that guarantees an at-most-cell-sized object can be placed within a single cell that contains it's centre point.

This is easy to visualise - imagine the centre point of a cell-sized object is at the very edge of a given cell - then the far edge of the object will be 1/2 of a cell width outside the cell. Add this boundary to both sides and you get your factor of two...

You are right that this does create overlap and can cause multiple child traversals, but you can avoid "unnecessary" traversals by paying attention to your bounding box as you descend the octree. In practice, you won't need to go very deep most of the time to eliminate the possibility of a collision.

You could reduce the scaling factor on the top level octree nodes but only if you can guarantee that no object would ever be large enough to extend beyond the size of this margin. There might be a small benefit in doing this, but as soon as you get down a few levels you will need your scaling factor of two anyway - which will account for the vast majority of nodes in the octree.

\$\endgroup\$
2
  • \$\begingroup\$ Nice answer. As for the unnecessary child traversals, do you think an acceleration structure such as an hgrid holding a forest of octrees is a feasible optimization when objects of a very large range of sizes are present? \$\endgroup\$ Commented Apr 4, 2011 at 19:59
  • 1
    \$\begingroup\$ I've found that a single octree usually works fine for a pretty large range of object sizes. I'd suggest starting with this unless you know you have a problem that requires a special fix. FWIW, I've found that having lots of overlapping AABBs can be a bigger problem than the size of the AABBs (since you run into n^2 intersections tests pretty quickly....) \$\endgroup\$ Commented Apr 4, 2011 at 21:20

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.