Real-Time Physics Simulation Forum

Re: Is btDbvt based on a paper or article?

2013-05-07T04:13:49+00:00

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

Statistics: Posted by sphet — Tue May 07, 2013 4:13 am

Re: Is btDbvt based on a paper or article?

2013-05-07T02:49:05+00:00

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

Statistics: Posted by Dirk Gregorius — Tue May 07, 2013 2:49 am

Re: Is btDbvt based on a paper or article?

2013-05-06T23:02:00+00:00

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?

Statistics: Posted by sphet — Mon May 06, 2013 11:02 pm

Re: Is btDbvt based on a paper or article?

2013-05-07T02:50:18+00:00

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.

Statistics: Posted by Dirk Gregorius — Mon May 06, 2013 9:10 pm

Is btDbvt based on a paper or article?

2013-05-06T18:40:21+00:00

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

Statistics: Posted by sphet — Mon May 06, 2013 6:40 pm