Mathematical Preliminaries (Advanced Methods in Computer Graphics) Part 2

Lines and Planes

Lines and planes form integral parts of three-dimensional models and virtual worlds. A good understanding of line and plane equations and their analytical properties is essential for the development of many applications. For example, even a simple ray tracing application requires the computation of several line-plane intersections.

A straight line segment can be defined using two points, say P = (xp, yp, zp, 1) and Q = (xq, yq, zq, 1). The equation of this line in terms of a single parameter t can be expressed as

For any value of t between 0 and 1, the above set of equations gives the coordinates of a point on the straight line that lies between P and Q. We can also write the equation of this line segment using vector notation as follows:

whereThe above equation can also be used to represent a ray starting from the point p and having a direction given by the vector m. In this representation, m is generally a unit vector and t can have any positive value. The line given in Eq. 2.12 can be rewritten in the standard form by eliminating t:

Fig. 2.5 Computation of shortest distances of a point V from (a) a Line PQ and (b) a plane PQR

From the above equation, we immediately get the condition for the collinearity of three points

Using Eq. 2.12, we can determine the point S on the line PQ that lies closest to a general three-dimensional point V = (xv, yv, zv, 1). The shortest distance of the point V from the line is given by VS (Fig. 2.5), where S is the projection of the point V on PQ. The point S satisfies the condition that the line segments PQ and VS are orthogonal to each other. Using this condition, the parametric value t of the point S can be obtained as follows:

Substitution of the above value in Eq. 2.12 gives the coordinates of the point S. The shortest (or the perpendicular) distance D of the point V from the line PS is obtained as the distance | V—S| .

A plane in three-dimensional space is uniquely defined by three non-collinear points, or equivalently, by a point P that lies on the plane and its surface normal vector n. The equation of the plane in terms of the coordinates of the three points

is given by the determinant

From this equation of the plane, we get the condition for the coplanarity of four points P, Q, R, S:

The determinant is equivalent to (P—Q)*(r x s) + (R—S>(p x q). The condition in Eq. 2.18 also points to the fact that the vectors (Q—P) and (R—S) are coplanar. Thus we can rewrite the above equation using the following scalar triple product:

The surface normal vector n for the above plane can be obtained (similar to Eq. 2.2), by taking the cross-product of vectors Q—P and R—P. The components of n written as a column vector are given below:

The plane equation can be written in point-normal form as

which can always be simplified into a linear equation ax + by + cz + d = 0, or expressed using vector notation as

where d = —p*n. The point of intersection of this plane and a ray can be obtained by substituting the equation of the ray, r = q +1 m, in the above equation and solving for t.

The denominator in the above equation becomes zero when the line is orthogonal to n, i.e., parallel to the plane. The shortest distance D of the point v from the plane (see Fig. 2.5b) is given by the equation

The above term is also called the signed distance of the point v from the plane, as it assumes a positive value if v is on the same side as n, and a negative value otherwise. In general, if the plane’s equation is given in the normal form ax + by + cz + d = 0, where a2 + b2 + c2 = 1, the signed distance of the point v = (xv, yv, zv) is given by

 

Fig. 2.6 Two-parameter representation of a plane

The above expression can be thought of as the dot product between the vector (a, b, c, d) and (xv, yv, zv, 1), which is the homogeneous representation of v. Note that the unit normal vector to the plane is given by (a, b, c). Signed distances are extensively used in collision detection and point inclusion tests using bounding volumes.

Given three non-collinear points P, Q, R, we can have a parametric representation of the plane through the points as

where u and v are vectors along two sides of the triangle PQR (Fig. 2.6). An alternate form for the above equation that expresses any point on the plane as a linear combination of the vertices of the triangle is

For every point r(s, t) inside the triangle, the following properties hold:

In addition to the above conditions, points along the edge PQ satisfy the parametric equation t = 0. Similarly, the edge PR is characterized by the equation s = 0, and RQ by the property s +1 = 1.

Intersection of 3 Planes

An interesting problem commonly encountered while working with planes is the computation of the point of intersection (if it exists) where three planes meet. Even if it is guaranteed that no two planes are parallel, there can be three different configurations in which three planes can meet (Fig. 2.7).

Fig. 2.7 Three different configurations in which three non-parallel planes can meet

In the first configuration in Fig. 2.7, the lines of intersection formed by taking two planes at a time coincide with the result that we get a single line of intersection. In the second configuration, the lines of intersections are parallel even though the planes are not. It can be easily proven that if two lines of intersection are parallel, then the third is also parallel to the other two. This situation arises when the three surface normal vectors of the planes are all coplanar. In the third configuration, the non-parallel lines of intersection meet at a single point.

Let the three planes be given by the equations (see Eq. 2.22) r»ni = —di, (i = 1,2, 3) where nis are unit normal vectors. The directions of the three lines of intersection are then specified by the cross products n x n2, n2 xn3, and n3 x m. The point of intersection, if it exists, can be expressed as a linear combination of these three vectors (Goldman 1990):

The above point lies on all three planes. Substitution in the plane equations gives

The scalar triple products on the left side of the above equations are all equal (see Box 2.2). Equation 2.29 can now be written as

For the first two configurations shown in Fig. 2.7, the vectors n1, n2, n3 are coplanar, and the denominator of the above equation becomes zero. For the third configuration, the equation returns a valid point.