Pseudo Ordering of CSG-Trees

Abstract

Using Constructive Solid Geometry (CSG) methods, it is usual for primitive object representations to be stored at the leaf nodes of binary trees. The major part of the work involved in generating an image of the object is finding what surface is visible at each pixel in the screen. Using conventional rendering methods this can be simplified by ordering the primitives by their screen positions and by their depths. Using ray tracing techniques this can be achieved by testing if rays intersect with primitives, the number of these intersection tests can be reduced by ordering. However it is not generally possible to order data (in any one direction) in CSG-trees where intersection or difference operators are involved. This paper describes a method that enables 'local' three-way ordering of the data contained in CSG-trees that can be used with either conventional scan-line rendering methods or ray tracing techniques. This is achieved by the introduction of underlying data structures that dynamically change throughout the image generation step. Using this method, the primitive/polygon visible at a particular pixel can usually be accessed directly via pointers.