Note
This is a very tricky issue to get right, because we have to make sure that the BVH Nodes are as lightweight as possible, and also make sure that the BVH construction is as fast and accurate as possible. Otherwise, for smaller scenes, the BVH construction time contributes more to the program runtime than the actual rendering algorithm runtime.
Currently, the rendering algorithm in Rendera checks if a given ray intersects with any object sequentially. This is fundamentally an $O(n)$ algorithm.
Can we do better? The answer is yes! If we partition the space inside the scene and organize it into a bounding volume hierarchy, then we can make the algorithm run in $O(\log n)$ time.
However, like I mentioned in the note, there are many competing factors here, so the actual implementation is quite tricky: one false step and we will introduce an unnecessary slowdown.
What to do
- Read up on the theory. The Wikipedia page is a great place to start. Reading Chapter 19 of Ray Tracing from the Ground Up is also highly recommended. Other than that, reading Chapters 4 and 6 in Real-Time Collision Detection by Christer Ericson would help too.
- Implement a lightweight struct which will hold the relevant bounding volume data. I recommend starting off by implementing AABBs (Axis-Aligned Bounding Boxes), as their implementation is very straightforward.
- Implement a BVH class which takes in a Scene object and creates a tree out of that. For now, a binary tree is good. In future, we can experiment with k-d trees.
a. In the context of ray tracing, the SAH (surface area heuristic) is a cheap and easy way of figuring out how to split each BVH node into smaller nodes.
Assignee: @prateekgargX and @mahesh0537
Currently, the rendering algorithm in Rendera checks if a given ray intersects with any object sequentially. This is fundamentally an$O(n)$ algorithm.
Can we do better? The answer is yes! If we partition the space inside the scene and organize it into a bounding volume hierarchy, then we can make the algorithm run in$O(\log n)$ time.
However, like I mentioned in the note, there are many competing factors here, so the actual implementation is quite tricky: one false step and we will introduce an unnecessary slowdown.
What to do
a. In the context of ray tracing, the SAH (surface area heuristic) is a cheap and easy way of figuring out how to split each BVH node into smaller nodes.
Assignee: @prateekgargX and @mahesh0537