Part 2: Gotta Go Fast/Power of Linear Algebra

 

Hello everybody, In this post I will be explaining the details of my second homework of Advanced Ray Tracing.

This Homework consists of two parts. First part is about implementing an acceleration structure for ray tracing. The other is about linear transformations and object instancing.

Acceleration Structures

    Before going into details I want to start by explaining what the acceleration structures are. If you you remember my first blog post or know anything about ray tracing at all, you should know that in ray tracing we send a ray from camera through each pixel and depending on the object/objects that ray is intersecting we determine that pixel's color by doing shading computations. Obviously in this process we need to choose the closest object to the eye. I don't know if you have noticed or not but this is basically a search algorithm. And would you look at that there are ways to optimize search algorithms. From basic knowledge of algorithms we know that searches can be done in O(logN) time. This is the quickest way to explain Bounding volume hierarchy or any other acceleration structure in my opinion. But of course we will go into details.

    In the previous post I was just intersecting my rays with every object with my rays then choosing the closest one leaving me with O(N) complexity. Now I am going to implement one of the most popular acceleration structures for ray tracing which being bounding volume hierarchy. If you'd like to learn about other ones you can check out kd-tree's or grid acceleration structure yourself.

Bounding Boxes

Before directly going into bounding volume hierarchy(BVH) I want to explain another concept we are going to use which are bounding boxes.

The idea of a bounding box is really simple instead of intersecting our ray with a complex object like this camouflage bunny below. (Because intersecting a ray with this bunny means intersecting the ray with all of it's triangles.)

We will put it in a box and check if the box is intersecting with the ray or not. If the ray doesn't intersect with the box we can be sure that ray doesn't intersect with the bunny and move on. Of course if they intersect we still have to test it but this will still save us a lot of time.

Bounding Volume Hierarchy

Now that we know bounding boxes we will use them in a more complicated (actually not so complicated) structure. We are going to use this bounding boxes and build a tree hierarchy with it. So the basic idea goes like this.

Let us have these Perlin bunnies chilling in our scene.

We take all the bunnies and computer their common bounding box, then split objects into two groups. Then we compute their bounding box and repeat as you can see at some point we will get a bounding box with only one bunny. Finally we have a tree structure at our hands. Now we can send a ray to the root Bounding box if the ray hits it we check if the same ray hits the children of this bounding box. Be careful here because if a ray hits the left child of node that does not mean it will not hit the right. Depending on the scene it still might hit the right so we check a node's both children.

In this way have approximately reduced our complexity to approximately to O(logN) with a tree structure. Of course there are important things to notice here.I have purposefully selected the bunnies in the above scene If I had split the bunnies such that the yellowish bunny and the purplish/blueish black spotted bunny were in the same group, it would not reduce the size of our bounding box. So In order to solve that I sorted the objects according to their centroids along X axis and split the object list into two. In this way we usually en up reducing bounding boxes if we don't have a weirdly long object. Another good idea is to split the object along different axis' with each split. So if you have sorted them with respect to X axis first sorting them w.r.t Y, then Z, then X again and so on, next time is a better idea.

And voila now the dragon mesh below can be rendered in 8 seconds or so in my laptop with Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz processor. (In a better processor it takes even less. For instance in an Intel(R) Xeon(R) E-2224 CPU @ 3.40GHz cpu it takes like 3.5 seconds) Before implementing BVH I tried to render it and it didn't render in 52 minutes and I have interrupted it for the sake of my cpu.

Transformations and Instancing

As I have mentioned in my first blog post I rather not go into details of mathematics since there are much better sources for this. Hence I will just talk about the general idea in this part.

In computer graphics we define our objects by their geometry in 3D space. Luckily we have a very powerful tool to help us when dealing with objects: Linear Algebra. 

In linear algebra we can define translation, rotation and scaling transformations as matrices. As you know in 3D design tools these are super helpful. With transformations instead of changing an mesh object's each vertex coordinate to move the object in a scene we can just use a transformation. If you want to learn more about them search homogeneous transformations. We use homogeneous transformations because it allows us to express translation transformation as a matrix multiplication instead of vector summation. With homogeneous transformations we can compute a single composite transformation for each object instead of applying each transformation one by one. And another benefit having transformations is we can create multiple instances of an object without actually storing the object multiple times in the memory.

For instance I have rendered the following scenes with storing only one dragon mesh on the memory. 

 

 

Obviously I don't know for sure but the aliens in the Toy Story ,or any object/character in cinema with copies of them for that matter, are probably rendered with this method. If not that's a waste of good memory.

Delicate Points about transformations.

When using transformations we still have to actually intersect the ray with the objects. So one might say "Well, we still have to transform our meshes' each face before intersecting them." WRONG! Instead of transforming our objects we can just inverse transform our ray before intersecting with our object. In this way we will have to inverse transform one tiny ray instead of transforming a giant dragon. (eg. translate the ray 5 meters left instead of translating a huge dragon 5 meters to the right) We will get the same result.

One cool result of this inverse transforming ray instead of transforming objects is without defining an ellipsoid equation in our scene we can get an ellipsoid with scaling transforms like below. 

But that leaves us with another problem. We have just implemented BVH what are we going to do about the bounding boxes. Easy. We are going to compute the bounding boxes without transformations and before putting them into BVH we will apply the transformation to the bounding box. Now if the BVH detects that our world space ray is intersecting with our box we will then transform the ray to object space by applying inverse transformation and check for intersection.

One other problem you may run into is an mesh being instanced on an already instanced mesh. This may cause instances to lose transformation information or something else If not handled carefully but that can be handled by writing clean code (which I admit I didn't do quite well at first).

Conclusion

As you can see using acceleration structures and transformations at the same time, you can get a lot of efficiency and utility. If you are into ray tracing and CG they are a must because otherwise you would probably not go far because of the slowness and memory greedines of your programs.