home *** CD-ROM | disk | FTP | other *** search
/ Esprit de Apple Corps / EDAC-2.iso / Graphics / Apps / Demos / Polygonia / ABOUT.POLYGONIA.txt next >
Encoding:
Text File  |  1989-11-11  |  11.2 KB  |  204 lines
  1.                __                                            __ __
  2.              )/  )     )                                       |
  3.              (__/  __  (         _     __    __  `   _         |
  4.              )    /  ) ) )   )  / \)  /  ) )/  ) )  / \)       |
  5.              (   (__/  ( (__/( (__/( (__/  (   ( ( (__/(_    __|__
  6.                           ___)  ___)
  7.  
  8.                          Copyright 1989 Jason Harper
  9.  
  10. Permission is granted to freely redistribute this work as long as the program
  11. and this documentation file remain together and intact.
  12.  
  13. POLYGONIA I,
  14. first in a series of programs designed to explore the use of the Apple IIgs's
  15. unique fill mode graphics for real-time animation of 3D objects.  The current
  16. version of the graphics algorithms only handle objects that fit entirely on
  17. the screen and do not decrease in apparent size with distance: future editions
  18. of Polygonia will handle true perspective views and boundary clipping, and
  19. (hopefully) will run faster.
  20.  
  21. SYSTEM REQUIREMENTS:
  22. Should run on any IIgs with 512K available memory (built-in plus expansion
  23. card minus RAMdisk).  No particular System version is required.
  24.  
  25. Will NOT produce proper results on a monitor or other video device hooked up
  26. to an Apple Video Overlay Card (VOC).  This is due to what I consider to be a
  27. major design flaw in the VOC.  If you have a VOC installed, and it isn't
  28. practical for you to connect your monitor to the built-in video output rather
  29. than the VOC's output, you may be able to get adequate results by connecting a
  30. normal RCA-to-RCA video cable between the IIgs's composite video output jack
  31. and the VOC's video input jack. This causes the VOC to genlock with the
  32. built-in video, which the animation is synchronized with.
  33.  
  34. USAGE:
  35. Polygonia I is mostly a 'sit back and watch'-type program.  There are only
  36. three keys that have any effect while it is running:
  37.  
  38. ESC: exits the program, returning to the program selector you ran it from.
  39.  
  40. TAB: steps to the next of the six included 3D objects.  After the last, TAB
  41. cycles back to the first one again.
  42.  
  43. CapsLock: turns off fill mode graphics, so you only see what the program is
  44. actually drawing (basically, just the left edges of each differently colored
  45. area) rather than apparently solid objects created by fill mode.  It is this
  46. ability to display a contigious row (up to the full width of the screen) of
  47. pixels of the same color by drawing only the leftmost pixel that makes this
  48. sort of animation possible on the IIgs.  Pressing CapsLock again restores fill
  49. mode graphics.
  50.  
  51. Every 10 seconds, the animation's average speed in frames per second is
  52. calculated and displayed in the lower left corner of the screen.  The absolute
  53. maximum speed an animation can run at is 60 FPS, the rate at which the image
  54. on the monitor is refreshed.  It is doubtful that the animation techniques
  55. used in Polygonia can ever reach that goal except for tiny, trivial objects.
  56. It would be quite possible to record the data generated by the animation
  57. routines and play them back later at a full 60 FPS, but there would be no
  58. possibility of any control over the animation other than moving it to
  59. different places on the screen: individual objects couldn't respond to user
  60. input or other external control.
  61.  
  62. THE OBJECTS:
  63. Object          # of vertices   # of polygons   Average # of edges per polygon
  64. ------          -------------   -------------   ------------------------------
  65. Cube            8               6               4
  66.  
  67. Tetrahedra      10              16              3
  68.  
  69. Dodecahedron    20              15              4.67
  70. The graphics algorithms can't really handle the zero-thickness areas created
  71. by the hole in this object, so an occasional incorrect frame is to be expected.
  72.  
  73. XYZ axes        47              42              4.14
  74.  
  75. Spaceship       132             94              4.77
  76.  
  77. Towers of Hanoi:
  78.   Base only     23              17              3.29
  79.   Each disk     16              12              4
  80.   Total         103             77              3.84
  81. For those of you who are unfamilar with the Towers of Hanoi puzzle, the rules
  82. are as follows: there is a base with three pegs, and an arbitrary number of
  83. disks of different sizes.  All the disks start on one peg, in decreasing order
  84. of size.  The object of the puzzle is to move all of the disks onto another
  85. peg in the same order.  Only one disk can be moved at a time, and no disk may
  86. ever be placed on top of a smaller disk.
  87.  
  88. HOW IT WORKS:
  89. Each object to be drawn is represented by a list of points specified by X, Y,
  90. and Z coordinates, plus a list of polygons specified by the points that form
  91. their boundary and a color.  Each polygon is constructed so that its border
  92. points are in clockwise order when viewed from the outside of the object: if
  93. the points end up in counterclockwise order, then the polygon is facing away
  94. from the viewer and can be quickly skipped.  Colors are independantly
  95. specified for even and odd rows of pixels, so it is possible to form
  96. additional dithered colors that are distinguishable from the 15 pure colors
  97. (the 16th color has no color of its own in fill mode, it gets the color of the
  98. pixel to its left and is used to fill horizontal rows of pixels with minimal
  99. effort).  For each frame to be displayed, the following steps are taken:
  100.  
  101. 1. A transformation matrix is generated from the individual rotation, scaling,
  102. and translation transformations needed to put the object on the screen in the
  103. desired position and orientation.
  104. 2. Each of the points in the object's point list is multiplied by the
  105. transformation matrix.  Building a single transformation matrix and applying
  106. it to all the points is far more efficient in general than applying each
  107. individual rotation, scaling, etc. separately to each point.
  108. 3. For each polygon in the object's list:
  109.     A. The polygon's area is computed from the coordinates of its points.  If
  110.        the result is negative, the polygon is facing away from the viewer, and
  111.        all further processing of it can be skipped.
  112.     B. For each edge (pair of adjacent points) of the polygon, an entry in the
  113.        Edge Table (ET) is created giving the information needed to draw the
  114.        line, including starting horizontal position, slope, and ending vertical
  115.        position.  The ET is divided into 200 separate lists, one for each
  116.        possible starting vertical position, so that information doesn't have
  117.        to be stored with each edge.
  118. 4. For each of the 200 rows of pixels on the screen:
  119.     A. All entries in the ET list corresponding to this scanline are moved
  120.        into the Active Edge Table (AET), being placed in ascending order of
  121.        their current horizontal position.
  122.     B. Each edge in the AET is examined to see if the display changes at that
  123.        horizontal position (there is no possibility of any change at points
  124.        other than on a polygon edge).  Most of the time, this can be done by
  125.        simply comparing the depth of the edge that the display is currently
  126.        'in' with the edge being processed: the new edge is either further
  127.        away and thus ignored, or closer and therefore becomes the current 'in'
  128.        edge.  Occasionally the whole list of polygons that currently have
  129.        edges in the AET has to be searched to find the closest one.  When a
  130.        change to a newly-colored edge is detected, it is NOT immediately drawn
  131.        to the screen: the edge processing generally takes longer than 1/60th
  132.        second, so there would be considerable flicker as the new frame slowly
  133.        replaces the old.  Instead, the new color and the screen position at
  134.        which it starts are saved in a list for later use.
  135.     C. After all the AET entries are processed, they are updated to be correct
  136.        for the next scanline.  Each edge's slope is added to its current
  137.        horizontal position: positive for lines that slant to the right, and
  138.        negative for those that slant to the left.  Any edge which reaches its
  139.        ending vertical position is deleted from the AET.  The AET is re-sorted
  140.        to maintain the ascending order of horizontal positions.
  141. 5. Now that all the color changes in the frame have been generated, they are
  142. drawn to the screen all at once (to eliminate flicker).  The program waits
  143. until the video scan just reaches the bottom of the screen, then uses the
  144. previous frame's change list to erase all of its color changes, then uses the
  145. change list just generated to draw all of the new color changes.  This can
  146. hopefully always be done before the video scan reaches the top of the screen
  147. on its next pass.  For fastest possible processing, the generated change lists
  148. are actually machine language code that carries out the changes, rather than
  149. just data for the program to interpret.  It was rather challenging to come up
  150. with a way to generate the change list code so that it can be used both for
  151. drawing the changes when the list is for the current frame, then later for
  152. erasing the changes when the next frame is drawn.  The change lists run in
  153. 8-bit native mode (there are seldom changes in adjacent bytes, so 16-bit mode
  154. would be inefficient) with the data bank register pointing to bank $E1 where
  155. the graphics screen resides, and contain code like this for each byte changed:
  156.         LDA dp
  157.         STA absolute
  158. The 'dp' address in the load instruction is the new value for the byte: to
  159. draw the changes the list is executed with the direct page set up so that each
  160. byte contains a value equal to its address, and to erase the changes a direct
  161. page containing all zeros is used.  The 'absolute' operand in the store
  162. instruction is the offset into bank $E1 where the byte is to go.
  163.  
  164. FOR FURTHER READING:
  165.     Fundamentals of Interactive Computer Graphics
  166.     James D. Foley & Andries Van Dam
  167.     Addison-Wesley Systems Programming Series
  168.     ISBN 0-201-14468-9
  169. Covers many aspects of 2D and 3D computer graphics, including the scanline
  170. algorithm used in Polygonia.
  171.  
  172.     Computer Graphics: A Programming Approach
  173.     Steven Harrington
  174.     McGraw-Hill
  175.     ISBN 0-07-026753-7
  176. This book covers fewer topics than the previous one, but tends to give more
  177. concrete examples of using them: fewer things are "left as an exercise for the
  178. reader".  The scanline algorithm is only mentioned in passing, but other
  179. details of Polygonia such as 3D coordinate transformations are covered.
  180.  
  181. FOR FURTHER VIEWING:
  182. As far as I know, there have only been two programs prior to Polygonia I that
  183. use the IIgs's fill mode graphics.  Both are freely distributable, and
  184. probably available wherever you found Polygonia.  They are available on
  185. CompuServe, currently in Library 11 of the APPRODUCTIVITY Forum: finding them
  186. on other systems is up to you.
  187.  
  188. Cubination (author unknown): the first known fill mode program, displays a
  189. rotating icosahedron (20-sided polyhedron) that moves diagonally around the
  190. screen, bouncing off the edges.  Faster than Polygonia I, but less flexible as
  191. it is playing back a recorded series of frames rather than creating them as
  192. needed: the object can only rotate around a single axis, and can only appear
  193. at the same size it was recorded at.  Filename is CUBINA.BNY on CompuServe.
  194.  
  195. FillMaze (also by Jason Harper): a 3D maze walkthru.  Very fast (about 55
  196. FPS), because the lines forming the left edges of each solid-colored area were
  197. laid out in advance to fall on byte boundaries, with easy-to-calculate integer
  198. slopes.
  199.  
  200. THE END:
  201.         Jason Harper
  202.         CompuServe: 76703,4222
  203.         Internet: 76703.4222@compuserve.com
  204.