Ray Tracing S01E07


Multiple Objects

So far the scene included only a single sphere set in the center. In this episode we’re going to add support for multiple objects in a scene. This could be done with an array of sphere objects, but a cleaner solution is to use an abstract class for anything a ray can hit, may it be a single sphere, a list of spheres, triangles, boxes, etc.

The hittable abstract class has a hit function that takes the ray r, a range of t from $t_{min}$ and $t_{max}$ and a hit_record structure. The hit_record will be used to track computed normals. If the ray hits multiple objects, only the closest object should count. Hit_record helps making the decision and dismiss hits that are not needed.

Inside the structure there’s also a float t as a time input variable. It will be used later for motion blur. And p is the hit point.

// hittable.h
#ifndef HITTABLEH
#define HITTABLEH

#include "ray.h"

struct hit_record {
  float t;
  vec3 p;
  vec3 normal;
};

class hittable {
  public:
    virtual bool hit(const ray& r, float t_min, float t_max, hit_record& rec) const = 0;
};
#endif

And this is the new sphere extending the hittable class:

// sphere.h
#ifndef SPHEREH
#define SPHEREH

#include "hittable.h"

class sphere: public hittable {
  public:
    sphere() {}

    // constructor that sets center and radius properties below
    sphere(vec3 cen, float r) : center(cen), radius(r) { };

    virtual bool hit(const ray& r, float t_min, float t_max, hit_record& rec) const;

    vec3 center;
    float radius;
};

bool sphere::hit(const ray& r, float t_min, float t_max, hit_record& rec) const {
  vec3 oc = r.origin() - center;
  float a = dot(r.direction(), r.direction());
  float b = dot(oc, r.direction());
  float c = dot(oc, oc) - radius*radius;
  float discriminant = b*b - a*c;

  if (discriminant > 0) {
    // solve quadratic formula -b - sqrt()
    float temp = (-b - sqrt(discriminant))/a;
    if (temp < t_max && temp > t_min) {
      rec.t = temp;
      rec.p = r.point_at_parameter(rec.t);
      rec.normal = (rec.p - center) / radius;
      return true;
    }

    // solve quadratic formula -b + sqrt()
    temp = (-b + sqrt(discriminant))/a;
    if (temp < t_max && temp > t_min) {
      rec.t = temp;
      rec.p = r.point_at_parameter(rec.t);
      rec.normal = (rec.p - center) / radius;
      return true;
    }
  }
  return false;
}
#endif

In the highlighted sections above, 2.0 was eliminated from b, the discriminant, and the denominator because they cancel each other out:

\[ \frac{ -b \pm \sqrt{b^2 - 4ac}}{2a} \]

$$ = \frac{2 (oc \cdot r_d) \pm \sqrt{(2 (oc \cdot r_d))^2 - 4ac}}{2a} $$ $$ = \frac{2 (oc \cdot r_d) \pm \sqrt{4 ((oc \cdot r_d)^2 - ac)}}{2a} $$ $$ = \frac{(oc \cdot r_d) \pm \sqrt{(oc \cdot r_d)^2 - ac}}{a} $$

If the discriminant is greater than 0 we know we hit the sphere. Then we check if the result for t lies within $ t_{min} $ and $ t_{max} $ - first with the smaller result $ -b - \sqrt{} $, then with the larger result $ -b + \sqrt{} $.

If the result is within the range, we store it in the hit_record along with the hit point and the normal at the hit point.

A list of multiple hittables can extend from the abstract hittable class as well:

// hittable_list.h
#ifndef HITTABLELISTH
#define HITTABLELISTH

#include "hittable.h"

class hittable_list: public hittable {
  public:
    hittable_list() { }
    hittable_list(hittable **l, int n) { list = l; list_size = n; }

    virtual bool hit(const ray& r, float t_min, float t_max, hit_record& rec) const;

    hittable **list;
    int list_size;
};

bool hittable_list::hit(const ray& r, float t_min, float t_max, hit_record& rec) const {
  hit_record temp_rec;

  // flag to indicate if we've hit anything at all
  bool hit_anything = false;

  // start with the farthest t
  float closest_so_far = t_max;

  // loop through the list
  for (int i = 0; i < list_size; i++) {
    // if we hit something set closest_so_far to the new hit object t which will also become the t_max for the next iteration
    if (list[i]->hit(r, t_min, closest_so_far, temp_rec)) {
      hit_anything = true;
      closest_so_far = temp_rec.t;
      rec = temp_rec;
    }
  }

  return hit_anything;
}
#endif

