Game Development Reference
In-Depth Information
Figure 4.11. Flood-fill algorithm, no faces map onto C :(a) G ( v ) covering full spherical
cap C ;(b)vertex v and neighbors overlap C , but faces of v map outside C ; (c) flood-fill
goes from vertex to edge to vertex.
We can't use just faces for flood-fill because we won't always find adjacent
vertices inside
C
, like in Figure 4.11. We can use vertices, but we need to check if
an area on
for each vertex then, which is possible but inconvenient.
Following edges is simple enough, and it guarantees that we find all edges,
vertices, and faces mapping inside
G
intersects
C
. Starting from the set of edges and vertices
(perhaps just one edge or one vertex), we can find all vertices adjacent to the
edges and edges intersecting
C
and adjacent to vertices. After a number of itera-
tions, when the set of found edges and vertices doesn't grow, it will be the vertices
comprising our supporting shape. Vertices that have all neighboring vertices in-
side
C
can be excluded. And we compute the two-dimensional convex hull for the
rest of them. See Listing 4.3 for the pseudocode of this algorithm.
C
4.6.4
Edge (Arc)-Cap
C
Overlap Test
Let n 0 and n 1 be the normals of faces adjacent to edge e . The Gauss map
G
( e )
obviously overlaps
C
if n i
s
α
n i ·
s
cos α (see Figure 4.12(a) ) .
Otherwise, let's consider the plane
P ( G ( e )) passing through
G ( e ) and o .Let
δ Pe be the angle between the plane
P
(
G
( e )) and s . The plane
P
(
G
( e )) normal is
e
n 0 , n 1 , hence Equation (4.6). If δ Pe , like in Figure 4.12(b), obviously
G
( e ) does not overlap
C
:
sin δ Pe =
|
e
·
s
|
.
(4.6)
If δ Pe
α
⇔|
e
·
s
|≤
sin α and n 0 , n 1 /
∈C
(see Figure 4.12(c ) , (d), and (e)),
P (
let's consider the plane
( e )) and contains o
and s (see Equation (4.7)). If points n 0 , n 1 are on the same side of
G
( e )) that is orthogonal to
P
(
G
P (
G
( e )),
then the edge does not intersect
.If n 0 , n 1 are on different sides, we just need
to check against the situation depicted in Figure 4.12(e)—arc near the pole
C
s .