EXHIBIT 1002
`
`EXHIBIT 1002
`
`

`

`The ZZ-Buffer:
`A Simple and Efficient Rendering Algorithm
`with Reliable Antialiasing
`∗
`
`†
`Jorge Stolfi
`DEC Systems Research Center
`
`David Salesin
`Stanford University
`
`Abstract
`
`1 Introduction
`
`The ZZ-buffer is a new rendering algorithm that
`is simple, efficient, and produces high-quality im-
`ages. The algorithm correctly renders transpar-
`ent surfaces, shadows with real penumbrae, and
`depth of field effects. The ZZ-buffer algorithm is
`substantially faster than ray tracing and nearly
`as versatile. While the ZZ-buffer is somewhat
`slower than the Z-buffer or A-buffer, it avoids the
`aliasing and other artifacts of these algorithms.
`The algorithm’s efficiency comes from a screen-
`space object indexing scheme, and from the use of
`lazy evaluation for visibility tests. It achieves reli-
`able antialiasing by employing an adaptive form of
`stochastic supersampling. The algorithm is simple
`enough that we give most of its code here in this
`paper. The algorithm has been implemented as
`part of a commercial production system and has
`proved robust over a large variety of images.
`
`∗
`
`Stanford University, Computer Science
`Address:
`Dept., Stanford, CA 94305, phone (415) 723-4102. Part
`of the work was done while this author was consulting at
`Sogitec Audiovisuel in Paris.
`†
`Address: DEC Systems Research Center, 130 Lytton
`Ave., Palo Alto, CA 94301, phone (415) 853-2226.
`
`1
`
`Existing rendering algorithms offer only the un-
`pleasant choice between low quality and high com-
`putational cost. One must either use an algo-
`rithm that makes unreliable approximations, such
`as the Z-buffer [5, 12] or A-buffer [4], and put up
`with aliasing and other artifacts, or fall back on a
`general-purpose ray tracing algorithm [7, 16, 30],
`and be prepared to pay the price.
`We present here the ZZ-buffer algorithm, a new
`rendering method that avoids aliasing and most
`other objectionable artifacts, and that is consider-
`ably more efficient than ray tracing. In addition
`to providing reliable antialiasing, the ZZ-buffer al-
`gorithm can handle transparent surfaces, shadows
`with real penumbrae, and depth of field effects. It
`can also handle a wide variety of geometric prim-
`itives directly, without converting them first to
`polygons or some other intermediate form.
`The ZZ-buffer algorithm superficially resembles
`the A-buffer and Z-buffer algorithms in that it uses
`an image-space buffer to aid in determining visi-
`bility. However, the ZZ-buffer algorithm avoids
`the aliasing and quantization artifacts that are
`inherent in the Z-buffer by using stochastic sam-
`pling [6, 9, 18, 19] and performing precise visibility
`tests at each sample point. Note that such arti-
`facts can also appear with an A-buffer whenever
`
`

