Fabien Sanglard's Website

June 8, 2012

Doom3 Source Code Review: Dmap (Part 2 of 6) >>

Like every id Software engine the maps generated by the design team were heavily preprocessed by a tool in order to increase performances at runtime.

For idTech4 the tool is named dmap and its goal is to read a soup of polyhedron from a .map file, identify areas connected by inter-area-portals and save those in a .proc file.

The goal is to power the runtime portal system of doom3.exe. There is an amazing paper from 1992 by Seth Teller: "Visibility Computations in Densely Occluded Polyhedral environment" : It describes well how idTech4 works with many explanatory drawings.

The editor

Designers produce level maps via CSG (Constructive Solid Geometry): They use polyhedrons that usually have 6 faces and place them on the map.
Those blocks are called brushes and the following drawing shows 8 brushes used (I use the same map to explain each step in dmap).

A designer may have a good idea of what is "inside" (on the left) but dmap receives a brushes soup where nothing is inside and nothing is outside (on the right).

Designer view Dmap view as brushes are read from the .map file.

A brush is not defined via faces but by its planes. It may seem very inefficient to give planes instead of faces but it is very helpful later when checking if two faces are on the same plane. There is no inside or outside since the planes are not oriented "consistently". The planes orientation can point outside or inside the volume indifferently.

Code overview

Dmap source code is very well commented, just look at the amount of green: There is more comments than code !

                                                                      
                                                                      
     bool ProcessModel( uEntity_t *e, bool floodFill ) {
     
     bspface_t        *faces;
     
     // build a bsp tree using all of the sides
     // of all of the structural brushes
     faces = MakeStructuralBspFaceList ( e->primitives );
     e->tree = FaceBSP( faces );
     
     // create portals at every leaf intersection
     // to allow flood filling
     MakeTreePortals( e->tree );
     
     // classify the leafs as opaque or areaportal
     FilterBrushesIntoTree( e );
     
     // see if the bsp is completely enclosed
     if ( floodFill && !dmapGlobals.noFlood ) {
       if ( FloodEntities( e->tree ) ) {
         // set the outside leafs to opaque
         FillOutside( e );
       } else {
         common->Printf ( "**********************\n" );
         common->Warning( "******* leaked *******" );
         common->Printf ( "**********************\n" );
         LeakFile( e->tree );
         // bail out here.  If someone really wants to
         // process a map that leaks, they should use
         // -noFlood
         return false;
       }
     }
     
     // get minimum convex hulls for each visible side
     // this must be done before creating area portals,
     // because the visible hull is used as the portal
     ClipSidesByTree( e );
     
     // determine areas before clipping tris into the
     // tree, so tris will never cross area boundaries
     FloodAreas( e );
     
     // we now have a BSP tree with solid and non-solid leafs marked with areas
     // all primitives will now be clipped into this, throwing away
     // fragments in the solid areas
     PutPrimitivesInAreas( e );
     
     // now build shadow volumes for the lights and split
     // the optimize lists by the light beam trees
     // so there won't be unneeded overdraw in the static
     // case
     Prelight( e );
     
     // optimizing is a superset of fixing tjunctions
     if ( !dmapGlobals.noOptimize ) {
        OptimizeEntity( e );
     } else  if ( !dmapGlobals.noTJunc ) {
        FixEntityTjunctions( e );
     }
     
     // now fix t junctions across areas
     FixGlobalTjunctions( e );
     
     return true;
     }

0. Loading the level geometry

A .map file is a list of entities. The level is the first entity in the file and has a "worldspawn" class. An entity contains a list of primitives that are almost always brushes. The remaining entities are lights, monsters, player spawning location, weapons etc ...


   Version 2
                            
    // entity 0
    {
        "classname" "worldspawn"
        // primitive 0
        {
            brushDef3
            {
                ( 0 0 -1 -272 ) ( ( 0.0078125 0 -8.5 ) ( 0 0.03125 -16 ) ) "textures/base_wall/stelabwafer1" 0 0 0
                ( 0 0 1 -56   ) ( ( 0.0078125 0 -8.5 ) ( 0 0.03125 16  ) ) "textures/base_wall/stelabwafer1" 0 0 0
                ( 0 -1 0 -3776) ( ( 0.0078125 0 4    ) ( 0 0.03125 0   ) ) "textures/base_wall/stelabwafer1" 0 0 0
                ( -1 0 0 192  ) ( ( 0.0078125 0 8.5  ) ( 0 0.03125 0   ) ) "textures/base_wall/stelabwafer1" 0 0 0
                ( 0 1 0 3712  ) ( ( 0.006944  0 4.7  ) ( 0 0.034   1.90) ) "textures/base_wall/stelabwafer1" 0 0 0
                ( 1 0 0 -560  ) ( ( 0.0078125 0 -4   ) ( 0 0.03125 0   ) ) "textures/base_wall/stelabwafer1" 0 0 0
            }
        }
        // primitive 1
        {
           brushDef3
        }
        // primitive 2
        {
            brushDef3
        }        
    }    
    .
    .
    .
   // entity 37
   {
        "classname" "light"
        "name" "light_51585"
        "origin" "48 1972 -52"
        "texture" "lights/round_sin"
        "_color" "0.55 0.06 0.01"
        "light_radius" "32 32 32"
        "light_center" "1 3 -1"
   }

