Ray tracing with KD-Tree from scratch
First contact with c++. First contact with computer graphics (CG).
It’s funny, but every project has a bit difficulty behind, but it’s never presented as it should be. Even because the focus of a presentation is on the final results (of course).
So, the goal with this post isn’t to show techniques and codes [you can check here], but instead, pass some project context, development process, the last seconds of the suffer and happiness (I want to keep this text format approach).
For code lovers ~ https://github.com/arthurflor23/ray-tracing.
In 2015, I was in graduation and had only known Pascal and C programming languages. I didn’t even know about Github.
Well, the computer graphics class had a new teacher with a different approach. Nothing of projects using Blender. Yep, that year it was the time to develop our own ray tracing.
But.. what the f*ck is a ray tracing!?
Formally, Wikipedia [here] says:
A ray tracing is a rendering technique for generating an image by tracing the path of light as pixels in an image plane and simulating the effects of its encounters with virtual objects.
I would rather say that is something complicated, involving a lot of math, CPU processing, more math, data structure and a lot of patience to finish a simple project that will put a blue ball in the center of the image.
The first challenge, for real, was to learn object-oriented programming and c++ (wow!). So, our adventure begins. The first task that we did were read a config file, with coordinates of the objects in the 3D space (starting with a simple circle) and put it in the center of an image (a) with 800x600.
The next tasks, and getting more difficult, it was to append lights (b), shadows (c) and triangles (d). Behind this, more math added and for each point of light, pixel-by-pixel:
- Check if the light collides with a circle (math);
- Check if the light collides with a triangle (math);
- Check if the shadow propagate in other objects (more math);
- The lights aren’t ended? repeat the loop with another light.
CPU processing has also increased considerably. If the script initially took less than 5 seconds (a), at the end of this, it took about 1 minute (d). Remember, the code hasn’t data structure yet and there are only 5 objects in the scene with 2 points of light.
Now we can go on and be sad when the script loads a cow object file with 8,708 objects in the scene (300x150) and take some like 45 minutes to put in the image.
Get sadder when the script loads a dragon object file with 30,181 objects in the scene (1100x300) and take some like 7 hours to put in the image.
And get more and sadder when the script loads a Batman object file with 41,792 objects in the scene (600x800) and take some like 12 hours to put in the image.
It was really frustrating to put the script to run the night and only the next day to see if the output image was right or not.
KD-Tree Data Structure
So, the last task in the project was to structure all the code with a KD-Tree. And man, was really hard until understanding the concept and put all the objects following the logic.
Basically, the objects were distributed in a binary tree, wherein each node represents a division of position in the axis of the time (alternating between the axes x, y, and z) until it reaches the leaves (with a stop condition).
The pixel-by-pixel process mentioned above was reduced drastically, because instead of checking the light collision on all objects, the code would now traverse the KD-Tree (guided by the position of the pixel to be tested) and return the 10 objects from the leaf (I can’t remember if the stop condition was actually with 10 objects, but anyway).
Then we went from a test of thousands of objects per pixel to 10.
The process that took 12 hours, now takes a maximum of 10 minutes. The rest you already know.
In the end, of course, some results
Finally, thank you who started reading the post and especially who got here ~ haha.
These projects are personal learning that I have developed in recent years and that I consider them interesting. Unfortunately, at the end of the development cycle, they end up forgotten in Github.
So I intend to create the habit of posting them here in a non-technical and relaxed way. See you in the next post.
References
- Amy Williams, Steve Barrus, R. Keith Morley & Peter Shirley (2005) An Efficient and Robust Ray-Box Intersection Algorithm, Journal of Graphics Tools, 10:1,49–54, DOI: 10.1080/2151237X.2005.10129188
- I. Wald and V. Havran, “On building fast KD-Trees for Ray Tracing, and on doing that in O(N log N),” 2006 IEEE Symposium on Interactive Ray Tracing, Salt Lake City, UT, 2006, pp. 61–69.
doi: 10.1109/RT.2006.280216 - Hapala, M. and Havran, V. (2011), Review: Kd‐tree Traversal Algorithms for Ray Tracing. Computer Graphics Forum, 30: 199–213. doi:10.1111/j.1467–8659.2010.01844.x
- Wald, I., Purcell, T.J., Schmittler, J., Benthin, C., & Slusallek, P. (2004). Real-time Ray Tracing and its use for Interactive Global Illumination.
