6.837 Introduction to Computer GraphicsAssignment 4: Grid AccelerationDue Wednesday October 15, 2003 at 11:59pmThis week, you will make your ray tracer faster using a spatial-accelerationdata structure. You will implement grid acceleration, using fast ray marching.To convince yourself of the efficiency of your acceleration, you will analyze a setof statistics about your computation.In order to test your grid structure before using it for acceleration, youwill implement the grid as a modeling primitive. Volumetric modeling can beimplemented by affecting a binary opaqueness value for each grid cell. This isthe equivalent of the discrete pixel representation of 2D images. Each volumeelement (or voxel) will be rendered as a solid cube. You can very easily rasterizesimple primitives in a grid; for example, to rasterize a sphere, simply test thedistance between the center of a voxel and the sphere center.After your grid modeling primitive is implemented and debugged, you willuse it for acceleration. As a preprocess, you will insert all scene objects in thecells of the grid that they span. In order to test your object insertion code, youwill render cells that contain one more more objects as opaque.Then, you will modify your ray tracer to use the grid for fast ray casting.You will use your ray marching code and intersect all the objects stored ineach traversed cell. You must pay attention to intersections outside the cell andimplement early rejection to stop marching when you have found an appropriateintersection.For this assignment, you may assume that no transformations are used. Thisway you may effectively ignore the group hierarchy and insert all primitives byscanning the scene in a depth-first manner.1 Ray Tracing StatisticsUse the provided RayTracingStats class to compute various statistics includingthe number of pixels, the number of rays cast, the number of ray/primitiveintersections, the number of cells in the grid, the number of grid cells traversedwith the ray marching technique, and the total running time. Add the followingtiming and counter increment functions provided in the RayTracerStatisticsclass to your code:1• Call RayTracingStats::Initialize(int width, int height,int num_x, int num_y, int num_z,const Vec3f &min, const Vec3f &max)before beginning computation,• Call RayTracingStats::IncrementNumNonShadowRays()for each non-shadow ray (a call to RayTracer::TraceRay()),• Call RayTracingStats::IncrementNumShadowRays()for each shadow ray,• Call RayTracingStats::IncrementCellsTraversed()for each cell traversed (a call to MarchingInfo::nextCell()),• Call RayTracingStats::IncrementNumIntersections()for each ray/primitive intersection (not groups and transforms), and• At the end of your main loop, print the various statistics by callingRayTracingStats::PrintStatistics().From these numbers we can compute the average number of rays per pixel,intersections per ray, grid cells per ray, rays per second, etc. Verify that thestatistics are reasonable for simple test scenes. To verify that the number of rayscast is correct, add a -no_shadows command line argument to your program.Test this part of the assignment with examples from last week.2 GridDerive from Object3D a Grid class for an axis-aligned uniform grid. Initiallya Grid will simply store whether each cell (voxel) is occupied so it can berendered opaque or transparent. The constructor takes two Vec3fs describingthe minimum and maximum coordinates of the grid, three integers describingthe number of cells along the three axes, and a Material*.Grid::Grid(Vec3f min, Vec3f max,int nx, int ny, int nz, Material *m);An array of nx × ny × nz bools stores whether each voxel is opaque or transpar-ent. Implement the Grid::rasterizeSphere(Vec3f center, float radius)method that sets the opaqueness of each voxel by testing whether its center isinside the sphere described by center and radius.Test your sphere-rasterization routine on a small grid (e.g., 4x4) by printingthe values of the array.23 Fast Ray Marching with 3DDDATo implement fast ray marching using 3DDDA, you will need a place to storethe information for the current ray and the current grid cell. Implement aMarchingInfo class that stores the current value of tmin; the grid indices i, jand k for the current grid cell; the next values of intersection along each axis(tnext_x, tnext_y, and tnext_z); the marching increments along the three axes(dtx, dty, dtz), and signx, signy, and signz. To render the occupied grid cellsfor visualization you will also need to store the surface normal of the cell facewhich was crossed to enter the current grid. Write the appropriate accessorsand modifiers.The intersection of a ray with a Grid will use two helpers to initialize themarch and to move to the next cell.3.1 InitializationFirst write:void Grid::initializeRayMarch(MarchingInfo &mi,const Ray &r, float tmin) const;This function sets the increments and the information relative to the first celltraversed by the ray. Make sure to treat all three intersection cases: when theorigin is inside the grid, when it is outside and the ray hits the grid, and whenit is outside and it misses the grid.Test your routine with a very simple grid, for example a 4x4 grid from (-2,-2,-2) to (2,2,2). Use simple rays for which you can manually test the result.For example, initialize the cell march for a ray with origin (0.5, 0.5, 0.5), or fora ray with origin (-2.5, 0.5,0.5) and direction (1, 0, 0). Also test more generalcases.3.2 Marching stepNext, implement:void MarchingInfo::nextCell();This update routine choose the smallest of the next t values (tnext_x, tnext_y,and tnext_z), and updates the corresponding cell index.Test your ray marching code using the same strategy as for initialization.For example, use a ray with origin (-3, -2, 0.5) and directions such as (5, 2,0). Note that the problem reduces to a 2D grid because the z component is 0.Manually compute the marching sequence, and print the steps taken by yourcode. Try other origins and directions to make sure that your code works for allorientations (in particular, test both positive and negative components of thedirection).33.3 Putting it all togetherFinally, use these two helpers in your main grid-ray intersection routine. If thenew cell is opaque, return the appropriate normal depending on which axis youadvanced last. Test cases to visualize a simple sphere rasterization on your gridare provided.4 Reducing the Number of IntersectionsIn order to
View Full Document
Unlocking...