The Datafile PD-CD 3

home *** CD-ROM | disk | FTP | other *** search

/ The Datafile PD-CD 3 / PDCD_3.iso / utilities / utilsf / graphtext / cga / text0000.txt < prev next >

Wrap

Text File | 1995-03-27 | 37.8 KB | 934 lines

REPOSTED DUE TO POPULAR DEMAND! It seems only selected parts of the globe got my last posting...? Please keep followups to comp.graphics.algorithm ----Snip---- SPEEDY FREE DIRECTION TEXTURE MAPPING ===================================== AND OTHER NIFTY TRICKS Some Wild-Ass Speculations and Untested Theories (that will work :-) by Hakan 'Zap' Andersson 95-02-02 -1. Greed/Copyright If you use any of this stuff in your commercial game, I at least think I deserve to: A) Be mentioned and thanked thoroughly in the game. Thank Hakan 'Zap' Andersson, zap@lysator.liu.se B) Receive a copy of the game!! C) Receive obscene amounts of cash :-) If you fail to comply to the above, it may turn out that I had already patented all algorithms herein, and I would then throw a "Unisys" at you! The information herein is Copyright -95 Hakan 'Zap' Andersson PART I "Texturing in a skewed universe" 0. Introduction So, you played Wolfenstein 3D. So you played DOOM. And you played Descent. Texturemapping in Real Time has proven to be a reality, even on a tiny old PC. This document will take you on a Guided Tour through one of my more recent speculations on the subject. There is no doubt that what I outline here will WORK. I call it speculations only because I havn't actually imple- mented or tested it! Sadly, I have a life, and that life prevents me from luxurios amounts of time at the console hacking for FUN. [It instead forces me to luxurious amounts at the same console, hacking for my bread]. So none would be happier than I if somebody had the time to IMPLEMENT any of this, and please give me the sourcecode when he is done!!! 1. History When I first played Wolfenstein 3D, I was chocked by the "real time textures" that it could produce on my old 386/20. I thought that stuff was only poss- ible on SGI Onyx machines and above. I was baffled. But after some months, the "secret" of the method was analyzed to death by the net. So, it was just vertical slices of wall being scaled vertically! But still - Wolfenstein proves to be the very basis of the idea that will be talked about in this document. Everybody and his sister trying to do a similar thing, would have initially tried to scan-convert the polygons HORIZONTALLY. Mostly because all textbooks on the subject talk about horizontal scanlines as if they were the only things that exists. [Reading too many books limits your thinking!] Wolfensteins strike of genious was to work VERTICALLY. But everybody "knew" that this only worked for walls. We all "knew" that there would NEVER be a game capable of drawing textured floors and ceilings. And boy were we wrong. Out came DOOM. As usual, I thought this was something only a SGI Onyx could do. Now the FLOOR had textures! How the hell was THIS possible!? As usual, the trusty ol' internet (not the RUSTY old internet :-) provided the answer. Naturally, they DID work horizontally on the floor, since horizontally meant along the same Z, which meant linearilly in texture space. "Of course" we thought. "Ok" we thought. "Now we know. Walls work. Floors too. But it is still impossible to work on any orientation of textures. That, at least, is something that only an SGI Onyx can do". Then came Descent. Of course, I knew this was not possible, and that this was not happening in MY tiny computer. (A mere 486/66!). I creapt around the case of my computer to see if there wasn't an SGI machine hidden in there after all! This time, I didn't wait for the 'net to think for me. This time, I did the thinking all on my own. This is the result of that thinking. 2. What Wolfenstein and DOOM taught us The basic principle taught by DOOM (and by Wolfenstein) is this: TRUTH I: As long as you are drawing your polygon ALONG LINES WITH EQUAL Z (The Y axis for walls and the X axis for floors/ceilings) THE TEXTURE IS TRAVERSED LINEARILY. Of course, this was all fine and dandy for FLOORS and WALLS. But what the hell did that help us on that sloping plane we wanted to texture!? The answer is, IT HELPED A LOT. We only have to bang our heads on the walls, and FORGET ALL THAT NONSENSE ABOUT WALKING ALONG HORIZONTAL OR VERTICAL SCANLINES!! TRUTH II: ALL polygons drawn on screen has along SOME DIRECTION equal Z coordinates along that line. This means, that if we can scanconvert our polygons not horizontally, not vertically, but ALONG THIS LINE, we can TRAVERSE THE TEXTURE LINEARILLY. I needn't go in to HOW MUCH THIS WILL SPEED UP EVERYTHING compared to one division per pixel (a common need in texturing algorithms) or bicubic approximations. 3. How the hell (whimsical DOOM reference intended) do we do it!? Step one: Find the elusive screen-direction which represents equal-Z. This turns out to be so trivial it hardly even needs to be mentioned: Take the normal vector, converted to screen-coordinates (as a 2D vector). Your 'constant Z line' will be that vector rotated 90 degrees. [Alternatively, the cross product between the normal and the viewing direction will give you the same line in 3D]. The special case being that the normal points directly at the screen (having (0, 0) size in screen space). This simply means that you can pick ANY line - since the whole POLYGON is on the same Z! Now all you have to do, is to scan-convert your polygon in THIS DIRECTION ON SCREEN. Calculate what texture-coordinate-span that line has, and linearily walk the texture as you draw that line in the polygon. That is "it", really. 4. How can we make this EFFICIENTLY (and without holes?) Firstly, as with ALL line-drawing algorithms, we need different 'versions' of it depending on if the lines slope is in the range +-45 degrees, or if it is closer to the Y direction. I will here only discuss the 'almost horizontal case', where the line has a direction so that for each pixel step along X, Y may OR may NOT increase/decrease one. The algorithm only needs to be "rotated" to work with Y instead of X, and I leave this as an exercise to the reader. Heh. :-) So, assuming that the polygon we want to draw turns out to fulfill this need, we can do the following: I am assuming we want to draw this polygon into a palette-device that is represented in memory as an array of bytes, row by row. This discussion does NOT assume any particular hardware. You may use MODE13 on a PC, or a WinGBitmap under Windows (NT), or you may use an X bitmap under X. Lets have the following C variables: unsigned char *screen; /* Pointer to screen memory */ short x_size; /* Screen X size */ short y_size; /* Screen Y size */ /* A macro to reference any given pixel (read OR write) */ #define PIXEL(x, y) screen[y * x_size + x] Since we are in this example walking along X, we find the 'maximum horizontal size' of the polygon: It's minimum X and it's maximum X coordinates. Now we get clever. We get ourselves an array of integers containing 'x_size' elements. [If we are on a PC, or are confined to 320x200, or any other resolution with less than 64k pixels, a short is sufficient. Otherwize, we need a long] This array will store our sloping line. To save time filling in the array, we only walk it starting in the MINIMUM X of the polygon and walk towards MAXIMUM X of the polygon. Into the array we fill in the BYTE OFFSET for that pixel. Meaning, for the purely horizontal line, the array would contain: 0 1 2 3 4 5 6 7 8 9 .... But for a line that looks like this: X X X X X X X X X Would, on a 320 x 200 graphics mode contain the following offsets: 0 1 2 -323 -324 -325 -646 -647 -648 The reason we store this in an array is threefold: Reason 1: Speed! The line is the same all across the polygon! Why calculate it more than once!? Reason 2: Avoid HOLES. If you calculated the line 'on the fly' you could end up with results such as this: 2 2 2 1 = Line 1 2 2 2 . 1 1 1 2 = Line 2 2 2 2 . 1 1 1 . = Holes in the texture 1 1 1 With a precalculated line, we are guaranteed to get: 2 2 2 2 2 1 1 1 2 2 2 1 1 1 1 1 1 Reason 3: By not only storeing the Y coordinate, but the BYTE OFFSET, we save ourselves a multiplication! 5. How to Scanconvert a polygon along a 'skewed line' But now your real headache starts. How the HELL should I make a polygon scan- conversion algorithm that works along this 'skewed line'!? Didn't I have ENOUGH trouble writing a normal "horizontal" polygon scan converter!? :-) All I say is: Relax, pal. There is hope. There is an easy way: If you have a line that is 'skewed' by a slope of 1:3 (as in the example above), all you have to do, is this: BEFORE scanconverting your polygon (but AFTER transforming to screen- space AND clipping), SKEW THE POLYGON VERTICIES by THE SAME AMOUNT but in the OPPOSITE DIRECTION (in screen space). Then use your NORMAL HORIZONTAL SCAN CONVERSION ALGORIHM. But when you DRAW the LINES, DONT draw the HORIZONTALLY! Use the offset vector, and draw them in the skewed direction! If our sloping line looks like this: X X X X X X X X X Then if this is the original polygon verticies: 1 . . 2 3 . . 4 After 'skewing' it would look like this: 1 . . 2 (moved down 2) 3 . . 4 (moved down 1) To paraphrase: Never "TELL" your scanconverter that you are working with skewed scanconversion! "Fool" it by feeding it a skewed polygon, and get the right result by "skewing back" the output! So, what's the catch? Well, using this method ain't "perfect". You can get seams and holes BETWEEN your polygons, because the outcome of the edge of the polygon depends a little (but not much) on the angle of the skewed line. [Maybe there is a way to treat the edges of the polygon specially? I have many different ideas on this subject, but I dont know how "bad" the result will be, since I have yet to implement ANY of this!] Now, keep in mind that each "scan" along this "skewed" line represents one Z coordinate. This means that for each "scan" you'll need only ONE divide to find out at which point on the TEXTURE your START COORDINATES are. You can also obtain the 'step' size and direction to walk the texture bitmap. Note that the step DIRECTION is the same all over the polygon, but the step SIZE depends on 1/Z. So the direction only needs to be calculated once per polygon. The size needs to be calculated once per scan. (HOW your texture is mapped to the polygon is irrelevant - as long it is linear. The texture needn't necessarily be mapped flat on the polygon - it may even be a threedimensional hypertexture!!) This method also lends itself nicely to a Z-buffer! No need to recalculate Z! It is the same along each "scan"! So only a TEST needs to be done! And if you use a 16-bit Z-buffer, you can use the 'offset vector' discussed above multiplied by two (= shifted left once) to get the offset into the Z-buffer! 6. Conclusion on texturing After realizing this, I feel that Descent isn't impossible after all. I doubt they use exactly THIS technique, but at least it has proven to be theoreti- cally possible to render free-direction textures in realtime. PART II "Let there be light" 0. Some words about lighting OK, so we figured out one way to do quick texturemapping. So we cracked the secret of Descent? Nope. Instead, one of Descent's MOST impressive effects is now the LIGHTING! It seems like they have TRUE lightsourcing with light fall-off in the distance!! And it is not just a "one shade per polygon" thing! It is a true "one shade per pixel" thing! (Try landing a flare on a polygon in some dark area! You get a nice pool of light around it!) This is extremely impressing that they can do this AND texturemapping in realtime, at the SAME time! Sadly, I havn't got a clue. Anyone? Instead, I have got quite a BIG clue about something completely DIFFERENT: 1. DOOM Lighting basics Instead of talking about how Descent does it's ligting, lets step back to something a lot less complex: DOOM's lighting. DOOM really doesn't have much of lighting. What you CAN do, is specify a 'brightness' of a certain area of your 'world'. What DOOM *has* is a 'shade remapping table', and this is what I will use as a base of my idea. Allow me to explain: DOOM uses a 256 color graphics mode - which means that it uses a palette. (Well, actually several palettes that gets exchanged, e.g. a red-ish palette for when you are hurt, e.t.c, but let's not get picky) When the lighting is 100% the pixel in the texturemap is the same pixel value that gets written to screen. But DOOM uses a bunch of (34 i think) remapping tables for different lighting levels. Such as: unsigned char LightRemap[34][256]; So to find the output pixel, the following algorithm would be used: output_pixel = LightRemap[light_level][input_pixel]; The LightRemap vector would be precalculated (in DOOM's case it is actually loaded from the WAD file). So when light_level is max, and imput_pixel references a white pixel, output_pixel will return the same white pixel. But when the lighting is 50%, output_pixel will instead be a gray color. 2. Random dithering to the people! Now one problem that is seen in ALL 3D games is that you can SEE how their lighting falls off in 'steps'. If the palette only contains three darkness-levels of purple, then the LightRemap vector would for light- levels from 0-25% reference BLACK, for 25%-50% the darkest, and so on. You would VERY EASILY *see* the borders between the different levels, as the light diminishes in the distance. That looks UGLY. Now if the game programmers had added FOR EACH PIXEL a RANDOM value to the light. (Quick random values can be gotten from a table. They dont need to be superrandom, only chaotic). This would have given us a DITHER of the screen. And that DITHER would CHANGE for each frame (since it is RANDOM). This would INCREASE the perceived number of colors greatly! Sure - EACH FRAME would look like a "snowy mess" of random noise. But when played quickly, it would look smooth! Compare the perceived color quality of a TV picture from what you get when pausing a frame on your VCR, and you will understand what I am saying. You dont see all the noise in the picture, because the average of the noise over time for each pixel is the intended pixel value. The human eye 'removes' the noise for you. Dithering would increase the colorresolution of games such as DOOM and Descent, and the 'noisy picture' would look MORE REAL than the 'clean' picture of today. (This is true of all moving graphics/animation) 1. Bumpmapping in realtime? Impossible! NOT! Now lets get to the REAL fun!!! One of the Truths I have found in computer graphics is that texture- mapping can GREATLY reduce the number of polygons you need to make an object convincing. But sometimes you still need to have extra polygons, just get away from the "flat" look of the polygons. Another Truth that I found (while implementing my once commercial raytracer) is that the REAL fun starts with BUMPMAPPING! That is when you start talking about REAL decreases in the polygon count! Instead of having hundreds of polygons to make a wobbly mountain side, have ONE polygon, and add the wobblyness of the surface as a bumpmap! The basic idea behind bumpmapping: To do bumpmapping, you need to be doing SOME kind of "real" lighting. But the lighting does NOT need to be ANY MORE COMPLEX than simple cosine lighting. We dont even need point lightsources! Directional light is OK. To get the light-level of a polygon, we simply take the dot-product between the light-direction and the surface normal vector! That's it! If we use directional light, we can assume that light is coming from the direction Lx, Ly, Lz. (This should be a normalized vector: The 'length' should be 1.0) and the polygon normal is Nx, Ny, Nz, the light level is: Light = Lx * Nx + Ly * Ny + Lz * Nz What could be simpler!? Now, Bumpmapping means VARYING the normal vector over the surface, and recalculating a NEW lightlevel for each pixel. For instance, lets assume a surface that is flat in the X-Y plane. If we vary the X component of the surface normal with a sinus function along X, it will look like the surface was rippled with waves in the X direction! The shading of these ripples would be "correct": If we the light comes from the LEFT, the LEFT side of the ripples would be bright and the right side would be dark. if the light came from the RIGHT, the reverse would be true. Now compare games like DOOM, where they "fake" bumpmapping by simply PAINTING light and dark edges on stuff like doors and similar. This looks horrible when two doors opposite eachother in a corridor both have their "bright" edges on their upper and LEFT sides! And trust me, the eye/brain is REALLY good at picking out these inconsitensies. The eye/brain uses shading as its PRIMARY CUE to the real nature of the surface! Yes! The PRIMARY cue! The whole human optical subsystem is oriented towards recognizing shades as being surface variations! A warning-this-is-not-real flag is IMMEDIATELY raised when the 'bright edge' of a door doesn't match the intended light direction! This is where even Descent falls apart! 2. How can we get this into games such as DOOM? Well, first of all SOME kind of 'directional light' must exist. But experience tells me that even a hardcoded directional light, where the light comes from the SAME direction all over the 'world', can increase the realism. And we need to be doing AT LEAST cosine shading. Above I said that to do bumpmapping, we must RECALCULATE THE SHADING FOR EACH PIXEL. Now that doesn't sound very fast, does it? Well, the thing is, we dont need to do that! But first let me explain: In advanced rendering systems you normally have one bitmap as texture- map, and another bitmap as the bump-map. The bumpmap usually defines the simulated 'height' of the surface as the brightness of the bitmap. But HEIGHT in ITSELF is not interesting! (If the surface is flat - it has the same height. Only where the height CHANGES the surface isn't flat, and the normal is affected); HEIGHT is not interesting, CHANGE of height is. So a traditional renderer will have to sample at least FOUR adjacent pixels in the bump-map bitmap, and calculate the 'slope' in that part of the bitmap based on their RELATIVE brightness. That 'slope' is then transformed into a deformation of the normal vector - which in turn (via the shading algorithm) yields another shade at that point (phew!). HOW THE HELL DO I INTEND TO DO SOMETHING LIKE THAT IN REALTIME!? Now, lets assume that we want to make a 'groove' along the Y axis in the middle of our polygon. Lets say the polygon is 64x64 units large, is flat in the XY plane, and the texture mapped to the polygon is also 64x64 in size. So what we want to do, is at X coordinate 32 we want to make a 'groove', so the polygon will LOOK as if it's profile was this: The 'intended' surface seen from negative Y axis: --------------\_/--------------- | ||| | X 0 / | \ X 64 X 31 32 33 Since we are using "flat shading", we will only calculate one brightness level for the whole polygon: The dot-product between the normal vector and the light direction. Lets say that the result is 80%. So, the overall lighting of the polygon is 80%! And 80% is the lightlevel we use on all pixels of the polygon EXCEPT those at X=31 and X=33! Because all pixels at X=31 should look as if they were going 'into' the surface (the normal vector displaced to the right), and those at X=33 should look as coming 'out of' the surface (normal vector displaced to the LEFT). Lets say the lighting level for a normal displaced a little to the left is 95%, and a normal vector displaced a little to the right is 50%. As you can see, we then have three different shadings for this polygon with the current lighting conditions: 80% for most of it, 50% for column 31, and 95% for column 33. As you can see, we do NOT need to recalculate the shading for each pixel. We only need to recalculate the shading level AS MANY TIMES AS WE HAVE DIFFERENT DISPLACEMENTS OF THE NORMAL VECTOR. 3. How to implement this: We can let the normal texture bitmap that you use for texturing contain additional data: Any number of 'normal displacement' structures. struct normal_displacement { int palette_index; real normal_displace_x, normal_displace_y; int color_to_use; }; Any number of these structures may be attached to a bitmap. Lets say we have the following bitmap. Our goal is to depict a flat gray surface with a raised gray square in the middle. (Each number represents the palette index for that pixel:) Y 11111111111111111111111111111 11111111111111111111111111111 11111222222222222222222111111 11111311111111111111114111111 11111311111111111111114111111 11111311111111111111114111111 11111311111111111111114111111 11111311111111111111114111111 11111311111111111111114111111 11111311111111111111114111111 11111355555555555555554111111 11111111111111111111111111111 11111111111111111111111111111 (0,0) X Attach to this bitmap we have the following four normal_displacement structures: { palette_index = 2; normal_displace_x = 0; normal_displace_y = 0.5; color_to_use = 1; } { palette_index = 3; normal_displace_x = -0.5; normal_displace_y = 0; color_to_use = 1; } { palette_index = 4; normal_displace_x = 0.5; normal_displace_y = 0; color_to_use = 1; } { palette_index = 5; normal_displace_x = 0; normal_displace_y = -0.5; color_to_use = 1; } Now what does this mean? Let's say that color index 1 is just medium gray. So all pixels with index 1 will simply be medium gray. The structures appended means that color index 2 *IN THE BITMAP* should represent an edge pointing 'upwards' (we displace the normal vector's Y by 0.5 (normally this displacement would need to be trans- formed into the space of the polygon, but for our example, this is sufficient)). Now since color index 2 maybe normally be GREEN, PURPLE or any other undesired color, the structure contains the member color_to_use. In our example, this is 1. This means that this pixel will ALSO be medium gray - but with a DIFFERENT LIGHTING LEVEL. Similarily, color index 3 is an edge pointing 'to the left', 4 is an edge pointing 'to the right', and 5 is an edge 'pointing down'. If we would have wanted another COLOR, but the same DISPLACEMENT, we would have needed another structure for that, e.g. if the lower half of the bitmap would have been GREEN, we would have needed a few different displacement-structures for green pixels as well. How how should we make this efficiently? Well, remember the LightRemap vector we talked about earlier. This comes into play for us. The overall color level of the polygon is 80%, remember? So, lets make a COPY of the LightRemap vector for light level 80%. Lets put this into vector LightRemapCopy: unsigned char LightRemapCopy[256]; memcpy(LightRemapCopy, LightRemap[light_level]); Now, lets walk through the normal_displacement structures. For each structure: struct normal_displacement nrm; /* Displace the normal */ displace_normal(normal, &new_normal, nrm); /* Calculate a new light level */ new_light = calculate_light(new_normal); /* Now plug this NEW stuff into the REMAPPING VECTOR FOR THAT PALETTE INDEX! */ LightRemapCopy[nrm.palette_index] = LightRemap[new_lightlevel][nrm.color_to_use]; After this is done, you simply SPLASH the polygon ONTO the screen, and use the 'LightRemapCopy' vector as your color-remapping vector! This will give you the correct bump-mapping shading for the whole bitmap WITHOUT ADDING ONCE SIGLE PROCESSOR CYCLE TO THE ACTUAL DRAWING OF THE TEXTURE ON SCREEN! [To speed this even further one can skip the copy step, and make these changes directly into the LightRemap vector - and remember the original values and plug them back after the polygon is rendered!] HOW ABOUT IT PEOPLE!? WHEN DO WE SEE THE FIRST DOOM-LIKE FREE-DIRECTION TEXTUREMAPPING GAME WITH BUMPMAPPING!? WHEN DO WE GET A VERSION OF DESCENT WHERE THE MINE *REALLY* LOOKS LIKE A MINE - WITH WOBBLY WALLS!!! HOW ABOUT TOMORROW!? I CANT WAIT!!!! Hope this wasn't completely unreadable! /Z ! Hakan "Zap" Andersson ! Cheif software developer ! Q: "0x2b | ~0x2b"! ! zap@lysator.liu.se ! Genius Cad Software Scandinavia ! A: 42 ! ! Phone: +46 16 96460 ! Fax: +46 16 96014 ! Whirled Peas. ! -- ! Hakan "Zap" Andersson ! Cheif software developer ! Q: "0x2b | ~0x2b"! ! zap@lysator.liu.se ! Genius Cad Software Scandinavia ! A: 42 ! ! Phone: +46 16 96460 ! Fax: +46 16 96014 ! Whirled Peas. ! Path: bcc.ac.uk!uknet!strath-cs!nntp0.brunel.ac.uk!sunsite.doc.ic.ac.uk!agate!newsxfer.itd.umich.edu!umcc.umich.edu!not-for-mail From: pnettle@umcc.umcc.umich.edu (Paul Nettle) Newsgroups: comp.graphics.algorithms Subject: S-Buffer FAQ is here! Date: 12 Mar 1995 05:26:53 -0500 Organization: UMCC, Ann Arbor, MI Lines: 944 Message-ID: <3jui9e$9ni@umcc.umcc.umich.edu> NNTP-Posting-Host: umcc.umcc.umich.edu Summary: Here's the s-Buffer FAQ Keywords: s-buffer X-Newsreader: NN version 6.5.0 #1 (NOV) ~Newsgroups: rec.games.programmer ~Subject: S-Buffer FAQ is here! Summary: Here's the s-Buffer FAQ you've all been waiting for... Keywords: s-buffer faq It's late, and I just finished the first pass. I wasn't expecting to have it done until late next week, but the response has been unforgettable. So, finally (yeah, right, only 2 days) here it is. :) Your comments are welcome. If you have any, please leave them in my e-mail box (contact information enclosed in the FAQ). Be careful, please make your comments HELPFUL and POSITIVE. - Paul ---------------------------------------------------------------------------- SS BBBBBB UU UU FFFFFFFF FFFFFFFF EEEEEEEE RRRRRR SS BB BB UU UU FF FF EE RR RR SS BB BB UU UU FF FF EE RR RR SS BB BB UU UU FF FF EE RR RR SS ---- BBBBBB UU UU FFFFF FFFFF EEEEE RRRRRR SS ---- BB BB UU UU FF FF EE RR RR SS BB BB UU UU FF FF EE RR RR SS BB BB UU UU FF FF EE RR RR SS BB BB UUUUUU FF FF EE RR RR SS BBBBBBB UUUU FF FF EEEEEEEE RR RR FFFFFFFF AAAA QQQQ Original Creation: FF AAAAAA Q Q Mar. 10, 1995 FF AA AA QQ QQ FF AA AA QQ QQ Written By: FFFFF AAAAAAAA QQ QQ Paul Nettle FF AA AA QQ QQ FF AA AA QQ QQ Version: FF AA AA QQ Q QQ 1.0.0 FF AA AA QQQQQQ FF AA AA QQQQQ QQ ------------------------------------------------------------------------------- A note from the author: This may be a bit wordy at times, so I'll try to keep it light with some of my humor -- you may not call it humor, but at least *I* think it's funny. :) Where did they come from? s-Buffers were developed for my game engine. Though, since I don't believe that FAQs should have anything to do with commercialization, I won't even mention the name of this product. Let's keep FAQs for their purpose -- FACTS. The technique described in the next few hundred lines of text bears a close resemblance to some scanline rendering methods of which I believe span-buffering is one of them. Actually, I had no idea what span-buffering was until I spoke to a gentleman named Chris Babcock who read the original posts about s-buffering. He explained to me what span-buffering was, and as it turns out, the two techniques are similar, but do have some major differences (mainly the Insertion routine and segment manager). The major difference is that s-Buffers are more so meant for use in game engines. Engines that are meant to produce a high frame rate. When I posted a note to the rec.games.programmer newsgroup about the fact that I had discovered a technique that would perform z-Buffers in software faster than hardware could, the response was, quite literally, overwhelming. Most of which was plagued with polite suspicion and skepticism. This alone told me that, at least, in the gaming community, this technique was unfamiliar territory. So, I propose to you, the game developer, a new technique, called s-Buffering. The particular implementation of this technique and it's name are both my own original creation, sparked by my own, sometimes wry thoughts. This FAQ and the techniques contained within are also all my own creation. This isn't to say that there isn't somebody else out there that has once thought about these techniques or variations thereof. I have no control over their thoughts (and wouldn't want to -- Ewwwwww!). I am quite confident, however, that this technique is not popular, not documented, and not in wide use within games. If you find the information contained within these words, diagrams, and psudo-codes useful to any degree, please contact me. If you use this technique in a product (commercial or otherwise) that you would not have done so if it had not been for this FAQ, please just drop me a line and let me know. It's nice to hear those things. Hearing good things about efforts like this can only spark more. I would also encourage anybody and everybody to dig in. Play with this new technique. It's not perfect, and the "Insertion" routine can be it's own line of discussion -- inventing many new algorithms for insertion can very possibly improve the performance of this technique in quantum leaps. I would expect that if this technique gains any popularity, you'll see new insertion algorithms popping up in the next Siggraph Proceedings. I'll be the caretaker of this document. Please make all corrections through me by contribution (internet e-mail preferred). If you do have other useful information related to this FAQ, !PLEASE! contact me. I may very well want to include it in future versions of this FAQ. Lets keep the InfoBahn alive, let's contribute to it, and share ideas. We've got a hell of a lot of brains out there to draw from. Striving for speeeeed, Paul Nettle Hot Wax Software "And now for something completely different. A man with six-hundred thirty-two-thousand four-hundred and forty-two big toes." ------------------------------------------------------------------------------- Q: "How do I contact Paul?" ------------------------------------------------------------------------------- My vitals are: -------------- ADR: 7054 Foxthorn Dr. Canton, MI 48187-3073 PH#: (313) 981-6143 anytime NET: pnettle@umcc.umich.edu CIS: 72163,2442 Please, the name's "Paul", not "Mr. Nettle" :) I hear "Mr. Nettle", and I turn around looking for an older man. ------------------------------------------------------------------------------- Q: "OK, so what the heck is this all about?!!" ------------------------------------------------------------------------------- The movie "Weekend at Bernies" quotes this line: "He's got good form!" I think that's one of my favorite quotes because, to me, it has a serious side other than it's humorous description of a corpse being dragged behind a moving boat by a rope, braining itself on buoys along the way. "Good form" is "Elegance." Webster defines "Elegant" as: "Marked by concision, incisiveness, and ingenuity; cleverly apt and simple" I couldn't have said it better, Noah. Since elegance is a goal and not a destination, it's something that's to be strived for. You can't reach pure elegance since there is always *something* that's more elegant (the human body, for example). I hope you find s-Buffers to be "simply brilliant." Not that I'm the brilliant one, mind you, I only discovered the technique. The technique then just started to jump up and down, wave it's arms, blare sirens, and was later found to be screaming out it's advantages at me. I'm just writing them down. So, back to the question. What's this all about? Elegance, Simplicity and, of course, Speeeeeeeeeeeeeeeeeeeeeeed! ------------------------------------------------------------------------------- Q: "Why s-Buffers?" ------------------------------------------------------------------------------- First, consider z-Buffers. If you're not sure EXACTLY how they work, I'll explain briefly: A z-Buffer is a `second copy' of the screen-image. It usually has the same resolution. This z-Buffer is initialized to the largest possible value held by an UNSIGNED INT (for 16-bit INTs, that's 0xFFFF, and for 32-bit INTs that's 0xFFFFFFFF). During the drawing of polygons, the depth-value for each pixel written has to be kept track of. As you draw each pixel in a polygon, you compare the depth-value of that pixel with the value in the z-Buffer's corresponding pixel location. If the z-Buffer value is larger (farther away from the camera), then the pixel is plotted, and the z-Buffer is updated with the new pixel's depth. If the z-Buffer value is lower (closer to the camera), then the pixel is not drawn since it is hidden behind the existing pixel. This is a very simple approach, and, depending on implementation, can offer pixel-perfect output. However it is very slow and cumbersome. Your code's inner-most loop (the code that's doing the drawing of the pixels) -- the same code you've hand-assembled for speed is being used to waste clock cycles as if they're as rich a commodity as Madonna CDs. Even if that mean-ol-nasty z-Buffer says the pixel is hidden, you still need to track your deltas. You still have to keep moving through your shades, texture maps, bump maps, colors, etc. So, you've had to add depth-tracking as well as a slow check to another buffer (possibly outside of your CPU's cache), and a conditional update to that buffer. Whew...what a waste. Such a waste in fact, that I plan to tell you how s-Buffers are not only FAST, but FASTER than z-Buffering in HARDWARE. Keep reading, it's all in here. Is there a more elegant solution? I believe I have found one. I call it, simply, "s-Buffering." ------------------------------------------------------------------------------- Q: "What are s-Buffers?" ------------------------------------------------------------------------------- `S-Buffers' or `segmented-Buffers' are the segmented representation of a z-Buffer. They have three key elements: 1. An array of linked-lists (for this example) 2. An insertion routine for inserting segments into the s-buffer 3. A segment manager These key Elements are outlined in the next few questions. To continue with the answer to this question, you'll need to read the next three Qs. ------------------------------------------------------------------------------- Q: "What is...KEY ELEMENT #1: The s-Buffer itself" ------------------------------------------------------------------------------- For the sake of simplicity, I'll just use a linked list, later, this can be expanded upon. It's the concept I'm trying to get across here. Lets consider our trusty friend, the z-Buffer. Pull out a single scanline from the z-Buffer and set it's representation on the kitchen table (watch out, don't set it in the little puddle of spaghetti sauce). You now have a single plane. Across the front is the x-direction through a scanline. As you run your finger from the front to the back you're moving it along the depth axis (z-axis). Now go wipe that spaghetti off your finger. Kitchen-table representation x z-Buffer (Dots represent the depth of a pixel) +-------------------+ _______________________ y|-------------------| / (far away) / n |-------------------| / / o |-------------------| / .. / i |-------------------| / . . / t |---------------------\ / ... .. . / c |-------------------| | / . .. / e |-------------------| | /.. . / r |-------------------| | / / i |-------------------| | / . ..../ d |-------------------| | / (close) . / / +-------------------+ \--->/______________________/ Z (front -- x-direction) When you look at the entire z-buffer, you're looking at a stack of these planes (that's not true at all, but I want you to think of it that way for now). So, lets just consider the kitchen-table representation. For each scanline in the z-Buffer, what you have is a list of depth values for each pixel. Even though you may only have a single polygon on the screen, and the depth values in the z-Buffer that the polygon occupies are all the same (it's orientation is perpendicular to the z-axis), you still have to check each pixel, right? Not any more.