PowerPoint Presentation
7: Raytracing &
Geometric Intersections
Dr. Hamish Carr
COMP 5812M: Foundations of Modelling & Rendering
Assumptions
Assume we have:
A triangle mesh M, with:
Vertex positions
Vertex normals
Texture coordinates (& a texture)
An eye E
An image plane Π made up of pixels
COMP 5812M: Foundations of Modelling & Rendering
High-Level Design
For each pixel π:
Start at the eye (E)
Cast a ray R through π
Keep going until you find P
Where the light came from
Eye E
Ray R
Point P
Pixel π
Plane Π
COMP 5812M: Foundations of Modelling & Rendering
Ray Casting
How do we find P?
for each pixel p_ij = (i,j)
let R_ij be the ray from E through p_ij
cast ray R into scene
find point P where R first intersects an object
compute lighting at point P
store in image[i,j]
COMP 5812M: Foundations of Modelling & Rendering
Finding P
P is a point on a triangle
But which triangle?
Simple strategy:
Test all triangles T
Take the one closest to the eye
We could sort, but we actually select
Because we only care about the closest
Point P
COMP 5812M: Foundations of Modelling & Rendering
Selecting an Item
Set distance = infinity
Then for each triangle T
Compute the point P where R intersects T
Compute the distance d
If d < distance
Compute the lighting and store it
At the end, we have the correct value
COMP 5812M: Foundations of Modelling & Rendering
Basic Raycaster
for each pixel p_ij = (i,j)
let R_ij be the ray from E through p_ij
closest = infinity
for each triangle T
find P at intersection of R_ij and T
find d = distance(P,E)
if (d > closest)
continue
compute lighting at point P
store in image[i,j]
COMP 5812M: Foundations of Modelling & Rendering
Adding Shadows
We’ve assume light cannot be blocked
Other objects, however, might be in the way
So we cast a shadow ray from P to the light
And see if P is visible from the light
P
COMP 5812M: Foundations of Modelling & Rendering
Shadow Ray Casting
This uses the same method that found P
But along the ray from L to P
If P is the closest to L, it’s lit
We allow a small tolerance ε>0
To avoid shadow acne
COMP 5812M: Foundations of Modelling & Rendering
Shadow Examples
Ground Plane
Shadows Added
Acne Removed
More Triangles
COMP 5812M: Foundations of Modelling & Rendering
Rasterisation
Just invert the two loops
for each pixel p_ij = (i,j)
depth[i,j] = infinity
for each triangle T
for each pixel p_ij = (i,j)
let R_ij be the ray from E through p_ij
find P at intersection of R_ij and T
find d = distance(P,E)
if (d > depth[i,j])
continue
compute lighting at point P
store in image[i,j]
COMP 5812M: Foundations of Modelling & Rendering
Geometric Intersection
Recurrent problem in graphics
Interpolation
Raytracing of all forms
Mesh manifold tests
Collision Detection
Mesh processing
COMP 5812M: Foundations of Modelling & Rendering
Intersection Tests
1D: point in segment, 2 segments
2D: points, lines, segments, circles, boxes, triangles, polygons
2.5D: rays & triangles in 3D
3D: points, lines, segments, planes, spheres, boxes, tetrahedra, polyhedra, cylinders, capsules
&c, &c, &c
COMP 5812M: Foundations of Modelling & Rendering
1D: The Easy One
COMP 5812M: Foundations of Modelling & Rendering
1D: Two Segments
No
Yes
Yes
Yes
Yes
No
COMP 5812M: Foundations of Modelling & Rendering
Test
But is there an easier way?
COMP 5812M: Foundations of Modelling & Rendering
Optimized
NN
YN
YN
NY
NY
NN
COMP 5812M: Foundations of Modelling & Rendering
Better Yet
COMP 5812M: Foundations of Modelling & Rendering
2D Intersections
Line – Line
Box – Box (AABB)
Circle – Circle
Triangle – Triangle
Polygon – Polygon
COMP 5812M: Foundations of Modelling & Rendering
Two Parametric Lines
Each has a separate parameter
We want to find r
by finding t1 at r
or t2 at r
COMP 5812M: Foundations of Modelling & Rendering
System of Equations
Two equations in two unknowns,
which means we can solve it . . .
or we can find a faster way
COMP 5812M: Foundations of Modelling & Rendering
Similar Triangles
Find t2 at r
Similar triangles, so
find d and D
COMP 5812M: Foundations of Modelling & Rendering
Finding d
Use the dot product:
COMP 5812M: Foundations of Modelling & Rendering
Finding D
Similarly,
COMP 5812M: Foundations of Modelling & Rendering
Solution
COMP 5812M: Foundations of Modelling & Rendering
Axis-Aligned Boxes (AAB)
Line segment test in both of x, y axes
COMP 5812M: Foundations of Modelling & Rendering
Circle – Circle
COMP 5812M: Foundations of Modelling & Rendering
Triangle-Triangle
Check for edge intersections
segment-segment intersection
line-line test & check parameters s,t
COMP 5812M: Foundations of Modelling & Rendering
But . . . .
Fails when one inside the other
Not actually a problem
If time steps are small enough
COMP 5812M: Foundations of Modelling & Rendering
Half-Plane Method
If vertex of A is inside B, intersection
assuming small time steps …
COMP 5812M: Foundations of Modelling & Rendering
Convex Polygons
Special case
Half-plane test still works
Points are consistently inside edges
COMP 5812M: Foundations of Modelling & Rendering
Concave Polygons
There is at least one corner with angle <
Cut it off, then iterate
COMP 5812M: Foundations of Modelling & Rendering
2.5D Intersections
Line (Ray) - Sphere
Line – Plane
Line – Triangle
Plane - Plane
Triangle - Triangle
COMP 5812M: Foundations of Modelling & Rendering
Line-Sphere Intersection
Given a sphere
And a line
Find point p at intersection
i.e. find t
COMP 5812M: Foundations of Modelling & Rendering
Step 1
COMP 5812M: Foundations of Modelling & Rendering
Step 2
COMP 5812M: Foundations of Modelling & Rendering
Planes
A plane is a flat sheet
a 2-D subspace of our 3-D space
defined by 3 points
or by 2 vectors and 1 point
Explicit, implicit/normal & parametric forms
COMP 5812M: Foundations of Modelling & Rendering
Equation of a Plane
Take the xy-plane through the origin:
Take a point p on this plane:
z-coordinate is 0
Call the plane ∏
COMP 5812M: Foundations of Modelling & Rendering
Rotating the Plane
COMP 5812M: Foundations of Modelling & Rendering
Rotated Plane
As ∏ rotates, so do the vectors
p is still the same sum of vectors
but the vectors have changed
Plane still passes through origin
COMP 5812M: Foundations of Modelling & Rendering
Arbitrary Planes
Not all planes pass through the origin:
COMP 5812M: Foundations of Modelling & Rendering
Full Parametric Form
Parametric form of arbitrary plane:
p is any point in ∏
u, v are any two independent vectors in ∏
COMP 5812M: Foundations of Modelling & Rendering
Normal Form
We know
Find (the cross-product)
perpendicular to and
therefore perpendicular to
a normal vector for
COMP 5812M: Foundations of Modelling & Rendering
Normal Form
Measures distance to the plane in 3D
Multiplied by
COMP 5812M: Foundations of Modelling & Rendering
Half-Space Test
Generalised form of half-plane test
Doesn’t give you distance directly
Because it uses an unnormalised normal
COMP 5812M: Foundations of Modelling & Rendering
Planar Coordinate System
Given plane defined by point , vectors
Normalise
Compute and normalise
Compute and normalize
, , are now an orthonormal basis
p is the origin with respect to the plane
So we can convert other coords onto it
COMP 5812M: Foundations of Modelling & Rendering
Converting to Planar CS
Assume you have a plane
And a point
Let
Then project onto
gives in the PCS
(i.e. are rows of matrix )
COMP 5812M: Foundations of Modelling & Rendering
Line – Plane Intersection
Assume you have a plane
And a line
Find = in PCS
Find
Then is the rate the line approaches
And is when they intersect
At point
COMP 5812M: Foundations of Modelling & Rendering
Line – Triangle Intersection
Assume you have a triangle
And a line
Construct vectors on
Use these to construct plane
Find point
Convert to PCS with
Do the same with
COMP 5812M: Foundations of Modelling & Rendering
Testing on the Plane
Notice that
So we can just look at the u,w coordinates
And now we can do barycentric interpolation
And test whether the point is in
There are obviously many optimisations
Which we may look at next term
COMP 5812M: Foundations of Modelling & Rendering
Plane-Plane Intersections
Given planes
Then is the vector of the shared line
and is on perpendicular to it
and line will intersect with
Then is on the shared line
I.e. the line is
COMP 5812M: Foundations of Modelling & Rendering
Triangle-Triangle Intersections
Use the triangles to construct two planes
Use the plane-plane test to find the line
Find the intersections with each triangle
Use the 1D test for intersection!
Again, there are many optimisations
Akenine-Möller, 3d ed.
COMP 5812M: Foundations of Modelling & Rendering
3D Intersections
Box - Box (AABB)
Sphere - Sphere
Tetrahedron - Tetrahedron
Polyhedron - Polyhedron
Cylinders & Capsules
COMP 5812M: Foundations of Modelling & Rendering
3D AAB - AAB
Axis-Aligned Boxes
Same as 2D
Project to individual axes
Then do line segment tests
COMP 5812M: Foundations of Modelling & Rendering
3D Spheres
Same as 2D Circles
or 1D Segments (2d form)
COMP 5812M: Foundations of Modelling & Rendering
3D Tetrahedra
Same as 2D Triangles
Use Half-Space Test
Test against each face
with consistent orientation
COMP 5812M: Foundations of Modelling & Rendering
3D Polyhedra
Convex Polyhedra
Half-Space Test
Concave Polyhedra
Decompose into Tetrahedra
Hard problem
COMP 5812M: Foundations of Modelling & Rendering
Bounding Primitives
Polyhedra tests are expensive
Especially for large complex objects
Commonest case: no intersection
So use cheap test first:
Bounding Spheres
Axis-Aligned Bounding Boxes
COMP 5812M: Foundations of Modelling & Rendering