| Linear Mappings and Matrices Updated 10 Jul 2001 | Upper levels: - QuArK Information Base - 4. The Source Code - 4.8. Math Background

4.8.2. Linear Mappings and Matrices | [ Prev - Up - Next ]

Linear mappings are functions taking vectors as input and producing vectors as output, which provide an easy-to-compute implementation of many intuitively natural transformations of objects, such as size-change (scaling) and rotation. This introduction assumes a basic grasp of vectors, including vector addition and scalar multiplication, plus trigonometry for rotations.

Index

- - Axes and Bases (10 Jul 2001)
- - Mappings & Matrices (10 Jul 2001)
- - Examples (10 Jul 2001)

Axes and Bases | tiglari - 10 Jul 2001 | [ Top ]

One of the most important aspects of vector spaces (sets of vectors with their associated math operations such as\ addition) is that they have 'bases', or coordinate systems. A basis is just three vectors, taken in a definite order, which don't lie on the same line or plane. We are usually interested only in bases where the vectors are of length 1, and are perpendicular to each other; these are called 'orthonormal bases' if you want a technical term for them. The most familiar (orthonormal) basis is:
    xa = <1, 0, 0>
    ya = <0, 1, 0>
    za = <0, 0, 1>
(In vector algebra books these are often called i, j and k; I'm using xa, ya and za for x-axis, y-axis and z-axis.) The most important fact about bases is that any vector can be expressed as a sum of (scalar) products of the basis vectors by numbers. In the case of the standard basis [xa, ya, za], we have the obvious identity:
    x*xa + y*ya + z*za = <x, y, x>
However it's also true for arbitrary bases, and even more usefully, if [xr, yr, zr] is a randomly chosen basis, we can get the coordinates of any vector v with respect to that basis by using the dot product:
    v = (xr*v)*xr + (yr*v)*yr + (zr*v)*zr
(Possibly a bit confusingly, the '*' inside the parentheses represents the dot product operation two vectors, yielding a number, while the '*' outside the parentheses represents the scalar product, multiplying a vector by a number).

Mappings & Matrices | tiglari - 10 Jul 2001 | [ Top ]

Technically, a linear mapping is a function making vectors from vectors that obeys this law, where L is the mapping, a and b are numbers (scalars), and v and w are vectors:
    L(a*v + b*w) = a*L(v) + b*L(w)
It is an immedidate consequence of the definition that if [x, y, z] are the coordinates of a vector v w.r,t, a basis xb, yb, zb, then the result of L on v can be predicted from v's coordinates, plus what v does to the vectors of the basis:
    L(v) = x*L(xb), y*L(yb), z*L(zb)
We can say that [L(xb), L(yb), L(zb)] are a 'replacement basis' for the original basis (this isn't a standard term, but I think it fits). There's one respect in which a replacement basis isn't like real basis: its vectors can all lie in the same plane or line, or even be 0 Not only does every linear mapping produce a replacement basis, but the reverse is true: if we pick three vectors at random, [xr, yr, zr], we can make a linear mapping out of them by choosing a (real) basis, and then transforming a vector v with coordinates <x, y, z> as follows:
    M(v) = x*xr + y*yr + z*zr
If you crank thru the algebra you'll see that M is a linear mapping. So for a given basis we've decided to use, every linear mapping produces a (unique) replacement basis, and every replacement basis produces a (unique) linear mapping. This is very nice, because a linear mapping is a sort of abstract transformation of space, but a replacement basis is just a sequence of vectors. And if we're doing 3D math, it will just be nine numbers. And there is a convenient package for delivering these numbers in, a matrix. A matrix is in general just a grid of numbers, m rows and n columns, for basic 3D math we're interested in 3x3 matrices. In the standard presentation, the first, second and third columns of the matrix represent the first, second and third members of the replacement basis (important: columns, not rows). QuArK python conforms to this in that if the arguments of quarkx.matrix(...) are three vectors, they will be taken to be the columns of the matrix (whereas if the input is tuples or a string, it's row-by-rlow). Then the rules of matrix multiplication have been set up so that if M is a matrix and v is a vector (thought of as a single column, constituting a 1-column matrix), M*v is the result of applying the mapping represented by M to v. Technically, these columns (both the columns of the matrix representing the linear mapping and the single columns representing the vectors), are taken to be the coordinates of vectors (the input and output vectors, and the replacement basis vectors) with respect to some basis. But in QuArK Python (and other computational vector and matrix sytems) we don't have to worry about this kind of thing, since we're taking the standard basis as the fundamental one. of the result of applying the mapping designated by M to the vector v (the vectors are treated as 1-column matrices). Furthermore, if M and N are matrices, then M*N is the matrix for the mapping derived by first applying N's mapping, then M's. Most of the time the basis we're most interested in is the standard one, which I'll repeat here:
    xa = <1, 0, 0>
    ya = <0, 1, 0>
    za = <0, 0, 1>

Examples | tiglari - 10 Jul 2001 | [ Top ]

For one example, consider rotations. Suppose we want to rotate by a degrees around the z axis. from elementry trig and some visualization you can see that the result of this will be to transform the x, y and z axes as follows:
    xa = <1, 0, 0>  -> <cos(a), sin(a), 0>
    ya = <0, 1, 0>  -> <-sin(a), cos(a), 0>
    za = <0, 0, 1>  -> <0, 0, 1> (no change)
So in quarkpy.qeditor.py, we find this function to define the matrix for rotation by an angle rad (specified in radians):
    def matrix_rot_z(rad):
        sin, cos = math.sin(rad), math.cos(rad)
        return quarkx.matrix(
           (cos, -sin, 0),
           (sin,  cos, 0),
           ( 0 ,   0,  1))
(Remember that when the input to quark.matrix is specified as three tuples, they are rows.) There are similar formulas for rotations around other axes. 'Scaling' is linear transformations that make things bigger or smaller by proportional amounts. To scale something by the factors x, y and z along the respective axes, this matrix would be used:
    x   0   0
    0   y   0
    0   0   z
As usual, each column represents what the mapping does to the corresponding coordinate vector. For most uses of linear mappings, we don't want to use them on their own, but need to combine them with another kind of mapping, 'translations'. Linear mappings always leave the origin <0, 0, 0> untouched; a translation adds the same amount to everything, thereby shifting the whole space by a certain amount in a certain direction. Now suppose we have an object sitting in our map, centered say at the point <100, 250, 920>. If we just applied a rotation to it, it would rotate around the map origin, which is probably not what we want. What we probably want to do is first apply a translation so that the point we want it to rotate around is now the map origin, then apply the rotation, and then apply the reverse of the translation. QuArK Python provides a quick way of doing this with the 'linear' method: if say we have a group grp, grp.linear(v, m) will apply the linear mapping represented by the matrix m to the group, using the point represented by v as the origin). This will also work for duplicators if their 'applylinear' method is properly defined (which, for certain of the more recent and complex ones, it isn't). In many applications what we want is not exactly a linear mapping, but an 'affine mapping'; which is a linear mapping followed by a translation (the offset). For example texturing a face. Conceptually, this is a mapping from the two-dimenensional texture plane, tiled with the texture image, onto some face. We can make it three-dimensional (and thereby get to use QuArK's matrix facility, by adding a z-dimension, which does nothing, to the substantively useful s and t dimensions (conventionally used instead of x and y for textures). The texture threepoints for a face (face.threepoints(2)), (p0, p1, p2) are the images of the texture origin, s axis and t axis under an affine map. The translation component of the map is represented by the vector p0, while the linear component has the matrix:
    quarkx.matrix(p1-p0,p1-p0,quarkx.vect(0, 0, 1))
(It's best to make no change for the formally necessary but substantively useless z component). The matrix for the texture scale can be used for complicated things such as aligning textures on faces and bezier patches, or converting texture positioning information between different formats. Here is a somewhat complex example, finding a series of point that will constitute the outline of a 'warped circle' inscribed in a quadrilateral (for possible use in a prism builder, for example). The actual routine is warpedCircleFrom4Points(n, points), from quarkpy.maputils. points is supposed to be a list of four points, the corners of the quadrilateral, while n is the number of points we want to generate. The basic intuition is that we think of our quadrilateral as warped square, so that our warped circle will be a warped version of real circle, touching the square at the midpoints of the edges. But since all four corners of the actual quadrilateral might be different, we really have to think of it as four perhaps differently warped quarter circles. So the strategy will be to generate n-1 angles in succession, performing the following operations on each: select the corner of the quadrilateral & adjust the angle appropriately find the point in the ideal quarter circle produced by the adjusted angle map this point into the corresponding actual point on the warped circle. The first step isn't very interesting, and is acheived by the code down to the comment 'get point in quarter-circle resting in the axes' (just note that each corner is constituted by the corner point and the midpoints of the two edges that meet there). The next step is basic trig, and performed by
            point = quarkx.vect(1.0-math.sin(angle*deg2rad), 1.0-math.cos(angle*deg2rad), 0)
(the idea here is that we're generating points on a circle of unit radius centered on the point (0,0)). So the next line is:
            mat = matrix_u_v(corner[1], corner[2])
where matrix_u_v(u,v) creates a matrix whose first column is u, second column is v, and last column is <0,0,1> (it's assumed that the third coordinate of the vectors to be mapped by this matrix will always be 0, so the last column of the matrix doesn't really matter; however a safer choice might be to use something based on the cross-product of the input vectors). Then comes the payoff line:
            circle.append(corner[0]+mat*point)
corner[0] is the map-location of the actual corner point, point is the ideal location on the quarter-circle, and multiplying by mat converts this into the actual position on the warped quarter-circle. This procedure generates n-1 of the n-points we want, the first is just a mid-edge (warped circle tangent) point. And last comes the interesting bit. Because we can make a matrix for a linear mapping out of the images that it produces for the coordinate axes, we get therefore get a linear mapping to warp our quarter-circle by thinking of the two arms of the warped corner as images of the clean, 90 dgree unit length corner. So there it is, and, slightly amazingly, it seems to work :) The same technique is employed in quarkpy.b2utils for generating bezier control points for bevels in the function arcSubdivideLine(n, p0, p1, p2), but the details are a bit different because on the one hand we're dealing with quarter circles rather than full circles to begin with, but on the other we need to generate control points that lie off the circle in order to get the patch to bend, which involves a bit of implicit (one variable) calculus plus calculating line intersections.

GNU General Public License by The QuArK (Quake Army Knife) Community - http://www.planetquake.com/quark | [ Prev - Top - Next ]