Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Polygon vs polygon contact points madness


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
11 replies to this topic

#1 Finalspace   Members   -  Reputation: 455

Like
0Likes
Like

Posted 21 July 2014 - 01:31 PM

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

Attached Thumbnails

  • contact_points_clipping_planes.png
  • contact_points_clipping_planes_flip.png

Edited by Finalspace, 27 July 2014 - 02:15 PM.


Sponsor:

#2 Dirk Gregorius   Members   -  Reputation: 1131

Like
0Likes
Like

Posted 21 July 2014 - 01:56 PM

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.


Edited by Dirk Gregorius, 21 July 2014 - 01:57 PM.


#3 Finalspace   Members   -  Reputation: 455

Like
0Likes
Like

Posted 21 July 2014 - 03:31 PM

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.


Edited by Finalspace, 21 July 2014 - 03:34 PM.


#4 Dirk Gregorius   Members   -  Reputation: 1131

Like
0Likes
Like

Posted 21 July 2014 - 04:03 PM

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



#5 Finalspace   Members   -  Reputation: 455

Like
0Likes
Like

Posted 21 July 2014 - 11:41 PM

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.
 

Attached Thumbnails

  • contact_points_clipping_planes_triangles_wrong2.png
  • contact_points_clipping_planes_triangle_wrong.png


#6 Finalspace   Members   -  Reputation: 455

Like
0Likes
Like

Posted 23 July 2014 - 07:47 AM

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).



#7 Randy Gaul   Members   -  Reputation: 1173

Like
0Likes
Like

Posted 23 July 2014 - 12:22 PM

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:

 

ej5E3Vw.png


Edited by Randy Gaul, 23 July 2014 - 12:27 PM.


#8 Finalspace   Members   -  Reputation: 455

Like
0Likes
Like

Posted 23 July 2014 - 12:53 PM

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.


Edited by Finalspace, 23 July 2014 - 01:46 PM.


#9 Finalspace   Members   -  Reputation: 455

Like
0Likes
Like

Posted 23 July 2014 - 02:06 PM

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

 

Now i code the clipping now.



#10 Finalspace   Members   -  Reputation: 455

Like
0Likes
Like

Posted 23 July 2014 - 03:45 PM

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

Seems to be okay i think?



#11 Finalspace   Members   -  Reputation: 455

Like
0Likes
Like

Posted 27 July 2014 - 02:43 PM

Its not working, i implemented it now in java and the contact points was generated like it was in my sample application from my last post.

BUT, this was all bullshit - nothing had work, boxes was falling through line segments, boxes was overlapping - the contact points was absolutely wrong.

So then i analyzed box2d lite a bit and the contact points generated there are completely different from my approach - now i am back to at the very start :-(

 

I searched a lot for a different approaches and found this: http://www.randygaul.net/2013/07/16/separating-axis-test-and-support-points-in-2d/

Seems to be very promising and of course i implemented the support point distance approach, because these was easier than projecting every vertex to the normal - and the sat-test itself works perfectly. But in some cases the used reference edge is on the back, not in the front - which results in support points which are on the back from the other as well - which are wrong.

 

I have 2 cases, one which works:

 

satsupport_correct.png

 

and one which are wrong:

 

satsupport_wrong.png

 

The red point are the support point on the incident body and the blue line with the numbers are the reference face.

As you can see, it should be just inverted, the reference face must be on the opposite side and the support point will be behind that face.

 

My code is brutally simple (There must be something missing!):

function findSupportPoint(body, normal) {
    var best = normal.dot(body.vertices[0]);
    var maxIndex = 0;
    for (var i = 1; i < body.vertices.length; i++) {
        var proj = normal.dot(body.vertices[i]);
        if (proj > best) {
            best = proj;
            maxIndex = i;
        }
    }
    return maxIndex;
}

function findLeastSeparation(bodyA, bodyB, relPos, result){
    var edgesA = [];

    // Get all the edges from bodyA - sometimes this edges are based on the closest point from the other bodies position
    addSATEdges(edgesA, bodyA, bodyB);

    // Loop through all edges of bodyA
    for (var i = 0; i < edgesA.length; i++) {
        var edge = edgesA[i];

        // Clone normal
        var n = new Vec2().setFrom(edge.eNormal);

        // Get point on edge (plane) with respect of the relative position of both bodies
        var p = new Vec2().setFrom(edge.v0).add(relPos);

        // Find support point for body B (Farthest vertex along negative normal)
        var supportPoint = bodyB.vertices[findSupportPoint(bodyB, new Vec2().setFrom(n).invert())];

        // Get distance from point to plane = d dot (p1 - p2)
        var d = n.dot(new Vec2().setFrom(supportPoint).sub(p));

        // Distance is positive - we have a separation
        if (d > 0) {
            return false;
        }

        // Record greatest negative distance (Least penetration)
        if (d > result.overlap) {
            result.overlap = d;
            result.referenceBody = bodyA;
            result.incidentBody = bodyB;
            result.referenceEdge = edge;
            result.normal.setFrom(n);
            result.support.setFrom(supportPoint);
        }
    }
    return true;
}

function supportSAT(body1, body2, result) {
    // Initialize result
    result.referenceBody = null;
    result.incidentBody = null;
    result.referenceEdge = null;
    result.overlap = Number.NEGATIVE_INFINITY;
    result.normal.zero();
    result.support.zero();

    // Get relative position
    var relPos = new Vec2().setFrom(body1.pos).sub(body2.pos);

    // Test faces of body 1 (A)
    if (!findLeastSeparation(body1, body2, relPos, result)) {
        return false;
    }
    // Test faces of body 2 (B)
    if (!findLeastSeparation(body2, body1, relPos, result)) {
        return false;
    }

    // Make sure the normal always is pushing away
    if (relPos.dot(result.normal) < 0) {
        result.normal.invert();
    }

    // We have a overlap
    return true;
}

Edited by Finalspace, 27 July 2014 - 02:50 PM.


#12 Randy Gaul   Members   -  Reputation: 1173

Like
0Likes
Like

Posted 28 July 2014 - 01:08 PM

Line 28 looks fishy. I'm not sure. I don't have time to debug the code, but you should try to make sure you space transformations are correct. Are you doing this in world space? In the space relative to the Reference OBB? Lastly, there exists code in both Box2D *Lite* for nearly the exact thing. The only difference is it's special case code for OBBs, but the math performed is doing the same SAT idea.

 

There's also an open source collision routine derived from Box2D Lite and Dirk's 2013 slides called "Impulse Engine" on Github. You can try looking at this for a reference.

 

We've all had silly bugs like this when implementing new things for the first time. It takes time to get rid of them, and they appear less often as time goes on and you understand math/concepts better :)






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS