Hi there,

i am currently in the process of implement a algorythm to calculate 2D contact points for two convex polygons (2 oriented boxes for now).

The basic idea is to clip the incident polygon face (line segment) to the reference polygon side face planes and my implementation goes as follow:

1.) Use separating axis theorem to get the collision normal and penetration depth.

2.) Determine which is the incident and reference body (Reference is body A and incident is body B always)

3.) Find the support point for the incident body along the inverted normal (Incident support)

4.) Find the support point for the reference body along the normal (Reference support)

5.) Find the incident edge (line segment) from the incident support point by finding the second vertex which is most perpendicular to the normal from the next or previous vertex.

6.) Find the reference edge (line segment) from the reference support point by finding the second vertex which is most perpendicular to the normal from the next or previous vertex.

7.) Get perpedicular left and right normal (right is (-y, x) left is (y, -x))

8.) Construct two planes for the the reference edge vertices (Plane 1 distance = vertex dot right normal, Plane 2 distance = vertex dot left normal)

9.) Clip the incident line segment against the two planes

10.) Keep only the vertices which penetrates or touches the reference polygon - thats the contact point(s)

I have already implemented part 1-8 and these works fine so far, but i am really unsure about the clipping planes.

Is it correct to just use the perpendiculars of the normal which located on the reference edge vertices? Or is there some better/faster way.

Of course the last thing i need to do is the actual clipping, but this seems to be very straight forward - should be easy to implement it right?

For better explanation i made two images - see attachments (For the first case the clipping would do nothing, because the vertices are on the other side of the plane, therefore my contact points whould just be the incident edge vertices.)

Would be really great is you guys can help me out with that.

Greetings,

Final

Looks good! I am not sure why you need step 4) and 5) though. The SAT should give you the reference face (which can come from either A or B) and then you can find the incident face by finding the most anti-parallel face on the other body (simply the smallest dot product). From there you build the two clipping planes and clip.

Additionally you can add some clipping IDs which can be used for matching impulses in the next frame for warm-starting.

Looks good! I am not sure why you need step 4) and 5) though. The SAT should give you the reference face (which can come from either A or B) and then you can find the incident face by finding the most anti-parallel face on the other body (simply the smallest dot product). From there you build the two clipping planes and clip.

Additionally you can add some clipping IDs which can be used for matching impulses in the next frame for warm-starting.

Yeah, you are right 4 and 5 are not really needed, because the edge face/normal are built for the sat already.

But what about if you have a oriented pox and a triangle polygon? Would the same method work, because there is no real anti parallel face?? Hmm oh ok, now i understand the reason why clipping is needed - the contact points must be contained in the reference body! Then the approach finding the most anti parallel face works even with triangles or more complex polygons. But, what about the second clipping plane? This must be the opposite normal from the anti parallel face or what?

Btw. my description is somehow wrong, the support point normals must be the opposite (incident is just the normal and reference is the inverted normal) - my sat relative offset was wrong all the time.

Say n=(x, y) is the reference normal. Then you build exactly two clipping planes as you described correctly in you first post.

Say n=(x, y) is the reference normal. Then you build exactly two clipping planes as you described correctly in you first post.

Ok, then the following images are wrong right? Normal was found on the incident triangle, but was been used on the reference face (orange line)

It should be the clipping planes perpendicular to the reference face normal (blue line), not the actual normal found in the sat, right?

See the images for illustration.

I have implemented it, but it generates wrong clipping planes for triangles. Box vs box planes seems to be fine so far.

To show you what i mean, i uploaded my simple visualized html5-app to see it in action: http://jsfiddle.net/cxzyL/1/

It would be really great if someone can help me to get this working for the wrong cases (triangles vs box and triangle vs triangle).

Hmm, I wish I had time to dive into that JSFiddle code but I can't. It looks like from the picture (if I'm seeing this right) you tried to make clipping planes by looking at adjacent edges to the reference face.

Instead of this, take the reference face plane and rotate it CCW 90 degrees. This will give you one clipping plane, that is a side plane for the reference face. However, the plane is currently intersecting the reference face at it's center. Assuming you stored your polygon vertices in CCW order, move the plane halfway across the reference face towards the second point that defines the reference face.

Then, make a copy of this plane and negate the normal and move it such that it lays upon the first point that defines the reference face. This ensures that each plane intersects the two end points of the reference face at a 90 degree angle.

This is all implemented in Box2D *Lite* in I think Collide.cpp.

Just to be clear I drew some example reference polygons and their side planes:

Ok, moment... you say i should just take the perpendicular of the reference face normal, based on the end points of the edge? Even when i have complex polys as reference bodies? Hmm, i had already made this yesterday and thought it was wrong -.-

Btw. you dont have to read all the code - the actual code for calculating the edges and support points are at the bottom - line 765

But i am grateful for all the help i got so far from you guys - it seems that you and dirk are pioneers at that field ;)

Hopefully i get it working today.

That was fast: http://jsfiddle.net/cxzyL/5/

Now i code the clipping now.

So clipping is implemented: http://jsfiddle.net/cxzyL/6/

Seems to be okay i think?