Acceleration Data Structures for Ray TracingLast Time:ScheduleTodayShadowsShadows & Light SourcesSoft ShadowsAntialiasing – SupersamplingReflectionGlossy ReflectionMotion BlurDepth of FieldRay Tracing Algorithm AnalysisQuestions?Slide 15Acceleration 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 26Slide 27Slide 28Regular GridCreate GridInsert Primitives into GridFor Each Cell Along a RayPreventing Repeated ComputationDon't Return Distant IntersectionsWhich Cells Should We Examine?Where Do We Start?Is there a Pattern to Cell Crossings?What's the Next Cell?What's the Next Cell?Pseudo-CodeRegular Grid DiscussionA Note about TyposSlide 43Slide 44Adaptive GridsPrimitives in an Adaptive GridAdaptive Grid DiscussionSlide 48Bounding Volume HierarchySlide 50Slide 51Slide 52Slide 53Where to split objects?Intersection with BVHSlide 56Bounding Volume Hierarchy DiscussionSlide 58Transformation HierarchyAssignments 5 & 6Ray Marching VisualizationNext Time:MIT EECS 6.837, Durand and CutlerAcceleration Data Structures for Ray TracingMIT EECS 6.837, Durand and CutlerLast Time:•Graphics Pipeline!!•Clipping •Line & PolygonRasterization–Bresenham (DDA)•Visibility–Depth Buffer(z-buffer)Modeling TransformationsIllumination(Shading)Viewing Transformation(Perspective / Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility / DisplayMIT EECS 6.837, Durand and CutlerSchedule•Wed Oct 13thAssignment 4 due(Shadows, Reflection, & Refraction)•Wed Oct 20th Assignment 5 due(Voxel Rendering)•Review Session for Quiz 1 –Monday 25th, 7:30 – 9pm, room TBA•Tuesday October 26th, in class: Quiz 1MIT EECS 6.837, Durand and CutlerToday•Motivation – Distribution Ray Tracing–Soft shadows–Antialiasing (getting rid of jaggies)–Glossy reflection–Motion blur–Depth of field (focus)•Bounding Boxes•Spatial Acceleration Data Structures •Flattening the Transformation HierarchyMIT EECS 6.837, Durand and CutlerShadows•one shadow ray per intersection per point light sourceno shadow raysone shadow rayMIT EECS 6.837, Durand and CutlerShadows & Light Sourceshttp://www.pa.uky.edu/~sciworks/light/preview/bulb2.htmclear bulb frosted bulbhttp://3media.initialized.org/photos/2000-10-18/index_gall.htmhttp://www.davidfay.com/index.phpMIT 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 CutlerRay Tracing 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 * size of recursive ray tree * num shadow rays * num supersamples * num glossy rays * num temporal samples * num focal samples * . . .can we reduce this?MIT EECS 6.837, Durand and CutlerQuestions?MIT EECS 6.837, Durand and CutlerToday•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 2, 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, ymin, zmin)= (min(x'0,x'1,x'2),
View Full Document
Unlocking...