Graphics Reference
In-Depth Information
edges. For (2) one divides the scan line into “sample spans” within which the same
face is visible (one is using “point-to-point” coherence along the line). Finally, at step
(3) each sample span must then be processed. How this is done depends on how they
were chosen. If we use the method indicated in Figure 7.8(a), then this is straight-
forward, although if we allow penetrating faces there are extra modifications needed:
At each vertex or span endpoint one must compute the depths of the segments that
fall into the span.
7.8
The Watkins Scan Line Algorithm
The Watkins algorithm ([Watk70]) is a scan line image space algorithm that is espe-
cially efficient. The idea is to let the right end of the current span “float” and keep the
left end fixed. One starts at the extreme right. As new segments are taken from the
x-sorted list, the right end moves left until one gets a span that is simple enough to
compute which segment is visible.
Algorithm 7.8.1 gives an outline of a Watkins-type algorithm. There are two things
to note. One is that for parity to work, one needs to shorten the edges appropriately
as described in Section 2.9.1. The other is that we assume that polygons have been
clipped.
To help clarify the algorithm we shall work through an example. Consider the
scene shown in Figure 7.9(a). Figures 7.9(b) and (c) show its projection onto the x-z
and x-y plane, respectively. Suppose that we are at scan line y as shown in Figure
7.9(c). The critical points along the x-axis are 0, a, b, c, and d. Table 7.7.1 shows how
the x scan progresses. We show the values of the indicated variables at the locations
in the procedure ProcessActiveEdgeList marked “LA” or “LB.” Note how the active
flag for each polygon toggles back and forth between true and false based on a parity-
type argument.
The objects in Figure 7.9(a) did not intersect. Figure 7.10 shows a case where one
polygon penetrates another. In such a case we have to find intersections and keep
moving the right end of the span to the left, saving the current values as we go along,
until we find an intersection-free segment. In the case shown there is one intersection
with x value x I in the segment [b,c]. We need to check all active polygons against all
other active polygons when testing for intersections. We can tell if two polygons inter-
sect by looking at their z-depth values at the endpoints of the span, call these zl 1 ,zr 1
for the first polygon and zl 2 ,zr 2 for the second polygon. The polygons will intersect if
(
(
)
(
)
)
(
(
)
(
)
)
zl
<
zl
and
zr
>
zr
or
zl
>
zl
and
zr
<
zr
.
1
2
1
2
1
2
1
2
If we find an intersection, then certain branches in the code of the procedure
LastVisiblePolygonColor will now be executed. The new x scan will now pass state-
ments marked “LC” and “LD,” as we can see from Table 7.7.2 in our example. First
we save c on the stack and deal with the segment [b,x I ]. Then we set spanLeft to x I ,
pop c from the stack, and deal with [x I ,c]. The rest proceeds as before.
Notice that we always check if segments intersect in an endpoint of a span. If so,
then we use the opposite endpoint's x value to do a depth check to see which polygon
is closer.
Search WWH ::




Custom Search