home *** CD-ROM | disk | FTP | other *** search
/ Collection of Hack-Phreak Scene Programs / cleanhpvac.zip / cleanhpvac / FAQSYS18.ZIP / FAQS.DAT / MATRIX.DOC < prev    next >
Text File  |  1996-04-07  |  45KB  |  897 lines

  1.  
  2.         OTMMATX.DOC     -   matrix transformation tutorial
  3.  
  4.         (or if you prefer, "A proven antidote for VLA 3d tutorials" :)
  5.  
  6.         Copyright (C) 1995, Zach Mortensen  [Voltaire OTM.TAP]
  7.         All rights reserved.
  8.  
  9.         email - mortens1@nersc.gov
  10.  
  11.  
  12. Table of Contents
  13.  
  14.         0.  Introduction
  15.         1.  Math Prerequisites
  16.         2.  Importance of Correct Transformations
  17.         3.  What a Matrix Represents
  18.         4.  Matrix Multiplication
  19.         5.  Transforming a Vector by a Matrix
  20.         6.  Object Space Transformations
  21.         7.  Camera Transformations
  22.         8.  Inverse Transformations
  23.         9.  Hierarchical Transformations
  24.         A.  Precision
  25.         B.  Conclusion
  26.  
  27.  
  28. Introduction
  29.  
  30.             It has been entirely too long since I wrote my last doc, I just
  31.         had to make another one :)  This is a topic which I have spent a great
  32.         deal of time teaching lately, so I decided to make a doc that would
  33.         expedite the process for me.
  34.  
  35.             If you are looking for advice from a certified expert, you will
  36.         not find it in this doc.  I am merely an individual who has spent the
  37.         past year studying realtime rendering, and who is willing to share
  38.         what he has learned.  However, you should rest assured that I do not
  39.         write docs about things I have never implemented in working code, and
  40.         I never code anything I don't fully understand.  In other words, I
  41.         think I know what I am talking about here :)
  42.  
  43.             All of the techniques in this file can be implemented regardless
  44.         of the programming language you use, from assembler to C to Visual
  45.         Basic.  I will, however, be giving any pseudocode examples in C,
  46.         because it seems to be the universal language of coders right now.
  47.         For the sake of simplicity, all code examples will use floating point
  48.         math.  Floating point is the wave of the future, as a matter of fact
  49.         its faster than fixed point integer math on the newest RISC machines
  50.         (PowerPC, DEC Alpha).  Unfortunately, Intel users have been given
  51.         hideously slow floating point processors in the past and are less than
  52.         confident in the ability of their machines; but things will get better
  53.         very shortly.
  54.  
  55.  
  56. Math Prerequisites
  57.  
  58.             Sadly, matrix math is something that is all but ignored in most
  59.         high school curricula in the United States.  But hey, the best stuff
  60.         is skipped in high school, everybody knows that :)  You should not be
  61.         afraid of matrix math just because your high school math teacher does
  62.         not teach it.  Now that I think about it, matrix math is probably
  63.         skipped in high school simply because there is nothing taught in high
  64.         school that applies its principles.
  65.  
  66.             The only matrix math I was taught in high school was for solving
  67.         systems of equations.  Basically, we were taught that a matrix is a
  68.         simple and powerful way to represent a complex system of equations.
  69.         This is a great explanation, although extremely simplistic.  Keep this
  70.         in mind throughout the course of this doc.
  71.  
  72.             The math of matrices is very simple.  Nothing higher than first
  73.         year algebra is used, although an understanding of trigenometry will
  74.         make your life much easier when it comes to understanding the meaning
  75.         of all those numbers in a matrix.  If you have had a course in Linear
  76.         Algebra at a university, this doc will probably be old news to you.
  77.  
  78.  
  79. Importance of Correct Transformations
  80.  
  81.             When I first began coding vector graphics, I had a great
  82.         understanding of trigenometry and anything but fond memories of matrix
  83.         math as it was presented in my high school courses.  To me, matrix
  84.         math seemed to be an unneccessarily complex way to solve a simple
  85.         algebraic problem, like trying to swat a fly with an elephant gun.
  86.         Indeed, many algebraic problems can be solved without the use of
  87.         matrix math.
  88.  
  89.             However, vector graphics pose a system of equations that are
  90.         anything but simple to solve algebraically.  Consider the following:
  91.         in a typical vector world, there are many objects.  Each of these
  92.         objects moves in its own space (object space), relative to its own set
  93.         of coordinate axes.  There are several cameras, each of which moves in
  94.         its own space (camera space or eyespace) according to its own set of
  95.         coordinate axes.  At some point, the objects must be transformed from
  96.         object space to eyespace so they can be displayed as the eye sees
  97.         them.  Apart from this, there is the issue of object hierarchies.  In
  98.         a realistic vector environment, object hierarchies must be handled
  99.         correctly.  These issues present formidable challenges without the use
  100.         of matrix math.  However, by using matrix math we can deal with all
  101.         of these issues in a simple and speedy manner.
  102.  
  103.             Granted, I am assuming that everyone wants to make simulation
  104.         quality vector code.  This type of code requires correct
  105.         transformations.  Speaking from a demo scene point of view, very few
  106.         demos implement correct transformations simply because they are not
  107.         required for the application.  The stereotypical vector scene in a
  108.         demo is a childish attempt to display speed and pretty rendering on a
  109.         single object.  Most demo coders do not care if their objects are
  110.         moving correctly, they just want them to move around a bit.  This
  111.         attitude is fine, assuming you never want to do anything with your
  112.         code besides show a spinning cube or toroid.
  113.  
  114.             Any impressive vector application (game, simulator, etc.) requires
  115.         correct transformations.  Consider the following example.  An airplane
  116.         is oriented such that its nose is pointing in the positive z
  117.         direction, its right wing is pointing in the positive x direction, its
  118.         cockpit is pointing in the positive y direction.  The airplane's local
  119.         x, y, and z axes are aligned with the world x, y, and z axes.  If this
  120.         airplane were rotated 90 degrees about its y axis, its nose would be
  121.         pointing toward the world -x axis, its right wing pointing toward
  122.         the world +z, and its cockpit remaining in the world +y direction.
  123.         Most transformations, whether correct or incorrect, would accomplish
  124.         this.  Here is the 'acid test' to see whether your transformations are
  125.         correct.  From this new position, rotate the airplane about its z
  126.         axis.  If your transformations are correct, the airplane will rotate
  127.         about its own z axis (it will roll).  If your transformation is
  128.         incorrect, the airplane will rotate about the world z axis (its nose
  129.         will pitch up or down).
  130.  
  131.             This rather silly example poses quite a serious question.  If your
  132.         transformations are not correct, how will you control object movement
  133.         in a vector world?  How will you guarantee your airplane will roll
  134.         when you tell it to instead of pitching?  The same problem arises with
  135.         incorrect camera rotation.  The consequences of such incorrectness in
  136.         a flight simulator or game would make the game unplayable.
  137.  
  138.             The solution to this problem is simple; the use of 4x4 matrix
  139.         transformations.
  140.  
  141.  
  142. What a Matrix Represents
  143.  
  144.             Before we continue, it will help you greatly to understand what
  145.         the values in a matrix represent.  A 4x4 matrix contains 4 vectors,
  146.         which represent the world space coordinates of the x, y and z unit
  147.         axis vectors, and the world space coordinate which is the origin of
  148.         these axis vectors.
  149.  
  150.                 X     Y     Z     C
  151.             ┌                         ┐
  152.             │ ┌   ┐ ┌   ┐ ┌   ┐ ┌   ┐ │
  153.             │ │   │ │   │ │   │ │   │ │
  154.             │ │X  │ │X  │ │X  │ │0  │ │
  155.             │ │   │ │   │ │   │ │   │ │
  156.             │ │   │ │   │ │   │ │   │ │
  157.             │ │Y  │ │Y  │ │Y  │ │0  │ │
  158.             │ │   │ │   │ │   │ │   │ │
  159.             │ │   │ │   │ │   │ │   │ │
  160.             │ │Z  │ │Z  │ │Z  │ │0  │ │
  161.             │ └   ┘ └   ┘ └   ┘ │   │ │
  162.             │ ┌───────────────┐ │   │ │
  163.         O   │  X     Y     Z    │1  │ │
  164.             │ └───────────────┘ └   ┘ │
  165.             └                         ┘
  166.  
  167.         The X column contains the world space coordinates of the local X axis
  168.         The Y column contains the world space coordinates of the local Y axis
  169.         The Z column contains the world space coordinates of the local Z axis
  170.  
  171.         These vectors are unit vectors.  A unit vector is a vector whose
  172.         magnitude is 1.  Basically, unit vectors are used to define
  173.         directions, when magnitude is not really important.
  174.  
  175.         The C column always contains the specified values
  176.         The O row contains the world space coordinates of the object's origin
  177.  
  178.         You can make life easy for yourself by storing matrices which contain
  179.         axis information in each object.  I keep two matrices for every
  180.         object; omatrix, which stores the object space matrix, and ematrix,
  181.         which stores the eyespace matrix for the object.
  182.  
  183.         A special matrix is the identity matrix:
  184.  
  185.         ┌                         ┐
  186.         │ ┌   ┐ ┌   ┐ ┌   ┐ ┌   ┐ │
  187.         │ │   │ │   │ │   │ │   │ │
  188.         │ │1  │ │0  │ │0  │ │0  │ │
  189.         │ │   │ │   │ │   │ │   │ │
  190.         │ │   │ │   │ │   │ │   │ │
  191.         │ │0  │ │1  │ │0  │ │0  │ │
  192.         │ │   │ │   │ │   │ │   │ │
  193.         │ │   │ │   │ │   │ │   │ │
  194.         │ │0  │ │0  │ │1  │ │0  │ │
  195.         │ └   ┘ └   ┘ └   ┘ │   │ │
  196.         │ ┌───────────────┐ │   │ │
  197.         │  0     0     0    │1  │ │
  198.         │ └───────────────┘ └   ┘ │
  199.         └                         ┘
  200.  
  201.         Notice why the identity matrix is special?  The identity matrix
  202.         represents a set of object axes that are aligned with the world axes.
  203.         Remember that the vectors stored in the matrix are unit vectors.  Now,
  204.         because the world x coordinate of the local x axis is 1, the world y
  205.         and z coordinates of the local x axis are 0, and the origin vector
  206.         is [0, 0, 0], the local x axis lies directly on the world x axis.  The
  207.         same is true for the local y and z axes.
  208.  
  209.         The other special property of the identity matrix is given away in its
  210.         name.  If you are familiar with math, you know that there are identity
  211.         elements in the set of any arithmetic operation.  When an binary
  212.         operation is performed on some operand and the identity element of the
  213.         set, the operand is the result of the operation.  For example,
  214.         identity elements for multiplication and division are 1, and identity
  215.         elements for addition and subtraction are 0.  x + 0 = x; x - 0 = x; x
  216.         * 1 = x; x / 1 = x.  Similarly, [x] * [identity] = [x] (I will denote
  217.         matrices in brackets [] throughout this doc, for example [x] is
  218.         "matrix x").
  219.  
  220.  
  221. Matrix Multiplication
  222.  
  223.             There are two matrix operations which we will use in our
  224.         matrix transformations, multiplying (concatenating) two matrices, and
  225.         transforming a vector by a matrix.  We will now examine the first of
  226.         these two operations, matrix multiplication.
  227.  
  228.             Matrix multiplication is the operation by which one matrix is
  229.         transformed by another.  A very important thing to remember is that
  230.         matrix multiplication is not commutative.  That is, [a] * [b] != [b] *
  231.         [a].  For now, it will suffice to say that a matrix multiplication
  232.         stores the results of the sum of the products of matrix rows and
  233.         columns.  Here is some example code of a matrix multiplication routine
  234.         which multiplies matrix [a] * matrix [b], then copies the result to
  235.         matrix a.
  236.  
  237.  
  238. void matmult(float a[4][4], float b[4][4])
  239. {
  240.     float temp[4][4];       // temporary matrix for storing result
  241.     int i, j;               // row and column counters
  242.  
  243.     for (j = 0; j < 4; j++)         // transform by columns first
  244.         for (i = 0; i < 4; i++)     // then by rows
  245.             temp[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] +
  246.                          a[i][2] * b[2][j] + a[i][3] * b[3][j];
  247.  
  248.     for (i = 0; i < 4; i++)         // copy result matrix into matrix a
  249.         for (j = 0; j < 4; j++)
  250.             a[i][j] = temp[i][j];
  251. }
  252.  
  253.             I have been informed that there is a faster way of multiplying
  254.         matrices, which involves taking the dot product of rows and columns.
  255.         However, I have yet to implement such a method, so I will not discuss
  256.         it here at this time.
  257.  
  258.  
  259. Transforming a Vector by a Matrix
  260.  
  261.             This is the second operation which is required for our matrix
  262.         transformations.  It involves projecting a stationary vector onto
  263.         transformed axis vectors using the dot product.  One dot product is
  264.         performed for each coordinate axis.
  265.  
  266.  
  267.         x = x0 * matrix[0][0] + y0 * matrix[1][0] + z0 * matrix[2][0] +
  268.             w0 * matrix[3][0];
  269.  
  270.         y = x0 * matrix[0][1] + y0 * matrix[1][1] + z0 * matrix[2][1] +
  271.             w0 * matrix[3][1];
  272.  
  273.         z = x0 * matrix[0][2] + y0 * matrix[1][2] + z0 * matrix[2][2] +
  274.             w0 * matrix[3][2];
  275.  
  276.  
  277.         The x0, y0, etc. coordinates are the original object space coordinates
  278.         for the vector.  That is, they never change due to transformation.
  279.  
  280.         "Alright," you say.  "Where did all the w coordinates come from???"
  281.         Good question :)  The w coordinates come from what is known as a
  282.         homogenous coordinate system, which is basically a way to represent 3d
  283.         space in terms of a 4d matrix.  Because we are limiting ourselves to
  284.         3d, we pick a constant, nonzero value for w (1.0 is a good choice,
  285.         since anything * 1.0 = itself).  If we use this identity axiom, we can
  286.         eliminate a multiply from each of the dot products:
  287.  
  288.  
  289.         x = x0 * matrix[0][0] + y0 * matrix[1][0] + z0 * matrix[2][0] +
  290.             matrix[3][0];
  291.  
  292.         y = x0 * matrix[0][1] + y0 * matrix[1][1] + z0 * matrix[2][1] +
  293.             matrix[3][1];
  294.  
  295.         z = x0 * matrix[0][2] + y0 * matrix[1][2] + z0 * matrix[2][2] +
  296.             matrix[3][2];
  297.  
  298.  
  299.         These are the formulas you should use to transform a vector by a
  300.         matrix.
  301.  
  302.  
  303. Object Space Transformations
  304.  
  305.             Now that we know how to multiply matrices together, we can
  306.         implement the actual formulas used in our transformations.  There are
  307.         three operations performed on a vector by a matrix transformation:
  308.         translation, rotation, and scaling.
  309.  
  310.             Translation can best be described as linear change in position.
  311.         This change can be represented by a delta vector [dx, dy, dz], where
  312.         dx represents the change in the object's x position, dy represents the
  313.         change in its y position, and dz its z position.
  314.  
  315.             If done correctly, object space translation allows objects to
  316.         translate forward/backward, left/right, and up/down, relative to the
  317.         current orientation of the object.  Using our airplane as an example,
  318.         if the nose of the airplane is oriented along the object's local z
  319.         axis, then translating the airplane in the +z direction will make the
  320.         airplane move forward (the direction in which its nose is pointing)
  321.         regardless of the airplane's orientation.
  322.  
  323.         Here is the translation matrix:
  324.  
  325.         ┌                         ┐
  326.         │ ┌   ┐ ┌   ┐ ┌   ┐ ┌   ┐ │
  327.         │ │   │ │   │ │   │ │   │ │
  328.         │ │1  │ │0  │ │0  │ │0  │ │
  329.         │ │   │ │   │ │   │ │   │ │
  330.         │ │   │ │   │ │   │ │   │ │
  331.         │ │0  │ │1  │ │0  │ │0  │ │
  332.         │ │   │ │   │ │   │ │   │ │
  333.         │ │   │ │   │ │   │ │   │ │
  334.         │ │0  │ │0  │ │1  │ │0  │ │
  335.         │ └   ┘ └   ┘ └   ┘ │   │ │
  336.         │ ┌───────────────┐ │   │ │
  337.         │  dx    dy    dz   │1  │ │
  338.         │ └───────────────┘ └   ┘ │
  339.         └                         ┘
  340.  
  341.         where [dx, dy, dz] is the displacement vector.  After this operation,
  342.         the object will have moved in its own coordinate system, according to
  343.         the displacement (translation) vector.
  344.  
  345.             The next operation that is performed by our matrix transformation
  346.         is rotation.  Rotation can be described as circular motion about some
  347.         axis, in this case the axis is one of the object's local axes.  Since
  348.         there are three axes in each object, we need to rotate around each of
  349.         them.  Here are the matrices for rotation about each axis:
  350.  
  351.         about the x axis:
  352.  
  353.         ┌                         ┐
  354.         │ ┌   ┐ ┌   ┐ ┌   ┐ ┌   ┐ │
  355.         │ │   │ │   │ │   │ │   │ │
  356.         │ │1  │ │0  │ │0  │ │0  │ │
  357.         │ │   │ │   │ │   │ │   │ │
  358.         │ │   │ │   │ │   │ │   │ │
  359.         │ │0  │ │cx │ │sx │ │0  │ │
  360.         │ │   │ │   │ │   │ │   │ │
  361.         │ │   │ │   │ │   │ │   │ │
  362.         │ │0  │ │-sx│ │cx │ │0  │ │
  363.         │ └   ┘ └   ┘ └   ┘ │   │ │
  364.         │ ┌───────────────┐ │   │ │
  365.         │  0     0     0    │1  │ │
  366.         │ └───────────────┘ └   ┘ │
  367.         └                         ┘
  368.  
  369.  
  370.         about the y axis:
  371.  
  372.         ┌                         ┐
  373.         │ ┌   ┐ ┌   ┐ ┌   ┐ ┌   ┐ │
  374.         │ │   │ │   │ │   │ │   │ │
  375.         │ │cy │ │0  │ │-sy│ │0  │ │
  376.         │ │   │ │   │ │   │ │   │ │
  377.         │ │   │ │   │ │   │ │   │ │
  378.         │ │0  │ │1  │ │0  │ │0  │ │
  379.         │ │   │ │   │ │   │ │   │ │
  380.         │ │   │ │   │ │   │ │   │ │
  381.         │ │sy │ │0  │ │cy │ │0  │ │
  382.         │ └   ┘ └   ┘ └   ┘ │   │ │
  383.         │ ┌───────────────┐ │   │ │
  384.         │  0     0     0    │1  │ │
  385.         │ └───────────────┘ └   ┘ │
  386.         └                         ┘
  387.  
  388.         about the z axis:
  389.  
  390.         ┌                         ┐
  391.         │ ┌   ┐ ┌   ┐ ┌   ┐ ┌   ┐ │
  392.         │ │   │ │   │ │   │ │   │ │
  393.         │ │cz │ │sz │ │0  │ │0  │ │
  394.         │ │   │ │   │ │   │ │   │ │
  395.         │ │   │ │   │ │   │ │   │ │
  396.         │ │-sz│ │cz │ │0  │ │0  │ │
  397.         │ │   │ │   │ │   │ │   │ │
  398.         │ │   │ │   │ │   │ │   │ │
  399.         │ │0  │ │0  │ │1  │ │0  │ │
  400.         │ └   ┘ └   ┘ └   ┘ │   │ │
  401.         │ ┌───────────────┐ │   │ │
  402.         │  0     0     0    │1  │ │
  403.         │ └───────────────┘ └   ┘ │
  404.         └                         ┘
  405.  
  406.  
  407.             The cx, sx, cy, sy, cz, and sz variables are the values of the
  408.         cosines and sines of the angles of rotation about the x, y, and z
  409.         axes, respectively.  Remeber that the angles used represent angular
  410.         displacement just as the values used in the translation step denote a
  411.         linear displacement.  Correct transformation CANNOT be accomplished
  412.         with matrix multiplication if you use the cumulative angles of
  413.         rotation.  I have been told that quaternions are able to perform this
  414.         operation correctly, however I know nothing of quaternions and how
  415.         they are implemented.  The incremental angles used here represent
  416.         rotation from the current object orientation.  In other words, by
  417.         rotating 1 degree about the z axis, you are telling your object
  418.         "Rotate 1 degree about your z axis, regardless of your current
  419.         orientation, and regardless of how you got to that orientation."  If
  420.         you think about it a bit, you will realize that this is how the real
  421.         world operates.  In object space, the series of rotations an object
  422.         undergoes to attain a certain orientation have no effect on the
  423.         object space results of any upcoming rotations.
  424.  
  425.             Now that we know the matrix formulas for translation and rotation,
  426.         we can combine them to transform our objects.  The formula for
  427.         transformations in object space is
  428.  
  429.         [O] = [O] * [T] * [X] * [Y] * [Z]
  430.  
  431.         where O is the object's matrix, T is the translation matrix, and X, Y,
  432.         and Z are the rotation matrices for their respective axes.  Remember,
  433.         that order of matrix multiplication is very important!
  434.  
  435.             The recursive assignment of O poses a question:  What is the
  436.         original value of the object matrix?  To eliminate any terrible errors
  437.         in transformation, the matrices which store an object's orientation
  438.         should always be initialized to identity.
  439.  
  440.  
  441. Camera Transformations
  442.  
  443.             Good camera code is a key to a good vector engine.  If the camera
  444.         does not move correctly in a first-person type simulation, any hope of
  445.         realism is lost.  Fortunately, camera code is very easy to implement
  446.         using matrices.
  447.  
  448.             Each camera should contain one matrix which defines its current
  449.         orientation.  Like the object matrix, the camera matrix (I call it
  450.         cmatrix) should be initialized to identity to avoid hideous errors.
  451.         The camera matrix is built in exactly the same way as the object
  452.         matrix, using CT, CX, CY and CZ.  These translation and
  453.         rotation matrices are made in exactly the same way as their
  454.         object space counterparts, except for the obvious fact that
  455.         they are made using camera rotation and translation vectors.
  456.         Depending on your implementation, the components of the displacement
  457.         vectors may need to be negated.  Sometimes all of the [dx, dy, dz] and
  458.         [xangle, yangle, zangle] need to be negated, sometimes some of them.
  459.         Once again, it depends on your implementation.  If you find your
  460.         camera is moving forward instead of backward, right instead of left,
  461.         up instead of down, etc. you need to negate a vector component
  462.         somewhere.  Once you get that straightened out, build the camera
  463.         matrix like this
  464.  
  465.         [C] = [C] * [CT] * [CX] * [CY] * [CZ]
  466.  
  467.         Once you have made the camera matrix, you can transform your object
  468.         matrices to camera space with a simple matrix multiplication
  469.  
  470.         [E] = [O] * [C]
  471.  
  472.         where [E] is the eyespace matrix, [O] is the object space matrix for
  473.         the object, and [C] is the camera space matrix for the camera you are
  474.         using (which we calculated above).
  475.  
  476.             If you are an incredibly astute individual, you will have realized
  477.         that I have left a step out of this process.  Where did I add the
  478.         world coordinates of the object's origin?  The translation in the
  479.         object matrix is a displacement which is added to the origin of
  480.         the object, but what of the original value of the object's origin?
  481.  
  482.             The reason I left this step out until now is because it is easiest
  483.         to perform this operation in the middle of transforming an object to
  484.         eyespace.  Something to remember is that the object origin is
  485.         expressed in terms of world space coordinates.  If we want our
  486.         transformations to be correct, we have to add world space coordinates
  487.         to world space coordinates, adding them to camera or object space
  488.         coordinates would give us incorrect results.  The only time we have
  489.         world space coordinates in this process is after object transformation
  490.         is complete.  At this time, we can add the coordinates of the object's
  491.         origin to the origin vector found in the transformation matrix.  Here
  492.         is some example code illustrating this process.  omatrix contains the
  493.         object space transformation matrix, cmatrix contains the camera
  494.         transformation matrix.  ematrix will be the result of omatrix *
  495.         cmatrix.
  496.  
  497.  
  498.     (initialize tmatrix, xmatrix, ymatrix, zmatrix...)
  499.  
  500.     ...
  501.  
  502.     matmult(omatrix, tmatrix);      // translate the object
  503.     matmult(omatrix, zmatrix);      // rotate about z
  504.     matmult(omatrix, xmatrix);      // rotate about x
  505.     matmult(omatrix, ymatrix);      // rotate about y
  506.  
  507.     initmatrix(ematrix);            // initialize eye space matrix to identity
  508.  
  509.     matmult(ematrix, omatrix);      // copy the object space matrix to eye space
  510.  
  511.     ematrix[3][0] += origin->lx;    // add origin vector
  512.     ematrix[3][1] += origin->ly;
  513.     ematrix[3][2] += origin->lz;
  514.  
  515.     matmult(ematrix, cmatrix);      // convert world space to eye space
  516.  
  517.  
  518.  
  519. Inverse Transformations
  520.  
  521.             Inverse transformations are used to perform hidden surface removal
  522.         in object space, without transforming any normal vectors.  Likewise,
  523.         the same technique can be used in shading.  This method provides some
  524.         obvious speed increases over transforming normal vectors, the correct
  525.         culling or shading information can be determined by inversely
  526.         transforming a view or light vector, then taking the dot product of
  527.         this inversely transformed vector and the non-transformed normal
  528.         vectors.  In addition to the rendering time saved by not transforming
  529.         normal vectors, this method can give significant time savings by
  530.         allowing you to hide points as well as polys.  If you determine that
  531.         only the points contained in visible polygons are visible, you can
  532.         avoid transforming points contained in those polygons which are not
  533.         visible.  This usually accounts for around half of the points in an
  534.         object.
  535.  
  536.             Inverse transformation requires an inverse matrix, which is made
  537.         by negating all of the angles in the constituent rotation matrices and
  538.         multiplying them together in reverse order.  As you can imagine, this
  539.         is quite a slow process, especially when a camera and hierarchical
  540.         object are involved!  Thankfully though, there is a shortcut.
  541.  
  542.             Certain types of matrices (I believe those that have a determinant
  543.         of 1) can be inverted by swapping rows and columns.  The
  544.         transformation matrix is this type of matrix.  I made a utility to
  545.         test this property, generating an inverse matrix with the negate and
  546.         multiply in reverse order algorithm, and comparing it to the original
  547.         matrix.  I found that transformation matrices do fit the pattern of
  548.         inversion by row and column swapping.
  549.  
  550.             This means that you can inverse transform your view and light
  551.         vectors with the following formulas (notice that these are identical
  552.         to the regular transformation formulas, but have the row and column
  553.         indices swapped):
  554.  
  555.  
  556.         x = x0 * matrix[0][0] + y0 * matrix[0][1] + z0 * matrix[0][2];
  557.  
  558.         y = x0 * matrix[1][0] + y0 * matrix[1][1] + z0 * matrix[1][2];
  559.  
  560.         z = x0 * matrix[2][0] + y0 * matrix[2][1] + z0 * matrix[2][2];
  561.  
  562.  
  563.         If you are a smart one, you will also notice that there are only 3
  564.         terms in these equations, the w term (translation part of the matrix)
  565.         is missing.  This is because we are inverse transforming, the result
  566.         is object space.  We want all of our vectors to start at the origin
  567.         for this operation, in object space the origin is [0, 0, 0].
  568.  
  569.  
  570. Hierarchical Transformations
  571.  
  572.             I must confess, MechWarrior ][ is the game that inspired me to
  573.         grind out all of this matrix code.  I found it so realistic, being
  574.         able to move in so many different coordinate systems (I wonder if the
  575.         casual user realizes this? :)  I had been wanting to implement all
  576.         this in my code for quite some time, and playing MW2 was the event
  577.         that pushed me over the edge.
  578.  
  579.             Another thing that this game showed me was the usefulness of
  580.         hierarchical transformations.  If you are lost in my terminology, let
  581.         me explain what I mean by hierarchical transformations.
  582.  
  583.             Apart from being a great spelling bee word, a hierarchy is an
  584.         organazation of things into levels.  In a very general sense, the
  585.         things higher up in a hierarchy have control over the lower things.
  586.         This applies to business, government, and our favorite subject, matrix
  587.         transformations.
  588.  
  589.             As far as matrix transformations are concerned, consider an arm as
  590.         an example of a hierarchical object.  The topmost object in the arm
  591.         hierarchy is the bicep or upper arm, followed by the forearm, the
  592.         hand, and the fingers.  Each of these 'objects' has an origin, the
  593.         bicep has the shoulder, the forearm has the elbow, the hand has the
  594.         wrist, and the fingers have the knuckles.
  595.  
  596.             Here is where the hierarchical part comes into play, remember what
  597.         I said earlier about higher things on a hierarchy being able to
  598.         control the lower things?  Well, move your bicep up in the air by
  599.         pivoting your shoulder.  Surprise!  Your forearm, hand and fingers
  600.         moved with your bicep.  Now move your forearm by bending your elbow.
  601.         Notice that your hand and fingers moved, but your bicep did not.  This
  602.         is because your forearm is lower in the hierarchy than your bicep, and
  603.         therefore has no control over it.
  604.  
  605.             Here is an interesting question.  How on earth do you
  606.         mathematically represent this hierarchy of objects in a correct
  607.         manner?  More importantly, how can you do it quickly?  Using matrices,
  608.         you can correctly transform a hierarchy of objects in no more time
  609.         than it takes to transform non-hierarchical objects.
  610.  
  611.             Alright, its time for a little side trip into the dreaded land of
  612.         data structures.  While it is coding hell for the beginner, the land
  613.         of data structures is the playground of any experienced programmer.
  614.         Data structures are easy, its the implementation that kills most
  615.         people.  Most people with little experience in data structures and
  616.         data relationship immediately try to swat a fly with an elephant gun
  617.         by applying every data structure in the book to a simple problem.
  618.         "How about if I make an array of stacks containing doubly linked lists
  619.         of AVL trees, would that work?"  Well, I'm not one to say it would
  620.         not.  However, I have found that the simplest solution to a problem is
  621.         generally the best.
  622.  
  623.             In this case, the simplest solution to creating a hierarchical
  624.         object data structure is to have parent objects keep track of their
  625.         children only.
  626.  
  627.  
  628. typedef struct object
  629. {
  630.     (other stuff here)
  631.  
  632.     ...
  633.  
  634.     object **children;
  635.     int numchildren;
  636.  
  637. } object;
  638.  
  639.  
  640.         The **children member of the struct above allows you to dynamically
  641.         allocate enough memory for the children of each object.  For example,
  642.         if we were making an instance of this struct for a hand, we would
  643.         allocate an array of five pointers for **children.  These pointers
  644.         would be set to the addresses of the object structs which contain the
  645.         children of the hand, namely the fingers.
  646.  
  647.             Now that we have discussed how to implement the hierarchy data
  648.         structures, lets move on to cover how to perform the actual
  649.         hierarchical transformations.  First, if you will recall, our system
  650.         of matrix transformations handles incremental rotation and
  651.         translation; that is, objects are transformed according to some change
  652.         in position and change in angles of rotation.  This feature lends
  653.         itself well to hierarchical transformation.
  654.  
  655.             If you were to transform two objects by the same matrix, what
  656.         would be the result?  The two objects would have the same orientation
  657.         relative to each other before and after the transformation.  This
  658.         property of matrix transformation is key to hierarchical
  659.         transformations.  Consider the arm example again.  Keeping your elbow
  660.         and wrist stiff, extend your arm in front of you and raise and lower
  661.         it by rotating your arm at the shoulder.  Your arm will stay straight,
  662.         it appears that all objects (bicep, forearm, hand, fingers) are
  663.         behaving as one object.
  664.  
  665.             If this were the extent of a hierarchy's usefulness, we could
  666.         simply transform each child object using the matrix of its parent.
  667.         But we want each child object to be able to move on its own too; that
  668.         is, we want to be able to bend the elbow, wrist, and fingers while we
  669.         raise and lower our shoulders, using the arm example again.  Here is
  670.         where the incremental rotation comes in handy.  Consider the matrix of
  671.         a parent object as a starting point.  The orientation of a child can
  672.         then be expressed in terms of this parent orientation plus some
  673.         rotation and translation increment.  This increment can be expressed
  674.         in terms of an object matrix.
  675.  
  676.             Actually, we already calculate this matrix in our code; in my code
  677.         its the omatrix member of the object struct.  This matrix contains the
  678.         orientation of the object, and we can easily express this orientation
  679.         in terms of an increment to the orientation of a parent object.  To do
  680.         this, simply understand that when you rotate the forearm 5 degrees,
  681.         you are putting a 5 degree bend in your arm between the forearm and
  682.         the bicep.  Likewise, translating the forearm or hand would move it
  683.         relative to its parent according to the displacement vector specified.
  684.         Of course, the initial position of the object's origin must be given
  685.         as a displacement from the origin of the parent object if you are
  686.         going to use this system of object hierarchy.
  687.  
  688.             Here is where the big advantages of this method come into play.
  689.         According to what we have already said, the transformation formula for
  690.         a child in an object hierarcy would be
  691.  
  692.         [O] = [O] * [T] * [X] * [Y] * [Z] * parent.[O] * parent.parent.[O] ...
  693.         [E] = [O] * [C]
  694.  
  695.         where parent.[O] is the object space matrix of the parent to this
  696.         object, parent.parent.[O] is the object space matrix of the parent's
  697.         parent, etc.
  698.  
  699.         We can shorten this definition to
  700.  
  701.         [E] = [O] * [T] * [X] * [Y] * [Z] * parent.[O] * ... * [C]
  702.  
  703.         Since [E] = [O] * [C], we can substitute parent.[E] = parent.[O] *
  704.         [C].  Then, our transformation formula becomes
  705.  
  706.         [E] = [O] * [T] * [X] * [Y] * [Z] * parent.[E]
  707.  
  708.         Which is the same number of matrix multiplies as our original
  709.         transformation formula!
  710.  
  711.             Now back to data structures for a second, so we can make some
  712.         pseudo code illustrating this point.  In my rendering engine, I keep a
  713.         list of objects to be rendered.  Using this method of hierarchy, only
  714.         the parent object in the hierarchy should be in this list.  This is
  715.         because all objects in the object list are rendered using the camera
  716.         matrix, whereas all children must be rendered using the eyespace
  717.         matrix of their parent (which contains the parent object space matrix
  718.         and the camera matrix).  Therefore, in a call to transform or render
  719.         an object, you should make sure that the object will transform and
  720.         render its children.  here is some pseudocode
  721.  
  722. void transformobject(object *obj, float cmatrix[4][4])
  723. {
  724.  
  725.     (do transformations on this object)
  726.  
  727.     ...
  728.  
  729.     for (count = 0; count < obj->numchildren; count++)
  730.         transformobject(obj->children[count], obj->ematrix);
  731.  
  732. }
  733.  
  734. void renderobject(object *obj)
  735. {
  736.  
  737.     (render the object however you like)
  738.  
  739.     ...
  740.  
  741.     for (count = 0; count < obj->numchildren; count++)
  742.         renderobject(obj->children[count]);
  743.  
  744. }
  745.  
  746.  
  747. Precision
  748.  
  749.             There is one drawback to this method of matrix transformation, it
  750.         requires that the values stored in your matrix be very precise.  This
  751.         is a problem because all digital representations of fractional numbers
  752.         are approximated somewhat, and no matter how precise the
  753.         approximation, errors will propagate.  This means that the more you
  754.         use an approximated value in calculations, the less precise the value
  755.         becomes.  There are several solutions to this problem, I will briefly
  756.         discuss each and then leave the decision to you.
  757.  
  758.             The first (and most obvious) solution is to use the most precise
  759.         data type availible.  On the PC, we have 64 bit (double) and 80 bit
  760.         (long double) floating point data types.  Clearly, using these data
  761.         types will result in VERY little loss of precision in calculations.
  762.         This is a viable solution to our problem but may not be desireable due
  763.         to the larger storage requirements and possible speed hits which
  764.         accompany these data types.
  765.  
  766.             The second solution is to use 32 bit single precision floating
  767.         point data.  Its precision is more than adequate in most cases, and
  768.         its speed is tolerable when a floating point coprocessor is present.
  769.         Also, single precision floats do not require any more space to store
  770.         than long integers.  Disadvantages of this data type are that it is
  771.         somewhat slow even on machines with a floating point coprocessor, and
  772.         there is always the chance that someone without a FPU will use the
  773.         software.  In this case, pure floating point math will be anywhere
  774.         from 10 to 100 times slower than integer math.
  775.  
  776.             The third option is to use integer math.  The obvious benefit here
  777.         is speed, the obvious disadvantage is precision.  16.16 integer math
  778.         (16 bit integer, 16 bit fraction) allows for less than 5 decimal
  779.         places of precision.  This may sound like a lot, but consider the fact
  780.         that the axis vectors in the transformation matrix all have a
  781.         magnitude of 1, which means that the individual x, y, and z components
  782.         are always less than or equal to 1.  Your fractional bits become very
  783.         important in such a situation.
  784.  
  785.             As far as my personal preference, I use single precision floating
  786.         point math in my transformation matrix.  I have found it to be the
  787.         best compromise between speed and precision.  As processors become
  788.         more and more adept at floating point calculation, floating point math
  789.         will be faster than integer math.  Many of the newer RISC based
  790.         processors already have floating point math that is faster than its
  791.         integer counterpart.  For example, friends of mine developing
  792.         PowerPC rendering software tell me that floating point math is three
  793.         to four times faster than integer math on their platforms.  The
  794.         PowerPC has a nifty little instruction called fpmuladd which performs
  795.         a floating point multiply and add in once clock cycle!  It makes your
  796.         matrix multiplication routines pretty fast.  There are also faster
  797.         desktop FPUs.  The floating point unit in a DEC Alpha chip is roughly
  798.         the same speed as those in Cray supercomputers made in the early
  799.         1980's!
  800.  
  801.             Now, about how to handle the loss of precision.  Two things
  802.         happen when a matrix loses precision; its axis vectors change
  803.         magnitude so that they are no longer unit vectors, and its axis
  804.         vectors "wander" around a bit so that they are no longer
  805.         perpendicular to each other.  I have implemented both integer and
  806.         single precision floating point versions of these matrix
  807.         transformations.  I found that the 16.16 fixed point integer versions
  808.         will lose precision after somewhere around 10^2 transformations, while
  809.         the single precision floating point version shows no noticable loss of
  810.         precision after 10^5 transformations.  However, there was a slightly
  811.         noticable wobble of objects in the third level of hierarchy when using
  812.         single precision floating point.  I attribute this to a normal,
  813.         usually unnoticable loss of precision which is more noticable because
  814.         it is shown in the same frame as objects transformed with more precise
  815.         versions of the same matrix.
  816.  
  817.             If you are a die hard integer math freak who refuses to accept the
  818.         fact that floating point is the wave of the future, there are a few
  819.         things you can do to justify your use of integer math with reasonable
  820.         matrix precision.  First, you could try using 0.32 fixed point in the
  821.         rotation portion of the transformation matrix.  However, you are going
  822.         to have to do some 64 bit shifting around, and some tricky shifting in
  823.         your matrix multiplication routine to accomidate translation values,
  824.         which are almost always greater than 1.  The next method involves
  825.         fixing your matrix so all the vectors are the proper length and
  826.         mutually perpendicular.  This is quite a math problem to solve if you
  827.         have never considered the solution or have no knowledge of vector
  828.         operations.  There are two ways of going about this, one involves dot
  829.         products, the other involves cross products.
  830.  
  831.             The dot product method is based on the fact that the dot product
  832.         of perpendicular vectors is 0, because the dot product is the
  833.         projection of one vector onto another.  If the dot product is not 0,
  834.         you have a value which is related to how far the vectors overlap in a
  835.         certain direction.  By subtracting this value from the vector, you can
  836.         straighten it in that direction.  After you straighten all your
  837.         vectors in this manner, you re-normalize them so that their lengths
  838.         are 1 (length changes as a result of the perpendicularity correction),
  839.         and you are set.
  840.  
  841.             The cross product method involves the fact that the cross product
  842.         operation yeilds a vector which is perpendicular to its operands.  By
  843.         taking the cross product of two axes, you can make a third axis which
  844.         is perpendicular to both.  Then, by taking the cross product of this
  845.         new axis and the first of the two axes in the first cross product
  846.         operation, you can generate a new second axis which is perpendicular
  847.         to axes one and three.  One is perpendicular to three and two, two is
  848.         perpendicular to three.  There you have it, mutual perpendicularity.
  849.         Of course, you also need to normalize these vectors when you are done.
  850.  
  851.  
  852. Conclusion
  853.  
  854.             Wow, writing docs is loads of fun...I wonder why I waited this
  855.         long to make a new one?  heh...
  856.  
  857.             All of this stuff came from my head.  I'm not the type who sits
  858.         down in front of a terminal with a copy of Foley's book (I don't even
  859.         own a copy of that monster...probably never will) or any other book
  860.         for that matter (don't own any books on graphics at all, come to think
  861.         of it :)  On the other hand, I'm not claiming that everything in here
  862.         is my own idea.  Actually, there are no big secrets divulged here,
  863.         sorry if thats what you were looking for.  These techniques are pretty
  864.         much common knowledge, if that were not the case, how would I have
  865.         found out about them? :)  "So why did you write a doc then, fool?"
  866.         Because I have found myself spending lots of time explaining this
  867.         stuff lately, and its better for all parties involved for me to write
  868.         things down in a doc rather than teaching the same things to different
  869.         people day after day.  Now I can just say, "here, read this! :)"
  870.  
  871.             I have been asked if its ok to publish my other docs in diskmags,
  872.         newsletters, etc.  I have no problem with this whatsoever, as long as
  873.         I am dealt with fairly.  That is, you can publish this doc anywhere as
  874.         long as you do not lead anyone to believe it is not my work.
  875.  
  876.         Greets to -
  877.  
  878.             OTM
  879.             TAP coders
  880.             lfp
  881.             HardCode
  882.             Darkshade and wili
  883.             StarScream
  884.             ShadowH
  885.             Daredevil
  886.             MaxD
  887.             tmL
  888.             Simm
  889.             MoominG
  890.             Silvio
  891.             MiKiEx
  892.             Riz
  893.  
  894.             y todos he olvidado
  895.  
  896.  
  897.