16/PCGPE10/FDTM.TXT

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