Bullet colission with Enviroments

[sukoy]

What bullet uses for collision with enviroments?

[Erwin Coumans]

For environments represented as 3d concave triangle meshes, Bullet uses a bounding volume hierarchy, an AABB tree with several improvements (compressed nodes, parallel SPU support, real-time deformation). There is also support for the special case of heightfields.

You can use btBvhTriangleMeshShape for general concave 3d environments, see Bullet/Demos/ConcaveDemo, or btHeightfieldTerrainShape for 2d heightfields, see VehicleDemo.

Hope this helps,
Erwin

[sukoy]

For environments represented as 3d concave triangle meshes, Bullet uses a bounding volume hierarchy, an AABB tree with several improvements (compressed nodes, parallel SPU support, real-time deformation). There is also support for the special case of heightfields.

You can use btBvhTriangleMeshShape for general concave 3d environments, see Bullet/Demos/ConcaveDemo, or btHeightfieldTerrainShape for 2d heightfields, see VehicleDemo.

Hope this helps,
Erwin

thx a lot !!!
I have a doubt,do you think that bullet implements Dynamic Plane Shifting BSP for concave 3d enviroments in it's AABB tree?
I'm going to implement a new Collision System and I'm studing "Colision Detection in Interactive 3D Enviroments" by Gino van den Bergen and Stan Melax BSP. Can I suppose that it's the best algorithm for collision with concave meshes? if it isn't and bullet doesn't use it, can you suggest me a paper or book in which i can find the method implemented by bullet for its AABB tree?
I think that for racing games 2d heightfields collision is the most performant algorithm...but I need a colision system that works fine in all cases and I suppose, after I studyed Melax BSP, that it may be the best!!I think I can adapt it with convex/concave polyhedras.

Thanks in advice.

[sukoy]

Hi,
I have just finished to study the demo and the other that you suggested me,don't read my previous post
In appConcaveDemo you build AABB tree from btBvhTriangleMeshShape and collisions are detected by "Sweet and Pruine" algorithm.In appVehicle demo you have a 2D height map from which you build btBvhTriangleMeshShape.I also studied BSPDemo, you Load Quake BSP and convert all brushes in static concave shapes.
Regarding the library, it's a fantastic and elegant job, but my goal is a Collision System on Nintendo DS,so you'll understand that i need a fast alghorithm that doesn't use Minkowski Sum explicitly but that has "support mapping". From my study of Melax BSp I can detect a collision with enviroments in O(logn) (the height of tree), the tree must be balanced. All that i need is the penetration depth to calculate the response of collision.

I tried to send an e-mail to Stan Melax to understand if he has ever used his BSP with open enviroments.

What do you think about Melax BSP?is it a robust algorithm?

Thanks in advice.

[Erwin Coumans]

Regarding the library, it's a fantastic and elegant job, but my goal is a Collision System on Nintendo DS,so you'll understand that i need a fast alghorithm that doesn't use Minkowski Sum explicitly but that has "support mapping".

Bullet uses a support mapping, it doesn't build the Minkowski Sum explicitly. Have you tried to use Bullet on a bsp level using convex decomposition (as in the BspDemo)? Is it too slow?

I'll ask Stan to comment on his approach,
Thanks,
Erwin

[melax]

AABB trees can be a suitable option too. Any hierarchical spatial structure can provide log(n) performance for collision queries.

The plane shifting bsp traversal was origianlly designed for translational sweep tests. There is some approximation (false positives) in the result since the separating axis can only be a plane normal taken from a node in the tree. Hence, additional bevel planes are used to minimize amount of error that can occur. The result is that its adaquate for many types of collision checks including character to environment navigation. For more accurate collision of an object (eg rigid body) against the environment, the technique can still be applied to conduct a "broadphase" query and determine which convex cells of the environment potentially collide with the object. At this point, gjk or something else can be used to find the separating axis.

