|
Acceleration Data Structures for Ray Tracing Today Review & Schedule
|
tarix | 07.11.2018 | ölçüsü | 2,21 Mb. | | #78510 |
|
Today Bounding Boxes Spatial Acceleration Data Structures Flattening the transformation hierarchy
Cool results from Assignment 2
Last Week: Ray Tracing - Shadows
- Reflection
- Refraction
Local Illumination - Bidirectional Reflectance Distribution Function (BRDF)
- Phong Model
Schedule 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) due
Questions?
Today Review & Schedule Motivation – Distribution Ray Tracing Bounding Boxes Spatial Acceleration Data Structures Flattening the transformation hierarchy
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)
Shadows one shadow ray per intersection per point light source
Soft Shadows
Antialiasing – Supersampling
Reflection one reflection ray per intersection
Glossy Reflection
Motion Blur Sample objects temporally
Depth of Field
Algorithm Analysis Ray casting Lots of primitives Recursive Distributed Ray Tracing Effects - Soft shadows
- Anti-aliasing
- Glossy reflection
- Motion blur
- Depth of field
Questions?
Today Review & Schedule Motivation – Distribution Ray Tracing Bounding Boxes - of each primitive
- of groups
- of transformed primitives
Spatial Acceleration Data Structures Flattening the transformation hierarchy
Acceleration of Ray Casting Goal: Reduce the number of ray/primitive intersections
Conservative Bounding Region First check for an intersection with a conservative bounding region Early reject
Conservative Bounding Regions
Intersection with Axis-Aligned Box From Lecture 3, Ray Casting II
Bounding Box of a Triangle
Bounding Box of a Plane
Bounding Box of a Group
Bounding Box of a Transform
Special Case: Transformed Triangle
Special Case: Transformed Triangle
Questions?
Today Review & Schedule Motivation – Distribution Ray Tracing Bounding Boxes Spatial Acceleration Data Structures - Regular Grid
- Adaptive Grids
- Hierarchical Bounding Volumes
Flattening the transformation hierarchy
Regular Grid
Create grid Find bounding box of scene Choose grid spacing gridx need not = gridy
Insert primitives into grid Primitives that overlap multiple cells? Insert into multiple cells (use pointers)
Does the cell contain an intersection? Yes: return closest intersection No: continue
Preventing repeated computation Perform the computation once, "mark" the object Don't re-intersect marked objects
Don't return distant intersections If intersection t is not within the cell range, continue (there may be something closer)
Where do we start? Intersect ray with scene bounding box Ray origin may be inside the scene bounding box
Is there a pattern to cell crossings? Yes, the horizontal and vertical crossings have regular spacing
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
What's the next cell? 3DDDA – Three Dimensional Digital Difference Analyzer
Pseudo-code create grid insert primitives into grid for each ray r find initial cell c(i,j), tmin, tnext_v & tnext_h compute dtv, dth, signx and signy while c != NULL for each primitive p in c intersect r with p if intersection in range found return c = find next cell
Regular Grid Discussion Advantages? - easy to construct
- easy to traverse
Disadvantages? - may be only sparsely filled
- geometry may still be clumped
Questions?
Today Review & Schedule Motivation – Distribution Ray Tracing Bounding Boxes Spatial Acceleration Data Structures - Regular Grid
- Adaptive Grids
- Hierarchical Bounding Volumes
Flattening the transformation hierarchy
Adaptive Grids
Primitives in an Adaptive Grid Can live at intermediate levels, or be pushed to lowest level of grid
Adaptive Grid Discussion Advantages? - grid complexity matches geometric density
Disadvantages? - more expensive to traverse (especially octree)
Bounding Volume Hierarchy Find bounding box of objects Recurse
Bounding Volume Hierarchy Find bounding box of objects Split objects into two groups Recurse
Bounding Volume Hierarchy Find bounding box of objects Split objects into two groups Recurse
Bounding Volume Hierarchy Find bounding box of objects Split objects into two groups Recurse
Bounding Volume Hierarchy Find bounding box of objects Split objects into two groups Recurse
Where to split objects? At midpoint OR Sort, and put half of the objects on each side OR Use modeling hierarchy
Intersection with BVH
Intersection with BVH Don't return intersection immediately if the other subvolume may have a closer intersection
Bounding Volume Hierarchy Discussion 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
Today Review & Schedule Motivation – Distribution Ray Tracing Bounding Boxes Spatial Acceleration Data Structures Flattening the transformation hierarchy
Transformation Hierarchy Group & Transformation hierarchy may not be a good spatial hierarchy
Questions?
Assignment 4 (due Oct 15th) 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)
Next Time:
Dostları ilə paylaş: |
|
|