A FAST PARALLEL TREE CONTRACTION FOR THE RAY- OBJECT CALCULUS USING OPEN-MP

Abstract

Ray tracing is a well known algorithm in the visualization area for its image quality and its simplicity. Unfortunately, it is computationally expensive. The basic operation of ray tracing is the calculus of the intersection points between rays and objects. This operation represents a large part of this algorithm. The goal of this work is mainly the proposition of an optimal parallel algorithm performing a ray-CSG intersection in O(log n log log n) time complexity and O(n) processors on a PRAM CREW model. It is based on the Contract tree algorithms developed in [1, 8] . Finally, the parallel tree contraction algorithm is implemented on a parallel machine.