aabb trees for dynamic objects

[ED209]

Hi, when i was about to implement a aabb tree for mesh collision i run into a design problem. There seems to be two diferent ways to process collisions for dynamic objects (this is not an isue for static objects).

1.If the aabb is given in objects space one way is to transform the aabb from object B into object A modelspace and preforming a 'sat' test (aabb vs oobb) like in Opcode or Solid.

2.The other way is to keep the aabb tree in world space and 'refit' the tree while the object is moving. Both methods have their own pros and cons.

For the first method the problem is that you have to transform the aabox every time you want to make a node overlap quiery. You also have to dequntize the box if the tree is compressed (may also have to dequantize the box from tree A or requantize the box from B into As quantization space). The slow SAT(sat lite) test is also an issue.

For the other method all aabb trees are given in worldspace and the overlap quierys are very fast (even faster if quntized). The problem is thatyou have to update the tree when the object transform changes. This means you have to refit the tree bottom up going thrue each leaf and transforming the vertices into worldspace (not every frame but atleast when a overlap is found betwine two objects).

Bullet seems to use this second method tho i only found an example using a static terrain mesh (only refited if the terrain is deformed).

Does anybody have an experience with thees issues and maybe can help me choosing the right one?

[Erwin Coumans]

Bullet seems to use this second method tho i only found an example using a static terrain mesh (only refited if the terrain is deformed).

Does anybody have an experience with thees issues and maybe can help me choosing the right one?

Bullet keeps the AABB tree locally, and transform the convex object into the tree local space and performs a quantized local traversal. There is no support for tree versus tree, unless you use the GIMPACT extension in Extras/GIMPACT, see MovingConcaveDemo. It is better to use convex decomposition and store convex subparts inside a compound. Bullet has a partial refit for local deformations that are compatible with quantization.

You can do the tree versus tree traversal in worldspace, and do a lazy update of the current nodes AABB's (to worldspace) while traversing to avoid a complete refit.

Erwin

[ED209]

You can do the tree versus tree traversal in worldspace, and do a lazy update of the current nodes AABB's (to worldspace) while traversing to avoid a complete refit.

How do i avoid a complete refit? If i need to calculate aabb for the root node i have to update all child nodes. The root node is the first aabb quiery that you normaly do?

I cant do a convex decomposition since my plan is to implement tri vs tri collision atleast for the first version.

[Genscher]

Hello!

It's good to see how bullet improves. That also results in a more closer look for a closer integration into blender, meaning bullet not only as game engine with the possibility to record to IPOs but as main collision engine.

In the moment, every tools has it's own AABB tree etc.

The vital question is now: Is bullet (with gimpact?) now able to handle dynamic moving objects with it's BoundingBoxes? So that the velocity get's calculated into the BB's?

We would love to use bullet for pruning for the start. As result, only BB-potential-colliders should be returned

Thank you very much for Bullet so far!

-------------------------------------------------
Update: It seems that GIMPACT supports moving concave trimeshes! Yeah!

[Erwin Coumans]

How do i avoid a complete refit? If i need to calculate aabb for the root node i have to update all child nodes. The root node is the first aabb quiery that you normaly do?

Various method exist to do an incremental refit, thereby preventing a complete refit. In Bullet, a partial refit is possible, by dividing the tree in subparts, and only updating the subparts.
Other ways are to loosen the tree nodes, based on aabb changes, and only do an entire refit once in a while (kind of a hybrid approach, Pierre Terdiman mentioned this in another thread).

Hello!
It's good to see how bullet improves. That also results in a more closer look for a closer integration into blender, meaning bullet not only as game engine with the possibility to record to IPOs but as main collision engine.

In the moment, every tools has it's own AABB tree etc.

The vital question is now: Is bullet (with gimpact?) now able to handle dynamic moving objects with it's BoundingBoxes? So that the velocity get's calculated into the BB's?

Yes, the tree versus tree can solve this. It is part of GIMPACT, but we plan to move to use Bullet's tree for this. Usually we only update AABB's within the midphase based on positions, not velocities (unless you want continuous collision detection).

We would love to use bullet for pruning for the start. As result, only BB-potential-colliders should be returned

Note that there are 2 separate problems: Bullet's broadphase AABB culling can generate potential overlapping pairs for N objects (each object can be a complex triangle mesh). Within those potential overlapping pairs, the AABB tree (midphase) can deal with two complex objects (trimeshes). The tree versus tree and (partial) refit can help with this (also with deformable objects).

-------------------------------------------------
Update: It seems that GIMPACT supports moving concave trimeshes! Yeah!

The latest GIMPACT 0.2 re-uses many Bullet datastructures, but tree versus tree is still done withint GIMPACT. However, we already plan to add tree versus tree query in Bullet's btOptimizedBvh.

Hope this helps,
Erwin