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;
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.
or P = C + t * D;
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
(2) dot(point_in_plane,plane_normal) = distance_to_origin
(Rationale: moving in the plane is motion perpendicular to the normal. The dot product of perpendicular vectors is zero.)
or dot(P,N) = k
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
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
or dot(C+t*D,N) = k
dot(C+t*D,N) = dot(C,N) + t*dot(D,N) = k
This is now just a linear equation in t, with solution:
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!
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:
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.
- 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.
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
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:
so (C.z+t*D.z)^2 + k - (C.x + t*D.x)^2 - (C.y + t*D.y)^2 = 0
c = C.z*C.z + k - C.x*C.x - C.y*C.y
We can now apply the quadratic equation, exactly as before.
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
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 ))
This gradient trick is handy way to extract normals for any surface that you have an equation for!
or N = +- normalize(vec3( -2*P.x, -2*P.y, + 2*P.z ))
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:
For these more complex objects, we'll need another approach--typically, we break the object down into simpler objects.
- 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.