`

`the scene contains features smaller than the reso-
`lution of the A-buffer’s pixel mask [4] or whenever
`surfaces become too close within a pixel.
`The ZZ-buffer improves on the performance of
`ray tracing by three major strategies. First, it
`uses an efficient indexing scheme, similar to the
`“item buffer” of Weghorst et. al. [29], for deter-
`mining the objects intersected by primary rays and
`by rays to the light sources. Second, it uses the
`same indexing scheme to detect those pixels that
`contain no small features and that can therefore
`be sampled by a single ray. Finally, it uses rough
`approximations to the depths of objects at each
`pixel in order to eliminate invisible objects with-
`out ever computing their exact depths. (The ZZ-
`buffer does not optimize the tracing of reflected
`or refracted rays, although these features can be
`incorporated into the ZZ-buffer algorithm at the
`usual cost.)
`Although our algorithm does more work per
`pixel than the A-buffer to determine visibility, the
`ZZ-buffer only shades surfaces that are actually
`visible, whereas the A-buffer must shade them all.
`The paper is organized as follows. Section 2 in-
`troduces the ZZ-buffer in its general form. Section
`3 shows how the ZZ-buffer is used in a rendering
`algorithm. Section 4 gives a more detailed anal-
`ysis of the ZZ-buffer algorithm’s capabilities and
`running time and compares it to the A-buffer and
`to some typical acceleration schemes for general
`ray tracing. Finally, Section 5 comments on our
`implementations of the ZZ-buffer, and Section 6
`proposes some areas for further research.
`
`2 The ZZ-buffer
`
`The ZZ-buffer is a two-dimensional array ZZ[i, j],
`each of whose entries is associated with a rectan-
`gular cell in the screen plane. Each cell covers a
`fixed-sized rectangular block of pixels (or possibly
`a single pixel) of the final image. See figure 1.
`
`Figure 1. The ZZ-buffer.
`
`2
`
`Each entry of the ZZ-buffer contains the follow-
`ing fields:
`
`type Entry = record
`tilelist:
`pointer to TileList
`zmin, zmax: Coordinate
`opaque:
`boolean
`end record
`The tilelist field points to a linked list of objects
`that may be visible within the ZZ-buffer cell. The
`opaque flag tells whether this list contains at least
`one object that is opaque and covers the cell en-
`tirely.
`The zmin and zmax fields (from which the ZZ-
`buffer derives its name) provide an estimate of the
`range of z-coordinates (depths) spanned by the
`visible objects in the cell. The range [zmin, zmax]
`stored in the ZZ-buffer need not be accurate, but
`must include the z-coordinates of every visible
`point of the model within the cell. See figure 2.
`
`Figure 2. Tiles.
`
`Each element of the tilelist is called a tile and de-
`scribes an object implicitly clipped to a ZZ-buffer
`cell. The contents of a tile are similar to those of
`a ZZ-buffer entry:
`
`type Tile = record
`obj:
`pointer to Object
`zmin, zmax: Coordinate
`opaque:
`boolean
`end record
`
`type TileList = record
`first:
`Tile
`rest:
`pointer to TileList
`end record
`However, in a Tile record, the opaque, zmin, and
`zmax fields refer to properties of a single object (re-
`stricted to the cell in question), whereas the fields
`of the ZZ-buffer entry summarize the properties of
`the entire list of objects.
`Each ZZ-buffer entry is constructed by repeated
`calls to the AddTile procedure below. The proce-
`dure performs a quick visibility test, based on the
`zmin, zmax, and opaque attributes of the new tile
`and of the ZZ-buffer entry. The new tile is thrown
`
`

`

