In this assignment and the next, you will make your ray tracer faster using a spatial-acceleration data structure. This week we will focus on the implementation of a grid data structure and on fast ray grid intersection. Next week you will use the grid to accelerate your ray tracer.
To test your grid structure, you will implement the grid as a modeling primitive. Volumetric modeling can be implemented by affecting a binary opaqueness value for each grid cell. This is the equivalent of the discrete pixel representation of 2D images. Each volume element (or voxel) will be rendered as a solid cube. You can easily rasterize simple primitives in a grid (similar to pixel rasterization). For example, to rasterize a sphere, simply compare the distance between the center of a voxel and the sphere center to the sphere radius. You will use the grid to store the objects of your scene. In order to test your object insertion code, you will render cells that contain one or more objects as opaque and use color to visualize the density.
Initially, you may assume that no transformations are used. This way you may effectively ignore the group hierarchy and insert all primitives by scanning the scene in a depth-first manner. For the later test cases you will need to correctly transform the bounding boxes of each primitive before rasterizing it to the grid.
To avoid creating an infinite bounding box, don't try to compute the bounding box of a Plane (the BoundingBox of this primitive should be NULL). Don't include this infinite primitive when computing the bounding box of a group. Test your bounding box code by printing out the intermediate and scene bounding boxes for various test cases from previous assignments. Make sure your code handles scenes whose bounding box does not include the origin.
Grid::Grid(BoundingBox *bb, int nx, int ny, int nz);
Internal to your grid class, an array of nx x ny x nz boolean values stores whether each voxel is opaque or transparent. Later we'll replace this array of booleans with an array of arrays of Objects3D.
virtual void insertIntoGrid(Grid *g, Matrix *m);
Note that this function is not pure virtual. Initially this function will do nothing. Override this function for spheres by implementing the corresponding method for the Sphere class. This method sets the opaqueness of each voxel which may intersect the sphere. You can do this by comparing the center of voxel to the sphere center and radius. Your computation should be conservative: you must label cells which might overlap the sphere, but it's also ok to label cells opaque which do not overlap the sphere. You may ignore the 2nd argument (Matrix *m) for this part, it will be used later in the assignment.
You will need a place to store the information for the current ray and the current grid cell. Implement a MarchingInfo class that stores the current value of tmin; the grid indices i, j, and k for the current grid cell; the next values of intersection along each axis (t_next_x, t_next_y, and t_next_z); the marching increments along each axis (d_tx, d_ty, d_tz), and the sign of the direction vector components (sign_x, sign_y, and sign_z). To render the occupied grid cells for visualization you will also need to store the surface normal of the cell face which was crossed to enter the current cell. Write the appropriate accessors and modifiers.
void Grid::initializeRayMarch(MarchingInfo &mi, const Ray &r, float tmin) const;
This function computes the marching increments and the information for the first cell traversed by the ray. Make sure to treat all three intersection cases: when the origin is inside the grid, when it is outside and the ray hits the grid, and when it is outside and it misses the grid. Test your initializeRayMarch routine by manually casting simple axis-aligned rays into a low-resolution grid. Also test more general cases. Make sure to test ray origins which are inside and outside the scene bounding box. Next, implement:
This update routine choose the smallest of the next t values (t_next_x, t_next_y, and t_next_z), and updates the corresponding cell index. Test your nextCell ray marching code using the same strategy as for initialization. Manually compute the marching sequence corresponding to a particular ray and then print the steps taken by your code. Try other origins and directions to make sure that your code works for all orientations (in particular, test both positive and negative components of the direction).
GLCanvas::initialize method has been modified to take in two additional parameters, the Grid, and a boolean indicating whether to visualize the grid or not. Insert the following commands within your Grid intersection routines as appropriate:
void RayTree::AddHitCellFace(Vec3f a, Vec3f b, Vec3f c, Vec3f d, Vec3f normal, Material *m); void RayTree::AddEnteredFace(Vec3f a, Vec3f b, Vec3f c, Vec3f d, Vec3f normal, Material *m);
To specify an entire cell, call AddHitCellFace 6 times. In the examples below, a color gradient has been used to show the order in which the cells are traversed (white, purple, ... orange, red). This gradient is optional, but can be helpful in debugging. To see the ray intersections more clearly, you may wish to turn off the transparent ray rendering in RayTree::paint()
In the examples below, a color gradient has been used to visualize the number of primitives which overlap each grid cell. Cells colored white have just 1 primitive, purple have 2 primitives, ... and cells colored red have many more. You should implement a similar visualization, but you may use a different color scheme.
You are not required to handle transformations in your Sphere::insertIntoGrid method. If m ≠ NULL, it's ok to fall back on the Object3D::insertIntoGrid implementation. To explicitly call a parent class method, pre-pend the method with the class name:
NOTE: We won't test or grade your transformation code until the next assignment, so it's ok if this isn't fully implemented or debugged yet. But we highly recommend that you try to do so now. Test scenes 10, 11, & 12 contain transformations.
raytracer -input scene5_01_sphere.txt -size 200 200 -output output5_01a.tga -gui -grid 1 1 1 -visualize_grid raytracer -input scene5_01_sphere.txt -size 200 200 -output output5_01b.tga -gui -grid 5 5 5 -visualize_grid raytracer -input scene5_01_sphere.txt -size 200 200 -output output5_01c.tga -gui -grid 15 15 15 -visualize_grid
raytracer -input scene5_02_spheres.txt -size 200 200 -output output5_02a.tga -gui -grid 15 15 15 -visualize_grid raytracer -input scene5_02_spheres.txt -size 200 200 -output output5_02b.tga -gui -grid 15 15 3 -visualize_grid
raytracer -input scene5_02_spheres.txt -size 200 200 -gui -grid 8 8 8 -visualize_grid
raytracer -input scene5_03_offcenter_spheres.txt -size 200 200 -output output5_03.tga -gui -grid 20 20 20 -visualize_grid
raytracer -input scene5_04_plane_test.txt -size 200 200 -gui -tessellation 30 15 -gouraud raytracer -input scene5_04_plane_test.txt -size 200 200 -output output5_04.tga -gui -grid 15 15 15 -visualize_grid
raytracer -input scene5_05_sphere_triangles.txt -size 200 200 -gui -tessellation 30 15 -gouraud raytracer -input scene5_05_sphere_triangles.txt -size 200 200 -output output5_05.tga -gui -grid 20 20 10 -visualize_grid
raytracer -input scene5_06_bunny_mesh_200.txt -size 200 200 -output output5_06.tga -gui -grid 10 10 7 -visualize_grid raytracer -input scene5_07_bunny_mesh_1k.txt -size 200 200 -output output5_07.tga -gui -grid 15 15 12 -visualize_grid raytracer -input scene5_08_bunny_mesh_5k.txt -size 200 200 -output output5_08.tga -gui -grid 20 20 15 -visualize_grid raytracer -input scene5_09_bunny_mesh_40k.txt -size 200 200 -output output5_09.tga -gui -grid 40 40 33 -visualize_grid
raytracer -input scene5_10_scale_translate.txt -size 200 200 -gui -tessellation 30 15 -gouraud raytracer -input scene5_10_scale_translate.txt -size 200 200 -output output5_10.tga -gui -grid 15 15 15 -visualize_grid
raytracer -input scene5_11_rotated_triangles.txt -size 200 200 -gui raytracer -input scene5_11_rotated_triangles.txt -size 200 200 -output output5_11.tga -gui -grid 15 15 9 -visualize_gridNote: the grid voxelization of the green triangle uses an optional special case for transformed triangles and will look different if you have not implemented this option.
raytracer -input scene5_12_nested_transformations.txt -size 200 200 -gui raytracer -input scene5_12_nested_transformations.txt -size 200 200 -output output5_12.tga -gui -grid 30 30 30 -visualize_gridNote: the grid voxelization of the blue rhombus uses an optional special case for transformed triangles and will look different if you have not implemented this option.
See the main Assignments Page for submission information.