NOTE : vectors are represented by capitals, scalars are represented by lower case. The x, y, and z components of a vector are denoted by '.x', '.y', and '.z' respectively. For example, the component of the vector V would be represented by 'V.x'. The function the 'DotProduct' will be represented by '|.|' in equations.
This information describes the process by which you intersect a ray with
a triangle. Triangles lie on planes, so planes are used heavily. If you
need to, check out 'Polygons and the Plane Equation'.
The Method
The point at which the ray intersects the plane is denoted by the vector I. Since I is a vector, and therefore has 3 components (x, y, and z), it cannot be calculated directly, because you have 3 unknowns. The ray vector is R, the location of the camera is L. Below is an equation used to calculate I (indirectly, - you'll see) :
This means that the scalar value t must be calculated. In the info titled 'Polygons and the Plane Equation' it states that the planes distance ('d') can be calculated with the formula
where N is the surface normal, and P is a point on the plane. The intersection point lies on the plane, so the following equations are therefore satisfied :
This leaves only one unknown, - t. When the equation is rearranged you will end up with the following equation (This is quite nasty and can take a while).
This will allow you to calculate t, which in turn will allow you to calculate
I. If 'N|.|R' is 0, then the ray does not hit the plane. Check this first,
to avoid a possible divide by 0 error. If the value of t is negative, it
means that I is behind the camera. You may also want to check for this.
If the camera is located at the origin, the 'N|.|L' part can be left out
altogether. Thats about it.
Checking if I is on the Triangle
The above process will intersect a ray with a plane. However, planes extend
through 3d space to infinity. If you intend to raytrace using triangles
(I have not found polygons with more than 3 vertices useful) you will need
to check to see if I is on the triangle (the above equations will generate
intersections which are not necessarily on the triangle). To do this, I
would set up 3 planes passing through each edge of the triangle.
In the section 'Polygons and the Plane Equation' I described how you could
check which side of a plane a point is on. I also described how you generate
the surface normal, and d. To generate the surface normal, two edges of
the polygon are used for the vectors U and V. In this case (setting up
the 'edge' planes) you would use the edge for one vector, and the surface
normal for the other. You would then check which side the opposite vertex
was on. (if you are working with the edge linking vertices A and B of a
triangle, the opposite vertex would be C) If it was on the wrong side,
(eg if the the dotproduct of the normal and the opposite vertex gave a
value smaller than d) you would reverse the plane. This way, all of the
'edge' planes (one 'edge' plane for each edge of the triangle) would give
a value greater than d should the point be within the boundaries of the
triangle.
Putting All of This to Use
Described in the 'Perspective Projection' dox, under the title 'Reverse
Perspective Projection', a process is described by which rays can be generated
given a screen coordinate. For each pixel, you generate a ray. You then
use the methods described above to check for intersections with each surface,
for each pixel on the screen. This is very slow however, since most triangles
will not generate intersections (once checked to see if they are on the
triangle) for every pixel on the screen, so a lot of time will be wasted,
- optimizations can be made.
Email suggestions, comments, death threats, questions, etc to :
mrmeanie@easynet.co.uk