`away if it is completely obscured by those in the
`list. Conversely, the tiles already in the list are
`thrown away if they are completely obscured by
`the new one.
`If neither of these two conditions
`holds, then the new object is appended to the list
`of potentially visible objects, and the fields zmin,
`zmax, and opaque of the ZZ-buffer entry are up-
`dated.
`
`procedure AddTile takes
`e:
`var Entry
`new: Tile
`begin
`if not e.opaque or new.zmin ≤ e.zmax then
`{ The new object may be visible: }
`if opaque and e.zmin > new.zmax then
`{ The new object blocks all the old ones: }
`reclaim(e.tilelist)
`e.tilelist ← alloc TileList[new, nil]
`e.zmin ← new.zmin
`e.zmax ← new.zmax
`e.opaque ← new.opaque
`else{ Add object to list and update entry: }
`e.tilelist ← alloc TileList[new, e.tilelist]
`e.zmin ← min(e.zmin, new.zmin)
`if e.opaque and new.opaque then
`e.zmax ← min(e.zmax, new.zmax)
`elseif not e.opaque and new.opaque then
`e.zmax ← new.zmax
`elseif not e.opaque then
`e.zmax ← max(e.zmax, new.zmax)
`endif
`e.opaque ← e.opaque or new.opaque
`endif
`endif
`end procedure
`
`Note that this operation takes only a constant
`amount of time per object and per cell, because
`whenever the z interval of the new tile overlaps
`that of the entire list, we just append the new tile
`to the list. We do not attempt to throw away the
`individual tiles that are obscured by the new tile
`because the time spent in this search is likely to
`be wasted when a subsequent tile obscures them
`all.
`
`3 ZZ-buffer rendering
`
`The ZZ-buffer rendering algorithm can be divided
`into two phases.
`In the first phase, called scan
`conversion, we take each object, compute a rough
`[zmin, zmax] interval for every cell that may con-
`tain some part of the object, and store the re-
`sulting tiles into the ZZ-buffer using the AddTile
`operation. In the second phase, called rendering,
`
`the visibility of objects within each pixel is fur-
`ther refined (if it has not already been resolved
`by the ZZ-buffer), visible objects are shaded, and
`the shades are blended to produce the final pixel
`colors.
`In practice, memory limitations may dictate
`that these two phases be interleaved on a scanline-
`by-scanline basis. This approach entails trans-
`forming all geometric primitives to screen coor-
`dinates at the outset and sorting them in y, but
`then allows us to keep in memory only those ob-
`jects that intersect the current scanline.
`In the algorithms below, we assume that each
`object O is represented internally by some record
`O.data, containing geometric parameters (already
`transformed to screen coordinates) and other data
`about the object, along with a suite of proce-
`dures O.methods that implement the basic render-
`ing and visibility functions that our algorithm re-
`quires. We will write O.M(x, . . .) as a shorthand
`for O.methods.M(O.data, x, . . .).
`
`3.1 Scan conversion
`In the scan-conversion phase, we estimate the set
`of cells that each object covers, either totally or
`partially. We also have to estimate the range of
`screen depths [zmin, zmax] of the visible parts of
`the object within each cell, and whether the ob-
`ject is “opaque,” that is, whether it is made of an
`opaque material and completely covers the cell.
`Both the [zmin, zmax] interval and the opaque
`flag can be rough approximations to the truth,
`as long as they are conservative. Thus, the
`[zmin, zmax] interval must completely contain the
`actual z depths of the visible portions of the ob-
`ject, but need not represent the smallest such in-
`terval. Similarly, the opaque flag should be true
`only if the object is indeed opaque and guaranteed
`to completely cover the cell, but it may always be
`set to false in case of doubt.
`The implementor of the scan-conversion pro-
`cess, therefore, has great latitude in performing
`these estimates. At one extreme, the program-
`mer could simply call AddTile for every cell within
`the xy-bounding box of the object, with opaque =
`false and [zmin, zmax] equal to the object’s over-
`all z-extent. This “sloppy” approach would be per-
`fectly correct. However, it will generally result in
`longer tile lists and make the rendering phase more
`expensive.
`At the other extreme, the programmer might
`code a very precise scan-conversion procedure that
`computes the tightest z range possible for each tile,
`and sets the opaque flag to true every time the
`time the object is opaque and completely covers
`the cell. However, this approach may also be inef-
`ficient since it means wasting a lot of computation
`on objects that may become obscured later on, and
`
`3
`
`

