Quake BSP/PVS/Lightmap Builder

From the README written by John Carmack: This is the source for the three utilties that a .map file passes through before it becomes a finished .bsp file. I went through 28 iterations of the output format, and eight major rewrites of the code during the development, so there are probably a few code skeletons lying around.

I have compiled this code on nextstep, digital unix, irix, and nt, so it should be easily portable to any environment you choose. The digital unix version is multi-threaded to run on SMP systems. The NT version has not been tested very well.

qbsp : 
   this does the CSG operations on the brushes, fills away the
   outside of the map, generates a bsp and all of the polygons
   required for drawing, bsps for the clipping hulls, and copies
   all of the textures that are actually used out of the editor's
   wadfiles into the output bsp files.
   In hindsight, I wish I had split this program up a little more.
   There is an awful lot of code in it.

   qbsp generates these files:
      map.bsp		- the output map file to be read by quake or light/vis
      map.prt		- the portal file to be read by vis
      map.h1
      map.h2		- hull files written by forked processes.
                  Can be safely deleted.
      map.pts		- pointfile for tracing leaks in the level.
    
   In quake, you can type "pointfile" and it will leave a trail of
      dots from the outside to the first entity it ran into. Qbsp
      will refuse to generate a .prt file if the map is not completely
      sealed in.
			It is possible to vis an unsealed map, but it could take hours.
			Seal it up first.

light : 
  
   this takes the .bsp file generated by qbsp and does light casting
   from all of the light objects in the map.  Normally, it takes one
   light sample for each lightmap point, but the "-extra" parameter
   causes it to take four samples (and four times as long to run) and
   average them.  The lighting model used has little theoretical
   grounding (it has linear fallof, for instance), it was just tweaked
   until it looked good.

vis : 

   this takes the .prt file generated by qbsp, along with the .bsp 
   file, and generates a compressed bit array of the potentially
   visible set of each leaf.  This can take a very long time, depending
   on the input data.  The time is related to the number of portals
   off of each leaf.  A simple wolfenstein like level would have leafs
   with an average of only two portals from each leaf, and would vis
   very fast.  The worst case for vising would be a stadium environment,
   where you have a huge area with lots of things sticking out of the
   ground but not contacting other major occluders.  A single large
   room like that can take more time to process than an entire level
   made up of more densly occluded areas.


These utilities are very processor intensive.  Here at id, we share a
four processor alpha 4/275 for all map processing.  The final levels
in quake take about 15-20 minutes each to fully process, which means
that on a pentium 90 it would probably take about 2 1/2 hours.
Obviously not something you want to do very often.

You can make a .bsp file that can be run by quake with just the qbsp
program.  When it is loaded into the game, it will be fullbright, and
will allways draw the entire level (slow).  This is fine for developing
small tests, but different methodologies are required for developing
full size levels.

Our map editor lets us region an active work area, so construction is
usually done a couple rooms at a time, allowing qbsp + light to be
done quickly, and not requiring a vis at all.

Once a level has been completed, entities (monsters, items, etc) can
be moved or changed without reprocessing the entire level by running
qbsp with the -onlyents parameter.  This does not work for doors,
triggers, etc that are composed of brushes.  One of these days I will
get around to coding that...

Our map editor also has a "relight" option, which does a qbsp -onlyents,
then a light, while still leaving the vis information intact.


There are oportunities for network level parallization with some recoding.
Qbsp uses fork level parallization to utilize up to three processors,
and it would be trivial to change to allow it to be run on three computers.
Light is embarassingly parallel, and can be divided arbitrarily. Vis is 
highly parallel, but it takes some advantage of order of completion in
the serial case, so scaling is not quite linear.
 
There are certainly major algorithmic optimzations that can be made to
the code to improve the processing speed.

The vis speed for bad cases could be improved dramatically by growing
together leafs that have large numbers of portals into larger pseudo-leafs.

The ray casting method I used in light is of debatable speed for the
normal sampling level, but at the -extra sampling level it would almost
certainly be faster to process an entire view from each light, rather
than each light to each sample point.  That would be a total rewrite,
though, not a simple patch.

I use doubles everywhere in these programs.  At one point this was
necessary to avoid some problems, but I tightened up the numerics in
the program since then, and it may not be needed any more. I don't
recall the change being a huge speed lose, in any case.

home qdev qdev dread rsc qdev doom license web
home dEr95 r3D dread netrsc quake doom legal web
Author: B., email to bernd@nero.uni-bonn.de, with public PGP key
Copyright (©) 1995, 1996 by author. All rights reserved.
Source: $Id: index.html,v 1.1 1996/07/22 10:27:04 b1 Exp $