Ray tracing CSG trees using the Sticks representation scheme

A fast ray tracing algorithm of CSG tree is presented. The algorithm uses an adaptative space subdivisions approach, based on the conversion of the objects or the scene into the volumetric Sticks representation scheme. This conversion scheme, which requires O(kn?2) memory space to represent data in a n?2 grid, makes it possible either to obtain very fast low-quality frontal orthographic projections, or to produce a high-quality rendering or the scene in time less than that needed by classical ray tracing and nearly independent of the number of objects in the scene. Furthermore, the characteristics of the Sticks scheme can be exploited to compute geometric or topological properties of the represented objects. Comparative analyses between the Sticks representation scheme and c1assical space subdivision schemes and between our Sticks-based ray tracing and classical algorithms are presented.