' '

Meshes made out of triangles can be used to model any shape: we simply need more triangles. The problem with having meshes consisting of millions of triangles is obvious: rendering times go through the roof. We need to find a way to speed it up quite a bit if we want to be able to admire the results within our lifetime.

1. Bounding Box Hierarchy

There are many ways to speed things up. You are free to implement any approach you wish, but in these pages, we will discuss one particular technique, namely bounding boxes.

The idea behind bounding boxes is simple. Say you have a mesh consisting of a million triangles, then for every ray shot out of the eye, you normally would compute its intersection with each of the million triangles, which amounts to a lot of work. We desperately want to cut that number down.

We can achieve that by enclosing all those triangles into a tight-fitting box. Then, for each ray, we would first check if the ray intersects with the box. If it doesn’t, the ray will not intersect any triangles inside the box. We just saved ourselves a million hit-checks. Of course, if the ray does intersect the box, we’re back to square one and have to deal with all million triangles.

def is_hit(ray, box):
  if ray hits box:
    # Assumes that the contents of the box are all triangles
    return any(is_triangle_hit(ray, triangle) for triangle in box.contents)
  else:
    return False
Example
bbh1

Let’s say the mesh consists of \(N\) triangles. We build a nice box around them. The green ray flies by the box containing all triangles. Only one intersection test is necessary, namely the one with the box.

The red ray, however, does hit the box, so all \(N\) triangles have to be considered in turn. Result: \(N+1\) intersection tests are necessary.

We could, however, add more boxes. Say we divide the large all-encompassing box into two additional smaller boxes: the upper half and the lower half. Each box would contain approximately half a million triangles. Then, if the ray intersects the large box, we check which of the two smaller boxes it intersects. If we’re lucky, the ray misses one of the smaller boxes and we avoided half a million hit-checks.

def is_hit(ray, object):
  if isinstance(object, Triangle):
    return is_triangle_hit(ray, object)
  else:
    # Note the recursive call: a child can be a BoundingBox
    return any(is_hit(ray, child) for child in object.contents)
Example
bbh2

Again we have \(N\) triangles. We put them in one big box. But inside the big box, we add two smaller boxes, each containing \(N/2\) triangles.

  • The green ray misses the outer box, so only 1 intersection check necessary.

  • The blue ray hits the outer box (1 intersection check). We check the two inner boxes (2 more intersection checks). The left box is hit, so we need to go through all triangles in the left box (\(N+2\) intersection checks). Total: \(N/2 + 3\) checks.

  • The red ray is less lucky. We first check if it hits the outer box (1 check), it does. Then, we check the two inner boxes (2 checks) and we see it hits both. All triangles need to be processed (\(N\) checks). Total: \(N+3\) checks.

We can continue this process recursively: we split each box into smaller boxes, thereby creating a bounding box hierarchy. We continue to do so until each single box contains only a small number of triangles. When tracing a ray, we only need to consider the contents of boxes it actually intersects. This way, instead of having to process a million triangles, we can get away with, say, a hundred.

The building of this bounding box hierarchy takes time. Fortunately, this needs to be done only once per mesh: once done, we can write the box hierarchy to file and read it whenever the mesh pops up in a scene. This means, however, that we need to build a tool separate from the ray tracer, one that reads in all triangles, builds the bounding box hierarchy and stores it into a file.

2. Approaches

How does one build a bounding box hierarchy? There are many ways and none of them is the One True Way. This is where you get creative, try out things and measure the rendering times to found out how well your algorithm is performing. Dare to experiment and think of how you could improve performance.

2.1. Bottom Up Approaches

One way to create a bounding box hierarchy is to start at the bottom (i.e., the triangles) and group them together into boxes. Then, in a second phase, you group those boxes together in bigger boxes. You continue like this until you’re left with only a single box.

  • How many triangles/boxes you bundle together is up to you. You might go for 10, for 2, or for some other number that might be decided upon dynamically.

  • Which triangles/boxes you team up is also up to you. Perhaps you simply group them randomly, or you try to find the two that are closest together.

  • "Closest together" is also ill-defined. How does one decide how far two triangles are from each other? Again, up to you. Perhaps you measure the distance between the centers, or simply of the first vertex of each.

2.2. Top Down Approaches

You could also start by building a large box that fits all triangles. Next, you divide this box into N subboxes. These boxes you also subdivide. After a number of subdivisions, you determine in which of these boxes a triangle fits.

  • There are many ways to subdivide a box into subboxes.

    • You can choose a random dimension and halve it along that dimension.

    • You can determine the longest dimension and halve along that dimension.

    • You can cut the box in two equal halves, or you can cut it so that you will have an equal amount of triangles in each subbox.

    • You can use an octree approach and subdivide each box in eight subboxes.

  • How long will you subdivide boxes?

    • You could go for a fixed amount.

    • You could subdivide until the box has a certain size.

    • You could subdivide until only K triangles fit in the box.