()

Lecture 22: Ray Tracing

This lecture was given by guest lectuere, Bill Mark (http://www-csl.csres.utexas.edu/users/billmark/). Basic ray-tracing concept and algorithms implementing it were introduced. Several optimizations to reduce computational complexity and enhance data locality were discussed. Major performance bottleneck that currently prevent real-time ray-tracing being used and current research focus addressing them were also presented. Finally, current application of ray-tracing and the lecturer’s point of view about programming explicitly managed memory system were discussed.

Introduction

Rendering

source

Rendering is a process that generates a 2D image from a 3D scene description. Ray-tracing is one of the rendering techniques that simulates the movement of light rays from light sources to an eye. To compute light intensity of a pixel, rays that falls onto the pixel and the eye are traced along the scene. This comprises of the following 3 subproblems.

Visibility

This is about finding out what is the first object the eye see in one direction: what is the first object in the scene that blocks the line that is defined by the eye and a pixel. This is primarily what a ray-tracing is about. Z-buffer does this job in a rasterization hardware.

Light transport

Not all lights comes from eminent light sources such as the sun and bulb. Although an area that is in shadow and not directly visible from light sources, it is not completely dark. This is because of the lights bounced off from surroundings, and called indirect lighting. Modeling indirect light is critical to produce realistic images. Without indirect light modeling, the image looks like a cartoon! Computing this indirect lighting is very compute intensive, so static scenes are often precomputed offline.

Material properties

Some objects are mirror-like and some are plain matte. Material properties determine how lights are reflected.

source

Among the three components, visibility is the primary bottleneck that makes ray-tracing expensive. All rays randomly access the geometry, therefore there is little locality. The key challenge is how to manage and exploit such locality in geometry.

Algorithms and optimizations

Tracing direction

Usually, ray is traced in the reverse direction (from an eye to the light sources) to the actual photons move (from light sources to an eye). This is because we do not care about the lights that does not beam into our eyes and contribute to the image we see. This reduces the amount of computation we do.

However, there are some hybrid algorithms which trace rays in both directions. It trace rays emitting from light sources and stores relevant data for the object those rays hit. When rays emitting from the eye are traced and hit such objects, the stored data is retrieved and used to calculate the light intensity.

Base algorithm

R = the set of rays need to be traced T = the set of triangles in the geometry 

for each ray r in R {
  for each triangle t in T {
    check if r intersects with t
  }
}

The computational complexity is simply |R| {$ \times $} |T|

Usually |R| amounts to 1 million (for 1024×1024 image) and |T| amounts to 1 million (for rather complex scene). To render a moving image, we need

|R| rays {$ \times $} |T| triangles {$ \times $} 60 frames / sec = 60 trillion triangle-ray intersection test / sec

This is obviously too much computation for current or near-future hardware and there are optimizations to reduce the complexity.

Acceleration structure

Intuitively, perform intersection test against all triangles for all rays in brute force manner is not smart. We can sort the triangles and selectively perform intersection test. This ‘ ’sorted” data structure is called an acceleration structure in graphics terminology and usually sorted in all 3 dimensions. There are number of different sorting scheme each has pros/cons. Several studies concluded there is no single best acceleration structure for all types of scenes.

Grid

source

Grid is not ideal acceleration structure, but traversal algorithm for uniform grid is simple.

Kd-tree

Kd-tree is the most popular acceleration structure for CPU raytracers.

With a good choice of acceleration structure, the number of test approximately reduces to log|T|. However, for animated scene, we need to sort the data structure every time it changes. The total cost is

|R| {$ \times $} log|T| + |T|log|T|

which is still better than the brute force algorithm above. In reality, because the very last image is almost sorted already, sorting is usually very cheap in terms of computation.

However, because we need to modify data structure, now it is no more read-only. This becomes a critical matter in parallel system, where synchronization is a big deal.

Ray packet

Instead of randomly pick rays to trace, trace rays originated from adjacent pixels will end up exploiting more locality, because those are likely to traverse the same part of the geometry. Using SIMD instructions such as SSE, multiple rays are traced in parallel and the unit of rays traced together is called a ray packet. When ray diverges (= traverse different acceleration structure nodes), then both path are traversed and each ray is predicated accordingly. This leads to more coherent memory access pattern.

Secondary rays

So far, most discussion was about eye rays. Tracing eye rays is not that interesting because it does what what z-buffer can do as well. The true advantage of ray-tracing is in it’s natural ability to model indirect lighting by tracing secondary rays. The following is what makes tracing secondary rays hard:

  • Secondary rays are determined by what the primary rays hit. Therefore, they are dependent on the tracing of primary rays.
  • Secondary rays are not as coherent as primary rays. Even two coherent rays can generate secondary rays that are incoherent to each other. Fortunately, in reality direction of secondary rays are not that random due to the coherence of physical material.
  • We can group coherent secondary rays together, but then it adds additional complexity of storing rays on memory, which requires a lot of space.

Improvement

  • It is believed that the optimal point lies between sorting geometries and sorting(=grouping) rays.
  • Beam (about 100s of rays) tracing is useful technique because it allows more compact representation of many rays.
  • Changing the approximation
  • Reorder/refactor algorithm
  • Low-level algorithm optimization
  • Parallel hardware, cache, ILP, ISP(?)

Applications

Mostly off-line raytracing currently, but it is projected that in 4–5 years, interactive raytracing will be used in real-time applications.

  • Movie (Pixxar, etc)
  • Compositing (Michael Jordan jumping from the roof of a building)
  • Automobile pre-prototype

The following movies are generated from IBM Cell iRT raytracers; source http://www.gametomorrow.com/minor/barry/iRT_shaders_560p.mov http://www.gametomorrow.com/minor/barry/lambo_loop_576p.mov

  • Medical imaging
  • Architecture - building model

Other topics discussed

  • Reuse of previous image generated
When only viewpoint is moved, new image can be transformed from previous frame. In applications like 3D games, for objects that are guaranteed not to move, image is preprocessed for those objects in high detail and reused many times.
  • Explicit-DMA machines
From software engineer’s point of view, not having coherent cache, and setting up explicit DMA transfer manually is extremely frustrating. He thinks programmers should not be neglected.