Each brush is described as a set of planes. The sides of a brush are called faces (also called windings) and each is obtained by clipping a plane with every other planes in the brush.

Note : During the loading phase a really neat and fast "Plane Hashing System" is used: idPlaneSet built on top of a idHashIndex it is really worth taking a look at it.

1. MakeStructuralBspFaceList & FaceBSP

The first step is to slice the map via Binary Space Partition. Every single non transparent faces in the map wil be used as splitting plane.

The heuristic to select a splitter is:

1 : If the map is more than 5000 units: Slice using an Axis Aligned Plane in the middle of the space. In the following drawing a 6000x6000 space is sliced three times.

2 : When there is no more parts bigger than 5000 units: Use the faces marked as "portal" (they have material textures/editor/visportal). In the following drawing the portal brushes are in blue.

3 : Finally use the remaining faces. Select the face that is collinear to the most other planes AND split the less faces ; Also try to favor axial splitters. The splitting planes are marked in red.

The process stops when no more faces are available: The BSP tree leaf all represent a convex subspace:

2. MakeTreePortals

The map is now divided into convex subspaces but those subspaces have no awareness of each other. The goal of this step is to connect each leaf to its neighbors by creating portals automatically. The idea is to start with six portals boundering the map: The connect "outside" to "inside" (the root of the BSP). Then for each nodes int the BSP: split each portal in the node, add the splitting plane as portal and recurse.

The original six portals are going to be split and propagated all the way down to the leafs. This is not as trivial as it seems since each time a node is split: Every portals it is connected to must also be split.

In the drawing on the left one portal is connecting two BSP sibling nodes. Upon following the left child its splitting plane cut the portal in two. We can see that the other node portals must also be updated so they don't connect to a sibling anymore but to its "nephews".

At the end of the process the six original portals have been split in hundreds of portals and new portals have been created on the splitting planes: Each leaf in the BSP has gained awareness of its neighbors via a linked list of portals connecting it to leafs sharing an edge:

3. FilterBrushesIntoTree

This step works like a game of Shape Sorter with the BSP being the board and the brushes being the shapes. Each brush is sent down the BSP in order to discover which leafs are opaque.

This work because of a well defined heuristic: If a brush is crossing a splitting plane a little but not more than EPSILON then it is not split. Instead it is sent all together on the plane side where all the other elements of the brush are.

Now "inside" and "outside" are starting to be visible.

A leaf hit by a brush is considered opaque (solid) and is hence marked accordingly.

4. FloodEntities & FillOutside

Using a player spawning entity a floodfill algorithm is triggered from each leaf. It mark leafs reachable by entities.

The final step FillOutside go through each leaf and if it is not reachable mark it as opaque.

We now have a level where each subspace is either reachable or opaque: Navigation via leaf portals can now be consistent by checking if the target leaf is opaque or not.

5. ClipSidesByTree

It is now time to discard useless parts of the brushes: Each original brush side is now sent down the BSP. If a side is within an opaque space then it is discarded. Otherwise it is added to the side's visibleHull list.

This result in a "skin" of the level, only visible parts are kept.

From this point only side's visibleHull are considered for the remaining operations.

6. FloodAreas

Now dmap group leafs together with area IDs: For each leaf a floodfilling algorithm is triggered. It tries to flow everywhere using portals associated to the leaf.

This is where the designer work is tremendously important: Areas can be identified only if visportals (the portal brushes mentioned in Step 1) were manually placed on the map. Without them dmap will identify only one area and the entire map will be sent to the GPU each frame.

The Floodfilling recursive algorithm is stopped only by areaportals and opaque nodes. In the following drawing an automatically generated portal (in red) will allow flood but a designer placed visportal (in blue, also called areaportal ) will stop it, making two areas:

At the end of the process each non opaque leaf belongs to an area and the inter-area-portals (in blue) have been identified.

7. PutPrimitivesInAreas

This step combines the areas identified in Step 6 and the visibleHull calculated in Step 5 in an other "Shape Sorter" game: This time the board is the areas and the shapes are the visibleHull.

An array of areas is allocated and each visibleHull of each brush is sent down the BSP: Surfaces are added to the area array at index areaIDs.

