**Unformatted text preview:**

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,

View Full Document