Previous: Clipping, Up: Caveats

#### 4.4.3 Hidden surface removal and polygon splitting

`Sketch` uses the depth sort algorithm for hidden surface removal. This is a very old technique due to Newell.1 It is generally regarded as too slow for real time graphics, but it is ideal for our purpose where speed is not very important.2

The depth sort algorithm merely sorts objects on a key of increasing z-coordinate, equivalent to decreasing depth. Objects are then drawn in the sorted sequence so that those at the rear of the scene are overwritten by those closer to the viewer. Since this is also how oil painters practice their art, depth sort is sometimes called “the painter's algorithm.”

In some cases it is impossible to strictly order polygons according to depth. Moreover, even if a correct depth ordering exists, the computation needed to find it may be too complex and slow. In these cases, `sketch` splits one or more polygons into pieces. The expectation is that the new, smaller polygons will be simpler to order. `Sketch` uses a BSP (binary space partition) to handle the splitting operation.

#### Footnotes

[1] Newell, M.E., R.G. Newell, and T.L. Sancha, A solution to the hidden surface problem. Proceedings of the ACM annual conference - Volume 1, page 443–450, ACM Press, 1972.

[2] We have run `sketch` on the famous Stanford Bunny, which consists of nearly 70,000 triangles. Run time was about 6 seconds. Most of this was spent writing the output file rather than in the hidden surface algorithm. LaTeX took much longer to process the resulting `PSTricks` code. The obvious conclusion is that the speed of the depth sort algorithm is not a worry.