Paralelização de algoritmos sequenciais de ray-tracing utilizando técnicas de divisão e conquista

Abstract

Ray-tracing is an important technique to obtain photo-realistic images. The basic algorithm is well-known. Its applicability is restricted by the high demands on processing required to check collision between all rays and primitives of a scene. Therefore, acceleration methods are needed. Recently, solutions that do not use any data structure for spatial subdivision have been proposed. These solutions implicitly subdivide the scene by using divide-and-conquer techniques. Thus, this work presents a new parallel algorithm for ray-tracing based on the divide and conquer paradigm, which allows to run individual instances of sequential algorithms concurrently and then combine the results in order to get the final image. The algorithm introduces a parallel scheme that, without using any data structure for spatial division, maintains memory management minimum and deterministic. Initially, the scene is divided into sub-scenes and data uniformly distributed in the parallel hardware. After, an iterative three-step process is performed until the ray-tracing is completed. Results show that our solution speeds up a sequential state-of-the-art algorithm by about 2.42 times when running in a four-thread configuration.