Collision detection - Concave->Compound objects - Speed

Post Reply
dim_tz
Posts: 11
Joined: Sun Apr 06, 2014 5:27 pm

Collision detection - Concave->Compound objects - Speed

Post by dim_tz »

Hi all,

I'm using bullet in my tracking-pipeline for physics simulation.
The basic setup was done without many problems, and examples with simple objects (e.g. spheres) were running fine.
However, as soon as I started with experimenting with more complex objects, I started having problems.
Please see in the image the case of concave-object (btConvexTriangleMeshShape). (it's an elastic and deformable pipe-like thing)
This object is suppose to be resting on the top cylinder and both cylinders are static objects (btCylinderShape).

Image

With green color you can see the (btCylinderShape) static, cylindrical bases.
With cyan color you can see the actual mesh of the pipe-like object, while with white you can see it's collision shape (btConvexTriangleMeshShape), that has been shifted to a weird location because of AABB overlap.
With red color you can see the AABB box of each object in the scene.

The AABB boxes overlap, so the collision shape of the pipe jumps to some pseudo-random location where there is no overlap of the 2 AABBs
and then falls down, as it is not resting on the cylindrical base any more.
Obviously I need some more detailed method that penalizes collisions and penetration.

Any hint on the direction I should go?
Could I avoid convex decomposition for this problem? (right now, with convex decomposition I'm not sure how to handle the actual physics simulation after collision detection, probably with a btCompoundShape)
Last edited by dim_tz on Tue Sep 16, 2014 12:20 pm, edited 2 times in total.
dim_tz
Posts: 11
Joined: Sun Apr 06, 2014 5:27 pm

Re: Collision detection - Concave objects

Post by dim_tz »

Just for the record, the problem was solved with convex(-like) decomposition.
I tried to do a proper convex decomposition with CGAL in the beginning, but it was too slow for my needs.
Then I started looking into HACD, when I realized that I could have tried something really really simple.
So I manually decomposed my object into parts, based on its skinning weights.
This is not apparent in the image of the previous post, but inside the pipe-mesh there is a skeleton (a long chain with ~35 parts/bones) that drives the deformations of the mesh using Linear Blend Skinning.
One can do a convex-like decomposition by finding the maximum skinning weight of each vertex (thus the most influential skinning weight).
Vertices influenced mostly from the same bone tend to be clustered.
If the skeletonization is good/detailed enough, the decomposition is almost convex, and needs to be done offline only once in the beginning, while having a negligible runtime.
For example, for the case of a pipe, it is a very good approximation.
For the case of hands, you can clearly see some non-convexities, but I think that this is not a major problem for practical scenarios (although this remains to be verified in practise).
If somebody thinks quite the opposite, please share your thoughts.
Have a look at the final decomposition, the above strategy might be of some help for some others in the future.

Image
dim_tz
Posts: 11
Joined: Sun Apr 06, 2014 5:27 pm

Re: Collision detection - Concave objects

Post by dim_tz »

In case of usual/light interaction between compound objects (e.g. hand touching the object with 4 fingertips) things are quite nice,
and speed is reasonable, although, as expected, it drops when touching points increase.

However, it seems that in case of *very* strong interaction between objects, there is a big bottleneck.
For example in the illustrated case, there are so many touching points, that the broad-phase is most probably triggered for many/most parts,
and the narrow-phase creates a big bottleneck.

Image

Is there any way to create a hierarchy of nested AABB trees in order to accelerate collision checks and avoid the costly narrow-phase as much as possible?
Or is there any other idea serving this purpose?

Thanks!
dim_tz
Posts: 11
Joined: Sun Apr 06, 2014 5:27 pm

Re: Collision detection - Concave->Compound objects - Speed

Post by dim_tz »

I forgot to mention that the meshes are pretty large, so maybe there is a better strategy for such cases, according to your experience.

The hands have ~10.000 triangles and ~20.000 vertices, while
the fat pipe has @6.000 triangles and ~12.000 vertices.

Both the hands and the pipe are compound objects.
The hand is a compound object consisting of btBvhTriangleMeshShape (I consider them static for each frame), while
the pipe is a compound object consisting of btConvexTriangleMeshShape (I want to see if the object is being held firmly by the hands or if it is falling).

Just a sing stepSimulation takes ~ 7sec in cases of strong interaction like in the last image, which is kind of prohibitive..
dim_tz
Posts: 11
Joined: Sun Apr 06, 2014 5:27 pm

Re: Collision detection - Concave->Compound objects - Speed

Post by dim_tz »

OK, so the only solution is to reduce the number of triangles to be processed.
That means that even after convex decomposition a subsequent step that finds the convex hull of each high-resolution convex mesh has to be followed.
This convex hull (consisting of much fewer points/triangles than the original mesh) is the one actually taking part in the physics simulation.
So, even though in my case there is no demand for real-time runtimes, I had to follow the classic strategy that is used in animation/games/etc:
The physics-world is separate from the visual-world and of much lower resolution, so that computations are tractable.
Screenshot:

Image
Post Reply