If there’s a list of multiple spheres, we only need to know which object the ray hits first. Here’s where the range $ t_{min} $ and $ t_{max} $ becomes useful. For each object, we adjust $ t_{max} $ to the closest found so far.

Excursion: Pointers and References in C++

At this point it may be time for a quick refresher on pointers and references in C++.

vec3 color(const ray& r, hittable *world) {
  hit_record rec;
  if (world->hit(r, 0.0, MAXFLOAT, rec)) { 
       return 0.5*vec3(rec.normal.x()+1, rec.normal.y()+1, rec.normal.z()+1);
  }
}

bool sphere::hit(const ray& r, float t_min, float t_max, hit_record& rec) const {
  vec3 oc = r.origin() - center;
  // ...
  rec.t = temp;
  rec.p = r.point_at_parameter(rec.t);
  rec.normal = (rec.p - center) / radius;
}

class hittable_list: public hittable {
  hittable_list(hittable **l, int n) { list = l; list_size = n; }
  hittable **list;
};

hittable *list[2];
list[0] = new sphere(vec3(0,0,-1), 0.5);
list[1] = new sphere(vec3(0,-100.5,-1), 100);
hittable *world = new hittable_list(list, 2);

This block of code contains a few examples of how various different pointer and reference operators are used in our ray tracer. It’s pretty clear what they accomplish here, but I have to admit I had to stop and think for a moment about why there’s a & operator here, a * there, and **, . and -> in other places. I’ll try to summarize quickly.

Variables

Let’s start with the easiest concept I still remember from my days in school. :)

Every variable is a location in memory and has a memory address that can be accessed with the ampersand operator.

int a, b;
cout << a << ", " << b << "\n"; // 0, 0
cout << &a << ", " << &b << "\n"; // 0xffffcc0c, 0xffffcc08

This line declares two int variables a and b which occupy the memory addresses 0xffffcc0c and 0xffffcc08 (in cygwin on this machine). Notice the distance between them is 4 bytes, the size of an integer.

void test_by_value(int x, int y) { ... }

If I pass these variables into a function with regular int arguments, the function will make a copy of these variables and store them in a different place in memory for the duration of the function call. Any changes made to x and y will be lost when I exit the function and return to main().

References

void test_by_reference(int &x, int &y) { ... }

But if I pass these variables into a function that defines its arguments as int references, the function will not make a copy of the variables but operate on the same memory location as the original variables a and b. For example, if the function changes x, it will also change a outside of the function scope.

bool sphere::hit(..., hit_record& rec) const { ... }

This is used to allow the hit function to change the hit_record and make it available to the next function call.

Pointers

So far, so good - this is pretty straightforward. The same can also be accomplished with pointers. A pointer is a variable whose value is a memory address.

int* a_ptr = &a;
int* b_ptr = &b;

If I call a function with these pointers, I can also change the values just like the reference variables above. The new values will persist outside the scope of the function:

void test_with_pointers(int* x, int* y) { ... }
test_with_pointers(a_ptr, b_ptr);

Inside the function, x and y refer to memory addresses, and *x and *y to the variable values at these addresses. For example, if I change *x to 123, I will find the original variable a with the same value.

This is where things may become a little confusing because the * is used to declare as well as dereference a pointer. And why are there references and pointers if they accomplish essentially the same thing?

The references are available in C++, and pointers were inherited from C. References are considered safer than pointers. It’s not possible to manipulate references like pointers. Its name always refers directly to the object it references. You can’t point it to a different object later, but you can do that with pointers.

Wikipedia has more details about references and pointers.

Arrays

The primitive datatypes were pretty simple, but I have to admit that **, -> and . confused me for a moment in the source code above. Let’s take a quick look at these now.

