Ray Tracing From Scratch: Optimizations & Transformations
A simple ray tracer was implemented in the previous blog post. Although it provides high quality realistic images, a lot of time required for rendering even a simple scene. In this blog post, some optimization techniques will be examined. In addition, shape transformations for defining scene geometry easily and instancing multiple shapes with different transformations from a shape will be shown.
Too Many Iterations
The ray tracing algorithm can be summarized as follows:
For a single pixel, the algorithm requires iterating each object, iterating those objects for each light source, then iterating each light source for each object again for shadows. Then, iterate that procedure for each pixel. Even there is no recursive part, which call the single pixel procedure repetitively, the algorithm requires too many iterations.
Excluding the shadow part and assuming there is one light source, the algorithm for a single pixel has O(n) complexity, where n is the object count. O(n) might seem not complex; however, for a simple scene with 800x800 resolution and 100 objects (a very low-poly mesh) 800*800*100 = 64000000 calculations are required. Considering the fact that even a single scene requires that many calculations, it is almost impossible to render a scene consists of millions of objects (very common for rendering). Therefore, a more efficient approach is required.
Bounding Volume Hierarchy
It is possible to provide a O(logn) solution for iterating all objects by using special data structures called as acceleration structures. Those structures simplifies the iteration process by defining hierarchy between objects, or spatially structuring the objects. One of the commonly used acceleration structures is Bounding Volume Hierarchy, or BVH.
BVH provides a hierarchical solution for that problem. Firstly, it defines a bounding box for each object. A bounding box is the smallest rectangular cuboid (rectangle in 2D) covering the object. Bounding boxes simplify the geometry object using only two vertices, namely the vertex with minimum coordinates and the vertex with largest coordinates. These vertices can be found by calculating maximum and minimum values for each coordinate axis.
Ray intersections with bounding boxes can calculate easily. However, the main use of bounding boxes in BVH is that two bounding boxes can be combined into one just by getting minimum and maximum coordinate values. If a ray hits one of the child bounding boxes, it also hits the parent bounding box. Conversely, if a ray does not hit the parent bounding box, it does not hit either boxes. Then, a ray-hit test can be done by testing intersection with the parent bounding box. Combining each pair of object boxes and parent boxes results in a BVH tree with one root box including all objects. The ray-hit tests for objects can be done by testing the parent bounding boxes, if hits testing their children and continuing the procedure recursively starting from the root. This solution divides the solution spaces and eliminates some parts so that it provides a logarithmic complexity compared to simple linear search of the space.
Construction of a BVH requires a little attention since a non-balanced tree produces slower even linear time solutions. Thus, it is not possible to divide leaf bounding boxes into left and right children bounding boxes randomly while constructing tree in a top-down manner. A naive solution might be finding center of the parent bounding box and leaf bounding boxes, then assigning children by comparing x values of the parent center and leaf centers. However, this solution splits children randomly if all centers have the same x values. Thus, a better approach would be testing each coordinate in a circular manner. For example, testing x values for the first level split, y values for the second level split and so on. Alternatively, a smarter coordinate selection might be used as explained in [2], which I have used in my implementation: Comparing range of center values for each three axis and choosing the axis with the largest range for acquiring a better split.
One of the problems I have faced during implementation of the construction algorithm is infinite recursion when all leaves are assigned to the same children. The solution for that problem is assigning half of the children boxes to the other children so that leaves are equally split. How to split children is not important since the main cause of the problem is objects with the same bounding box as given below:
Multithreading
Another optimization technique is using multi-threading. Thanks to parallelizable structure of the ray tracing algorithm, it is easy to implement multithreading. The approach I have used is one of the most naive ones: dividing pixels into equal regions in y axis and running different threads for each region. A better alternative might be dividing the pixels into smaller chunks, then assign those chunks for threads, and if a thread finishes its job, assign a new chunk.
The resulting speed ups after both optimizations are applied as follows:
Transformations
Transformations is a common method in rendering. The mesh data and its orientation can be separated thanks to it. Moreover, different instances can be rendered using the same mesh data by transforming the same data for each instance so that the storage is efficiently used. The most common transformations are translation, rotation and scaling.
Transformations can be defined as matrices. The resulting vertices can be found by multiplying the original vertex with the transformation matrix. Moreover, sequential transformations can be multiplied with each other and can be stored as a single matrix thanks to associative property of the matrix multiplication.
In order to provide translation operation requiring summation as a matrix operation an extra dimension is defined. Thus, 4x1 vectors used for vertices and 4x4 matrices used for transformations.
Translation
Translation moves vertices through axis directions. Each value defines the movement in each axis. The translation operation can be done as a matrix multiplication as follows:
Rotation
Rotation operation defines the amount of the rotation in angles in counter-clockwise and the rotation axis. The rotation operation can be done as a matrix multiplication as follows where K = 1-cos(rotation_angle) and a, b, and c are vector coordinates of the rotation axis:
Scaling
Scaling operation scales the vertices in each axis direction. Each value defines the scaling in each axis. The scaling operation can be defined as a matrix as follows:
For transforming a mesh, the composite transformation matrix can be multiplied with each vertex. However, this approach prevents acquiring efficiency via instancing. Thus, another useful property of transformations can be used: Instead of transforming objects, the rays can be transformed using inverse of the transformation operations as follows:
Normal transformation requires extra steps. Firstly, normals do not translate. Thus, their fourth element is assigned as 0. In addition, sphere normals depend on intersection points. Thus, they need to be recalculated after transformations. For triangle normals, inverse transpose is used to prevent errors caused by scaling.
For implementing instances in BVH, only bounding boxes ,which are pointing to the original instanced BVH, are transformed and used for intersection testing. Then, inversely transformed ray is sent to the instanced BVH for intersection testing. One important point while implementing bounding boxes is that rotations deforms the grid based structure. Thus, the bounding boxes must be recalculated as shown below:
There are some buggy results in my implementation when there is scaling. It is probably caused by normal transformation errors that I missed which I will fix in the next version. One of the buggy results are as follows:
Outputs
Sources
- Akyüz, A. O. (2022). CENG 795 Special Topics: Advanced Ray Tracing. Middle East Technical University.
- Pharr, M., Jakob, W., & Humphreys, G. Physically Based Rendering: From Theory To Implementation