T1 AABB Box (MS1)

We have learned in semester 1 that hierarchical spatial data structures such as AABB, Octree, Bounding Sphere Volumes can be used to accelerate ray-object intersection. This can be used for picking as well as for ray tracing.

In this tutorial, Professor Shirley used the simplest one - AABB, as we did in semester 1 for picking.

We have learned that for Ray-AABB intersection, we are using the slab algorithm.

Add a new public method expand() for class interval in interval.h

class interval {
  public:
    // ...

    // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
    // merge two intervals into one
    interval(const interval& a, const interval& b) {
        // Create the interval tightly enclosing the two input intervals.
        min = a.min <= b.min ? a.min : b.min;
        max = a.max >= b.max ? a.max : b.max;
    }
    // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
    
    // ...
    
    // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
    interval expand(double delta) const {
        auto padding = delta/2;
        return interval(min - padding, max + padding);
    }
    // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
    
    // ...
};

Add a new aabb class for the axis aligned bounding box

create aabb.h and put the following code into it.

The aabb is defined by three intervals along the x, y, z direction.

The most important method, hit(), implemented the slab algorithm.

(t_exit is ray_t.max, t_enter iray_t.min)

#ifndef AABB_H
#define AABB_H

class aabb {
  public:
    interval x, y, z;

    aabb() {} // The default AABB is empty, since intervals are empty by default.

    aabb(const interval& x, const interval& y, const interval& z)
      : x(x), y(y), z(z) {}

    aabb(const point3& a, const point3& b) {
        // Treat the two points a and b as extrema for the bounding box, so we don't require a
        // particular minimum/maximum coordinate order.

        x = (a[0] <= b[0]) ? interval(a[0], b[0]) : interval(b[0], a[0]);
        y = (a[1] <= b[1]) ? interval(a[1], b[1]) : interval(b[1], a[1]);
        z = (a[2] <= b[2]) ? interval(a[2], b[2]) : interval(b[2], a[2]);
    }
    
    // compute the bbox  of two bbox
    aabb(const aabb& box0, const aabb& box1) {
        x = interval(box0.x, box1.x);
        y = interval(box0.y, box1.y);
        z = interval(box0.z, box1.z);
    }

    const interval& axis_interval(int n) const {
        if (n == 1) return y;
        if (n == 2) return z;
        return x;
    }

    bool hit(const ray& r, interval ray_t) const {
        const point3& ray_orig = r.origin();
        const vec3&   ray_dir  = r.direction();

        for (int axis = 0; axis < 3; axis++) {
            const interval& ax = axis_interval(axis);
            const double adinv = 1.0 / ray_dir[axis];

            auto t0 = (ax.min - ray_orig[axis]) * adinv;
            auto t1 = (ax.max - ray_orig[axis]) * adinv;

            if (t0 < t1) {
                if (t0 > ray_t.min) ray_t.min = t0;
                if (t1 < ray_t.max) ray_t.max = t1;
            } else {
                if (t1 > ray_t.min) ray_t.min = t1;
                if (t0 < ray_t.max) ray_t.max = t0;
            }

            if (ray_t.max <= ray_t.min)
                return false;
        }
        return true;
    }
};

#endif

Add a bounding_box virtual interface in hittable

#include "ray.h"
#include "aabb.h" // <<<<<<<<<<<<<<<<<<<<<<<<<

class material;  

// ...

// an abstract class for objects can be hit.
// all hittable objects, such as sphere, triangle, should inherit from it
class hittable {
  public:
    virtual ~hittable() = default;

    // every descedant class need to implement this method
    // to provide means to calculate the intersection point
    
    //virtual bool hit(const ray& r, double ray_tmin, double ray_tmax, hit_record& rec) const = 0;
    virtual bool hit(const ray& r, interval ray_t, hit_record& rec) const = 0;

    //>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
    virtual aabb bounding_box() const = 0;
    //<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
};

Revise sphere.h to add the bounding box

add a bbox private member in class sphere, revise the construtor and add a get method (returning bbox).

Note: Don't use static_center if you skipped motion blur. Please see the following code.

class sphere : public hittable {
  private:
    point3 center;
    double radius;
    shared_ptr<material> mat; 
    aabb bbox;  // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
    
  public:
    sphere(const point3& center, double radius, shared_ptr<material> mat)
    //  : center(center), radius(std::fmax(0,radius)), mat(mat) {}
    // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
    /* use static_center if have done motion blur 
    : center(static_center, vec3(0,0,0)), radius(std::fmax(0,radius)), mat(mat)
    {
        auto rvec = vec3(radius, radius, radius);
        bbox = aabb(static_center - rvec, static_center + rvec);
    }
    */
    // otherwise stick to center
    : center(center), radius(std::fmax(0,radius)), mat(mat)
    {
        auto rvec = vec3(radius, radius, radius);
        bbox = aabb(center - rvec, center + rvec);
    }

    aabb bounding_box() const override { return bbox; }
    // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
    
    // ...
};

Creating Bounding Box for List of Objects

hittable_list.h

Add a private bbox member for hittable_list.

Revise add() to update the bbox when adding new objects.

Add a get method to return the bbox.

