Game Development Reference
In-Depth Information
Bisector b = n 0 ( e )+ n 1 ( e ) ( Figure 4.16 ) shows the intuitive direction “out-
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