Acceleration Data Structures for Ray TracingTodayCool results from Assignment 2Last Week:ScheduleQuestions?Slide 7Extra rays needed for these effects:ShadowsSoft ShadowsAntialiasing – SupersamplingReflectionGlossy ReflectionMotion BlurDepth of FieldAlgorithm AnalysisSlide 17Slide 18Acceleration of Ray CastingConservative Bounding RegionConservative Bounding RegionsIntersection with Axis-Aligned BoxBounding Box of a TriangleBounding Box of a SphereBounding Box of a PlaneBounding Box of a GroupBounding Box of a TransformSpecial Case: Transformed TriangleSlide 29Slide 30Slide 31Regular GridCreate gridInsert primitives into gridFor each cell along a rayPreventing repeated computationDon't return distant intersectionsWhere do we start?Is there a pattern to cell crossings?What's the next cell?What's the next cell?Pseudo-codeRegular Grid DiscussionSlide 44Slide 45Adaptive GridsPrimitives in an Adaptive GridAdaptive Grid DiscussionBounding Volume HierarchySlide 50Slide 51Slide 52Slide 53Where to split objects?Intersection with BVHSlide 56Bounding Volume Hierarchy DiscussionSlide 58Transformation HierarchySlide 60Assignment 4 (due Oct 15th)Next Time:MIT EECS 6.837, Durand and CutlerAcceleration Data Structures for Ray TracingMIT EECS 6.837, Durand and CutlerToday•Review & Schedule•Motivation – Distribution Ray Tracing•Bounding Boxes•Spatial Acceleration Data Structures•Flattening the transformation hierarchyMIT EECS 6.837, Durand and CutlerCool results from Assignment 2koiseantekMIT EECS 6.837, Durand and CutlerLast Week:•Ray Tracing–Shadows–Reflection–Refraction•Local Illumination–Bidirectional Reflectance Distribution Function (BRDF)–Phong ModelirirMIT EECS 6.837, Durand and CutlerSchedule•Wednesday October 1st:Assignment 3 (Ray Tracing & Phong Materials) due•Sunday October 5th, 5-7 PM, Room TBA: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 CutlerQuestions?MIT EECS 6.837, Durand and CutlerToday•Review & Schedule•Motivation – Distribution Ray Tracing•Bounding Boxes•Spatial Acceleration Data Structures •Flattening the transformation hierarchyMIT EECS 6.837, Durand and CutlerExtra 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 CutlerShadows•one shadow ray per intersection per point light sourceno shadow raysone shadow rayMIT EECS 6.837, Durand and CutlerSoft Shadows•multiple shadow rays to sample area light sourceone shadow raylots of shadow raysMIT EECS 6.837, Durand and CutlerAntialiasing – Supersampling•multiple rays per pixelpoint lightarea lightjaggies w/ antialiasingMIT EECS 6.837, Durand and Cutler•one reflection ray per intersectionperfect mirrorReflectionθθMIT EECS 6.837, Durand and CutlerGlossy Reflection•multiple reflection rayspolished surfaceθθJustin LegakisMIT EECS 6.837, Durand and CutlerMotion Blur•Sample objects temporallyRob CookMIT EECS 6.837, Durand and CutlerDepth of Field•multiple rays per pixelJustin Legakisfocal lengthfilmMIT EECS 6.837, Durand and CutlerAlgorithm 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 CutlerQuestions?MIT EECS 6.837, Durand and CutlerToday•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 CutlerAcceleration of Ray Casting•Goal: Reduce the number of ray/primitive intersectionsMIT EECS 6.837, Durand and CutlerConservative Bounding Region•First check for an intersection with a conservative bounding region•Early rejectMIT EECS 6.837, Durand and CutlerConservative Bounding Regionsaxis-aligned bounding boxnon-aligned bounding boxbounding spherearbitrary convex region (bounding half-spaces)• tight → avoid false positives• fast to intersectMIT EECS 6.837, Durand and CutlerIntersection with Axis-Aligned BoxFrom Lecture 3, Ray Casting II•For all 3 axes, calculate the intersection distances t1 and 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 CutlerBounding Box of a Triangle(xmin, ymin, zmin)(xmax, ymax, zmax)(x0, y0, z0)(x1, y1, z1)(x2, y2, z2)= (min(x0,x1,x2), min(y0,y1,y2), min(z0,z1,z2))= (max(x0,x1,x2), max(y0,y1,y2), max(z0,z1,z2))MIT EECS 6.837, Durand and CutlerBounding Box of a Spherer(xmin, ymin, zmin)(xmax, ymax, zmax)(x, y, z)= (x-r, y-r, z-r)= (x+r, y+r, z+r)MIT EECS 6.837, Durand and CutlerBounding Box of a Plane(xmin, ymin, zmin)(xmax, ymax, zmax)= (-∞, -∞, -∞)*= (+∞, +∞, +∞)*n = (a, b, c)ax + by + cz = d* unless n is exactly perpendicular to an axisMIT EECS 6.837, Durand and CutlerBounding Box of a Group(xmin_b, ymin_b, zmin_b)(xmin, ymin, zmin)(xmax, ymax, zmax)= (min(xmin_a,xmin_b), min(ymin_a,ymin_b), min(zmin_a,zmin_b))= (max(xmax_a,xmax_b), max(ymax_a,ymax_b), max(zmax_a,zmax_b))(xmin_a, ymin_a, zmin_a)(xmax_b, ymax_b, zmax_b)(xmax_a, ymax_a, zmax_a)MIT EECS 6.837, Durand and CutlerBounding Box of a Transform(x'min, y'min, z'min)(x'max, y'max, z'max)= (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 CutlerSpecial Case: Transformed TriangleMCan we do better?MIT EECS 6.837, Durand and CutlerSpecial 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,
View Full Document
Unlocking...