Game Development Reference
In-Depth Information
lie on the contact plane, and the contact penetration can be computed as the
projection of the difference between the shapes' vertices onto the contact
normal. We can also use the difference to compute the contact normal for
each contact point separately. In any case, the contact points with the most
penetration are the most important.
4.6.9 Contact Area Intersection
The brute-force algorithm is used to build bit-matrices B a and B b for polygons
a and b , respectively: each element B i,j will contain 0 if the vertex i of the
polygon x is on the outside of edge j of the other polygon, and vice versa. For two
quadrilaterals, it's just two 4
×
4 matrices, 32 two-dimensional tests total. Let's
consider a vertex N in the N -gon the same as vertex 0. Vertices with all 1sinthe
row lie inside the other polygon and get admitted as contacts. We will also need
to compute contact points for each pair of edges (one edge from each polygon)
that intersects. Polygon a with edge i ( E i ) with vertices i, i +1intersects E j
if
and only if B i,j B i +1 ,j (that is, edge E i
is split in two by infinite line E j ) and,
symmetrically, B j,i
B j +1 ,i . See Figure 4.15 for an example. The symbol
denotes xor (exclusive or).
The brute-force algorithm is only good for triangles or quadrilaterals. If we
don't care much about precision, we can always just cull extra vertices from the
contact area and reduce it to a quadrilateral. For example, cull vertices with the
highest angle until just four vertices are left in each shape's contact area. But if we
want more precision, there are linear-time, convex polygon-polygon intersection
algorithms [O'Rourke 98], and they deserve a lot more attention than we can give
in this chapter. Next is a small illustration of one such algorithm.
Figure 4.15. Bit-matrices for brute-force polygon intersection. Each polygon has its B
matrix written inside. Each intersection vertex is linked to the bits in B that determine its
status.