SVG Essentials/Matrix Algebra

From WikiContent

< SVG Essentials(Difference between revisions)
Jump to: navigation, search
(Initial conversion from Docbook)
Current revision (13:40, 7 March 2008) (edit) (undo)
(Initial conversion from Docbook)
 
(4 intermediate revisions not shown.)

Current revision

SVG Essentials

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."

Contents

Matrix Terminology

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.

Figure D-1. 2 by 7 matrix of daily temperatures

2 by 7 matrix of daily temperatures

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.

Figure D-2. Coordinates expressed as a matrix

Coordinates expressed as a matrix

Matrix Addition

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.

Figure D-3. Addition of two 3 by 2 matrices

Addition of two 3 by 2 matrices

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).

Figure D-4. Simple method to translate coordinates

Simple method to translate coordinates

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.

Matrix Multiplication

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.

Figure D-5. Two matrices to be multiplied

Two matrices to be multiplied

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.

Figure D-6. First entry in multiplied matrices

First entry in multiplied matrices

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.

Figure D-7. Second entry in multiplied matrices

Second entry in multiplied matrices

Calculating the remaining items produces the result shown in Figure D-8.

Figure D-8. Completed multiplication of matrices

Completed multiplication of matrices

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.

Figure D-9. Simple scaling by multiplying matrices

Simple scaling by multiplying matrices

Warning

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.

Figure D-10. Multiplying a scalar by a matrix

Multiplying a scalar by a matrix

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.

Figure D-11. SVG representation of a coordinate

SVG representation of a coordinate

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-12. SVG representation of translation

SVG representation of translation

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.

Figure D-13. SVG representation of scaling

SVG representation of scaling

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).

Figure D-14. Translation followed by scaling

Translation followed by scaling

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.

Figure D-15. Result of multiplying translation and scaling matrices

Result of multiplying translation and scaling matrices

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.

Figure D-16. Result of premultiplying translation and scaling matrices

Result of premultiplying translation and scaling matrices

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.

Note

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.

Figure D-17. Rotate, skew x, and skew y transformation matrices

Rotate, skew x, and skew y transformation matrices

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.

The <feColorMatrix> filter, described in Chapter 10 in Section 10.3.1, lets you specify all twenty values and places them in the pixel transformation matrix as shown in Figure D-18.

Figure D-18. Color transformation matrix

Color transformation matrix

Personal tools