SVG Essentials/Matrix Algebra - Revision history

Docbook2Wiki: Initial conversion from Docbook

Docbook2Wiki — Fri, 07 Mar 2008 13:40:50 GMT

Initial conversion from Docbook

←Older revision

Revision as of 13:40, 7 March 2008

Docbook2Wiki: Initial conversion from Docbook

Docbook2Wiki — Fri, 07 Mar 2008 12:51:41 GMT

Initial conversion from Docbook

←Older revision

Revision as of 12:51, 7 March 2008

Evanlenz: 1 revision(s)

Evanlenz — Thu, 06 Mar 2008 23:40:44 GMT

1 revision(s)

←Older revision

Revision as of 23:40, 6 March 2008

Docbook2Wiki: Initial conversion from Docbook

Docbook2Wiki — Thu, 06 Mar 2008 23:33:32 GMT

Initial conversion from Docbook

←Older revision

Revision as of 23:33, 6 March 2008

Evanlenz: 1 revision(s)

Evanlenz — Thu, 06 Mar 2008 22:52:52 GMT

1 revision(s)

←Older revision

Revision as of 22:52, 6 March 2008

Docbook2Wiki: Initial conversion from Docbook

Docbook2Wiki — Thu, 06 Mar 2008 22:38:57 GMT

Initial conversion from Docbook

←Older revision

Revision as of 22:38, 6 March 2008

Evanlenz: 1 revision(s)

Evanlenz — Thu, 06 Mar 2008 22:22:15 GMT

1 revision(s)

←Older revision

Revision as of 22:22, 6 March 2008

Docbook2Wiki: Initial conversion from Docbook

Docbook2Wiki — Thu, 06 Mar 2008 22:21:01 GMT

Initial conversion from Docbook

←Older revision		Revision as of 22:21, 6 March 2008
Line 9:		Line 9:
	'''Figure D-1. 2 by 7 matrix of daily temperatures'''		'''Figure D-1. 2 by 7 matrix of daily temperatures'''

-	[[Image:SVG ~~Essentials/I__tt377~~.png\|2 by 7 matrix of daily temperatures]]	+	[[Image:SVG Essentials_I__tt377.png\|2 by 7 matrix of daily temperatures]]
	</div>		</div>

Line 19:		Line 19:
	'''Figure D-2. Coordinates expressed as a matrix'''		'''Figure D-2. Coordinates expressed as a matrix'''

-	[[Image:SVG ~~Essentials/I__tt378~~.png\|Coordinates expressed as a matrix]]	+	[[Image:SVG Essentials_I__tt378.png\|Coordinates expressed as a matrix]]
	</div>		</div>

Line 29:		Line 29:
	'''Figure D-3. Addition of two 3 by 2 matrices'''		'''Figure D-3. Addition of two 3 by 2 matrices'''

-	[[Image:SVG ~~Essentials/I__tt379~~.png\|Addition of two 3 by 2 matrices]]	+	[[Image:SVG Essentials_I__tt379.png\|Addition of two 3 by 2 matrices]]
	</div>		</div>

Line 37:		Line 37:
	'''Figure D-4. Simple method to translate coordinates'''		'''Figure D-4. Simple method to translate coordinates'''

-	[[Image:SVG ~~Essentials/I__tt380~~.png\|Simple method to translate coordinates]]	+	[[Image:SVG Essentials_I__tt380.png\|Simple method to translate coordinates]]
	</div>		</div>

Line 51:		Line 51:
	'''Figure D-5. Two matrices to be multiplied'''		'''Figure D-5. Two matrices to be multiplied'''

-	[[Image:SVG ~~Essentials/I__tt381~~.png\|Two matrices to be multiplied]]	+	[[Image:SVG Essentials_I__tt381.png\|Two matrices to be multiplied]]
	</div>		</div>

Line 61:		Line 61:
	'''Figure D-6. First entry in multiplied matrices'''		'''Figure D-6. First entry in multiplied matrices'''

