1!CS 431/636 !Advanced Rendering Techniques"Dr. David Breen"University Crossings 149"Tuesday 6PM → 8:50PM"Presentation 4"4/22/08"Questions from Last Week?" Color models" Light models" Phong shading model" Assignment 2"Slide Credits" Leonard McMillan, Seth Teller, Fredo Durand, Barb Cutler - MIT" David Luebke - University of Virginia" Matt Pharr - Stanford University" Jonathan Cohen - Johns Hopkins U." Kevin Suffern -University of Technology, Sydney, Australia!Motivation"Extra rays needed for these effects" Distributed Ray Tracing" Soft shadows" Anti-aliasing (getting rid of jaggies)" Glossy reflection" Motion blur" Depth of field (focus)"Shadows" one shadow ray per intersection per point light source"no shadow rays one shadow ray2!Soft Shadows" multiple shadow rays to sample area light source"one shadow ray lots of shadow rays Antialiasing – Supersampling" multiple rays per pixel"point light area light jaggies w/ antialiasing  one reflection ray per intersection"perfect mirror Reflection"θθGlossy Reflection" multiple reflection rays"polished surface θ θ Justin Legakis Motion Blur" Sample objects temporally"Rob Cook Depth of Field" multiple rays per pixel"Justin Legakis focal length film3!Algorithm Analysis" Ray casting" Lots of primitives" Recursive" Distributed Ray !Tracing Effects" Soft shadows" Anti-aliasing" Glossy reflection" Motion blur" Depth of field"cost ≤ height * width * num primitives * intersection cost * num shadow rays * supersampling * num glossy rays * num temporal samples * max recursion depth * . . . can we reduce this? Bounding Regions"Acceleration of Ray Casting" Goal: Reduce the number of ray/primitive intersection tests"Conservative Bounding Region" First check for an intersection with a conservative !bounding region" Early reject"Conservative Bounding Regions"bounding sphere axis-aligned bounding box arbitrary convex region (bounding half-spaces) non-aligned bounding box • tight → avoid false positives • fast to intersect4!Bounding Volumes" What makes a “good” bounding volume?" Tightness of fit (expressed how?)" Simplicity of intersection "! Total cost = b*B + i*I • b: # times volume tested for intersection"• B: cost of ray-volume intersection test"• i: # times item is tested for intersection"• I: cost of ray-item intersection test"Bounding Volumes" Spheres" Cheap intersection test" Poor fit " Somewhat expensive to fit to data"bounding sphere Bounding Volumes" Axis-aligned bounding boxes (AABBs)" Relatively cheap intersection test" Usually better fit" Trivial to fit to data"axis-aligned bounding box Bounding Volumes" Oriented bounding boxes (OBBs)" Medium-expensive intersection test" Very good fit (asymptotically better)" Medium-difficult to fit to data"oriented bounding box5!Bounding Volumes" Slabs (parallel planes)" Comparatively expensive" Very good fit" Very difficult to fit to data"arbitrary convex region (bounding half-spaces) Intersection with Axis-Aligned Box"From Lecture 2" 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< 0, !box is behind" If box survived tests, !report intersection at tnear!y=Y2 y=Y1 x=X1 x=X2 tnear tfar t1x t1y t2x t2y Bounding Box of a Triangle"(xmin, ymin, zmin) (x0, y0, z0) (x1, y1, z1) (x2, y2, z2) = (min(x0,x1,x2), min(y0,y1,y2), min(z0,z1,z2)) (xmax, ymax, zmax) = (max(x0,x1,x2), max(y0,y1,y2), max(z0,z1,z2)) Bounding Box of a Sphere"r (x, y, z) (xmin, ymin, zmin) = (x-r, y-r, z-r) (xmax, ymax, zmax) = (x+r, y+r, z+r) Bounding Box of a Group"(xmin, ymin, zmin) = (min(xmin_a,xmin_b), min(ymin_a,ymin_b), min(zmin_a,zmin_b)) (xmax, ymax, zmax) = (max(xmax_a,xmax_b), max(ymax_a,ymax_b), max(zmax_a,zmax_b)) (xmin_b, ymin_b, zmin_b) (xmin_a, ymin_a, zmin_a) (xmax_b, ymax_b, zmax_b) (xmax_a, ymax_a, zmax_a) Acceleration Spatial Data Structures"6!Spatial Data Structures" Spatial partitioning techniques classify all space into non-overlapping portions" Easier to generate automatically" Can “walk” ray from partition to partition" Hierarchical bounding volumes surround objects in the scene with (possibly overlapping) volumes" Often tightest fit"Spatial Partitioning" Some spatial partitioning schemes:" Regular grid (2-D or 3-D)" Octree" k-D tree" BSP-tree"Acceleration Spatial Data Structures"Regular Grid"Regular Grid"Create grid" Find bounding box of scene" Choose grid spacing" gridx need not = gridy"Cell (i, j) gridy gridx Insert primitives into grid" Primitives that overlap multiple cells?" Insert into !multiple cells (use pointers)"7! Does the cell contain an intersection?" Yes: return closest!intersection" No: continue"For each cell along a ray "Preventing repeated computation" Perform the computation once, "mark" !the object " Don't !re-intersect !marked !objects" If intersection t is not within the cell range, continue (there may be something closer)"Don't return distant intersections"Where do we start?" Intersect ray with scene bounding box" Ray origin may be inside the scene bounding box"tmin tnext_v tnext_h tmin tnext_v tnext_h Cell (i, j) Is there a pattern to cell crossings?" Yes, the horizontal and vertical crossings have regular spacing"dtv = gridy / diry dth = gridx / dirx gridy gridx (dirx, diry) What's the next cell?"if tnext_v < tnext_h ! i += signx! tmin = tnext_v! tnext_v += dtv!else! j += signy! tmin = tnext_h! tnext_h += dth!dtv dth Cell (i, j) tmin tnext_v tnext_h Cell (i+1, j) (dirx, diry) if (dirx > 0) signx = 1 else signx = -1 if (diry > 0) signy = 1 else signy = -18!What's the next cell? " 3DDDA – Three Dimensional Digital !Difference Analyzer" 3D Bresenham Algorithm"Pseudo-code"create grid insert primitives into grid for each ray r find initial cell c(i,j), tmin,