Efficient Parallel Evaluation Of Csg Tree Using Fixed Number Of Processors

Evaluation of CSG tree in a CSG based solid modeler is a very computationally intensive operation. In this paper we explore avenues for evaluating CSG trees by using multiple processors with shared memory. We propose a new parallel tree contraction algorithm, and apply the algorithm for parallel evaluation of CSG trees. Our algorithm is optimal as long as the number of processors p, is smaller than O(n/log n), where n is the number of leaf nodes in the CSG tree. We compare the performance of our algorithm with existing optimal tree contraction algorithms by implementing a ray casting of polygon problem in a BBN butterfly GP1000 shared memory MIMD machine equipped with 2 clusters of 32 processors each. We have formulated the ray casting problem with seven different structures of the CSG tree. We have obtained uniformly better performance results for varying structures of the CSG trees