Mathematical operations on points, vectors and matrices are needed for processing information related to geometrical objects. Even in the modelling of a simple threedimensional scene, vectors and matrices play an important role in specifying an object’s position, orientation and transformations. Methods for lighting, intersection testing, projections, etc., use a series of vector operations.
Parametric representations are often used in methods involving geometrical primitives. This topic deals with analytical equations of lines, planes and curves, and their applications in geometrical computations. Properties of three-dimensional transformations are discussed using their matrix representations. The topic also introduces concepts such as signed area and distance, affine combinations of points and barycentric coordinates.
Points and Vectors
A point is the most fundamental graphics primitive, and is represented in a threedimensional Cartesian coordinate system by the 3-tuple (x, y, z), where x, y, z denote the distances of the point from the origin of the system along the respective axes directions. In graphics, we commonly use an extended coordinate system, where the same point is denoted by the 4-tuple (x, y, z, 1). This representation is called the homogeneous coordinate system. Homogeneous coordinates provide a unified and elegant framework for representing different types of transformations and projections that are commonly applied to both points and vectors (Box 2.1).
Box 2.1 Homogeneous Coordinate System
A 3D point given by homogeneous coordinates (a, b, c, d) where d is nonzero, has an equivalent representation in Cartesian coordinates given by (a/d, b/d, c/d).
The 4-tuple (a, b, c, 0) denotes a point at infinity that has associated with it a directional vector (a, b, c).
The many-one mapping from homogeneous to Cartesian space is shown below:
Fig. 2.1 Geometric interpretation of (a) subtraction of a point from another, (b) addition of two points given in homogeneous coordinates, and (c) addition of two vectors
We will now look at the geometrical interpretations of operations of addition and subtraction on homogeneous coordinates. When we subtract a point Q = (xq, yq, zq, 1) from the point P = (xp, yp, zp, 1), we get a vector P—Q which has components (xp—xq, yp—yq, zp—zq, 0). This vector originates from the point Q and is directed towards the point P, and is denoted as QP. The direct addition of two points P and Q is not a geometrically valid operation, as it can produce different results depending on the coordinate reference frame used. If we use the homogeneous coordinate representation of P and Q as given above, the operation of addition yields (xp + xq, yp + yq, zp + zq, 2), which is actually the midpoint of the line segment PQ (Fig. 2.1b). Points can, however, be added in a special way called the affine combination (see Sect. 2.7) that gives a well-defined point. The addition of two vectors p = (xp, yp, zp, 0) and q = (xq, yq, zq, 0) is always a valid operation that produces another vector p + q = (xp + xq, yp + yq, zp + zq, 0). This vector is along the diagonal of the parallelogram formed by p and q.
Fig. 2.2 (a) Dot-product and cross-product of two vectors u,v. (b) Projection of a vector s on a unit vector u. (c) Reflection of a vector s with respect to a unit vector n
Fig. 2.3 The normal vector and area of a triangle specified using vertex coordinates can be computed with the help of two vectors defined along the edges
Like addition, the operations of negation and scalar multiplication should also be carefully performed on points represented in homogeneous coordinates. It can be seen that the operation of negation given by — P = (—xp, —yp, —zp, —1) in effect yields the same point P. In general, the operation of scalar multiplication defined as sP = (sxp, syp, szp, s) for any non-zero value of s, gives the same point P.
We will often require the computation of angles between two vectors. This and other operations, such as projection, require vectors to be normalized first. The normalization of a vector is the process of converting it to a unit vector that has a magnitude 1. In order to normalize a vectorp = (xp, yp, zp, 0), we simply divide each element by the vector magnitude d given by
Two important vector operations used in graphics are the dot-product and the cross-product. Given two unit vectors u = (xu, yu, zu, 0) and v = (xv, yv, zv, 0), their dot-product u*v = xuxv + yuyv + zuzv is equal to the cosine of the angle between the vectors. The cross-product u x v = (yuZv — yvZu, Zuxv — Zvxm xuyv — xvyu, 0) is a vector perpendicular to both u and v, so that u, v, u x v form a right-handed system (Fig. 2.2). Obviously, this operation is useful for computing the surface normal vector of a planar element defined by two vectors u and v. The magnitude of u x v (denoted by |u x v|) gives twice the area of the triangle formed by the two vectors (Figs. 2.2a and 2.3). For unit vectors, |u x v| is also equal to the sine of the angle between the two vectors (Box 2.2).
Box 2.2 Vector Products
The following facts are commonly used in computations involving vectors:
If u is a unit vector, then «•« = 1.
If u is perpendicular to v, then u*v = 0.
If u is parallel to v, then u x v = 0. In particular, u x u = 0.
The magnitude of u x v is the area of the parallelogram formed by u, v.
The scalar triple product u*(v x w) gives the volume of the parallelepiped formed by the vectors u,v and w. The value does not change with a cyclic permutation of the vectors: u*(v x w) = v*(w x u) = w*(u x v).
The vector triple product u x (v x w) is the same as (u*w)v — (u*v)w.
The magnitudes of the dot and cross products of two vectors u and v are related by the equation: |u x v|2 = |u|2|v|2 — (u*v)2.
We saw in the previous paragraph that both the dot and the cross products of two unit vectors can give us the information about the angle between them in the form of trigonometric functions cos() and sin() respectively. Note that the function acos(u*v) returns the angle in the range [0, i ] only. Neither can we use asin(|u x v|) to determine the angle correctly because the resulting value will always be in the restricted range [0, i /2] (even though asin() returns a value in the range [—h/2, h/2], since |u x v| is always positive, so would be the result). We will explore ways to compute the true angle in the range [— , ] in Sect. 2.2.
If we represent the vertices of a triangle by points A = (xa, ya, za), B = (xb, yb, zb), C = (xc, yc, zc ), the surface normal vector and the area of the triangle can be obtained from the cross product of two vectors u, v constructed as shown in Fig. 2.3.
The normal vector n of the triangle in Fig. 2.3 has components (xn, yn, zn) given by
The above vector is the same as u x v. The area of the triangle ABC can be computed from the above components of the normal vector as follows:
Let us turn our attention to another important vector operation called projection. A vector s can be projected onto a unit vector n, with the projected vector given by (s»n)n (see Fig. 2.2b). This also implies that the length of the projection of s on a unit vector n is s*n. We can use this fact to express any vector s in terms of its projections along three mutually orthogonal unit vectors u,v, and w as
If s is also a unit vector, then the terms s*u, s*v, s*w are called the direction cosines of the vector in the coordinate space spanned by the unit vectors u, v, and w. In a new coordinate space defined by u, v, and w, the components of any vector s are therefore given by (s»u, s*v, s»w).
The reflection of the vector s with respect to a unit vector n is the vector r that lies on the plane containing s and n as shown in Fig. 2.2c, such that the angle between r and n is the same as the angle between s and n. The reflection vector is commonly used in lighting calculations and ray tracing, where s stands for the vector towards a light source, and n is the surface normal vector. The vector components of r can be computed using the formula
Signed Angle and Area
In the previous section, we noted that the computation of the angle between two vectors using acos() or asin() functions always yielded only positive values in the range [0, i ]. One may suggest using the function atan2(|u x v|, u*v). This form of computation of angle has the advantage that neither u nor v needs to be normalized. However, this function also returns values in the positive range [0, ] only, because the numerator | u x v| is always positive. The difference between the positive and negative sense of angle is completely view dependent. For vectors residing on the two-dimensional xy-plane, the direction to the viewer is always implied to be the + z direction. In a general three-dimensional case, we need to specify this view direction in order to determine the signed angle in the range [— , ] between two given vectors.
If we denote the view direction by w (Fig. 2.4), the angle measured from u to v is positive if the sense of rotation from u to v is anticlockwise when viewed from w. In other words, if w is in the same direction as u x v, then the angle is positive, otherwise negative. We can now define the signed angle between u and v with respect to the view vector w as
Fig. 2.4 The angle between two vectors and the area of the triangle formed by the vectors can have either a positive or a negative sign depending on the orientation of the vertices with respect to a given direction
If u and v are two-dimensional vectors on the xy-plane, we can have the following simplified form for the signed angle:
We can also define a view-dependent sign for the area of a triangle based on the above concept. If the view vector w has components (xw, yw, zw, 0), Eq. 2.3 now gets modified as follows:
where xn, yn, zn are computed from the vertex coordinates using Eq. 2.2.
For a triangle on the xy-plane, the right-hand side of the above equation reduces to zn/2. Thus the signed area of a triangle with vertices A = (xa, ya), B = (xb, yb), C = (xc, yc) is
The signed area is positive only if the vertices A, B, C are oriented in an anticlockwise sense with respect to the view direction. The signed area of a triangle is useful in determining if a point is inside the triangle or not. This method is discussed in detail in Sect. 2.8. The concepts presented above are also used for defining the orientation of three points. Three points A, B, C are said to be oriented in the anticlockwise sense with respect a direction w if
If the above condition is satisfied, the three points are said to make a left turn when viewed from the direction w. With reference to Fig. 2.4, the equivalent condition in vector notation is (u x v)*w > 0. On the xy-plane, the three points make a left turn if
The reversal of the inequality implies a right turn. The points are collinear if the above expression yields 0. In the next section we will use vector notations and related operations to get concise forms of line and plane equations.