The CDPD Public Domain Collection for CDTV 3/CDPDIII.bin/pd/programming/assembler/thesource/volume4/source/vectors/bmaps.lha/3dbmaps.txt

Text File | 1993-02-17 | 25.4 KB | 591 lines

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: [e-mail] (Dave Stampe-Psy+Eng)
Subject: Re: Wolfstein 3D graphics : HOW ??
Message-ID: <[e-mail]>
Organization: University of Waterloo
References: <[e-mail]>
Date: Thu, 14 May 1992 14:05:42 GMT
Lines: 44

In article <[e-mail]> [e-mail] (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?         | [e-mail] |
__________________________________________________________________________



Article: 6921 of rec.games.programmer
Newsgroups: rec.games.programmer
Path: dg-rtp!psinntp!uunet!sun-barr!cs.utexas.edu!utgpu!watserv1!dstamp
From: [e-mail] (Dave Stampe-Psy+Eng)
Subject: Re: Wolfstein 3D graphics : HOW ??
Message-ID: <[e-mail]>
Organization: University of Waterloo
References: <[e-mail]>
Date: Sun, 17 May 1992 13:47:00 GMT
Lines: 27

[e-mail] (Ross Ridge) writes:
>[e-mail] (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?         | [e-mail] |
__________________________________________________________________________



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: [e-mail] (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: <[e-mail]>
Date: 17 May 92 19:17:18 GMT
References: <[e-mail]>
Sender: [e-mail]
Organization: Univ. of Florida CIS Dept.
Lines: 64
Nntp-Posting-Host: reef.cis.ufl.edu

In article <[e-mail]> [e-mail] (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
[e-mail]


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: [e-mail] (Michael O'Reilly)
Subject: Re: Wolfstein 3D graphics : HOW ??
Message-ID: <[e-mail]>
Sender: [e-mail] (USENET News System)
Nntp-Posting-Host: tartarus.uwa.edu.au
Organization: University of Western Australia
References: <[e-mail]>
Date: Mon, 18 May 1992 08:36:07 GMT
Lines: 18

[e-mail] (Ross Ridge) writes:
: [e-mail] (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]
: [e-mail]                            /()\/()/
: 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: [e-mail] (Dave Stampe-Psy+Eng)
Subject: Re: Wolfstein 3D graphics : HOW ??
Message-ID: <[e-mail]>
Organization: University of Waterloo
References: <[e-mail]>
Date: Mon, 18 May 1992 13:48:56 GMT
Lines: 38

 [e-mail] (Michael O'Reilly) writes:
>[e-mail] (Ross Ridge) writes:
>: [e-mail] (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?         | [e-mail] |
__________________________________________________________________________



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: [e-mail] (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: <[e-mail]>
Date: 18 May 92 10:34:39 GMT
Sender: [e-mail]
Followup-To: rec.games.misc
Organization: University of Missouri - Rolla
Lines: 38
Originator: [e-mail]


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:  [e-mail]                 |
|  Computer Science Dept.  |    Bitnet:  [e-mail]   |
| 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: [e-mail] (Gary McTaggart)
Newsgroups: rec.games.programmer
Subject: Here's some C code for Wolfenstein-type graphics
Message-ID: <[e-mail]>
Date: 19 May 92 00:57:52 GMT
Sender: [e-mail]
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
[e-mail]


------------------------------------------------------------------------------

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: [e-mail] (Dave Stampe-Psy+Eng)
Subject: Re: Wolfstein 3D graphics : HOW ??
Message-ID: <[e-mail]>
Organization: University of Waterloo
References: watserv1.waterloo.edu> <[e-mail]>
Date: Tue, 19 May 1992 22:18:20 GMT
Lines: 44

 [e-mail] (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?         | [e-mail] |
__________________________________________________________________________



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: [e-mail] (Chris Trimble)
Subject: Re: Help with Grapics Techniques
References: <[e-mail]>
Message-ID: <[e-mail]>
Sender: [e-mail] (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! <Tears up picture of Elvis>
Beckman Institute Systems Services  -  [e-mail]  -  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: [e-mail] (Kuo-Sheng Chang)
Newsgroups: comp.graphics,alt.graphics,alt.msdos.programmer,comp.programming,rec.games.programmer
Subject: Re: Help with Grapics Techniques
Message-ID: <[e-mail]>
Date: 5 Feb 93 21:07:00 GMT
Article-I.D.: csus.1993Feb5.210700.5489
References: <[e-mail]> <[e-mail]>
Sender: [e-mail]
Organization: San Francisco State University
Lines: 31

In article <[e-mail]> [e-mail] (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