670
`
`Visible- surface Determination
`
`0 0 0 0 0 0 0 0
`0 0 0 0 0 0 0 0
`0 0 0 0 0 0 0 0
`
`5 5 5 5 5 5 51
`5 5 5 5 5 5
`5 5 5 5 5
`
`0 0 0 0 0 0 0 0 + 5 • 5 5
`
`5 5 5
`5 5
`..!
`
`0 0 0 0 0 0 0 0
`0 0 0 0 0 0 0 0
`0 0 0 0 0 0 0 0
`(a) 0 0 0 0 0 0 0 0
`5 5 5 5 5 5 5 0
`5 5 5 5 5 5 0 0
`5 5 5 5 5 0 0 0
`5 5 5 5 0 0 0 0 +
`5 5 5 0 0 0 0 0
`5 5 0 0 0 0 0 0
`5 0 0 0 0 0 0 0
`(b) 0 0 0 0 0 0 0 0
`
`5 5 5 5 5 5 5 0
`5 5 5 5 5 5 0 0
`5 5 5 5 5 0 0 0
`5 5 5 5 0 0 0 0
`5 5
`0 0 0 0
`5 5
`0 0 0 0
`6
`0 0 0 0
`0
`
`=
`
`-
`
`Fig. 15.22 The z-buffer. A pixel" s shade is shown by its color, its z value is shown as a
`number. (a) Adding a polygon of constant z to the empty z-buffer. (b) Adding another
`polygon that intersects the first.
`
`the surface has not been determined or if the polygon is not planar (see Section 11.1.3),
`z(x, y) can be determined by interpolating the z coordinates of the polygon's vertices along
`pairs of edges, and then across each scan li ne, as shown in Fig. 15.23. Incremental
`calculations can be used here as well. Note that the color at a pixel does not need to be
`computed if the conditional determining the pixel's visibility is not satisfied. Therefore, if
`the shading computation is time consuming, additional efficiency can be gained by
`performing a rough front-to-back depth sort of the objects to display the closest object~
`first.
`The z-buffer algorithm does not require that objects be polygons. Indeed, one of its
`most powerful attractions is that it can be used to render any object if a shade and a z-value
`
`y
`
`Fig. 15.23 Interpolation of z values along polygon edges and scan lines. z. is
`interpolated between z, and z2; z0 between z, and z3; z0 between z. and z0.
`
`0717
`
`

`
`15.4
`
`The z-Buffer Algorithm
`
`671
`
`can be determined for each point in its projection; no explicit intersection algorithms need
`to be written.
`The z-buffer algorithm perfomts radix sons in x andy, requiring no comparisons, and
`its z sort takes only one comparison per pixel for each polygon containing that pixel. The
`time taken by the visible-surface calculations tends to be independent of the number of
`polygons in the objects because, on the average, the number of pixels covered by each
`polygon decreases as the number of polygons in the view volume increases. Therefore, the
`average size of each set of pairs being searched tends to remain fixed. Of course, it is also
`necessary to take into account the scan-conversion overhead imposed by the additional
`polygons.
`Although the z-buffer algorithm requires a large amount of space for the z-buffer, it is
`easy to implement. If memory is at a premium, the image can be scan-converted in strips,
`so that only enough z-buffer for the strip being processed is required, at the expense of
`performing multiple passes through the objects. Because of the z-buffer's simplicity and the
`lack of additional data structures, decreasing memory costs have inspired a number of
`hardware and firmware implementations of the z-buffer, examples of which are discussed in
`Chapter 18. Because the z-buffer algorithm operates in image precision, however, it is
`subject to aliasing. The A-buffer algorithm [CARP84], described in Section 15.7.
`addresses this problem by using a discrete approximation to unweighted area sampling.
`The z-buffer is often implemented with 16- through 32-bit integer values in hardware,
`but software (and some hardware) implementations may use floating-point values.
`Allhough a 16-bit z-buffer offers an adequate range for many CAD/CAM applications, 16
`bits do not have enough precision to represent environmentS in whicb objectS defined with
`millimeter detail are positioned a kilometer apart. To make matters worse, if a perspective
`projection is used, the compression of distant z values resulting from the perspective divide
`has a serious effect on the depth ordering and intersections of distant objects. Two pointS
`that would transform to different integer z values if close to the view plane may transform to
`the same z value if they are farther back (see Exercise 15.13 and [HUGH89)).
`The z-buffer's finite precision is responsible for another aliasing problem. Scan(cid:173)
`conversion algorithms typically render two different setS of pixel.s when drawing the
`common part of two collinear edges that stan at different endpoints. Some of those pixels
`shared by the rendered edges may also be assigned slightly different z values because of
`numerical inaccuracies in performing the z interpolation. This effect is most noticeable at
`the shared edges of a polyhedron's faces. Some of the visible pixels along an edge may be
`part of one polygon, while the rest come from the polygon's neighbor. The problem can be
`fixed by inserting extra vertices to ensure that vertices occur at the same points along the
`common pan of two collinear edges.
`Even after the image has been rendered, the z-buffer can still be used to advantage.
`Since it is the only data structure used by the visible-surface algorithm proper, it can be
`saved along with the image and used later to merge in other objects whose z can be
`computed. The algorithm can also be coded so as to leave the z-buffer contents unmodified
`when rendering selected objects. lf the z-buffer is masked off this way, then a single object
`can be written into a separate set of overlay planes with hidden surfaces properly removed
`(if the object is a single-valued function of x and y) and then erased without affecting the
`contents of the z-buffer. Thus, a simple object, such as a ruled grid, can be moved about the
`
`0718
`
`

`
`672
`
`Visible-surface Determination
`
`image in x, y, and z. to serve as 3 "30 cursor" that obscures and is obscured by the objects
`in the environment. Cutaway views can be created by making the z-buffer and frame-buffer
`writes contingent on whether the z value is behind a cutting plane. If the objects being
`displayed have a single z value for each (x, y), then the z-buffer contents can also be used to
`compute area and \IQiume. Exercise 15.25 e11plains how to use the z-buffer for picking.
`Rossignac and Requicha [ROSS86] discuss how to adapt the z-buffer algorithm to
`handle objects defi ned by CSG. Each pixel in a surface's projection is written only if it is
`both closer in z and on a CSG object constructed from the surface. Instead of storing only
`the point with closest z at each pixel, Atherton suggests saving a list of all points, ordered by
`z and accompanied by each surface's identity, to fonn an object buffer [ATHE8 1 ]. A
`postprocessing stage determines how the image is displayed. A variety of effects, such as
`transparency, clipping, and Boolean set operations, can be achieved by processing each
`pixel's list, without any need to rc-scan convert the objects.
`
`15.5 LIST-PRIORITY ALGORITHMS
`
`List-priority algorithms detem1ine a visibility ord.ering for objects e nsuring that a correct
`picture results if the objects are rendered in that order. For exumple, if no object overlaps
`another in z, then we need only to sort the objects by increasing z, and to render them in that
`order. Farther objects are obscured by closer ones as pixels from the closer polygons
`overwrite those of the more d istant ones. If objects overlap in z, we may still be able to
`detcnnine a correct order, as in Fig. 15.24(a). If objects cyclically overlap each other, as
`Fig. t5.24(b) and (c), or penetrate each other, then there is no correct order. In these cases,
`it will be necessary to split one or more objects to make a linear order possible.
`List-priority algorithms are hybrids that combine both object-precision and image(cid:173)
`precision operations. Depth comparisons and object splitting are done with object
`precision. Only scan conversion, which relies on the ability of the graphics device to
`overwrite the pixels of previously drawn objects, is done with image precision. Because the
`list of sorted objects is created with object precision, however, it can be redisplayed
`correctly at any resolution. As we shall see, list-priority algorithms differ in how they
`detennine the sorted order, as well as in which objects get split, and when the splitting
`occurs. The sort need not be on z, some objects may be split that neither cyclically overlap
`nor penetrate others, and the splitting may even be done independent of the viewer's
`position.
`
`y
`
`y
`
`(a)
`
`(b)
`
`(c)
`
`Fig. 15.24 Some cases in which z extents of polygons overlap.
`
`0719
`
`

