Acceleration Data Structures for Ray Tracing Today Review & Schedule



Yüklə 2,21 Mb.
tarix07.11.2018
ölçüsü2,21 Mb.
#78510


Acceleration Data Structures for Ray Tracing


Today



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

  • multiple rays per pixel



Reflection

  • one reflection ray per intersection



Glossy Reflection

  • multiple reflection rays



Motion Blur

  • Sample objects temporally



Depth of Field

  • multiple rays per pixel



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 Sphere



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)



For each cell along a ray

  • 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?



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



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)

  • Bounding boxes for primitives

  • 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:

  • Curves & Surfaces



Yüklə 2,21 Mb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©www.genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə