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.

## Concave trimesh contact points reduction

- Erwin Coumans
- Site Admin
**Posts:**4232**Joined:**Sun Jun 26, 2005 6:43 pm**Location:**California, USA-
**Contact:**

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

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

Thank you for the pointer, but I checked them before I post myErwin Coumans wrote: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

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;
```

following explanation, that is, does the array have any optimal size ?

Yes, that is what I am try to do. Also the maximal occupied area should beErwin Coumans wrote: 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

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.

Yes, I've noticed that you recommend the convex decomposition methodErwin Coumans wrote:

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

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
- Site Admin
**Posts:**4232**Joined:**Sun Jun 26, 2005 6:43 pm**Location:**California, USA-
**Contact:**

Could you give more details about what exactly not works in 'almost works' ?Hanz wrote: 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:should be optimized again or not. Here "optimize" is related to yourCode: Select all

`btAlignedObjectArray<btPersistentManifold*> m_mainfoldsPtr;`

following explanation, that is, does the array have any optimal size ?

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.

Does the unmodified MovingConcaveDemo using GIMPACT have the same issue?BTW, when I running my updated MovingConcaveDemo, sometimes some

of the concave objects/meshes were pulled together, which I can not

explain

I'm not sure what this means, can you please explain more about this?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.

Thanks!

Erwin

Sorry for my poor wording... I will try to explain the problem.Erwin Coumans wrote:

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

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?

Which is quite true in my mind.Erwin Coumans wrote:

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.

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);
```

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.

I'm not sure what this means, can you please explain more about this?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.

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.

### Re:

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?Erwin Coumans wrote: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