Is btDbvt based on a paper or article?

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
sphet
Posts: 38
Joined: Mon May 06, 2013 6:14 pm

Is btDbvt based on a paper or article?

Post by sphet »

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
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Is btDbvt based on a paper or article?

Post by Dirk Gregorius »

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.
Last edited by Dirk Gregorius on Tue May 07, 2013 2:50 am, edited 1 time in total.
sphet
Posts: 38
Joined: Mon May 06, 2013 6:14 pm

Re: Is btDbvt based on a paper or article?

Post by sphet »

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?
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Is btDbvt based on a paper or article?

Post by Dirk Gregorius »

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
sphet
Posts: 38
Joined: Mon May 06, 2013 6:14 pm

Re: Is btDbvt based on a paper or article?

Post by sphet »

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
Post Reply