`
`15.5
`
`List-priority Algorithms
`
`673
`
`15.5 .1 The Depth-Sort Algorithm
`
`The basic idea of the depth-sort algorithm. developed by Newell, Newell, and Sancha
`[NEWE72], is to paint the polygons into the frame buffer in order of decreasing distance
`from the viewpoint. Three conceptual steps are performed:
`
`I. Sort all polygons according to the smallest (farthest) z coordinate of each
`2. Resolve any ambiguities this may cause when the polygons' z extents overlap, splitting
`polygons if necessary
`3. Scan convert each polygon in ascending order of smallest z coordinate (i.e., back to
`front).
`
`Consider the use of explicit priority, such as that associated with views in SPHl GS.
`The explicit priority takes the place of the minimum z value, and there can be no depth
`ambiguities because each priority is thought of as corresponding to a different plane of
`constant z. This simplified version of the depth-sort a.lgorithm is often known as the
`painter's algorithm, in reference to how a painter might paint closer objects over more
`distant ones. Environments whose objects each exist in a plane of constant z, such as those
`of VLSJ layout, cartography, and window management, are said to be ~ and can be
`correctly handled with the painter's algorithm. The painter's algorithm may be applied to a
`scene in which each polygon is not embedded in a plane of constant z by sorting the
`polygons by their minimum z coordinate or by the z coordinate of their centroid. ignoring
`step 2. Although scenes can be constructed for which this approach works, it does not in
`general produce a correct ordering.
`Figure 15.24 shows some of the types of ambiguities that must be resolved as part of
`step 2. How is this done? Let the polygon currently at the far end of the sorted list of
`polygons be called P. Before th.is polygon is scan-converted into the frame buffer, it must
`be tested against each polygon Q whose z extent overlaps the z extent of P , to prove that P
`cannot obscure Q and that P can therefore be written before Q. Up to five tests are
`perfom1ed, in order of increasing complexity. As soon as one succeeds, P has been shown
`not to obscure Q and the next polygon Q overlapping Pin z is tested. lf all such polygons
`pass, then Pis scan-converted and the next polygon on the list becomes the new P. The five
`tests are
`
`I. Do the polygons' x extents not overlap?
`2. Do the polygons' y extents not overlap?
`ls P entirely on the opposite side of Q's plane from the viewpoint? (This is not the case
`3.
`in Fig. 15.24(a), but is true for Fig. 15.25.)
`Is Q entirely on the same side of P's plane as the viewpoint? (This is not the case in
`Fig. 15.24(a), but is true for Fig. 15.26.)
`5. Do the projections of the polygons onto the (x, y) plane not overlap? (This can be
`determined by comparing the edges of one polygon to the edges of the other.)
`
`4.
`
`· Exercise 15.6 suggests a way to implement tests 3 and 4.
`If all five tests fail, we assume for the moment that P actually obscures Q, and therefore
`test whe.ther Q can be scan-converted before P. Tests I, 2, and 5 do not need to be repeated,
`
`0720
`
`