-	[[Image:SVG ~~Essentials/I__tt382~~.png\|First entry in multiplied matrices]]	+	[[Image:SVG Essentials_I__tt382.png\|First entry in multiplied matrices]]
	</div>		</div>

Line 69:		Line 69:
	'''Figure D-7. Second entry in multiplied matrices'''		'''Figure D-7. Second entry in multiplied matrices'''

-	[[Image:SVG ~~Essentials/I__tt383~~.png\|Second entry in multiplied matrices]]	+	[[Image:SVG Essentials_I__tt383.png\|Second entry in multiplied matrices]]
	</div>		</div>

Line 77:		Line 77:
	'''Figure D-8. Completed multiplication of matrices'''		'''Figure D-8. Completed multiplication of matrices'''

-	[[Image:SVG ~~Essentials/I__tt384~~.png\|Completed multiplication of matrices]]	+	[[Image:SVG Essentials_I__tt384.png\|Completed multiplication of matrices]]
	</div>		</div>

Line 85:		Line 85:
	'''Figure D-9. Simple scaling by multiplying matrices'''		'''Figure D-9. Simple scaling by multiplying matrices'''

-	[[Image:SVG ~~Essentials/I__tt385~~.png\|Simple scaling by multiplying matrices]]	+	[[Image:SVG Essentials_I__tt385.png\|Simple scaling by multiplying matrices]]
	</div>		</div>

Line 99:		Line 99:
	'''Figure D-10. Multiplying a scalar by a matrix'''		'''Figure D-10. Multiplying a scalar by a matrix'''

-	[[Image:SVG ~~Essentials/I__tt386~~.png\|Multiplying a scalar by a matrix]]	+	[[Image:SVG Essentials_I__tt386.png\|Multiplying a scalar by a matrix]]
	</div>		</div>

Line 111:		Line 111:
	'''Figure D-11. SVG representation of a coordinate'''		'''Figure D-11. SVG representation of a coordinate'''

-	[[Image:SVG ~~Essentials/I__tt387~~.png\|SVG representation of a coordinate]]	+	[[Image:SVG Essentials_I__tt387.png\|SVG representation of a coordinate]]
	</div>		</div>

Line 119:		Line 119:
	'''Figure D-12. SVG representation of translation'''		'''Figure D-12. SVG representation of translation'''

-	[[Image:SVG ~~Essentials/I__tt388~~.png\|SVG representation of translation]]	+	[[Image:SVG Essentials_I__tt388.png\|SVG representation of translation]]
	</div>		</div>

Line 127:		Line 127:
	'''Figure D-13. SVG representation of scaling'''		'''Figure D-13. SVG representation of scaling'''

-	[[Image:SVG ~~Essentials/I__tt389~~.png\|SVG representation of scaling]]	+	[[Image:SVG Essentials_I__tt389.png\|SVG representation of scaling]]
	</div>		</div>

Line 135:		Line 135:
	'''Figure D-14. Translation followed by scaling'''		'''Figure D-14. Translation followed by scaling'''

-	[[Image:SVG ~~Essentials/I__tt390~~.png\|Translation followed by scaling]]	+	[[Image:SVG Essentials_I__tt390.png\|Translation followed by scaling]]
	</div>		</div>

Line 145:		Line 145:
	'''Figure D-15. Result of multiplying translation and scaling matrices'''		'''Figure D-15. Result of multiplying translation and scaling matrices'''

-	[[Image:SVG ~~Essentials/I__tt391~~.png\|Result of multiplying translation and scaling matrices]]	+	[[Image:SVG Essentials_I__tt391.png\|Result of multiplying translation and scaling matrices]]
	</div>		</div>

Line 153:		Line 153:
	'''Figure D-16. Result of premultiplying translation and scaling matrices'''		'''Figure D-16. Result of premultiplying translation and scaling matrices'''

