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