DEPTH-SORTING METHOD

                                 Using both image-space and object-space operations, the depth-sorting method performs the subsequent basic functions:

1. Surfaces are sorted so as of decreasing depth.
2. Surfaces are scan converted so as, starting with the surface of greatest depth.

Sorting operations are administered in both image and object space, and also the scan conversion of the polygon surfaces is performed in image space. This method for solving the hidden-surface problem is usually cited because the painter's algorithm. In creating an oil painting, an artist first paints the background colors. Next, the foremost distant objects are added, then the nearer objects, so forth. At the ultimate step, the foreground objects are painted on the canvas over the background and other objects that are painted on the canvas.

Each layer of paint covers up the previous layer. employing a similar technique, we first sort surfaces in step with their distance from the view plane. The intensity values for the farthest surface are then entered into the refresh buffer. Taking each succeeding surface successively (in decreasing depth order); we "paint" the surface intensities onto the buffer storage over the intensities of the previously processed surfaces.

Painting polygon surfaces onto the buffer storage in step with depth is administered in several steps. Assuming we are viewing along the-z direction, surfaces are ordered on the primary pass in step with the tiniest z value on each surface. Surface 5 with the best depth is then compared to the opposite surfaces within the list to see whether there are any overlaps thorough. If no depth overlaps occur, 5 is scan converted. This process is then repeated for the following surface within the list. As long as no overlaps occur, each surface is processed thorough order until all are scan converted. If a depth overlap is detected at any point within the list, we'd like to form some additional comparisons to see whether any of the surfaces should be reordered. We make the subsequent tests for every surface that overlaps with 5. If anyone of those tests is true, no reordering is critical for that surface. The tests are listed so as of accelerating difficulty

1. The bounding rectangles within the xy plane for the 2 surfaces don't over- lap
2. Surface 5 is totally behind the overlapping surface relative to the viewing position.
3. The overlapping surface is totally ahead of 5 relative to the viewing position.
4. The projections of the 2 surfaces onto the view plane don't overlap.

We perform these tests within the order listed and proceed to the following overlapping surface as soon as we discover one in every of the tests is true. If all the overlapping surfaces pass a minimum of one in every of these tests, none of them is behind 5. No reordering is then necessary and S is scan converted.

Test 1 is performed in two parts. We first check for overlap within the x direction, so we check for overlap within the y direction. If either of those directions shows no overlap, the 2 planes cannot obscure one other. An example of two surfaces that overlap within the z direction but not within the x direction

We can perform tests 2 and three with an "inside-outside" polygon test. That is, we substitute the coordinates for all vertices of S into the plane equation for the overlapping surface and check the sign of the result. If the plane equations are founded in order that the skin of the surface is toward the viewing position, then S is be- hind S' if all vertices of S are "inside" S'. Similarly, S' is totally ahead of S if all vertices of S are "outside" of S'.

If tests 1 through 3 have all failed, we try test 4 by checking for intersections between the bounding edges of the 2 surfaces using line equations within the xy plane. As demonstrated in picture, two surfaces may or might not intersect although their coordinate extents overlap within the x, y, and z directions.

Should all four tests fail with a specific overlapping surface S', we inter- change surfaces S and S' within the sorted lit. An example of two surfaces that might be reordered with this procedure is given in picture. At this time, we still don't know sure that we've found the farthest surface from the view plane. But since S" obscures a part of S', we'd like to interchange s'' and S' to urge the three surfaces into the proper depth order. Therefore, we'd like to repeat the testing process for every surface that's reordered within the list.

It is possible for the algorithm just outlined to urge into an infinite loop if two or more surfaces alternately obscure one another. In such situations, the algorithm would regularly reshuffle the positions of the overlapping surfaces. To avoid such loops, we will flag any surface that has been ordered to a farther depth position in order that it can not be moved again. If a trial is created to modify the surface a second time, we divide it into two parts to eliminate the cyclic overlap. the first surface is then replaced by the 2 new surfaces, and that we continue processing as before.