-	[[Image:SVG ~~Essentials/I__tt392~~.png\|Result of premultiplying translation and scaling matrices]]	+	[[Image:SVG Essentials_I__tt392.png\|Result of premultiplying translation and scaling matrices]]
	</div>		</div>

Line 169:		Line 169:
	'''Figure D-17. Rotate, skew x, and skew y transformation matrices'''		'''Figure D-17. Rotate, skew x, and skew y transformation matrices'''

-	[[Image:SVG ~~Essentials/I__tt393~~.png\|Rotate, skew x, and skew y transformation matrices]]	+	[[Image:SVG Essentials_I__tt393.png\|Rotate, skew x, and skew y transformation matrices]]
	</div>		</div>

Line 179:		Line 179:
	'''Figure D-18. Color transformation matrix'''		'''Figure D-18. Color transformation matrix'''

-	[[Image:SVG ~~Essentials/I__tt394~~.png\|Color transformation matrix]]	+	[[Image:SVG Essentials_I__tt394.png\|Color transformation matrix]]
	</div>		</div>

Docbook2Wiki: Initial conversion from Docbook

Docbook2Wiki — Tue, 04 Mar 2008 22:37:00 GMT

Initial conversion from Docbook

New page

{{SVG Essentials/TOC}}
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."

== Matrix Terminology ==

