Transcript 3D Polyhedral Morphing

Computing Voronoi Diagram

For each site pi, compute the common intersection of the half-planes h(pi , pj) for i j, using
linear programming: O(n2 log n)

The worst case time bound is O(n log n)
=> Many, but we’ll describe a algorithm based on
plane sweep (Fortune’s algorithm)
UNC Chapel Hill
M. C. Lin
Plane-Sweep Algorithm

Maintaining the status of the sweep line l: the part
of Vor(P) above l depends not only on the sites
above l but also sites below l

Solution: Maintaining the information about the
part of Voronoi diagram of the sites above l that
cannot be changed by the sites below l. We’ll call
this closed half-space l+.

Observation: the locus of points that are closer to
some (any) site pi l+ than to l is bounded by a
parabola (parabolic arcs or the beach line).
UNC Chapel Hill
M. C. Lin
Beach Line



The beach line is the function that -- for each xcoordinate-- passes through the lowest point of
all parabolas.
The breakpoints between different parabolic arcs
forming the beach line lie on the edges of the
Voronoi diagram; they exactly trace out the
Voronoi diagram as l moves from top to bottom.
The combinatorial structure of a beach line
changes when a new parabolic arc appears on it,
and when a parabolic arc shrinks to a point and
disappears.
UNC Chapel Hill
M. C. Lin
Site Events



The only way in which a new arc can appear on
the beach line is through a site event, where a
new site is encountered by l.
At a site event, 2 new breakpoints appear, which
start tracing out edges. In fact, the they coincide
first, then move in opposite directions to trace out
the same edge. The growing edge, initially not
connected to the rest of the diagram, will
eventually become connected to the rest.
Each site encountered gives rise to 1 new arc and
splits at most one existing one into two.
UNC Chapel Hill
M. C. Lin
Circle Events

The only way an existing arc can disappear
from the beach line is through a circle event,
where the sweep line reaches the lowest
point of a circle through 3 sites defining 3
consecutive arcs on the beach line.

Every Voronoi vertex is defined by means of a
circle event.
UNC Chapel Hill
M. C. Lin
Data Structures



Store Voronoi diagrams using doubly-connected edge
list. Bound the scene using a bounding box large
enough to contain all vertices.
Beach line is represented by a binary search tree T as
the status structure. Its leaves correspond to the arcs
of the beach line. A breakpoint is stored at an internal
node by an ordered pair of sites <pi, pj>. In T, we also
store pointers to other 2 data structures. Every internal
node has pointer to a half-edge in the Voronoi diagram
being traced out by the breakpoint it represents.
The event Q is implemented as a priority queue, where
the priority is the y-coordinate.
UNC Chapel Hill
M. C. Lin
VoronoiDiagram(P)
Input: A set P := {p1, p2, …, pn} of point sites in the plane.
Output: The Voronoi diagram Vor(P) given inside a bounding box
in a doubly-connected edge list structure.
1. Initialize the event queue Q
2. while Q is not empty
3.
do Consider the event with the largest y-coordinate in Q
4.
if the event is a site event, occurring at site pi
5.
then HandleSiteEvent(pi)
6.
else HandleCircleEvent(pl), where pl is the lowest
point of the circle causing the event
7.
Remove the event from Q
UNC Chapel Hill
M. C. Lin
VoronoiDiagram(P)
8. The internal nodes still present in T correspond to the
half-infinite edges of the Voronoi diagram. Compute a
bounding box that contains all vertices of the Voronoi
diagram in its interior, and attach the half-infinite edges
to the bounding box by updating the doubly-connected
edge list appropriately.
9. Traverse the half-edges of the doubly-connected edge
list to add the cell records and the pointers to and from
them.
UNC Chapel Hill
M. C. Lin
HandleSiteEvent(pi)
1. Search in T for the arc  vertically above pi and delete all
circle events involving  from Q.
2. Replace the leaf of T that represents  with a subtree having
three leaves. The middle leaf stores the new site pi and the
other two leaves store the site pj that was originally stored
with . Store the tuples < pj , pi > and < pi , pj > representing the
new breakpoints at the two new internal nodes. Perform
rebalancing operations on T if needed.
3. Create new records in the Voronoi diagram structure for the
two half-edges separating V(pi) and V(pj) , which will be traced
out by the two new breakpoints.
4. Check the triples of consecutive arcs involving one of the
three new arcs. Insert the corresponding circle event only if
circle intersects sweep line & the event isn’t present yet in Q.
UNC Chapel Hill
M. C. Lin
HandleCircleEvent(pi)
1. Search in T for the arc  vertically above pl that is about to
disappear, and delete all circle events that involve  from Q
2. Delete the leave that represents  from T. Update the tuples
representing the breakpoints at the internal nodes. Perform
rebalancing operations on T if needed.
3. Add the center of the circle causing the event as a vertex
record in the Voronoi diagram structure and create two halfedge records corresponding to the new breakpoint of the
Voronoi diagram. Set the pointers between them appropriately.
4. Check the new triples of consective arcs that arise because of
the disappearance of . Insert the corresponding circle event
into Q only if the circle intersects the sweep line & circle event
isn’t present yet in Q.
UNC Chapel Hill
M. C. Lin
Algorithm Analysis

Degeneracies can be handled
– 2 or more events on a common horizontal line
– Event points coincide, e.g. 4 or more co-circular sites
– A site coincides with an event

The Voronoi diagram of a set of n point sites in
the plane can be computed with a sweep line
algorithm in O(n log n) time using O(n) storage.
UNC Chapel Hill
M. C. Lin