CS184 Section 5
Acceleration Structures

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

Logistics

Today

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).

BSP Worksheet

Worksheet

k-d Trees

AABB Trees

k-d/AABB Worksheet

Worksheet

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