CS184 Section 5
Acceleration Structures

Brandon Wang
February 26, 2013
Material adapted from James O'Brien.

Logistics

• Do AS2.

Today

• BSP Trees
• AABB Trees

Acceleration Structures

Even if you do not implement them for AS2, you are responsible for knowing them.

BSP Trees

Split space into partitions, along each plane (3D) or line (2D).

k-d Trees

AABB Trees

Ray Tracer Structure

class Scene
{
  public:
    ...
    bool intersect(Ray &r, double &closest_t, 
      GeometryProperties &geom_prop, MaterialProperties &mat_prop);
  private:
    std::vector<Primitive> primitives;
    std::vector<Light> lights;
}

Ray Tracer Structure

bool scene::intersect(Ray &r, double &closest_t, 
  GeometryProperties &geom_prop, MaterialProperties &mat_prop);
{
  closest_t = std::numeric_limits<double>::infinity();
  for(std::vector<Primitive> prim_it = primitives.begin();
    prim_it != primitives.end(); ++prim_it)
  {
    Primitive cur_prim = *prim_it;
    ...
  }
}

Ray Tracer Structure

class Scene
{
  public:
    ...
    bool intersect(Ray &r, double &closest_t, 
      GeometryProperties &geom_prop, MaterialProperties &mat_prop);
    void calculateAcceleration();
  private:
    AABBNode acceleration_root;
    std::vector<Primitive> primitives;
    std::vector<Light> lights;
}

Ray Tracer Structure

bool scene::intersect(Ray &r, double &closest_t, 
  GeometryProperties &geom_prop, MaterialProperties &mat_prop);
{
  closest_t = std::numeric_limits<double>::infinity();
  std::vector<Primitive> relevant_prims = 
    acceleration_root.relevant_prims(r);
  for(std::vector<Primitive> prim_it = relevant_prims.begin();
    prim_it != relevant_prims.end(); ++prim_it)
  {
    Primitive cur_prim = *prim_it;
    ...
  }
}

Ray Tracer Structure

• Scene
• Camera
• Acceleration Structure
• Matrix Stack
• Primitives (with subclasses: Sphere, Triangle, etc)