Note : Pretty clever, this step will also optimize entity spawning. If some entities are marked "func_static" they are instantiated now and associated to an area. This is a way to "melt" boxes, barrels,chairs into an area (also have its shadow volume pre-generated).

8. Prelight

For each static light dmap pre-calculate the shadow volumes geometry. Those volumes are later saved in the .proc as it. The only trick is that shadow volumes are saved with a name "_prelight_light" concatenated to the light ID so the engine can match the light from the .map file and the shadow volume from the .proc file:

 


      shadowModel { /* name = */ "_prelight_light_2900"

      /* numVerts = */ 24 /* noCaps = */ 72 /* noFrontCaps = */ 84 /* numIndexes = */ 96 /* planeBits = */ 5
   
     ( -1008 976 183.125 ) ( -1008 976 183.125 ) ( -1013.34375 976 184 ) ( -1013.34375 976 184 ) ( -1010 978 184 ) 
     ( -1008 976 184 ) ( -1013.34375 976 168 ) ( -1013.34375 976 168 ) ( -1008 976 168.875 ) ( -1008 976 168.875 ) 
     ( -1010 978 168 ) ( -1008 976 167.3043518066 ) ( -1008 976 183.125 ) ( -1008 976 183.125 ) ( -1010 978 184 ) 
     ( -1008 976 184 ) ( -1008 981.34375 184 ) ( -1008 981.34375 184 ) ( -1008 981.34375 168 ) ( -1008 981.34375 168 ) 
     ( -1010 978 168 ) ( -1008 976 167.3043518066 ) ( -1008 976 168.875 ) ( -1008 976 168.875 ) 
  
     4 0 1 4 1 5 2 4 3 4 5 3 0 2 1 2 3 1 
     8 10 11 8 11 9 6 8 7 8 9 7 10 6 7 10 7 11 
     14 13 12 14 15 13 16 12 13 16 13 17 14 16 15 16 17 15 
     22 21 20 22 23 21 22 18 19 22 19 23 18 20 21 18 21 19 
     1 3 5 7 9 11 13 15 17 19 21 23 4 2 0 10 8 6 
     16 14 12 22 20 18 
     }

9. FixGlobalTjunctions

Fixing TJunction is usually important in order to avoid visual artefacts but this is even more important in idTech4: The geometry is also used to generated the shadow while writing to the stencil buffer. T-Junctions are twice as annoying.

10. Write output

In the end all this preprocessing is saved to a .proc file:

For each area a set of surface faces grouped by material.
The BSP Tree with areaID for leafs.
Inter-area-portals winding.
Shadow Volumes.

History

Many code segments from dmap feature similarities with code found in the preprocessing tools of Quake (qbsp.exe), Quake 2 (q2bsp.exe) or Quake (q3bsp.exe). That's because the Potentially visible Set was generated via a temporary portal system:

qbsp.exe read a .map and generated a .prt file that contained connectivity information between leafs in the BSP: Portals (exactly like Step2. MakeTreePortals).
vis.exe used the .prt as input. For each leaf:

fillFlood into connected leaf using portals.
Before flooding into a leaf: Test for visibility by clipping the next portal with the two previous portal anti view frustrum (many people claimed that visibility was done by casting thousands of rays but this is a myth that many still believe nowadays).

A drawing is always better: Let's say qbsp.exe identified 6 leafs connected by portals and now vis.exe is running to generate the PVS. This process will be executed for each leaf but this example focus exclusively on leaf 1.

Since a leaf is always visible by itself the initial PVS for leaf 1 is as follow:

Leaf ID 1 2 3 4 5 6

Bit vector (PVS for leaf 1) 1 ? ? ? ? ?

The floodFilling algorithm starts: The rule is that as long as we don't have two portals in the path, the leaf is considered visible from the starting point. This means we reach leaf3 with the following PVS:

Leaf ID 1 2 3 4 5 6

Bit vector (PVS for leaf 1) 1 1 1 ? ? ?

Once in the leaf3 we can actually start checking for visibility:

By taking two points form the portal n-2 and the portal n-1 we can generate clipping planes and test if the next portals are potentially visible.

In the drawing the can see that portals leading to leaf 4 and 6 will fail the tests while portal toward 5 will succeed. The floorFilling algorithm will then recurse to leaf6. In the end the PVS for leaf 1 will be:

Leaf ID 1 2 3 4 5 6

Bit vector (PVS for leaf 1) 1 1 1 0 1 0

In idTech4 the PVS is not generated, instead the portal data is conserved. The visibility of each area is computed at runtime by projecting the portal windings into screen space and clipping them against each others.

Trivia : Michael Abrash explained this entire process in 10 seconds and a sharpie in this excellent video from GDC Vault:

Designer view	`Dmap` view as brushes are read from the `.map` file.