`
`674
`
`Visible-surface Determination
`
`.-------------x
`
`z
`
`Fig. 15.25 Test 3 is true.
`
`but new versions of tests 3 and 4 are used, with the polygons reversed:
`3'. Is Q entirely on the opposite side of P 's plane from the viewpoint?
`4'. Is P entirely on the same side of Q's plane as the viewpoint?
`ln the case of Fig. 15.24(a), test 3' succeeds. Therefore, we move Q to the end of the list
`and it becomes the new P. In the case of Fig 15.24(b), however, the tests are still
`inconclusive; in fact, there is no order in which P and Q can be scan-converted correctly.
`Instead, either P or Q must be split by the plane of the other (see Section 3.14 on polygon
`clipping, treating the clip edge as a clip plane). The original unsplit polygon is discarded,
`its pieces are inserted in the list in proper z order, and the algorithm proceeds as before.
`Figure 15.24(c) shows a more subtle case. It is possible for P, Q, and R to he oriented
`such that each polygon can always he moved to the end of the list to place it in the correct
`order relative to one, but not both, of the other polygons. This oould result in an infinite
`loop. To avoid looping, we must modify our approach by marking each polygon that is
`moved to the end of the list. Then, whenever the first five tests fail and the current polygon
`Q is marked, we do not try tests 3' and 4'. Instead, we split either P or Q (as if tests 3' and
`4' had both failed) and reinsert the pieces.
`Can two polygons fail all the tests even when they are already ordered correctly?
`Consider P and Q in Fig. 15.27(a). Only the z coordinate of each vertex is shown. With P
`and Q in their current position, both the simple painter' s algorithm and the full depth-sort
`algorithm scan convert P first. Now, rotate Q clockwise in its plane until it hegins to
`obscure P, but do not allow P and Q themselves to intersect, as shown in Fig. 15.27(b).
`(You can do this nicely using your bands asP and Q, with your palms facing you.) P and Q
`
`.----- - - - --X
`
`z
`
`Fig. 15.26 Test 3 is false, but test 4 is true.
`
`0721
`
`

`
`16.5
`
`y
`
`Ust-priority Algorithms
`
`675
`
`0
`
`0
`
`y
`
`0
`
`0
`0
`L-------~--~~ X
`(a)
`
`0
`L-----~----+ X
`(b)
`
`Fig. 15.27 Correctly ordered polygons may be split by the depth-sort algorithm.
`Polygon vertices are labeled with their z values. (a) Polygons P and Q are scan-converted
`without splitting. (b) Polygons P and Q fail all five tests even though they are correctly
`ordered.
`
`have overlapping z extents, so they must be compared. Note that tests I and 2 (x and y
`extent) fail, tests 3 and 4 fail because neither is wholly in one half-space of the other, and
`test 5 fails because the projections overlap. Since tests 3' and 4' also fail, a polygon will be
`split. even though P can be scan-<Jonverted before Q. Although the simple painter's
`algorithm would correctly draw P first because P has the smallest minimum z coordinate,
`try the example again with z = -0.5 at P's bottom and z = 0.5 at P's top.
`
`15.5 .2 Binary Space-Partitioning Trees
`
`The binary space-partitioning (BSP) tree algorithm, developed by Fucbs, Kedem, and
`Naylor [FUCH80; FUCH83], is an extremely efficient method for calculating the visibility
`relationships among a static group of 30 polygons as seen from an arbitrary viewpoint. It
`trades off an initial time- and space-intensive preprocessing step against a linear display
`algorithm that is executed whenever a new viewing specification is desired. Thus, the
`algorithm is well suited for applications in which the viewpoint changes, but the objects do
`not.
`The BSP tree algorithm is based on the work of Schumacker [SCHU69], who noted
`that environments can be viewed as being composed of clusters (collections of faces), as
`shown in Fig. 15.28(a). U a plane can be found that wholly separates one set of clusters
`from another, then clusters that are on the same side of the plane as the eyepoint can
`obscure, but cannot be obscured by, clusters on the other side. Each of these sets of clusters
`can be recursively subdivided if suitable separating planes can be found. As shown in Fig.
`J5.28(b), this partitioning of the environment can be represented by a binary tree rooted at
`
`0722
`
`

`
`676 Visible-surface Determination
`
`P1
`
`P2
`
`P1
`fr~cl<
`
`P2
`
`P2
`
`tronA back fron'Rcl<
`
`D
`3, 1. 2
`
`C
`3, 2, 1
`
`A
`1, 2. 3
`(b)
`
`8
`2. 1, 3
`
`(a)
`
`D
`
`c
`
`Fig. 15.28 Cluster priority. (a) Clusters 1 through 3 are divided by partitioning planes
`Pl and P2, determining regions A through Din which the eyepoint may be located. Each
`region has a unique cluster priority. (b) The binary-tree representation of (a). (Based on
`(SUTH74a).)
`
`the first partitioning plane chosen. The tree's internal nodes are the partitioning planes; its
`leaves are regions in space. Each region is associated with a unique order in which clusters
`can obscure one another if the viewpoint is located in that region. Determining the region in
`which the eyepoint lies involves descending the tree from the root and choosing the left or
`right child of an internal node by comparing the viewpoint with the plane at that node.
`Schumacker selects the faces in a cluster so that a priority ordering can be assigned to
`each face independent of the viewpoint, as shown in Fig. 15.29. After back-face culling has
`been performed relative to the viewpoint, a face with a lower priority number obscures a
`face with a higher number wherever the faces' projections intersect. For any pixel, the
`correct face to display is the highest-priority (lowest-numbered) face in the highest-priority
`cluster whose projection CO\'efS the pixel. Schumacker used special hardware to determine
`the front most face at each pixel. Alternatively, clusters can be displayed in order of increasing
`cluster priority (based on the viewpoint), with each cluster's faces displayed in order of their
`increasing face priority. Rather than take this two-part approach to computing an order in
`which faces should be scan-converted, the BSP tree algorithm uses a generalization of
`Schumacker's approach to calculating cluster priority. lt is based on the observation that a
`polygon will be scan-converted correctly (i.e., will not incorrectly OVCTiap or be incorrectly
`
`1
`
`3
`
`3
`
`(a)
`
`1
`
`(b)
`
`Viewpoint
`
`Fig. 15.29 Face priority. (a) Faces in a cluster and their priorities. A low er number
`indicates a higher priority. (b) Priorities of visible faces. (Based on (SUTH74a).)
`
`0723
`
`

`
`15.5
`
`List-priority Algorithms
`
`617
`
`overlapped by other polygons) if all polygons on the other side of it from the viewer are
`scan-converted first, then it, and then all polygons on the same side of it as the viewer. We
`need to ensure that this is so for each polygon.
`The algorithm makes it easy to determine a correct order for scan conversion by
`building a binary tree of polygons, the BSP tree. Tbe BSP tree's root is a polygon selected
`from those to be d.isplayed; the algorithm works correctly no matter which is picked. The
`root polygon is used to partition the environment into two half-spaces. One half-space
`contains all remaining polygons in front of the root polygon, relative to its surface normal;
`the other contains all polygons behind the root polygon. Any polygon lying on both sides of
`the root polygon's plane is split by the plane and its front and back pieces are assigned to the
`appropriate half-space. One polygon each from the root polygon's front and back
`half-space become its front and back children, and each child is recursively used to divide
`the remaining polygons in its half-space in the same fashion. The algorithm terminates
`when each node contains only a single polygon. Pseudocode for the tree-building phase is
`shown in Fig. 15.30; Fig. 15.31 shows a tree being built.
`Remarkably, the BSP tree may be traversed in a modified in-order tree walk to yield a
`correct priority-ordered polygon list for an arbitrary viewpoint. Consider the root polygon.
`It divides the remaining polygons into two sets, each of which lies entirely on one side of the
`root's plane. Thus, the algorithm needs to only guarantee that the sets are displayed in the
`correct relative order to ensure both that one set's polygons do not interfere with the other's
`and that the root polygon is displayed properly and in the correct order relative to the others.
`U tbe viewer is in the root polygon's front half-space, then the algorithm must first display
`all polygons in the root's rear half-space (those that could be obscured by the root), then the
`root, and finally all polygons in its front half-space (those that could obscure the root).
`Alternatively, if the viewer is in the root polygon's rear half-space, then the algorithm must
`first display all polygons in the root's front half-space, then the root, and finally all
`polygons in its rear half-space. U the polygon is seen on edge, either display order suffices.
`Back-face culling may be accomplished by not displaying a polygon if the eye is in its rear
`half-space. Each of the root's children is recursively processed by this algorithm.
`Pseudocode for displaying a BSP tree is shown in Fig. I 5.32; Fig. 15.33 shows bow the tree
`of Fig. l5.31 (c) is traversed for two different projections.
`Each polygon's plane equation can be transformed as it is considered, and the
`polygon's vertices can be transformed by the displayPolygon routine. The BSP tree can also
`assist in 30 clipping. Any polygon whose plane does not intersect the view volume has one
`subtree lying entirely outside of the view volume that does not need to be considered
`further.
`Which polygon is selected to serve as the root of each subtree can have a significant
`effect on the algorithm's performance. Ideally, the polygon selected should cause the fewest
`splits among all its descendants. A heuristic that is easier to satisfy is to select the polygon
`that splits the fewest of its children. Experience shows that testing just a few (five or six)
`polygons and picking the best provides a good approximation to the best case [FUCH83].
`Like the depth-sort algorithm, the BSP tree algorithm performs intersection and
`sorting entirely at object precision, and relies on the image-precision overwrite capabilities
`of a raster device. Unlike depth sort, it performs all polygon splitting during a pre(cid:173)
`processing step that must be repeated only when the environment changes. Note that more
`
`0724
`
`

`
`678
`
`Visible-surface Determination
`
`typeder struct {
`polygon root;
`BSP.tree •backChild, •frontChild;
`} BSP.tree;
`
`BSP. tree •BSP.makeTree (polygon •polylist)
`{
`
`polygon root;
`polygon •backList, •frontlist:
`polygon p, backPart,frontPart;
`
`I• We assume each polygon is convex. •I
`
`if (palyUst == NULL)
`return NULL;
`else {
`root = BSP.seleclAndRemovePoly (&polylist};
`backlisr = NULL:
`frontList = NlJLL:
`for (each remaining polygon pin poly list) {
`If (polygon pin from of root}
`BSP.addToList (p, &fronrUst};
`else If (polygon pin back of root)
`BSP. addToList (p, &backlist};
`I• Polygon p must be sptiL • I
`else {
`BSP.splitPoly (p, root, &fronrParr, &backPart};
`BSP.addToList (fronrPart, &fronrlisr):
`BSP.addToList (backParr, &backList};
`
`}
`
`}
`return BSP.combineTree (BSP.makeTree (fronrlist) ,
`root,
`BSP. makeTree (backlist));
`
`}
`/• BSP. makeTree •/
`
`}
`
`Fig . 15.30 Pseudocode for building a BSP tree.
`
`polygon splitting may occur than in the depth-sort algorithm.
`List-priority algorithms allow the use of hardware polygon scan converters that are
`typically much faster than are those that check the z at each pixel. The depth-sort and BSP
`tree algorithms display polygons in a back-to-front order, poss.ibly obscuring more distant
`ones later. Thus, like the z-buffer algorithm, shading calculations may be computed more
`than once for each pixel. Alternatively, polygons can instead be displayed in a front-to-back
`order, and each pixel in a polygon can be written only if it has not yet been.
`If a list-priority algorithm is used for bidden-line removal, special attention must be
`paid to the new edges introduced by the subdjvision process. If tbese edges are
`
`0725
`
`

