An Overview

To determine what sections of a map the player can see, the Q3Map2 compiler has to first find a way to partition (or split) a map into separate volumes of space. The relationship of connectivity between each of these volumes needs to be indexed so that the engine has some way of tracking where the player is at any given time, and in another process determine whether the player can potentially see into other adjacent volumes. Q3Map2 begins this first process with a Binary Space Partition (BSP).

A BSP is a recursive function (an operation that causes itself to repeat within itself) of Q3Map2 that takes the entire volume of a map and continuously partitions it roughly in half into smaller volumes until each area is a single convex volume (one in which none of the outward faces meet at an angle of less than 180°). As Q3Map2 continuously refines each volume to smaller chunks, it indexes it all into something called a BSP-tree. Each node on the BSP-tree represents a portal that divides a volume into two (binary) branches. When a volume cannot be subdivided because it is a single convex volume, Q3Map2 looks at the next branch. The process stops only when every single volume in the map is convex. A single convex volume is called a leaf node on the BSP-tree.

Convex volumes are important for visability (later calculated as part of the "VIS" process of Q3Map2) since it is much easier working with convex volumes to determine whether or not two convex volumes can see each other. This process will be explored in another section. For now, you just need to be able to recognize what a convex shape looks like.

The process works as follows:

• If the volume contains structural brushes...
  • Then split the volume along the plane of a face of one structural brush. Continue to the first child volume produced and repeat the operation.
• Else if the Volume does not contain structural Brushes, it contains no Planes for splitting, and a Leaf Node is created for the volume...
  • Then return to the next child volume up the tree and repeat the operation.
• Else there is no child volume...
• End the operation.

Notes:

• Each split-plane does not always divide the volume exactly in half. It is important to split the tree roughly in half each time in order that each Leaf Node is roughly the same distance from the tree's root, balancing the branches of the tree.
• Axial split-planes are chosen before non-axial split-planes. The split-plane which cuts through the maximum number of brushes is chosen.

An Example

The process might sound complicated in theory, but it is really just a simple function that breaks the problem down into many of the same but smaller problems. That is the power of recursion! Let's look at a simplified 2-D map and see how BSP works:

1. We start with the basic map layout (left). It is a single volume on the BSP tree (right), denoted as (1).

   

2. The BSP process creates a portal (A), which partitions the volume into two new volume nodes (2) & (3) of approximately equal size.

   

3. We progress down the first branch at (2) and create a portal (B), creating partitions (4) & (5).

   

4. Further down the branch, portal (C) creates partitions (6) & (7). Note in the layout view that these two new partitions are both convex volumes, the BSP process cannot partition these volumes any further. These convex volumes are called “leaf nodes”, because they sit at the end of a branch of the BSP-tree.

   

5. Having reached the end of one branch, the process moves back up the tree to the next available branch at node (5), partitioned by (D) into leaf nodes (8) & (9). This marks the end of this half of the tree and the process continues at node (3).

   

Try to work out the rest of the BSP-tree yourself. Keep in mind that you want to partition each node more or less in equal halves. Due to the somewhat random nature of BSPs, there is usually more than one solution.

Triangle Mesh

-----stuff about converting brushes, models, patches, etc. to triangle meshes or bezier curves-----