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.