COMP 236 Reading Assignment 2

Read "A Characterization of Ten Hidden-Surface Algorithms" by Sutherland, Sproull, and Shumacker. Choose one object-space method and one image-space method from the ten. Write a paper, in the form of a web page, describing how your chosen methods work. Compare and contrast your two methods with each other and with the Z-buffer (their "brute force") algorithm.

A Comparison between the Newell, Watkins and Z-buffer Algorithms

In their paper, Sutherland, Sproull and Schumacker present a classification of ten hidden‑surface algorithms. Their criterion is the space in which the solution is computed: object space vs. image space. From the algorithms presented, I chose a list‑priority algorithm and an image‑space algorithm because these are the domains in which I think further developments are more likely. Object‑space algorithms have a quadratic running time with respect to the environment complexity, so they are computationally intensive. While today’s widely‑implemented Z-buffer algorithm can also be considered computationally intensive, the elementary operations are simple enough to implement cheaply in hardware.

The Newell Hidden-Surface Algorithm

The first algorithm I chose is called a “list‑priority” algorithm because it precomputes a visibility order (called “priority”) in object‑space, then generates the picture in image‑space. This way, the algorithm takes advantage of some features of each space: priority computations are done with arbitrarily high precision in object space, yet the fact that the results are displayed on a finite‑resolution device also has a considerable impact.

As stated in the paper, the principal contributions brought about by the Newell algorithm are the “priority computer” and the concept of “overwriting” values to achieve transparency. The priority computer sorts an arbitrary collection of faces into a priority order. Transparency is achieved by allowing transparent faces that overlap other faces to overwrite their intensity values in a special way, by linear blending, if the face behind the transparent one has a higher intensity.

The algorithm consists of the following steps:

1) sort in Z: sort all the faces by depth of the furthest vertex of each face

If the faces do not overlap in Z, this sort establishes the correct priority order.

Figure 1 shows a projection of the environment on the XZ plane, so faces become lines. Sorting them in increasing Z order correctly assigns the priorities in the order F1, F2, F3.

Figure 1: Sorting in Z in the Newell algorithm.

2) Newell special sort: check if the Z-order list from step 1 is in priority order, and revise if necessary

Let us consider the case in Figure 2. P is the face with the furthest vertex in Z‑order, so it is the last in the list produced in the previous step. Q is the next‑to‑last face in the same list.

If the closest vertex of P is deeper than the furthest vertex of Q, P can be safely written to the video buffer, as it does not obscure any other face. If not, we need to perform another kind of test to determine whether P obscures Q and all other faces with the furthest vertex closer than the closest vertex of P. If P obscures some face Q’ in this set, swap P and Q’ and repeat.

Figure 2: The Newell special sort.

To avoid infinite loops, swapped faces are marked. If a pair of unorderable faces exist, one of them must be divided into two faces to break the “cyclic overlap”, as shown in Figure 3.

Figure 3: Breaking a cyclic overlap.

There are several tests that can be performed to check whether faces P and Q overlap. The algorithm needs to perform them in increasing order of their difficulty, until a test can decide if the two faces overlap. The tests are:

- do P and Q overlap in Z? – tested implicitly by selecting Q from the Z‑ordered list

- do the extreme X coordinates overlap? – minimax test in X

- do the extreme Y coordinates overlap? – minimax test in Y

- are all vertices of P further than the plane of Q?

- are all vertices of Q closer than the plane of P?

- do P and Q overlap on the screen?

Using these tests, a priority ordering can be decided for any environment, if appropriate breaking of cyclic overlaps are also performed.

On a final note, picture elements are not stored like in a video buffer, one for each pixel. Instead, the Newell algorithm uses “beads”, which are visible segments grouped in a “bucket” for each scan-line. This allows easy merging of new segments and overwriting values to achieve transparency.

The Watkins Hidden-Surface Algorithm

The second algorithm I chose is called an “image‑space” algorithm because it computes the answer to the hidden‑surface problem in image‑space, in a form and order suitable for a raster display. It is also called a “point‑sampling” algorithm because it samples the environment with rays that pass through infinitesimal points on the screen.

