From: jgm@cs.brown.edu (Jonathan Monsarrat)
Subject: Re: Exactly What does a Transformation Matrix Do?
Organization: Brown University Department of Computer Science
Date: Tue, 13 Oct 1992 05:08:06 GMT

Here's a file I just wrote about transformation matrixes.

It will be cleaned up and put into a FAQ tutorial file. I'm starting a
series of these FAQ files which will not posted to the group
regularly, but instead will be freely available by ftp as "The Usenet
Guide to PostScript". Want to help write them?

Many things are awkward and some are probably dead wrong.
Please correct me! If your improvement suggestion is the rewording
of a sentence, or anything less than a real error correction, you
probably want to mail me personally, not post to the group, but that
is your choice of course. :)

-Jon

P.S. Of the three books, I should to tell you to read the first because
van Dam and Hughes are Brown professors! :)

%! jgm@cs.brown.edu   -- Brown University CS Dept --  Try out this PostScript:
/p{translate}def/y{-1 roll exec}def{<2020202020666F6E74>dup 0 4 y putinterval
cvx 0 y}dup dup/Times-Roman<2066696E64>3 y 100<7363616C65>4 y<2020736574>3 y
90 rotate 0 -612 p 1 1.8 scale 36 144 moveto <50532020202020207B484F4E4B7D2069
66> show gsave 220 130 p {0 0 moveto 29 58 29 -45 180 arc} cvx dup 0 y -1 1
scale 0 y gsave 0.6 setgray fill grestore 2 setlinewidth stroke showpage

