SourceForge.net Logo

MAP3BSPC - TECHNICAL README



[.map files][Worldspawn][.bsp files][How does it work][Visibility algorithm][More Info?][Further reading][Main]


Note: This site hasnšt been updated since version 0.2. Since v0.3 is almost a complete rewrite, all the details presented here are no longer accurate. In general though this info is still relevant as an intro to bsp compilation.

.map files

The .map files store the level in a text format. This is the input format MAP3BSPC understands.

The levels are made up of entities. The .map file is basically a list of entities. Entities store everything that is found in the level, from the level infrastructure (walls, floors etc) to lights, healthpaks and weapons. An entity in the .map file looks like this:

{ 
  "classname" "entityname" 
  // entity data 
}

A line containing just "{" marks the start of an entity, and a line containing just "}"marks the end of the entity. The first line inside the entity contains the type declaration for the entity (its classname. In the example the name would be "entityname" without the quotes).

Also notice that comments can be inserted using the C++ //-style. The entity data uses the same format as the classname, in most cases (the only exception I've seen so far is the worldspawn entity. More on that a bit later.). So for example a light entity might look like this:

{ 
  "classname" "light" 
  "origin" "300 0 255" 
  "light" "200" 
  "_color" "255 0 0" 
} 

classname, origin, light and _color are the parameter names and the strings following them contain the values. Commas don't seem to be used in the .map format, the normal separator is space.

This is also the format in which the entities are stored in the BSP file entities lump, with the exception of worldspawn. The BSP compiler only really needs to parse the worldspawn and light entities. Others are only read and stored as is and then written into the BSP file.

Worldspawn

The most interesting entity is called "worldspawn", and it describes the level itself. Worldspawn is always the first entity in the file and must always be present. As far as I can tell worldspawn is also the only complex entity in the file. Worldspawn stores both the immobile objects (the level itself, which gets stored in a BSP tree in the BSP file) and also any models placed into the level (that can be moved around and get stored in the models lump in the BSP file). The models are also stored as entities that contain additional information, but the problem is that apparently the worldspawn format doesn't make any distinction between these the brushes that are part of worldspawn and those that are parts of the models two, but stores them both lumped together. But it doesn't really matter, I guess, since the models are static anyway, so the model bounding brushes can be stored along with the other brushes, only no planes need to be generated, since the misc_model entity contains a MD3 filename from which the model mesh should be loaded. If it becomes necessary to separate the model brushes from the others the only way to determine which bits are parts of the level and which are models appears to be to parse the comments written out by quark, where it seems to be defined. The problem with this approach is that it may compromise the compilers usability on other modellers. Adding to the confusion is the fact that the models lump seems to want an index to the brushes bounding the model as well as the mesh. Maybe its only used for the worldspawn, which is the first model? Doesn't seem reasonable to me.

On the surface worldspawn looks just like any other entity, but its entity data part is significantly more complicated. The level is constructed using brushes and patches.

A brush is a convex shape that completely encloses a part of the space inside itself. This property will later be used for collision detection to limit the players from walking through walls. The brushes are declared as a space that is behind a set of planes, that from an enclosed space. So for instace for a cube brush you need six planes: left, right, top, bottom, front and back. Patches will be dealt with later.

Here's what a brush defined by planes looks like:

{ 
  { 
    brushDef 
    { 
      (0 0 145) (145 543 0) (555 666 777) ( ( 0.0054 0.000 0.0015) (0.00013 0.005 0.000) ) texture 0 0 0 
      ... more planes 
    } 
  } 
} 

So a brush defined by planes is declared by "brushDef". Note that there are some redundant "{" and "}" there. Inside the brush definition there are plane definitions one plane per line. The planes are defined by three points given at the start of the line. In the end of the line the texture name is given followed by some texture parameters. AFAIK only the first one is used to tell whether the plane should be a detail plane, ie. non structural. This is the case if the value is the decimal equivalent of 8000000 hex. The others are unknown to me so I don't know if there is something that needs to be taken into consideration when doing lighting, but at the moment they get passed directly into the BSP file. What is between these two ends is the top two rows of a transformation matrix for the texture coordinates for the vertices of the face that is on this plane. The last row is always (0 0 1) to from a three by three matrix. So what is essentially stored here are the multipliers of two linear equations of the form: u = a*u0 + b*v + c, where a, b and c are the values from one or the other row in the matrix and u0 & v0 are the untransformed texture coordinates and u & v the final coordinates. More on texture coordinate generation later.

