Re: Ray tracing math help
Re: Ray tracing math help
Sounds like a request for a crash course in vector geometry! :-)
I'm not sure what your math level is, so first let's go through some terminology.
A vector is a line segment in space which has both a length and a direction. You can think of it as a movement from one point in space to another but with one significant difference; a "movement from one point in space to another" implies a fixed location in that space, but a vector has no fixed location, only distance and direction. (Also not all vectors represent "movement". For example, they can represent forces or electric fields.) In spite of this, it is convenient to use a notation in which a vector can be defined by two points let's say A and B. The vector which is directed from point A to point B is written as AB (normally with an arrow to the right written over the top). This vector moves in some direction on the x, y, and z axis, which is conveniently written as a triplet. For example, if A is (5, 9, 20) and B is (7, 9, 17) then AB = <7-5, 9-9, 17-20> = <2, 0, -3>.
The formula for a plane can be expressed as a single point on the plane and a vector which is normal to the plane.
"Normal to the plane" means that any angle you measure between the vector and the plane as you rotate around the intersection of the vector and the plane is 90 degrees. A vector which is NOT "normal" to a plane but which can still intersect the plane at a single point (as opposed to being parallel to the plane or lying on it) will, as you rotate around the point, have two places where you can measure an angle of 90 degrees, but all other places will be either less than or greater than 90.
Now think of the three points in your triangle. Let's call them A, B, and C. Imagine two vectors, one from point A to point B, and one from point A to point C. Call these two vectors AB and AC. They are parallel to your plane because they are (effectively) two edges of your triangle.
These two vectors can be used to find a third vector which is normal to the plane containing them. To do so, you need to calculate the "cross-product" of the two vectors. This is written as AB X AC. There's an easy way to visualize the cross product: Imagine placing your right forearm along AC so that AC is pointed toward your elbow and your fist is holding the point A. With that, AB is either emering from your palm or from the back of your hand. Next, twist your forearm (if needed) so that you can point your fingers in the same direction as AB. Now, without otherwise moving your hand, stick out your thumb. The vector which results from the cross-product points in the same dirction as your thumb, with a 90 degree angle between it and AB, and also with a 90 degree angle between it and AC.
To calculate the cross-product, we need two more definitions.
First, the "unit vectors" i, j, and k are needed. These are simply just vectors whose length is one and which are parallel to the x, y, and z axis. Or more formally, i = <1, 0, 0>, j = <0, 1, 0> and k = <0, 0, 1>.
Second, determinants are need. These are widely used in matrices. A two-by-two determinant is written as
Code:
| x1 x2 |
| x3 x4 |
This a non-vector quantity (a scalar) which is equal to x1 * x4 - x2 * x3.
This is not to be confused with matrix notation. Normally, a determinant is enclosed on the left and right by vertical bars and a matrix is enclosed on the left and right by large square brackets.
To compute the cross product AB X AC, imagine that AB = <ABx, ABy, ABz> = <Bx - Ax, By - Ay, Bz - Az> and use the same notation for AC. With this notation, by ABx what I mean is "the x component of AB". I don't mean "AB times x". We need the three-by-three determinant
Code:
| i j k |
|ABx ABy ABz|
|ACx ACy ACz|
Determinants get increasingly messy to compute as they get larger. A couple of different but equivalent ways to compute a three-by-three determinant exist. The one we want expresses it as the sums and differences of three two-by-two determinants as follows:
Code:
|ABy ABz| |ABx ABz| |ABx ABy|
|ACy ACz| * i - |ACx ACz| * j + |ACx ACy| * k
Note this is itself a vector. The determinants give you three scalar quanities, one each for the x, y, and z axes. (Don't accidentally drop the negative on the j term!)
Code:
<|ABy ABz| |ABx ABz| |ABx ABy|>
AB X AC = <|ACy ACz|, -|ACx ACz|, |ACx ACy|>
Let's say N = AB X AC. This is you a normal vector for your plane. Now you can use any of the three points on the triangle, say your (x1, y1, z1) to finish off the formula for the plane.
Nx * (x - x1) + Ny * (y - y1) + Nz * (z - z1) = 0.
The next step is to find the point where your ray from the camera through P(x,y,z) intersects the plane.
First, find the formula for the line through C and P.
In 3D space, a line can be specified by a point on the line and a vector parallel to the line. The vector V = CP is parallel to the line and P is on it. The forumla for a line in space is
(x - Px) / Vx = (y - Py) / Vy = (z - Pz) / Vz
if none of Vx, Vy, and Vz are zero. For any which are zero, remove the corresponding quotient from the equation and replace it with x = Px (if for example Vx is zero).
To find the point where the ray intersects the plane you now need to solve the simultaneous system of equations
Nx * (x - x1) + Ny * (y - y1) + Nz * (z - z1) = 0
(x - Px) / Vx = (y - Py) / Vy = (z - Pz) / Vz
for x, y, and z (keeping in mind the subsitution for any zero V component). You can use Gaussian elimination for this. This is reasonably straightforward but is really tedious.
That will give you the point I (Ix, Iy, Iz).
The distance between P (Px, Py, Pz) and I is the square root of (Px - Ix) ^ 2 + (Py - Iy) ^ 2 + (Pz - Iz) ^ 2.
I'm not sure about the best way to determine if I is inside the triangle. You could find the center of the triangle and the equations of the three lines which pass through the three pairs of vertices of the triangles. Then find the intersection of the line from the point I to the center with the three lines. If the point I comes between the center and the intersection with the triangle edge for any one of the three lines, I is inside the triangle.
