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


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu


Introduction
Forward Tracing
Backward Tracing
Kinds of Rays
Different Approaches
Different Computational Methods
Aliasing and Antialiaing
Reducing the Number of Objects to Check
Parallelization
Common Elements
The Ray Class

The Specification

cppexamples/graphics3d/Ray.h
        #ifndef edu_jmu_cs_Ray_h
#define edu_jmu_cs_Ray_h
#include <glm/glm.hpp>

/**
 * An encapsulation of a Ray.
 *
 * @author Prof. David Bernstein, James Madison University
 */
class Ray {
 public:
  glm::vec3 o;
  glm::vec3 d;

  /**
   * Default Constructor.
   */
  Ray();

  /**
   * Explicit Value Constructor.
   *
   * @param origin     The origin
   * @param direction  The direction
   */
  Ray(const glm::vec3& origin, const glm::vec3& direction);

  /**
   * Get the pointAt t along the direction from the origin.
   *
   * @return  The point
   */
  glm::vec3 pointAt(float t) const;
};

#endif


        
The Ray Class (cont.)

The Implementation

cppexamples/graphics3d/Ray.cpp
        #include "Ray.h"

Ray::Ray() {
}

Ray::Ray(const glm::vec3& origin, const glm::vec3& destination) {
  o = origin;
  d = destination;
}

glm::vec3 Ray::pointAt(float t) const {
  return o + t*d;
}


        
The Shape3D Interface
cppexamples/graphics3d/Shape3D.h
        #ifndef edu_jmu_cs_Shape3D_h
#define edu_jmu_cs_Shape3D_h

#include "Ray.h"
#include "Intersection.h"

/**
 * The requirements of Shape3D objects.
 *
 * @author Prof. David Bernstein, James Madison University
 */
class Shape3D  {
 public:
  /**
   * Find the intersection (if any) of the given Ray with this Shape3D
   * (within given bounds).
   *
   * @param r            The Ray
   * @param tMin         The lower bound of the parameter
   * @param tMax         The upper bound of the parameter
   * @param intersection The (outbound) point of intersection
   * @return             true if there is an intersection; false otherwise
   */
  virtual bool intersectsWith(const Ray& r,
                              float tMin, float tMax,
                              Intersection* intersection) const = 0;
};

#endif




        
The Intersection Class

The Specification

cppexamples/graphics3d/Intersection.h
        #ifndef edu_jmu_cs_Intersection_h
#define edu_jmu_cs_Intersection_h

#include "Material.h"
#include "Shape3D.h"
#include <glm/glm.hpp>

class Shape3D;

/**
 * An encapsulation of the intersection between a Ray and
 * a Shape3D.
 *
 * @author Prof. David Bernstein, James Madison Univesity
 */
class Intersection {
 public:
  const Shape3D*   shape;
  float      t;
  glm::vec3  p;
  glm::vec3  n;
  const Material*  material;

  /**
   * Default Constructor.
   */
  Intersection();

  /**
   * Explicit Value Constructor.
   *
   * @param s      The Shape3D
   * @param t      The portion of the Intersection on the Ray
   * @param point  The point on the Shape3D
   * @param normal The normal at the point
   * @param m      The Material of the Shape3D
   */
  Intersection(const Shape3D* s, float tOnRay, const glm::vec3& point,
               const glm::vec3& normal, const Material* m);
};

#endif
        
The Intersection Class (cont.)

The Implementation

cppexamples/graphics3d/Intersection.cpp
        #include "Intersection.h"

Intersection::Intersection() {
}

Intersection::Intersection(const Shape3D* s, float tOnRay,
                           const glm::vec3& point, const glm::vec3& normal,
                           const Material* m):
    shape(s), t(tOnRay), p(point), n(normal), material(m) {
}
        
The CompositeShape3D Class

The Specification

cppexamples/graphics3d/CompositeShape3D.h
        #ifndef edu_jmu_cs_CompositeShape3D_h
#define edu_jmu_cs_CompositeShape3D_h

#include "Intersection.h"
#include "Ray.h"
#include "Shape3D.h"

/**
 * A Shape3D that contains other Shape3D objects (in the
 * sense of the composite pattern.
 *
 * @author Prof. David Bernstein, James Madison University
 */
class CompositeShape3D: public Shape3D  {
 private:
  Shape3D **shapes;
  int     length;

 public:
  /**
   * Default Constuctor.
   */
  CompositeShape3D();

  /**
   * Explicit Value Constructor.
   *
   * @param s   The array of Shape3D objects
   * @param n   The number of Shape3D objects
   */
  CompositeShape3D(Shape3D** s, int n);

  virtual bool intersectsWith(const Ray& r,
                              float tMin, float tMax,
                              Intersection* intersection) const;
};

#endif

        
The CompositeShape3D Class (cont.)

The Implementation

cppexamples/graphics3d/CompositeShape3D.cpp
        #include "CompositeShape3D.h"

CompositeShape3D::CompositeShape3D() {
}

CompositeShape3D::CompositeShape3D(Shape3D** s, int n) {
  shapes = s;
  length = n;
}

bool CompositeShape3D::intersectsWith(const Ray& r,
                             float tMin, float tMax,
                             Intersection* intersection) const {
  Intersection temp;
  bool intersects = false;
  double closest = tMax;

  for (int i = 0; i < length; i++) {
    if (shapes[i]->intersectsWith(r, tMin, closest, &temp)) {
      intersects = true;
      closest = temp.t;
      intersection->shape = temp.shape;
      intersection->t = temp.t;
      intersection->p = temp.p;
      intersection->n = temp.n;
      intersection->material = temp.material;
    }
  }
  return intersects;
}
        
The Light Class

The Specification

cppexamples/graphics3d/Light.h
        #ifndef edu_jmu_cs_Light_h
#define edu_jmu_cs_Light_h

#include <glm/glm.hpp>

/**
 * An encapsulation of a Light.
 *
 * @author Prof. David Bernstein, James Madison University
 */
class Light {
 public:
  glm::vec3 location;
  glm::vec3 color;

  /**
   * Explicit Value Constructor.
   *
   * @param xyz  The location of the Light
   * @param rgb  The color/intensity of the Light
   */
  Light(const glm::vec3 &xyz, const glm::vec3 &rgb);
};

#endif
        
The Light Class (cont.)

The Implementation

cppexamples/graphics3d/Light.cpp
        #include "Light.h"

Light::Light(const glm::vec3 &xyz, const glm::vec3 &rgb):
    location(xyz), color(rgb) {
}