`

`since in many cases visibility can be determined by
`a much coarser estimate.
`The best approach to writing scan-conversion
`routines is to strike a balance between these two
`extremes. To illustrate these tradeoffs, we present
`scan-conversion routines for two popular geomet-
`ric primitives: polygons and quadric surfaces.
`
`Polygons
`
`We classify polygons into two categories: small
`and large. We consider a polygon small if its xy-
`bounding box does not span more than a few cells
`(say, 5 or 6) in each dimension. For a polygon
`this small, there is little difference between the
`cells touched by the polygon and by its bounding
`box, so we can use the sloppy approach described
`above.
`If the polygon is larger than a few cells, we
`can treat it with an ordinary scan-conversion al-
`gorithm [22], except for one small change: as the
`scan conversion proceeds, we keep track of two po-
`sitions along each active edge instead of just one.
`See figure 3. For each edge of the polygon, imagine
`two “bugs” that trace Bresenham paths along the
`grid lines bracketing that edge. These paths di-
`vide the cells into three main sets, characterized by
`how much each cell is covered by the polygon: the
`outside cells, disjoint from the polygon; the inside
`cells, completely covered by it; and the boundary
`cells, covered only in part.
`
`Figure 3. Scan-converting a polygon.
`
`We update only the ZZ-buffer entries correspond-
`ing to inside or boundary cells. For boundary
`cells, the object inserted into the ZZ-buffer is the
`polygon itself, with opaque = false. For interior
`cells, we store instead a pointer to a simplified ob-
`ject that consists only of the polygon’s supporting
`plane, without its edges. This substitution is made
`so that the rendering phase will not look at the
`polygon’s edges if it needs to test whether a sam-
`ple ray within this cell intersects the polygon. The
`opaque flag is true or false depending on whether
`the polygon is made of an opaque or transparent
`
`4
`
`material. The zmin and zmax along each scanline
`can be obtained incrementally by the Bresenham
`algorithm.
`If a polygon is large and also has many edges,
`it may be worth extending the optimization above
`even further, by remembering for each cell touched
`by the polygon the subset of edges intersecting
`the current scanline. These edges are all we need
`for testing whether a ray passing through the cell
`intersects the polygon.
`
`Quadric surfaces
`
`For quadric surfaces, such as ellipsoids, parabol-
`oids, cylinders, and cones, we do scan conversion
`as follows. First, we map the quadric to screen
`space, so that its equation has the form
`
`ax2+bxy+cxz+dy2+eyz+f z2+gx+hy+iz+j = 0,
`
`where x, y, and z are screen coordinates. Now con-
`sider a particular ZZ-buffer cell that corresponds
`to the region [x − ε, x + ε] × [y − ε, y + ε] of the
`screen plane. A ray from the viewpoint through
`this cell consists of the points (x + δx, y + δy, z)
`for all z. Substituting this expression into the for-
`mula above and collecting powers of z gives the
`quadratic equation Az2 + Bz + C = 0, where
`
`A = f
`B = cx + ey + i + cδx + eδy
`C = ax2 + bxy + dy2 + gx + hy + j
`+ (2ax + by + g)δx + (bx + 2dy + h)δy
`
`
`+ aδ2x + dδ2y.
`We then compute intervals ¯A, ¯B, and ¯C that are
`guaranteed to contain the possible values of A, B,
`and C for this particular cell:
`¯A = [f, f]
`¯B = cx + ey + i ± ε ∗ (|c| + |e|)
`¯C = ax2 + bxy + dy2 + gx + hy + j
`± ε ∗ (|2ax + by + g| + |bx + 2dy + h|)
`+ a ∗ [0, ε2] + b ∗ [0, ε2]
`In these equations, u± v denotes the interval [u−
`v, u + v], and the intervals are added as in interval
`arithmetic [21].
`The result is a “fuzzy” second-degree equation
`¯Az2 + ¯Bz + ¯C = 0 whose coefficients are inter-
`vals. We solve this equation using standard inter-
`val arithmetic methods, obtaining a pair of inter-
`vals [z0.lo, z0.hi] and [z1.lo, z1.hi] that are guar-
`anteed to contain the z-coordinates of the first and
`second intersections of any ray with the quadric
`surface within this cell. We then store into the
`ZZ-buffer either the first interval [z0.lo, z0.hi], or
`else the union of the two intervals, depending on
`whether the surface is opaque or transparent.
`
`