class hittable_list : public hittable {
  
  private:
    aabb bbox;  // <<<<<<<<<<<<<<<

  public:
    std::vector<shared_ptr<hittable>> objects;

    hittable_list() {}
    hittable_list(shared_ptr<hittable> object) { add(object); }

    void clear() { objects.clear(); }

    void add(shared_ptr<hittable> object) {
        objects.push_back(object);
        // update bbox when adding new objects
        bbox = aabb(bbox, object->bounding_box()); // <<<<<<<<<<<<<<<
    }

    aabb bounding_box() const override { return bbox; } // <<<<<<<<<<<<<<<
    
    // ...
};

Add a bvh_node class

create bvh.h, write class bvh_node to inherit from the hittable abstract class

#ifndef BVH_H
#define BVH_H

#include <algorithm> // you can also add it at the beginning of rtweekend.h

#include "aabb.h"
#include "hittable.h"
#include "hittable_list.h"

class bvh_node : public hittable {
  public:
    bvh_node(hittable_list list) : bvh_node(list.objects, 0, list.objects.size()) {
        // There's a C++ subtlety here. This constructor (without span indices) creates an
        // implicit copy of the hittable list, which we will modify. The lifetime of the copied
        // list only extends until this constructor exits. That's OK, because we only need to
        // persist the resulting bounding volume hierarchy.

    }

    bvh_node(std::vector<shared_ptr<hittable>>& objects, size_t start, size_t end) {
        int axis = random_int(0,2);

        auto comparator = (axis == 0) ? box_x_compare
                        : (axis == 1) ? box_y_compare
                                      : box_z_compare;

        size_t object_span = end - start;

        if (object_span == 1) {
            left = right = objects[start];
        } else if (object_span == 2) {
            left = objects[start];
            right = objects[start+1];
        } else {
            std::sort(std::begin(objects) + start, std::begin(objects) + end, comparator);

            auto mid = start + object_span/2;
            left = make_shared<bvh_node>(objects, start, mid);
            right = make_shared<bvh_node>(objects, mid, end);
        }

        bbox = aabb(left->bounding_box(), right->bounding_box());
    }

    bool hit(const ray& r, interval ray_t, hit_record& rec) const override {
        if (!bbox.hit(r, ray_t))
            return false;

        bool hit_left = left->hit(r, ray_t, rec);
        bool hit_right = right->hit(r, interval(ray_t.min, hit_left ? rec.t : ray_t.max), rec);

        return hit_left || hit_right;
    }

    aabb bounding_box() const override { return bbox; }

  private:
    shared_ptr<hittable> left;
    shared_ptr<hittable> right;
    aabb bbox;

    static bool box_compare(
        const shared_ptr<hittable> a, const shared_ptr<hittable> b, int axis_index
    ) {
        auto a_axis_interval = a->bounding_box().axis_interval(axis_index);
        auto b_axis_interval = b->bounding_box().axis_interval(axis_index);
        return a_axis_interval.min < b_axis_interval.min;
    }

    static bool box_x_compare (const shared_ptr<hittable> a, const shared_ptr<hittable> b) {
        return box_compare(a, b, 0);
    }

    static bool box_y_compare (const shared_ptr<hittable> a, const shared_ptr<hittable> b) {
        return box_compare(a, b, 1);
    }

    static bool box_z_compare (const shared_ptr<hittable> a, const shared_ptr<hittable> b) {
        return box_compare(a, b, 2);
    }

};

#endif

add random_int() in rtweekend.h

// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
inline int random_int(int min, int max) {
    // Returns a random integer in [min,max].
    return int(random_double(min, max+1));
}
// <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

Revise main.cpp

add bvh. to main.cpp

change the scene to a simple two sphere scene

set the image resolution to a low resolution for fast testing

#include "rtweekend.h"

#include "bvh.h"  // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
#include "camera.h"
#include "hittable.h"
#include "hittable_list.h"
#include "material.h" 
#include "sphere.h"


int main() {

    hittable_list world;
    
    // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
    auto material2 = make_shared<lambertian>(color(0.4, 0.2, 0.1));
    world.add(make_shared<sphere>(point3(-4, 1, 0), 1.0, material2));

    auto material3 = make_shared<metal>(color(0.7, 0.6, 0.5), 0.0);
    world.add(make_shared<sphere>(point3(4, 1, 0), 1.0, material3));

    world = hittable_list(make_shared<bvh_node>(world));
    // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

    camera cam;

    cam.aspect_ratio      = 16.0 / 9.0;
    // cam.image_width       = 1200;
    // cam.samples_per_pixel = 500;
    cam.image_width       = 400;
    cam.samples_per_pixel = 100;
    cam.max_depth         = 50;

    cam.vfov     = 20;
    cam.lookfrom = point3(13,2,3);
    cam.lookat   = point3(0,0,0);
    cam.vup      = vec3(0,1,0);

    // if you are using defocus, you can set the following parameters
    // cam.defocus_angle = 0.6;
    // cam.focus_dist    = 10.0;

    cam.render(world);

}

Build and Run

Build and run you programme, if successful, you are going to see an image similar to the following

Note: I did do Gamma correct so my image may look darker.