-------------------------------------------------------------
               Exactly What Does a Transformation Matrix Do? 

                (or ``What's all this CTM stuff, anyway?'') 



    1 What it's for 

    As you already know, PostScript lets you draw pictures up, down, 
    left, right, sideways, rotated, translated, scaled, and even 
    sheared, which means slanted like cursive writing is slanted 
    compared with printing. 

      How that's implemented is with an engineering optimization trick 
    that uses matrixes. So when you see all this fancy PostScript 
    voodoo talking about matrixes and the CTM, just keep in mind that 
    it's all white magic meant to make your programs run faster. 

      Here's how it works. 

      Let's say that as a programmer, you want to write a program that 
    draws a line from (0,0) to (100,0). 

      Where does the line really get drawn? 

      If you've used the translate operator, then the line gets drawn 
    in the same way, but off to the side, or up and across. 

      If you've used the rotate operator, then the line gets drawn in 
    the same way, but rotated as though you have spun the page with the 
    center of rotation at the origin. 

      If you've used the scale operator, then the line gets drawn int 
    the same way, but bigger or smaller depending on how you've scaled 
    it. 

      And you can combine all these various techniques. 

      You should learn about translate, rotate, and scale before 
    reading the rest of this file. 


    2 How it works 

    PostScript allows the user to think about lines from (0,0) to 
    (100,0), and tells the device to draw the lines wherever is 
    appropriate. 

      The user specifies that one end of the line should be placed at 
    the point (x,y), but that the point is drawn by the device at some 
    point (x', y'). In fact, every point in the user world called the 
    user space is transformed into the device world called the device 
    space. 

      (By the way, device is just a fancy way to say a printer, or 
    computer screen, or whatever thing PostScript is being displayed 
    with.) 

      So mathematically, that becomes a problem of taking any point 
    (x,y) in user space and turning it into (x', y') in device space. 
    We use some two simple functions to do this transformation. One 
    function gives us x' given x and y, and the other gives us y' given 
    x and y. 

      One thing to keep in mind: when a line is transformed from user 
    space into device space, it should remain a line! We don't want the 
    line turning into a circle or a bendy squiggle or anything. Getting 
    circles and bendy squiggles are perfectly valid transformations, 
    but they're non-intuitive and hard to implement. So in PostScript 
    you can only have ``affine transformations'' (no, not ``linear 
    transformations'', although that's close). What this basically 
    means is: 



   1. A line stays a line. 


   2. Two parallel lines stay parallel. 

      There's a simple way to make any affine transformation function 
    you want, in a fill-in-the-blanks way. Take these two equations. 



1.  x' = ax + cy + e
2.  y' = bx + dy + f


      Here the blanks to fill in are the values of a, b, c, d, e, and 
      f, which are all constants. You can make any affine 
      transformation function with some set of values for these 
      constants. 


      3 Now, here's the interesting part! 

      Now, let's see how these transformation functions can be used to 
      implement the PostScript function translate. 

        Let's say that the device space and the user space are oriented 
      the same. So a line from (0,0) to (100,0) in user space is drawn 
      as a line from (0,0) to (100,0) on the printer or computer 
      screen. 

        The tranformation functions for this are pretty easy to write: 



1. x' = x

2. y' = y


        Another way to write this is 



1.  x' = ax + cy + e
2.  y' = bx + dy + f


          As long as a=1, c=0, e=0, b=0, d=1, and f=0. 

            Let's say that the user wants to shift the line a little 
          over the right, maybe 50 points. As you know, you'd do that 
          with the PostScript translate function. But what does it mean 
          mathematically? It means that the line in device space gets 
          drawn a little to the right of where it is specified in user 
          space. In other words, the x coordinate x' of the device 
          space is always bigger than the x coordinate of the user 
          space. 

            In fact, for a 50 point shift, that would be 



1. x' = x + 50

2. y' = y


            Another way to write this is 



1.  x' = ax + cy + e
2.  y' = bx + dy + f


              As long as a=1, c=0, e=50, b=0, d=1, and f=0. 

                So the only difference between the normal device space 
              and this new transformed device space is that e is 50 
              instead of 0. 

                In fact, if we wanted to translate 300 instead of 50, 
              we'd just set e to 300. 


              4 The Most Important Thing 

              So here's the main thing about transformations. Here is 
              the most important thing in this file: 

                It turns out that are a few simple rules for changing 
              the constant variables. If you follow these simple rules, 
              then you can fill in the blanks of the generic equations 



1.  x' = ax + cy + e
2.  y' = bx + dy + f


                and get some specific transformation functions. These 
                transformation functions that you get define a 
                relationship between user space and device space. This 
                relationship is what you think about when you think 
                about the PostScript commands translate, rotate, and 
                scale. 

                  In other words: 

                  You can make your own translate, rotate, and scale by 
                just playing around with the constants. 


                5 The Constant Setting Rules 

                Here are the rules that you can use to perform a 
                translate, rotate, and scale, and also this strange 
                thing called shearing, which is like slanting. 

                  Later on I'll tell you how you can set these 
                constants in PostScript. Right now let's just assume 
                that you will be able to do this, and concentrate on 
                the rules for setting the constants. 

                  The first three rules are: 



    * To do a ``j k translate'', set constants e = e + j, and f = f + 
      k. 


    * To do ``j k scale'', set constants a = aj, and d = dk. 


    * To do ``j rotate'', which gives a spin of angle j in the 
      clockwise direction, set constants a = cos j, b = sin j, c = - 
      sin j, d = cos j. 

      If you use a negative rotation, things get rotated in the 
    counterclockwise direction. 

      If you use a negative scale, things get flipped around, like in a 
    mirror image. 

      Now, about shearing. I don't know why there isn't a PostScript 
    operator for shearing, but you can do it if you want to. 

      To get a good idea what shearing does, think about a normal 
    skyscraper. What if we turn that skyscraper into the Leaning Tower 
    of Piza? 

      If you keep the top and bottom of the Leaning Tower horizontal, 
    but retain the tilt, that's shearing. Shearing just means tilting 
    something. And don't forget the two properties of any affine 
    transformation: 



   1. A line stays a line. 


   2. Two parallel lines stay parallel. 

      Even though the Leaning Tower of Piza leans over, all the sides 
    are still straight, and the sides are still parallel. 

      So here's the last rule: 



    * To do ``j k shear'', which gives a tilt of angle j in the X 
      direction, and a tilt of angle k in the Y direction, set 
      constants b = sin j, c = cos k. 

      And the funny thing is, it turns out that you can do a lot of 
    these transformations in a row. 

      For example, if you want to do ``50 80 translate'' and then ``2 3 
    scale'', you can apply the rule for translate first, and then apply 
    the rule for rotate second. 

      Because of the way the algebra works out, that's different that 
    doing ``2 3 scale'' first and doing ``50 80 translate'' afterwards. 
    Have you already noticed the importance of ordering transformations 
    when writing PostScript programs? The reason it's different is 
    because applying the rules in a different order produces different 
    changes to the constants. 

      Doing many transformations in a row with these simple rules only 
    works for scale and translate, and not for rotate and shear. There 
    are more complex rules that let you do many transformations in a 
    row for rotations and shears also. 

      Now, here's a big secret that the people who do computer graphics 
    don't want us to tell anybody, but I'll tell you: 

      Matrixes are just a sneaky programming trick to implement filling 
    in the blanks quickly using the complex rules. They don't really 
    mean anything besides that. 


    6 Matrixes? Yuck! I'll never understand this... 

    That's my attitude too about matrixes, but I have to admit that 
    they're useful. To continue reading, you will need an idea what a 
    matrix is, but you don't have to like them! To become an expert at 
    making your own transformations in PostScript, you should also know 
    how to multiply matrixes, but you don't need to know this. 

      PostScript stores a copy of the two affine transformation 
    equations currently being used: 



1.  x' = ax + cy + e
2.  y' = bx + dy + f


      (Actually, there is one copy for each graphics state, but this 
      file isn't about the PostScript graphics state.) 

        PostScript stores its copy in what's called the current 
      transformation matrix or CTM. Basically, this just means storing 
      the values of all the constants a, b, c, d, e, and f in a matrix, 
      like this: 



[  a   b   0
   c   d   0
   e   f   1  ]


        The three numbers 0, 0, and 1 in the rightmost column you can 
        ignore. That's yet another secret sneaky programming trick. 

          In fact, it turns out that PostScript ignores them entirely! 
        When you think about transform matrixes in PostScript, you 
        write them as 



[  a   b
   c   d
   e   f  ]


          because the 0, 0, 1 part never changes, so why store it in 
          memory? 

            For now, let's keep the 0, 0, 1 as part of the matrix 
          because they are important part to the matrix sneaky trick. 

            This is how transformation constants are stored in 
          PostScript. And because the constants define the functions, 
          this is also how transformation functions are stored in 
          PostScript. 


          7 Using Matrixes to Make Transformations 

          You can use matrixes to make transformations by representing 
          the user space point (x,y) with a matrix 


 \[ x y 1 \]


          and the device space point (x',y') with a matrix 


 \[ x' y' 1 \].


            Again, ignore the additional 1's stuck in there. If you 
            know some matrix mathematics then you'll see how this is 
            useful. Otherwise, you don't need to understand it. 

              Let's say we have some point (x,y) in user space that I 
            want to transform into (x', y'). We do this by applying the 
            affine transformation equations (we assume that the blanks 
            have been filled in): 



1.  x' = ax + cy + e
2.  y' = bx + dy + f


              Well, another way of saying exactly the same thing with 
              matrixes is to say (x', y') = CTM * (x, y), or: 



[ x'       [  a  b  0       [ x
  y'    =     c  d  0    *    y
  1 ]         e  f  1 ]       1 ]


                So, depending on what the constants are, the right 
                transformation will take place. 

                  If you've learned some things about matrixes then 
                you'll know that it's common to represent algebraic 
                equations as matrixes, particularly as an optomization 
                technique when you want to do a lot of number 
                crunching. PostScript represents equations this way 
                because transforming a coordinate from user space to 
                device space must be done very frequently. In fact, it 
                happens every single time you deal with user space in 
                your program! 

                  Well, what if we have want the device space the same 
                as the user space? We have already seen that this is 
                given by the transformation equations 



1. x' = x

2. y' = y


                  Which means a=1, c=0, e=0, b=0, d=1, and f=0. 

                    So when your PostScript program starts running, the 
                  current transformation matrix must be 



[  a   b   0
   c   d   0
   e   f   1  ]


                    which is 



[  1   0   0
   0   1   0
   0   0   1  ]


                      This is called the identity matrix, and it just 
                      means that the device space is the same as the 
                      user space. The transformation doesn't change 
                      anything. 

                        Of course, when you're programming PostScript, 
                      the rightmost column won't be included so you'll 
                      get 



[  a   b
   c   d
   e   f  ]


                        which is 



[  1   0
   0   1
   0   0  ]



                          8 Changing the CTM 

                          In a previous section you saw that if you 
                          want to make a translate, rotate, scale, or 
                          shear, you do that by following certain rules 
                          to change the values of the constants. 

                            Here's how PostScript does this with the 
                          current transformation matrix. This rule also 
                          works for rotate and shear as well as for 
                          translate and scale. This are just another 
                          rule, and if you follow it things will work 
                          fine: 



   1. Figure out what the transformation would be like applied to the 
      identity matrix ( not the device default matrix introduced 
      below), using the simple rules. Make some matrix out of this. 
      Let's call it ``A''. 


   2. CTM = CTM * A 

      Let's take the example doing ``2 3 scale'' first and then doing 
    ``50 80 translate'' 

      Well, filling in the blanks by the rules: 

      The identity matrix has a=1, c=0, e=0, b=0, d=1, and f=0. 

      The rule for scale says 



    * To do ``j k scale'', set constants a = aj, and d = dk. 

      So we have j=2, k=3, a=j, c=0, e=0, b=0, d=k, and f=0. Make a 
    matrix A out of these: 



[  2   0   0
   0   3   0
   0   0   1  ]


      And CTM = CTM * A. 

        Then for ``50 80 translate'', since the identity matrix has 
      a=1, c=0, e=0, b=0, d=1, and f=0, and the rule for translate says 



    * To do a ``j k translate'', set constants e = e + j, and f = f + 
      k. 

      So we have j=50, k=80, a=1, c=0, e=j, b=0, d=1, and f=k. Make a 
    matrix B out of these: 



[  1   0   0
   0   1   0
  50  80   1  ]


      And CTM = CTM * B. 

        This means that in order to perform ``2 3 scale'' and ``50 80 
      translate'' we need to change the CTM, so that the new CTM is 
      given by: 

        CTM = CTM * A * B 

        This will work no matter what the CTM is. And don't forget that 
      the reason we're using all this in the first place is so that you 
      can say (x', y') = CTM * (x, y), which gives us the correct 
      coordinates (x', y') in device space to draw something given at 
      (x, y) in user space. 


      9 All the PostScript Matrix Commands 

      Keep in mind two important things when you think about matrixes 
      in PostScript: 

        1. A matrix that looks like 



[  1   3   7   4    5
   0  -1  14   9   10
   8  12  13  11   15  ]


        Will be written in a PostScript program as 



[ 1 3 7 4 5 0 -1 14 9 10 8 12 13 11 15 ].


          Look in the blue book for a description of arrays. Matrixes 
          are really just arrays. In fact, matrixes are really arrays 
          of fixed size! PostScript matrix operators only work on 
          matrixes of the right size to be transformation matrixes. 

            2. PostScript transformation matrixes have the right column 
          chopped off. So any CTM that looks like 



[  a   b   0
   c   d   0
   e   f   1  ]


            Will actually be represented by a 2x3 matrix as an array 



[ a b c d e f ].


              Finally, you should be warned the identity matrix is not 
              always 



[  1   0   0
   0   1   0
   0   0   1  ]


                because sometimes there are device dependent features 
                that set it to something else. Let's call this the 
                device default matrix. 

                  The good news is that, it doesn't really matter! As 
                long as you let PostScript apply the rules properly (or 
                you apply them yourself properly), they will work fine 
                anyway. 

                  Just don't be frightened if you give the PostScript 
                commands 

                  matrix currentmatrix == 

                  and your PostScript interpreter doesn't respond with 



[ 1 0 0 1 0 0 ].


                  but instead responds with some close approximation 
                  with some of the numbers wrong. 

                    This should be enough for you to use matrixes in 
                  PostScript. Just use them as arrays. Here is a brief 
                  description of what all the PostScript matrix 
                  commands do, in the context of what we've been 
                  talking about. Notice that each command is repeated 
                  twice. The first time is the ``quickie'' command that 
                  assumes you want to deal with the CTM. The second 
                  lets you do the operation on any transformation 
                  matrix. So you can build your own little CTMs and 
                  swap them around. 

                    In fact, being able to build your own little CTMs 
                  and swap them around is the main practical knowledge 
                  you'll get from this file. 



    - matrix matrix 
      Pushes the identity matrix on the stack. This is not like the 
      string and dict commands that let you create any size object. 
      This command just creates a matrix of the proper size for 
      transformations. In fact, all of these functions are not 
      generally applicable to matrixes. They always assume that your 
      matrix is the 3x3 transformation matrix, which as you know is 
      represented as a 2x3 matrix in PostScript. 


    - initmatrix - 
      Sets the CTM to be the identity matrix. 


    matrix identmatrix matrix 
      Sets given matrix = identity matrix. If you understand why the 
      same array stored on the stack twice is really only one array, 
      then this command will make sense to you. If you don't, don't 
      worry about it. 


    matrix defaultmatrix matrix 
      Sets given matrix = the device default matrix. 


    matrix currentmatrix matrix 
      Sets given matrix = CTM. 


    matrix setmatrix - 
      Sets CTM = given matrix. 


    j k translate - 
      Performs the translate rules on the CTM. 


    j k matrix translate - 
      Performs the translate rules on given matrix. 


    j k scale - 
      Performs the scale rules on the CTM. 


    j k matrix scale - 
      Performs the scale rules on the given matrix. 


    j rotate - 
      Performs the rotate rules on the CTM. 


    j matrix rotate - 
      Performs the rotate rules on the given matrix. 


    matrix concat - 
      Sets CTM = CTM * given matrix. If you don't understand matrix 
      multiplication, don't worry about this. 


    matrix1 matrix2 matrix3 concatmatrix matrix3 
      Sets matrix3 = matrix 1 * matrix2. 


    x y transform x' y' 
      Transforms user space coordinates into device space coordinates 
      using the rules (x',y') = CTM * (x,y). 


    x y matrix transform x' y' 
      Transforms user space coordinates into device space coordinates 
      using the rules (x',y') = given matrix * (x,y). 


    dx dy dtransform dx' dy' 
      Transforms the difference between two user space coordinates into 
      the difference between two device space coordinates using the 
      rules (x',y') = CTM * (x,y). 


    dx dy matrix dtransform dx' dy' 
      Transforms the difference between two user space coordinates into 
      the difference between two device space coordinates using the 
      rules (x',y') = given matrix * (x,y). 


    x' y' itransform x y 
      Transforms device space coordinates into user space coordinates 
      using the rules (x',y') = CTM * (x,y) backwards. 


    x' y' matrix itransform x y 
      Transforms device space coordinates into user space coordinates 
      using the rules (x',y') = given matrix * (x,y) backwards. 


    dx' dy' idtransform dx dy 
      Transforms the difference between two device space coordinates 
      into the difference between two user space coordinates using the 
      rules (x',y') = CTM * (x,y) backwards. 


    dx' dy' matrix idtransform dx dy 
      Transforms the difference between two device space coordinates 
      into the difference between two user space coordinates using the 
      rules (x',y') = given matrix * (x,y) backwards. 


    matrix1 matrix2 invertmatrix matrix2 
      Performs a backwards matrix multiplication. If you don't 
      understand this, don't worry about it. 


    10 Further Reading 

    For a poor explanation of transformation matrixes, read Chapter 4, 
    section 4 of the "red book". (section 4-3 of the version 2 red 
    book). 

      Transformation matrixes are used through all of computer 
    graphics, not just for PostScript. For a thorough discussion of 
    geometrical transformations see: 

      chapter 5 of "Computer Graphics: Principles and Practice", by 
    Foley, van Dam, Feiner, and Hughes. 1991, Addison-Wesley Publishing 
    Company, Reading Massachusetts. ISBN 0-201-12110-7 

      chapter 7 of "Graphics Gems II", edited by James Arvo. 1991, 
    Academic Press, Inc., 1250 6th Avenue, San Diego, CA 92101. ISBN 
    0-12-064480-0. 

      Principles of Interactive Computer Graphics, by Newman and 
    Sproull. 1979, McGraw-Hill. 

      This approach is generalizable to three or more dimensions. To 
    see an example of a CTM for three dimensional graphics, check out 
    The PostScript Zone by anonymous ftp to wilma.cs.brown.edu 
    (128.148.31.66) to get "pub/zone.tar.Z". The PostScript Zone also 
    has examples of arbitrary non-affine transformations and conformal 
    mapping. 

      This document was written with the LaTeX language and formatted 
    by LameTeX, the PostScript hacker's LaTeX.