- Forward


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


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Introduction
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • Bounding Volume Hierarchies:
    • Selects volumes based on given objects
  • Spatial Subdivision:
    • Selects objects based on given volumes
Parallelization
Back SMYC Forward
  • Trivial:
    • Divide the view plane into subsets and use a different processor for each subset
  • Other Techniques:
    • Vector processors (SIMD)
    • "Custom" algorithms
Common Elements
Back SMYC Forward
  • 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
Back SMYC Forward

The Specification

cppexamples/graphics3d/Ray.h
 
The Ray Class (cont.)
Back SMYC Forward

The Implementation

cppexamples/graphics3d/Ray.cpp
 
The Shape3D Interface
Back SMYC Forward
cppexamples/graphics3d/Shape3D.h
 
The Intersection Class
Back SMYC Forward

The Specification

cppexamples/graphics3d/Intersection.h
 
The Intersection Class (cont.)
Back SMYC Forward

The Implementation

cppexamples/graphics3d/Intersection.cpp
 
The CompositeShape3D Class
Back SMYC Forward

The Specification

cppexamples/graphics3d/CompositeShape3D.h
 
The CompositeShape3D Class (cont.)
Back SMYC Forward

The Implementation

cppexamples/graphics3d/CompositeShape3D.cpp
 
The Light Class
Back SMYC Forward

The Specification

cppexamples/graphics3d/Light.h
 
The Light Class (cont.)
Back SMYC Forward

The Implementation

cppexamples/graphics3d/Light.cpp
 
There's Always More to Learn
Back -