Game Development Reference

In-Depth Information

new lower bound on
d
min
. Note that it is neither simple nor practical to literally

search through all vertices for a given face in
FV
and
VF
cases. Obviously,

since we know the potential
s
min
direction for the face, we can just directly find

the opposing-shape support vertex, which is faster and easier. The support-plane

search can be accelerated using the Dobkin-Kirkpatrick (DK) hierarchy [Dobkin

and Kirkpatrick 90] or gradient walk. Most of the signed distance values will

usually be deeply negative, if we enumerate all of the possibilities.

If
d
min
≤

0, it means the polytopes intersect and we found the correct

(
s
min
,d
min
). Otherwise, we have the following choices:

1. Stop and detect no collision.

2. Stop and return
d
min
as the lower bound of distance.

3. Continue to find the exact Euclidean distance (Equation (4.5)).

In the latter case, we need to incrementally compute (
s
,d
) for the remaining

(
s
min
,d
min
)=max

d

{

(
s
,d
):
s

∈

FV

∪

VF

∪

EE

∪

VE

∪

EV

∪

VV

}

.
(4.5)

The algorithm from Equation (4.5) is in Listing 4.2. Please refer to Table 4.4

for the notation used.

v
0
(
e
)
,
v
1
(
e
)

The two vertices of edge
e
;
v
0
(
e
)
=
v
1
(
e
)

norm
||·||
(
x
)

Normalization operator :

x
/||
x
||

n
0
(
e
)
,
n
1
(
e
)

Normals of faces adjacent to edge
e
;
n
0
=
n
1

e
(
e
)

Edge
e
direction
±
norm
||·||
(
v
1
(
e
)
−
v
0
(
e
))

e
(
e
)=
norm
||·||
(
n
0
(
e
)
×
n
1
(
e
))
if
n
0
=
n
1

proj
⊥
(
v
,e
)

Projection of

v

onto edge
e
:

v
0
(
e
)+
e
(
e
)((
v
−
v
0
(
e
))
·
e
(
e
))

n
(
f
)

Normal of face
f

V
(
S
)
,
E
(
S
)
,
F
(
S
)

Sets of vertices
{
v
i
}
, edges
{e
i
}
, faces
{f
i
}
of shape
S

Ta b l e 4 . 4 .
Notation guide.