The algorithm computes the intersections of the plane of a scan-line with all the faces in the environment, resulting in segments whose coherence properties are exploited between scan-lines. Although this simplifies the hidden‑surface problem by reducing it to a two‑dimensional problem, the computed intensity of a raster element is not an average of all the contributing intensities, but a single sample point.

This results in effects like:

- objects “disappearing” between the lines, because no sample points fall within them;

- incorrect intensities at the edges of large objects because the intensity at sample points is different from the average.

These effects can be ameliorated by oversampling (in this case, situations where objects disappear can still be constructed) or random sampling (at the price of having straight edges look “fuzzy”).

The intersections of the scan-line plane with the faces in the environment define “segments”, and the scan-line is divided into “spans” within which only one segment (the closest) is visible.

As stated in the paper, the principal contributions brought about by the Watkins algorithm are the aggressive span generation and the logarithmic Z‑search. Spans are dynamic, having their left edge fixed and their right edge moved to the left as necessary when new segments are extracted from the previous list. In the logarithmic Z‑search, segments are split until the visibility can be computed with simple minimax tests, as shown in Figure 4.

Figure 4: The Watkins logarithmic Z-search.

Here, splitting segment A in half is enough to decide that segment B is invisible.

Although this approach can ultimately lead to computing the depth of segment A at the endpoints of segment B by a large number of splits, the process usually ends much sooner.

The algorithm consists of the following steps:

1) sort in Y: limit the attention of the algorithm to the current scan-line.

This is an insertion sort: new segments are inserted in their proper place, and segments that terminate are deleted. By this incremental approach, the algorithm takes advantage of one type scan-line coherence: segments that intersect a scan-line are likely to intersect the next.

2) sort in X: examine the previous list to decide which faces are visible in which portion of the scan-line, by dividing it into spans.

3) span cull: cull out the segments within each span to determine which fall inside the span

4) Z depth search: search the segments in each span to find which one is visible.

On a final note, a hardware implementation of the Watkins algorithm was available at the time from Evans and Sutherland Computer Corporation.

The Z-buffer (“Brute Force”) Hidden-Surface Algorithm

The Z-buffer algorithm is also an “image‑space” and “point‑sampling” algorithm, so it suffers from the same drawbacks. It was developed by Catmull, and is very simple to implement. It requires, beside a frame buffer (where color values are kept), a Z-buffer (hence the name) of the same size, where a depth value is kept for each pixel.

The algorithm consists of the following steps:

0) clear the Z‑buffer.

1) “sort” in Y: limit the attention of the algorithm to the current scan-line.

2) “sort” in X: allow access the current pixel.

3) scan convert each face and “sort” in Z: for each pixel in the face’s projection, if the Z‑depth is greater than the Z‑value stored in the buffer, replace the color in the frame buffer with the face’s color at that point.

On a final note, both “sorts” in X and Y are radix sorts, so they require no comparisons. They are listed here only for comparison, since they are reduced to accessing memory locations. The “sort” in Z requires only one comparison, since it only keeps the maximum value.

Hidden-Surface Algorithm Comparison and Contrast

As shown in the paper, the computing cost for the first two algorithms is roughly the same for anisotropic environments, because they perform complex face-to-face computations only for the very few faces that overlap in all three dimensions:

- the first step in the Newell algorithm, in which faces are considered only if they overlap the depth of a test face, is just as effective as the first step in the Watkins algorithm, where faces are considered only if their vertical extent overlaps the current scan-line;

- the Newell algorithm follows the Z-depth overlap test with tests in X and Y, while the Watkins algorithm follows the Y test with overlap tests in X and Z.

In contrast, the Z-buffer algorithm needs to perform no face-to-face comparisons, the entire process being just a search over pairs {color, Z‑value}(X,Y) for fixed X and Y to find the largest Z‑value.

The first two algorithms take advantage of coherence (depth coherence in the Newell algorithm and scan-line coherence in the Warnock algorithm), while the Z‑buffer algorithm uses the brute‑force approach.

Since they are image‑space algorithms, the Watkins and Z‑buffer algorithms suffer from edge effects, while the Newell algorithm does not.