Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
    
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? –  da code monkey Apr 4 '11 at 19:59
1  
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....) –  mikera Apr 4 '11 at 21:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.