Parametric Object Geometry: Raytrace Intersection Tests

2010, Dr. Lawlor, CS 481/681, CS, UAF

In a uniform transparent medium, light travels in straight lines.

Straight lines have a very simple equation:

(1)	position_along_line = point_on_line + some_float * line_direction;
or	P = C + t * D;

This is called a parametric equation, because "some_float" is a free parameter. Raytracing is a way to draw arbitrary objects by solving for this floating-point parameter.

Raytracing Planes

For example, consider a plane. If we specify the plane using a surface normal vector "plane_normal", the distance along this normal from the plane to the origin, then points on a plane satisfy this equation:

(2)	dot(point_in_plane,plane_normal) = distance_to_origin
or	dot(P,N) = k

(Rationale: moving in the plane is motion perpendicular to the normal. The dot product of perpendicular vectors is zero.)

If we want to find when the plane and line intersect, we just set:

	point_in_plane = position_along_line

This lets us substitute equation (1) into equation (2), giving:

	dot(point_on_line + some_float * line_direction,plane_normal) = distance_to_origin
or	dot(C+t*D,N) = k

which we have to solve for "some_float" (t). It's not immediately clear how to do this, because t is trapped inside the dot product. But linearity to the rescue! It turns out that dot product distributes over vector addition and scalar multiplication, so

	dot(C+t*D,N) = dot(C,N) + t*dot(D,N) = k

This is now just a linear equation in t, with solution:

	t=(k-dot(C,N))/dot(D,N)

We can then plug this parameter t back into the ray equation (1) to get the ray/line intersection point.

Note that if dot(D,N)==0, then the ray is parallel to the plane, and there is no solution for t. Also, depending on the orientation of the camera and plane, the camera ray may hit the plane behind the viewer, at negative t values. So in practice, you compute t as above, then check to see if it's a reasonable intersection. If so, we draw the object.

To actually draw the object, we also need a surface normal. This is really easy for a plane, because a plane only has one fixed value for its surface normal, and we've already had to specify it just to define the plane!

Raytracing Spheres

Points on a sphere satisfy this equation:

(3)	length(point_on_sphere) = radius

Annoyingly, computing length takes a square root, which makes this equation difficult to solve. However, if we square both sides of this equation (radius is positive, so this will always work), we can express the length-squared as a dot product:

	radius^2 = length(point_on_sphere)^2 = dot(point_on_sphere,point_on_sphere)

Now we've reduced the square root business to just dot products. With shorter symbol names:

	r*r = dot(P,P)

Substitute in the ray equation (1) to find the ray/line intersection point:

	r*r = dot(C+t*D,C+t*D) = dot(C,C) + 2*dot(C,t*D) + dot(t*D,t*D)

	r*r = dot(C+t*D,C+t*D) = dot(C,C) + 2*t*dot(C,D) + t*t*dot(D,D)

This is a quadratic equation in t, with constants c=dot(C,C)-r*r, b=2*dot(C,D), and a=dot(D,D). The t values are then a problem from high school algebra:

	t = (-b +- sqrt(b*b-4.0*a*c))/(2.0*a)

Note that there can be:

Two solutions, corresponding to the + and - versions of the square root, which are the ray entering and leaving the sphere respectively. Some of those solutions may be behind the camera!
Exactly one solution, if b*b-4.0*a*c==0. This corresponds to the ray just barely grazing the surface of the sphere.
No solutions, if b*b-4.0*a*c<0. This corresponds to the ray missing the sphere entirely.

A sphere's normal is very simple--draw a line from the center point (often the origin) to the intersection point you just computed. That's the normal vector.

Raytracing Hyperboloids

Let's say we're looking for 3D points that satisfy the following odd equation (a hyperboloid)

	z^2 + k = x^2 + y^2

Substituting in the ray equation, we get:

	(C.z+t*D.z)^2 + k = (C.x + t*D.x)^2 + (C.y + t*D.y)^2
so	(C.z+t*D.z)^2 + k - (C.x + t*D.x)^2 - (C.y + t*D.y)^2 = 0

We've got to solve this for t. Each of the (C+t*D) terms expands out to C*C+2*t*C*D + t*t*D*D, so we have a quadratic with:

	c = C.z*C.z + k - C.x*C.x - C.y*C.y
	b = 2.0*(C.z*D.z - C.x*D.x - C.y*D.y)
	a = D.z*D.z-D.x*D.x-D.y*D.y

We can now apply the quadratic equation, exactly as before.

The surface normal of this shape is a little trickier to compute. One way to compute the surface normal is to write the defining equation as a space-filling function:

	f(P) = P.z^2 + k - P.x^2 - P.y^2

The shape itself consists of the set of points where f(P)=0. But the gradient of f points along the surface normal:

	N = +- normalize(vec3( df / dP.x, df / dP.y, df/dP.z ))
or	N = +- normalize(vec3( -2*P.x, -2*P.y, + 2*P.z ))

This gradient trick is handy way to extract normals for any surface that you have an equation for!

Raytracing in General

Given a function f(P), we can raytrace the 3D surface f(P)=0 by plugging in the ray equation f(C+t*D) and solving for t.

Once we find a point on the surface, we can compute surface normals from the gradient of f.

The only thing this *doesn't* work for is:

Objects whose function is too complex to solve analytically. Unfortunately, even simple functions like sin(x)-x=k have no elementary inverse function.
Objects that don't have a simple equation. For example, I can trivially write the equation for a sphere, a cube, etc; but I can't write one equation for the shape of my cat.

For these more complex objects, we'll need another approach--typically, we break the object down into simpler objects.