`

`3.2 Rendering
`
`Once all the objects intersecting a given scanline
`have been placed into the ZZ-buffer by the scan-
`conversion phase, the rendering phase takes over.
`We begin this phase by sorting the tile list in each
`cell of the ZZ-buffer in order of increasing zmin.
`(At this point, we can throw away any tile whose
`zmin is greater than the cell’s zmax.)
`Once the tile lists are sorted, we render each
`pixel, using either a single sampling ray or a bun-
`dle of S × S jittered sampling rays, depending
`on the complexity of the scene inside the pixel.
`We determine visibility by using first the z ranges
`and opaque flags stored in the tiles, and comput-
`ing exact z values only when this information is
`not enough. Finally, we perform shading only for
`those surfaces that are found to be visible.
`
`Top-level rendering routines
`
`the top-level routine
`In the rendering phase,
`RenderPixel is called once for each pixel; its task
`is to compute the pixel’s color based on the tile
`list of the cell covering the pixel. The routine first
`attempts to compute an overall shade for the en-
`tire pixel by going through the tile list from front
`to back and evalutating the shade of each tile at
`the pixel center. This process continues until an
`opaque tile is reached, or until the situation be-
`comes too complex to be rendered accurately with
`a single sample. In the latter case, the routine re-
`it shoots S × S
`sorts to jittered supersampling:
`rays within the pixel, for some constant S, and
`tests each ray against the remainder of the list.
`In the following pseudocode, (xc, yc) are the co-
`ordinates of the center of the pixel being rendered,
`and a Tint is a record t consisting of a color triple
`t.color = [r, g, b] and the opacity coefficients for
`each channel t.alpha = [αr, αg, αb] [23].
`
`procedure RenderPixel takes
`tilelist: pointer to TileList
`xc, yc: Coordinate
`begin
`(tint, tilelist) ← RenderArea(tilelist, xc, yc)
`if tilelist = nil then
`PutPixel(xc, yc, tint)
`else
`fgd ← tint;
`for i ← 1 to S do
`for j ← 1 to S do
`(xs, ys) ← Jitter(xc, yc, i, j )
`tint ← RenderPoint(tilelist, xs, ys, fgd)
`PutSample(xs, ys, tint)
`end for
`end for
`endif
`end procedure
`
`5
`
`The subroutine PutSample simply stores the given
`tint into an array of sampled tints, with every
`block of S×S elements in the array corresponding
`to a single pixel. The subroutine PutPixel repli-
`cates the given tint into all S × S sample positions
`covered by the pixel. The array of samples will
`ultimately be filtered to produce the final image,
`as described in Section 3.4.
`The function Jitter(xc, yc, i, j) considers the
`pixel centered at (xc, yc) to be an S × S array of
`subpixels, and it computes a uniformly distributed
`random point within subpixel [i, j].
`The subroutine RenderArea is the part of
`RenderPixel that takes care of tiles that can be
`rendered with a single sample per pixel. It repeat-
`edly extracts the nearest tile from the tile list, ren-
`ders it, and blends the resulting color and opacity
`with those of the previously rendered tiles. If the
`routine cannot determine which is the closest tile
`(because of overlapping z ranges), or if the closest
`tile is too complex to be rendered with a single
`sample, then the routine gives up, returning the
`tint that it has computed so far, along with the
`list of tiles that remain to be processed.
`The test to see whether the tile can be shaded
`with a single sample is handled by the method
`TooComplex, associated with the tile’s object.
`This method must return true if the object does
`not cover the pixel entirely, or if the object’s shade
`varies too much within the pixel—e.g., because the
`object is textured or contains a highlight within
`the pixel. In case of doubt, it is always safer to
`return true and force supersampling.
`
`procedure RenderArea takes
`tilelist: pointer to TileList
`xc, yc: Coordinate
`returns
`Tint
`tint:
`remainder: pointer to TileList
`begin
`tint.color ← [0, 0, 0]
`tint.alpha ← [0, 0, 0]
`l ← tilelist
`(cid:54)= nil
`while l
`and not Saturated(tint.alpha)
`and (l.rest = nil or l.zmax < l.rest.first.zmin)
`and not l.first.obj.TooComplex(xc, yc) do
`zc ← l.first.obj.ComputeZs(xc, yc);
`objtint ← ShadePoint(l.first.obj, xc, yc, zc)
`tint ← ComposeTints(tint, objtint)
`l ← l.rest
`end while
`return (tint, l)
`end procedure
`
`

