Contact Points: Polygons & Clipping

Determining which side a point c lies vs a line segment (a - b)


create 2 vectors
a-b
a-c


c# - How to tell whether a point is to the right or left side of a line - Stack Overflow

user
then take the cross
isLeft(a, b, c) {
return (

public bool isLeft(Point a, Point b, Point c){ return ((b.X - a.X)*(c.Y - a.Y) - (b.Y - a.Y)*(c.X - a.X)) > 0; }


Where a = line point 1; b = line point 2; c = point to check against.
If the formula is equal to 0, the points are colinear.
If the line is horizontal, then this returns true if the point is above the line.

Taking the above ideas to the process of clipping...

We'll follow through an example in the same was a Dyn4j (but in at snail like pace), Javascript like pseudo code.

Reference edge and the incident edge are the closest edges of the two polygons being analysed, and Reference Edge is used to "clip" the Incident Edge.

The important part to remember is the relationship between the faces and the normals (we hold the outward facing normals of the polygon class in array/property this.normals).

• normals[i] is in fact the outward facing normal of edge[i], edge[i] being the edge between vertices[i] and vertices[i+1].
• edge[i] is normal of the left-side plane of edge[i]
• edge[i].negate() is the normal of the right-side plan of edge[i]

To find the distance of a point p to an edge (plane), you take the dot product between the normal (needs to be unit vector) of the edge with the ( p - v1 ) or ( p - v2).

Hence:

• distance of v2 from the left-plane of the reference edge = (reference.edge.normalized()).dot(v2 - referenceEdge.v1)
• distance of v1 from the "right plane"of the reference edge = (reference.edge).negate().normalize().dot(v1 - referenceEdge.v1)
• distance from point p to edge[i], we need simply take the dot product between normals[i] with ( p - vertices[i]) - since the normals are outward facing, if the resulting dot is negative it means p is "inside" the polygon (strictly speaking, "behind" the edge - it might not be entirely inside the polygon).

This is the most important step in understanding the clipping process. As long as we keep our head clear about this, then we can begin to understand how to implement the code. Of course, we need to be careful about the direction of the vectors and local vs world space...I never said this was easy.

First obtain the reference and incident edges from the reference and incident polygons

// create the reference edge vector

var refev = reference.getEdge();

// normalize it so that we have the normal vector necessary to calculate distance of a point from the side planes of the reference edge

refev.normalize();

// compute the offset of the reference edge points along the reference edge

var offset1 = -refev.dot(reference.getVertex1().getPoint());

// clip the incident edge by the reference edge's left edge

var clip1 = this.clip(incident.getVertex1(), incident.getVertex2(), refev.getNegative(), offset1);

Code to clip the incident edge segment given by v1 and v2 by reference edge

Parameters

• v1: the first vertex of the segment to be clipped
• v2: the second vertex of the segment to be clipped
• n: the normalized vector of the reference edge - > hence this would be the normal relevant to the side planes
• offset: the offset of the end point of the segment to be clipped

clip(v1, v2, n, offset) {

List<PointFeature> points = new ArrayList<PointFeature>(2);

Vector2 p1 = v1.getPoint();

Vector2 p2 = v2.getPoint();

// calculate the distance between the end points of the edge and the clip line

double d1 = n.dot(p1) - offset;

double d2 = n.dot(p2) - offset;

// add the points if they are behind the line

if (d1 <= 0.0) points.add(v1);

if (d2 <= 0.0) points.add(v2);

// check if they are on opposing sides of the line

if (d1 * d2 < 0.0) {

// get the edge vector

Vector2 e = p1.to(p2);

// clip to obtain another point

double u = d1 / (d1 - d2);

e.multiply(u);

e.add(p1);

if (d1 > 0.0) {

points.add(new PointFeature(e, v1.getIndex()));

} else {

points.add(new PointFeature(e, v2.getIndex()));

}

}

return points;

}

Useful References


https://gdcvault.com/play/1015496/Physics-for-Game (for the very advanced! Talks about multiple contacts points with rotation)

https://box2d.org/files/ErinCatto_ContactManifolds_GDC2007.pdf (this explains the key points of contact generation, with reference to SAT and GJK)

https://www.toptal.com/game/video-game-physics-part-ii-collision-detection-for-solid-objects (this covers a lot of topics and is a good read to get overall understanding of context)

https://dyn4j.org/2011/11/contact-points-using-clipping/ (this explains how to implement contact points using clipping)

http://media.steampowered.com/apps/valve/2015/DirkGregorius_Contacts.pdf (this is quite beginner friendly - goes into a fair bit of depth about different situations of contact points)

http://www.richardtonge.com/presentations/Tonge-2012-GDC-solvingRigidBodyContacts.pdf (a little bit more detail)

https://research.ncl.ac.uk/game/mastersdegree/gametechnologies/previousinformation/physics5collisionmanifolds/2017%20Tutorial%205%20-%20Collision%20Manifolds.pdf (describes clipping method)

https://ubm-twvideo01.s3.amazonaws.com/o1/vault/gdc09/slides/04-GDC09_Catto_Erin_Solver.pdf (maybe one day I will understand some of this)