A Practical List-Priority Algorithm for 3D Polygons
Arne Dür, Sylvia Leimgruber · Journal of Graphics Tools · 2003
To determine a correct order for rendering three-dimensional polygons, the commonly used Binary Space-Partitioning (BSP) tree algorithm recursively splits polygons whenever points of the polygons lie on both sides of the spanning plane which, for large scenes, significantly increases the number of polygons. To keep the number of new polygons small, we present an alternative algorithm that splits only penetrating polygons and applies a topological sort to the resulting polygons with respect to the covering relation. Although the existence of a correct order cannot be guaranteed in general, the new algorithm has proved to be successful for many polygonal approximations of famous surfaces from geometry where it has been used to produce quality PostScript output from OpenGL.