int list[3];
list[0] = 1;
list[1] = 2;
list[2] = 3;
cout << list << "\n";         // 0xffffcbdc
cout << &list[0] << "\n";     // 0xffffcbdc
cout << &list[1] << "\n";     // 0xffffcbe0
cout << &list[2] << "\n";     // 0xffffcbe4
cout << &*(list) << "\n";     // 0xffffcbdc
cout << &*(list + 1) << "\n"; // 0xffffcbe0
cout << &*(list + 2) << "\n"; // 0xffffcbe4
cout << list[0] << "\n";      // 1
cout << *list << "\n";        // 1
cout << *(list + 1) << "\n";  // 2
cout << *(list + 2) << "\n";  // 2

A few observations:

  • list without the square brackets is the memory address of the first element which essentially makes list a pointer.
  • list[0] is equivalent to *list where ‘*’ is used as a dereferencing operator.
  • the square brackets [n] are essentially a shortcut for *(list + n)
  • &*(list + n) gives the memory address of the nth element. Notice the distance between the memory addresses? 4 Bytes, the length of the int data type.

If I pass a list by value into a function just like the primitive values above…

void list_not_really_by_value(int l[3]) { ... }

the function will not as expected change the values of a local copy, but the original list as well. This is a consequence of list being a pointer. The following is equivalent to the function declaration with int l[3]:

void list_not_really_by_value(int *l) { ... }

Objects

In our ray tracer we have a list of pointers to object instances:

hittable *list[2];
list[0] = new sphere(vec3(0,0,-1), 0.5);
list[1] = new sphere(vec3(0,-100.5,-1), 100);
hittable *world = new hittable_list(list, 2);

Object instances have to be collected in an array of pointers. I won’t be able to initialize the list as hittable list[2] because the new keyword returns an address after allocating memory for the instance.

Well, that’s not entirely correct, I could create a hittable list[2] and then assign *new sphere(..), for example:

test testlist[2];
testlist[0] = *new test(2);
testlist[1] = *new test(5);
cout << &testlist[1] << "\n";      // address 1
cout << testlist[1].get() << "\n"; // value 5
cout << (&testlist[1])->get() << "\n";  // value 5 as well

In addition to the int-constructor and the get() function, the test class will also need a default constructor without function arguments for this to compile without errors. For example test() { value = 0; }. But back to the array of pointers:

test *testlist[2];
testlist[0] = new test(2);
testlist[1] = new test(5);
cout << testlist[1] << "\n";          // address 1
cout << testlist[1]->get() << "\n";   // value 5
cout << (*testlist[1]).get() << "\n"; // value 5 as well

Both versions return memory addresses and values where you’d expect them. I’m not sure if there is any difference.

Note the use of ->get() versus .get() in both examples. When I try to access a member of an object given with its address, I have to use ->. If it’s a dereferenced object instance, I will have to use ..

Back to our ray tracer:

So we keep track of our hittable elements with an array of pointers list. The world is a pointer to a new hittable_list instance. The array pointer is passed into the constructor of hittable_list.

hittable *list[2];
list[0] = new sphere(vec3(0,0,-1), 0.5);
list[1] = new sphere(vec3(0,-100.5,-1), 100);
...
hittable *world = new hittable_list(list, 2);
...
class hittable_list: public hittable {
  hittable_list(hittable **l, int n) { list = l; list_size = n; }
  hittable **list;
};

What’s going on here? Suddenly there are two asterisks, but why? In declarations those two ** simply mark a pointer to a pointer. It holds the memory address of another pointer. It can also be a double-dereferencing operator.

For primitive arrays as in int list[3] I’ve shown abov that the variable list is a pointer itself, and that the function declaration can accept an array as int *l.

When dealing with a list of pointers as in hittable *list[2] we’re really looking at pointers to pointers. For a function declaration it means that we need to use hittable **l.

This excursion turned out to be a little longer than intended, but I felt it was really necessary to get up to speed for all the C++ programming that follows. After so many years of Javascript and PHP I’m afraid (and ashamed) I simple wasn’t used to explicit pointers and references anymore. :)

Javascript and Canvas

Here’s also the Javascript implementation. Two spheres! So far it’s rendering pretty fast even in Javascript. :)

Please see my repository at github.com/celeph/ray-tracing for the complete code. For more details, check out Peter Shirley’s excellent book that inspired this episode: “Ray Tracing in One Weekend” and his original book and code repo.

Coming next: S01E08 - Antialiasing

Or go back to: S01E06 - Surface Normals

Or start over at the beginning: S01E01 - Introduction

Credits and Further Reading