`

`The ComposeTints function combines the colors
`and transparencies of a foreground object f and a
`background object b into a single tint t, according
`to the standard compositing formulas [23]:
`t.color .γ = f.color .γ + (1 − f.alpha.γ) ∗ b.color .γ
`t.alpha.γ = f.alpha.γ + (1 − f.alpha.γ) ∗ b.alpha.γ,
`where γ is either r, g, or b.
`Once RenderPixel decides to use jittered super-
`sampling, it calls the subroutine RenderPoint for
`each sample ray. Note that if the first few ob-
`jects in the ZZ-buffer tile list are transparent, they
`may have already been shaded by RenderArea be-
`fore RenderPoint is called. RenderPoint therefore
`takes as a parameter the color of the preceding lay-
`ers, along with the list of tiles not yet rendered,
`and the jittered sample position.
`The RenderPoint routine works by computing
`shades for the objects that intersect the ray at
`(xs, ys) in increasing z order until the alpha for the
`sample is saturated. RenderPoint calls NextHit to
`enumerate intersections in correct z order. Note
`that this task is not trivial, since the tiles are
`sorted in order of increasing zmin, which may not
`correspond to the order of the objects’ actual z co-
`ordinate at (xs, ys). Note also that each tile may
`represent more than a single intersection: for ex-
`ample, a tile for a transparent sphere represents
`two intersections, one for the front surface and one
`for the back.
`The RenderPoint routine makes calls to a rou-
`tine ShadePoint that returns the object’s shade
`at a sample point. The ShadePoint routine does
`not have to do any color averaging or antialias-
`ing itself, since (as observed by Cook, Porter, and
`Carpenter [7]) the stochastic sampling that is al-
`ready being performed by RenderPixel will avoid
`aliasing in the shading as well.
`
`procedure RenderPoint takes
`tilelist:
`pointer to TileList
`xs, ys:
`Coordinate
`foreground: Tint
`returns
`tint: Tint
`begin
`tint ← foreground
`hits ← nil
`tiles ← tilelist
`(obj, z, tiles) ← NextHit(tiles, hits, xs, ys)
`(cid:54)= nil
`while obj
`and not Saturated(tint.alpha) do
`objtint ← ShadePoint(obj, xs, ys, z )
`tint ← ComposeTints(tint, objtint)
`(obj, z ) ← NexHit(hitqueue)
`end while
`return tint
`end procedure
`
`Visibility Testing
`
`When testing for visibility, instead of computing
`all ray-object intersections and sorting them at the
`outset, we determine each subsequent intersection
`only as it is needed. In most cases, we will only
`need to compute the first intersection.
`It
`The NextHit routine implements this idea.
`scans the given tile list and tests each tile against
`the ray through (xs, ys) using the HitTest object
`method. Whenever NextHit finds a tile that inter-
`sects the ray, it calls upon the ComputeZs method
`to get the exact z values of the intersection points,
`and merges those intersections into the sorted list
`hits. This process continues until NextHit is sure
`it has located the nearest intersection in the list—
`that is, until the zmin of the next tile lies beyond
`the smallest z in hits. At this point, NextHit sus-
`pends its search, removes the first element of hits,
`and returns it as the next closest hit, along with
`the list of tiles not yet examined.
`type HitList = record
`obj:
`pointer to Object
`z:
`Coordinate
`rest: pointer to HitList
`end record
`
`procedure NextHit takes
`tilelist: pointer to Tilelist
`hits:
`pointer to HitList
`xs, ys: Coordinate
`returns
`Object
`obj:
`Coordinate
`z:
`tilelist: pointer to Tilelist
`begin
`zbest ← +∞
`if hits (cid:54)= nil then zbest ← hits.z endif
`while tiles (cid:54)= nil and zbest > tiles.first.zmin do
`tile ← tiles.first; tiles ← tiles.rest
`if tile.opaq or tile.obj.HitTest(xs, ys) then
`zlist ← tile.obj.ComputeZs(xs, ys)
`for each z in zlist do
`if z < zbest then zbest ← z endif
`InsertHits(tile.obj,z,hits)
`end for
`endif
`end while
`
`if hits = nil then
`return (nil, +∞)
`else
`obj ← hits.obj
`z ← hits.z
`hits ← hits.rest
`return (obj, z )
`endif
`end procedure
`
`6
`
`

