程序代写代做代考 PowerPoint Presentation

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