Graphics Reference
In-Depth Information
A good way to implement these partial polygons is via a circularly linked list, or cycle,
and a pointer that points to the last element of the list.
The algorithm now computes the bounds of the output polygons from the LML
by scanning the world from the bottom to the top using what are called
scan beams
.
A scan beam is a horizontal section between two scan lines (not necessarily adjacent),
so that each of these scan lines contains at least one vertex from the polygons but
there are
no
vertices in between them. Figure 3.18(a) shows the scan beams and the
scan lines that determine them for that particular polygon. The scan beams are the
regions between the horizontal lines. It should be noted here that the scan lines that
determine the scan beams are not computed all at once but incrementally in a bottom-
up fashion. The information about the scan beams is kept in a
scan beam list
(SBL),
which is an ordered list ordered by the y-coordinates of all the scan lines that define
the scan beams. This list of increasing values will be thought of as a stack. As we scan
the world, we also maintain an
active edge list
(AEL), which is an ordered list con-
sisting of all the edges intersected by the current scan beam.
When we begin processing a scan beam, the first thing we do is to check the LML
to see if any of its bound pairs start at the bottom of the scan beam. These bounds
correspond to local minima and may start a new output polygon or break one into
two depending on whether the local minimum starts with a left-right or right-left edge
pair. After any new edges from the LML are added to the AEL, we need to check for
intersections of edges within a scan beam. These intersections affect the output poly-
gons and are dealt with separately first. Finally, we process the edges on the AEL.
Algorithm 3.3.5.1 summarizes this overview of the Vatti algorithm.
To understand the algorithm a little better we look at some more of its details.
The interested reader can find a much more thorough discussion with abstract pro-
grams and explicit data structures in the document VattiClip on the accompanying
CD. The UpdateLMLandSBL procedure in Algorithm 3.3.5.1 finds the bounds of a
polygon, adds them to LML, and also updates SBL. Finding a bound involves finding
the edges that make them up and initializing their data structure that maintains the
information that we need as we go along. For example, we keep track of the x-coor-
dinate of their intersection with the bottom of the current scan beam. We call this the
x-value
of the edge. The edges of the AEL are ordered by these values with ties being
broken using their slope. We also record the
kind
of an edge which refers to whether
it belongs to the clip or subject polygon. Two edges are called
like
edges if they are of
the same kind and
unlike
edges otherwise. The partial polygons that are built and that,
in the end, may become the polygons that make up the clipped polygon are called the
adjacent polygons
of their edges.
Because horizontal edges complicate matters, in order to make dealing with hor-
izontal edges easier, one assumes that the matching left and right bound pairs in the
LML list are “normalized”. A
normalized
left and right bound pair satisfies the fol-
lowing properties:
(1) All consecutive horizontal edges are combined into one so that bounds do not
have two horizontal edges in a row.
(2) No left bound has a bottom horizontal edge (any such edges are shifted to the
right bound).
(3) No right bound has a top horizontal edge (any such edges are shifted to the
left bound).
