16/PCGPE10/DOOM.TXT

   1 \r
   2 ******************************************************************************\r
   3 *                       'Doom' 3D Engine techniques                          *\r
   4 ******************************************************************************\r
   5 By Brian 'Neuromancer' Marshall\r
   6 (Email: brianm@vissci.demon.co.uk)\r
   7 \r
   8         This document is submitted subject to certain conditions:\r
   9 \r
  10 1. This Document is not in any way related to Id Software, and is \r
  11    not meant to be representive of their techniques : it is based\r
  12    upon my own investigations of a realtime 3d engine that produces\r
  13    a screen display similar to 'Doom' by Id software.\r
  14 \r
  15 2. I take no responsibility for any damange to data or computer equipment\r
  16    caused by attempts to implement these algorithms.\r
  17 \r
  18 3. Although I have made every attempt to ensure that this document is error\r
  19    free i take no responsability for any errors it may contain.\r
  20 \r
  21 4. Anyone is free to use this information as they wish, however I would\r
  22    appreciate being credited if the information has been useful.\r
  23 \r
  24 5. I take no responsability for the spelling or grammar.\r
  25    (My written english is none too good...so I won't take offence\r
  26     at any corrections: I am a programmer not a writer...)\r
  27 \r
  28         Right now that that little lot is out of the way I will start this\r
  29 document proper....\r
  30 \r
  31 1:  Definition of Terms\r
  32 ======================\r
  33 \r
  34         Throughout this document I will be making use of many graphical terms\r
  35 using my understanding of them as they apply to this algorithm. I will\r
  36 explain all the terms below. Feel free to skip this part....\r
  37 \r
  38 Texture:\r
  39         A texture for the purpose of this is a square image.\r
  40 \r
  41 U and V:\r
  42         U and V are the equivelants of x and y but are in texture space.\r
  43 ie They are the the two axies of the two dimensional texture.\r
  44 \r
  45 Screen:\r
  46         For my purposes 'screen' is the window we wish to fill: it doesn't\r
  47 have to be the whole screen.\r
  48 \r
  49 Affine Mapping:\r
  50         A affine mapping is a texture map where the texture is sampled\r
  51 in a linear fashion in both U and V.\r
  52 \r
  53 Biquadratic Mapping:\r
  54         A biquadratic mapping is a mapping where the texture is sampled\r
  55 along a curve in both U and V that approximates the perspective transform.\r
  56 This gives almost proper forshortening.\r
  57 \r
  58 \r
  59 Projective Mapping:\r
  60         A projective mapping is a mapping where a changing homogenous\r
  61 coordinated is added to the texture coordinateds to give (U,V,W) and\r
  62 a division is performed at every pixel. This is the mathematically and\r
  63 visual correct for of texture mapping for the square to quadrilateral\r
  64 mappings we are using.\r
  65         (As an aside it is possible to do a projective mapping without\r
  66 the divide (or 3 multiplies) but that is totally unrelated to the matter\r
  67 in hand...)\r
  68 \r
  69 Ray Casting:\r
  70         Ray Casting in this context is back-firing 'rays' along a two\r
  71 dinesional map. The rays do however follow heights... more on that later\r
  72 \r
  73 Sprite:\r
  74         A Sprite is a bitmap that is either a monster or an object. To\r
  75 put it another way it is anything that is not made out of wall or\r
  76 floor sectins.\r
  77 \r
  78 Sprite Scaling:\r
  79         By this I mean scaling a bitmap in either x or y or both.\r
  80 \r
  81 Right... Now thats over with onto the foundation:\r
  82 \r
  83 2:   Two Dimensional Ray Casting Techniques\r
  84 ===========================================\r
  85 \r
  86         In order to make this accessible to anyone I will start by\r
  87 explaining 2d raycasting as used in Wolfenstein 3d style games.\r
  88 \r
  89   2.1: Wolfenstien 3D Style Techniques...\r
  90   =======================================\r
  91 \r
  92           Wolfenstein 3d was a game that rocked the world (well me anyway!).\r
  93   It used a technique where you fire a ray accross a 2d grid based map to\r
  94   find all its walls and objects. The walls were then drawn vertically\r
  95   using sprite scaling techniques to simulate texture mapping.\r
  96 \r
  97           The tracing accross the map looked something like this;\r
  98 \r
  99 \r
 100         =============================================\r
 101         =   =   =   =   =   =  /=   =   =   =   =   =\r
 102         =   =   =   =   =   = / =   =   =   =   =   =\r
 103         =   =   =   =   =   =/  =   =   =   =   =   =\r
 104         ====================/========================\r
 105         =   =   =   =   =  /=   =   =   =   =   =   =\r
 106         =   =   =   =   = / =   =   =   =   =   =   =\r
 107         =   =   =   =   =/  =   =   =   =   =   =   =\r
 108         ================/============================\r
 109         =   =   =   =  /#   =   =   =   =   =   =   =\r
 110         =   =   =   = / #   =   =   =   =   =   =   =\r
 111         =   =   =   =/  #   =   =   =   =   =   =   =\r
 112         ============/===#########====================\r
 113         =   =   =  /=   =   =   #   =   =   =   =   =\r
 114         =   =   = / =   =   =   #   =   =   =   =   =\r
 115         =   =   =/  =   =   =   #   =   =   =   =   =\r
 116         ========/===============#====================\r
 117         =   =  /=   =   =   =   #   =   =   =   =   =\r
 118         =   = P =   =   =   =   #   =   =   =   =   =\r
 119         =   =  \=   =   =   =   #   =   =   =   =   =\r
 120         ========\===============#====================\r
 121         =   =   =\  =   =   =   #   =   =   =   =   =\r
 122         =   =   = \ =   =   =   #   =   =   =   =   =\r
 123         =   =   =  \=   =   =   #   =   =   =   =   =\r
 124         ============\=======#####====================\r
 125         =   =   =   =\  =   #   =   =   =   =   =   =\r
 126         =   =   =   = \ =   #   =   =   =   =   =   =\r
 127         =   =   =   =  \=   #   =   =   =   =   =   =\r
 128         ================\===#========================\r
 129         =   =   =   =   =\  #   =   =   =   =   =   =\r
 130         =   =   =   =   = \ #   =   =   =   =   =   =\r
 131         =   =   =   =   =  \#   =   =   =   =   =   =\r
 132         =============================================\r
 133 \r
 134         (#'s are walls, = is the grid....)\r
 135 \r
 136         This is just a case of firing a ray for each vertical\r
 137   line on the screen. This ray is traced accross the map to\r
 138   see where it crosses a grid boundry. Where it crosses a\r
 139   boundry you cjeck to see if there is a wall there we see how\r
 140   far away it it and draw a scaled vertical line from the texture\r
 141   on screen. The line we draw is selected from the texture by\r
 142   seeing where the line has intersected on the side of the square it\r
 143   hit.\r
 144         This is repeated with a ray for each vertical line on the\r
 145   screen that we wish to display.\r
 146         This is a very quick explaination of how it works missing\r
 147   out how the sprites are handled. If you want a more detailed \r
 148   explaination then I suggest getting acksrc.zip from\r
 149   ftp.funet.fi in /pub/msdos/games/programming\r
 150 \r
 151         This is someone's source for a Wolfenstien engine written\r
 152   in Borland C and Assembly language on the Pc.\r
 153         Its is not the fastest or best but has good documentation\r
 154   and solves similiar sprite probelms, distance probelms and has\r
 155   some much better explaination of the tracing technique tahn I have\r
 156   put here. I recommend to everyone interested taht you get a copy\r
 157   and have a thorough play around with it.\r
 158   (Even if you don't have a Pc: Everything but the drawing and video\r
 159    mode setting is done in 'C' so it should not be too hard to port\r
 160    ....)\r
 161 \r
 162  \r
 163   2.2 Ray Casting in the Doom Environment\r
 164   =======================================\r
 165 \r
 166         When you look at a screen from Doom you see floors, steps\r
 167   walls and lots of other trappings.\r
 168         You look out of windows and accross courtyards and you\r
 169   say WOW! what a great 3d game!!\r
 170         Then you fire your gun a baddie who's in line with you but\r
 171   above you and bang! he's a corpse.\r
 172         Then you climb up to the level where the corpse is and look\r
 173   out the window to where you were and you say Gosh! a 3d game!!\r
 174 \r
 175         Hmmm....\r
 176 \r
 177         Stop gawping at the graphics for a minute and look at the map\r
 178   screen. Nice line vectors. But isn't the map a bit simple???\r
 179         Notice how depite colours showing you that there are different\r
 180   heights. Then notice that despite the fact that there is NEVER a\r
 181   place where you can exist on two different levels. Smelling a little\r
 182   2d yet???\r
 183         Look where there are bridges (or sort of bridges) : managed to\r
 184   see under them yet??\r
 185 \r
 186         The whole point to this is that Doom is a 2D games just like\r
 187   its ancestor Wolfenstein but it has rather more advanced raycasting\r
 188   which does a very nice job of fooling the player into thinking its a\r
 189   3d game that shifting loads of polygons and back-culling, depth\r
 190   sorting etc... \r
 191 \r
 192         Right the explaination of how you turn a 2d map into the 3d\r
 193   doom screen is complex so if you are having difficulty try reading\r
 194   it a few times and if all else fails mail me....\r
 195 \r
 196 \r
 197   2.3 What is actually done!\r
 198   ==========================\r
 199 \r
 200         Right to start with the raycasting is started in the same\r
 201   way as Wolfenstien. That is find out where the player is in the 2d\r
 202   map and get a ray setup for the first vertical line on the screen.\r
 203 \r
 204         Now we have an extra stage from the Wolfenstein I described\r
 205   whcih involves a data srtucture that we will use later to actually\r
 206   draw the screen.\r
 207 \r
 208         In this data structure we start the ray off as at the bottom\r
 209   of the screen. This is shown in the diagram below;\r
 210 \r
 211         =================================\r
 212         =                               =\r
 213         =                               =\r
 214         =                               =\r
 215         =                               =\r
 216         =                               =\r
 217         =                               =\r
 218         =                               =\r
 219         =                               =\r
 220         =                               =\r
 221         =                               =\r
 222         =                               =\r
 223         =                               =\r
 224         =                               =\r
 225         =                               =\r
 226         =                               =\r
 227         =                               =\r
 228         =*                              =\r
 229         =================================\r
 230 \r
 231 \r
 232         Where the '=' show the boundry of the screen and '*' is the virtual\r
 233   position of the ray.\r
 234 \r
 235         Note: the Data structure is really two structures:\r
 236         One which is a set of list for each vertical 'scanline' and\r
 237         One which is a corresponding list for horizontal scanlines.\r
 238 \r
 239         Now we start tracing the ray. We skip accross the 2d map until\r
 240   we hit something interesting. By something interesting I mean something\r
 241   that is an actual wall or florr section edge.\r
 242         Right we have hit the edge of either a floor or wall section.\r
 243   We have several things to do know. These are;\r
 244 \r
 245         If it was a wall we hit:\r
 246 \r
 247   1: Find out how 'high' of screen this section of wall should be\r
 248      due to the distance it is accross the 2d map.\r
 249   2: Find out at what 'virtual height' it is: This is so that we can see\r
 250      where in the vertical scanline in comes for testing where to insert\r
 251      it and for clipping it.\r
 252   3: Test in our structure to see if you draw it or not.\r
 253      (This is done so that you can look through windows : how this works\r
 254       will become apparent later.)\r
 255   4: If any of the wall segment is visible then we find out where along\r
 256      the texture we have hit it and write into the structure the area of\r
 257      the screen it takes up as well as the texture, the point where we\r
 258      have hit the texture and the size it should be on screen. (This is\r
 259      so that we can draw it correctly even if the whole span is not on\r
 260      screen.\r
 261 \r
 262 \r
 263         If it was a floor section that we hit:\r
 264 \r
 265   1: Find out where on the vertical line we are working the floor section\r
 266      that the ray has hit is. (We know the height of the the floor in the\r
 267      virtual map (2d) and we know the height of the player and the distance\r
 268      of the floor square from the player so it is easy).\r
 269      As a side effect of this we now know the U,V value where the ray has\r
 270      hit the floor square.\r
 271 \r
 272   2: Trace Accross the floor square till we hit the far edge of the floor\r
 273      square : we then workout where this is on the vertical scanline using\r
 274      the same technique as above. We now know the vertical span of the\r
 275      floor section, and where on the span it is.\r
 276 \r
 277   3: We check to see if the span is visible on the vertical span.\r
 278      If it is or part of it is used then we mark that part of the vertical\r
 279      scanline as used.\r
 280      We also have to make use of the horizontal buffer I mentioned. We\r
 281      insert into this in 2 places. The first is the x coordinate of where\r
 282      we hit the floor square into the y line where we where on the screen.\r
 283      Phew got that bit?? We also insert here the U,V value which we knew \r
 284      from the tracing. (I told you we'd need it later....)                                                                \r
 285 \r
 286 \r
 287         As you can see there's a little more to hiting a floor segment than\r
 288 a wall segment. Also note that a you exit a floor segment you may also hit\r
 289 a wall segment.\r
 290 \r
 291         Tracing the individual ray is continued until we hit a special kind\r
 292 of wall. This wall is marked as a wall that connects to the ceiling.\r
 293 This is one place to stop tracing this ray. However we can stop tracing early\r
 294 if we have found enough to fill the whole vertical scanline then we can stop\r
 295 whenevr we have done this.\r
 296 \r
 297         Next come a trick. I said we were tracing along a 2d map. Well I\r
 298 lied a bit. There are (In my implementation at least..) TWO 2d maps. One is\r
 299 basically from the floor along including all the 'floor' walls and everything\r
 300 up to and including the walls that join onto the ceiling. The other map\r
 301 is basically the ceiling (with anything coming down from the ceiling on it\r
 302 if you are doing this: this makes life a little more complex as I'll explain\r
 303 below..)\r
 304         Now when we have traced along the bottom map and hit a wall that \r
 305 connects to the ceiling then we go back and trace along the ceiling from\r
 306 the start to fill in the gaps. There is a problem with this however.\r
 307 The problem is when you have things like a monolith or something else built\r
 308 out of walls jutting down from the ceiling. you have to decide whether to\r
 309 draw it or draw whatever was already in the scanline structure. This means\r
 310 either storing extra information in the buffer ie z coordinates or tracing\r
 311 along both the ceiling and floor at the same time.... for most people I would\r
 312 suggest just not having anything jutting down from the ceiling.\r
 313         Also you could trace backwards instead of starting a new ray. This \r
 314 would be fasterfor many cases as you wouldn't be tracing through lots\r
 315 of floor squares that aren't on screen. By tracing backwards you can keep\r
 316 going up the vertical scanline and you know that you are on the screen. As\r
 317 soon as something goes off the top of the screen you can handle that and then\r
 318 stop tracing.\r
 319 \r
 320         Phew. has everyone got that???\r
 321 \r
 322         Now we just go back and fire rays up the rest of the vertical\r
 323 scanlines. Easy!!???\r
 324 \r
 325         At the end of this lot we have the necessary data in the two buffers\r
 326 to go back and draw the screen background.\r
 327 (There is one more thing done while tracing but I'll explain that later...)\r
 328 \r
 329 \r
 330         Oh... one other thing... you have may want to change the raycasting\r
 331 a bit to subdivide the map... it helps with speed.\r
 332         And don't forget the added complexity that walls aren't all at\r
 333 90 degrees to each other...\r
 334 \r
 335 3: Drawing the walls and Why it works!!\r
 336 =======================================\r
 337 \r
 338         If you are familiar with Wolfenstein then please still read this\r
 339 as it is esential background to understanding the floor routine.\r
 340 \r
 341 \r
 342         As all of you probably know the walls are drawn by scaling the line\r
 343 of the texture to the correct size for the screen. The information in the\r
 344 vertical buffer makes this easy. What you probably don't know is why this\r
 345 creates texture mapping that is good enough to fool us.\r
 346 \r
 347         The wall function is a Affine texture mapping. (well almost)\r
 348 Now affine texture mappings look abysmal unless you do quite a lot of\r
 349 subdivision (The amount needed varies according to the angle the projected\r
 350 square is at.). So why does the Doom technique work??\r
 351 \r
 352         Well when we traced the rays we found out exactly where along the\r
 353 side of the square we hit we were in relation to the width of the texture.\r
 354 This means that the top and bottom pixels of the scaled wall piece are\r
 355 calculated correctly. This means that we have effecively subdivided the\r
 356 texture along vertical scanlines and as the effective subdidvisons are\r
 357 calculated exactly with proper forshortening as a result of the tracing.\r
 358 So the ray casting has made the texture mapping easy for us.\r
 359         (We have enough subdivision by this scanline effect as the wall\r
 360 only rotates about one axis and we have proper foreshortening.)\r
 361 \r
 362         This knowlege helps us understand how to do the floors and why\r
 363 that works.\r
 364 \r
 365         We can now draw all the wall segments by just looking at the buffer\r
 366 and drawing the parts marked as walls.(Skiping where we put in the bits used\r
 367 by the floor/ceiling bits: we draw them later.)\r
 368 \r
 369 4:  Drawing the Floor/Ceiling and why it works!\r
 370 ===============================================\r
 371 \r
 372         If you have grasped why the walls work then you have just about\r
 373 won for the floors.\r
 374         We have the information needed to draw the floors from the horizontal\r
 375 buffer.\r
 376         All we have to do is look at the horizontal spans in the buffer\r
 377 and draw them in all.\r
 378         Each of these spans has 2 end coordinates for which we have\r
 379 exact texture coorinates. This tells us which line across the texture\r
 380 we have to step along to do an Affine or linear mapping.\r
 381         This is shown below;\r
 382 \r
 383 \r
 384         =================================\r
 385         =                               =\r
 386         =                               =\r
 387         =                               =\r
 388         =                               = U1,V1 (exit)\r
 389         =                              **\r
 390         =                           *** =\r
 391         =                        ***    =\r
 392         =                     ***       =\r
 393         =                  ***          =\r
 394         =               ***             =\r
 395         =            ***                =\r
 396         =         ***                   =\r
 397         =       **                      =\r
 398         =     **                        =\r
 399         =   **                          =\r
 400         = **                            =\r
 401   U0,V0 **                              =\r
 402 (entry) =                               =\r
 403         =                               =\r
 404         =                               =\r
 405         =                               =\r
 406         =                               =\r
 407         =                               =\r
 408         =                               =\r
 409         =================================\r
 410 \r
 411 (apologies for the wonky line: it should be straight!!)\r
 412 \r
 413         Now...as the end coordinates are correct and the axis along\r
 414 which forshortening takes place is not involved (this is a fudge)\r
 415 we can step linearly along this line across the texture to approximate\r
 416 the mapping. (This is far easier than a proper texture map).\r
 417         This is effectivly a wall lying on its side which works as the\r
 418 texture coordinates at the ends of the span have been calculated correctly.\r
 419 This is a benefit of the raycasting we used to find everything.\r
 420         Easy huh??\r
 421 \r
 422 \r
 423 5: Sprites\r
 424 ==========\r
 425 \r
 426         The Sprites are really quite easy to do. The basic technique is the\r
 427 same as used in Wolfenstein 3d.\r
 428         This is done as follows:\r
 429 \r
 430 When you enter a 'square' on the floor map you test to see if there are\r
 431 any sprites in the square. If there are you flag that sprite as visible\r
 432 and add it to a list of visible sprites.\r
 433 \r
 434 When you have finished tracing and drawing the walls and floor you\r
 435 depth sort the sprites and draw them from the back to the front. (painters\r
 436 algorithm). The only complication in drawing them is that you have to check \r
 437 buffer that has the walls in, in order to clip the sprites correctly.\r
 438 \r
 439         (If you're interested in Doom you can occasionally see large \r
 440 explosions (ie BFG) slip partially behind a wall segment.)\r
 441 \r
 442         On possibly faster way of handling the sprites would be to mark\r
 443 them like wall segments as you find them in the buffer. The only (ONLY!)\r
 444 complication to this approach is that sprites can have holes in them. By\r
 445 this I mean things like the gap between an arm and a leg which should be \r
 446 the background colour.\r
 447 \r
 448 \r
 449 6: Lighting and Depth Cueing\r
 450 ============================\r
 451 \r
 452         Lighting and Depth Cueing fits nicely in with the way that we have\r
 453 prepared the screen ready for drawing.\r
 454         All we have to do is see how far away we are when we found either\r
 455 the floor or wall section and set the light level according to the distance.\r
 456         The other thing that is applied is a light level. This is taken from\r
 457 the map at the edges where you have hit something. As the map is 2D it is\r
 458 easy to manage lighting, flickering etc.\r
 459         For things like pools of light on the floor all you have to do\r
 460 is subdivide that patch of floor so that you can set the bit under the \r
 461 skylight to a lighter colour. Its also very easy to frig this for the\r
 462 lighting goggles.\r
 463 \r
 464 \r
 465 7: Controlling the Baddies\r
 466 ==========================\r
 467         \r
 468 \r
 469         This is pretty easy: all you have to think about is moving and\r
 470 reacting on a 2d map. the only complications are things like the monsters\r
 471 looking through windows and seeing a player but this all degenerates into\r
 472 a simple 2d problem. Things like deciding whether the player has been hit or\r
 473 has he/she hit a monster is just another case of firing a ray. (Or do it\r
 474 another way...)\r
 475 \r
 476 \r
 477 8: Where next???\r
 478 ================\r
 479 \r
 480         Thats all folks... hopefully a useful and intersting insight into\r
 481 my Doom engine works.\r
 482         As to the question where next... well I already have some enhancements\r
 483 to my Doom enigine and others are in the works...\r
 484 \r
 485 Some of what you may eventually see are:\r
 486 \r
 487         Proper lighting (I have done this already...its easier than you\r
 488                         think)\r
 489         Non-Vertical walls (i.e. Aliens style corridors...)\r
 490         Orgranic Walls (i.e. Curved like the Aliens nest...)\r
 491         Fractal Landscapes (This one is still very much a theory but how\r
 492                         about being able to go outside and walk up and down\r
 493                         hills etc??)\r
 494 \r
 495         If there are bits people are really shaky about I may post a new\r
 496 version of this... but I cannot get into implimentation issues as all\r
 497 implementation work is under copyright...\r
 498 \r
 499         By the way if anyone out there implements this I'd love to here\r
 500 how you get on...\r
 501 \r
 502         Anyone got any comments or any other interesting algorithms???\r
 503 \r
 504 Brian 'Neuromancer' Marshall         'When do graphics not look like graphics?\r
 505 ( Email: brianm@vissci.demon.co.uk )  :when we get it RIGHT.'\r