Ray Tracing 007Hittable

Summary

Added a base class to represent any object that can be hit by a ray.
Extending this class, I added a hittable sphere class.
Also extending this class, I added a hittable list.
Updated to render a hittable list representing a world with a couple of spheres inside.
Excursion: A refresher in C++ pointers and references.

Previously, I only had a single sphere in the scene. I want to be able to add multiple spheres, and eventually other objects to the scene. In this chapter I add 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.

Click to view C++ source code

// 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:

Click to view C++ source code

// 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());
  [HL]
  float b = dot(oc, r.direction());
  [/HL]
  float c = dot(oc, oc) - radius*radius;
  [HL]
  float discriminant = b*b - a*c;
  [/HL]

  if (discriminant > 0) {
    // solve quadratic formula -b - sqrt()
    [HL]
    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;
    }
    [/HL]
  }
  return false;
}
#endif

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

\begin{equation} \frac{ -b \pm \sqrt{b^2 - 4ac}}{2a} \end{equation}

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

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

\begin{equation} = \frac{(oc \cdot r_d) \pm \sqrt{(oc \cdot r_d)^2 - ac}}{a} \end{equation}

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{b^2 - 4ac}$ , then with the larger result $-b+\sqrt{b^2 - 4ac}$ .

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:

Click to view C++ source code

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

Refresher: Pointers and References in C++

Warning: The following section turned out longer than expected and is mostly intended as a refresher for myself as I haven't programmed in C++ since college. This is for C++ beginners only. :)

Click to view C++ source code

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 this program. 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 decypher and summarize:

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 the 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);
[HL]
hittable *world = new hittable_list(list, 2);
[/HL]
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 above 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 necessary to get up to speed before I continue. I hope it will be a good reference when my memory fades again some day because I'm not using it enough. Perhaps it can be helpful for others as well :)

Javascript and Canvas

Here's the example in Javascript.

Figure RT007: Simple canvas image.

Click to view Javascript source code

Gerrit Wessendorf 👋

Ray Tracing 007Hittable

Next Steps

Summary

Refresher: Pointers and References in C++

Variables

Pointers

Arrays

Objects

Back to the ray tracer

Javascript and Canvas

Links

Next Steps