Ray Tracing: Homework 2

 In this homework, I could not finish on the time to submit a meaningful output, unfortunately. I will still submit the latest working snapshot of my ray tracer project, however, the snapshot I will upload does not handle the transformations.

However small it is, I can explain my work since the submission of homework 1 till today in a couple of paragraphs and some screenshots.

From the last homework, there were some issues in the lighting: The algorithm I used were precalculating the ambient and background lighting, and then not using those when computing the mirror and dielectric lighting. This resulted in pretty dark dielectric and mirror images. I started by fixing this issue. I also fixed another issue which caused the specular lighting to be on a wrong location. The issue was because of a non-normalized sum of w_i and w_o vectors, which was resulting in a weighted normalized average of them. You can see below that the right one waas the desired image, where my result was as on the left.

After I fixed these issues, I worked my way into creating a Box class. Then I made a recursive intersection function of it to make the calculations more intuitive. After that, I enabled multithreading to be able to see the images while they are generated.

I defined a Box as a center Vector and a dimensions Vector. Boxes were axis aligned, so these 2 parameters were enough to define a box. The dimensions component is the distance of x,y,z faces of the box to the center.

Then I started to think about the intersection function of the box. The initial intersection test between a box and a ray is just a yes/no question, I realized. We'd not need a location of intersection. I kept this in my mind to think about optimizing the intersection tests. I knew that my code probably has a lot of horrible bottlenecks before such kind of implementation reduces the computation time effectively, however, I think the main purpose of these homeworks are learning advanced concepts rather than optimizing some random C++ code.

After I realized about the possible optimization of calculating intersections, another idea came to my mind: Since the boxes were only for optimizing the scene, the ray-box intersections may be done using integers rather than floats to even make the code quicker. This'd have some difficulties, though. We'd need to make sure that the precision loss of the integer calculations lay on the safe side rather than misleading the program into some cancelled intersections. I decided to apply this if I finish the homework and still have time, and report the results.

After that, I tried to calculate every box as a sphere whose center is the same as the box and whose radius is the length of the dimensions vector of the box. I believed that even packing the objects in the scene into these really inefficient abstract spheres'd make the calculations quicker. The reason I thought this was because the intersection of a ray and a sphere is actually easier to compute if we are not interested in the intersection points. We can define a vector from the ray origin to the sphere's origin first. We then only need to calculate whether the angle between this new ray and the original ray is small enough for the ray to hit the sphere. After I implemented this in a nested fashion and tested the program (After debugging some mistakes.), I was a little startled to see that the program is actually slower. Then I wanted to see why and realized that some boxes were really thin and abstractly converting them into spheres were making extremely redundant calculations, killing the initial reason of boxes.

After realizing that, I made some edits to the code and improved the recursive boxing system. Then started to think about a way to mathematically utilize the lack of need for exact intersection points. (I strongly admit and realize that I have really went off track there.) Then I came up with the idea of projection. That is, a ray actually represents a point in any plane it is perpendicular to. And it intersects with objects only if the object's projection onto any such plane includes the ray's projection (a point). However, projecting a box onto a plane is easier thought than done. Especially if it is represented by such a minimal (actually, close to minimal) data: centre and half-length-per-axis (dimensions). I intuitively concluded that the box's real projection onto any such plane can exactly be represented by 4 vectors: a central vector and 3 shape vectors. The shape vectors are projections of the dimension vector and its 2 variants where different axes of it are inverted. However, this results in on average 12 triangles. And the efficient computation of the ray-projection's preposition becomes non-trivial. Since I have not got this time, I decided to make a 2 dimensional bounding box of the projection to further reduce the complexity. Then I rendered the scene. The results were... They were unexpected, but speed was increased, non-doubtfully:

This is a render-time screenshot of the initial results of this solution. The unrendered lines showcase multithreading. In this image, every triangle is enboxed, and that is all.

After some debugging, I realized I was computing the 2d bounding box with a logical error, so I re-rendered the scene and the intermediate result was like this:

The results were better, however the problem was not resolved. So, I decided to increase the margin of the 2d bounding box:

It was almost the same. Seems like the error is probably not about the error margin.

I was so determined to solve this bug, however, at that point I realized that I did not have even a quarter of the enough time to apply this fantasy. So I switched back to the classic solution to calculate the box-intersections. The result was now as expected:

The scene was rendered in a way that each triangle had its own box. The time to render that was more than the time to render the boxless scene:

Now I tried more layers of the boxes, where for each step below, the boxes in the global scope are binarily grouped into newer boxes, so that there is a tree structure:

In the last one, the limit of the depth was reached as I let the program do the layering until there is a single global box. However, the time to render is actually increased this way. I guess it has something to do with my implementation where each box holds pointers to other objects (other boxes, triangles or spheres). Thus, I decided to change the structure of the scene and let each box have its own container for objects, so that the memory accesses are more contiguous. The results were better:

This was the result of the algorithm that enboxed each mesh and put that box into the global scope. So only 4 boxes here are tested in each iteration of the loop. After that, I further subdivided the meshes into boxes and made this recursively:

I did not want to start the transformations before gaining such a performance. I thought that I'd be able to at least implement one or 2 types of transformations. However, I was not able to write a functional parser to parse them all, so I had to upload this homework without implementing any transformations.

Conclusion

In this homework, I was unable to even start transformations and I still am unable to read the .ply files. It might be said that I implemented a custom acceleration structure: random recursive boxing. I plan to implement the missing stuff in the next weeks together with the next homework's tasks. I also am excited to see how do the projection and integerization techniques of mine affect the rendering time after I implemented the transformations and tried the complex scenes with millions of triangles. I plan to use heuristics to further reduce the computation time of box intersections where boxes are closer to cubes. In that case, I plan to implement a efficient integer-based sphere-intersection algorithm. I plan to develop a smart algorithm where the intersections are computed differently in different cases to speed up the overall process.

My plans also include creating a binary encoding system for our scenes. In that case parsing the scenes'd be a easy task and even the future homeworks can be given with this custom encoding and a special parser for that.