Game Development Reference

In-Depth Information

Figure 4.17.
Testing if edge-edge is a candidate support pair: (a) edge face normals,

(b) edge arcs, and (c) tetrahedron containing the origin.

The above do not detect arc intersections exactly. However, it is relatively easy to

detect both the intersection and the direction of
s
at the same time. Next, we will

present such a method.

For the shape
S
, we can compute the edge direction
e
S
n
S,
0
×
n
S,
1
(the

order is important). By projecting the arcs onto a plane orthogonal to
b
=
n
A,
0
+

n
A,
1
, as in Figure 4.18, it is easy to see that the candidate support direction
s
is

as in Equation (4.9). The vector
s
is also the point of intersection of two arcs (see

Figure 4.18(a)
and
(b)
).
If the arcs do not intersect,
s
is undefined, and the edge

pair is not a candidate support feature pair. See Figure 4.18 for examples of the

cases in Equation (4.9):

⎧

⎨

⎧

⎨

e
A
·−

n
B,
0
>
0

e
A
·−
n
B,
1
<
0

−

−

e
B
×

e
A

if

⎩

e
B

·

n
A,
0
<
0

−

e
B

·

n
A,
1
>
0

⎧

⎨

s
=

e
A
·−

n
B,
0
<
0

e
A
·−

(4.9)

⎩

n
B,
1
>
0

e
A
×−

e
B

if

⎩

−

e
B

·

n
A,
0
>
0

−

·

n
A,
1
<
0

e
B

undefined otherwise

We only need to check nonparallel pairs of edges with intersecting arcs. In-

tersection and direction
s
can be detected according to Equation (4.9). See Fig-

ure 4.19 for examples of excluded cases. And for those pairs that we need to

check, we just need to compute the distance between the edges along the direc-

tion
s
.If
e
A
×

e
B
is close to zero, we can skip that
EE
check as it is a degenerate

case (shown in
Figure 4.19(a)
)
.