PITS - A Practical List-Priority Algorithm for 3D-Polygons

PITS (Polygon Intersection Topological Sorting) is a list-priority algorithm for 3D-polygons developed by Arne Dür, Sylvia Leimgruber, Roswitha Elsner, Christian Mitterrutzner and Marion Maran. Compared to the Binary Space-Partitioning (BSP) Tree Algorithm of Fuchs, Kedem and Naylor, PITS cannot guarantee a correct order in all cases but usually succeeds with only a small number of additional polygons. To show the differences between BSP and PITS in output size and rendering order, we have generated the following PostScript images using our own implementation of PITS or C. Geuzaine's implementation of BSP, respectively. When viewing the images with Firefox and GhostView, BSP polygons appear scattered on the screen while PITS polygons are drawn locally (other browsers and plugins may cache the output).

More examples of PITS can be found in the Gallery of Famous Surfaces. The theory of PITS is described in the paper A Practical List-Priority Algorithm for 3D Polygons by A. Dür and Sylvia Leimgruber, Journal of Graphic Tools, Vol. 8, Nr. 4 (2003), 23-34.