`
`I
`
`'/... ~ I 13
`I X
`X
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`(a)
`
`~ ...
`
`... ...
`
`... ~
`............ :/3
`~ I
`I X
`X I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`'
`
`I
`
`,
`
`,
`
`,
`
`I
`
`I
`
`I
`
`I
`
`I
`
`,
`
`I
`
`I
`I
`
`,- ;
`
`I
`
`,
`
`;
`
`;
`
`... ...
`
`(b)
`
`...
`
`(C)
`
`,
`
`;
`
`;
`
`(d)
`
`... ~
`............ j3
`~ I
`,X ,
`X
`.. ,
`-----~
`--
`-
`-
`~
`:13
`I ,X ,
`
`,X ;
`
`I
`I
`
`I , ,
`
`~
`
`,
`
`,
`
`Fig. 15.31 BSP trees. (a) Top view of scene w ith BSP tree before recursion with
`polygon 3 as root. (b) After building left subtree. (c) Complete tree. (d) Alternate tree
`with polygon 5 as root. (Based on (FUCH83).)
`
`679
`
`0726
`
`

`
`680
`
`Visible-surface Determination
`
`void BSP. displayTree (BSP.tree •me)
`{
`
`if (tree != NULL) {
`if (viewer is in front oftree->root) {
`f• Display back child. root. and front child. •f
`BSP.displayTree (tree- >backChild);
`displayPolygon (tree- > root);
`BSP. dis playTree (tree->frontChild);
`} else {
`f• Display front child, root, and back child. •f
`BSP.dis playTrec (tree->frontChiid) ;
`displayPolygon (tree- >roor);
`f• Only if back-face culling not desired •f
`BSP. displayTree (tree->backChild};
`
`}
`
`}
`
`f• BSP. displayTree *'
`
`}
`
`Fig. 1 5.32 Pseudocode for displaying a BSP tree.
`
`scan-converted like the original polygon edges, they will appear in the picture as
`unwelcome artifacts, and they thus should be ftagged so that they will not be scan(cid:173)
`converted.
`
`15.6 SCAN-LINE ALGORITHMS
`
`Scan-line algorichms, first developed by Wylie, Romney, Evans, and Erdahl rWYLI67],
`Bouknight rsOUK70a; BOUK70b], and Watkins [WATK70], operate at image precision to
`create an image one scan line at a time. The basic approach is an extension of the polygon
`scan-conversion algorithm described in Section 3.6, and thus uses a variety of forms of
`cohe.rence, including scan-line coherence and edge coherence. The difference is that we
`
`..! ~~·
`', . ,
`- ~ Irs!)
`', -:7.3
`.
`....
`// /\'.
`.. ,
`
`I
`I
`
`,
`
`,
`
`,
`
`•
`
`,
`
`,
`
`' '
`
`' '
`
`' ' ' '
`
`I
`I
`
`I .. ,
`
`I
`
`1
`
`t-,
`
`'
`
`7
`
`I
`
`t
`Fig. 15.33 Two traversals of the BSP tree corresponding to two different projections.
`Projectors are shown as thin lines. White numbers indicate drawing order.
`
`0727
`
`

`
`15.6
`
`Scan-line Algorithms
`
`681
`
`deal not with just one polygon, but rather with a set of polygons. The first step is to create
`an edge table (Ef) for all nonhorizontal edges of all polygons projected on the view plane.
`As before, horizontal edges are ignored. Entries in the ET are sorted into buckets based on
`each edge's smaller y coordinate, and within buckets are ordered by increasing x coordinate
`of their lower endpoint. Each entry contains
`
`I. The x coordinate of the end with the smaller y coordinate
`2. The y coordinate of the edge's other end
`3. The x increment, tu, used in stepping from one scan line to the next (tu is the inverse
`slope of the edge)
`4. The polygon identification number, indicating the polygon to which the edge belongs.
`
`Also required is a polygon table (PT) that contains at least the following information
`for each polygon, in addition to its ID:
`
`I. The coefficients of the plane equation
`2. Shading or color information for the polygon
`3. An in-out Boolean flag, initialized to false and used during scan-line processing.
`
`Figure 15.34 shows the projection of two triangles onto the (x, y) plane; hidden edges
`are shown as dashed lines. The soned ET for this figure contains entries for AB. AC. FD.
`FE, CB, and DE. The PT has entries for ABC and DEF.
`The active-edge table (AET) used in Section 3.6 is needed here also. It is always kept in
`order of increasing x. Figure 15.35 shows ET, PT, and AET entries. By the time the
`algorithm has progressed upward to the scan line y = a, the AET contains AB and AC, in
`that order. The edges are processed from left to right. To process AB, we first invert the
`in-out flag of polygon ABC. ln this case, the flag becomes true; thus, the scan is now ''in"
`the polygon, so the polygon must be considered. Now, because the scan is "in" only one
`polygon (ABC), it must be visible, so the shading for ABC is applied to the span from edge
`AB to the next edge in the AET, edge AC. This is an instance of span coherence. At this
`
`y
`
`E
`
`L------------------------------------+ X
`Fig. 15.34 Two polygons being processed by a scan-line algorithm.
`
`0728
`
`

`
`682
`
`Visible-surface Determination
`
`ET entry
`
`X
`
`Y.,...
`
`/!i)(
`
`10
`
`•
`
`PT entry
`
`10
`
`Planeeq.
`
`Shading info
`
`AET contents
`Scan line
`Entries
`AB AC
`a
`AB AC FD FE
`fJ
`
`In-out I y, Y+ 1 AB DE CB FE
`
`Y+ 2
`
`AB CB DE FE
`
`Fig. 15.35 ET. PT. AET for the scan-line algorithm.
`
`edge the Hag for ABC is inverted to false, so that the scan is no longer "in" any polygons.
`Furthermore, because AC is the last edge in the AET, the scan-line processing is completed.
`The AET is updated from the ET and is again ordered on x because some of its edges may
`have crossed, and the next scan line is processed.
`When the scan line y "' fJ is encountered, the ordered AET is AB, AC, FD, and FE.
`Processing proceeds much as before. There are two polygons on the scan line, but the scan
`is · • in" only one polygon at a time.
`For scan line y = 1· things are more interesting. Entering ABC causes its Hag to
`become true. ABC's shade is used for the span up to the next edge, DE. At this point, the
`flag for DEF also becomes true, so the scan is "in" two polygons. (It is useful to keep an
`explicit list of polygons whose in-<>ut Hag is true, and also to keep a count of how many
`polygons are on the list.) We must now decide whether ABC or DEF is closer to the viewer,
`which we dete.rmine by evaluating the plane equations of both polygons for z at y • 1 and
`with x equal to the intersection of y = 1 with edge DE. This value of xis in the AET entry
`for DE. In our example, DEF bas a larger z and thus is visible. Therefore, assuming
`nonpenetrating polygons, the shading for DEF is used for the span to edge CB, at which
`point ABC's flag becomes false and the scan is again "in" only one polygon DEF whose
`shade continues to be used up to edge FE. Figure 15.36 shows the relationship of the two
`polygons and they = 1 plane; the two thick lines are the intersections of the polygons with
`the plane.
`
`z
`Fig. 15.36 Intersections of polygons ABC and DEF with the plane y = y.
`
`X
`
`0729
`
`

`
`16.6
`
`Scan-line Algorithms
`
`683
`
`r
`
`G
`
`Fig. 16.37 Three nonpenetrating polygons. Depth calculations do not need to be
`made when scan line y leaves the obscured polygon ABC, since nonpenetrating
`polygons maintain their relative z order.
`
`Suppose there is a large polygon GHIJ behind both ABC and DEF, as in Fig. 15.37.
`Then, when they = 'Y scan line comes to edge CB, the scan is still " in" polygons DEF and
`GHIJ, so depth calculations are perfonned again. These calculations can be avoided,
`however, if we assume that none of the polygons penetrate another. This assumption means
`that, when the scan leaves ABC, the depth relationship between DEF and GHIJ cann01
`change, and DEF continues to be in front. Therefore, depth computations are unnecessary
`when the scan leaves an obscured polygon, and are required only when it leaves an
`obscuring polygon.
`To use this algorithm properly for penetrating polygons, as shown in Fig. 15.38, we
`break up KLM into KLL' M' and L' MM' , introducing the false edge M' L'. Alternatively, the
`algorithm can be modified to find the point of penetration on a scan line as the scan line is
`processed.
`Another modification to this algorithm uses depth coherence. Assuming that polygons
`do not penetrate each other, Romney noted that, if the same edges are in the AET on one
`scan line as are on the immediately preceding scan line, and if they are in the same order,
`then no changes in depth relationships have occurred on any part of the scan line and no new
`depth computations are needed [ROMN68]. The record of visible spans on the previous
`scan line then defines the spans on the current scan line. Such is the case for scan lines y = 'Y
`s
`
`K
`
`Fig. 15.38 Polygon KLM pierces polygon RSTat the line L'M'.
`
`T
`
`0730
`
`

`
`684
`
`Visible-surface Det erm ination
`
`and)' = 'Y + I in Fig. l5.34, for both of which the spans from AB to DE and from DE to
`FE are visible. The depth coherence in this figure is lost, however, as we go from y = y + I
`to y = y + 2, because edges DE and CB change order in the AET (a situation that the
`algorithm must accommodate). The visible spans therefore change and. in this case,
`become AS to CB and DE to FE. Hamlin and Gear [HAMLn] show how depth coherence
`can sometimes be maintained even when edges do change order in the AET.
`We have not yet discussed how to treat the background. The simplest way is to initialize
`the frame buffer to the background color, so the algorithm needs to process only scan lines
`that intersect edges. Another way is to include in the scene definition a large enough
`p