© 1997 by British Computer Society
A New Algorithm for The Rendering of CSG Scenes
1 Dipartimento di Automatica e Informatica, Politecnico di Torino, corso Duca degli Abruzzi 24, 10129 Torino, Italy Email: sanna{at}polito.it, 2 Centro di Servizi Informatici e Telematici, Politecnico di Torino, corso Duca degli Abruzzi 24, 10129 Torino, Italy
The generation of 3-D solid objects, and more generally solid geometric modelling, is very important in Computer Aided Design (CAD). An important role is played by the Constructive Solid Geometry (CSG) representation scheme. IN CSG, objects are described by trees of Boolean operations on half-spaces or boundaries of primitive solids. The study of techniques to speed up the rendering of scenes modelled with the CSG scheme is an attractive field of research; in this paper we propose a new algorithm which reduces the computational complexity for ray casting approaches. Our strategy identifies a set of areas on the plane of view where the rays starting from the observer have to be traced; for each zone, only a portion of the entire CSG tree has to be considered for intersection tests, instead of the whole database of the primitive objects. A comparison of our algorithm with a ray caster that adopts bounding volume hierarchies and with a freeware ray tracer called POV-Ray shows that, for the examples considered, we may reduce the intersection tests to one third of those performed when standard optimizations are adopted.
Received February 19, 1997. revised November 12, 1997.