HW1

CSE 168 HW1, no doubt as mentioned in the email, is the hardest programing assignment I have ever done in UCSD. If I have not started during the spring break, I don't think I would be able to finish it. This is probably the most physics based assignment I have ever done.
The part that took the longest for me is the acceleration structure. I will talk about the general implementation of my nxnxn grid.

The x and y coordinate represents the array indices of the grid

First of all, the grid itself is considered as a bounding box with a vec3 min and vec3 max. The min and max are determined by the min coordinate of all objects in the scene. In the 2D example above, I have triangle a and sphere b. They both have their bounding boxes.

The bounding box of triangle is calculate using the minimum and maximum of three vertices coordinates. 

The bounding box of sphere is required the the radius after transformation. For ellipsoid, however, the scaling factor is not uniform across all coordinates. Hence I take the greatest scaling factor among the three coordinates. In the case above, sphere b originally has radius r. After transformation, the radius in x direction (forgive me if this is not the right term) is 3r. Using this scaled radius and transformed center, I can calculate the bounding box (which is always a square). There are probably much better and efficient way, however, this way I don't have to worry about any rotation applied.

Since sphere b has the greatest min and triangle a has the greatest max among the objects, the grid min is b.min and grid max is a.max. With the grid min and max, I can calculate the cell size of the grid, which is simply (grid.max-grid.min)/grid_dimension.

To insert them in the object, I simply transform the object min and max to grid coordinates, and do a box box intersection. The disadvantage of box box intersection is that, for the example above, if a ray traverse at grid[3][3], the cell would include the triangle a even though none of its edges are in the cell. In the beginning, I was trying to do box triangle intersection. However, in scene 7, there are thousands of triangles in each of the nxnxn cell, which means the difference between box box and box triangle intersection would not make much difference.

Finally, to use the ray, first determine if the ray hit the grid. Since we have the grid min and max, we can do a ray box intersection. If it doesn't hit the grid, terminate. Otherwise, calculate where the ray grid coordinate after the ray intersected with the grid. Then use 3D DDA algorithm to traverse through the grid. In each grid cell, check if the ray intersect with the objects inside the grid cell, use a hash set to prevent redundant checking.

Below is a table that has the execution time of scene 7 with respect to different grid dimension. I am extremely impressed by the results as with no acceleration structure, it took almost 30 min for me to render scene 7. With dimension more than 200, the overhead seems to cause more time than the ray intersection and the time is actually longer than grid dimension of 200. With the increases of the dimension, however, the memory cost also increases.

Grid dimension	Seconds
5	386
10	109
20	33
30	17
40	11
50	9
100	4.8
200	4.19
300	5.41