Bounding Volume Hierarchy and Marble Solid Texture
by Dimitri Charitou
Introduction
For this project, I optimized my code by implementing a BVH (bounding volume hierarchy). This allowed for rendering multiple meshes in a scene. Throughout the class, the closest ray-primitive intersection was calculated using a linear search. This gave O(n) time such that n is the number of primitives in the scene. When attempting to render complex geometry containing thousands of triangles, the intersection calculation became very slow. The flame graph below displays a CPU profiling of the ray tracer using linear search. As is evident, the get_closest_hit function utilizes a significant amount of CPU cycles. Therefore, the intersection calculation should be optimized.
I also explored solid textures by implementing a marbled texture. Solid textures are simply procedurally generated textures calculated at runtime. While solid textures can be expensive, they are incredibly versatile as there is no explicit UV mapping calculation which must be programmed. Therefore, all geometry can be textured for free. See the figure below for an example of different textured geometry.
Bounding Volume Hierarchy (BVH)
A bounding volume hierarchy is a balanced binary tree whose datatype is some volume such as an axis-aligned bounding box, sphere, or capsule. Each level of the hierarchy contains a smaller volume than its parent. Primitives exist at the leaves. To find an intersection, the program must traverse the tree, searching for the closest intersection. If the ray does not hit a bounding volume, the program can prune all children of that subtree.
Construction
BVH's have a top-down construction. Conveniently, since primitives are not added to the scene, one does not need to implement self-balancing. Since construction ultimately occurs once, it is important to construct the most optimized tree to get the best performance. The key to good performance is building tight bounding volumes. This allows for more effective pruning. There are also heuristics which can be used calculate the most effective split of bounding volumes.
Traversal
The easiest method for traversing is a simple post-order traversal while simultaneously pruning the tree. This is the method which I implemented. While still naive, the algorithm yielded fantastic results. One method for optimizing traversal is thoughtfully choosing which subtree to traverse: the left or right. The extension is to choose the subtree which is closer to the ray, that is, based on the direction of the ray. This yields faster intersection times and better pruning.
Performance
As long as the tree is balanced, searching is conducted in O(log(n)) time. The image below uses a linear search algorithm to render with 20 SSP and a recursion depth of 20. The rendering ultimately required 13min and 24s of real time and 13min 3s of user time. However, using a BVH to render the same image only took 46s of real and user time. About a 12min difference! This allows for more meshes to exist in the scene without a drastic slowdown.
Marble Solid Texture
Noise
Noise is a texture of random values. Noise is used in many applications to generate natural looking terrain, behavior, and textures. One of the easiest forms of noise to implement is white noise. White noise can be generated by obtaining random values and converting the values to colors. Below is an example of white noise.
Perlin Noise
Perlin noise was invented by Ken Perlin in 1983. Perlin noise generates random noise whose neighboring points vary slightly. This yields a blurred, splotchy effect. The method in which Perlin accomplished this was to divide white noise into a lattice structure. At every intersection of the lattice, a vector with random direction would be generated. For every point between four vectors, the color is determined by interpolating between the vector directions. Perlin noise has since been used extensively throughout computer graphics. Below is an example of each.
Turbulence
Turbulence is a method for distoring an image to create more natural looking textures. Turbulence is the sum of multiple frequencies of the same image. Frequency refers to how splotchy an image is. Adding turbulence to our Perlin noise function yields the image below.
Marble
Finally, we run the distored Perlin noise through a sin() function. After tweaking the values in the sin() function, we obtain a marble like effect.
Final Results
- Scene with 35,000 polygons rendered with 100 SSP and 50 depth in real time: 61min 32s, user time: 60min 4s
- Colored marble rendered with 100 SSP 50 depth in real: 1min 7s and user: 1min 6s
- Marble Man rendered with 500 SSP and 100 depth in real: 8min 21s and user: 8min 20s
