Hi, Here is what I have recieved so far some techniques used to do the graphics in Wolfenstien 3D. I post this to the net. hope it is useful to you. If you come across anything, please let me know. I will post another summary if I have more satisfactory answers. ..... Tom ------------------------------------------------------------------ Article: 6901 of rec.games.programmer Newsgroups: rec.games.programmer Path: dg-rtp!psinntp!rpi!usc!cs.utexas.edu!utgpu!watserv1!dstamp From: dstamp@watserv1.waterloo.edu (Dave Stampe-Psy+Eng) Subject: Re: Wolfstein 3D graphics : HOW ?? Message-ID: <1992May14.140542.3654@watserv1.waterloo.edu> Organization: University of Waterloo References: <783@hobby.ukc.ac.uk> Date: Thu, 14 May 1992 14:05:42 GMT Lines: 44 In article <783@hobby.ukc.ac.uk> jm6@ukc.ac.uk (J.Mitchell) writes: > >How do the graphics in Wolfstein 3D work, I think they must be bitmapped >using a lookup table to dump them to the screen. I think this because of the >speed and the false perspective on the objects such as the suits of armour >the washbasin etc. ie. if you move around them they don't change shape like >the walls do. This brings me to the problem of storing all the walls, I haven't >tried to work out the required storeage but it must be very large and obviously >you can get it all into memory but how? A little thought reveals what is done. First, the program runs in an X mode varient (hence no flicker). Therefore it has to access pixels in columns differing by 4 and do 4 passes (no 4-pixel copies here). Also, the perspective of the walls is centered therefore the top-to-bottom compression/expansion is constant for any column, and the left-to-right compression may be looked up in a table or calculated on the fly. So what you have are: -bitmaps in memory of objects and walls -lookup tables for vertical compression (100 or so at 400 bytes each) -lookup tables for horizontal compression (optional) You simply select a column in the screen area, lookup the offset address in the horizontal table, then move down the screen column adding the horizontal offset, center left screen address, and the vertical offset from the table to get the address in the bitmap to read. This is just an outline, but it's eminantly codeable in assembler and would get about 1 million pixels/sec on a 386 (500,000 for a slow 286) with a fast video card (1/2 that for a slow card). Problem is, this method limits the perspective views possible. It isn't general enough to use in a 3D generic renderer, for example. For that, you need a stepping parametric surface method, which probably is 1/3 or less of the speed. -------------------------------------------------------------------------- | My life is Hardware, | | | my destiny is Software, | Dave Stampe | | my CPU is Wetware... | | | Anybody got a SDB I can borrow? | dstamp@watserv1.uwaterloo.ca | __________________________________________________________________________ Article: 6921 of rec.games.programmer Newsgroups: rec.games.programmer Path: dg-rtp!psinntp!uunet!sun-barr!cs.utexas.edu!utgpu!watserv1!dstamp From: dstamp@watserv1.waterloo.edu (Dave Stampe-Psy+Eng) Subject: Re: Wolfstein 3D graphics : HOW ?? Message-ID: <1992May17.134700.4605@watserv1.waterloo.edu> Organization: University of Waterloo References: <1992May17.063824.15590@zooid.guild.org> Date: Sun, 17 May 1992 13:47:00 GMT Lines: 27 ross@zooid.UUCP (Ross Ridge) writes: >dstamp@watserv1.waterloo.edu (Dave Stampe-Psy+Eng) writes: >>This is just an outline, but it's eminantly codeable in assembler >>and would get about 1 million pixels/sec on a 386 (500,000 for a slow >>286) with a fast video card (1/2 that for a slow card). > >This I seriously doubt, as you can only get about 1.5Mb/s with a >REP MOVSW and a fast VGA card (ie. ATI Wonder XL). > Oh yeah? With a 280x150 window (42000 pixels) and quick math, you get about 2uS per loop INCLUDING the VGA access wait time (and of course you code this inline too). So that's 84 mS per screen, and the screen clear and drawing of celing and floor takes 15 mS or less, as it's done in a special mode. So that's 10 fps on the slower PCs. Point is, you can't expect to do sizing in the X-mode varients and get enhanced performance. I know whereof I speak: I've written full-screen 3D graphics that run at 50 fps with 100 lit polys in 256 color mode. -------------------------------------------------------------------------- | My life is Hardware, | | | my destiny is Software, | Dave Stampe | | my CPU is Wetware... | | | Anybody got a SDB I can borrow? | dstamp@watserv1.uwaterloo.ca | __________________________________________________________________________ Article: 6922 of rec.games.programmer Path: dg-rtp!psinntp!rutgers!jvnc.net!darwin.sura.net!tulane!uflorida!reef.c s.ufl.edu!gmt From: gmt@reef.cis.ufl.edu (Gary McTaggart) Newsgroups: rec.games.programmer Subject: Re: Questions on graphics programming like in Underworld and Wolfenstein 3D Keywords: graphics programming underworld wolfensten Message-ID: <35574@uflorida.cis.ufl.edu> Date: 17 May 92 19:17:18 GMT References: Sender: news@uflorida.cis.ufl.edu Organization: Univ. of Florida CIS Dept. Lines: 64 Nntp-Posting-Host: reef.cis.ufl.edu In article P.S.Haight@cornell.edu (Peter Haight) writes: > > Does anyone have some general idea how they do the graphics for those new >graphic games like Underworld and Wolfenstein 3D? What I mean is, how do >they get the real dungeon effect by calculating distances and angles and >things like that? or what? This is all just speculation, but: Ignoring objects in the scenes, the 3d calculations for the walls are minimal being that only very few walls can be seen at any given time. Only the corners of each wall have to be calculated. This is simplified by the fact that the walls are stationary, therefore a lot of pre-processing can be done for hidden surface removal. Once the screen coordinates of the corners of each wall is calculated, it is then just a simple matter of outputting a scaled version of a "sprite" to the appropriate four-sided polygonal area on the screen. consider: (x1, y1) |... | ~~~... | ~~~... | ~~~| (x2, y2) | | | | | ...| (x2, y4) | ...~~~ | ...~~~ (x1, y3) |~~~ Generating the distorted sprite to the screen is simplified by the fact that the left-most x values for the corners are always equivalent and the right-most x values are also equivalent. You can then do a loop which is indexed by the screen x coordinate from the left to the right. The sprite x coordinate is initially zero and is incremented by (sprite_width / screen_image_width) each iteration. The inside y loop is similar. I can tell that Wolfenstein uses either ModeX or ModeY, but I'm no sure how they are using the quirks of either to their advantage. The most that I can figure out is that the are doing the outside x loop four times per image and setting the map mask only once at the beginning of each loop. Also their is the advantage of multiple pages and all. Of course, this is all pure speculation, but I am in the process of assembly-izing the above at the moment. If you are interested in an extremely ugly C version of the algorithm (for algorithmical purposes only: it is extremely inefficient), send me some mail. As soon as I get the assembly version working, I'll post it so that many hands can improve upon it. It includes the ability to load the images from GIF files so that the plates can be created with any paint program. I also have an incomplete library of stuff to manipulate 3d polygonal objects which could be incorporated, but I'm not sure if I'm going to release that any time soon, thoug. I think that they would make a good marriage. By the way, I haven't seen the Ultima game that uses this technique, how is it? Any input would be appreciated, Thanks, Gary McTaggart gmt@cis.ufl.edu Article: 6928 of rec.games.programmer Newsgroups: rec.games.programmer Path: dg-rtp!psinntp!uunet!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!jvnc.net! arwin.sura.net!mips!mips!munnari.oz.au!uniwa!oreillym From: oreillym@tartarus.uwa.edu.au (Michael O'Reilly) Subject: Re: Wolfstein 3D graphics : HOW ?? Message-ID: <1992May18.083607.9732@uniwa.uwa.edu.au> Sender: news@uniwa.uwa.edu.au (USENET News System) Nntp-Posting-Host: tartarus.uwa.edu.au Organization: University of Western Australia References: <1992May17.063824.15590@zooid.guild.org> Date: Mon, 18 May 1992 08:36:07 GMT Lines: 18 ross@zooid.guild.org (Ross Ridge) writes: : dstamp@watserv1.waterloo.edu (Dave Stampe-Psy+Eng) writes: : >This is just an outline, but it's eminantly codeable in assembler : >and would get about 1 million pixels/sec on a 386 (500,000 for a slow : >286) with a fast video card (1/2 that for a slow card). : : This I seriously doubt, as you can only get about 1.5Mb/s with a : REP MOVSW and a fast VGA card (ie. ATI Wonder XL). Thats about right. 1.5 Mb/s == about 6 million pix's per second. You are setting 4 pixels with each byte if I remember right??? : Ross Ridge : : -- : Ross Ridge - The Great HTMU l/ // : [OO][oo] : ross@zooid.guild.org /()\/()/ : uunet.ca!torag!zooid!ross db // Article: 6931 of rec.games.programmer Newsgroups: rec.games.programmer Path: dg-rtp!psinntp!uunet!cs.utexas.edu!utgpu!watserv1!dstamp From: dstamp@watserv1.waterloo.edu (Dave Stampe-Psy+Eng) Subject: Re: Wolfstein 3D graphics : HOW ?? Message-ID: <1992May18.134856.1137@watserv1.waterloo.edu> Organization: University of Waterloo References: <1992May18.083607.9732@uniwa.uwa.edu.au> Date: Mon, 18 May 1992 13:48:56 GMT Lines: 38 oreillym@tartarus.uwa.edu.au (Michael O'Reilly) writes: >ross@zooid.guild.org (Ross Ridge) writes: >: dstamp@watserv1.waterloo.edu (Dave Stampe-Psy+Eng) writes: >: >This is just an outline, but it's eminantly codeable in assembler >: >and would get about 1 million pixels/sec on a 386 (500,000 for a slow >: >286) with a fast video card (1/2 that for a slow card). >: >: This I seriously doubt, as you can only get about 1.5Mb/s with a >: REP MOVSW and a fast VGA card (ie. ATI Wonder XL). >Thats about right. 1.5 Mb/s == about 6 million pix's per second. >You are setting 4 pixels with each byte if I remember right??? > Yes, when your'e doing fills where you know the color of all 4 pixels or they're all the same color. You load the 4 on-chip plane latches, then use them in mode X to squirt 4 pixels to the screen with each write. You can also do fast copies (sprites) from video memory this way. You waste 1.5 uS in accessing the mask resister, though, every time you need to access less than 4 pixels. This method won't work when doing dynamic resizing, and especially not for 3D texture mapping-- you have to go back to 1 pixel per write. You can access every 4th pixels without changing the plane mask register, which is expensive. The mapping method I described earlier is column-based, so you can do every 4th column, change the mask, do the secind set, and so on. Quite efficient. 1/4 the speed of the 4-pixel fills, but then most of the screen isn't texture mapped. -------------------------------------------------------------------------- | My life is Hardware, | | | my destiny is Software, | Dave Stampe | | my CPU is Wetware... | | | Anybody got a SDB I can borrow? | dstamp@watserv1.uwaterloo.ca | __________________________________________________________________________ Article: 6930 of rec.games.programmer Xref: dg-rtp rec.games.misc:34493 rec.games.programmer:6930 Path: dg-rtp!psinntp!rutgers!usc!zaphod.mps.ohio-state.edu!uakari.primate.wi c.edu!umriscc!mcs213k.cs.umr.edu!bkirby From: bkirby@cs.umr.edu (Bill Kirby) Newsgroups: rec.games.misc,bit.listserv.games-l,rec.games.programmer Subject: WolfEdit v1.0 (Graphic Editor for Wolfenstein 3-D) Message-ID: <5118@umriscc.isc.umr.edu> Date: 18 May 92 10:34:39 GMT Sender: news@umriscc.isc.umr.edu Followup-To: rec.games.misc Organization: University of Missouri - Rolla Lines: 38 Originator: bkirby@mcs213k.cs.umr.edu Our news feed has been down since I posted last, so I don't know what kind of response I got. I did get several e-mail requests to upload my editor, so here it is. I uploaded it to two sites: wuarchive.wustl.edu (128.252.135.4) /pub/MSDOS_UPLOADS/wolfed10.zip cs.umr.edu (131.151.6.11) /bkirby/wolfed10.zip I'm going to remove it from my local site after a week. I decided that my editor was pretty cheezy, so I added a GIF-import feature that lets you convert a GIF file into a wall image. Use your favorite paint/draw program and save it as a GIF. I just wrote the GIF decoder yesterday, and it's the first time I've ever written any LZW compression routines, so it probably still has a bug or two in it. I didn't include source code, primarily because the code is *REALLY* ugly. If I ever clean up the code, i'll include it in future versions. If you want to know the various file formats, look in FILEINFO.TXT. If you come up with any nifty graphics, upload them for everyone to see. I wouldn't upload the VSWAP.WL1 file, because it's huge and it may violate the "do not distribute any modified version" shareware rule. Upload the .WAL files instead. Enjoy, +--------------------------+-----------------------------------------------+ | Bill Kirby | Internet: bkirby@cs.umr.edu | | Computer Science Dept. | Bitnet: bkirby%cs.umr.edu@umrvmb.bitnet | | University of MO - Rolla | UUCP: ...!uunet!cs.umr.edu!bkirby | +--------------------------+-----------------------------------------------+ Article: 6938 of rec.games.programmer Path: dg-rtp!psinntp!uunet!caen!uflorida!reef.cis.ufl.edu!gmt From: gmt@reef.cis.ufl.edu (Gary McTaggart) Newsgroups: rec.games.programmer Subject: Here's some C code for Wolfenstein-type graphics Message-ID: <35595@uflorida.cis.ufl.edu> Date: 19 May 92 00:57:52 GMT Sender: news@uflorida.cis.ufl.edu Organization: Univ. of Florida CIS Dept. Lines: 96 Nntp-Posting-Host: reef.cis.ufl.edu Here's some ugly, nasty, uncommented, inefficient C code to place sprites on the screen as necessary for games such as Wolfenstein 3d. It is completely unoptimized and I'm not sure if this is even the algorithm that they are using, but it works. x1: the leftmost x coordinate for the screen image. x2: the rightmost x coordinate for the screen image. y1: the y coordinate of the upper-left of the screen image. y2: the y coordinate of the upper-right of the screen image. y3: the y coordinate of the lower-left of the screen image. y4: the y coordinate of the lower-right of the screen image. Notice that the x coodinate for the 2 leftmost corners equivalent, as is in Wolfenstein. (Same goes for the right.) The sprite is a understood to be a continuous stream in memory of the palette indices for the image. In order to use this, you need to calculate the screen coordinates of the corners of a wall tile. (All of the walls are made up of square tiles.) If you don't know how to do this, I will soon post stuff to do this with, or consult Foley and Van Damn (Computer Graphics: Principles and Practices). I will also be posting some code to read GIF files for use with this. The tiles can not be too large because the distortion of the images is only an approximation for where each actual "pixel" would be. Forshortening is only taken account for on the level of the tiles themselves and their corners. The code assumes mode 13h (320x200x8bit) for simplicity. Keep in mind that the code is not *NEAR* to completion and is only here to show the algorithm involved. The following improvements must be made before it is even close to being usable: 1. The "quirks" of ModeX must be taken into account as advantages. eg. If you limit the number of colors for a given tile, you can preload all possible combinations of the color into an unviewed video page and spit out 4 pixels at one time. Also, if you choose not to do the preloading in preference of more colors, then you can write every fourth column in four passes, loading the map mask only once for each column. 2. 386 specific code would probably be benificial considering that most of the values used are 16.16 fixed point. We could take advantage of the 32 bit math instructions. 3. It needs to be ported to assembler. I am currently working on doing this, but I be RRRREEEEAAAALLLL slow with writing assembly!!!!!!! Any ideas would be greatly appreciated. I am not sure if all of this crap covers everything that needs to be known in order to make this run efficiently. Any questions, comments, flames, etc would be greatly appreciated, Thanks, Gary McTaggart gmt@cis.ufl.edu ------------------------------------------------------------------------------ extern unsigned char far *vid; void out( const char *sprite, int sprite_width, int sprite_height, int x1, int x2, int y1, int y2, int y3, int y4) { long topslope, botslope, yimage_top, yimage_bot, x_ratio, y_ratio, xsprite, ysprite; int ximage, yimage, yimage_bot_shr_16; unsigned int vidoffset; topslope = ( ( long )( y2 - y1 ) << 16 ) / ( x2 - x1 ); botslope = ( ( long )( y4 - y3 ) << 16 ) / ( x2 - x1 ); yimage_top = ( long ) y1 << 16; yimage_bot = ( long ) y3 << 16; x_ratio = ( ( long ) sprite_width << 16 ) / ( x2 - x1 ); ximage = x1; xsprite = 0; for( ; ximage < x2; ximage++, xsprite += x_ratio ) { y_ratio = ( ( long ) sprite_height << 16 ) / ( ( yimage_bot - yimage_top ) >> 16); ysprite = 0; yimage = yimage_top >> 16; vidoffset = 320 * yimage + ximage; yimage_bot_shr_16 = yimage_bot >> 16; for( ; yimage < yimage_bot_shr_16; yimage++, ysprite += y_ratio ) { *( vid + vidoffset ) = sprite[( xsprite >> 16 ) + ( sprite_width * ( ysprite >> 16 ) )]; vidoffset += 320; } yimage_top += topslope; yimage_bot += botslope; } } Article: 6947 of rec.games.programmer Newsgroups: rec.games.programmer Path: dg-rtp!psinntp!rpi!usc!cs.utexas.edu!utgpu!watserv1!dstamp From: dstamp@watserv1.waterloo.edu (Dave Stampe-Psy+Eng) Subject: Re: Wolfstein 3D graphics : HOW ?? Message-ID: <1992May19.221820.25442@watserv1.waterloo.edu> Organization: University of Waterloo References: watserv1.waterloo.edu> <1992May19.040211.4109@zooid.guild.org> Date: Tue, 19 May 1992 22:18:20 GMT Lines: 44 ross@zooid.guild.org (Ross Ridge) writes: > >42000 pixels in 84 ms is only 500,000 pixel/sec not the 1 million >you claim. I wouldn't mind seeing this quick math. > Since not all machines are as fast as mine, I used the slower end of the range. I try to be cautious that way. There are several ways to get that speed, even writing one pixel at a time. The idea is to eliminate the needs for any more calculations than a table lookup, or an add and shift. This is easily done for the special perspective case of the W grphics. For full 3D texture mapping (as in the Underworld demo) you cannot use table lookups, but there are iterative algorithms using adds and shifts for this as well. Speeds here are 2 or 3 times as slow. For the W graphics, you precompute a table (one entry for each column of the poly on-screen) containing the bitmap start address, screen start address, compression factor (8 bits integer, 8 bits fractional) and the number of pixels in the screen column. This can be done with little math. Then for each screen column, you load registers from the table then loop. For best results, use an inline implementation and use a jump vector to the start or end. add dl, ah adc bx,si mov al,es:[bx] mov al,0000[di] ; one number for each screen offset so no inc needed dl is the fractional step accumulator, si is the integer step, bx is the bitmap pointer, di is the screen column pointer, al holds the fractional step. Repeat as needed in memory (200x max) then offset the column address and jump to the correct entry point to set the number of pixels in the column. Load dl, si, bx, and di from the column start table. THis code will execute at 1 Mpix/sec on a 386/25 or better and a fast VGA card. -------------------------------------------------------------------------- | My life is Hardware, | | | my destiny is Software, | Dave Stampe | | my CPU is Wetware... | | | Anybody got a SDB I can borrow? | dstamp@watserv1.uwaterloo.ca | __________________________________________________________________________ Article 9400 of rec.games.programmer: Xref: netcom.com comp.graphics:30649 alt.graphics:945 alt.msdos.programmer:6316 comp.programming:3657 rec.games.programmer:9400 Newsgroups: comp.graphics,alt.graphics,alt.msdos.programmer,comp.programming,rec.games.programmer Path: netcom.com!csus.edu!wupost!howland.reston.ans.net!spool.mu.edu!agate!ames!saimiri.primate.wisc.edu!sdd.hp.com!ux1.cso.uiuc.edu!news.cso.uiuc.edu!ph-meter.beckman.uiuc.edu!trimble From: trimble@ph-meter.beckman.uiuc.edu (Chris Trimble) Subject: Re: Help with Grapics Techniques References: <1993Feb2.192545.18255@ultb.isc.rit.edu> Message-ID: Sender: usenet@news.cso.uiuc.edu (Net Noise owner) Organization: University of Illinois at Urbana Date: Tue, 2 Feb 1993 23:37:59 GMT Lines: 26 In comp.graphics you write: >I am looking for references, either books or source code, to the technique > used to do the graphics in Wolfenstien 3D. I am familar with 3D >graphics and texture mapping, but I am unsure of the best way to apply this to >a 3D maze. From what I have come to understand, all of the so-called "3D" in C.W. was pre-drawn and then just scaled to the screen. Think of it this way --- for each little 3-d effect on the screen, the writers have drawn a corresponding bitmap.. then the program just scales to according to its depth (i.e. - shrinks it if its far away, makes it grow if its near). If you think about it, this is what the arcade game manufacturers do, too. Very few arcade games have rendered-on-the-fly 3-d, and you can tell straight off that that's what they are doing. Atari is the only one that comes to mind right now (e.g. Hard Drivin'). A good example of an arcade game that uses this 'phoney' three-d is AfterBurner II. In fact, I think most of the Sega games do this. - Chris -- Chris Trimble Fight the real enemy! Beckman Institute Systems Services - chris1@uiuc.edu - PGP key available. Article 9472 of rec.games.programmer: Xref: netcom.com comp.graphics:30783 alt.graphics:954 alt.msdos.programmer:6350 comp.programming:3713 rec.games.programmer:9472 Path: netcom.com!netcomsv!butch!kronos.arc.nasa.gov!ames!haven.umd.edu!darwin.sura.net!spool.mu.edu!uwm.edu!ogicse!flop.ENGR.ORST.EDU!gaia.ucs.orst.edu!umn.edu!csus.edu!sfsuvax1.sfsu.edu!kschang From: kschang@sfsuvax1.sfsu.edu (Kuo-Sheng Chang) Newsgroups: comp.graphics,alt.graphics,alt.msdos.programmer,comp.programming,rec.games.programmer Subject: Re: Help with Grapics Techniques Message-ID: <1993Feb5.210700.5489@csus.edu> Date: 5 Feb 93 21:07:00 GMT Article-I.D.: csus.1993Feb5.210700.5489 References: <1993Feb5.023217.24145@scammell.ecos.tne.oz.au> Sender: news@csus.edu Organization: San Francisco State University Lines: 31 In article <1993Feb5.023217.24145@scammell.ecos.tne.oz.au> pcm@scammell.ecos.tne.oz.au (Peter Murray) writes: > >What about Comanche? Apparantly this game is generating terrain >in real time based on terrain maps, although the various >helicopters and tanks seem to be of the pre-drawn bitmap >type (as in Wing Commander). > >I have seen the question brought up a number of times in this group >regarding the techniques used in Wolfenstein and Commanche but >have never seen a satisfactory answer, e.g. what optimisation >techniques are they using to get the speed and what (assembler) >tricks they are using. I don't have any sources, but I managed to get into the Wolf3D's debug mode and found that their walls are ALL predrawn. It is not inconceivable that they preloaded the bitmaps for the walls and did 3-D projection of them on the fly. After all, as you move around, you can notice the seams in the tiles that makes up the walls. Squashing a bitmap is not that hard, esp when Wolf used oversized pixels. Terrain in Commanche, while looks amazing from flight-view, is actually not as impressive as we are led to believe. Upon closer view, the terrain is actually MORE tiles (though they blend together quite nicely). My guess is the program have data for different elevations and used that to determine which view of the tile to display. That's why you need 4 megs: so it can put together all those teeny pieces of bitmap before it shows you! This is obviously a total guess on my part, and may NOT be accurate. Any one from NovaLogic reading this? :-) --Kasey Chang