Tracing Algorithms for 3D Graphics

Tracing Algorithms for 3D Graphics
An Introduction with Examples in C++

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Introduction

The Idea:
- Model light rays/photons/waves from the source(s), onto and off of objects in the scene/world, to the eye/camera
Requirements:
- Understanding of elecromagnetic waves
- Understanding of materials

Forward Tracing

The Idea:
- Model light as multiple rays with different energy levels/intensities for different colors/wavelengths
- Start from the source and end at the view plane
A Shortcoming:
- Many rays are not seen
- It's too computationally expensive to trace rays that don't contribute to the image

Backward Tracing

The Major Difference:
- Consider the rays that certainly contribute to the image by starting at the view plane and trace backwards to the light source(s)
Odd Terminology:
- The "first object" that could have emitted a given ray is first in the backwards sense

Kinds of Rays

Feeler Ray:
- A ray sent from the eye
Illumination Ray:
- A feeler ray that reaches a light
Shadow Ray:
- A feeler ray that does not reach a light

Different Approaches

Ray Tracing:
- A ray can give rise to multiple rays (e.g., reflected, transmitted) as it moves through the scene/world, each of which is traced
Path Tracing:
- Each trace involves a single path through the scene that is stochastic in nature (e.g., as a result of reflection/transmission probabilities); multiple rays are traced for each pixel

Different Computational Methods

Tracing (Event-Based):
- Calculates the intersection between the ray and the objects in the scene
Marching (Space-Based):
- The array is moved a small amount each step until it contacts an object in the scene

Aliasing and Antialiaing

An Observation:
- Pixels are large relative to light rays
An Implication:
- Pixels may have sharp distinctions between them (i.e., "jaggies" of aliasing) if one ray is used for each pixel
Antialiasing Methods:
- Supersampling - Use multiple rays per pixel (e.g., 9) and average the result
- Adaptive Supersampling - Start with a smaller number ofrays per pixel (e.g., 5) and subdivide further if the colors are different
- Stochastic Sampling - Randomly generate multiple rays for each pixel and average the result

Reducing the Number of Objects to Check

Bounding Volume Hierarchies:
- Selects volumes based on given objects
Spatial Subdivision:
- Selects objects based on given volumes

Parallelization

Trivial:
- Divide the view plane into subsets and use a different processor for each subset
Other Techniques:
- Vector processors (SIMD)
- "Custom" algorithms

Common Elements

A Ray class
An empty (for semantics only) Material interface
A Shape3D interface
An Intersection class
A CompositeShape (in the sense of the composite pattern) class
Some classes that implement the Shape3D interface
A Light class

The Ray Class

The Specification

cppexamples/graphics3d/Ray.h

The Ray Class (cont.)

The Implementation

cppexamples/graphics3d/Ray.cpp

The Shape3D Interface

cppexamples/graphics3d/Shape3D.h

The Intersection Class

The Specification

cppexamples/graphics3d/Intersection.h

The Intersection Class (cont.)

The Implementation

cppexamples/graphics3d/Intersection.cpp

The CompositeShape3D Class

The Specification

cppexamples/graphics3d/CompositeShape3D.h

The CompositeShape3D Class (cont.)

The Implementation

cppexamples/graphics3d/CompositeShape3D.cpp

The Light Class

The Specification

cppexamples/graphics3d/Light.h

The Light Class (cont.)

The Implementation

cppexamples/graphics3d/Light.cpp

There's Always More to Learn