qbsp_29.txt

version 29 chnages:  the lighting calculations were changed to allow the overbrighting added in quake 1.0, and some restrictions on maximum face count in qbsp were removed.  A little memory was also saved in qbsp.

=============================================================================

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 can 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 id 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 psuedo-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.



John Carmack
Id Software