Game Development Reference

In-Depth Information

already. Of course, we'll need to project that point onto the other shape to

find out the penetration. We can just project it onto the aligned feature

on the other shapeâ€”be it a face, an edge, or another point. We might

also want to remember the midpoint (the point right in the middle between

the two shapes) as the point of contact because it makes our computations

independent on the order of the shapes. Since the distance is usually small,

the difference is not significant, but it's good to be consistent for easier

debugging. When projecting onto an edge or a face, we can project onto

the corresponding infinite line or infinite plane. There's a chance that the

resulting point will be slightly outside of the other shape (vertex-vertex

converting to face-vertex), but the error will never be significant because

we are using the closest features on both shapes.

2.
Edge-edge.
In the case of two contact edges, we need to intersect them

approximately. We're actually intersecting their projections onto the con-

tact plane because they don't generally intersect in

3
. To produce stable

contacts, we want to find two contact points when both edges are almost

parallel (very parallel, not-so-parallel edges). A relatively simple heuristic

is to find the extreme points at which both edges (or their projections onto

the contact plane, whichever is simpler) are still closer than some threshold.

R

3.
Face-edge.
If we have a contact face on one side of the collision and a

contact edge on the other, we just intersect the edge with the face either by

projecting the edge onto the face (which is cleaner) or by intersecting their

projections onto the contact plane (which may be simpler sometimes but

may produce slightly inconsistent results). We've probably already spent

linear time to generate the face, so linear-time, brute-force cutting of the

edge by the face edges works fine to find the two contact-manifold vertices.

The edge line will split the face vertices into two sides: left and right of the

edge. We'll need to find the two polygon edges intersecting the edge's line

and then intersect the edge with that segment. If the edge doesn't intersect

the polygon, we probably want to fall back and generate one contact point.

4.
Face-face.
This is the most complicated of all because we need to intersect

two polygons. If we sample with eight directions, we will never have more

than eight vertices in each polygon. One thing to remember is that we don't

really need the intersection polygon, we just need its vertices, so any order

will do. So for small numbers of vertices in both polygons, we can use

brute force and it will sometimes be fast. But in the more general case,

we need to actually intersect two polygons in two dimensions and project

them onto the contact plane. For each intersection, the contact point may