Transcript PPT

Ray Tracing
Acceleration (3)
Ray Tracing Acceleration Techniques
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
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
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
Spatial Decompositions:
• Focus on spatial data structures that
partition space into regions, or cells, of
some type
– Generally, cut up space with planes that
separate regions
– Always based on tree structures
Tree-structure Hierarchy: Variations
KD tree
Quadtree (2D)
Octree (3D)
BSP tree
Spatial Decompositions:
Tree-structure Hierarchy
• Kd-trees: Axis aligned planes, in
alternating directions, cut space into
rectilinear regions
Spatial Decompositions:
Tree-structure Hierarchy
• Octrees (Quadtrees): Axis aligned,
regularly spaced planes cut space
into cubes (squares)
Spatial Decompositions:
Tree-structure Hierarchy
• BSP Trees: Arbitrarily aligned
planes cut space into convex
regions
Creating Spatial Hierarchies
insert(node,prim) {
if( overlap(node->bound,prim) )
if( leaf(node) ) {
if( node->nprims > MAXPRIMS &&
node->depth < MAXDEPTH ) {
subdivide(node);
foreach child in node
insert(child,prim)
}
else list_insert(node->prims,prim);
}
else
foreach child in node
insert(child,prim)
}
// Typically MAXDEPTH=16, MAXPRIMS=2-8
K-d trees
(K-dimensional)
2-D tree
K-d trees
• An axis-aligned plane is introduced to break down
each volume into two sub-volumes.
• The subdivision stops when the number of objects
overlapping a cell falls below a certain threshold.
• As in uniform grid, objects must be assigned to
cells.
A
A
Leaf nodes correspond to unique regions in space
A
B
A
Leaf nodes correspond to unique regions in space
A
B
B
A
Leaf nodes correspond to unique regions in space
A
C
B
B
A
A
C
B
C
B
A
A
C
D
B
C
B
A
A
C
D
B
C
B
D
A
K-d tree (Spatial Hierarchies)
A
D
B
B
C
C
D
A
Leaf nodes correspond to unique regions in space
Kd-tree Example
4
6
1
10
8
2
11
3
13
2
4
12
5
8
9
5
1
3
7
9
6
10
7
11
12
13
Heuristics on where to put the
partitioning plane
• Median-cut: .find the plane that puts
approximately equal number of objects at
each side.
Heuristics on where to put the partitioning plane:
Median-Cut
• Find the plane that puts approximately equal number of
objects at each side.
• Build hierarchy bottom-up
• Chose direction and position carefully
• Surface-area heuristic
Heuristics on where to put the partitioning plane:
Surface Area and Rays
• The number of rays in a given direction
that hits the object is proportional to the
projected area A.
Heuristics on where to put the partitioning plane:
Surface Area and Rays
• And rays in all directions that
hits the object is proportional to
the surfaces area S.
• Crofton’s Theorem states that
•
is average projected area in
all directions.
Heuristics on where to put the partitioning plane:
Surface Area and Rays
Crofton’s theorem:
For a convex body: A 
S
4
Example: Sphere
S  4 r
2
A  r
2
Aproj
Heuristics on where to put the partitioning plane:
Surface Area and Rays
• Probability of a ray hitting an object that is
completely inside a cell is:
Sc
So
So
Pr  r  O  
Sc
K-d tree (Spatial Hierarchies)
A
D
B
B
C
C
D
A
Point location by recursive search
Search for 
A
C
D
B
C
B
D
A
Search for 
Left or Right of partition plane A?
A
C
D
B
C
B
D
A
Search for 
A
C
Left or Right
of partition
plane B?
D
B
C
B
D
A
Search for 
A
C
D
B
C
B
D
A
Left or
Right of
partition
plane C?
FOUND !
A
C
D
B
C
B
D
A
Point location by recursive search
Leaf nodes correspond to unique regions in space
Ray Traversal Algorithms
• tmin, tmax are near and far intersection points of
the ray with the current volume;
• t* is the intersection of ray with partitioning plane.
Ray Traversal Algorithms
Recursive inorder traversal
Kaplan, Arvo, Jansen
tmax
t*
tmax
tmax
t*
tmin
tmin
tmax  t *
tmin  t *  tmax
Intersect(L,tmin,tmax)
Intersect(L,tmin,t*)
Intersect(R,t*,tmax)
t * tmin
t *  tmin
Intersect(R,tmin,tmax)
Ray Traversal Algorithms
• The previous slide applies for ray going to the right.
• The dot product of ray direction with plane normal r · n tells
where the ray is going with respect to the plane.
3-d Trees (K-d Trees)
Tree-structure Hierarchy: Variations
•
•
•
Similarly, we can construct quadtree, octree, etc.
In BSP tree, the partitioning plane is not necessarily axis-aligned
As in uniform grid, objects must be assigned to cells
KD tree
Quadtree (2D)
Octree (3D)
BSP tree
Other Partitioning Structures
• Octree
– Ray can parse through large
empty areas
– Requires less space than grid
– Subdivision takes time
• Binary Space Partition
(BSP) Tree
– Planes can divide models
nearly in half
– Trees better balanced,
shallower
– Added ray-plane intersections
octree
Octrees
Octrees
BSP Example
1
1
2
2
A
3
4
out
5
7
3
6
A
C5B
out
B
6
C
8
out
D
out
out
• Notes:
D
4
8
7
– Splitting planes end when they
intersect their parent node’s planes
– Internal node labeled with planes,
leaf nodes with regions
BSP Example
BSP Trees
Ray Tracing BSP Trees