home *** CD-ROM | disk | FTP | other *** search
/ Collection of Hack-Phreak Scene Programs / cleanhpvac.zip / cleanhpvac / FAQSYS18.ZIP / FAQS.DAT / DOOM.TXT < prev    next >
Text File  |  1996-01-04  |  23KB  |  506 lines

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