Nima Kalantari

CSCE 441 - Computer Graphics

​

Ray Tracing (Acceleration)

Some slides from Ren Ng

Ray Tracing – Performance Challenges

• Simple ray-scene intersection
• Exhaustively test ray-intersection with every object
• Problem:
• Exhaustive = #pixels ⨉ #objects (triangles)
• Very slow!

Ray Tracing – Performance Challenges

San Miguel Scene, 10.7M triangles

Jun Yan, Tracy Renderer

Ray Tracing – Performance Challenges

Plant Ecosystem, 20M triangles

Deussen et al; Pharr & Humphreys, PBRT

Outline

• Bounding Volumes
• Uniform Spatial Subdivision
• Non-uniform Spatial Subdivision
• Bounding Volume Hierarchy (BVH)

​

​

Bounding Volumes

• Quick way to avoid intersections: bound complex object with a simple volume
• Object is fully contained in the volume
• If it doesn’t hit the volume, it doesn’t hit the object
• So test bounding volume first, then test object if it hits

Ray-Intersection With Box

• Could intersect with 6 faces individually
• Better way: box is the intersection of 3 slabs

Ray Intersection with Axis-Aligned Box

• 2D example; 3D is the same! Compute intersections with slabs and take intersection of t_min/t_max intervals

t_xmin

t_xmax

Intersections with x planes

How do we know when the ray misses the box?

Optimize Ray-Plane Intersection For Axis-Aligned Planes?

General

Perpendicular�to x-axis

Outline

• Bounding Volumes
• Uniform Spatial Subdivision
• Non-uniform Spatial Subdivision
• Bounding Volume Hierarchy (BVH)

​

​

Uniform Spatial Partitions (Grids)

Preprocess – Build Acceleration Grid

1. Find bounding box

Preprocess – Build Acceleration Grid

1. Find bounding box
2. Create grid

Preprocess – Build Acceleration Grid

1. Find bounding box
2. Create grid
3. Store each object�in overlapping cells

Ray-Scene Intersection

Step through grid in ray traversal order

For each grid cell test intersection with all objects stored at that cell

Grid Resolution?

One cell

• No speedup

Grid Resolution?

Too many cells

• Inefficiency due to extraneous grid traversal

Careful! Objects Overlapping Multiple Cells

What goes wrong here?

• First intersection found (red) is not the nearest!

Solution?

• Check intersection point is inside cell

Uniform Grids – When They Work Well

Deussen et al; Pharr & Humphreys, PBRT

Grids work well on large collections of objects�that are distributed evenly in size and space

Uniform Grids – When They Fail

Jun Yan, Tracy Renderer

“Teapot in a stadium” problem

Outline

• Bounding Volumes
• Uniform Spatial Subdivision
• Non-uniform Spatial Subdivision
• Bounding Volume Hierarchy (BVH)

​

​

Spatial Hierarchies

A

A

Spatial Hierarchies

A

A

B

Spatial Hierarchies

A

B

C

D

1

2

3

4

5

A

Spatial Partitioning Variants

BSP-Tree

KD-Tree Pre-Processing

• Find bounding box
• Recursively split cells, axis-aligned planes
• Until termination criteria met
• Store obj references with each leaf node

KD-Tree Pre-Processing

4

5

D

3

2

C

A

B

C

D

1

B

A

Root

Internal Nodes

Leaf Nodes

Only leaf nodes store �references to geometry

1

2

3

4

5

KD-Tree Pre-Processing

• Choosing the set partition
• Simple #1: Split objects around spatial midpoint
• Simple #2: Split at location of median object

​

• Termination criteria?
• Simple: stop when node contains few elements (e.g. 5)

Spatial Split (KD-Tree)

Spatial Midpoint

Spatial Split (KD-Tree)

Median Object

Top-Down Recursive In-Order Traversal

4

5

D

3

2

C

A

B

C

D

1

B

A

Top-Down Recursive In-Order Traversal

4

5

D

3

2

C

A

B

C

1

B

A

Internal node: split

D

Top-Down Recursive In-Order Traversal

4

5

D

3

2

C

B

C

1

B

A

Leaf node: intersect�all objects

D

A

Top-Down Recursive In-Order Traversal

4

5

D

3

2

C

B

C

1

B

A

Internal node: split

D

A

Top-Down Recursive In-Order Traversal

4

5

D

3

2

C

B

C

1

B

A

Leaf node: intersect�all objects

D

A

Top-Down Recursive In-Order Traversal

4

5

D

3

2

C

B

C

1

B

A

Internal node: split

D

A

Top-Down Recursive In-Order Traversal

4

5

D

3

2

C

B

C

1

B

A

A

Leaf node: intersect�all objects

D

Top-Down Recursive In-Order Traversal

4

5

D

3

2

C

B

C

D

1

B

A

Intersection found

A

Outline

• Bounding Volumes
• Uniform Spatial Subdivision
• Non-uniform Spatial Subdivision
• Bounding Volume Hierarchy (BVH)

​

​

Spatial vs Object Partitions

• Spatial partition (e.g.KD-tree)
• Partition space into non-overlapping regions
• Objects can be contained in multiple regions
• Object partition (e.g. BVH)
• Partition set of objects into disjoint subsets
• Bounding boxes for each set may overlap in space

Bounding Volume Hierarchy (BVH)

Root

Bounding Volume Hierarchy (BVH)

Bounding Volume Hierarchy (BVH)

Bounding Volume Hierarchy (BVH)

A

B

C

D

Bounding Volume Hierarchy (BVH)

• Internal nodes store
• Bounding box
• Children: reference to child nodes
• Leaf nodes store
• Bounding box
• List of objects
• Nodes represent subset of primitives in scene
• All objects in subtree

BVH Pre-Processing

• Find bounding box
• Recursively split set of objects in two subsets
• Stop when there are just a few objects in each set
• Store obj reference(s) in each leaf node

BVH Pre-Processing

• Find bounding box

BVH Pre-Processing

• Sort triangles in terms of x
• Divide them into two groups
• Find bounding box for each

BVH Pre-Processing

• Sort triangles in terms of y
• Divide them into two groups
• Find bounding box for each

BVH Pre-Processing

• Sort triangles in terms of y
• Divide them into two groups
• Find bounding box for each

BVH Recursive Traversal

Intersect (Ray ray, BVH node)

{

if (ray misses node.bbox) return;

​

if (node is a leaf node)

test intersection with all objs;

return closest intersection;

​

hit1 = Intersect (ray, node.child1);

hit2 = Intersect (ray, node.child2);

​

return closer of hit1, hit2;

}

​

node

child1

child2