COMPUTING AND INFORMATICS, Vol 20, No 1 (2001)

Font Size:  Small  Medium  Large

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

Zineb Habbas, Francine Herrmann, Michaël Krajecki

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.