Collision between concave objects

[atul]

Hi,
I need to find collision between concave objects. I am currently using PhysX for my research.
In last few days after reading many postings and articles on various forums I discovered following things (may be obvious to most of you but being new to this area I had to put efforts)
1. The best way to detect collision between concave objects is to decompose each concave object into largest convex subparts and glue them. After this most of the physics engine can take care.
2. Another way is using pmaps (here I am specific about PhysX). Dearth of sample codes as it is deprecated, led me to think if really it can be used or not.
I think that if my concave objects change during the runtime I need to have a good convex decomposition algo at place. My questions are following -
a. Is there any library for convex decomposition that handles triangulated data (*.stl file specifically). I saw John Ratcliff's http://codesuppository.blogspot.com/200 ... ition.html which can be used for wavefront obj files and many more. If there are some more libraries kindly let me know so that I can compare and select the one that suits me.
b. Just as a prototype, I tried to use pmap. I don't know, why even after loading pmap into the NxTriangleMesh my parts are not colliding. Can anybody help me to figure out possible reasons for the problem. I am currently looking at Aegia's documentation and http://www.boolean.name/archive/index.php/t-1830.html.
I apologize for a long post and appreciate for your time,

sincerely,

-Atul

[Erwin Coumans]

a. Is there any library for convex decomposition that handles triangulated data (*.stl file specifically). I saw John Ratcliff's http://codesuppository.blogspot.com/200 ... ition.html which can be used for wavefront obj files and many more. If there are some more libraries kindly let me know so that I can compare and select the one that suits me.

Indeed, for real-time applications it is recommended to use compounds of convex shapes to approximate moving concave objects. Use John Ratcliff's convex decomposition, or check out OpenConvexDecomposition3DObjects.

b. Just as a prototype, I tried to use pmap. I don't know, why even after loading pmap into the NxTriangleMesh my parts are not colliding. Can anybody help me to figure out possible reasons for the problem. I am currently looking at Aegia's documentation and http://www.boolean.name/archive/index.php/t-1830.html.

PMaps are deprecated, I'm not sure if you can get support for that anywhere. It seems a method similar to signed distance maps. You can find a free open source implementation of SDM in the OpenTissue physics library. You can also consider GIMPACT moving concave triangle mesh, it is part of Bullet (see MovingConcaveDemo). However, if possible I recommend going for convex decomposition, either automatic or manual.

Hope this helps,
Erwin

[atul]

Thanks a lot for the help...
I'll try implementing convex decomposition now.

-Atul

[cycloverid]

This thread leads directly into a problem I have been experiencing.

I have been implementing concave polygons in my physics engine as minimal convex decompositions as you describe. It took a long time to program so I'm glad this is an accepted solution to handle concave geometry!

Anyways, my debacle is this: When an arbitrary polygon that I will call A slides up against the surface of a concave polygon which I will call B, A experiences a stutter when sliding passed a split in the concave polygon where two convex sub-polygons were made. This is caused by allowing a penetration depth. A thinks it is colliding with one of the inner edges of one of the sub-polygons of B. Perhaps my explanation is a bit confusing so I will include a drawing to assist in clarifying the problem.

I can think of a solution, such as creating a boolean for each edge of a polygon which stores whether it is an inner edge or outer edge. For convex polygons they would be all outer edges. For concave polygons, each convex decomposition set would store whether the edge was an outer edge, and whether it was an inner edge. If it is an inner edge, during the SAT minimum penetration depth step, the algorithm would skip inner edges and only consider outer edges.

However, if there is a better solution to this problem I would love to hear it, since this problem occurs in stacked rigid bodies as well ( when moving from the edge of one to the other when they are in close proximity ).

I appreciate any feedback!