Skip Ahead: Raytracing: derivations & c++ code
This discussion assumes the reader understands high school algebra and vectors.
We begin with the equation of a line.
Let P, Po and V be vectors, and let 't' be a scalar multiplier.
Note:
For the purpose of this discussion all vectors have 3 elements ( x, y, z ).
When we want to reference the components of a vector, we will use the
programming convention of using a period ('.') to denote a subfield;
ie. the components of vector A, ( x, y, z ) will be referenced as
( A.x, A.y, A,z ).
Po ( P subscript zero ), pronounced 'P Oh', denotes the initial point,
'Point initial, a fixed point in space.
V is a unit vector, conceptually it's a little arrow, one unit in length,
it's tail located at Po, and points along the line passing through the points
Po and ( Po - V ), the latter being the vector ( Po.x - V.x, Po.y - V.y,
Po.z - V.z )
The parametric equation of our line is:
P = Po + t * V
This defines a line, an infinite number of points:
all the points generated from the expression
( P assumes all the values of ( Po + t * V ) ) as
't' varies from negative infinity to positive infinity.
The equation of a plane is:
A ( x ) + B ( y ) + C ( z ) = D
where ( x, y, z ) is a point on the plane and ( A, B, C )
is a vector perpendicular to the plane, and 'D' is a scalar,
a constant for any given plane.
We will call the two vectors 'Pop' and 'N', respectively; 'Pop'
for 'Point on Plane' and 'N' for 'Normal'. ( 'Normal' is used
universally in graphics to mean 'the line or vector perpendicular
to the planar surface' ).
Now we begin ( a job well begun is half done, were half done; now the fun begins ):
The intersection
of the line: P = Po + t * V
and the plane: A ( X ) + B ( Y ) + C ( Z ) = D
is: A ( P.x ) + B ( P.y ) + C ( P.z ) = D by substitution.
A ( Po.x + t * V.x ) + B ( Po.y + t * V.y ) + C ( Po.z + t * V.z ) = D
well that's messy,
let's replace: ( Po.x, Po.y, Po.z ) with ( x, y, z )
and replace: ( V.x, V.y, V.z ) with ( a, b, c ).
Thus we have: A ( x + a * t ) + B ( y + b * t ) + C ( z + c * t ) = D
or: A ( a * t + x ) + B ( b * t + y ) + C ( c * t + z ) = D
or: A ( at + x ) + B ( bt + y ) + C ( ct * z ) = D
All these symbols represent scalars, and briefly, we will we pretend to forget everything
else they represent, and just do the algebra, solving for 't'.
( If we're neat, were never make mistakes. )
Ok, here we go: A ( at + x ) + B ( bt + y ) + C ( ct + z ) = D ( repeating )
( A * at + A * x ) + ( B * bt + B * y ) + ( C * ct + C * z ) = D
( A * at + B * bt + C * ct ) + ( A * x + B * y + C * z ) = D
t * ( A * a + B * b + C * c ) + ( A * x + B * y + C * z ) = D
t * ( A * a + B * b + C * c ) = D - ( A * x + B * y + C * z )
D - ( A * x + B * y + C * z )
t = ---------------------------------------
( A * a + B * b + C * c )
or if we prefer:
( A * x + B * y + C * z ) - D
t = - ---------------------------------------
( A * a + B * b + C * c )
Thus, for some point, perhaps the position of a shower head, perhaps the point
at the tip of Durer's sighting device, or perhaps we close one eye, and stare
at a point, a spot on a table top, and concentrate, our (open) eye is at some
point Po = (x,y,z) and we stare, in some direction, call it vector V = ( a, b,c )
at a spot on a table top on the plane A ( X ) + B ( Y ) + C ( Z ) = D.
Where's is that damn spot?
The spot is some point, P, along the line
P = Po + t V where we know Po, and V. If only we knew 't'....
Oh, we solved for 't', so we have Po, t, and V so that's it were done.
Given the line: P = Po + t * v
and the plane: A ( X ) + B ( Y ) + C ( Z ) = D
they intersect at: P = Po + V * t
_ _
| |
| ( A * x + B * y + C * z ) - D |
or substituting: P = Po + V * | - --------------------------------------------- |
| ( A * a + B * b + C * c ) |
|_ _|
where ( x, y, z ) <---> Po
( a, b, c ) <---> V
( A, B, C ) <---> N, the normal to the plane
( X, Y, Z ) is any point on the plane
and P is the spot, the point of intersection.
( '<--->' means 'is interchangeable with' )
Well, except for the fact it's a big and klutzy equation and it just looks messy and the we
can easily lose track of what it all means.
We've reduced it to one equation, which was our goal, but it's more convenient to deal with
the earlier, easier to remember and work with:
1) P = Po + t * V
( A * x + B * y + C * z ) - D
2 ) t = - ---------------------------------------
( A * a + B * b + C * c )
N * Po - D
or: P = Po + t * V where t = - --------------- and D = N * Pop
N * V
This allows you, to paraphrase Henry Ford, to raytrace any object you to, as long it's a plane.
The equation of the Plane is: A ( X ) + B ( Y ) + C ( Z ) = D
the equation of a circle is: x^2 + y^2 = r^2
the equation of a sphere is: x^2 + y^2 + z^2 = r^2
or x^2 + y^2 + z^2 = d
Let P = ( X, Y, Z )
and Po = ( x, y, z )
and V = ( a, b, c )
The parametric equation of a line:
P = Po + t * V
represents: X = x + t * a
Y = y + t * b
Z = z + t * c
So the two equations we need to find the intersection of a line and a sphere is:
The line: P = Po + t * V
the sphere: ( X ) ^ 2 + ( Y ) ^ 2 + ( Z ) ^ 2 = ( r ^ 2 )
yielding: r ^ 2 = ( x + t * a ) ^ 2 + ( y + t * b ) ^ 2 + ( z + t * c ) ^ 2
0 = ( x + t * a ) ^ 2 + ( y + t * b ) ^ 2 + ( z + t * c ) ^ 2 - r ^ 2
0 = ( a^2 t^2 + 2ta + x^2 ) +
( b^2 t^2 + 2tb + y^2 ) +
( c^2 t^2 + 2tc + z^2 ) - r ^ 2
0 = ( a^2 + b^2 + c^2 ) t^2 + ( 2*( ax + bx + cz ) t ) + ( x^2 + y^2 + z^2 - r^2 )
Let A = ( a^2 + b^2 + c^2 ); B = ( ax + bx + cz ); C = ( x^2 + y^2 + z^2 - r^2 )
substituting: 0 = A t ^ 2 + 2 B t + C
which is
of the form: a x ^ 2 + 2 b x + c = 0 which we can solve using the quadratic equation.
let me momentarily change from upper case to lower case
( but the lower case variables a,b,c below are NOT the a,b,c in the equations above )
a t ^ 2 + 2 b t + c = 0
__________________
/
-b (+/-) \/ b^2 - 4 * a * c
where t = ----------------------------------------- ( quadratic equation )
2 * a
Therefore the solution, the intersection of a line and a sphere is:
Given Po the eye at position, sighting in the direction V,
the point of intersection is Point 'P' as follows:
Po <---> ( x,y,z); V <---> (a,b,c); 'r' is the radius of the sphere
A = ( a ^ 2 + b^2 + c ^ 2 )
B = ( a x + b y + c z )
C = ( x^2 + y^2 + z^2 - r^2 )
___________________
/
-B (+/-) \/ B^2 - 4 * A * C
t = ------------------------------------------
2 * A
P = Po + t * V
( finis )
![[home.gif]](home.gif)
Return: My humble Home Page