home *** CD-ROM | disk | FTP | other *** search
/ Collection of Hack-Phreak Scene Programs / cleanhpvac.zip / cleanhpvac / FAQSYS18.ZIP / FAQS.DAT / 3DROTATE.DOC < prev    next >
Text File  |  1996-01-04  |  18KB  |  485 lines

  1.  
  2.         ╓────────────────┤% VLA Proudly Presents %├────────────────╖
  3.         ║                                                          ║
  4.         ╙──────────────────────────────────────────────────────────╜
  5.  
  6. ──────────────────────────────────────────────────────────────────────────────
  7.      ────────────────────────────────────────────────────────────────────
  8.           ──────────────────────────────────────────────────────────
  9.               Three Dimensional Rotations For Computer Graphics
  10.           ──────────────────────────────────────────────────────────
  11.      ────────────────────────────────────────────────────────────────────
  12. ──────────────────────────────────────────────────────────────────────────────
  13.                               By Lithium /VLA
  14.  
  15.  
  16.  
  17.     One of the most difficult programming difficulties you will face is that
  18. of representing a 3D world on that 2D screen in front of you.  It requires
  19. some linear alegbra that may be difficult for some, so I will spend some
  20. bytes explaining the mathmatic computations of using matricies in addition
  21. to the equations to get you going.  This document is intended to be an aid
  22. to anyone programming in any language, as a result it will use mathmatic
  23. notation.  If you are worthy of using these routines, you ought to be able
  24. to get them into your favorite language.  All I ask is that you pay a little
  25. tribute to your programming buddies in VLA.
  26.  
  27.  
  28.     If you aren't a math person, skip to the end and get the final equations.  
  29. Just be forewarned, implimenting these equations into a coherient 3D world 
  30. is hard enough when you undersand the mathmatics behind them...
  31.  
  32.                 
  33.                    REAL PROGRAMMERS AREN'T AFRAID OF MATH
  34.  
  35.  
  36. 3D Coordinates
  37. ──────────────
  38.  
  39.     Just so we all understand each other, 3D is defined in of course three
  40. directions, we'll call them (X,Y,Z).  X will be the horizontal plane of your
  41. screen, Z will stretch vertically, and Y will extend out of and into your
  42. screen.  Got it?  Hope so, becuase it gets a bit tricky now.  The next 
  43. system is called Sphereical Coordinates it is defined by angles and distance 
  44. in (Θ,φ,p) These Greek letters are Theta (Θ), Phi (φ), and Roe (p)
  45.  
  46.         Z                                  Z
  47.         |                                  |         Θ - Angle in the XY 
  48.         |                                  |\            plane
  49.         |                                  |\\
  50.         |                                  | \\      φ - Angle from the Z
  51.         |______ X                          |φ_|\___X     axis
  52.        /                                  / \ v \
  53.       /                                  / Θ \   o   p - Distance to point
  54.      /                                  /\    \  |       from the origin
  55.     /                                  /  -->  \ |       (0,0,0)
  56.    Y                                  Y         \|
  57.  
  58.  
  59.     To relate the two systems you can use these equations.
  60.  
  61.     X = p(sinφ)(cosΘ)                 Θ = arctan (X/Y)
  62.     Y = p(sinφ)(sinΘ)                 φ = arccos (Z/p)
  63.     Z = p(cosφ)                       p = √(X^2 + Y^2 + Z^2)
  64.  
  65.     If these don't seem right, do a couple of example problems for yourself,
  66. it should make since after a bit of trig.
  67.  
  68.  
  69. Matrix Notation
  70. ───────────────
  71.  
  72.     Lets say I can define Xt and Yt with the equations:
  73.  
  74. Xt = aX + bY        Where a,b,c,d are coeffiencets
  75. Yt = cX + dY
  76.  
  77.     The matrix notation for this system of equations would be:
  78.                ┌   ┐
  79. (Xt,Yt) = (X,Y)│a c│
  80.                │   │        And we solve for this with these steps
  81.                │b d│
  82.                └   ┘
  83.            
  84.            ┌   ┐ 
  85.  Xt = (X,Y)│a .│  = aX + bY
  86.            │   │            We move across the coordinates left to right
  87.            │b .│            and multiply them by the coeffients in the
  88.            └   ┘            matrix, top to bottom
  89.            ┌   ┐ 
  90.  Yt = (X,Y)│. c│  = cX + dY
  91.            │   │            For Y, the second number, we use the second
  92.            │. d│            column of the matrix
  93.            └   ┘            
  94.  
  95.  We can also multiply matricies in this fashion    
  96.                         ┌   ┐           ┌   ┐
  97.  T = T1*T2  Where  T1 = │a c│ and  T2 = │e g│
  98.                         │   │           │   │
  99.                         │b d│           │f h│
  100.                         └   ┘           └   ┘
  101.  
  102. ┌   ┐┌   ┐   ┌                     ┐
  103. │a c││e g│   │(ae + cf)   (ag + ch)│    rows ->   columns |
  104. │   ││   │ = │                     │                      v
  105. │b d││f h│   │(be + df)   (bg + dh)│
  106. └   ┘└   ┘   └                     ┘
  107.  
  108.     This product is dependent on position, so that means that 
  109.     T1*T2 *DOES NOT* equal T2*T1
  110.  
  111.     In English, the process above went like this, we move left to right in 
  112. the first matrix, T1, and top to bottom in the second, T2.  AE + CF is our 
  113. first position.  
  114.  
  115.     The numbers in the first row are multiplied by the numbers in the
  116. first column.  1st * 1st + 2nd * 2nd is our first value for the new matrix.
  117. Then you repeat the process for the next column of the second matrix.  
  118.  
  119.     After that, you move down to the next row of the first matrix, and 
  120. multiply it by the 1st column of the second matrix.  You then do the same 
  121. for the next column of the second matrix.  This process is repeated until 
  122. you've done all of the rows and columns.  
  123.  
  124. If this is your introduction to matricies, don't feel bad if you're a bit 
  125. confused.  They are a different mode of thinking about equations.  The 
  126. operations above give the same results as if you were to do the long hand 
  127. algebra to solve them.  It may seem a bit more difficult for these examples, 
  128. but when you get to systems of equations with many variables, this way is 
  129. MUCH faster to compute.  Trust me, especially when you make your program do 
  130. it.
  131.  
  132.  
  133. So, now you have the basic math....
  134.  
  135.  
  136.     One important point for these matricies below.  I will use a homogeneous
  137. coordinate system, (X/r, Y/r, Z/r, r) Now I'll use r=1, so nothing will
  138. really be different in my calculations, but you need to understand the 
  139. purpose.  
  140.  
  141.     This form is very convienent for the translations and rotation
  142. equations we will need to do because it allows for scaling of our points with
  143. respect to a center point.  
  144.     
  145.     Consider a point (2,2,2) in an object centered at (1,1,1).  If we were 
  146. to scale the X direction by 3,(the X length to the center is 3 times what it 
  147. was) the point we want would be (4,2,2).  Our new X = 3*(OldX-CenterX).  
  148. Without the added factor of the homogeneous system, calculations assume all 
  149. objects are centered at the origin, so our point would have turned out to be 
  150. (6,2,2), NOT the one we wanted.  So that's why we are going to do it that way.
  151.  
  152.  
  153.  
  154.                         ROTATIONS AND TRANSFORMATIONS
  155. ─────────────────────────────────────────────────────────────────────────────
  156.  
  157. Translation
  158. ───────────
  159.     We will start with translation from the origin.  Most objects are not
  160. at (0,0,0,1), so we'll call their center (Tx,Ty,Tz,1).  
  161.  
  162. ┌             ┐
  163. │ 1   0   0  0│ = T1
  164. │             │
  165. │ 0   1   0  0│     This physically moves the object, so it is centered
  166. │             │     at the origin for our calcuations, eliminating the
  167. │ 0   0   1  0│     need for a -Tx for each X, the matrix will factor it
  168. │             │     in when we multiply it by the others
  169. │-Tx -Ty -Tz 1│
  170. └             ┘     But, we need sphereical coordinates...
  171.  
  172. ┌                                            ┐
  173. │       1             0            0      0  │
  174. │                                            │  =  T1  
  175. │       0             1            0      0  │
  176. │                                            │
  177. │       0             0            1      0  │
  178. │                                            │
  179. │-p(cosΘ)(sinφ) -p(sinΘ)(sinφ) -p(cosφ)   1  │
  180. └                                            ┘
  181.  
  182.  
  183. XY Clockwise Rotation
  184. ─────────────────────
  185.     This will be our first rotation, about the Z-Axis
  186.  
  187. ┌                   ┐
  188. │ sinΘ  cosΘ  0   0 │
  189. │                   │  =  T2
  190. │-cosΘ  sinΘ  0   0 │
  191. │                   │
  192. │  0     0    1   0 │
  193. │                   │
  194. │  0     0    0   1 │
  195. └                   ┘
  196.  
  197.  
  198. YZ Counter-Clockwise Rotation
  199. ─────────────────────────────
  200.     Now we rotate about the X axis
  201. ┌                   ┐
  202. │  1    0    0    0 │
  203. │                   │  =  T3
  204. │  0 -cosφ -sinφ  0 │
  205. │                   │
  206. │  0  sinφ -cosφ  0 │
  207. │                   │
  208. │  0    0    0    1 │
  209. └                   ┘
  210.  
  211.     Notice that with two rotations that we can get any position in 3D space.
  212.  
  213. Left Hand Correction 
  214. ────────────────────
  215.     This will flip the X coordinates.  Think about when you
  216. look into the mirror, your left hand looks like your right.
  217. These rotations do the same thing, so by flipping the X, it
  218. will make your X move right when you increase it's value.
  219.  
  220. ┌             ┐
  221. │ -1  0  0  0 │
  222. │             │  =  T4
  223. │  0  1  0  0 │
  224. │             │
  225. │  0  0  1  0 │
  226. │             │
  227. │  0  0  0  1 │
  228. └             ┘
  229.  
  230.  
  231. The Final Viewing Matrix
  232. ────────────────────────
  233.     This is the net transformation matrix for our viewing perspective
  234.  
  235. The math for this one is really messy, and I would need to go over even
  236. more matrix stuff to get it reduced, so I will ask you to trust my 
  237. calculations
  238.  
  239. V = T1*T2*T3*T4
  240.  
  241. ┌                                        ┐
  242. │ -sinΘ  -(cosΘ)(cosφ)  -(cosΘ)(sinφ)  0 │
  243. │                                        │  =  V
  244. │  cosΘ  -(sinΘ)(cosφ)  -(sinΘ)(sinφ)  0 │
  245. │                                        │
  246. │   0         sinφ          -cosφ      0 │
  247. │                                        │
  248. │   0          0              p        1 │
  249. └                                        ┘
  250.  
  251.  
  252. Lets say our original (X,Y,Z,1) were just that, and the point after the 
  253. rotation is (Xv,Yv,Zv,1)
  254.  
  255. (Xv,Yv,Zv,1) = (X,Y,Z,1) * V
  256.  
  257.  
  258. Xv = -XsinΘ + YcosΘ
  259.  
  260. Yv = -X(cosΘ)(cosφ) - Y(sinΘ)(cosφ) + Zsinφ
  261.  
  262. Zv = -X(cosΘ)(sinφ) - Y(sinΘ)(sinφ) - Zcosφ + p
  263.  
  264.  
  265. ────────────────────────
  266. ────────────────────────
  267.  
  268.  
  269.     Some people have had trouble concepts of this implimentation, so I have
  270. another way of setting up the equations.  This works off of the straight
  271. X,Y, and Z coordinates too, but uses another angle.
  272.  
  273.  
  274. We will define the following variables
  275.  
  276. Xan = Rotation about the X-Axis  
  277. Yan = Rotation about the Y-Axis  
  278. Zan = Rotation about the Z-Axis
  279.  
  280.  
  281. Rotation about the Y Axis 
  282. ────────────────────────
  283.  
  284. ┌                                   ┐
  285. │  cos(Yan)     0       sin(Yan)    │
  286. │                                   │  
  287. │   0           1           0       │
  288. │                                   │
  289. │ -sin(Yan)     0       cos(Yan)    │
  290. └                                   ┘
  291.  
  292.  
  293. Rotation about the Z Axis 
  294. ────────────────────────
  295.  
  296. ┌                                   ┐
  297. │   1           0           0       │
  298. │                                   │  
  299. │   0        cos(Zan)   -sin(Zan)   │
  300. │                                   │
  301. │   0        sin(Zan)    cos(Zan)   │
  302. └                                   ┘
  303.  
  304.  
  305. Rotation about the X Axis 
  306. ────────────────────────
  307.  
  308. ┌                                   ┐
  309. │  cos(Xan)  -sin(Xan)      0       │
  310. │                                   │
  311. │  sin(Xan)   cos(Xan)      0       │
  312. │                                   │
  313. │   0           0           1       │
  314. └                                   ┘
  315.  
  316.  
  317. For simplification, lets call sin(Yan) = s1, cos(Xan) = c3, 
  318.  sin(Zan) = s2, etc
  319.  
  320. Final Rotation Matrix
  321. ────────────────────────
  322.  
  323. ┌                                                       ┐
  324. │  c1c3 + s1s2s3        -c1s3 + c3s1s2          c2s1    │
  325. │                                                       │
  326. │      c2s3                  c2c3               -s2     │
  327. │                                                       │
  328. │ -c3s1 + c1s2s3         s1s3 + c1c3s2          c1c2    │
  329. └                                                       ┘
  330.  
  331.  
  332. ────────────────────────
  333.  
  334. Xv = x(s1s2s3 + c1c3) + y(c2s3) + z(c1s2s3 - c3s1)
  335.  
  336. Yv = x(c3s1s2 - c1s3) + y(c2c3) + z(c1c3s2 + s1s3)
  337.  
  338. Zv = x(c1s2s3 - c3s1) + y(-s2)  + z(c1c2)
  339.  
  340. ────────────────────────
  341.  
  342.  
  343. Where Xv,Yv, and Zv are the final rotated points and the little x,y,z are
  344. the original points.
  345.  
  346.  
  347.  
  348.  
  349.  
  350.         Normal Vectors - The Secret To Shading and Plane Elimination
  351. ─────────────────────────────────────────────────────────────────────────────
  352.  
  353.  
  354.     So, now you have the rotation equations...  But, how do we make it fast?
  355. Well, one of the best optimizations you can impliment is plane elimination.
  356. It boils down to not displaying the planes that won't be seen.  With that
  357. said, here comes more math....
  358.  
  359.                         BE A MAN, KNOW YOUR NORMALS
  360.  
  361.     A 'normal' vector is perpendicular to a plane.  Imagine the face of a
  362. clock as a plane.  Take your right hand and point your thumb toward yourself
  363. and the other end toward the clock.  Now curl your fingers in the 
  364. counter-clockwise direction.  Your thumb is pointing in the direction of the
  365. normal vector.  This is called 'The Right Hand Rule' and it is the basis for
  366. figuring the facing of planes.
  367.  
  368.     A plane can be determined with three points, try it.  That's the minimum
  369. you need, so that's what we will base our process on.  Now if we have a line
  370. segment, we could move it to the origin, maintaining it's direction and 
  371. lenght by subtracting the (X,Y,Z) of one of the points from both ends.  This
  372. is our definition of a vector.  A line segment, starting at the origin and
  373. extending in the direction (X,Y,Z).  
  374.  
  375.     Here will be our plane, built from the three points below.
  376.  
  377. (X1,Y1,Z1)      V = (X1-X2, Y1-Y2, Z1-Z2)
  378. (X2,Y2,Z2)      W = (X1-X3, Y1-Y3, Z1-Z3)
  379. (X3,Y3,Z3)
  380.  
  381.     So, we have our three points that define a plane.  From these points we
  382. create two vectors V and W.  Now if you where to use the right hand rule with
  383. these vectors, pointing your fingers in the direction of V and curling them
  384. toward the direction of W, you would have the direction of the Normal vector.
  385. This vector is perpendicular to both vectors, and since we have defined the
  386. plane by these vectors, the normal is perpendicular to the plane as well.
  387.  
  388. The process of finding the normal vector is called the 'Cross Product' and
  389. it is of this form:
  390.  
  391.      ┌                     ┐
  392. V*W =│   i      k      j   │ 
  393.      │                     │
  394.      │ X1-X2  Y1-Y2  Z1-Z2 │
  395.      │                     │
  396.      │ X1-X3  Y1-Y3  Z1-Z3 │
  397.      └                     ┘
  398.  
  399.  i = (Y1-Y2)(Z1-Z3) - (Z1-Z2)(Y1-Y3)
  400.  
  401. -k = (Z1-Z2)(X1-X3) - (X1-X2)(Z1-Z3) 
  402.  
  403.  j = (X1-X2)(Y1-Y3) - (Y1-Y2)(X1-X3)
  404.  
  405. The Normal to the plane is (i,-k,j)
  406.  
  407.  
  408. NOTE: V*W *DOESN'T* equal W*V, it will be pointing in the negative direction
  409.         To prove that to yourself, lets go back to how I explained it before
  410.         We pointed in the direction of V and curled our fingers toward W, the
  411.         normal vector in the direction of your thumb.  Try it in the 
  412.         direction of W, toward V.  It should be in the opposite direction.
  413.         Your normal, still perpendicular to both vectors, but it is negative.
  414.         If you use in your program, you will have the planes appearing when
  415.         they shouldn't and dissapearing when they are coming into view.
  416.  
  417.     So, now that we have a way to determin the direction of the plane,
  418. how do we hide the plane?  If the angle between the view point and the
  419. normal is greater than 90 degrees, don't show it.  One quick way that I
  420. always use is to place the view point on an axis.  I tipically set the 
  421. Z axis to come out of the screen, Y up and X across.  Set the view point
  422. to be at a positive point on the Z and then, if that normal vector has Z
  423. greater than zero, I display it, otherwise I skip to the next one.
  424.  
  425.     This also has an application in shading.  If you define a light scource,
  426. just like the view point, you find the angle the normal and the light form.
  427. Since you don't usually just want two colors, our 90 degree trick won't work
  428. for you, but by finding this angle, and dividing all of the possible angles
  429. by the number of colors you will allow in the shading, that color can be
  430. assigned to the plane and, presto-chango, it looks like you know what your 
  431. doing...
  432.  
  433.     As you do your rotations, just rotate the coordinates of the normal and
  434. that will keep everything updated.
  435.  
  436.  
  437. Tips To Speed-Up Your Routines
  438. ──────────────────────────────
  439.  
  440. Pre-Calculate as many values as possible
  441.     The main limitation you will have is the speed of your math, using
  442.     precalculated values like Normals, Sin/Cos charts, and distance from the
  443.     origin are all good candidates.
  444.  
  445. If you can get away with using a math-coprocessor, well...
  446.     This will greatly increase the speed of your routine.  Unfortunately,
  447.     not everyone has one.
  448.  
  449. Only figure values once
  450.     If you multiply (SinΘ)(CosΘ) and will use that same value later, by all 
  451.     means, keep it and use it then instead of doing the multiplication again.
  452.  
  453. Another thing to keep in mind
  454.     The order of rotations *DOES* make a difference.  Try it out and you'll
  455.     understand.  Also, when you start to use these routines, you'll find
  456.     yourself making arrays of points and plane structures.  
  457.  
  458.  
  459. Counter-Clockwise points
  460.     Be sure to list your points for the planes in counter-clockwise order.  
  461.     If you don't, not all of your planes will display correctly when you 
  462.     start hiding planes.
  463.  
  464. And as always, be clever
  465.     Just watch out, because when you have clever ideas you can lose a foot.
  466.     My brother once had a clever idea to cut his toe nails with an axe and
  467.     he lost his foot.
  468.  
  469. ─────────────────────────────────────────────────────────────────────────────
  470.  
  471. Books to look for...
  472. ────────────────────
  473.     Any math book, the topics I covered will be found in:
  474.  
  475.     Normal Vectors      - Analytic Geometry
  476.     Matrix Operations   - Linear Algebra
  477.     Sines and Cosines   - Trigonometry
  478.  
  479.     The Art of Graphics, by Jim McGregor and Alan Watt
  480.         1986 Addison-Wesley Publishers
  481.  
  482.  
  483.  
  484. Read the VLA.NFO file to find out how to contact us.
  485.