home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 15 / CD_ASCQ_15_070894.iso / news / 2513 / fdtm.txt < prev    next >
Text File  |  1994-04-24  |  6KB  |  179 lines
  1.  
  2.                    ┌────────────────────────────────┐
  3.                    │ Free Direction Texture Mapping │
  4.                    └────────────────────────────────┘
  5.  
  6. The following article was posted by Hannu Helminen (dm@stekt.oulu.fi) to
  7. comp.graphics.algorithms (article 4061). It has been included in the PC-GPE
  8. with his permission.
  9.  
  10. ─────────────────────────────────────────────────────────────────────────────
  11.  
  12. From X Sat Apr  2 10:24:14 EST 1994
  13. Article: 4061 of comp.graphics.algorithms
  14. Newsgroups: comp.graphics.algorithms
  15. Path: csc.canberra.edu.au!newshost.anu.edu.au!harbinger.cc.monash.edu.au!msuinfo!agate!howland.reston.ans.net!EU.net!news.funet.fi!ousrvr.oulu.fi!news.oulu.fi!dm
  16. From: dm@stekt13.oulu.fi (Hannu Helminen)
  17. Subject: Re: extended DOOM: free-direction texture mapping
  18. In-Reply-To: dm@stekt13.oulu.fi's message of Fri, 25 Mar 1994 10:37:02 GMT
  19. Message-ID: <DM.94Mar28152625@stekt13.oulu.fi>
  20. Lines: 160
  21. Sender: news@ousrvr.oulu.fi
  22. Organization: University of Oulu, Department of Electrical Engineering, Finland
  23. References: <DM.94Mar25123702@stekt13.oulu.fi>
  24. Date: Mon, 28 Mar 1994 12:26:24 GMT
  25.  
  26. The idea of free-direction texture-mapping seems to be new to many
  27. few people, so I decided to post this short introduction.
  28.  
  29. Warning: The level of this discussion is quite introductory, if you know
  30. (or guess) what I'm going to talk about, you probably know as much as I
  31. do.
  32.  
  33.  
  34. First look at the principles. In Doom (and in Wolfenstain) the method
  35. used to draw the walls is quite simple. You divide the wall into
  36. vertical lines. Then you calculate where the wall should start and where
  37. to end on the screen (A and B in my nice ascii-picture), and where in
  38. the texture space the corresponding line should start and end.
  39.  
  40. Wall:      Texture:
  41.  \            Y
  42.   \B       \/\^\/\/\
  43.   ^\       /\/./\/\/
  44.   . \      \/\.\/\/\
  45.   . /      /\/./\/\/
  46.   ./          X
  47.   /A
  48.  /      
  49.  
  50. Then you simply do a highly optimized loop in which you do all the
  51. pixels in the vertical line, pick a color from the texture, put it onto
  52. the screen, and move to next position in the texture.
  53.  
  54.  
  55. The floor is a bit more complicated. (I understand that Wolfenstain had
  56. no floor texturing, am I correct?) This time, the floor segment is
  57. mapped to a horizontal line, which is simple enough. However, in texture
  58. space that same line may be in any direction, so you'll have a 2D line
  59. in the texture, like this:
  60.  
  61. Floor:     Texture:
  62.     /\                Y
  63.  A/...>\B       \/\/\.\/\
  64. /        \      /\/\.\/\/
  65.                 \/./\/\/\
  66.                 /./\/\/\/
  67.                 X
  68.  
  69.  
  70. This is old and dull. Now for the new and exciting part: suppose we wish
  71. to draw a polygon in 3-space that has free orientation. A bit of thought
  72. and a simple extension of the above ideas tell us that we should use a
  73. free-direction line in the display coordinates as well.
  74.  
  75. When we map a plane with free orientation to the screen, there is
  76. always one direction on the screen, in which the z-coordinate
  77. (distance) stays the same. In doom's walls it is vertical, in doom's
  78. floors it is horisontal.  But there is one such direction for every
  79. plane.
  80.  
  81. Why is constant z-coordinate important? These lines have the special
  82. property that constant movement along them corresponds to constant
  83. movement in texture space.
  84.  
  85. Read the above two paragraphs again until you have understood them,
  86. since they are the key thing. The rest is only implementation,
  87. following is a short explanation on how I did it.
  88.  
  89. For each polygon you are about to draw on the screen, do the following.
  90. Find the plane equation. From that, derive the "constant-z" direction.
  91. (Come on, take a piece of paper and a pen, it is quite easy.)
  92.  
  93. It helps to make the distinction between two cases here.  Either the
  94. "constant-z" direction is more horisontal, or it is more vertical.
  95. Suppose that it is more horisontal. The constant-z line equation is now
  96. something like y = p*x, where -1 <= p <= 1.
  97.  
  98.  ----
  99.      ---   Example of a constant-z line
  100.         ----
  101.             ----
  102.  
  103. Now, a change in the coordinate system is in order. x is the same x as
  104. before, but y is "slanted" by the factor of p. This means that the
  105. x-axis will be "slanted" but y-axis will be the same as before.
  106.  
  107. The next thing is to convert the polygon to this coordinate system.
  108. Scan convert it line by line, but along these "slanted" (constant-z)
  109. lines.
  110.  
  111. Suppose that we are about to draw a triangle shown below, and the
  112. slanted line is the one shown above. So the path to follow on the
  113. is as follows (ascii art is back again). The path in the texture is
  114. also determined.
  115.         
  116. On the screen:     In texture (eg.):
  117.  
  118.  \-------            Y
  119.  A...    -----/      /./\/\/\/
  120.    \ ...     /       \/./\/\/\
  121.     \   ..../        /\/./\/\/
  122.      \     /B        \/\/./\/\
  123.       \   /               X
  124.        \ /
  125.         X
  126.  
  127.  
  128. So when you render the triangle, the result would be like this. The
  129. numbers are lines of constant Z-value.
  130.  
  131.  22221110   
  132.   3332221111000
  133.    44333222211
  134.     544433332  
  135.      5554444   
  136.       66555    
  137.        766     
  138.         7      
  139.  
  140. Note: you should stack the constant-z lines just as shown in the picture.
  141.  
  142. Implementation notes: this will be a bit slower than DOOM floors, since
  143. the algorithm is a bit more complicated. Another thing is that it will
  144. not be quite as cache-coherent.
  145.  
  146. If you are rendering big polygons (and have a large cache), it helps
  147. to precalculate the pixels lying on the line, so you need not worry about
  148. your Bresenham having to choose right pixels. All you need to do is offset
  149. the line to right memory offset.
  150.  
  151. The inner loop of this machine could look something like this:
  152.  
  153. zbufpointer = zbufbase + offset;
  154. pixelpointer = pixelbase + offset;
  155.  
  156. while (--count >= 0) {
  157.   off = *precalculatedline++;
  158.   if (z > zbufpoiner[off]) {
  159.     zbufpointer[off] = z;
  160.     pixelpointer[off] = texture(x,y);
  161.   }
  162.   x += dx;
  163.   y += dy;
  164. }
  165.  
  166. There is an error of about 0.5 pixel-lengths, since the pixels lying on
  167. the constant-z lines are rounded to nearest pixels.
  168.  
  169. Another error can also be seen in the above picture, the line marked
  170. with 0's has a small "gap" in it, what should we do with it?
  171.  
  172. Happy programming!
  173.  
  174. --dm
  175. --
  176.  
  177.   Hannu    dm@stekt.oulu.fi  || You have been hacking too long when you
  178.  Helminen dm@phoenix.oulu.fi || talk of people as users (or end-users)
  179.