Patches are parametric surfaces, allowing a lot more detailed representation of curved surfaces. A patch is a curved surface defined by a three by three grid of control points. A single patch can consist of any number of adjoining surfaces, which each surface sharing one row/column of control points with its neighbors. Support for patches is scheduled for v0.3.

.bsp files

The BSP files consist of several tables each with a distinct function. For details see this site

How does map3bspc work

MAP3BSPC is implemented as a pipeline of phases, each of which gets passed the data produced by the previous phases. Each of these phases is implemented in a subclass of BSPCompilerPhase. The pure virtual function doPhase() must be implemented and is the place where the data processing should occurr. The phases and their execution order is defined in a table in main(). This table is processed in a loop from beginning until a NULL is encountered, so that every compiler phase in the table gets executed.

The first phase is the map parser which reads the input file and generates a lot of info. After this phase the following data has been generated:

  1. Brushes
  2. Brushsides
  3. Planes
  4. Textures
  5. Faces
  6. Vertices, including texture coordinates, but excluding vertex normals
  7. Meshvertices

The next phase is the BSP-tree builder which produces the nodes and leafs of the BSP tree, including leaffaces and leafbrushes.

At the moment the PVS lighting phases only produce some filler information (that should be valid though!) that gets written to the bsp file.

Finally the data produced is written to a BSP file.

The order of the phases defined in the release should be maintained. any phases may be inserted in between these phase is you want to extend the functionality, but the order of the original phases should not be changed as the later phases depend on data being generated by the earlier phases. Also the map parser phase should always be te first phase and the BSP file writer the last, for obvious reasons.

The .map file parser

The parser is implemented as a generic framework that takes care of identifying the entities and skipping empty and comment lines. The actual parsing of entities is left to specific parsers that are subclasses of MapEntityParser. These parsers need to be registered to the map parser before it can use them. This is done in main() by calling registerEntityParsers(), which gets passed a table of entity parsers terminated by NULL. So if you want to implement an additional parser you only need to write the class an instantiate an object of that class in this table and thats it. The parser will automatically call the new parser when an entity is found that matches the name of the entityparser. At the moment only two parsers are implemented MapWorldspawnParser that takes care of parsing the worldspawn entity and MapLightParser that parses light entities for use in the lighting phase. Any other entities are parsed as text by MapUnknownEntityParser and are stored as MapUnknownEntity-objects and get written out as is into the bsp file entities table.

A helper class has been implemented to assist paring simple entities (such as light entities), called MapSimpleEntityParser. Passing an array of parameter names as strings and an empty array of equal size ift will parse the parameters given in the file for the entity and match the values to the parameter names passed to it. See MapLightParser for details on how to use MapSimpleEntityParser.

Computing vertices

Vertices and polygon faces are computed by intersecting all combinations of three in a brush against each other to find a vertex. See this map tutorial for details.

The vertices are stored in vertices-table. For each face there are face.numVertices vertices starting from face.vertexIndex.

Generating texture coordinates

The way texture coordinates are generated for polygons is a bit complicated. As seen above in the worldspawn section no actual texture coordinates are stored in the map file. So how do we get them, then? To do that we need to define a two dimensional coordinate space that is coplanar with the face we're texturing. The two unit vectors s and t that define the coordinate space are computed in the function getAxisBase that comes directly from the Quark source, who in turn have taken it from somewhere else. I've no idea how it's works, but it does, so I won't complain. Once the unit vectors are defined we only need to do a scalar projection of each vertex to those axes to get the untransformed texture coordinates. To get the final texture coordinates the untransformed coordinates are first transformed by using the plane's transformation matrix parsed from the map file and finally translating all the coordinates so that they're as close to zero as possible. This is done by finding the smallest u and smallest v and subtracting the whole part from all the coordinates. The resulting texture coordinates are in [0...1] range, so they need to be scaled to the texture 0..width and 0..height range when they're rendered (this will probably be taken care of by the underlying driver).