`

`Shading
`
`Once we have determined a surface that is visi-
`ble along a sample ray, we compute its color and
`transparency at the point of intersection p by call-
`ing the routine ShadePoint. This routine calls the
`object method SurfaceProperties to determine the
`surface’s material and normal vector at the point
`p. Then, for each light source, ShadePoint calls
`a subroutine Illuminate to determine the amount
`of light reaching p from that source. It then com-
`putes the effect of the light on the surface, using
`the method GetColor associated with the surface’s
`material.
`
`procedure ShadePoint takes
`obj: pointer to ProjectedObject
`ps:
`ScreenCoordinates
`returns
`tint: Tint
`begin
`p ← Map(xs, ys, zs, camera.screen-to-world)
`(norm, material) ← obj.SurfaceProperties(p)
`viewdir ← Normalize(camera.viewpoint − p)
`tint.alpha ← material.GetAlpha(norm, viewdir)
`tint.color ← [0, 0, 0]
`for each source in source-list do
`(lightcolor, lightdir) ← Illuminate(source, p)
`objcolor ← material.GetColor
`(lightcolor, lightdir, norm, viewdir)
`tint.color ← tint.color + objcolor
`end for
`return tint
`end procedure
`
`Shadows
`
`The ZZ-buffer can also be used to compute shad-
`ows, in a manner similar to the “light buffer” of
`Haines and Greenberg [14]. We will first consider
`using the ZZ-buffer to cast shadows from a point
`source—i.e., casting shadows without penumbrae.
`We will then see how the algorithm can be en-
`hanced to compute accurate penumbrae in the fol-
`lowing section.
`To implement shadows, we modify the ZZ-buffer
`algorithm in two ways. During scan conversion,
`we create an additional ZZ-buffer for each light
`source, and we scan convert every object into each
`of these ZZ-buffers from the point of view of the
`corresponding light. This scan conversion is iden-
`tical to the ordinary scan conversion already de-
`scribed. The resolution of the light ZZ-buffers are
`independent of each other and of the resolution of
`the camera ZZ-buffer (and are often considerably
`smaller).
`During rendering, we determine visibility as
`usual, but when computing the illumination from
`each light source we use the light’s ZZ-buffer to
`
`detect any obscuring objects. To do this, we
`transform the visible surface point p that is be-
`ing shaded to the screen coordinate system cor-
`responding to the light’s point of view. We then
`extract the list of tiles from the corresponding cell
`of the light’s ZZ-buffer and check each tile’s object
`against the ray from the light source to the point p,
`using the object’s HitTest and ComputeZs meth-
`ods. If we find an opaque object that intersects the
`ray, then p is in shadow with respect to the light.
`If we find transparent objects, then the light is
`filtered by the objects’ transmission coefficients.
`In order to compute which objects are in front
`of the point being shaded, it is not necessary to
`sort the obscuring objects by their distance from
`the light, since their combined transmission coef-
`ficients are independent of this order. Instead, we
`can just go through the list of tiles, multiplying
`the transmission coefficients of every object that
`intersects the ray, until we find a tile whose zmin
`is greater than the z of the point being shaded.
`
`Penumbrae
`
`Penumbrae (soft shadow edges) are among the
`most important ingredients of realistic image syn-
`thesis, as illustrated by figure 4.
`
`Figure 4. A scene with real penumbrae.
`
`To produce penumbrae, we imagine that each light
`source is a disk of some fixed size, oriented paral-
`lel to the projection plane of its ZZ-buffer. See
`figure 5. The visibility computation is performed
`as before, but shadowing is done, as in distributed
`ray tracing [7], by casting a perturbed ray from
`a jittered point on this disk to the point being
`shaded. In screen coordinates, these rays will be
`lines of the form (xp + mxz, yp + myz, z, 1), where
`(xp, yp) is the point where the ray hits the screen
`plane, and mx, my are numbers that describe the
`deviation of the ray from the z-axis. See figure
`5. Note that in the light’s screen coordinates, the
`light source itself is a disk at infinity centered at
`
`7
`
`

`

`the point (0, 0, 1, 0), so(cid:113)m2
`
`x + m2y < tan θ, where
`
`θ is the angular radius of the disk. Note that this
`bound on mx and my is independent of the screen
`coordinates xp and yp.
`
`of the object sheared by the map (x, y, z) →
`(x − mxz, y − myz, z). Therefore, if the bound-
`ing box is of the form R × [zmin, zmax], we in-
`sert the object into every cell of the ZZ-buffer that
`(cid:48) obtained by dis-
`overlaps the enlarged rectangle R
`placing the edges of R outward by the distance
`(tan θ) max{|zmin|,|zmax|}.
`Note that we must set the opaque flag to false
`(cid:48). Although in this
`in every cell covered by R
`way we lose the ability to remove covered objects
`from the ZZ-buffer in the AddTile routine, the ZZ-
`buffer still provides an indexing capability, and its
`z ranges still optimize the visibility computation.
`The following code implements the Illuminate
`subroutine for shadows with penumbrae:
`
`procedure Illuminate takes
`source: LightSource
`pt:
`WorldCoordinates
`returns
`lightcolor: Color
`lightdir: Direction
`begin
`(xs, ys, zs) ← Map(pt, source.world-to-screen)
`(mx, my) ← LightJitter(source.size)
`lightpos ← (mx, my, 1, 0)
`lightpos ← Map(lightpos, source.screen-to-world)
`if source.at-infinity then
`distsq ← 1
`else
`distsq ← |lightpos − point|2
`endif
`lightdir ← Direction(lightpos − pt)
`(xp, yp) ← (xs − mx ∗ zs, ys − my ∗ zs)
`list ← source.zzbuffer[xp, yp]
`atten ← source.BeamIntensity(light.dir)/distsq
`lightcolor ← atten ∗ source.color
`while list (cid:54)= nil
`and not TooDark(lightcolor) do
`tile ← list.first; obj ← tile.obj
`if tile.zmin < zs − ε
`and (tile.opaque or obj.HitTest(xp, yp, mx, my))
`then
`zlist ← obj.ComputeZs(xp, yp, mx, my)
`in zlist do
`for each z
`< zs − ε then
`if z
`, yp + my ∗ z
`pt(cid:48) ← (xp + mx ∗ z
`)
`.z
`pt(cid:48) ← Map(pt(cid:48), source.screen-to-world)
`alpha ← obj.GetAlpha(pt(cid:48), lightdir)
`lightcolor ← lightcolor ∗ ((1, 1, 1) − alpha)
`endif
`end for
`endif
`end while
`end procedure
`
`(cid:48)s
`
`(cid:48)s
`
`(cid:48)s
`
`(cid:48)s
`
`(cid:48)s
`
`Note that this code requires slightly generalized
`versions of HitTest and ComputeZs that take a
`perturbed ray (with slope (mx, my)) instead of a
`
`8
`
`Figure 5. Ray tracing penumbrae.
`
`In order to find the objects that might be inter-
`sected by this perturbed ray, we have to mod-
`ify the scan conversion somewhat. We place into
`the ZZ-buffer list for each cell every object that
`is intersected by the double truncated “pyramid”
`shown in figure 6. This pyramid is the union of all
`perturbed rays that hit the ZZ-buffer cell.
`
`Figure 6. Scan converting for penumbrae.
`
`Ideally, we would like to determine exactly which
`pyramids intersect the primitive, compute tight
`bounds for the z ranges of such intersections, and
`determine which cells have their pyramids com-
`pletely blocked by the primitive (which would al-
`low us to set the corresponding opaque flags to
`true). Unfortunately, these computation are dif-
`ficult, except perhaps for very simple primitives
`such as planes or quadrics. A practical alternative
`is to scan convert an enlarged three-dimensional
`bounding box of the object in screen space. To
`compute the enlarged bounding box, note that
`a perturbed ray intersects an object if and only
`if the corresponding unperturbed ray (with the
`same screen intercept (xp, yp)) intersects a copy
`
`

