Graphics Reference
In-Depth Information
D
d
B
B
E
E
A
A
C
C
(a)
(b)
Figure 9.13
(a) The vertex
A
is in a local minimum because hill climbing to either of its
neighbors
B
and
C
does not move closer to the extreme vertex
E
. (b) Adding an artificial
neighbor (here,
D
) not coplanar with the other neighbors avoids becoming stuck in the local
minimum.
However, for a polyhedron this small the amount of work is roughly the same in that
a larger number of neighbors must be examined at each step of the algorithm.
Adding artificial neighbors also addresses what is otherwise a problem for hill-
climbing-like methods; namely, coplanar faces. Figure 9.13 illustrates how hill
climbing can become stuck in a local minimum due to the presence of coplanar
faces (or, as here, edges). In Figure 9.13a, vertex
A
is in a local minimum in that
hill climbing to either of its neighbors
B
and
C
does not move closer to the extreme
vertex
E
. If moving randomly to either neighbor, the next step might move back to
A
, causing infinite looping. In 2D, disallowing moving back to a previously visited
vertex can prevent such cycling, but this does not hold in 3D (in which a vertex may
end up with no remaining visitable neighbors during the search).
By adding an artificial neighbor
N
to each vertex
V
, where
N
is
not
coplanar with
V
and its real neighbors, local minima can effectively be avoided during hill climbing.
Figure 9.13b shows how adding
D
as an artificial neighbor to
A
helps escape the local
minimum. Note that a hierarchical representation such as the Dobkin-Kirkpatrick
hierarchy could be used to locate an extreme vertex in logarithmic time.
9.5.5
Exploiting Coherence by Vertex Caching
The amount of effort spent hill climbing for an extreme vertex highly depends on the
choice of the starting point
P
. In the best case,
P
itself is the extreme vertex and the
search can terminate immediately. Worst case,
P
lies on the opposite side of where
the extreme vertex is located. Because objects tend not to move much from frame to
frame relative one another, a good choice for the initial point
P
would be the closest
