SVG Essentials/Matrix Algebra
(Initial conversion from Docbook)
m (1 revision(s))
Revision as of 22:22, 6 March 2008
Matrix algebra is a branch of mathematics that defines operations on matrices, which are series of numbers arranged in rows and columns. In addition to its many uses in science and engineering, matrix algebra makes the computations for graphic operations very efficient. The purpose of this appendix is to introduce you to the fundamental concepts of matrix algebra that SVG uses "behind the scenes."
We describe a matrix by its number of rows and columns. Figure D-1 displays a matrix that arranges a series of daily temperatures over a two-week period into two rows of seven columns each. This matrix is called a "two-by-seven" matrix. Matrices are enclosed in square brackets when written.
Here are some other terms that you may encounter when dealing with matrix operations: A square matrix is a matrix with the same number of rows as columns. A vector is a matrix with only one row, and a column vector is a matrix with only one column. The individual entries in a matrix are called entries, and the technical term for a plain number is a scalar. Now you can bring these sure-fire conversation stoppers to the next party you attend.
Applying the concept of a matrix to SVG, you might express a set of x and y coordinates as a two-by-one matrix. This isn't the way we'll ultimately end up representing coordinates, but it's a good place to start, as it's easy to understand. In this representation, the point (3, 5) is expressed as shown in Figure D-2.
The easiest matrix operation is addition. To add two matrices, you add their corresponding elements. This, of course, requires that your matrices have exactly the same number of rows and columns. Figure D-3 shows the addition of 2 matrices, each 3-by-2.
We see that the translate transformation in SVG could be accomplished easily by matrix addition. For example, the matrix addition in Figure D-4 would implement transform="translate(7, 2)" for any point (x, y).
The order in which you add matrices doesn't matter. Technically, we say that matrix addition is commutative (A + B = B + A). It is also associative; given three matrices A, B, and C, (A + B) + C is the same as A + (B + C). There is such a thing as matrix subtraction; just subtract the corresponding elements of the two matrices. Just as with regular subtraction, matrix subtraction is not commutative.
You may be thinking that matrix multiplication works in a similar manner, and that's how you can do a scale() transformation. Unfortunately, the easy way doesn't work this time. Matrix multiplication is significantly more complicated than matrix addition. In the first examples that follow, this complexity appears to be needless. As we proceed, you'll see that the usefulness of matrix multiplication far outweighs its difficulty.
In order to multiply two matrices, the number of columns of the first matrix must equal the number of rows of the second matrix. Such matrices are called compatible. This means you can multiply a 3-by-5 matrix times a 5-by-4 matrix, but not a 3-by-5 matrix times a 3-by-2 matrix. The matrices we will multiply in Figure D-5 are compatible.
The resulting matrix will have the same number of rows as the first matrix, and the same number of columns as the second matrix. Thus, the example's 2-by-3 matrix times the 3-by-2 matrix will result in a 2-by-2 matrix.
The entry that will go in row one, column one of our result matrix is the cross product of the first row of the first matrix and the first column of the second matrix. "Cross product" is a fancy way of saying "add up the products of the corresponding entries in a row and column" as shown in Figure D-6.
To find the quantity to place in row two, column one (the lower left) of the result matrix, take the cross product of row two in the first matrix and column one in the second matrix, as shown in Figure D-7.
Calculating the remaining items produces the result shown in Figure D-8.
Given this information, we can now use matrix multiplication to express the calculations needed to scale a point (x, y) by a factor of 3 horizontally and a factor of 1.5 vertically. Our transformation matrix will have to have two rows and two columns so it is compatible with our two row by one column coordinates, as shown in Figure D-9.
Unlike multiplication of single numbers, matrix multiplication is not commutative. If two matrices, A and B, aren't square matrices, then A·B won't have the same number of rows and columns as B·A (if they're even compatible in both directions). Even if A and B are both 3-by-3 square matrices, there's no guarantee that A times B will result in the same answer as B times A. In fact, they'll come out equal in only a very few special cases.
There is another limited form of multiplication; multiplying a matrix by a scalar (a plain number) will multiply every item in the matrix by the scalar, as shown in Figure D-10. We didn't mention this in conjunction with scaling, since this construct scales uniformly, and SVG scaling isn't always the same horizontally and vertically.
There is no such thing as matrix division as such. There is a construct called a matrix inverse, which is analogous to the reciprocal of a number, but it's very complicated to calculate, and SVG doesn't make any great use of it.
How SVG Uses Matrix Algebra for Transformations
The approach we've taken to translation and scaling works, but it's not ideal. For instance, if we want to translate a point and then scale it, we need to do one matrix addition and then a matrix multiplication. SVG uses a clever trick to represent coordinates and transformation matrices so you can do scaling and translation all with one operation. First, it adds a third value, which is always equal to one, to the coordinate matrix. This means that the point (3, 5) will be represented as shown in Figure D-11.
SVG uses a 3-by-3 matrix, again set up with extra zeroes and ones, to specify the transformation. Figure D-12 shows a matrix that translates a point by a horizontal distance of tx and a vertical distance of ty.
Figure D-13 shows a transformation matrix that will scale a point by a factor of sx in the horizontal direction and sy in the vertical direction.
What we've bought with this is a consistent notation; all our transformations, including rotation and skewing, can be represented with 3-by-3 matrices. Furthermore, since everything is 3-by-3, we can construct a chain of transformations by multiplying those matrices together; they're guaranteed to be compatible. For example, to do a translation followed by a scaling, we multiply the matrices in that order (see Figure D-14).
Again, it seems as if we're needlessly complicating matters. In order to transform the point (3, 5), we now need two matrix multiplications. To transform another point would require two more multiplications. Given a <path> element with several hundred points, this could run into some serious computing time.
Here's where SVG does something clever: it multiplies the first two matrices together, and stores that result, as shown in Figure D-15.
This "pre-multiplied" matrix now embodies both of the transformations. By multiplying this new matrix times a coordinate point's matrix, we can do the translation and scaling with a single matrix multiplication (see Figure D-16). Now conversion of a hundred points would require only one hundred multiplications, not two hundred.
If we had to do a translation followed by a rotation followed by a scale, we'd create three 3-by-3 matrices; one to do the translation, one to do the rotation, and one to do the scaling. We'd multiply them all together (in that order), and the resulting matrix would embody all the calculations needed to do all three transformations.
As we mentioned in Section D.3, matrix multiplication is not commutative. If we change the order of the transformation matrices, we get a different result. This is the mathematics behind the fact that the sequence of transformations makes a difference in the resulting graphic, as described in Chapter 5 in Section 5.3.
This, then, is the power of matrix algebra; it lets us combine the information about as many transformations as we want into one single 3-by-3 matrix, thus dramatically reducing the amount of calculation necessary to transform points. The matrices in Figure D-17 are the ones used to specify a rotation by an angle a, a skew along the x-axis of ax, and a skew along the y-axis of ay.
SVG also uses matrix algebra quite heavily in the calculations associated with filters, which are described in Chapter 10. There, a pixel's red, green, blue, and alpha (opaqueness) values are described as a matrix with five rows and one column. It also adds a fifth row so that a 5-by-5 transformation matrix can add a constant amount to any of the values as well as multiply them by any desired factor. The economies of scale we get by pre-multiplying coordinate transformation matrices work equally well when pre-multiplying pixel manipulation matrices.