We describe a matrix by its number of rows and columns. [[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-1|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.

<div id="svgess-APP-D-FIG-1">
'''Figure D-1. 2 by 7 matrix of daily temperatures'''

[[Image:SVG Essentials/I__tt377.png|2 by 7 matrix of daily temperatures]]
</div>

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 [[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-2|Figure D-2]].

<div id="svgess-APP-D-FIG-2">
'''Figure D-2. Coordinates expressed as a matrix'''

[[Image:SVG Essentials/I__tt378.png|Coordinates expressed as a matrix]]
</div>

== 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. [[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-3|Figure D-3]] shows the addition of 2 matrices, each 3-by-2.

<div id="svgess-APP-D-FIG-3">
'''Figure D-3. Addition of two 3 by 2 matrices'''

[[Image:SVG Essentials/I__tt379.png|Addition of two 3 by 2 matrices]]
</div>

We see that the <tt>translate</tt> transformation in SVG could be accomplished easily by matrix addition. For example, the matrix addition in [[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-4|Figure D-4]] would implement <tt>transform="translate(7, 2)"</tt> for any point (''x'', ''y'').

<div id="svgess-APP-D-FIG-4">
'''Figure D-4. Simple method to translate coordinates'''

[[Image:SVG Essentials/I__tt380.png|Simple method to translate coordinates]]
</div>

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 <tt>scale()</tt> 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 [[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-5|Figure D-5]] are compatible.

<div id="svgess-APP-D-FIG-5">
'''Figure D-5. Two matrices to be multiplied'''

[[Image:SVG Essentials/I__tt381.png|Two matrices to be multiplied]]
</div>

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 [[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-6|Figure D-6]].

<div id="svgess-APP-D-FIG-6">
'''Figure D-6. First entry in multiplied matrices'''

[[Image:SVG Essentials/I__tt382.png|First entry in multiplied matrices]]
</div>

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 [[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-7|Figure D-7]].

<div id="svgess-APP-D-FIG-7">
'''Figure D-7. Second entry in multiplied matrices'''

[[Image:SVG Essentials/I__tt383.png|Second entry in multiplied matrices]]
</div>

Calculating the remaining items produces the result shown in [[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-8|Figure D-8]].

<div id="svgess-APP-D-FIG-8">
'''Figure D-8. Completed multiplication of matrices'''

[[Image:SVG Essentials/I__tt384.png|Completed multiplication of matrices]]
</div>

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 [[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-9|Figure D-9]].

<div id="svgess-APP-D-FIG-9">
'''Figure D-9. Simple scaling by multiplying matrices'''

[[Image:SVG Essentials/I__tt385.png|Simple scaling by multiplying matrices]]
</div>

<div class="warning">
'''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.
</div>

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 [[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-10|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.

<div id="svgess-APP-D-FIG-10">
'''Figure D-10. Multiplying a scalar by a matrix'''

[[Image:SVG Essentials/I__tt386.png|Multiplying a scalar by a matrix]]
</div>

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 [[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-11|Figure D-11]].

<div id="svgess-APP-D-FIG-11">
'''Figure D-11. SVG representation of a coordinate'''

[[Image:SVG Essentials/I__tt387.png|SVG representation of a coordinate]]
</div>

SVG uses a 3-by-3 matrix, again set up with extra zeroes and ones, to specify the transformation. [[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-12|Figure D-12]] shows a matrix that translates a point by a horizontal distance of <tt>tx</tt> and a vertical distance of <tt>ty</tt>.

<div id="svgess-APP-D-FIG-12">
'''Figure D-12. SVG representation of translation'''

[[Image:SVG Essentials/I__tt388.png|SVG representation of translation]]
</div>

[[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-13|Figure D-13]] shows a transformation matrix that will scale a point by a factor of <tt>sx</tt> in the horizontal direction and <tt>sy</tt> in the vertical direction.

<div id="svgess-APP-D-FIG-13">
'''Figure D-13. SVG representation of scaling'''

[[Image:SVG Essentials/I__tt389.png|SVG representation of scaling]]
</div>

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 [[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-14|Figure D-14]]).

<div id="svgess-APP-D-FIG-14">
'''Figure D-14. Translation followed by scaling'''

[[Image:SVG Essentials/I__tt390.png|Translation followed by scaling]]
</div>

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 <tt><path></tt> 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 [[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-15|Figure D-15]].

<div id="svgess-APP-D-FIG-15">
'''Figure D-15. Result of multiplying translation and scaling matrices'''

[[Image:SVG Essentials/I__tt391.png|Result of multiplying translation and scaling matrices]]
</div>

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 [[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-16|Figure D-16]]). Now conversion of a hundred points would require only one hundred multiplications, not two hundred.

<div id="svgess-APP-D-FIG-16">
'''Figure D-16. Result of premultiplying translation and scaling matrices'''

[[Image:SVG Essentials/I__tt392.png|Result of premultiplying translation and scaling matrices]]
</div>

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.

<div class="note">
'''Note'''

As we mentioned in [[SVG Essentials/Matrix Algebra#Matrix Multiplication|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 [[SVG Essentials/Transforming the Coordinate System|Chapter 5]] in [[SVG Essentials/Transforming the Coordinate System#Sequences of Transformations|Section 5.3]].
</div>

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 [[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-17|Figure D-17]] are the ones used to specify a rotation by an angle <tt>a</tt>, a skew along the ''x''-axis of <tt>ax</tt>, and a skew along the ''y''-axis of <tt>ay</tt>.

<div id="svgess-APP-D-FIG-17">
'''Figure D-17. Rotate, skew x, and skew y transformation matrices'''

[[Image:SVG Essentials/I__tt393.png|Rotate, skew x, and skew y transformation matrices]]
</div>

SVG also uses matrix algebra quite heavily in the calculations associated with filters, which are described in [[SVG Essentials/Filters|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 <tt><feColorMatrix></tt> filter, described in [[SVG Essentials/Filters|Chapter 10]] in [[SVG Essentials/Filters#The feColorMatrix Element|Section 10.3.1]], lets you specify all twenty values and places them in the pixel transformation matrix as shown in [[SVG Essentials/Matrix Algebra#svgess-APP-D-FIG-18|Figure D-18]].

<div id="svgess-APP-D-FIG-18">
'''Figure D-18. Color transformation matrix'''

[[Image:SVG Essentials/I__tt394.png|Color transformation matrix]]
</div>