Ray Tracing Acceleration Techniques

Introduction. Today, ray-tracing techniques (RTT) are being used successfully in many computer applications. The most common applications are static and dynamic scene visualizations, movies, commercials, and video games, wherein near perfect realism can be achieved. Virtual reality is also an important field for the application of RTT, not only for recreational purposes, but also for scientific and engineering research.

Another field in which RTT play a crucial role is in the study of acoustic and electromagnetic wave propagation in complex scenarios. The deployment of modern radio communication networks, particularly for communication or surveillance wireless systems, requires high-quality RTT that are well fitted to the particular needs of this field.

The aforementioned RTT applications (including many others that are not cited or that will be developed in the future) have a common need for computational efficiency in the vein of central processing unit time and memory usage. Often, very complex scenarios are visualized or analyzed in ‘‘real time’’ for many observation points or illumination sources.

This article is devoted to presenting a tutorial view of modern RTT. Although all the aforementioned techniques share the common need for computational efficiency, the geometry and morphology of scenarios, the nature of the lightsources, and the phenomenology of wave transmission and scattering can differ drastically. Each application requires a partially or completely specialized RTT.

In the next section, we consider the different kinds of geometries, morphologies, and qualities of illumination found in ray-tracing problems. Then, we introduce raytracing mechanisms to elucidate the different tasks involved in successfully applying RTT.

The problems and corresponding complexity of these tasks in typical scenarios are covered in the section on problems and complexity of RTT, wherein the two main subproblems associated with RTT are discussed: flash-points searching, that is, searching for reflection, diffraction, and transmission points, and ray shooting query, which consists of determining whether a given segment is cut by any entity of the scene.

The two main strategies for addressing the first subproblem are discussed in the sections on RTT strategies for the flash-point searching (FPS): the shooting and bouncing of rays and the solution of the inverse problem. Several efficient techniques for solving a ray shooting query are outlined in the section on Algorithms to reduce the computationalcost.

The section on the angular Z-Buffer algorithm introduces the angular zeta buffer algorithm as a solution to the inverse problem strategy and also as a tool for flash-point searching. Finally, the last section compares the techniques presented in the previous two sections.