The decision to use bsp traversal should depend on whether or not you use BSP trees in your game. I was using BSP trees for a demo since I was doing CSG (real time boolean) operations. This is implemented by merging trees together. Since I already have the spatial structure sitting around, I use it to check collisions between rigid bodies and the environment. Obviously, in this case it makes no sense to try and maintain yet another structure such as AABB and try to update it each time the player shoots a hole in the wall.

BSPs work best when you know you will have manifold geometry. Having this means that you dont need to keep the mesh data around (for some applications). You only need the planes at runtime for basic collision. Doing BSPs isn't easy. Numerical robustness can be an issue when compiling a mesh into a BSP tree. (Robustness isn't a problem during tree traversal.) To really get the most out of BSPs (naylor's tree compilation heuristics, adding bevels, geomod, full collision) you need to also know the convex volume at each node. I use a pointerless winged edge structure for these so I can boolean them quickly.

What I just described is what I do in a little puzzle demo "teeter". (shameless plug) In the room with the spider you can shoot holes in the floor. I turned off being able to shoot holes elsewhere in the game since that would take away from the objective of the game itself.

In comparison to bsp tech, AABB trees are really easy. You wont have to struggle with any numerical robustness issues. Polygon soup isn't a problem Constructing good AABB and OBB trees can sometimes be difficult when the polygons vary dramatically in size (big floor and walls, smaller detatils throughout level). Tesselation can be helpful.
The original mesh must be kept around since when you get to the leaves of the aabb tree, you then have to test the actual primitives (triangles or convex polyhedra).

I wouldn't discourage the use of BSP trees, however, I would suggest that AABB is an easier starting point.

Since its not an easy bit of code to develop, I've been talking with Erwin about the idea of putting the bsp geomod tech into a bullet "destruction" module/lib or demo. There would have to be some code cleanup that would have to occur first.


my 2c

[sukoy]

Hi everyone...this is for me a low priority task so my my work proceeds slowly :p

After having implemented the bsp tree building, i have test it with simply test for inclusion/exclusion of a poit in a mesh and it works fine.Now i'm devoting to ray test with bsp. Gino van den Bergen in his book "Collision Detection in Interactive 3D Environments" propose a test to determining the first time of impact of a moving object.It's quite similar to melax test,only difference is :melax segments ray dir with shifting planes between p0-p1 and determines 4 points3d while gino segments a ray between 0-1 to find the first time of impact.Both test works fine,now i need to find the normal of impact,mealx in his bspfeedback propose this test

Code: Select all

  // BSP collision detection with plane shifting
  HitCheckBSP(node n,vector v0,vector v1,vector current_normal)
    int hit = 0
    vector w0,w1
    if(n is an empty leaf)
      return 0
    if(n is a solid leaf)
      Impact = v0  // point of impact
      impact_normal = current_normal;
      return 1
    // we use new_normal if w0 doesn't equal v0
    vector new_normal = (dot(n->normal,v1-v0)>0)? -n : n
    if(dot(n->normal,v1-v0)>0)
      if(segmentunder(n shifted upward,v0,v1,&w0,&w1))
        hit = HitCheckBSP(n->under,w0,w1,((w0==v0)?current_normal:new_normal));
        if(hit)
          v1 = Impact
      if(segmentover(n shifted downward,v0,v1,&w0,&w1))
        hit |= HitCheckBSP(n->over,w0,w1,((w0==v0)?current_normal : new_normal));
      return hit
    else
      same as above but in the other direction
  End

in this test melax get new normal each time the ray is segmented by a plane otherwise used parent's normal.I don't understand why he negates normal if (ray dot node's normal)>0 ,this means if the ray and the plane have same direction
************************************|
************************************|plane
****************************** n^ |
************************** <---------- |
************************************|
************************************|
********************************<----|------ raydir
************************************|
right?
I try to implement this test in gino's function

first-hit.jpg (44.03 KiB) Viewed 9179 times

like for melax tp is a lower bound for subinterval [t0,t1] so the node that have mininum tp is the best candidate to get normal of collision.There is only one problem it doesn't work very good in some case the result normal is wrong.

Could you give me tips to solve my mistake?

If it can be useful I post my code .

thankes in advice