Ray Tracing 2: AccelerationRay Tracing Acceleration TechniquesUniform GridsSlide 4Slide 5Slide 6Slide 7Caveat: OverlapSpatial HierarchiesSlide 10VariationsCreating Spatial HierarchiesMedian-CutSurface Area and RaysSlide 15Ray Traversal AlgorithmsHierarchical GridsHierarchical Bounding VolumesComparisonCS 445Greg Humphreys, Spring 2003Ray Tracing 2:AccelerationGreg Humphreys, Spring 2003Intro Graphics Raytracing StufRay Tracing Acceleration TechniquesToo Slow!Uniform gridsSpatial hierarchies•K-D•Octtree•BSPHierarchical gridsHierarchical bounding volumes (HBV)Tighter boundsFaster intersectorEarly ray terminationAdaptive samplingBeam tracingCone tracingPencil tracingFaster intersectionN 1Fewer rays Generalized raysGreg Humphreys, Spring 2003Intro Graphics Raytracing StufUniform GridsPreprocess scene1. Find bounding boxGreg Humphreys, Spring 2003Intro Graphics Raytracing StufUniform GridsPreprocess scene1. Find bounding box2. Determine grid resolution3| |n d O=Greg Humphreys, Spring 2003Intro Graphics Raytracing StufUniform GridsPreprocess scene1. Find bounding box2. Determine grid resolution3. Place object in cell if its bounding box overlaps the cell3| |n d O=Greg Humphreys, Spring 2003Intro Graphics Raytracing StufUniform GridsPreprocess scene1. Find bounding box2. Determine grid resolution3. Place object in cell if its bounding box overlaps the cell4. Check that object overlaps cell (expensive!)3| |n d O=Greg Humphreys, Spring 2003Intro Graphics Raytracing StufUniform GridsPreprocess sceneTraverse grid3D line = 3D-DDA6-connected lineGreg Humphreys, Spring 2003Intro Graphics Raytracing StufCaveat: OverlapOptimize objects that overlap multiple cellsCaveat 1 (correctness):Intersection must lie within current cellCaveat 2 (eficiency):Redundant intersection tests“Mailboxes”Assign each ray a numberObject intersection cache (“mailbox”)•Store ray number, intersection informationGreg Humphreys, Spring 2003Intro Graphics Raytracing StufSpatial HierarchiesABCDABCDLeaf nodes correspond to unique regions in spaceGreg Humphreys, Spring 2003Intro Graphics Raytracing StufSpatial HierarchiesABCDABCDPoint location by recursive searchGreg Humphreys, Spring 2003Intro Graphics Raytracing StufVariationsKD treeocttree BSP treeGreg Humphreys, Spring 2003Intro Graphics Raytracing StufCreating Spatial Hierarchiesinsert(node,prim) {if( overlap(node->bound,prim) )if( leaf(node) ) {if( node->nprims > MAXPRIMS && node->depth < MAXDEPTH ) {subdivide(node);foreach child in nodeinsert(child,prim)}else list_insert(node->prims,prim);}elseforeach child in nodeinsert(child,prim)}// Typically MAXDEPTH=16, MAXPRIMS=2-8Greg Humphreys, Spring 2003Intro Graphics Raytracing StufMedian-CutBuild hierarchy bottom-upChose direction and position carefullySurface-area heuristicGreg Humphreys, Spring 2003Intro Graphics Raytracing StufSurface Area and RaysNumber of rays in a given direction that hit an object is proportional to its projected areaThe total number of rays hitting an object is Crofton’s theorem:For a convex body: Example: SphereprojA4 Ap4SA =2 24 S r A rp p= =Greg Humphreys, Spring 2003Intro Graphics Raytracing StufSurface Area and RaysProbability of a ray hitting an object that is completely inside a cell is:cSoS[ ]ProcSr OS� =Greg Humphreys, Spring 2003Intro Graphics Raytracing StufRay Traversal AlgorithmsRecursive inorder traversalKaplan, Arvo, Jansenmintmaxt*t*maxt t<Intersect(L,tmin,tmax)mintmaxt*t*min maxt t t< <Intersect(L,tmin,t*)Intersect(R,t*,tmax)maxtmint*t*mint t<Intersect(R,tmin,tmax)Greg Humphreys, Spring 2003Intro Graphics Raytracing StufHierarchical GridsGood compromise preferred by many practitionersIMAGEIMAGEIMAGEGreg Humphreys, Spring 2003Intro Graphics Raytracing StufHierarchical Bounding VolumesCreate tree of bounding volumesChildren are contained within parentCreation preprocessFrom model hierarchyAutomatic clusteringSearchintersect(node,ray,hits) {if( intersectp(node->bound,ray)if( leaf(node) )intersect(node->prims,ray,hits)elsefor each childinter sect(child,ray,hits)}Greg Humphreys, Spring 2003Intro Graphics Raytracing StufComparisonScheme SpheresRingsTreeUniform grid D=1 244 129 1517D=2038 83 781Hierarchical grid34 116 34Vlastimil Havran, Best Efficiency Scheme
View Full Document