In this final segment for the first rayracing lecture, we're going
to consider optimizations and acceleration.

Testing each object for each ray is slow. This is one of the causes
why raytracing has historically been slow.

One can therefor consider using fewer rays by adaptively sampling
which pixels to shoot a ray fo,r by having adaptive depth controls. One
could also consider generalized rays where you shoot multiple rays at
a time: things like beam tracing, cone tracing, pencil tracing and so
on.

Finally, one can consider faster intersections where one optimizes a
ray object intersection. So ray triangle intersections are very
optimized. Or, and this is where most of the acceleration work falls,
one can have fewer intersections.

We come to a rich area of raytracing known as acceleration structures,
where given a ray, you want to ensure that you test as few objects as
possible: ideally only the object the ray will hit. That's not possible
in practice but we can often consider the number of intersections to
be logarithmic in the total size of the number of objects.

So first we consider bounding boxes possibly hierarchically, so you
could have a bounding box for the whole scene, the bounding box for your
room, the bounding box for the various triangles in your room.

If the ray doesn't intersect the entire bounding box, and remember,
there are very efficient ray box intersection tests, then one needn't
check the individual objects within the bounding box. One can also
consider spatial hierarchies that organize these bounding boxes,
things like oct-trees, kd trees, BSP trees. BSP stands for binary
space partitioning. Octtree takes 3D space, cuts it along the center
for each axis of a cube, to break it into 8 octants.

Another acceleration structure is a grid. And so this could be a
regular grid or hierarchical grid as far as we're concerned we're
going to consider just a regular grid.
I trace my way through the grid.

So what I do is, I first go to the first grid cell.
And I see there's no intersection. Also, note that the traversal
through the grid might seem irregular, but in fact there are regular
intersection points along either of the two axes here, or three axes
in 3D, and so you can very simply and incrementally compute the
next intersection point in the next cell. So I go to the next cell and
each cell has a pointer to all of the objects that intersect that
cell. The next cell after that, the next cell after that, and now we
can see that I have an intersection, that
I need to test. So I need to test my ray against this object, but
it doesn't intersect. So I go to the next point. And if I implement
something like mailboxing, I know I've already tested against this
object, so I don't need to test again. Come down here.

Again I need to test against this object, no intersection, go forward.
And finally I have the object that I'm actually intersecting. One of
the interesting things to note is that the two objects on the side, so
this object and this object, were never tested against. There was no
need to actually even test them for intersection, and so a large part
of the space that is not in the traversal part actually need never be
tested for a ray surface intersection.

So regular grids are the simplest acceleration structure. So, for
example, a 5 by 5 by 5 grid. For each grid cell you store all the
overlapping triangles, you march the way along the grid, you need to
be careful in doing this efficiently and you test against each
triangle in the grid cell. There are of course more complicated
spatial data structures trees like kd-trees, octtrees, bsptrees or
you can use hierarchical bounding boxes.