One thing that is still slightly unclear is where the origin of the texture coordinate space actually is. There is some discussion in the quark info pages and apparently the origin is defined by the plane (unit) normal scaled by its distance from the origin, but the current version appears to produce correct texture coordinates with the origin at (0,0,0). If this is wrong, the question that remains here, then is how to work the origin into the equations?

Face triangulation

Polygon-faces are triangulated by using the algorithm described in this doc.

Patches can be easily triangulated by using the control points.

The triangles produced are stored in meshvertices. Each face has a sequence of face.numMeshVertices mesh vertices starting from face.meshVertexIndex. Each mesh vertex is an index into the array of vertices for that face. So to get the actual vertex you need to do face.vertexIndex + meshVertindex. Each triplet of indices describes one triangle.

The BSP tree generator

BSP stands for Binary Space Partitioning. It works by recursively dividing the space by a plane into a front and back halves, until some arbitrary limit is reached. The resulting data structure is a binary tree (thats where the name comes from). The whole space is partitioned, so any point in the space is in one and only one leaf.

There are several different kinds of BSP trees. The one I'll describe here is the kind used by Quake3.

A BSP tree is built by using the planes of structural brushes as splitters. The algorithm divides the level into three kinds of leaves: structural, inside and outside. Structural leaves are leaves that contain only (parts of) one or more structural brushes and no empty space around them. An inside leaf contains only zero or more detail brushes and is bound on all sides by other inside leaves or or structural leaves. Outside leaves are the ones that surround the level and are connected to the Great Void outside the level. The outside leaves are bounded by other outside leaves or structural leaves.

So here's how the algorithm works

  1. generate splitter plane candidates by taking all the structural brush sides that haven't been used as a splitter in the tree above this node
  2. If there are no more splitter candidates, generate a leaf.
  3. select the next splitting plane. A good splitting plane is one that divides the structural brushes into two as evenly as possible without causing too many brushes being split into two to accommodate.
  4. Divide all the brushes based on the splitter plane into front and back lists and generate front and back nodes recursively.

The BSP tree is stored in four tables in the BSP file. The nodes are stored in the nodes table and leafs in the leafs table. The nodes have indices that indicate the front and back children, both of which are _always_ present. If the index is positive the child is a node and if it's negative it's a leaf whise index can be found by -index + 1. The indices to the faces stored for each leaf are stored in leaffaces as a sequence of leaf.numLeafFaces starting from leaf.leafFaceIndex. Brushes that are at least partially inside the leafs space are stored in a similar manner in leafbrushes.

Visibility determination

First portals are generated. Portals are areas that connect two leaves of the bsp tree with one another. Any portals connecting two structural, two outside or an outisde and a structural leaf are discarded, as these have no impact on the visibility determination. All portals are on the node splitter planes. The algorithm is described here

Once portals are generated, we can start building the PVS table. Initially each leaf forms a cluster. After that we iterate through each cluster to determine which clusters are visible through the portals connecting to this clusters.

Briefly, the following clusters are visible:

  1. the cluster itself
  2. the clusters connected directly to this clusters
  3. clusters connected to clusters connected directly to this cluster, unless the portals are coplanar
  4. any cluster visible through the clusters visible to this cluster

The actual algorithm is explained here

Finally the PVS table is optimized by joining those cluster whose visible sets are the same.

Need more information?

contact the project team. See main page.

Further reading

Quark documentation on Brush primitives

MAP file tutorial in the tutorials section. Discusses an older format, but has enough good stuff for us as well.

Quake 3 BSP file format

Another Q3 BSP file format

Minimum triangulation of a convex polygon

Binary Space Partitioning tutorial

Another BSP tutorial Has a section on choosing the splitter plane

some stuff on Quake 3 collision detection. Seems pretty thorough.

On potentially visible sets

Automatic portal generation

Q3Radiant manual

Q3A Shader manual

q3map explanation


CVS ID: $Id: tech.html,v 1.2 2003/09/12 18:10:33 heiks Exp $