Ray Tracing in Computer Graphics
undefinedC
o
m
p
u
t
e
r
G
r
a
p
h
i
c
s
CSE 167 [Win 24], Lecture 15: Ray Tracing
Ravi Ramamoorthi
http://viscomp.ucsd.edu/classes/cse167/wi24
T
o
D
o
HW 3 due tomorrow Feb 28. Any questions?
HW 4 milestone due Mar 8, full homework Mar 19
START EARLY; FIND A PARTNER IF POSSIBLE
Likely hardest assignment you will have at UCSD
(but most rewarding).
Some comments from edX:
The last assignment took me 50+ hours brutal but worth it
The final project (a ray tracer from scratch) was great; it’s
remarkable that the instructor ... students all the tools to
successfully complete it.
E
f
f
e
c
t
s
n
e
e
d
e
d
f
o
r
R
e
a
l
i
s
m
(Soft) Shadows
Reflections (Mirrors and Glossy)
Transparency (Water, Glass)
Interreflections (Color Bleeding)
Complex Illumination (Natural, Area Light)
Realistic Materials (Velvet, Paints, Glass)
And many more
Image courtesy Paul Heckbert 1983
R
a
y
T
r
a
c
i
n
g
Different Approach to Image Synthesis as
compared to Hardware pipeline (OpenGL)
Pixel by Pixel instead of Object by Object
Easy to compute shadows/transparency/etc
O
u
t
l
i
n
e
History
Basic Ray Casting (instead of rasterization)
Comparison to hardware scan conversion
Shadows / Reflections (core algorithm)
Ray-Surface Intersection
Optimizations
Current Research
R
a
y
T
r
a
c
i
n
g
:
H
i
s
t
o
r
y
Appel 68
Whitted 80 [recursive ray tracing]
Landmark in computer graphics
Lots of work on various geometric primitives
Lots of work on accelerations
Current Research
Real-Time raytracing (historically, slow technique)
Ray tracing architecture
R
a
y
T
r
a
c
i
n
g
H
i
s
t
o
r
y
R
a
y
T
r
a
c
i
n
g
H
i
s
t
o
r
y
F
r
o
m
S
I
G
G
R
A
P
H
1
8
Real Photo: Instructor and Turner Whitted at SIGGRAPH 18
O
u
t
l
i
n
e
i
n
C
o
d
e
Image Raytrace (Camera cam, Scene scene, int width, int height)
{Image image = new Image (width, height) ;
for (int i = 0 ; i < height ; i++)
for (int j = 0 ; j < width ; j++) {Ray ray = RayThruPixel (cam, i, j) ;
Intersection hit = Intersect (ray, scene) ;
image[i][j] = FindColor (hit) ;
}
return image ;
}
O
u
t
l
i
n
e
History
Basic Ray Casting
(instead of rasterization)
Comparison to hardware scan conversion
Shadows / Reflections (core algorithm)
Ray-Surface Intersection
Optimizations
Current Research
R
a
y
C
a
s
t
i
n
g
Produce same images as with OpenGL
Visibility per pixel instead of Z-buffer
Find nearest object by shooting rays into scene
Shade it as in standard OpenGL
Ray Casting
Virtual Viewpoint
Virtual Screen
Objects
Ray misses all objects: Pixel colored black
Ray intersects object: shade using color, lights, materials
Multiple intersections: Use closest one (as does OpenGL)
C
o
m
p
a
r
i
s
o
n
t
o
h
a
r
d
w
a
r
e
s
c
a
n
-
l
i
n
e
Per-pixel evaluation, per-pixel rays (not scan-convert
each object). On face of it, costly
But good for walkthroughs of extremely large models
(amortize preprocessing, low complexity)
More complex shading, lighting effects possible
O
u
t
l
i
n
e
History
Basic Ray Casting (instead of rasterization)
Comparison to hardware scan conversion
Shadows / Reflections (core algorithm)
Ray-Surface Intersection
Optimizations
Current Research
Shadows
Virtual Viewpoint
Virtual Screen
Objects
Light Source
Shadow ray to light is unblocked: object visible
Shadow ray to light is blocked: object in shadow
Shadows: Numerical Issues
•
Numerical inaccuracy may cause intersection to be
below surface (effect exaggerated in figure)
•
Causing surface to incorrectly shadow itself
•
Move a little towards light before shooting shadow ray
Mirror Reflections/Refractions
Virtual Viewpoint
Virtual Screen
Objects
R
e
c
u
r
s
i
v
e
R
a
y
T
r
a
c
i
n
g
For each pixel
Trace Primary Eye Ray, find intersection
Trace Secondary Shadow Ray(s) to all light(s)
Color = Visible ? Illumination Model : 0 ;
Trace Reflected Ray
Color += reflectivity * Color of reflected ray
P
r
o
b
l
e
m
s
w
i
t
h
R
e
c
u
r
s
i
o
n
Reflection rays may be traced forever
Generally, set maximum recursion depth
Same for transmitted rays (take refraction into
account)
Turner Whitted 1980
Effects needed for Realism
•
(Soft)
Shadows
•
Reflections (Mirrors and
Glossy
)
•
Transparency (Water, Glass)
•
Interreflections (Color Bleeding)
•
Complex Illumination (Natural, Area Light)
•
Realistic Materials (Velvet, Paints, Glass)
Discussed in this lecture
Not discussed but possible with distribution ray tracing
Hard (but not impossible) with ray tracing; radiosity methods
O
u
t
l
i
n
e
History
Basic Ray Casting (instead of rasterization)
Comparison to hardware scan conversion
Shadows / Reflections (core algorithm)
Ray-Surface Intersection
Optimizations
Current Research
R
a
y
/
O
b
j
e
c
t
I
n
t
e
r
s
e
c
t
i
o
n
s
Heart of Ray Tracer
One of the main initial research areas
Optimized routines for wide variety of primitives
Various types of info
Shadow rays: Intersection/No Intersection
Primary rays: Point of intersection, material, normals
Texture coordinates
Work out examples
Triangle, sphere, polygon, general implicit surface
R
a
y
-
S
p
h
e
r
e
I
n
t
e
r
s
e
c
t
i
o
n
R
a
y
-
S
p
h
e
r
e
I
n
t
e
r
s
e
c
t
i
o
n
Substitute
Simplify
R
a
y
-
S
p
h
e
r
e
I
n
t
e
r
s
e
c
t
i
o
n
Solve quadratic equations for t
2 real positive roots: pick smaller root
Both roots same: tangent to sphere
One positive, one negative root: ray
origin inside sphere (pick + root)
Complex roots: no intersection (check
discriminant of equation first)
R
a
y
-
S
p
h
e
r
e
I
n
t
e
r
s
e
c
t
i
o
n
Intersection point:
Normal (for sphere, this is same as coordinates
in sphere frame of reference, useful other tasks)
R
a
y
-
T
r
i
a
n
g
l
e
I
n
t
e
r
s
e
c
t
i
o
n
One approach: Ray-Plane intersection, then
check if inside triangle
Plane equation:
A
B
C
R
a
y
-
T
r
i
a
n
g
l
e
I
n
t
e
r
s
e
c
t
i
o
n
One approach: Ray-Plane intersection, then
check if inside triangle
Plane equation:
Combine with ray equation:
A
B
C
R
a
y
i
n
s
i
d
e
T
r
i
a
n
g
l
e
Once intersect with plane, still need to find if in
triangle
Many possibilities for triangles, general polygons
(point in polygon tests)
We find parametrically [barycentric coordinates]. Also
useful for other applications (texture mapping)
R
a
y
i
n
s
i
d
e
T
r
i
a
n
g
l
e
O
t
h
e
r
p
r
i
m
i
t
i
v
e
s
Much early work in ray tracing focused on ray-primitive
intersection tests
Cones, cylinders, ellipsoids
Boxes (especially useful for bounding boxes)
General planar polygons
Many more
Many references. For example, chapter in Glassner
introduction to ray tracing (see me if interested)
R
a
y
-
T
r
a
c
i
n
g
T
r
a
n
s
f
o
r
m
e
d
O
b
j
e
c
t
s
We have an optimized ray-sphere test
But we want to ray trace an ellipsoid…
Solution: Ellipsoid transforms sphere
Apply inverse transform to ray, use ray-sphere
Allows for instancing (traffic jam of cars)
Mathematical details worked out in class
T
r
a
n
s
f
o
r
m
e
d
O
b
j
e
c
t
s
Consider a general 4x4 transform M
Will need to implement matrix stacks like in OpenGL
Apply inverse transform M
-1
to ray
Locations stored and transform in homogeneous
coordinates
Vectors (ray directions) have homogeneous coordinate
set to 0 [so there is no action because of translations]
Do standard ray-surface intersection as modified
Transform intersection back to actual coordinates
Intersection point p transforms as Mp
Distance to intersection if used may need recalculation
Normals n transform as M
-t
n. Do all this before lighting
O
u
t
l
i
n
e
History
Basic Ray Casting (instead of rasterization)
Comparison to hardware scan conversion
Shadows / Reflections (core algorithm)
Ray-Surface Intersection
Optimizations
Current Research
A
c
c
e
l
e
r
a
t
i
o
n
Testing each object for each ray is slow
Fewer Rays
Adaptive sampling, depth control
Generalized Rays
Beam tracing, cone tracing, pencil tracing etc.
Faster Intersections
Optimized Ray-Object Intersections
F
e
w
e
r
I
n
t
e
r
s
e
c
t
i
o
n
s
We just discuss some approaches at high level; chapter 13 briefly covers
A
c
c
e
l
e
r
a
t
i
o
n
S
t
r
u
c
t
u
r
e
s
Bounding boxes (possibly hierarchical)
If no intersection bounding box, needn
’
t check objects
Bounding Box
Ray
Spatial Hierarchies (Oct-trees, kd trees, BSP trees)
A
c
c
e
l
e
r
a
t
i
o
n
S
t
r
u
c
t
u
r
e
s
:
G
r
i
d
s
A
c
c
e
l
e
r
a
t
i
o
n
a
n
d
R
e
g
u
l
a
r
G
r
i
d
s
Simplest acceleration, for example 5x5x5 grid
For each grid cell, store overlapping triangles
March ray along grid (need to be careful with
this), test against each triangle in grid cell
More sophisticated: kd-tree, oct-tree bsp-tree
Or use (hierarchical) bounding boxes
Try to implement some acceleration in HW 4
O
u
t
l
i
n
e
History
Basic Ray Casting (instead of rasterization)
Comparison to hardware scan conversion
Shadows / Reflections (core algorithm)
Ray-Surface Intersection
Optimizations
Current Research
I
n
t
e
r
a
c
t
i
v
e
R
a
y
t
r
a
c
i
n
g
Ray tracing historically slow
Now viable alternative for complex scenes
Key is sublinear complexity with acceleration;
need not process all triangles in scene
Allows many effects hard in hardware
NVIDIA OptiX ray-tracing API like OpenGL
Today: TuringRT 10G rays/second:
Video
R
a
y
t
r
a
c
i
n
g
o
n
G
r
a
p
h
i
c
s
H
a
r
d
w
a
r
e
Modern Programmable Hardware general
streaming architecture
Can map various elements of ray tracing
Kernels like eye rays, intersect etc.
In vertex or fragment programs
Convergence between hardware, ray tracing
[Purcell et al. 2002, 2003]
http://graphics.stanford.edu/papers/photongfx
Explore the fascinating world of ray tracing in computer graphics through this comprehensive lecture series. From creating realism with effects like shadows, reflections, and transparency to delving into the history and evolution of ray tracing, this content covers it all. Discover the different approach of ray tracing compared to hardware pipelines and learn about the landmark contributions in the field. Get insights into the challenges and rewards of assignments involving ray tracing techniques, and the importance of early start and collaboration. Don't miss out on this essential knowledge for anyone interested 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
Computer Graphics CSE 167 [Win 24], Lecture 15: Ray Tracing Ravi Ramamoorthi http://viscomp.ucsd.edu/classes/cse167/wi24
To Do HW 3 due tomorrow Feb 28. Any questions? HW 4 milestone due Mar 8, full homework Mar 19 START EARLY; FIND A PARTNER IF POSSIBLE Likely hardest assignment you will have at UCSD (but most rewarding). Some comments from edX: The last assignment took me 50+ hours brutal but worth it The final project (a ray tracer from scratch) was great; it s remarkable that the instructor ... students all the tools to successfully complete it.
Effects needed for Realism (Soft) Shadows Reflections (Mirrors and Glossy) Transparency (Water, Glass) Interreflections (Color Bleeding) Complex Illumination (Natural, Area Light) Realistic Materials (Velvet, Paints, Glass) And many more
Ray Tracing Different Approach to Image Synthesis as compared to Hardware pipeline (OpenGL) Pixel by Pixel instead of Object by Object Easy to compute shadows/transparency/etc
Outline History Basic Ray Casting (instead of rasterization) Comparison to hardware scan conversion Shadows / Reflections (core algorithm) Ray-Surface Intersection Optimizations Current Research
Ray Tracing: History Appel 68 Whitted 80 [recursive ray tracing] Landmark in computer graphics Lots of work on various geometric primitives Lots of work on accelerations Current Research Real-Time raytracing (historically, slow technique) Ray tracing architecture
From SIGGRAPH 18 Real Photo: Instructor and Turner Whitted at SIGGRAPH 18
Outline in Code Image Raytrace (Camera cam, Scene scene, int width, int height) { Image image = new Image (width, height) ; for (int i = 0 ; i < height ; i++) for (int j = 0 ; j < width ; j++) { Ray ray = RayThruPixel (cam, i, j) ; Intersection hit = Intersect (ray, scene) ; image[i][j] = FindColor (hit) ; } return image ; }
Outline History Basic Ray Casting (instead of rasterization) Comparison to hardware scan conversion Shadows / Reflections (core algorithm) Ray-Surface Intersection Optimizations Current Research
Ray Casting Produce same images as with OpenGL Visibility per pixel instead of Z-buffer Find nearest object by shooting rays into scene Shade it as in standard OpenGL
Ray Casting Virtual Viewpoint Virtual Screen Objects Ray misses all objects: Pixel colored black Ray intersects object: shade using color, lights, materials Multiple intersections: Use closest one (as does OpenGL)
Comparison to hardware scan-line Per-pixel evaluation, per-pixel rays (not scan-convert each object). On face of it, costly But good for walkthroughs of extremely large models (amortize preprocessing, low complexity) More complex shading, lighting effects possible
Outline History Basic Ray Casting (instead of rasterization) Comparison to hardware scan conversion Shadows / Reflections (core algorithm) Ray-Surface Intersection Optimizations Current Research
Shadows Light Source Virtual Viewpoint Virtual Screen Objects Shadow ray to light is unblocked: object visible Shadow ray to light is blocked: object in shadow
Shadows: Numerical Issues Numerical inaccuracy may cause intersection to be below surface (effect exaggerated in figure) Causing surface to incorrectly shadow itself Move a little towards light before shooting shadow ray
Mirror Reflections/Refractions Virtual Viewpoint Virtual Screen Objects Generate reflected ray in mirror direction, Get reflections and refractions of objects
Recursive Ray Tracing For each pixel Trace Primary Eye Ray, find intersection Trace Secondary Shadow Ray(s) to all light(s) Color = Visible ? Illumination Model : 0 ; Trace Reflected Ray Color += reflectivity * Color of reflected ray
Problems with Recursion Reflection rays may be traced forever Generally, set maximum recursion depth Same for transmitted rays (take refraction into account)
Effects needed for Realism (Soft) Shadows Reflections (Mirrors and Glossy) Transparency (Water, Glass) Interreflections (Color Bleeding) Complex Illumination (Natural, Area Light) Realistic Materials (Velvet, Paints, Glass) Discussed in this lecture Not discussed but possible with distribution ray tracing Hard (but not impossible) with ray tracing; radiosity methods
Outline History Basic Ray Casting (instead of rasterization) Comparison to hardware scan conversion Shadows / Reflections (core algorithm) Ray-Surface Intersection Optimizations Current Research
Ray/Object Intersections Heart of Ray Tracer One of the main initial research areas Optimized routines for wide variety of primitives Various types of info Shadow rays: Intersection/No Intersection Primary rays: Point of intersection, material, normals Texture coordinates Work out examples Triangle, sphere, polygon, general implicit surface
Ray-Sphere Intersection P = P0+P1t ray sphere (P -C)i(P -C)-r2= 0 C P0
Ray-Sphere Intersection P = P0+P1t ray sphere (P -C)i(P -C)-r2= 0 Substitute P = P0+P1t ray sphere (P0+P1t -C)i(P0+P1t -C)-r2= 0 Simplify t2(P1iP1)+2t P1i(P0-C)+(P0-C)i(P0-C)-r2= 0
Ray-Sphere Intersection t2(P1iP1)+2t P1i(P0-C)+(P0-C)i(P0-C)-r2= 0 Solve quadratic equations for t 2 real positive roots: pick smaller root Both roots same: tangent to sphere One positive, one negative root: ray origin inside sphere (pick + root) Complex roots: no intersection (check discriminant of equation first)
Ray-Sphere Intersection P = P0+P1t ray Intersection point: Normal (for sphere, this is same as coordinates in sphere frame of reference, useful other tasks) P -C P -C normal =
Ray-Triangle Intersection One approach: Ray-Plane intersection, then check if inside triangle A B n =(C - A) (B- A) (C - A) (B- A) Plane equation: plane Pin- Ain = 0 C
Ray-Triangle Intersection One approach: Ray-Plane intersection, then check if inside triangle A B n =(C - A) (B- A) (C - A) (B- A) Plane equation: plane Pin- Ain = 0 Combine with ray equation: P = P0+P1t (P0+P1t)in = Ain C ray t =Ain-P0in P1in
Ray inside Triangle Once intersect with plane, still need to find if in triangle Many possibilities for triangles, general polygons (point in polygon tests) We find parametrically [barycentric coordinates]. Also useful for other applications (texture mapping) B P =aA+ bB+gC a 0,b 0,g 0 a + b +g =1 A P C
Ray inside Triangle P =aA+ bB+gC a 0,b 0,g 0 a + b +g =1 B A P C P -A= b(B-A)+g(C-A) 0 b 1 , 0 g 1 b +g 1
Other primitives Much early work in ray tracing focused on ray-primitive intersection tests Cones, cylinders, ellipsoids Boxes (especially useful for bounding boxes) General planar polygons Many more Many references. For example, chapter in Glassner introduction to ray tracing (see me if interested)
Ray-Tracing Transformed Objects We have an optimized ray-sphere test But we want to ray trace an ellipsoid Solution: Ellipsoid transforms sphere Apply inverse transform to ray, use ray-sphere Allows for instancing (traffic jam of cars) Mathematical details worked out in class
Transformed Objects Consider a general 4x4 transform M Will need to implement matrix stacks like in OpenGL Apply inverse transform M-1 to ray Locations stored and transform in homogeneous coordinates Vectors (ray directions) have homogeneous coordinate set to 0 [so there is no action because of translations] Do standard ray-surface intersection as modified Transform intersection back to actual coordinates Intersection point p transforms as Mp Distance to intersection if used may need recalculation Normals n transform as M-tn. Do all this before lighting
Outline History Basic Ray Casting (instead of rasterization) Comparison to hardware scan conversion Shadows / Reflections (core algorithm) Ray-Surface Intersection Optimizations Current Research
Acceleration Testing each object for each ray is slow Fewer Rays Adaptive sampling, depth control Generalized Rays Beam tracing, cone tracing, pencil tracing etc. Faster Intersections Optimized Ray-Object Intersections Fewer Intersections We just discuss some approaches at high level; chapter 13 briefly covers
Acceleration Structures Bounding boxes (possibly hierarchical) If no intersection bounding box, needn t check objects Bounding Box Ray Spatial Hierarchies (Oct-trees, kd trees, BSP trees)
Acceleration and Regular Grids Simplest acceleration, for example 5x5x5 grid For each grid cell, store overlapping triangles March ray along grid (need to be careful with this), test against each triangle in grid cell More sophisticated: kd-tree, oct-tree bsp-tree Or use (hierarchical) bounding boxes Try to implement some acceleration in HW 4
Outline History Basic Ray Casting (instead of rasterization) Comparison to hardware scan conversion Shadows / Reflections (core algorithm) Ray-Surface Intersection Optimizations Current Research
Interactive Raytracing Ray tracing historically slow Now viable alternative for complex scenes Key is sublinear complexity with acceleration; need not process all triangles in scene Allows many effects hard in hardware NVIDIA OptiX ray-tracing API like OpenGL Today: TuringRT 10G rays/second: Video
Raytracing on Graphics Hardware Modern Programmable Hardware general streaming architecture Can map various elements of ray tracing Kernels like eye rays, intersect etc. In vertex or fragment programs Convergence between hardware, ray tracing [Purcell et al. 2002, 2003] http://graphics.stanford.edu/papers/photongfx
