Real-Time Physics Simulation Forum

Hello,

I need to implement a data structure similar to btDbvt, and wonder if it is based on any particular article or paper? I would use bullet in situ but our company/publisher requires all source code to be first party.

Specifically I am interested in the incremental optimization and optimization-path strategy used, and whether it converges on an ideal tree over time, assuming all entities are only performing periodic movement. We are hoping to use a BVT to accelerate the broadphase and frustum culling so rapid insert/removal is key over perfect balance.

Thanks for any details.

S

There is a good chapter on BVH in C. Ericsons book "Real-time Collision Detection". Chapter 6.2.3 talks about incremental construction specifically.
I also suggest looking at the Box2D dynamic tree. It is essentially the same concept, but uses SAH and AVL tree rotations to balance the tree. I would study both implementations.

Dirk,

Thanks for post - I'll have another look at the Ericsons chapter. For some reason it slipped my mind.

I'll take another look at Box2D; any thoughts on how SAH and rotations perform in contrast to bullet's implementation?

I think (!) that in theory the btDbvt can degenerate into a linked-list, but I don't remember the details and it might be fixed. Personally I ported the Box2D version to 3D. It works awesome and I never needed to think about it again. Anyway, both version seem to work great in practice. I found the Box2D version easier to read and more comprehensible.

There is a paper that describes the AVL tree rotations in the Box2D version if you want to look into it: http://citeseerx.ist.psu.edu/viewdoc/su ... 1.125.7818

Hmm - interesting. I'll take a look again at the Box2D case. I'm working in a pretty slow and particular hardware environment so testing out both implementations may be the best bet. Thanks for the article on AVL rotations; I don't think I've seen that one.

S