Title

Efficient Parallel Evaluation Of Csg Tree Using Fixed Number Of Processors

Abstract

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.

Publication Date

1-1-1993

Number of Pages

137-146

Document Type

Article; Proceedings Paper

Identifier

scopus

Personal Identifier

scopus

DOI Link

https://doi.org/10.1145/164360.164409

Socpus ID

0027882645 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0027882645

This document is currently not available here.

Share

COinS