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.