Transcript PPT

Ray Tracing
Acceleration (2)
Ray Tracing Acceleration Techniques
Spatial Index Structures
Too Slow!
Faster intersection
N
Uniform grids
Spatial hierarchies
•K-D
•Octtree
•BSP
Hierarchical grids
Hierarchical
bounding
volumes (HBV)
Fewer rays
Generalized rays
1
Tighter bounds
Faster intersector
Early ray
termination
Adaptive sampling
Beam tracing
Cone tracing
Pencil tracing
Spatial Data Structures
• Create a data structure aware of the spatial
relations
– Partition space and place objects within subregions
– Only consider subregions that the ray passes through
– Avoid computing intersections twice if object lies
inside multiple subregions
Roadmap
(LRT book, ch 4 – Intersection Acceleration)
• Approaches To Reducing Intersections
–
–
–
–
–
–
Ray-Box Intersections
Regular Grid
Hierarchical bounding volumes
BSP trees and friends
Meta-Hierarchies
Refinements to basic approaches
• Hierarchical Grid Accelerator
– Creation
– Traversal
• Kd Tree
– Tree Representation
– Tree construction
– Traversal
• Further Reading
Uniform (Regular) Grids
One of the simplest and implemented in lrt.
Construction steps:
1. Compute bounding box (bbox) of the scene
2. Divide bbox into grids of certain resolution,
which is often determined by: n3 = d|O|
– Where d is a constant (in lrt it’s 8) and |O| is the
number of objects.
3. Place objects into cells by:
– Calculating bbox of each object,
– For each overlapped cell, put a pointer to the object
in cell structure.
Uniform (Regular) Grid
Uniform (Regular) Grids
One of the simplest and implemented in lrt.
Construction steps:
1. Compute bounding box (bbox) of the scene
2. Divide bbox into grids of certain resolution,
which is often determined by: n3 = d|O|
– Where d is a constant (in lrt it’s 8) and |O| is the
number of objects.
3. Place objects into cells by:
– Calculating bbox of each object,
– For each overlapped cell, put a pointer to the object
in cell structure.
Create grid
• Find
bounding
box of scene
Cell (i, j)
• Choose grid
spacing
• gridx = gridy
gridy
gridx
Uniform (Regular) Grids
One of the simplest and implemented in lrt.
Construction steps:
1. Compute bounding box (bbox) of the scene
2. Divide bbox into grids of certain resolution,
which is often determined by: n3 = d|O|
– Where d is a constant (in lrt it’s 8) and |O| is the
number of objects.
3. Place objects into cells by:
– Calculating bbox of each object,
– For each overlapped cell, put a pointer to the object
in cell structure.
Insert primitives into grid
• Primitives
that overlap
multiple
cells?
• Insert into
multiple cells
(use
pointers)
Uniform (Regular) Grids
•
Once the uniform grid is built up, ray-object
intersection is detected by running a
traversal algorithm.
•
It’s similar to 3D DDA
(Digital Differential Analyzer)
Uniform (Regular) Grids :
Traversal Algorithm: INITIALIZATION
At ray origin (X, Y ), compute:
•
Next ray intersection with
–
–
•
horizontal edge nextx and
vertical edge nexty (both are values of t);
Distances along the ray between horizontal crossings
deltax and vertical crossings deltay,
Uniform (Regular) Grids : Traversal Algorithm:
Incremental traversal by running the following loop:
Uniform (Regular) Grids : Traversal Algorithm:
Incremental traversal by running the following loop:
Notice that stepping for X and Y
might be +1 or -1,
depending on which direction
the line goes.
Uniform (Regular) Grids :
Traversal Algorithm
Be careful when implementing this algorithm!
•
•
Make sure the intersection is inside the current grid
The same ray-object intersection might be computed
multiple times
•
One solution is to use ”mailbox” to record the intersection
between a specific ray and an object
(not always effective)
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
Where do we start?
Cell (i, j)
• Intersect ray
with scene
bounding box
• Ray origin
may be inside
the scene
bounding box
tnext_v
tmin
tnext_h
tnext_v
tmin tnext_h
Is there a pattern to cell
crossings?
• Yes, the
horizontal
and vertical
crossings
have regular
spacing
(dirx, diry)
dtv = gridy / diry
gridy
dth = gridx / dirx
gridx
What's the next cell?
Cell (i+1, j)
if tnext_v < tnext_h
i += signx
tmin = tnext_v
tnext_v += dtv
else
j += signy
tmin = tnext_h
tnext_h += dth
Cell (i, j)
tnext_h
tnext_v
tmin
(dirx, diry)
dth
if (dirx > 0) signx = 1 else signx = -1
if (diry > 0) signy = 1 else signy = -1
dtv
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
Grids
• Grid
– Partitioning with equal, fixed sized
“voxels”
• Building a grid structure
– Partition the bounding box (bb)
– Resolution: often n3 = d|O|
– Inserting objects
• Trivial: insert into all voxels
overlapping objects bounding box
• Easily optimized
• Traversal
– Iterate through all voxels in order
as pierced by the ray
– Compute intersection with objects
in each voxel
– Stop if intersection found in current
voxel
Uniform Grids (another example)
Uniform Grids
Preprocess scene
1. Find bounding box
Uniform Grids
Preprocess scene
1. Find bounding box
2. Determine grid resolution
Uniform Grids
Preprocess scene
1. Find bounding box
2. Determine grid resolution
3. Place object in cell if its
bounding box overlaps
the cell
Uniform Grids
Preprocess scene
1. Find bounding box
2. Determine grid resolution
3. Place object in cell if its
bounding box overlaps the
cell
4. Check that object overlaps
cell (expensive!)
Uniform Grids
Preprocess scene
Traverse grid
3D line = 3D-DDA
6-connected line
Caveat: Overlap
Optimize objects that overlap multiple cells
Caveat 1 (correctness):
• Intersection must lie within current cell
Caveat 2 (efficiency):
• Redundant intersection tests
• “Mailboxes”
– Assign each ray a number
– Object intersection cache (“mailbox”)
• Store ray number, intersection information
Uniform (Regular) Grid Discussion
• Advantages?
– easy to construct
– easy to traverse
• Disadvantages?
– may be only sparsely filled
– geometry may still be clumped
Grid Issues  Traversal
• Requires enumeration of voxel along ray
3D-DDA
• Simple and hardware-friendly
Grid Issues  Resolution
• Strongly scene dependent
• Cannot adapt to local density of objects
– Problem: “Bunny in a stadium”
• Sparse scenes, for example, a very complicated
bunny model put at the center of a huge stadium.
Grid Issues  Resolution
• Strongly scene dependent
• Cannot adapt to local density of objects
– Problem: “Bunny in a stadium”
• Sparse scenes, for example, a very complicated
bunny model put at the center of a huge stadium.
• Possible solution: grids within grids –
hierarchical grids (later)
Grid Issues  Objects in multiple voxels
• Store only references
• Use mailboxing to avoid multiple
intersection computations
– Store (ray, object)-tuple in small cache (e.g.
with hashing)
– Do not intersect if found in cache
• Original mailbox uses ray-id stored with
each triangle
– Simple, but likely to destroy CPU caches