Commonly referred to as the BSP, this tag contains level geometry, weather data, material assignments, AI pathfinding information, lightmaps, and other data structures. The name "BSP" is commonly used to refer to non-object level geometry in general. Aside from sounds and bitmaps, the BSP tends to be one of the largest tags in a map.
BSP stands for Binary Space Partitioning, a technique where space within a sealed static mesh is recursively subdivided by planes into convexleaf nodes. The resulting BSP tree can be used to efficiently answer geometric queries, such as which surfaces should be collision-tested for physics objects.
While a scenario can reference multiple BSPs, Halo can only have a single BSP loaded at a time. Transitions between BSPs can be scripted (switch_bsp), e.g. using trigger volumes. Objects in unloaded BSPs are not simulated.
The most commonly used shader type for BSPs is shader_environment, suitable for most opaque surfaces and alpha-tested grates or billboard trees (as in Timberland). This shader type supports the blending between multiple detail maps, often used for ground maps with dirt and grass areas.
Transparent shaders can also be used, for example:
Clusters are sealed volumes of a BSP separated by portal planes. They are used both as a rendering optimization and artistically; map authors can assign weather_particle_system, wind, sound_environment, and sound_looping tags to define local atmospheric and ambience qualities for each section of the map.
Note that it may still be desirable to reference weather for indoor clusters if there are outdoor areas visible from them, otherwise snow and rain particles will abruptly disappear. To mask weather in such clusters, use weather polyhedra.
There is a maximum limit to visible weather polyhedra. The exact amount is unconfirmed but is around 8-10. Beyond this point, some polyhedra will be ignored and Sapien will print warnings.
Areas of a map which need a fog layer can be marked using fog planes. These are 2D surfaces which reference fog tags, not to be confused with atmospheric fog which is part of the sky tag.
Weather polyhedra are simple convex volumes where weather particles will not render. They can be used to mask rain or snow from under overhangs, doorways, and indoor spaces when the cluster has weather.
When a JMS is compiled to BSP by tool, connected convex faces with the material name +weatherpoly will generate weather polyhedra. Within the tag, the polyhedra are represented as a center point, bounding radius, and up to 16 planes which enclose a volume.
The BSP contains data on traversable surfaces which aid AI in pathfinding (walking to a destination). This data is generated automatically during BSP compilation and is retained even in when the BSP is compiled into multiplayer maps.
The maximum pathfinding distance that Halo's engine permits is 3276.7 world units, an extremely long distance. For reference, the distance between bases in Timberland is approximately 100 units.
In a10, lens flare markers were generated for fluorescent lights
When a shader_environment references a lens_flare, lens flare markers are automatically created and stored in the BSP tag during structure compilation. These are used to give lights a "glowy" appearance. If the shader has a lens flare spacing of 0, a single lens flare is placed on the surface(how?). Otherwise, the lens flares are evenly spaced within the surface according to the spacing value (world units).
A BSP can contain up to 65535 lens flare markers, and up to 256 types of lens flares. However, there is a much lower limit to how many the game will draw at a given time, exactly how many is unknown.
Danger Canyon contains at least two prevalent cases of phantom BSP.
Phantom BSP is a collision artifact sometimes produced when compiling BSPs. It manifests itself as invisible surfaces which projectiles and vehicles collide with (but not players), and appears around sharp corners like those around doorways.
Phantom BSP can often be fixed by slightly moving or altering sections of the level that contain them, which causes the BSP to be divided differently. However, this may simply create new phantom BSP in another location. The chances of phantom BSP being created can be lowered by reducing complex dense geometry, ensuring co-planarity of faces, and avoiding edges sharper than 90 degrees. If Phantom BSP cannot be avoided and is a hindrance to gameplay, the tool Ghostbuster can be used to fix problematic BSP tags.
Bungie was aware of this bug, and even implemented a Sapien feature to troubleshoot it (collision_debug_phantom_bsp 1). It is now understood to be caused when Tool's BSP compilation process chooses a BSP dividing plane that fails to divide the remaining space meaningfully, i.e. there are no surfaces on one side of the plane, and the surfaces under the corresponding node leave parts of the dividing plane "exposed".
A reference to the bitmap storing the level's baked lightmaps. The level will not be visible without this.
vehicle floor
f32 (world units)
The lowest Z-axis height (absolute, not frame relative) that vehicles can reach while occupied. Does not affect other object types. An unoccupied vehicle will still drop below this soft barrier, but when it becomes occupied again it will quickly shoot back up into the play area. An example of a map using a vehicle floor is Gephyrophobia to prevent players from flying too far below the bridge.
vehicle ceiling
f32 (world units)
The maximum Z-axis height (absolute, not frame relative) that vehicles can reach while occupied. Does not affect other objects types. Above this point, occupied vehicles will elastically move back below the ceiling. This can be used to limit the height that players in flying vehicles like Banshees can reach for gameplay reasons. An example of this can be seen in Blood Gulch.
An block of nodes used to efficiently find collideable surfaces. Each node divides space with an infinite plane and references two child nodes by index into this block. The first element in the block is the root node. A test point can be recursively tested against planes to find a leaf of potentially colliding surfaces.
Field
Type
Comments
plane
u32
An index into the planes block. The plane divides 3D space in two. Generally, tool chooses surfaces to make dividing planes using an unknown heuristic. The first few levels of BSP seem to use special axis-aligned planes which are stored at the tail of the planes block, likely to avoid poor early heuristic choices which would negatively affect collision testing performance.
back child
u32 (flagged)
Index of the bsp3d node representing space to the back of the dividing plane. If the index is -1, then the space behind the plane is considered outside the sealed BSP (Sapien labels this as "solid" space when using debug_structure). Otherwise, if the highest order bit is set (0x80000000), the remaining 31 bits (mask 0x7FFFFFFF) represent an index into the leaves block.
Planes are infinite 2D surfaces in 3D space. They are used both to subdivide the BSP in each bsp3d node and to define collideable surfaces. The first 8 planes in the block seem to serve a special purpose -- the first 4 define the XY bounding box, with the next 4 axis aligned planes unkown. Furthermore, the last 8 planes in the block are used for the first few levels of bsp3d nodes. A single plane may be referenced from multiple bsp3d nodes since the surfaces that planes derive from can also be found in multiple leaves.
Field
Type
Comments
plane
Plane3D
i: f32
j: f32
k: f32
d: f32
A plane which divides 3D space in two, stored as a 3-float normal and d (distance from origin) parameter.
Leaves mark the transition between the 3D BSP and a collection of convex collideable surfaces in the same localized area. Each set of co-planar surfaces within this leaf is stored within a child 2D BSP.
Note that surfaces may be found under multiple leaves, since any surface which is not completely on either side of a 3D plane will need to belong to both child 3D BSP nodes.
Field
Type
Comments
flags
bitfield(16)
Flags used to optimize collision checks at runtime.
Flag
Mask
Comments
contains double sided surfaces
0x1
Indicates if any surface in any of this leaf's 2D BSPs is double-sided (e.g. glass).
bsp2d reference count
u16
Determines how many contiguous 2D BSP references belong to this leaf.
first bsp2d reference
u32
Index of the first 2D BSP reference associated with this leaf. It will be followed by a number of other 2D BSP references according to the above count.
Represents either a 2D BSP of surfaces, or a singular surface if the node index is flagged. In either case, test points or 3D line traces should be projected onto the basis plane in order to continue
Field
Type
Comments
plane
u32 (flagged)
Index for the plane used to decide what basis plane is best to project on (X,Y), (Y,Z) or (X,Z). The basis plane is chosen by the referenced plane's most significant normal component. The meaning of a flagged plane index is unknown.
bsp2d node
u32 (flagged)
The starting node for the 2D BSP on this plane. If flagged, then the index (masked to 0x7FFFFFFF) refers to a surface instead.
Surfaces are planar collideable polygons. They are not necessarily triangular (4 is also common, and Blood Gulch has one with 7 edges), and can be visualized in sapien using debug_structure 1. These surfaces are not used for the rendered geometry.
Field
Type
Comments
plane
u32 (flagged)
Index into the planes block for this surface's plane. Note that multiple co-planar surfaces may reference the same plane since this plane index is a copy of the parent bsp2d reference's plane index, even when flagged.
first edge
u32
flags
bitfield(8)
Flag
Mask
Comments
two sided
0x1
invisible
0x2
climbable
0x4
Indicates if the surface is a climbable ladder.
breakable
0x8
Indicates if the surface is breakable. The surface must also have a breakable surface index below.
breakable surface
i8
Index into this tag's breakable surfaces block. It is unknown if this is a signed or flagged field, but since it is 8-bit there cannot be more than 256 unique breakable surfaces in a BSP.
Edges, surfaces, and vertices form a data structure called a doubly connected edge list (DCEL), also known as a half-edge data structure. The edges and their vertices define the boundaries of the collideable surfaces within a leaf.
