662
`
`Visible-surface Determination
`
`where b is the number of times the bounding volume is tested for intersection, B is the cost
`of performing an intersection test on the bounding volume, o is the number of times the
`object is tested for intersection (the number of times the bounding volume is actually
`intersected), and 0 is the cost of performing an intersection test on the object.
`Since the object intersection test is performed only when the bound.ing volume is
`actually intersected, o <b. Although 0 and bare constant for a particular object and set of
`tests to be performed, Band o vary as a function of the bounding volume's shape and size.
`A " tighter" bounding volume, which minimizes o, is typically associated with a greater B.
`A bounding volume's effectiveness may also depend on an object's orientation or the kind
`of objects with which that object will be intersected. Compare the two bounding volumes
`for the wagon wheel shown in Fig. 15. 16. If the object is to be intersected with projectors
`perpendicular to the (x. y) plane, then the tighter bounding volume is the sphere. If
`
`y L.
`
`--"Jo-•-.... ..._
`,.f' /
`I
`\
`''\.._
`ee - " -- • -- •-..,,
`I
`\
`\ \
`/ I
`I
`I I I
`f
`\
`\ \
`~·--·---·---·--·~
`t
`I
`l
`1 \
`
`---
`\\ \ l i ,,
`\ ·--~---!---~--+ .,' j"
`
`-+
`
`\
`
`\
`
`'~, \
`
`I
`
`•
`I
`-- - ~"'
`.... ..~
`I f'
`
`Z
`
`----~'
`Fig. 15.16 Bounding volume selection. (Courtesy of Hank Weghorst, Gary Hooper,
`Donald P. Greenberg, Program of Computer Graphics, Cornell University, 1g84.)
`
`- 44
`
`-
`
`TEXAS INSTRUMENTS EX. 1009 - 709/1253
`
`

`
`15.2
`
`Techniques for Efficient Visible-surface Algorithms
`
`663
`
`projec10rs are perpendicular to the (x. z) or (y, z) planes, then the rectangular extent is the
`tighter bounding volume. Therefore, multiple bounding volumes may be associated with an
`object and an appropriate one selected depending on the circumstances.
`
`15.2.4 Back-Face Culling
`
`If an object is approximated by a solid polyhedron, then its polygonal faces completely
`enclose its volume. Assume that all the polygons have been defined such that their surface
`normals point out of their polyhedron. If none of the polyhedron's interior is exposed by
`the front clipping plane, then those polygons whose surface normals point away from the
`observer lie on a part of the polyhedron whose visibility is completely blocked by other
`closer polygons, as shown in Fig. 15.17. Such invisible back-facing polygons can be
`eliminated from further processing, a technique known as back-face culling. By analogy,
`those polygons that are not back-facing are often called front-faciJJg.
`In eye coordinates, a back-facing polygon may be identified by the nonnegative dot
`product that its surface normal forms with the vector from the center of projection to any
`point on the polygon. (Strictly speaking, the dot product is positive for a back-facing
`polygon; a zero dot product indicates a polygon being viewed on edge.) Assuming that the
`perspective transformation has been performed or that an orthographic projection onto the
`(x, y) plane is desired, then the direction of projection is (0, 0, -
`I). In this case, the
`dot-product test reduces to selecting a polygon as back-facing only if its surface normal has
`a negative z coordinate. If the environment consists of a single convex polyhedron,
`back-face culling is the only visible-surface calculation that needs to be performed.
`Otherwise, there may be front-facing polygons, such as C and E in Fig. 15. 17, that are
`partially or totally obscured.
`If the polyhedra have missing or clipped front faces, or if the polygons are not part of
`polyhedra at all, then back -facing polygons may still be given special treatment. If culling is
`not desired, the simplest approach is to treat a back-facing polygon as though it were
`from-facing, Hipping its normal in the opposite d irection. In PHIGS+, the user can specify
`a completely separate set of properties for ea.ch side of a surface.
`
`z
`
`Fig. 15.17 Back-face culling. Back-facing polygons (A.B,D,F) shown in gray are
`eliminated, whereas front-facing polygons (C,E,G,H) are retained.
`
`TEXAS INSTRUMENTS EX. 1009 - 710/1253
`
`

`
`664
`
`Visible-surface Determination
`
`Extrapolaling from Section 7.12.2's parity-check algorithm for determining whelher a
`point is contained in a polygon, no1e that a projector passing through a polyhedron
`intersects the same number of back-facing polygons as of front-facing ones. Thus, a point in
`a polyhedron's projection lies in the projections of as many back-facing polygons as
`front-facing ones. Back-face culling therefore halve.~ the number of polygons to be
`considered for each pixel in an image-precision visible-surface algorithm. On average,
`approximately one-half of a polyhedron's polygons are back-facing. Thus, back-face
`culling also typically hal'i'CS the number of polygons to be considered by the remainder of an
`object-preci ion visible-surface algorithm. (Note,llowever, that 1his is true only on average.
`For example, a pyramid's base may be that object's only back· or fron1-facing polygon.)
`As described so far, back-face culling is an object-precision 1echnique thai requires
`time linear in the number of polygons. Sublinear performance can be oblained by
`preprocessing the objects 10 be displayed. For example, consider a cube centered aboul the
`origin of i1s own object coordinate sys1em, with its faces perpendicular to the coordinate
`system's axes. From any viewpoinl outside the cube, at most three of its faces are visible.
`Furthermore, each octant of 1he cube's coordinate system is associated with a specific set of
`three pot.emially visible faces. Therefore, the position of the viewpoinl relative to the cube's
`coordinate sys1em can be used to select one of the eight sets of three potentially visible
`faces. For objects with a relatively small number of faces, a table may be made up in
`advance 10 allow visible-surface determination without processing all the object's faces for
`each change of viewpoint.
`A table of visible faces indexed by viewpoint equivalence class may be quite large,
`however, for an object with many faces. Tanimoto [TAN1771 suggests as an alternative a
`graph-theoretic approach thai takes advantage of fr.une coherence. A graph is constructed
`with a node for each face of a convex polyhedron, and a graph edge connecting each pair of
`nodes whose faces share a polygon edge. The list of edges separating visible faces from
`invisible ones is then computed for an initial viewpoint. This list contains all edges on the
`object's silhoueue. Tanimoto shows that, as the viewpoinl changes between frames. only
`the visibilities of faces lying be1wecn the old and new silhouettes need to be recomputed.
`
`15.2 .5 Spatial Partitioning
`
`Spatial partitioni11g (also known as spatial subdivision) allows us to break down a large
`problem inlo a number of smaller ones. The basic approach is to assign objects or their
`projections 10 spatially coherent groups as a preprocessing step. For CJtample, we can divide
`the projection plane with a coarse, regular 20 rectangular grid and determine in which grid
`spaces each object's projection lies. Projections need to be companed for overlap with only
`those other projections that fall within their grid boxes. This technique is used by
`[ENCA72; MAHN73; FRAN80; HED082]. Spatial partitioning can be used to impose a
`regular 30 grid on the objects in the environment. The process of determining which
`objects intersecl with a projector can 1hen be sped up by firs1 de1ennining which partitions
`the projector intersects, and then tesling only the objects lying within those partitions
`(Section 15.10).
`If the objects being depicted are unequally distributed in space, i1 may be more efficien1
`to use adapti1-e partitioning, in which the size of each partition varies. One approach 10
`adaptive partilioning is to subdivide space recursively until some lennination criterion is
`
`TEXAS INSTRUMENTS EX. 1009 - 711/1253
`
`

`
`16.3
`
`Algorithms for Visible-line Determination
`
`665
`
`Floor 1 Floor 2 Floor 3 Floor 4
`
`~ Room 1 Room 2 Room 3
`
`Fig. 15.18 Hierarchy can be used to restrict the number of object comparisons
`needed. Only if a projector intersects the building and floor 1 does it need to be tested
`for intersection with rooms 1 through 3.
`
`fulfilled for each partition. For example, subdivision may stop when there are fewer than
`some maximum number of objects in a partition [TAMM82]. The quadtree, octree, and
`SSP-tree data structures of Section I 2.6 are particularly attractive for this purpose.
`
`15.2.6 Hierarchy
`
`As we saw in Chapter 7, hierarchies can be useful for relating the structure and motion of
`different objects. A nested hierarchical model, in which each child is considered part of its
`parent, can also be used to restrict the number of object comparisons needed by a
`visible-surface algorithm [CLAR76; RUBI80; WEGH84]. An object on one level of the
`hierarchy can serve as an extent for its children if they are entirely contained within it, as
`shown in Fig. 15.18. In this case, if two objects in the hierarchy fail to intersect, the
`lower" level objects of one do not need to be tested for intersection with those of the other.
`Similarly, only if a projector is found to penetrate an object in the hierarchy must it be
`tested against the object's children. This use of hierarchy is an important instance of object
`coherence. A way to automate the construction of hierarchies is discussed in Section
`15.10.2.
`
`15.3 ALGORITHMS FOR VISIBLE-LINE DETERMINATION
`
`Now that we have discussed a number of general techniques, we introduce some visible-line
`and visible-surface algorithms to see how these techniques are used. We begin with
`visible-line algorithms. The algorithms presented here all operate in object precision and
`produce as output a list of visible line segments suitable for vector display. The
`visible-surface algorithms discussed later can also be used for visible-line determination by
`rendering each surface as a background-colored interior surrounded by a border of the
`desired line color; most visible-surface algorithms produce an image-precision array of
`pixels, however, rather than an object-precision list of edges.
`
`15.3.1 Roberts's Algorithm
`
`The earliest visible-line algorithm was developed by Roberts [ROBE63]. It requires that
`each edge be part of the face of a convex polyhedron. First, back-face culling is used to
`remove all edges shared by a pair of a polyhedron's back-facing polygons. Next, each
`remaining edge is compared with each polyhedron that might obscure it. Many polyhedra
`
`TEXAS INSTRUMENTS EX. 1009 - 712/1253
`
`

`
`888
`
`Visible-surface Determination
`
`can be trivially eliminated from the comparison through extent testing: the extents of their
`projections may fail to overlap in x or y, or one object's extent may be farther back in z than
`is the other. Those polyhedra that are tested are compared in sequence with the edge.
`Because the polyhedra are convex, there is at most one contiguous group of points on any
`line that is blocked from the observer by any polyhedron. Thus, each polyhedron either
`obscures the edge totally or causes one or two pieces to remain. Any remaining pieces of the
`edge are compared with the next polyhedron.
`Roberts's visibility test is performed with a parametric version of the projector from
`the eye to a point on the edge being tested. He uses a linear-programming approach to solve
`for those values of the line equation that cause the projector to pass through a polyhedron,
`resulting in t.he invisibility of the endpoint. The projector passes through a polyhedron if it
`contains some point that is inside all the polyhedron's front faces. Rogers (ROGE85]
`provides a detailed explanation of Roberts's algorithm and discusses ways in which that
`algorithm can be further improved.
`
`1 5.3 .2 Appel's Algorithm
`
`Several more general visible-line algorithms [APPE67; GALI69; LOUTIO] require only
`that lines be the edges of polygons, not polyhedra. These algorithms also consider only
`lines that bound front-facing polygons, and taice advantage of edge-coherence in a fashion
`typified by Appel's algorithm. Appel [APPE67] defines the quantitative invisibility of a
`point on a line as the number of front-facing polygons that obscure that point. When a line
`passes behind a front-facing polygon, its quantitative invisibility is incremented by I; when
`it passes out from behind that polygon, its quantitative invisibility is decremented by I. A
`line is visible only when its quantitative invisibility is 0. Line AB in Fig. 15. 19 is annotated
`with the quantitative invisibility of each of its segments. If interpenetrating polygons are not
`allowed, a line's quantitative invisibility changes only when it passes behind what Appel
`
`Fig. 1 5.19 Quantitative invisibility of a line. Dashed lines are hidden. Intersections of
`AS's projection with projections of contour lines are shown as large dots (e), and each
`segment of AB is marl<ed with its quantitative invisibility.
`
`TEXAS INSTRUMENTS EX. 1009 - 713/1253
`
`

`
`15.3
`
`Algorithms for Visible-line Determination
`
`667
`
`calls a contour li11e. A contour line is either an edge shared by a front-facing and a
`back-facing polygon, or the unsbared edge of a front-facing polygon that is not part of a
`closed polyhedron. An edge shared by two front-facing polygons causes no change in
`visibility and therefore is not a contour line. In Fig. 15.19, edges AB, CD, DF, and KLare
`contour lines, whereas edges CE, EF, and JK are not.
`A contour line passes in front of the edge under consideration if it pierces the triangle
`formed by the eyepoint and the edge's two endpoints. Whether it does so can be determined
`by a point-in-polygon containment test, such as that discussed in Section 7.12.2. The
`projection of such a contour line on the edge can be found by clipping the edge against the
`plane determined by the eyepoint and the contour line. Appel 's algorithm requires that all
`polygon edges be drawn in a consistent direction about the polygon, so that the sign of the
`change in quantitative invisibility is determined by the sign of the cross-product of the edge
`with the contOur line.
`The algorithm first computes the quantitative invisibility of a "seed" vertex of an
`object by detennining the number of front-facing polygons that hide it. This can be done
`by a brute.-force computation of all front-facing polygons whose intersection with the pro(cid:173)
`jector to the seed vertex is closer than is the seed vertex itself. The algorithm then takes ad(cid:173)
`vantage of edge coherence by propagating this value along the edges emanating from
`the point, incrementing or decrementing the value at each point at which an edge passes
`behind a contour line. Only sections of edges whose quantitative invisibility is zero are
`drawn. When each line's other endpoint is reached, the quantitative invisibility asso(cid:173)
`ciated with that endpoint becomes the initial quantitative invisibility of all lines emanat(cid:173)
`ing in turn from it.
`At vertices through wb.ich a contour line passes, there is a complication that requires us
`to make a correction when propagating the quantitative invisibility. One or more lines
`emanating from the vertex may be hidden by one or more front-facing polygons sharing the
`vertex. For example, in Fig. 15.19, edge JK has a quantitative invisibility of 0 , wb.ile edge
`KL has a quantitative invisibility of I because it is hidden by the object's top face. This
`change in quantitative invisibility at a vertex can be taken into account by testing the edge
`against the front-facing polygons that share the vertex.
`For an algorithm such as Appel's to handle intersecting polygons, it is necessary to
`compute the intersections of edges with front-facing polygons and to use each such
`intersection to increment or decrement the quantitative invisibility. Since visible-line
`algorithms typically compare whole edges with other edges or objects, they can benefit
`greatly from spatial-partitioning approaches. Each edge then needs to be compared with
`only the other edges or objects in the grid boxes containing its projection.
`
`15.3.3 Haloed Unes
`
`Any visible-line algorithm can be easily adapted to show hidden lines as dotted, as dashed,
`of lower intensity, or with some other rendering style supported by the display device. The
`program then outputs the hidden line segments in the line style selected, instead of
`suppressing them. In contrast, Appel , Rohlf, and Stein [APPE79] describe an algorithm for
`rendering haloed lines, as shown in Fig. 15.20. Each line is surrounded on both sides by a
`halo that obscures those parts of lines passing beb.ind it. This algorithm, unlike those
`
`TEXAS INSTRUMENTS EX. 1009 - 714/1253
`
`

`
`668
`
`Visible-surface Determination
`
`(a)
`
`(b)
`
`(c)
`
`Fig. 15.20 Three heads rendered (a) without hidden lines eliminated, (b) with hidden
`lines haloed, and (c) with hidden lines eliminated. (Courtesy of Arthur Appel, IBM T .J .
`Watson Research Center.)
`
`discussed previously, does not require each line to be part of an opaque polygonal face.
`Lines that pass behind others are obscured only around their intersection on the view plane.
`The algorithm intersects each line with those passing in front of it, keeps track of those
`sections that are obscured by halos, and draws the vis.ible sections of each line after the
`intersections have been calculated. If the halos are wider than the spacing between lines,
`then an effect similar to conventional hidden-line elimination is achieved, except that a
`line's halo extends outside a polygon of which it may be an edge.
`In the rest of this chapter, we discuss the rich variety of algorithms developed for
`visible-surface determination. We concentrate here on computing which parts of an object's
`surfaces are visible, leaving the determination of surface color to Chapter 16. In describing
`each algorithm, we emphasize its application to polygons, but point out when it can be
`generalized to handle other objects.
`
`15.4 THE z-BUFFER ALGORITHM
`
`The z-buffer or depth-buffer image-precision algorithm, developed by Catmull [CATM74b ],
`is one of the simplest visible-surface algorithms to implement in either software or
`hardware. ll requires that we have available not only a frame buffer F in which color values
`are stored, but also a z-buffer Z, with the same number of entries, in which a z-value is
`stored for each pixeL The z-buJfer is initialized to zero, representing the z-value at the back
`clipping plane, and the frame buffer is initialized to the background color. The largest v-.tlue
`that can be stored in the z-buffer represents the z of the front clipping plane. Polygons are
`scan-converted into the frame buffer in arbitrary order. During the scan-conversion process,
`if the polygon point being scan-converted at (x, y) is no farther from the viewer than is the
`point whose color and depth are currently in the buffers, then the new point's color and
`depth replace the old values. The pseudocode for the z-buffer algorithm is shown in Fig.
`15.21. The WritePixel and ReadPixel procedures introduced inChapter3 are supplemented
`here by WriteZ and ReadZ procedures that write and read the z-buffer.
`
`TEXAS INSTRUMENTS EX. 1009 - 715/1253
`
`

`
`16.4
`
`The z-Buffer Algorithm
`
`669
`
`void zBuffer( void)
`{
`
`}
`
`}
`
`int x, y;
`for (y = 0; y < YMAX; y++) {
`for (x = O; x < XMAX; x++) {
`WritePixel (x, y, BACKGROUND. VALUE);
`WriteZ (x, y, 0);
`
`/• Clear frame buffer and z-buffer • I
`
`I• Draw polygons +I
`for (each polygon) {
`for (each pixel in polygon's projection) {
`double pz =polygon 's z-value at pixel coords (x, y);
`if (pz >= ReadZ (x, y)) {
`I• New point is not farther •I
`WriteZ (x, y, pz);
`WritePixel (x, y, polygon s color at pixel coords (x, y));
`
`}
`
`}
`
`}
`
`}
`I• zBuffer •I
`Fig. 15.21 Pseudocode for the z-buffer algorithm.
`
`No presorting is necessary and no object-object comparisons are required. The entire
`process is no more than a search over each set of pairs {Z,{x ,y), F;(x, y)} for fixed x and y, to
`find the largest Z;. The z-buffer and the frame buffer record the information associated with
`the largest z encountered thus far for each (x, y). Thus, polygons appear on the screen in the
`order in which they are processed. Each polygon may be scan-converted one scan line at a
`time into the buffers, as described in Section 3.6. Figure 15.22 shows the addition of two
`polygons to an image. Each pixel's shade is shown by its color; its z is shown as a number.
`Remembering our discussion of depth coherence, we can simplify the calculation of z
`for each point on a scan line by exploiting the fact that a polygon is planar. Normally, to
`calculate z. we would solve the plane equation Ax + By + Cz + D = 0 for the variable z:
`- D - Ax- By
`c
`Now, if at (x, y) Eq. (15.6) evaluates to z1, then at (x + IU, y) the value of z is
`A
`z, - c<~U).
`
`(15.6)
`
`( 15. 7)
`
`z=
`
`Only one subtraction is needed to calculate z(x + l ,y) given z{x, y), since the quotient AJC
`is constant and ax = I. A similar incremental calculation can be performed to determine
`the first value of z on the next scan line, decrementing by BIC for each Ay. Alternatively, if
`
`TEXAS INSTRUMENTS EX. 1009 - 716/1253
`
`

`
`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.
`
`TEXAS INSTRUMENTS EX. 1009 - 717/1253
`
`

`
`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
`
`TEXAS INSTRUMENTS EX. 1009 - 718/1253
`
`

`
`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.
`
`TEXAS INSTRUMENTS EX. 1009 - 719/1253
`
`

`
`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