Ray Tracing Techniques in Computer Graphics
C
S
5
8
0
:
R
a
y
T
r
a
c
i
n
g
S
u
n
g
-
E
u
i
Y
o
o
n
(
윤
성
의
)
C
o
u
r
s
e
U
R
L
:
h
t
t
p
:
/
/
s
g
l
a
b
.
k
a
i
s
t
.
a
c
.
k
r
/
~
s
u
n
g
e
u
i
/
G
C
G
/
R
e
c
u
r
s
i
v
e
R
a
y
C
a
s
t
i
n
g
●
Gained popularity in when
Turner Whitted (1980)
recognized that
recursive
ray casting could be used
for global illumination
effects
R
a
y
C
a
s
t
i
n
g
a
n
d
R
a
y
T
r
a
c
i
n
g
●
Trace rays from eye into scene
●
Backward ray tracing
●
Ray casting used to compute visibility at
the eye
●
Perform ray tracing for arbitrary rays
needed for shading
●
Reflections
●
Refraction and transparency
●
Shadows
●
Rays are cast from the eye point through
each pixel in the image
B
a
s
i
c
A
l
g
o
r
i
t
h
m
s
S
h
a
d
o
w
s
●
Cast ray from the intersection point to each
light source
●
Shadow rays
U
s
e
d
3
d
s
M
a
x
R
e
f
l
e
c
t
i
o
n
s
●
If object specular, cast secondary reflected
rays
R
e
f
r
a
c
t
i
o
n
s
●
If object tranparent, cast secondary
refracted rays
A
n
I
m
p
r
o
v
e
d
I
l
l
u
m
i
n
a
t
i
o
n
M
o
d
e
l
[
W
h
i
t
t
e
d
8
0
]
●
Phong illumination model
●
Whitted model
●
S and T are intensity of light from reflection
and transmission rays
●
Ks and Kt are specular and transmission
coefficient
O
p
e
n
G
L
’
s
I
l
l
u
m
i
n
a
t
i
o
n
M
o
d
e
l
From Wikipedia
A
m
b
i
e
n
t
L
i
g
h
t
S
o
u
r
c
e
●
A simple
hack
for indirect illumination
●
Incoming ambient illumination (I
i,a
) is constant
for all surfaces in the scene
●
Reflected ambient illumination (I
r,a
) depends
only on the surface’s ambient reflection
coefficient (k
a
) and not its position or
orientation
●
These quantities typically specified as (R, G, B)
triples
I
d
e
a
l
D
i
f
f
u
s
e
R
e
f
l
e
c
t
i
o
n
●
Ideal diffuse reflectors (e.g., chalk)
●
Reflect uniformly over the hemisphere
●
Reflection is view-independent
●
Very rough at the microscopic level
●
Follow Lambert’s cosine law
L
a
m
b
e
r
t
’
s
C
o
s
i
n
e
L
a
w
●
The reflected energy from a small surface area
from illumination arriving from direction is
proportional to the cosine of the angle between
and the surface normal
C
o
m
p
u
t
i
n
g
D
i
f
f
u
s
e
R
e
f
l
e
c
t
i
o
n
●
Constant of proportionality depends on
surface properties
●
The constant k
d
specifies how much of the
incident light I
i
is diffusely reflected
●
When the incident light is blocked by
the surface itself and the diffuse reflection is 0
S
p
e
c
u
l
a
r
R
e
f
l
e
c
t
i
o
n
●
Specular reflectors have a bright, view
dependent highlight
●
E.g., polished metal, glossy car finish, a mirror
●
At the microscopic level a specular reflecting
surface is very smooth
●
Specular reflection obeys
Snell’s law
Image source: astochimp.com and wiki
S
n
e
l
l
’
s
L
a
w
●
The relationship between the angles of
the incoming and reflected rays with the
normal is given by:
●
n
i
and n
o
are the indices of refraction for the
incoming and outgoing ray, respectively
●
Reflection is a special case where n
i
= n
o
so
o
=
i
●
The incoming ray, the surface normal, and the
reflected ray all lie in a common plane
N
o
n
-
I
d
e
a
l
R
e
f
l
e
c
t
o
r
s
●
Snell’s law applies only to
ideal
specular
reflectors
●
Roughness of surfaces causes highlight to
“spread out”
●
Empirical models try to simulate the
appearance of this effect, without trying to
capture the physics of it
P
h
o
n
g
I
l
l
u
m
i
n
a
t
i
o
n
●
One of the most commonly used
illumination models in computer graphics
●
Empirical model and does not have no physical
basis
●
is the direction to the viewer
●
is clamped to [0,1]
●
The specular exponent n
s
controls how quickly
the highlight falls off
E
f
f
e
c
t
o
f
S
p
e
c
u
l
a
r
E
x
p
o
n
e
n
t
●
How the shape of the highlight changes
with varying n
s
E
x
a
m
p
l
e
s
o
f
P
h
o
n
g
v
a
r
y
i
n
g
l
i
g
h
t
d
i
r
e
c
t
i
o
n
v
a
r
y
i
n
g
s
p
e
c
u
l
a
r
e
x
p
o
n
e
n
t
P
u
t
t
i
n
g
i
t
A
l
l
T
o
g
e
t
h
e
r
A
n
I
m
p
r
o
v
e
d
I
l
l
u
m
i
n
a
t
i
o
n
M
o
d
e
l
[
W
h
i
t
t
e
d
8
0
]
●
Phong illumination model
●
Whitted model
●
S and T are intensity of light from reflection
and transmission rays
●
Ks and Kt are specular and transmission
coefficient
R
a
y
T
r
e
e
e
y
e
s
0
b
a
d
c
f
e
s
1
s
2
R
T
R
R
T
T
A
c
c
e
l
e
r
a
t
i
o
n
M
e
t
h
o
d
s
f
o
r
R
a
y
T
r
a
c
i
n
g
●
Rendering time for a ray tracer depends on the
number of ray intersection tests per pixel
●
The number of pixels X the number of primitives in the scene
●
Early efforts focused on accelerating the ray-
object intersection tests
●
Ray-triangle intersection tests
●
More advanced methods required to make ray
tracing practical
●
Bounding volume hierarchies
●
Spatial subdivision (e.g., kd-trees)
B
o
u
n
d
i
n
g
V
o
l
u
m
e
s
●
Enclose complex objects within a simple-to-
intersect objects
●
If the ray does not intersect the simple object then its contents
can be ignored
●
The likelihood that it will strike the object depends on how
tightly the volume surrounds the object.
●
Spheres are simple, but not tight
●
Axis-aligned bounding boxes often better
●
Can use nested or hierarchical bounding volumes
B
o
u
n
d
i
n
g
V
o
l
u
m
e
s
●
Sphere [Whitted80]
●
Cheap to compute
●
Cheap test
●
Potentially very bad fit
●
Axis-Aligned Bounding Box
●
Very cheap to compute
●
Cheap test
●
Tighter than sphere
B
o
u
n
d
i
n
g
V
o
l
u
m
e
s
●
Oriented Bounding Box
●
Fairly cheap to compute
●
Fairly Cheap test
●
Generally fairly tight
●
Slabs / K-dops
●
More expensive
to compute
●
Fairly cheap test
●
Can be tighter than OBB
H
i
e
r
a
r
c
h
i
c
a
l
B
o
u
n
d
i
n
g
V
o
l
u
m
e
s
●
Organize bounding volumes as a tree
●
Choose a partitioning plane and distribute
triangles into left and right nodes
●
Each ray starts with the scene BV and
traverses down through the hierarchy
r
S
p
a
t
i
a
l
S
u
b
d
i
v
i
s
i
o
n
I
d
e
a
:
D
i
v
i
d
e
s
p
a
c
e
i
n
t
o
s
u
b
r
e
g
i
o
n
s
●
Place objects within a subregion into a list
●
Only traverse the lists of subregions that the ray
passes through
●
“Mailboxing” used to avoid multiple test with
objects in multiple regions
●
Many types
●
Regular grid
●
Octree
●
BSP tree
●
kd-tree
O
v
e
r
v
i
e
w
o
f
k
d
-
T
r
e
e
s
●
Binary spatial subdivision
(special case of BSP tree)
●
Split planes aligned on main axis
●
Inner nodes: subdivision planes
●
Leaf nodes: triangle(s)
E
x
a
m
p
l
e
E
x
a
m
p
l
e
E
x
a
m
p
l
e
E
x
a
m
p
l
e
E
x
a
m
p
l
e
What about triangles overlapping the split?
E
x
a
m
p
l
e
S
p
l
i
t
P
l
a
n
e
s
●
How to select axis & split plane?
●
Largest dimension, subdivide in middle
●
More advanced:
●
Surface area heuristic
●
Makes large difference
●
50%-100% higher
overall
speed
M
e
d
i
a
n
v
s
.
S
A
H
(from [Wald04])
R
a
y
T
r
a
c
i
n
g
w
i
t
h
k
d
-
t
r
e
e
●
Goal: find closest hit with scene
●
Traverse tree front to back
(starting from root)
●
At each node:
●
If leaf: intersect with triangles
●
If inner: traverse deeper
C
l
a
s
s
i
c
R
a
y
T
r
a
c
i
n
g
●
Gathering approach
●
From lights, reflected, and refracted
directions
●
Pros of ray tracing
●
Simple and improved realism over
the rendering pipeline
●
Cons:
●
Simple light model, material, and light propagation
●
Not a complete solution
●
Hard to accelerate with special-purpose H/W
H
i
s
t
o
r
y
●
Problems with classic ray tracing
●
Not realistic
●
View-dependent
●
Radiosity (1984)
●
Global illumination in diffuse scenes
●
Monte Carlo ray tracing (1986)
●
Global illumination for any environment
C
l
a
s
s
O
b
j
e
c
t
i
v
e
s
w
e
r
e
:
●
Understand a basic ray tracing
●
Know the Phong illumination model
●
Implement its acceleration data structure
and know how to use it
A
n
y
Q
u
e
s
t
i
o
n
s
?
●
Come up with one question on what we
have discussed in the class and submit at
the end of the class
●
1 for already answered questions
●
2 for typical questions
●
3 for questions with thoughts
●
Submit questions at least four times before
the mid-term exam
●
Multiple questions for the class is counted as
only a single time
H
o
m
e
w
o
r
k
●
Go over the next lecture slides before the
class
●
Watch 2 SIGGRAPH videos and submit your
summaries right brefore every Tue. class
●
Just one paragraph for each summary
E
x
a
m
p
l
e
:
T
i
t
l
e
:
X
X
X
X
X
X
X
X
X
X
X
A
b
s
t
r
a
c
t
:
t
h
i
s
v
i
d
e
o
i
s
a
b
o
u
t
a
c
c
e
l
e
r
a
t
i
n
g
t
h
e
p
e
r
f
o
r
m
a
n
c
e
o
f
r
a
y
t
r
a
c
i
n
g
.
T
o
a
c
h
i
e
v
e
i
t
s
g
o
a
l
,
t
h
e
y
d
e
s
i
g
n
a
n
e
w
t
e
c
h
n
i
q
u
e
f
o
r
r
e
o
r
d
e
r
i
n
g
r
a
y
s
,
s
i
n
c
e
b
y
d
o
i
n
g
s
o
,
t
h
e
y
c
a
n
i
m
p
r
o
v
e
t
h
e
r
a
y
c
o
h
e
r
e
n
c
e
a
n
d
t
h
u
s
i
m
p
r
o
v
e
t
h
e
o
v
e
r
a
l
l
p
e
r
f
o
r
m
a
n
c
e
.
P
A
1
●
Get to know pbrt
N
e
x
t
T
i
m
e
●
Radiosity
F
i
g
s
.
B
a
s
i
c
A
l
g
o
r
i
t
h
m
s
S
h
a
d
o
w
s
R
e
f
r
a
c
t
i
o
n
s
●
If object tranparent, cast secondary
refracted rays
Explore the fundamentals of ray tracing including recursive ray casting, ray casting vs. ray tracing, basic algorithms, shadows, reflections, refractions, and advanced illumination models like Whitted model and OpenGL's illumination model. Learn about casting rays from the eye, handling reflections and refractions, shadow calculations, and achieving realistic lighting effects in computer graphics.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CS580: Ray Tracing Sung-Eui Yoon ( ) Course URL: http://sglab.kaist.ac.kr/~sungeui/GCG/
Recursive Ray Casting Gained popularity in when Turner Whitted (1980) recognized that recursive ray casting could be used for global illumination effects 2
Ray Casting and Ray Tracing Trace rays from eye into scene Backward ray tracing Ray casting used to compute visibility at the eye Perform ray tracing for arbitrary rays needed for shading Reflections Refraction and transparency Shadows 3
Basic Algorithms Rays are cast from the eye point through each pixel in the image 4
Shadows Cast ray from the intersection point to each light source Shadow rays Used 3ds Max 5
Reflections If object specular, cast secondary reflected rays 6
Refractions If object tranparent, cast secondary refracted rays 7
An Improved Illumination Model [Whitted 80] Phong illumination model = 1 1 j j numLights numLights L L R R n n j j a a j j a a j j d d I I j j d d j j s s j j s s I I (k (k I I k k N N ( ( ) ) k k I I V V ( ( ) ) ) ) = + + s s r r j j Whitted model numLights numLights = j j j j a a j j j j I I (k (k I I a a k k I I d d N N ( ( d d L L )) )) j j k k S S s s k k T T t t + + + r r j j 1 1 = S and T are intensity of light from reflection and transmission rays Ks and Kt are specular and transmission coefficient 8
OpenGLs Illumination Model numLights numLights = 1 1 j j N N L L V V R R n n j j a a j j a a j j d d I I j j d d j j s s I I j j s s I I (k (k I I k k max(( max(( ),0) ),0) k k max(( max(( ) ) ,0)) ,0)) = + + s s r r j j From Wikipedia 9
Ambient Light Source A simple hack for indirect illumination Incoming ambient illumination (Ii,a) is constant for all surfaces in the scene Reflected ambient illumination (Ir,a ) depends only on the surface s ambient reflection coefficient (ka) and not its position or orientation r,a a i,a I k I = These quantities typically specified as (R, G, B) triples 10
Ideal Diffuse Reflection Ideal diffuse reflectors (e.g., chalk) Reflect uniformly over the hemisphere Reflection is view-independent Very rough at the microscopic level Follow Lambert s cosine law 11
Lamberts Cosine Law The reflected energy from a small surface area from illumination arriving from direction is proportional to the cosine of the angle between and the surface normal L L N L I I I I cos cos r r i i N N ) ) ( ( I I i i L L 12
Computing Diffuse Reflection Constant of proportionality depends on surface properties k k I I d d r,d r,d = N N ) ) ( ( I I i i L L The constant kd specifies how much of the incident light Ii is diffusely reflected Diffuse reflection for varying light directions (N L) When the incident light is blocked by the surface itself and the diffuse reflection is 0 0 13
Specular Reflection Specular reflectors have a bright, view dependent highlight E.g., polished metal, glossy car finish, a mirror At the microscopic level a specular reflecting surface is very smooth Specular reflection obeys Snell s law Image source: astochimp.com and wiki 14
Snells Law The relationship between the angles of the incoming and reflected rays with the normal is given by: N R L i = nsin n sin o i i o o ni and no are the indices of refraction for the incoming and outgoing ray, respectively Reflection is a special case where ni = no so o = i The incoming ray, the surface normal, and the reflected ray all lie in a common plane 15
Non-Ideal Reflectors Snell s law applies only to ideal specular reflectors Roughness of surfaces causes highlight to spread out Empirical models try to simulate the appearance of this effect, without trying to capture the physics of it N L R 16
Phong Illumination One of the most commonly used illumination models in computer graphics Empirical model and does not have no physical basis n n i i s s r r ) ) R R V V ( ( I I k k = N V L R I I k k I I (cos (cos ) ) = s s n n s s s s i i (V) is the direction to the viewer is clamped to [0,1] The specular exponent ns controls how quickly the highlight falls off R R V V ( ( ) ) 17
Effect of Specular Exponent How the shape of the highlight changes with varying ns 18
Examples of Phong varying light direction varying specular exponent 19
Putting it All Together numLights numLights = 1 1 j j N N L L V V R R n n j j a a j j a a j j d d I I j j d d j j s s I I j j s s I I (k (k I I k k max(( max(( ),0) ),0) k k max(( max(( ),0)) ),0)) = + + s s r r j j 20
An Improved Illumination Model [Whitted 80] Phong illumination model = 1 1 j j numLights numLights L L R R n n j j a a j j a a j j d d I I j j d d j j s s j j s s I I (k (k I I k k N N ( ( ) ) k k I I V V ( ( ) ) ) ) = + + s s r r j j Whitted model numLights numLights = j j j j a a j j j j I I (k (k I I a a k k I I d d N N ( ( d d L L )) )) j j k k S S s s k k T T t t + + + r r j j 1 1 = S and T are intensity of light from reflection and transmission rays Ks and Kt are specular and transmission coefficient 21
Ray Tree e s2 s1 f s0 a d c eye b eye R T s0 b a R T T R s1 b s2 f c e 22
Acceleration Methods for Ray Tracing Rendering time for a ray tracer depends on the number of ray intersection tests per pixel The number of pixels X the number of primitives in the scene Early efforts focused on accelerating the ray- object intersection tests Ray-triangle intersection tests More advanced methods required to make ray tracing practical Bounding volume hierarchies Spatial subdivision (e.g., kd-trees) 23
Bounding Volumes Enclose complex objects within a simple-to- intersect objects If the ray does not intersect the simple object then its contents can be ignored The likelihood that it will strike the object depends on how tightly the volume surrounds the object. Spheres are simple, but not tight Axis-aligned bounding boxes often better Can use nested or hierarchical bounding volumes 24
Bounding Volumes Sphere [Whitted80] Cheap to compute Cheap test Potentially very bad fit Axis-Aligned Bounding Box Very cheap to compute Cheap test Tighter than sphere 25
Bounding Volumes Oriented Bounding Box Fairly cheap to compute Fairly Cheap test Generally fairly tight Slabs / K-dops More expensive to compute Fairly cheap test Can be tighter than OBB 26
Hierarchical Bounding Volumes Organize bounding volumes as a tree Choose a partitioning plane and distribute triangles into left and right nodes Each ray starts with the scene BV and traverses down through the hierarchy r 27
Spatial Subdivision Idea: Divide space in to subregions Place objects within a subregion into a list Only traverse the lists of subregions that the ray passes through Mailboxing used to avoid multiple test with objects in multiple regions Many types Regular grid Octree BSP tree kd-tree 28
Overview of kd-Trees Binary spatial subdivision (special case of BSP tree) Split planes aligned on main axis Inner nodes: subdivision planes Leaf nodes: triangle(s) 29
Example 30
Example 31
Example 32
Example 33
Example What about triangles overlapping the split? 34
Example 35
Split Planes How to select axis & split plane? Largest dimension, subdivide in middle More advanced: Surface area heuristic Makes large difference 50%-100% higher overall speed 36
Median vs. SAH (from [Wald04]) 37
Ray Tracing with kd-tree Goal: find closest hit with scene Traverse tree front to back (starting from root) At each node: If leaf: intersect with triangles If inner: traverse deeper 38
Classic Ray Tracing Gathering approach From lights, reflected, and refracted directions Pros of ray tracing Simple and improved realism over the rendering pipeline Cons: Simple light model, material, and light propagation Not a complete solution Hard to accelerate with special-purpose H/W 39
History Problems with classic ray tracing Not realistic View-dependent Radiosity (1984) Global illumination in diffuse scenes Monte Carlo ray tracing (1986) Global illumination for any environment 40
Class Objectives were: Understand a basic ray tracing Know the Phong illumination model Implement its acceleration data structure and know how to use it 41
Any Questions? Come up with one question on what we have discussed in the class and submit at the end of the class 1 for already answered questions 2 for typical questions 3 for questions with thoughts Submit questions at least four times before the mid-term exam Multiple questions for the class is counted as only a single time 42
Homework Go over the next lecture slides before the class Watch 2 SIGGRAPH videos and submit your summaries right brefore every Tue. class Just one paragraph for each summary Example: Title: XXX XXXX XXXX Abstract: this video is about accelerating the performance of ray tracing. To achieve its goal, they design a new technique for reordering rays, since by doing so, they can improve the ray coherence and thus improve the overall performance. 43
PA1 Get to know pbrt 44
Next Time Radiosity 45
Figs. 46
Shadows 48
Refractions If object tranparent, cast secondary refracted rays 50
