raycasting-1

Ray Casting
Forward
Forward && Backward
Backward Ray
Ray Tracing
Tracing
Ray
Ray Casting
Casting
Ray-Surface
Ray-Surface Intersection
Intersection Testing
Testing
Barycentric
Barycentric Coordinates
Coordinates
11 Apr. 2000
Light is Bouncing Photons
• Light sources send off photons in all directions
– Model these as particles that bounce off objects in the scene
– Each photon has a wavelength and energy (color and intensity)
– When photons bounce, some energy is absorbed, some reflected,
some transmitted
• If we can model photon bounces we can generate images
• Technique: follow each photon from the light source until:

– All of its energy is absorbed (after too many bounces)
– It departs the known universe
– It strikes the image and its contribution is added to appropriate
pixel
Computer Graphics 15-462 2

Forward Ray Tracing
• Rays are the paths of these photons
• This method of rendering by following photon paths is
called ray tracing
• Forward ray tracing follows the photon in direction that
light travels (from the source)
• BIG problem with this approach:
– Only a tiny fraction of rays will not reach the image
– Extremely slow
• Ideal Scenario:
– we'd like to magically know which rays will eventually contribute
to the image, and trace only those

Backward Ray Tracing
• The solution is to start from the image and trace backwards
- backward ray tracing
– Start from the image and follow the ray until the ray finds (or fails
to find) a light source
– People actually used to believe vision worked this way

Backward Ray Tracing
• Basic ideas:
– Each pixel gets light from just one direction - the line through the
image point and focal point
– Any photon contributing to that pixel’s color has to come from this
direction
– So head in that direction and find what is sending light this way
– If we hit a light source - we’re done
– If we find nothing - we’re done
– If we hit a surface - see where that surface is lit from
• At the end we’ve done forward ray tracing, but only for the
rays that contribute to the image

Ray Casting
• This version of ray tracing is often called ray casting
• The algorithm is:
loop y
loop x
shoot ray from eye point through pixel (x,y) into scene
intersect with all surfaces, find first one the ray hits
shade that point to compute pixel (x,y)’s color
(perhaps simulating shadows)
• A ray is p+td: p is ray origin, d the direction

– t=0 at origin of ray, t>0 in positive direction of ray
– typically assume ||d||=1
– p and d are typically computed in world space
• This is easily generalized to give recursive ray tracing...

Recursive Ray Tracing
• We’ll distinguish four ray types:

– Eye rays: orginate at the eye
– Shadow rays: from surface point toward light source
– Reflection rays: from surface point in mirror direction
– Transmission rays: from surface point in refracted direction
• Trace all of these recursively. More on this later.

Writing a Simple Ray Caster
Raycast() // generate a picture

for each pixel x,y
color(pixel) = Trace(ray_through_pixel(x,y))
Trace(ray) // fire a ray, return RGB radiance

// of light traveling backward along it
object_point = Closest_intersection(ray)
if object_point return Shade(object_point, ray)
else return Background_Color
Closest_intersection(ray)
for each surface in scene
calc_intersection(ray, surface)
return the closest point of intersection to viewer
(also return other info about that point, e.g., surface
normal, material properties, etc.)
Shade(point, ray) // return radiance of light leaving

// point in opposite of ray direction
calculate surface normal vector
use Phong illumination formula (or something similar)
to calculate contributions of each light source

Ray-Surface Intersections
• Ray equation: (given origin p and direction d)
x(t) = p+td
• Surfaces can be represented by:
– Implicit functions: f(x) = 0
– Parametric functions: x = g(u,v)
• Compute Intersections:
– Substitute ray equation for x
– Find roots
– Implicit: f(p + td) = 0
» one equation in one unknown – univariate root finding
– Parametric: p + td - g(u,v) = 0
» three equations in three unknowns (t,u,v) – multivariate root finding
– For univariate polynomials, use closed form soln. otherwise use
numerical root finder
The Devil’s in the Details
• Solving these intersection equations can be tough...
– General case: non-linear root finding problem
– Simple surfaces can yield a closed-form solution
– But generally a numerical root-finding method is required
» Expensive to calculate
» Won’t always converge
» When repeated millions of times, errors WILL occur
• The good news:
– Ray tracing is simplified using object-oriented techniques
» Implement one intersection method for each type of surface primitive
» Each surface handles its own intersection
– Some surfaces yield closed form solutions:
» quadrics: spheres, cylinders, cones, elipsoids, etc…)
» polygons
» tori, superquadrics, low-order spline surface patches

Ray-Sphere Intersection
• Ray-sphere intersection is an easy case
• A sphere’s implicit function is: x2+y2+z2-r2=0 if sphere at origin
• The ray equation is: x = px+tdx
y = py+tdy
z = pz+tdz
• Substitution gives: (px+tdx)2 + (py+tdy)2 + (pz+tdz)2 - r2 = 0
• A quadratic equation in t.
• Solve the standard way: A = dx2+dy2+dz2 = 1 (unit vec.)
At2+Bt+C=0 B = 2(pxdx+pydy+pzdz )
C = px2+py2+pz2 - r2
• Quadratic formula has two roots: t=(-B±sqrt(B2-4C))/2
– which correspond to the two intersection points
– negative discriminant means ray misses sphere

Ray-Polygon Intersection
• Assuming we have a planar polygon
– first, find intersection point of ray with plane
– then check if that point is inside the polygon
• Latter step is a point-in-polygon test in 3-D:

– inputs: a point x in 3-D and the vertices of a polygon in 3-D
– output: INSIDE or OUTSIDE
– problem can be reduced to point-in-polygon test in 2-D
• Point-in-polygon test in 2-D:

– easiest for triangles
– easy for convex n-gons
– harder for concave polygons
– most common approach: subdivide all polygons into triangles
– for optimization tips, see article by Haines in the book Graphics Gems IV

Ray-Plane Intersection
• Ray: x=p+td
– where p is ray origin, d is ray direction. we’ll assume ||d||=1 (this simplifies the algebra later)
– x=(x,y,z) is point on ray if t>0
• Plane: (x-q)•n=0
– where q is reference point on plane, n is plane normal. (some might assume ||n||=1; we won’t)
– x is point on plane
– if what you’re given is vertices of a polygon
» compute n with cross product of two (non-parallel) edges
» use one of the vertices for q
– rewrite plane equation as x•n+D=0
» equivalent to the familiar formula Ax+By+Cz+D=0, where (A,B,C)=n, D=-q•n
» fewer values to store
• Steps:
– substitute ray formula into plane eqn, yielding 1 equation in 1 unknown (t).
– solution: t = -(p•n+D)/(d•n)
» note: if d•n=0 then ray and plane are parallel - REJECT
» note: if t<0 then intersection with plane is behind ray origin - REJECT
– compute t, plug it into ray equation to compute point x on plane

Projecting A Polygon from 3-D to 2-D
• Point-in-polygon testing is simpler and faster if we do it in 2-D
– The simplest projections to compute are to the xy, yz, or zx planes
– If the polygon has plane equation Ax+By+Cz+D=0, then

» |A| is proportional to projection of polygon in yz plane
» |B| is proportional to projection of polygon in zx plane
» |C| is proportional to projection of polygon in xy plane
» Example: the plane z=3 has (A,B,C,D)=(0,0,1,-3), so |C| is the largest and xy
projection is best. We should do point-in-polygon testing using x and y coords.
– In other words, project into the plane for which the perpendicular component of the
normal vector n is largest
• Optimization:
– We should optimize the inner loop (ray-triangle intersection testing) as much as
possible
– We can determine which plane to project to, for each triangle, as a preprocess

Interpolated Shading for Ray Tracing
• Suppose we know colors or normals at vertices
– How do we compute the color/normal of a specified point inside?
• Color depends on distance to each vertex

– Want this to be linear (so we get same answer as scanline algorithm such as
Gouraud or Phong shading)
– But how to do linear interpolation between 3 points?
– Answer: barycentric coordinates
• Useful for ray-triangle intersection testing too!

Barycentric Coordinates in 1-D
• Linear interpolation between colors C0 and C1 by t
C (1  t )C0  tC1
• We can rewrite this as
C  C0   C1 where    1
C is between C0 and C1   ,   [0,1]
• Geometric intuition:
– We are weighting each vertex by ratio of distances (or areas)
C0 C C1
 
  and  are called barycentric coordinates

Barycentric Coordinates in 2-D
• Now suppose we have 3 points instead of 2
C1
C
C2
C0
• Define three barycentric coordinates: , , 
C  C0   C1 C 2 where      1
C is inside C0C1C 2   ,  ,   [0,1]
• How to define , , and  ?

Barycentric Coordinates for a Triangle
• Define barycentric coordinates to be ratios of triangle areas
C1 Area CC1C 2 

Area C0C1C 2 
Area C0CC 2 
C  
 Area C0C1C 2 
 C2 Area C0C1C
 1    
Area C0C1C 2 
C0

Computing Area of a Triangle
• in 3-D
C
A B
– Area(ABC) = parallelogram area / 2 = ||(B-A) x (C-A)||/2

– faster: project to xy, yz, or zx, use 2D formula
• in 2-D
– Area(xy-projection(ABC)) = [(bx-ax)(cy-ay) – (cx-ax)(by-ay)]/2
project A,B,C to xy plane, take z component of cross product
– positive if ABC is CCW (counterclockwise)

Computing Area of a Triangle - Algebra
That short formula,
Area(ABC) = [(bx-ax)(cy-ay) – (cx-ax)(by-ay)]/2
Where did it come from?
ax bx cx cy
1
Area ( ABC )  a y by cy
2 ay
1 1 1
 bx c x c x a x a x bx 
   /2
 by
 by c y c y a y a y by  ax bx cx
(bx c y  c x by  c x a y  a x c y  c x a y  a x c y ) / 2
The short & long formulas above agree.
Short formula better because fewer multiplies. Speed is important!
Can we explain the formulas geometrically?
Computing Area of a Triangle - Geometry
Area(ABC) =[(bx-ax)(cy-ay) – (cx-ax)(by-ay)]/2
is a sum of rectangle areas, divided by 2.
(bx-ax)(cy-ay) (cx-ax)(ay-by)
[ ]
cy
? ay
+ /2 = /2 =
b
ax b x cx y
cy
ay
! !
/2 = = =
by
ax b x cx since triangle area = base*height/2
it works!
Uses for Barycentric Coordinates
• Point-in-triangle testing!
– point is in triangle iff , ,  > 0
– note similarity to standard point-in- N1
polygon methods that use tests of form
aix+biy+ci<0 for each edge i
 
 N2
N0
• Can use barycentric coordinates to interpolate any quantity

– Gouraud Shading (color interpolation)
– Phong Shading (normal interpolation)
– Texture mapping ((s,t) texture coordinate interpolation)

raycasting-1

Uploaded by

Copyright:

Available Formats

raycasting-1

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

raycasting-1

Uploaded by

Copyright:

Available Formats

Ray Casting

• If we can model photon bounces we can generate images

• Technique: follow each photon from the light source until:

Computer Graphics 15-462 2

Computer Graphics 15-462 3

Computer Graphics 15-462 4

Computer Graphics 15-462 5

• A ray is p+td: p is ray origin, d the direction

• This is easily generalized to give recursive ray tracing...

Computer Graphics 15-462 6

• We’ll distinguish four ray types:

Computer Graphics 15-462 7

Raycast() // generate a picture

Trace(ray) // fire a ray, return RGB radiance

Shade(point, ray) // return radiance of light leaving

Computer Graphics 15-462 8

Computer Graphics 15-462 10

Computer Graphics 15-462 11

• Latter step is a point-in-polygon test in 3-D:

• Point-in-polygon test in 2-D:

Computer Graphics 15-462 12

Computer Graphics 15-462 13

– If the polygon has plane equation Ax+By+Cz+D=0, then

Computer Graphics 15-462 14

• Color depends on distance to each vertex

Computer Graphics 15-462 15

Computer Graphics 15-462 16

• How to define , , and  ?

Computer Graphics 15-462 17

• Define barycentric coordinates to be ratios of triangle areas

Computer Graphics 15-462 18

– Area(ABC) = parallelogram area / 2 = ||(B-A) x (C-A)||/2

Computer Graphics 15-462 19

• Can use barycentric coordinates to interpolate any quantity

Computer Graphics 15-462 22

You might also like