AN IMPROVED RAY SHOOTING METHOD FOR CONSTRUCTIVE SOLID GEOMETRY MODELS VIA TREE CONTRACTION

In the Constructive Solid Geometry (CSG) representation a geometric ob ject is described as the hierarchical combination of a number of primi tive shapes using the operations union, intersection, subtraction, and exclusive-union. This hierarchical description defines an expression tree, T, called the CSG tree, with leaves associated with primitive sh apes, internal nodes associated with operations, and whose ''value'' i s the geometric object. Evaluation of CSG trees is an important comput ation that arises in many rendering and analysis problems for geometri c models, with ray shooting (also known as ''ray casting'') being one of the most important. Given any CSG tree T, which may be unbalanced, we show how to convert T into a functionally-equivalent binary tree, D , that is balanced. We demonstrate the utility of this conversion by s howing how it can be used to improve the worst-case running time for r ay shooting against a CSG model from O(n(2)) to O(n log n), which is o ptimal. In addition, the practicality of our method has been demonstra ted in experimental benchmarking tests using the BRL-CAD package.