of performing front-to-back rendering from a BSP tree, rather than the traditional back-to-front approach. They utilized a special data structure to record, efficiently, parts of the screen that have been drawn, and those yet to be rendered. This algorithm, together with the description of BSP Trees in the standard computer graphics textbook of the day (Computer Graphics: Principles and Practice) was used by John Carmack in the making of Doom (video game). 1992 Teller's Ph.D. thesis described the efficient generation of potentially visible sets as a pre-processing step to accelerate real-time visible surface determination in arbitrary 3D polygonal environments. This was used in Quake and contributed significantly to that game's performance. 1993 Naylor answered the question of what characterizes a good BSP tree. He used expected case models (rather than worst-case analysis) to mathematically measure the expected cost of searching a tree and used this measure to build good BSP trees. Intuitively, the tree represents an object in a multi-resolution fashion (more exactly, as a tree of approximations). Parallels with Huffman codes and probabilistic binary search trees are drawn. 1993 Hayder Radha's Ph.D. thesis described (natural) image representation methods using BSP trees. This includes the development of an optimal BSP-tree construction framework for any arbitrary input image. This framework is based on a new image transform, known as the Least-Square-Error (LSE) Partitioning Line (LPE) transform. H. Radha's thesis also developed an optimal rate-distortion (RD) image compression framework and image manipulation approaches using BSP trees. See also k-d tree Octree Quadtree Hierarchical clustering, an alternative way to divide 3D model data for efficient rendering. Guillotine cutting References Additional references https://ui.adsabs.harvard.edu/abs/1996ITIP....5.1610R/abstract Describes a randomized Painter's Algorithm.. External links BSP trees presentation Another BSP trees presentation A Java applet that demonstrates the process of tree generation A Master Thesis about BSP generating BSP Trees: Theory and Implementation BSP in 3D space Binary trees Geometric data structures 3D computer graphics Articles with example C code