CSE190: Computer Graphics - Rendering AlgorithmsProgramming Assignment 2Due 11:59pm, Monday, May 19Henrik Wann JensenApril 30, 2003 (revised May 6, 2003)This assigment involves implementing two acceleration structures to the raytracer with the purpose of making it efficient in scenes with a large numberof triangles.For all tasks the three builtin scenes 1, 2 and 3 that are built by the Trianglesconstructor must be rendered using miro (or your own derivative renderer).Note that if you use your own renderer then you must make sure that the cam-era, the image resolution, the shading, and the sampling (1 sample throughthe center of each pixel) matches the implementation in miro.For reference here are the number of ray-triangle tests for the three scenesunaccelerated at a low resolution of 16x12.Scene Triangles Ray-triangle intersections1 69451 13,334,5922 69451 13,334,7843 1389021 266,692,032All the (accelerated) images should be rendered at 640x480 with 1 sampleper pixel.Percentages indicate percentage value for this assignment.This assignment requires reporting on results. Send a PDF fileor an ascii text file with the results, and send the source files (all.cpp, .h and makefile - not object files) as a packed .tar.gz file [email protected] before the deadline.Task 1: Implement and optimize a Bounding Box Hierarchy: 40 %This task can be divided into a set of smaller tasks:• Task 1a: Axis-aligned bounding box intersection test: 10 %Compute bounding box for all the triangles and add a fast slab basedintersection test to see if an incoming ray intersects the box.• Task 1b: Build the bounding box hierarchy: 10 %Build the hierarchy for the triangles in the triangles object. One possi-ble technique that can be used is building the hierarchy starting with1one bounding box per triangle and then merging near bounding boxes.Alternatively, the hierarchy can be built by splitting the triangles andcreating smaller bounding boxes in a top-down approach.• Task 1c: Intersect the hierarchy: 10 %Implement a heap-based method to intersect a ray with the hierarchysuch that boxes are processed in the order in which they are intersectedby the ray.• Task 1d: Optimize the hierarchy: 10 %Minimize the number of ray triangle and ray box intersections based ona cost function. Use the following cost: bounding box cost = 1, trianglecost = 4. Report the number of ray-triangle intersections (perhaps witha parameter study) and describe (briefly) the cost function that is beingused. Particularly clever implementations will receive extra credit.Task 2: Implement BSP tree acceleration: 60 %This task can be divided into a set of smaller tasks:• Task 2a: Triangle-Box intersection: 10 %Implement a function to test if a triangle overlaps with a given axis-aligned box.• Task 2b: BSP tree construction: 15 %Implement code to construct a BSP tree for a given number of trian-gles. The minimal set of parameters for the tree constructor should bemaximum depth and maximum number of objects per node. Use thetriangle-box intersection code from Task 1a.• Task 2c: Implement fast ray tracing of the BSP tree: 20 %Implement a ray traversal algorithm making it possible to trace raysthrough the BSP tree such that only triangles in the BSP nodes arechecked for intersection. Once the ray tracer is implemented make aparameter study (depth and max objects per node) to investigate whatcombination of parameters result in the lowest number of intersections.• Task 2d: BSP tree optimizations: 15 %Design and optimize a cost function that can be used to build an ef-ficient BSP tree with a minimal number of ray-triangle and ray-planeintersections. As a starting point use the following cost-estimate: planeintersection = 1, triangle cost = 8.This task should be solved by carefully picking the splitting dimensionx, y or z as well as the splitting plane position when building theBSP tree. Make a parameter study to investigate what combinationof parameters result in the lowest number of intersections. Reportthe number of ray-triangle intersections as a function of parameterssuch as depth, number of bsp nodes, and cost function parameters.Describe (briefly) the cost function that is being used. Particularlyclever implementations will receive extra
View Full Document
Unlocking...