🔒 Locked

Generating contacts from EPA result (normal + depth)

Started by Bow_vernon Dec 12, 2016 at 3:08 PM 3 replies 5.8k views

Original Post

Dec 12, 2016 at 3:08 PM

I've been working on a simple physics engine in 2D, but will translate to 3D after everything works right. Right now I have GJK for collision detection, which will return a 2-Simplex (a triangle) containing origin when the two shapes are colliding. If collision is positive, I run EPA using the returned simplex for initializing polytope. When the EPA terminates successfully, it will give me collision normal and depth, which when combined would give me enough information to separate the two shapes.

But now I need to generate contact points. What suitable method would be best to use with GJK+EPA? in the past, I did it by identifying the closest feature of both shapes (most aligned "face" with collision normal), and clip them against each other. But it was when I was using SAT algorithm, and I used special data structure containing a shape's feature (Edge+Face List, mainly. It was 3D. Also it only supports box so far). But I'm looking for a simpler method now, since GJK+EPA are more generic than SAT, I lean more towards them. Also, I didn't store feature(face/edge) in the Shape data structure, only its vertex (in clockwise order, also they must be convex). Because the "Feature" are so diverse (in 3d, we can have triangle-face, quad-face, planar_polygon-face, even curved surface as a "face/feature" of spherical shape).

TL;DR;

So what is the most suitable method for generating contacts when one is already using GJK+EPA?

Below is some of my WIP

3d physics engine. Support box only so far. Using SAT for collision detection, and use some feature identification + clipping to generate contacts.

based of Box2D-lite (it's basically 3D version of Box2D-lite). Has contact caching, support warmstarting, also support stacking (the number can get

quite high depending on the simulation rate and the solver iteration). Stacked boxes wiggle around for a while before resting in peace forever.

2d implementation of GJK + EPA.

Red and White shapes : the shapes being tested for collision

Yellow triangle : Simplex returned by GJK

Red-Purplish shape : 2D Polytope generated by EPA

Green dot : origin

I didn't show the collision normal + depth, but it's there.

Irlan Robson

Dec 12, 2016 at 3:48 PM

What suitable method would be best to use with GJK+EPA?

The simplest method is to add up to 4 contact points to a manifold each frame. Like Bullet does. When there are 4 contact points and a new point is about to be added then the combination of contact points that maximizes the contact area in the manifold is mantained. IIRC there is some code at btPersistentManifold.cpp implementing this algorithm. The downside for the contact solver is contact points proximity are matched against a distance tolerance. Not against the features that built them. Ocasionally (specially in stacking scenarios) the consequence is bad manifold stability.

I switched to SAT and clipping for contact generation since some time ago and can recommend. This is the common method used these days.

Bow_vernon

Dec 13, 2016 at 3:39 AM

What suitable method would be best to use with GJK+EPA?

The simplest method is to add up to 4 contact points to a manifold each frame. Like Bullet does. When there are 4 contact points and a new point is about to be added then the combination of contact points that maximizes the contact area in the manifold is mantained. IIRC there is some code at btPersistentManifold.cpp implementing this algorithm. The downside for the contact solver is contact points proximity are matched against a distance tolerance. Not against the features that built them. Ocasionally (specially in stacking scenarios) the consequence is bad manifold stability.

I switched to SAT and clipping for contact generation since some time ago and can recommend. This is the common method used these days.

question. Do I need to always start with 4? I mean wasn't it supposed to start with one point, building the manifold over time? how do I add 4 points each frame?

Well, it seems that I have to do feature clipping again. Seems like there's no other way. But do you know how bullet does it?

Irlan Robson

Dec 13, 2016 at 12:31 PM

Oops, I wrote way too fast, sorry.

No, EPA finds 1 point each frame. So yes, one contact point can be added each frame. When there are more than 4 points you need reduce to 4 points. That's how Bullet does.

Dirk discussed state-of-the art contact creation and the reduction algorithm was mentioned in his talk at the GDC:

http://box2d.org/files/GDC2015/DirkGregorius_Contacts.pdf

Bow_vernon

Dec 15, 2016 at 12:26 PM

Oops, I wrote way too fast, sorry.

No, EPA finds 1 point each frame. So yes, one contact point can be added each frame. When there are more than 4 points you need reduce to 4 points. That's how Bullet does.

Dirk discussed state-of-the art contact creation and the reduction algorithm was mentioned in his talk at the GDC:

http://box2d.org/files/GDC2015/DirkGregorius_Contacts.pdf

I decided to implement the one shot manifold as described in that paper, and it works nice!! I haven't implement contact reduction, but I will once I move to 3D, I guess. Thanks a lot pal for your contribution! Wish I could +1 you again.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.