`

`ray parallel to the screen z-axis. If penumbrae are
`not required, then source.size is 0, mx and my are
`0, xp = xs, yp = ys, and the code can be simplified
`considerably.
`
`3.3 Depth of field effects
`
`The same mechanism that we use to produce
`penumbrae can be used to create images that sim-
`ulate the effects of limited depth of field, as shown
`in figure 7. When rendering each sample point, we
`generate a random point on the camera’s “lens”
`(which is a disk on the camera plane centered at
`the nominal viewpoint) and fire a ray from this
`jittered viewpoint toward the sample point on the
`screen plane.
`In order to locate all objects that
`might intersect this perturbed ray, we must scan-
`convert objects into the camera’s ZZ-buffer by the
`same mechanism that we used for extended light
`sources.
`
`Figure 7. Limited depth of field.
`
`3.4 Filtering
`
`Recall that the output of the rendering phase is
`an array of samples, with S × S samples for each
`pixel of the final image. After each scanline of
`pixels is produced, we take the corresponding S
`rows of the sample array and compress them into
`a single row of pixel values, using standard con-
`volution filtering [20, 24].
`In this filtering, each
`sample contributes to a 3 × 3 square of pixels in
`the final image, with weights that depend on the
`distance between the unjittered sample position
`and the centers of those pixels.
`
`4 Comparison to other meth-
`ods
`
`We now compare the ZZ-buffer algorithm against
`several other rendering algorithms that resemble
`it in capability or speed.
`In particular, we will
`
`9
`
`consider the classical Z-buffer and A-buffer algo-
`rithms, and some variants of ray tracing.
`
`4.1 Capabilities
`
`The ZZ-buffer algorithm approaches the versatil-
`ity of distributed ray tracing in that it can ren-
`der a wide variety of objects and produce many
`of the same effects, such as shadows and penum-
`brae, depth of field, and transparent surfaces. The
`ZZ-buffer algorithm is also free of many of the ap-
`proximation errors that plague the Z-buffer and
`A-buffer algorithms, and that can result in alias-
`ing and other image artifacts; the images produced
`by the ZZ-buffer, in fact, are as good as those of
`distributed ray tracing.
`In the rest of this section, we will discuss these
`points in more detail.
`
`Antialiasing
`
`The stochastic supersampling that the ZZ-buffer
`employs replaces aliasing by noise of the correct
`average intensity. Although this noise is somewhat
`objectionable, it arises in cases where the Z-buffer
`or A-buffer would produce much more objection-
`able aliasing effects, such as jaggies or Moir´e pat-
`terns.
`The Z-buffer has t