Game Development Reference
InDepth Information
side” the edge. The inequalities in Equation (4.8) relate
b
and
±
s
.
If neither
direction
s
nor
s
satisfy both conditions in Equation (4.8), then this
EE
case is
clearly not the support feature pair.
s
−
·
b
A
<
0
,
b
A
=
n
0
(
e
A
)+
n
1
(
e
A
);
(4.8)
s
·
b
B
>
0
,
b
B
=
n
0
(
e
B
)+
n
1
(
e
B
)
.
In Figure 4.16, cases (d), (e), and (f) are examples of noncandidate (filtered
out) cases where
s
·
b
A
>
0. Cases (a), (b), and (c) require the additional test of
b
B
.
The inequalities in Equation (4.8) generate a lot of false positives and require
computing
s
, but they illustrate the
EE
case in
3
. Let us consider the
EE
case
R
on a Gauss map (see
Figure 4.17
)
. The arcs
(
e
B
) are the ones we
need to test for intersection (note the negation). Their point of intersection is the
candidate support direction
s
. If the arcs don't intersect, then there are no parallel
support planes
G
(
e
A
) and
−G
P
A
(
s
) and
P
B
(
−
s
) for this edge pair, and we need not consider
this edge pair.
The arcs
(
e
B
) intersect if and only if the tetrahedron
n
A,
0
n
A,
1
n
B,
0
n
B,
1
contains
o
, like in Figure 4.17(c). The direction of the line
from
G
(
e
A
) and
−G
(
e
A
) through
o
is the candidate
s
. Note that the
n
B,i
are not
negated (see
Figure 4.17(a)
and
(c)
)
. If the arcs
G
(
e
B
) to
G
G
(
e
A
) and
G
(
e
B
) intersect as in
Figure 4.19(b), then
G
(
e
A
) and
−G
(
e
B
) do
not
intersect, and we skip the edge
pair.
In Figure 4.17(c) it's easy to see that the tetrahedron contains the origin if and
only if
1. the plane through (
o
,
n
A,
0
,
n
A,
1
) splits chord
n
B,
0

n
B,
1
,
2. the plane through (
o
,
n
B,
0
,
n
B,
1
) splits chord
n
A,
0

n
A,
1
,and
3. arcs
G
(
e
A
) and
G
(
e
B
) do not intersect.
See Figure 4.17(c): the plane through (
o
,
n
0
,
n
1
) has the equation (
n
0
×
n
1
)
·
x
=0,and
n
0
×
e
is the edge direction that we can (but don't have to)
cache. Thus, the necessary condition for two edges to be supporting features in
the direction
e
A
×
n
1
e
B
is
sign(
e
A
·
n
B,
0
)
=sign(
e
A
·
n
B,
1
)
,
·
·
n
A,
1
)
.
sign(
e
B
n
A,
0
)
=sign(
e
B