Game Development Reference

In-Depth Information

convex hull. Although it may lead to generation of out-of-bounds contact points

due to the projection, they will not be far outside.

), if we don't want to miss

a single vertex (see Section 4.6.7 for an approximate algorithm), is to flood-fill

all features inside

One way to find the support shape (faces within

C

C

by following topological connectivity: from each feature

inside

, go to adjacent features and check if they are also inside. Repeat until all

features inside

C

C

are found.

if
F
is
vertex
then
(
V
queue
,E
queue
)
←
(
F,
∅)

if
F
is
edge
then
(
V
queue
,E
queue
)
←
(∅
, F
)

if
F
is
face
then
(
V
queue
,E
queue
)
←
(
V
(
F
)
,
E
(
F
))

(
V, E
)
←
(∅
,
∅)

while
(
V
queue
,E
queue
)
=(∅
,
∅)

for each
v
queue
∈ V
queue
do

V
queue
← V
queue
\{
v
queue
}

// move
v
queue
to
V

V ← V ∪{
v
queue
}

for each
e
adj
∈
E
(
v
queue
)
do

if
e
adj
∈ E ∪ E
queue
and
overlap(
e
adj
,

C
(
α,
s
)
)
then

E
queue
← E
queue
∪{e
adj
}

for each
e
queue
∈

E
queue
do

E
queue
← E
queue
\{e
queue
}

// move
e
queue
to
E

E ← E ∪{e
queue
}

V
queue
← V
queue
∪
V
(
e
queue
)
\ V

return
V

function
overlap(
e
,
C
(
α,
s
)
)

if
s
·
n
0
(
e
)
≤
cos
α
or
s
·
n
1
(
e
)
≤
cos
α
then return true

if
s
·
e
>
sin
α
then return false

n
⊥
←
s
×
e

if
sign(
n
⊥
·
n
0
(
e
)) = sign(
n
⊥
·
n
1
(
e
))
then return false

return
(
n
0
(
e
)+
n
1
(
e
))
·
s
>
0

Listing 4.3.
Exact support shape flood-fill algorithm.