Concave trimesh contact points reduction

[Hanz]

Is there any standard way to do contact points reduction for concave
triangle meshes?

In my simulator, the board-phrase/middle-phrase collision module can
provide me the overlapped triangle pairs, and my problem is how to
find the reasonable/reduced contact points for further collision
response (I want to switch to Bullet, but you know #"# .. ).

In Bullet, for convex primitives, libCollision uses btManifoldPoint &
btPersistentManifold to maintain the reduced contact points. However,
since the cache size is limited to 4 (which is quite reasonable for convex
mesh), it is difficult to handle concave-concave triangle meshes
contact points. It seems that ODE (the new tritri algorithm contributed
by GIMPACT's author) get the contact point approximations using some
special rules. And some other engines even ignore concave triangle
mesh for simplicity & speed.

In my simulation, the default collision shapes are exact concave
triangle meshes (unfortunately ) and can I extend the method used
by Bullet to handle such a situation (say, change cache size from 4 to 16
or 64) ? If not, must I dig into GIMPACT library to get the necessary
information for contact point reduction?

Thank you for your time.

[Erwin Coumans]

You can use multiple contact manifolds for concave versus concave:
The optional GIMPACT integration in Bullet uses an array of contact manifolds. See MovingConcaveDemo, and Bullet/Extras\GIMPACTBullet\btConcaveConcaveCollisionAlgorithm.cpp
One approach you can try is to cluster/group contact points based on their contact normal. Then keep a separate contact manifold for each contact group (with a 'fuzzy' similar contact normal) (each manifold reduces to 4 points).

In my experience, a single contact manifold behaves really well in practice for concave compounds (btCompoundShape with multiple convex shapes generated by convex decomposition). If your concave triangle meshes have volume, you could try to create a tetrahedralization as convex decomposition.

Hope this helps,
Erwin

[Hanz]

You can use multiple contact manifolds for concave versus concave:
The optional GIMPACT integration in Bullet uses an array of contact manifolds. See MovingConcaveDemo, and Bullet/Extras\GIMPACTBullet\btConcaveConcaveCollisionAlgorithm.cpp
Erwin

Thank you for the pointer, but I checked them before I post my
question here.

Actually I managed to change the demo code to work with my concave
mesh, and I almost works. However, I am still not sure the contact
manifold array:

Code: Select all

    btAlignedObjectArray<btPersistentManifold*>	m_mainfoldsPtr;

should be optimized again or not. Here "optimize" is related to your
following explanation, that is, does the array have any optimal size ?

One approach you can try is to cluster/group contact points based on their contact normal. Then keep a separate contact manifold for each contact group (with a 'fuzzy' similar contact normal) (each manifold reduces to 4 points).
Erwin

Yes, that is what I am try to do. Also the maximal occupied area should be
consider in my mind. In Game Programming Gems, Pierre Terdiman
purposed some basis concepts for this issue, but I did not see any
applicable implementation.

I will check it.

BTW, when I running my updated MovingConcaveDemo, sometimes some
of the concave objects/meshes were pulled together, which I can not
explain(same behavior in ODE was found). But I think this has little
to do with the contact point generation, maybe this is caused by the
wrong constraints added by collision response.

In my experience, a single contact manifold behaves really well in practice for concave compounds (btCompoundShape with multiple convex shapes generated by convex decomposition). If your concave triangle meshes have volume, you could try to create a tetrahedralization as convex decomposition.

Erwin

Yes, I've noticed that you recommend the convex decomposition method
several time in this forum. Actually I studied the demo carefully but
unfortunately I found it does not meet my simulation needs.

In my simulation the concave information plays an important role.
For an example, suppose a ball is rolling on a continuous hill-plane, the
trajectory will be different if the hill-plane mesh info changes. Maybe
this is different from real-time animation domain.

Thank you for your suggestion.

[Erwin Coumans]

Actually I managed to change the demo code to work with my concave
mesh, and I almost works. However, I am still not sure the contact
manifold array:

Code: Select all

    btAlignedObjectArray<btPersistentManifold*>	m_mainfoldsPtr;

should be optimized again or not. Here "optimize" is related to your
following explanation, that is, does the array have any optimal size ?

Could you give more details about what exactly not works in 'almost works' ?
The optimal size is an interesting topic. I would definately include the contact manifolds with the deepest penetration. Adding more manifolds will introduce a trade-off between performance versus quality, so its size can become a tuning parameter.

BTW, when I running my updated MovingConcaveDemo, sometimes some
of the concave objects/meshes were pulled together, which I can not
explain

Does the unmodified MovingConcaveDemo using GIMPACT have the same issue?

In my simulation the concave information plays an important role.
For an example, suppose a ball is rolling on a continuous hill-plane, the
trajectory will be different if the hill-plane mesh info changes.

I'm not sure what this means, can you please explain more about this?
Thanks!
Erwin

[Hanz]

Could you give more details about what exactly not works in 'almost works' ?

Sorry for my poor wording... I will try to explain the problem.

When I run the MovingConcaveDemo, I found that if I shoot the
concave mesh several times within a short time (push "." key quickly ),
then the meshes will be pulled together. The added constraints are
quite strong and I can not even separate the individual object by mouse
dragging.

Here is the steps for a quick test:

1. Compile the MovingConcaveDemo.exe

2. Quick press the "." key to shoot the meshes
(say, 3 times within one second)

3. The three objects will be pulled/glued together, and work like they are
just one object.

In my customized demo, I saw the same behavior.

BTW, if I shoot the mesh using normal speed. the problem disappears.
Also I do not see any problem when I shoot non-concave meshes
like boxes (by mouse right click).

I am just wondering that maybe this is caused by discrete collision
detection, possible contact points were lost if the speed is an issue?
Or, do we have warm-up or object creation/management problems here?

The optimal size is an interesting topic. I would definitely include the contact manifolds with the deepest penetration. Adding more manifolds will introduce a trade-off between performance versus quality, so its size can become a tuning parameter.

Which is quite true in my mind.

The problem is, I am not sure GIMPACT's

Code: Select all

//! Merges duplicate contacts with minimum depth criterion
void gim_merge_contacts(GDYNAMIC_ARRAY * source_contacts,
					GDYNAMIC_ARRAY * dest_contacts);


//! Merges to an unique contact
void gim_merge_contacts_unique(GDYNAMIC_ARRAY * source_contacts,
					GDYNAMIC_ARRAY * dest_contacts);

can do the reduction/optimization as you mentioned before.
My guess is not, since the low level CD library can not get enough
information to implement such kind of optimization.

Indeed here finding the trade-off is quite difficult in my mind.

BTW, is there any docs/papers for GIMPACT's interals?

Does the unmodified MovingConcaveDemo using GIMPACT have the same issue?

Yes. I just checked out the newest SVN trunk rev, the problem is still
there.

I post the steps above, which will generate the abnormal behavior.
If you have time please have a look at it.

In my simulation the concave information plays an important role.
For an example, suppose a ball is rolling on a continuous hill-plane, the
trajectory will be different if the hill-plane mesh info changes.

I'm not sure what this means, can you please explain more about this?
Thanks!
Erwin[/quote]

Well, maybe my understanding of convex decomposition is wrong...
But as I said in my previous post, my collision shapes are all triangle
meshes. In my simulator there is no assumption about the mesh shape.
Even the ground plane is modelled as Hill-Plane, which is constructed by
lots of triangles.

In my mind, the convex decomposition will try to keep the important
structural features and less important one will be discarded. Is this true?
Since I can not make any assumption about the convexity about my
object mesh model, then I can not assure that the new generated
convex shapes will give me the desired results.

In short, my problem is, I want to use the concave shape information to
get the accurate result and I am worrying about the convex decomposition
generated meshes can not provide me good enough approximation.

Actually I am not a game engine builder. what I am now doing is trying to
build my robotics simulator. Speed will be definitely a big plus but the
accuracy is the most important thing.

Please do correct me if I am wrong and I do appreciate your opinion
on how to build the *accurate* dynamics simulator.

Thank you for your time.

[topcomer]

You can use multiple contact manifolds for concave versus concave:
The optional GIMPACT integration in Bullet uses an array of contact manifolds. See MovingConcaveDemo, and Bullet/Extras\GIMPACTBullet\btConcaveConcaveCollisionAlgorithm.cpp
One approach you can try is to cluster/group contact points based on their contact normal. Then keep a separate contact manifold for each contact group (with a 'fuzzy' similar contact normal) (each manifold reduces to 4 points).

In my experience, a single contact manifold behaves really well in practice for concave compounds (btCompoundShape with multiple convex shapes generated by convex decomposition). If your concave triangle meshes have volume, you could try to create a tetrahedralization as convex decomposition.

Hope this helps,
Erwin

I've got a tetrahedralization of my object and at the moment I'm considering using concave vs concave GImpact trimeshed collsion detection. Should I change my approach then?