home *** CD-ROM | disk | FTP | other *** search
/ Collection of Hack-Phreak Scene Programs / cleanhpvac.zip / cleanhpvac / FAQSYS18.ZIP / FAQS.DAT / SPEEDY.TXT < prev    next >
Text File  |  1996-08-18  |  26KB  |  624 lines

  1.      Hello, my friend! You are viewer nr 3098 since December 1995 of:
  2.  
  3.                    SPEEDY FREE DIRECTION TEXTURE MAPPING
  4.                            AND OTHER NIFTY TRICKS
  5.  
  6.               Some Wild-Ass Speculations and Untested Theories
  7.                             (that will work :-)
  8.  
  9.                      by Hσkan 'Zap' Andersson, 95-02-02
  10.  
  11.                   Throw me a mail at: zap@lysator.liu.se
  12.  
  13. -1. Greed/Copyright
  14.  
  15. If you use any of this stuff in your commercial game, I at least think I
  16. deserve to:
  17.  
  18.   1. Be mentioned and thanked thoroughly in the game. Thank Hakan 'Zap'
  19.      Andersson, zap@lysator.liu.se
  20.   2. Receive a copy of the game!!
  21.   3. Receive obscene amounts of cash :-)
  22.  
  23. If you fail to comply to the above, it may turn out that I had already
  24. patented all algorithms herein, and I would then throw a "Unisys" at you! A
  25. joke, I hope you get that?
  26.  
  27. The information herein is Copyright -95 Hσkan 'Zap' Andersson
  28.  
  29.   If you want to add this page to your WWW page, feel free to link to this
  30.   page (http://www.lysator.liu.se/~zap/speedy.html) but don't make a local
  31.    copy of it onto your WWW site without telling me (I might update this
  32.                 later, and your copy wouldn't get updated!)
  33.  
  34. PART I
  35.  
  36. "Texturing in a skewed universe"
  37.  
  38. 0. Introduction
  39.  
  40. So, you played Wolfenstein 3D. So you played DOOM. And you played Descent.
  41. Texturemapping in Real Time has proven to be a reality, even on a tiny old
  42. PC.
  43.  
  44. This document will take you on a Guided Tour through one of my more recent
  45. speculations on the subject. There is no doubt that what I outline here
  46. will WORK. I call it speculations only because I havn't actually imple-
  47. mented or tested it! Sadly, I have a life, and that life prevents me from
  48. luxurios amounts of time at the console hacking for FUN. [It instead forces
  49. me to luxurious amounts at the same console, hacking for my bread].
  50.  
  51. So none would be happier than I if somebody had the time to IMPLEMENT any
  52. of this, and please give me the sourcecode when he is done!!!
  53.  
  54. 1. History
  55.  
  56. When I first played Wolfenstein 3D, I was chocked by the "real time
  57. textures" that it could produce on my old 386/20. I thought that stuff was
  58. only poss- ible on SGI Onyx machines and above. I was baffled.
  59.  
  60. But after some months, the "secret" of the method was analyzed to death by
  61. the net. So, it was just vertical slices of wall being scaled vertically!
  62.  
  63. But still - Wolfenstein proves to be the very basis of the idea that will
  64. be talked about in this document. Everybody and his sister trying to do a
  65. similar thing, would have initially tried to scan-convert the polygons
  66. HORIZONTALLY. Mostly because all textbooks on the subject talk about
  67. horizontal scanlines as if they were the only things that exists. [Reading
  68. too many books limits your thinking!] Wolfensteins strike of genious was to
  69. work VERTICALLY.
  70.  
  71. But everybody "knew" that this only worked for walls. We all "knew" that
  72. there would NEVER be a game capable of drawing textured floors and
  73. ceilings. And boy were we wrong.
  74.  
  75. Out came DOOM. As usual, I thought this was something only a SGI Onyx could
  76. do. Now the FLOOR had textures! How the hell was THIS possible!?
  77.  
  78. As usual, the trusty ol' internet (not the RUSTY old internet :-) provided
  79. the answer. Naturally, they DID work horizontally on the floor, since
  80. horizontally meant along the same Z, which meant linearilly in texture
  81. space.
  82.  
  83. "Of course" we thought. "Ok" we thought. "Now we know. Walls work. Floors
  84. too. But it is still impossible to work on any orientation of textures.
  85. That, at least, is something that only an SGI Onyx can do".
  86.  
  87. Then came Descent.
  88.  
  89. Of course, I knew this was not possible, and that this was not happening in
  90. MY tiny computer. (A mere 486/66!). I creapt around the case of my computer
  91. to see if there wasn't an SGI machine hidden in there after all!
  92.  
  93. This time, I didn't wait for the 'net to think for me. This time, I did the
  94. thinking all on my own. This is the result of that thinking.
  95.  
  96. 2. What Wolfenstein and DOOM taught us
  97.  
  98. The basic principle taught by DOOM (and by Wolfenstein) is this:
  99.  
  100. TRUTH I:
  101.      As long as you are drawing your polygon ALONG LINES WITH EQUAL Z (The
  102.      Y axis for walls and the X axis for floors/ceilings) THE TEXTURE IS
  103.      TRAVERSED LINEARILY.
  104.  
  105. Of course, this was all fine and dandy for FLOORS and WALLS. But what the
  106. hell did that help us on that sloping plane we wanted to texture!?
  107.  
  108. The answer is, IT HELPED A LOT. We only have to bang our heads on the
  109. walls, and FORGET ALL THAT NONSENSE ABOUT WALKING ALONG HORIZONTAL OR
  110. VERTICAL SCANLINES!!
  111.  
  112. TRUTH II:
  113.      ALL polygons drawn on screen has along SOME DIRECTION equal Z
  114.      coordinates along that line.
  115.  
  116. This means, that if we can scanconvert our polygons not horizontally, not
  117. vertically, but ALONG THIS LINE, we can TRAVERSE THE TEXTURE LINEARILLY. I
  118. needn't go in to HOW MUCH THIS WILL SPEED UP EVERYTHING compared to one
  119. division per pixel (a common need in texturing algorithms) or bicubic
  120. approximations.
  121.  
  122. 3. How the hell (whimsical DOOM reference intended) do we do it!?
  123.  
  124. Step one: Find the elusive screen-direction which represents equal-Z. This
  125. turns out to be so trivial it hardly even needs to be mentioned:
  126.  
  127. Take the normal vector, converted to screen-coordinates (as a 2D vector).
  128. Your 'constant Z line' will be that vector rotated 90 degrees.
  129. [Alternatively, the cross product between the normal and the viewing
  130. direction will give you the same line in 3D]. The special case being that
  131. the normal points directly at the screen (having (0, 0) size in screen
  132. space). This simply means that you can pick ANY line - since the whole
  133. POLYGON is on the same Z!
  134.  
  135. Now all you have to do, is to scan-convert your polygon in THIS DIRECTION
  136. ON SCREEN. Calculate what texture-coordinate-span that line has, and
  137. linearily walk the texture as you draw that line in the polygon.
  138.  
  139. That is "it", really.
  140.  
  141. 4. How can we make this EFFICIENTLY (and without holes?)
  142.  
  143. Firstly, as with ALL line-drawing algorithms, we need different 'versions'
  144. of it depending on if the lines slope is in the range +-45 degrees, or if
  145. it is closer to the Y direction. I will here only discuss the 'almost
  146. horizontal case', where the line has a direction so that for each pixel
  147. step along X, Y may OR may NOT increase/decrease one.
  148.  
  149. The algorithm only needs to be "rotated" to work with Y instead of X, and I
  150. leave this as an exercise to the reader. Heh. :-)
  151.  
  152. So, assuming that the polygon we want to draw turns out to fulfill this
  153. need, we can do the following:
  154.  
  155. I am assuming we want to draw this polygon into a palette-device that is
  156. represented in memory as an array of bytes, row by row. This discussion
  157. does NOT assume any particular hardware. You may use MODE13 on a PC, or a
  158. WinGBitmap under Windows (NT), or you may use an X bitmap under X. Lets
  159. have the following C variables:
  160.  
  161.      unsigned char *screen; /* Pointer to screen memory */
  162.      short x_size;          /* Screen X size */
  163.      short y_size;          /* Screen Y size */
  164.  
  165.      /* A macro to reference any given pixel (read OR write) */
  166.      #define PIXEL(x, y) screen[y * x_size + x]
  167.  
  168. Since we are in this example walking along X, we find the 'maximum
  169. horizontal size' of the polygon: It's minimum X and it's maximum X
  170. coordinates.
  171.  
  172. Now we get clever. We get ourselves an array of integers containing
  173. 'x_size' elements. [If we are on a PC, or are confined to 320x200, or any
  174. other resolution with less than 64k pixels, a short is sufficient.
  175. Otherwize, we need a long]
  176.  
  177. This array will store our sloping line. To save time filling in the array,
  178. we only walk it starting in the MINIMUM X of the polygon and walk towards
  179. MAXIMUM X of the polygon.
  180.  
  181. Into the array we fill in the BYTE OFFSET for that pixel.
  182.  
  183. Meaning, for the purely horizontal line, the array would contain:
  184.  
  185.    0   1   2   3   4   5   6   7   8   9   ....
  186.  
  187. But for a line that looks like this:
  188.  
  189.                X X X
  190.          X X X
  191.    X X X
  192.  
  193. Would, on a 320 x 200 graphics mode contain the following offsets:
  194.  
  195.   0  1  2  -323 -324 -325 -646 -647 -648
  196.  
  197. The reason we store this in an array is threefold:
  198.  
  199.   1. Speed! The line is the same all across the polygon! Why calculate it
  200.      more than once!?
  201.   2. Avoid HOLES. If you calculated the line 'on the fly' you could end up
  202.      with results such as this:
  203.  
  204.                             2 2 2           1 = Line 1
  205.                       2 2 2 . 1 1 1         2 = Line 2
  206.                 2 2 2 . 1 1 1               . = Holes in the texture
  207.                   1 1 1
  208.  
  209.                With a precalculated line, we are guaranteed to get:
  210.  
  211.                               2 2
  212.                         2 2 2 1 1 1
  213.                   2 2 2 1 1 1
  214.                   1 1 1
  215.  
  216.   3. By not only storeing the Y coordinate, but the BYTE OFFSET, we save
  217.      ourselves a multiplication!
  218.  
  219. 5. How to Scanconvert a polygon along a 'skewed line'
  220.  
  221. But now your real headache starts. How the HELL should I make a polygon
  222. scan- conversion algorithm that works along this 'skewed line'!? Didn't I
  223. have ENOUGH trouble writing a normal "horizontal" polygon scan converter!?
  224. :-)
  225.  
  226. All I say is: Relax, pal. There is hope. There is an easy way:
  227.  
  228. If you have a line that is 'skewed' by a slope of 1:3 (as in the example
  229. above), all you have to do, is this:
  230.  
  231. BEFORE scanconverting your polygon (but AFTER transforming to screen- space
  232. AND clipping), SKEW THE POLYGON VERTICIES by THE SAME AMOUNT but in the
  233. OPPOSITE DIRECTION (in screen space). Then use your NORMAL HORIZONTAL SCAN
  234. CONVERSION ALGORIHM. But when you DRAW the LINES, DONT draw the
  235. HORIZONTALLY! Use the offset vector, and draw them in the skewed direction!
  236.  
  237. If our sloping line looks like this:
  238.  
  239.                  X X X
  240.            X X X
  241.      X X X
  242.  
  243. Then if this is the original polygon verticies:
  244.  
  245.    1 .               . 2
  246.  
  247.    3 .
  248.              . 4
  249.  
  250. After 'skewing' it would look like this:
  251.  
  252.    1 .
  253.  
  254.                      . 2    (moved down 2)
  255.  
  256.    3 .
  257.  
  258.              . 4  (moved down 1)
  259.  
  260. To paraphrase: Never "TELL" your scanconverter that you are working with
  261. skewed scanconversion! "Fool" it by feeding it a skewed polygon, and get
  262. the right result by "skewing back" the output!
  263.  
  264. So, what's the catch? Well, using this method ain't "perfect". You can get
  265. seams and holes BETWEEN your polygons, because the outcome of the edge of
  266. the polygon depends a little (but not much) on the angle of the skewed
  267. line. [Maybe there is a way to treat the edges of the polygon specially? I
  268. have many different ideas on this subject, but I dont know how "bad" the
  269. result will be, since I have yet to implement ANY of this!]
  270.  
  271. Now, keep in mind that each "scan" along this "skewed" line represents one
  272. Z coordinate. This means that for each "scan" you'll need only ONE divide
  273. to find out at which point on the TEXTURE your START COORDINATES are. You
  274. can also obtain the 'step' size and direction to walk the texture bitmap.
  275. Note that the step DIRECTION is the same all over the polygon, but the step
  276. SIZE depends on 1/Z. So the direction only needs to be calculated once per
  277. polygon. The size needs to be calculated once per scan. (HOW your texture
  278. is mapped to the polygon is irrelevant - as long it is linear. The texture
  279. needn't necessarily be mapped flat on the polygon - it may even be a
  280. threedimensional hypertexture!!)
  281.  
  282. This method also lends itself nicely to a Z-buffer! No need to recalculate
  283. Z! It is the same along each "scan"! So only a TEST needs to be done! And
  284. if you use a 16-bit Z-buffer, you can use the 'offset vector' discussed
  285. above multiplied by two (= shifted left once) to get the offset into the
  286. Z-buffer!
  287.  
  288. 6. Conclusion on texturing
  289.  
  290. After realizing this, I feel that Descent isn't impossible after all. I
  291. doubt they use exactly THIS technique, but at least it has proven to be
  292. theoreti- cally possible to render free-direction textures in realtime.
  293.  
  294. PART II:
  295.  
  296. "Let there be light"
  297.  
  298. 0. Some words about lighting
  299.  
  300. OK, so we figured out one way to do quick texturemapping. So we cracked the
  301. secret of Descent? Nope.
  302.  
  303. Instead, one of Descent's MOST impressive effects is now the LIGHTING! It
  304. seems like they have TRUE lightsourcing with light fall-off in the
  305. distance!! And it is not just a "one shade per polygon" thing! It is a true
  306. "one shade per pixel" thing! (Try landing a flare on a polygon in some dark
  307. area! You get a nice pool of light around it!)
  308.  
  309. This is extremely impressing that they can do this AND texturemapping in
  310. realtime, at the SAME time!
  311.  
  312. Sadly, I havn't got a clue. Anyone?
  313.  
  314. Instead, I have got quite a BIG clue about something completely DIFFERENT:
  315.  
  316. 1. DOOM Lighting basics
  317.  
  318. Instead of talking about how Descent does it's ligting, lets step back to
  319. something a lot less complex: DOOM's lighting.
  320.  
  321. DOOM really doesn't have much of lighting. What you CAN do, is specify a
  322. 'brightness' of a certain area of your 'world'.
  323.  
  324. What DOOM *has* is a 'shade remapping table', and this is what I will use
  325. as a base of my idea. Allow me to explain:
  326.  
  327. DOOM uses a 256 color graphics mode - which means that it uses a palette.
  328. (Well, actually several palettes that gets exchanged, e.g. a red-ish
  329. palette for when you are hurt, e.t.c, but let's not get picky)
  330.  
  331. When the lighting is 100% the pixel in the texturemap is the same pixel
  332. value that gets written to screen. But DOOM uses a bunch of (34 i think)
  333. remapping tables for different lighting levels. Such as:
  334.  
  335.    unsigned char LightRemap[34][256];
  336.  
  337. So to find the output pixel, the following algorithm would be used:
  338.  
  339.    output_pixel = LightRemap[light_level][input_pixel];
  340.  
  341. The LightRemap vector would be precalculated (in DOOM's case it is actually
  342. loaded from the WAD file). So when light_level is max, and imput_pixel
  343. references a white pixel, output_pixel will return the same white pixel.
  344. But when the lighting is 50%, output_pixel will instead be a gray color.
  345.  
  346. 2. Random dithering to the people!
  347.  
  348. Now one problem that is seen in ALL 3D games is that you can SEE how their
  349. lighting falls off in 'steps'. If the palette only contains three
  350. darkness-levels of purple, then the LightRemap vector would for light-
  351. levels from 0-25% reference BLACK, for 25%-50% the darkest, and so on. You
  352. would VERY EASILY *see* the borders between the different levels, as the
  353. light diminishes in the distance. That looks UGLY.
  354.  
  355. Now if the game programmers had added FOR EACH PIXEL a RANDOM value to the
  356. light. (Quick random values can be gotten from a table. They dont need to
  357. be superrandom, only chaotic). This would have given us a DITHER of the
  358. screen. And that DITHER would CHANGE for each frame (since it is RANDOM).
  359. This would INCREASE the perceived number of colors greatly! Sure - EACH
  360. FRAME would look like a "snowy mess" of random noise. But when played
  361. quickly, it would look smooth!
  362.  
  363. Compare the perceived color quality of a TV picture from what you get when
  364. pausing a frame on your VCR, and you will understand what I am saying. You
  365. dont see all the noise in the picture, because the average of the noise
  366. over time for each pixel is the intended pixel value. The human eye
  367. 'removes' the noise for you.
  368.  
  369. Dithering would increase the colorresolution of games such as DOOM and
  370. Descent, and the 'noisy picture' would look MORE REAL than the 'clean'
  371. picture of today. (This is true of all moving graphics/animation)
  372.  
  373. 3. Bumpmapping in realtime? Impossible! NOT!
  374.  
  375. Now lets get to the REAL fun!!!
  376.  
  377. One of the Truths I have found in computer graphics is that texture-
  378. mapping can GREATLY reduce the number of polygons you need to make an
  379. object convincing.
  380.  
  381. But sometimes you still need to have extra polygons, just get away from the
  382. "flat" look of the polygons.
  383.  
  384. Another Truth that I found (while implementing my once commercial
  385. raytracer) is that the REAL fun starts with BUMPMAPPING! That is when you
  386. start talking about REAL decreases in the polygon count!
  387.  
  388. Instead of having hundreds of polygons to make a wobbly mountain side, have
  389. ONE polygon, and add the wobblyness of the surface as a bumpmap!
  390.  
  391. The basic idea behind bumpmapping:
  392.  
  393. To do bumpmapping, you need to be doing SOME kind of "real" lighting. But
  394. the lighting does NOT need to be ANY MORE COMPLEX than simple cosine
  395. lighting. We dont even need point lightsources! Directional light is OK.
  396.  
  397. To get the light-level of a polygon, we simply take the dot-product between
  398. the light-direction and the surface normal vector! That's it!
  399.  
  400. If we use directional light, we can assume that light is coming from the
  401. direction Lx, Ly, Lz. (This should be a normalized vector: The 'length'
  402. should be 1.0) and the polygon normal is Nx, Ny, Nz, the light level is:
  403.  
  404.     Light = Lx * Nx + Ly * Ny + Lz * Nz
  405.  
  406. What could be simpler!?
  407.  
  408. Now, Bumpmapping means VARYING the normal vector over the surface, and
  409. recalculating a NEW lightlevel for each pixel. For instance, lets assume a
  410. surface that is flat in the X-Y plane. If we vary the X component of the
  411. surface normal with a sinus function along X, it will look like the surface
  412. was rippled with waves in the X direction!
  413.  
  414. The shading of these ripples would be "correct": If we the light comes from
  415. the LEFT, the LEFT side of the ripples would be bright and the right side
  416. would be dark. if the light came from the RIGHT, the reverse would be true.
  417.  
  418. Now compare games like DOOM, where they "fake" bumpmapping by simply
  419. PAINTING light and dark edges on stuff like doors and similar. This looks
  420. horrible when two doors opposite eachother in a corridor both have their
  421. "bright" edges on their upper and LEFT sides!
  422.  
  423. And trust me, the eye/brain is REALLY good at picking out these
  424. inconsitensies. The eye/brain uses shading as its PRIMARY CUE to the real
  425. nature of the surface! Yes! The PRIMARY cue! The whole human optical
  426. subsystem is oriented towards recognizing shades as being surface
  427. variations! A warning-this-is-not-real flag is IMMEDIATELY raised when the
  428. 'bright edge' of a door doesn't match the intended light direction!
  429.  
  430. This is where even Descent falls apart!
  431.  
  432. 4. How can we get this into games such as DOOM?
  433.  
  434. Well, first of all SOME kind of 'directional light' must exist. But
  435. experience tells me that even a hardcoded directional light, where the
  436. light comes from the SAME direction all over the 'world', can increase the
  437. realism. And we need to be doing AT LEAST cosine shading.
  438.  
  439. Above I said that to do bumpmapping, we must RECALCULATE THE SHADING FOR
  440. EACH PIXEL. Now that doesn't sound very fast, does it? Well, the thing is,
  441. we dont need to do that! But first let me explain:
  442.  
  443. In advanced rendering systems you normally have one bitmap as texture- map,
  444. and another bitmap as the bump-map. The bumpmap usually defines the
  445. simulated 'height' of the surface as the brightness of the bitmap. But
  446. HEIGHT in ITSELF is not interesting! (If the surface is flat - it has the
  447. same height. Only where the height CHANGES the surface isn't flat, and the
  448. normal is affected); HEIGHT is not interesting, CHANGE of height is.
  449.  
  450. So a traditional renderer will have to sample at least FOUR adjacent pixels
  451. in the bump-map bitmap, and calculate the 'slope' in that part of the
  452. bitmap based on their RELATIVE brightness. That 'slope' is then transformed
  453. into a deformation of the normal vector - which in turn (via the shading
  454. algorithm) yields another shade at that point (phew!).
  455.  
  456. HOW THE HELL DO I INTEND TO DO SOMETHING LIKE THAT IN REALTIME!?
  457.  
  458. Now, lets assume that we want to make a 'groove' along the Y axis in the
  459. middle of our polygon. Lets say the polygon is 64x64 units large, is flat
  460. in the XY plane, and the texture mapped to the polygon is also 64x64 in
  461. size.
  462.  
  463. So what we want to do, is at X coordinate 32 we want to make a 'groove', so
  464. the polygon will LOOK as if it's profile was this:
  465.  
  466. The 'intended' surface seen from negative Y axis:
  467.  
  468.   --------------\_/---------------
  469.  
  470.   |             |||              |
  471. X 0            / | \           X 64
  472.            X 31  32 33
  473.  
  474. Since we are using "flat shading", we will only calculate one brightness
  475. level for the whole polygon: The dot-product between the normal vector and
  476. the light direction.
  477.  
  478. Lets say that the result is 80%. So, the overall lighting of the polygon is
  479. 80%! And 80% is the lightlevel we use on all pixels of the polygon EXCEPT
  480. those at X=31 and X=33! Because all pixels at X=31 should look as if they
  481. were going 'into' the surface (the normal vector displaced to the right),
  482. and those at X=33 should look as coming 'out of' the surface (normal vector
  483. displaced to the LEFT).
  484.  
  485. Lets say the lighting level for a normal displaced a little to the left is
  486. 95%, and a normal vector displaced a little to the right is 50%.
  487.  
  488. As you can see, we then have three different shadings for this polygon with
  489. the current lighting conditions:
  490. 80% for most of it, 50% for column 31, and 95% for column 33.
  491.  
  492. As you can see, we do NOT need to recalculate the shading for each pixel.
  493.  
  494. We only need to recalculate the shading level AS MANY TIMES AS WE HAVE
  495. DIFFERENT DISPLACEMENTS OF THE NORMAL VECTOR.
  496.  
  497. 5. How to implement this:
  498.  
  499. We can let the normal texture bitmap that you use for texturing contain
  500. additional data: Any number of 'normal displacement' structures.
  501.  
  502.    struct normal_displacement {
  503.        int palette_index;
  504.        real normal_displace_x, normal_displace_y;
  505.        int color_to_use;
  506.    };
  507.  
  508. Any number of these structures may be attached to a bitmap. Lets say we
  509. have the following bitmap. Our goal is to depict a flat gray surface with a
  510. raised gray square in the middle. (Each number represents the palette index
  511. for that pixel:)
  512.  
  513.   Y
  514.     11111111111111111111111111111
  515.     11111111111111111111111111111
  516.     11111222222222222222222111111
  517.     11111311111111111111114111111
  518.     11111311111111111111114111111
  519.     11111311111111111111114111111
  520.     11111311111111111111114111111
  521.     11111311111111111111114111111
  522.     11111311111111111111114111111
  523.     11111311111111111111114111111
  524.     11111355555555555555554111111
  525.     11111111111111111111111111111
  526.     11111111111111111111111111111
  527. (0,0)                             X
  528.  
  529. Attach to this bitmap we have the following four normal_displacement
  530. structures:
  531.  
  532.     {
  533.        palette_index      = 2;
  534.        normal_displace_x  = 0;
  535.        normal_displace_y  = 0.5;
  536.        color_to_use       = 1;
  537.     }
  538.     {
  539.        palette_index      = 3;
  540.        normal_displace_x  = -0.5;
  541.        normal_displace_y  = 0;
  542.        color_to_use       = 1;
  543.     }
  544.     {
  545.        palette_index      = 4;
  546.        normal_displace_x  = 0.5;
  547.        normal_displace_y  = 0;
  548.        color_to_use       = 1;
  549.     }
  550.     {
  551.        palette_index      = 5;
  552.        normal_displace_x  = 0;
  553.        normal_displace_y  = -0.5;
  554.        color_to_use       = 1;
  555.     }
  556.  
  557. Now what does this mean?
  558.  
  559. Let's say that color index 1 is just medium gray. So all pixels with index
  560. 1 will simply be medium gray.
  561. The structures appended means that color index 2 *IN THE BITMAP* should
  562. represent an edge pointing 'upwards' (we displace the normal vector's Y by
  563. 0.5 (normally this displacement would need to be trans- formed into the
  564. space of the polygon, but for our example, this is sufficient)).
  565. Now since color index 2 maybe normally be GREEN, PURPLE or any other
  566. undesired color, the structure contains the member color_to_use. In our
  567. example, this is 1. This means that this pixel will ALSO be medium gray -
  568. but with a DIFFERENT LIGHTING LEVEL.
  569. Similarily, color index 3 is an edge pointing 'to the left', 4 is an edge
  570. pointing 'to the right', and 5 is an edge 'pointing down'.
  571.  
  572. If we would have wanted another COLOR, but the same DISPLACEMENT, we would
  573. have needed another structure for that, e.g. if the lower half of the
  574. bitmap would have been GREEN, we would have needed a few different
  575. displacement-structures for green pixels as well.
  576.  
  577. How how should we make this efficiently? Well, remember the LightRemap
  578. vector we talked about earlier. This comes into play for us.
  579.  
  580. The overall color level of the polygon is 80%, remember?
  581.  
  582. So, lets make a COPY of the LightRemap vector for light level 80%. Lets put
  583. this into vector LightRemapCopy:
  584.  
  585.     unsigned char LightRemapCopy[256];
  586.     memcpy(LightRemapCopy, LightRemap[light_level]);
  587.  
  588. Now, lets walk through the normal_displacement structures. For each
  589. structure:
  590.  
  591.     struct normal_displacement nrm;
  592.  
  593.     /* Displace the normal */
  594.  
  595.     displace_normal(normal, &new_normal, nrm);
  596.  
  597.     /* Calculate a new light level */
  598.  
  599.     new_light = calculate_light(new_normal);
  600.  
  601.     /* Now plug this NEW stuff into the REMAPPING VECTOR FOR THAT PALETTE
  602.        INDEX! */
  603.  
  604.     LightRemapCopy[nrm.palette_index] = LightRemap[new_lightlevel][nrm.color_to_use];
  605.  
  606. After this is done, you simply SPLASH the polygon ONTO the screen, and use
  607. the 'LightRemapCopy' vector as your color-remapping vector! This will give
  608. you the correct bump-mapping shading for the whole bitmap WITHOUT ADDING
  609. ONCE SIGLE PROCESSOR CYCLE TO THE ACTUAL DRAWING OF THE TEXTURE ON SCREEN!
  610.  
  611. [To speed this even further one can skip the copy step, and make these
  612. changes directly into the LightRemap vector - and remember the original
  613. values and plug them back after the polygon is rendered!]
  614.  
  615. HOW ABOUT IT PEOPLE!? WHEN DO WE SEE THE FIRST DOOM-LIKE FREE-DIRECTION
  616. TEXTUREMAPPING GAME WITH BUMPMAPPING!? WHEN DO WE GET A VERSION OF DESCENT
  617. WHERE THE MINE *REALLY* LOOKS LIKE A MINE - WITH WOBBLY WALLS!!! HOW ABOUT
  618. TOMORROW!? I CANT WAIT!!!!
  619.  
  620. Hope this wasn't completely unreadable!                             [Image]
  621. /Z
  622.  
  623. To My Homepage....
  624.