Contact generation for meshes

Here is another paper I wrote some time ago. If you are struggling with invalid contacts against internal edges in your rigid body simulation, this one might help.

http://www.codercorner.com/MeshContacts.pdf

As usual, the bitcoin tip jar is here if you like what you read :)

5 Responses to “Contact generation for meshes”



  1. Dennis Says:

    Hi Pierre, great to see this technique described again. We did indeed use this at Meqon and I still think this is the best way to tackle the problem. Our biggest issue with it was high speed objects that generate a ton of speculative contacts. We did not implement your optimizations in section 5, but IIRC all the “voided features” were added before considering any of the vertices, which also gives a correct result. (Hence, in figure 7, T2 would always be added to V before considering Cp2 and Cp3)

  2. Erin Says:

    Thanks for writing this up Pierre! I like this holistic, feature based approach. And yes, tolerances and magic numbers are awful. Have you extended this technique to polytopes? Regardless, I plan to try this in Box2D.

    I currently have a system that works fairly well for convex polygon versus line segment chains, with the added complexity of handling double-sided collision on the chains. However, that system only considers a single segment and the immediate neighbors. This gets to be error prone when the line segments are small compared to the polygon.

  3. Kido Says:

    Is this algorithm implemented in Physx 3.3?

  4. Raigan Says:

    Awesome paper, thanks for writing it! :)

    A cheap-ass way to get similar results, without having to explicitly dealing with different features, is to find the single closest point on any triangle, and deal with that single contact point (push the sphere out of it, then repeat, finding the new single closest point and pushing out etc).

    The nature of distance (or something) means that if there’s a face contact, it must be the closest feature (thus edge contacts get thrown out automatically).

  5. Richard Says:

    Great write up. I’m trying this now. You don’t explain how you suggest tracking the void set or how to search the void set.

    I’m curious if you took a fancy approach to avoid adding duplicates or to handle added edges differently from added vertices?

    I’m inclined to just absorb the cost of duplicates in favor of anything fancy but would love to hear your thoughts.

shopfr.org cialis