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.
[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.