Space Division for Ray Tracing in CSG

A system of Constructive Solid Geometry (CSG) enables an engineering designer to compose threedimensional shapes by combining simpler ones. Definitions of such objects are represented by tree structures or directed acyclic graphs. Most existing systems convert this representation to a more conventional boundary representation of the solids in order to render pictures from the model. More recently, a number of systems have been described that render the pictures directly from the CSG structure. We describe such a system. We render a scene by ray tracing from a directed acyclic graph. This process is made efficient for large models by using an adaptive method of space division to reduce the number of intersection calculations needed.