MIT EECS 6.837, Durand and Cutler Acceleration Data Structures for Ray TracingMIT EECS 6.837, Durand and Cutler Today•Review & Schedule•Motivation –Distribution Ray Tracing•Bounding Boxes•Spatial Acceleration Data Structures•Flattening the transformation hierarchyMIT EECS 6.837, Durand and Cutler Last Week:•Ray Tracing–Shadows–Reflection–Refraction•Local Illumination–Bidirectional Reflectance Distribution Function (BRDF)–PhongModelθiθrφiφrMIT EECS 6.837, Durand and Cutler Schedule•Wednesday October 1st:Assignment 3 (Ray Tracing & PhongMaterials) due•Sunday October 5th, 5-7 PM,Review Session for Quiz 1•Tuesday October 7th:Quiz 1: In class•Wednesday October 15th:Assignment 4 (Grid Acceleration) dueMIT EECS 6.837, Durand and Cutler Questions?MIT EECS 6.837, Durand and Cutler Today•Review & Schedule•Motivation –Distribution Ray Tracing•Bounding Boxes•Spatial Acceleration Data Structures•Flattening the transformation hierarchyMIT EECS 6.837, Durand and Cutler Extra rays needed for these effects:•Distribution Ray Tracing–Soft shadows–Anti-aliasing (getting rid of jaggies)–Glossy reflection–Motion blur–Depth of field (focus)MIT EECS 6.837, Durand and Cutler Shadows•one shadow ray per intersection per point light sourceno shadow raysone shadow rayMIT EECS 6.837, Durand and Cutler Soft Shadows•multiple shadow rays to sample area light sourceone shadow raylots of shadow raysMIT EECS 6.837, Durand and Cutler Antialiasing–Supersampling•multiple rays per pixelpoint lightarea lightjaggiesw/antialiasingMIT EECS 6.837, Durand and Cutler Reflection•one reflection ray per intersectionperfect mirrorθθMIT EECS 6.837, Durand and Cutler Glossy Reflection•multiple reflection rayspolished surfaceθθ Courtesy of Justin Legakis. Used with permission.MIT EECS 6.837, Durand and Cutler Motion Blur•Sample objects temporally Image removed due to copyright considerations.MIT EECS 6.837, Durand and Cutler Depth of Field•multiple rays per pixelfocal lengthfilm Courtesy of Justin Legakis. Used with permission.MIT EECS 6.837, Durand and Cutler Algorithm Analysis•Ray casting•Lots of primitives•Recursive•Distributed Ray Tracing Effects–Soft shadows–Anti-aliasing–Glossy reflection–Motion blur–Depth of fieldcost ≤ height * width * num primitives * intersection cost * num shadow rays *supersampling*num glossy rays * num temporal samples *max recursion depth *. . .can we reduce this?MIT EECS 6.837, Durand and Cutler Questions?MIT EECS 6.837, Durand and Cutler Today•Review & Schedule•Motivation –Distribution Ray Tracing•Bounding Boxes–of each primitive–of groups–of transformed primitives•Spatial Acceleration Data Structures•Flattening the transformation hierarchyMIT EECS 6.837, Durand and Cutler Acceleration of Ray Casting•Goal: Reduce the number of ray/primitive intersectionsMIT EECS 6.837, Durand and Cutler Conservative Bounding Region•First check for an intersection with a conservative bounding region•Early rejectMIT EECS 6.837, Durand and Cutler Conservative Bounding Regionsaxis-aligned bounding boxnon-aligned bounding boxbounding spherearbitrary convex region (bounding half-spaces)•tight →avoidfalse positives•fast to intersectMIT EECS 6.837, Durand and Cutler Intersection with Axis-Aligned BoxFrom Lecture 3, Ray Casting II•For all 3 axes, calculate the intersection distances t1and t2•tnear= max (t1x, t1y, t1z)tfar= min (t2x, t2y, t2z)•If tnear> tfar, box is missed•If tfar< tmin, box is behind•If box survived tests, report intersection at tneary=Y2y=Y1x=X1x=X2tneartfart1xt1yt2xt2yMIT EECS 6.837, Durand and Cutler Bounding Box of a Triangle(xmax, ymax, zmax)(xmin, ymin, zmin)(x0, y0, z0)(x1, y1, z1)(x2, y2, z2)= (max(x0,x1,x2),max(y0,y1,y2),max(z0,z1,z2))= (min(x0,x1,x2), min(y0,y1,y2),min(z0,z1,z2))MIT EECS 6.837, Durand and Cutler Bounding Box of a Sphere(xmax, ymax, zmax)r(x, y, z)= (x+r, y+r, z+r)(xmin, ymin, zmin)= (x-r, y-r, z-r)MIT EECS 6.837, Durand and Cutler Bounding Box of a Plane(xmax, ymax, zmax)= (+∞, +∞, +∞)*n = (a, b, c)ax + by + cz= d(xmin, ymin, zmin)= (-∞, -∞, -∞)** unless n is exactly perpendicular to an axisMIT EECS 6.837, Durand and Cutler Bounding Box of a Group(xmax, ymax, zmax)(xmin_b, ymin_b, zmin_b)(xmin_a, ymin_a, zmin_a)(xmax_b, ymax_b, zmax_b)(xmax_a, ymax_a, zmax_a)= (max(xmax_a,xmax_b), max(ymax_a,ymax_b),max(zmax_a,zmax_b))(xmin, ymin, zmin)= (min(xmin_a,xmin_b), min(ymin_a,ymin_b),min(zmin_a,zmin_b))MIT EECS 6.837, Durand and Cutler Bounding Box of a Transform(x'max, y'max, z'max)(x'min, y'min, z'min)= (min(x0,x1,x2,x3,x4,x5,x6,x7), min(y0,y1,y2,y3,y4,x5,x6,x7),min(z0,z1,z2,z3,z4,x5,x6,x7))M(xmin, ymin, zmin)(x0,y0,z0) = M (xmin,ymin,zmin)= (max(x0,x1,x2,x3,x4,x5,x6,x7), max(y0,y1,y2,y3,y4,x5,x6,x7),max(z0,z1,z2,z3,z4,x5,x6,x7))(x1,y1,z1) = M (xmax,ymin,zmin)(x2,y2,z2) = M (xmin,ymax,zmin)(x3,y3,z3) = M (xmax,ymax,zmin)(xmax, ymax, zmax)MIT EECS 6.837, Durand and Cutler Special Case: Transformed TriangleCan we do better?MMIT EECS 6.837, Durand and Cutler Special Case: Transformed Triangle(xmax, ymax, zmax)= (max(x'0,x'1,x'2),max(y'0,y'1,y'2),max(z'0,z'1,z'2))M(xmin, ymin, zmin)= (min(x'0,x'1,x'2), min(y'0,y'1,y'2),min(z'0,z'1,z'2))(x'0,y'0,z'0) = M (x0,y0,z0)(x'1,y'1,z'1) = M (x1,y1,z1)(x'2,y'2,z'2) = M (x2,y2,z2)(x2, y2, z2)(x1, y1, z1)(x0, y0, z0)MIT EECS 6.837, Durand and Cutler Questions?MIT EECS 6.837, Durand and Cutler Today•Review & Schedule•Motivation –Distribution Ray Tracing•Bounding Boxes•Spatial Acceleration Data Structures–Regular Grid–Adaptive Grids–Hierarchical Bounding Volumes•Flattening the transformation hierarchyMIT EECS 6.837, Durand and Cutler Regular GridMIT EECS 6.837, Durand and Cutler Create grid•Find bounding box of scene•Choose grid spacing•gridxneed not = gridyCell (i, j)gridygridxMIT EECS 6.837, Durand and Cutler Insert primitives into grid•Primitives that overlap multiple cells?•Insert into multiple cells (use pointers)MIT EECS 6.837, Durand and Cutler For each cell along a ray •Does the cell contain an intersection?•Yes: return closestintersection•No: continueMIT EECS 6.837, Durand and Cutler Preventing repeated computation•Perform the computation once, "mark" the object •Don't re-intersect marked objectsMIT EECS 6.837, Durand and Cutler Don't return distant intersections•If intersection t is not within the cell range, continue (there may be something closer)MIT EECS 6.837, Durand and Cutler Where do we start?•Intersect ray with scene bounding box•Ray origin may be insidethe scene bounding boxtmintnext_vtnext_htmintnext_vtnext_hCell (i, j)MIT EECS 6.837, Durand and Cutler Is there a pattern to cell crossings?•Yes, the horizontal and vertical crossings have regular spacingdtv= gridy/dirydth= gridx/dirxgridygridx(dirx, diry)MIT EECS 6.837, Durand and Cutler What's the next cell?if tnext_v< tnext_hi += signxtmin= tnext_vtnext_v+= dtvelsej += signytmin= tnext_htnext_h+= dthCell (i+1, j)Cell (i, j)dtvdthtmintnext_vtnext_h(dirx, diry)if (dirx> 0) signx= 1 else signx= -1if (diry> 0) signy= 1 else signy= -1MIT EECS 6.837, Durand and Cutler What's the next cell? •3DDDA –Three Dimensional Digital Difference Analyzer•We'll see this again later, for line rasterizationMIT EECS 6.837, Durand and Cutler Pseudo-codecreate grid insert primitives into gridfor each ray rfind initial cell c(i,j), tmin, tnext_v& tnext_hcompute dtv, dth, signxand signywhile c!= NULLfor each primitive pin cintersect rwith pif intersection in range foundreturnc= find next cellMIT EECS 6.837, Durand and Cutler Regular Grid Discussion•Advantages?–easy to construct–easy to traverse•Disadvantages?–may be only sparsely filled–geometry may still be clumpedMIT EECS 6.837, Durand and Cutler Questions?MIT EECS 6.837, Durand and Cutler Today•Review & Schedule•Motivation –Distribution Ray Tracing•Bounding Boxes•Spatial Acceleration Data Structures–Regular Grid–Adaptive Grids–Hierarchical Bounding Volumes•Flattening the transformation hierarchyMIT EECS 6.837, Durand and Cutler Adaptive GridsNested GridsOctree/(Quadtree)•Subdivide until each cell contains no more than nelements, or maximum depth d is reachedMIT EECS 6.837, Durand and Cutler Primitives in an Adaptive Grid•Can live at intermediate levels, orbe pushed to lowest level of gridOctree/(Quadtree)MIT EECS 6.837, Durand and Cutler Adaptive Grid Discussion•Advantages?–grid complexity matches geometric density•Disadvantages?–more expensive to traverse (especially octree)MIT EECS 6.837, Durand and Cutler Bounding Volume Hierarchy•Find bounding box of objects•Split objects into two groups•RecurseMIT EECS 6.837, Durand and Cutler Bounding Volume Hierarchy•Find bounding box of objects•Split objects into two groups•RecurseMIT EECS 6.837, Durand and Cutler Bounding Volume Hierarchy•Find bounding box of objects•Split objects into two groups•RecurseMIT EECS 6.837, Durand and Cutler Bounding Volume Hierarchy•Find bounding box of objects•Split objects into two groups•RecurseMIT EECS 6.837, Durand and Cutler Bounding Volume Hierarchy•Find bounding box of objects•Split objects into two groups•RecurseMIT EECS 6.837, Durand and Cutler Where to split objects?•At midpoint OR•Sort, and put half of the objects on each side OR•Use modeling hierarchyMIT EECS 6.837, Durand and Cutler Intersection with BVH•Check subvolumewith closer intersection firstMIT EECS 6.837, Durand and Cutler Intersection with BVH•Don't return intersection immediately if the other subvolumemay have a closer intersectionBounding Volume Hierarchy Discussion MIT EECS 6.837, Durand and Cutler •Advantages–easy to construct–easy to traverse–binary•Disadvantages–may be difficult to choose a good split for a node–poor split may result in minimal spatial pruning MIT EECS 6.837, Durand and Cutler Today•Review & Schedule•Motivation –Distribution Ray Tracing•Bounding Boxes•Spatial Acceleration Data Structures•Flattening the transformation hierarchyMIT EECS 6.837, Durand and Cutler Transformation Hierarchy•Group & Transformation hierarchy may not be a good spatial hierarchygroupgrouptransformtransformtransformtransformACDEtransformBgrouptransformA BtransformC DtransformC EFlattenMIT EECS 6.837, Durand and Cutler Questions?MIT EECS 6.837, Durand and Cutler Assignment 4 (due Oct 15th)•Bounding boxes for primitives•Regular grid acceleration data structure •Flatten the transformation hierarchy•Collect statistics–Average # of rays per pixel–Average # of ray/primitive intersections per pixel•Extra Credit: Distribution Ray Tracing (and anything else from past weeks)MIT EECS 6.837, Durand and Cutler Next Time:Curves & Surfaces