scenario_structure_bsp

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 convex leaf nodes. The resulting BSP tree can be used to efficiently answer geometric queries, such as which surfaces should be collision-tested for physics objects.

Compilation

After level geometry is exported to JMS format, it can be compiled into a BSP tag using Tool's structure verb.

BSP transitions

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.

Although multiple BSPs are intended for singleplayer maps and do not synchronize, some custom multiplayer maps have used nearly identical BSPs which only differ in lighting to add a day/night switch scripted by a button in the escape menu.

Shaders

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:

The shader_model type will not be rendered by the game since it is intended for use with object models.

Clusters and cluster data

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. Different clusters can also reference different skies.

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.

Fog planes

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

Weather polys from AotCR

Weather polys extracted from AotCR.

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 game can only support a maximum of 8 visible weather polyhedra. Beyond this point, some polyhedra will be ignored and Sapien will print warnings.

Pathfinding data

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.

See more about the pathfinding system.

Lightmaps

See main page: Lightmaps.

Lens flare markers

Lens flare markers in a10

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 initial structure compilation or updated with structure-lens-flares. 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.

Collision artifacts

Phantom BSP

Danger Canyon contains at least two prevalent cases of phantom BSP. The Warthog and bullets are both colliding with invisible extensions of nearby surfaces.

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 mostly appears around sharp corners near cases of "nearly coplanar faces" warnings in your WRL file.

Bungie was aware of this bug, and even implemented a Sapien feature to help spot it (collision_debug_phantom_bsp 1). If you find phantom BSP in your map, there are a few steps you can take to resolve it:

  1. Preemptively, keep your geometry simple and robust without an abundance of dense, complex, or spiky shapes. Flat surfaces like floors and walls should be kept as flat as possible by using alignment tools when modeling rather than "eyeballing it".
  2. Fix any "nearly coplanar" warnings in your source model by scaling affected faces to 0 along their normal axis or using alignment. Since Tool slightly rounds vertex coordinates when compiling BSPs, sometimes this warning cannot be resolved for surfaces which are not axis-aligned.
  3. Using phantom_tool to compile your BSP will prevent phantom BSP at the cost of slightly increasing the tag size.
  4. There is an element of chance to phantom BSP appearing which depends on how your geometry is recursively subdivided form a BSP tree. Modifying unrelated parts of your level like adding portals or moving vertices can sometimes affect how the level is subdivided and make phantom BSP disappear.
  5. If you do not have access to source JMS, and are trying to fix a BSP tag, the tool Ghostbuster may fix it.

On a technical level, cases of phantom BSP are dividing planes where a child index is -1, but the space on that side of the plane is not actually completely outside the level. The artifact is bounded by all parent dividing planes.

BSP holes

This location in Derelict has a small collision hole where items can fall through the map.

BSP holes or leaks are another type of collision artifact where items or players can fall through the map. It is not known what causes this, but it can be resolved by altering triangulation around the affected area (rotating edges). Compiling the BSP with phantom_tool also prevents this.

Structure and fields

Field Type Comments
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.

pad(20)
default ambient color
ColorRGB (3)
  • red: f32
  • green: f32
  • blue: f32
pad(4)
default distant light 0 color
ColorRGB (3)
  • red: f32
  • green: f32
  • blue: f32
default distant light 0 direction
Vector3D (3)
  • i: f32
  • j: f32
  • k: f32
default distant light 1 color
ColorRGB (3)
  • red: f32
  • green: f32
  • blue: f32
default distant light 1 direction
Vector3D (3)
  • i: f32
  • j: f32
  • k: f32
pad(12)
default reflection tint
ColorARGB (4)
  • alpha: f32
  • red: f32
  • green: f32
  • blue: f32
default shadow vector
Vector3D (3)
  • i: f32
  • j: f32
  • k: f32
default shadow color
ColorRGB (3)
  • red: f32
  • green: f32
  • blue: f32
pad(4)
collision materials Block?
Field Type Comments
pad(2)
material enum (little endian?)
  • Only set when the tag is compiled into a map cache.
Option Value Comments
dirt 0x0
sand 0x1
stone 0x2
snow 0x3
wood 0x4
metal hollow 0x5
metal thin 0x6
metal thick 0x7
rubber 0x8
glass 0x9
force field 0xa
grunt 0xb
hunter armor 0xc
hunter skin 0xd
elite 0xe
jackal 0xf
jackal energy shield 0x10
engineer skin 0x11
engineer force field 0x12
flood combat form 0x13
flood carrier form 0x14
cyborg armor 0x15
cyborg energy shield 0x16
human armor 0x17
human skin 0x18
sentinel 0x19
monitor 0x1a
plastic 0x1b
water 0x1c
leaves 0x1d
elite energy shield 0x1e
ice 0x1f
hunter shield 0x20
collision bsp Block?
Field Type Comments
bsp3d nodes Block?

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.

front child u32 (flagged)

Similar to the back child field.

planes 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 (4)
  • 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 Block?

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.

bsp2d references Block?

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.

bsp2d nodes Block?
Field Type Comments
plane
Plane2D (3)
  • i: f32
  • j: f32
  • d: f32

A 2D plane (line) subdividing left and right child surfaces. This line is in the space of the 2D BSP reference's basis plane.

left child u32 (flagged)

Index of the left child bsp2d node. If the highest bit is set, then the remaining bits (mask 0x7FFFFFFF) are instead an index into the surfaces block.

right child u32 (flagged)

Similar to the left child field.

surfaces Block?

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.

material Index: u16
edges Block?

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.

Field Type Comments
start vertex u32
end vertex u32
forward edge u32
reverse edge u32
left surface u32
right surface u32
vertices Block?

The 3D coordinates used for edge starting and ending locations.

Field Type Comments
point
Point3D (3)
  • x: f32
  • y: f32
  • z: f32
first edge u32
nodes Block?
Field Type Comments
node stuff u16 (little endian?) x3
world bounds x f32 (min & max)
world bounds y f32 (min & max)
world bounds z f32 (min & max)
leaves Block?
Field Type Comments
vertices u16 (little endian?) x3
pad(2)
cluster Index: u16
surface reference count u16
surface references i32
leaf surfaces Block?
Field Type Comments
surface i32
node i32
surfaces Block?
Field Type Comments
vertex0 index Index: u16
vertex1 index Index: u16
vertex2 index Index: u16
lightmaps Block?
Field Type Comments
bitmap Index: u16
pad(2)
pad(16)
materials Block?
Field Type Comments
shader permutation Index: u16
flags bitfield(16)
Flag Mask Comments
coplanar 0x1
fog plane 0x2
surfaces i32
surface count i32
centroid
Point3D (3)
  • x: f32
  • y: f32
  • z: f32
ambient color
ColorRGB (3)
  • red: f32
  • green: f32
  • blue: f32
distant light count u16
pad(2)
distant light 0 color
ColorRGB (3)
  • red: f32
  • green: f32
  • blue: f32
distant light 0 direction
Vector3D (3)
  • i: f32
  • j: f32
  • k: f32
distant light 1 color
ColorRGB (3)
  • red: f32
  • green: f32
  • blue: f32
distant light 1 direction
Vector3D (3)
  • i: f32
  • j: f32
  • k: f32
pad(12)
reflection tint
ColorARGB (4)
  • alpha: f32
  • red: f32
  • green: f32
  • blue: f32
shadow vector
Vector3D (3)
  • i: f32
  • j: f32
  • k: f32
shadow color
ColorRGB (3)
  • red: f32
  • green: f32
  • blue: f32
plane
Plane3D (4)
  • i: f32
  • j: f32
  • k: f32
  • d: f32
breakable surface Index: u16
pad(2)
pad(4)
rendered vertices count u32
rendered vertices offset u32
pad(8)
pad(4)
lightmap vertices count u32
lightmap vertices offset u32
pad(8)
uncompressed vertices
TagDataOffset (4)
  • size: u32
  • external: u32
  • file offset: u32
  • pointer: u64
compressed vertices
TagDataOffset (4)
  • size: u32
  • external: u32
  • file offset: u32
  • pointer: u64
  • Not included when the tag is compiled into a map cache.
pad(12)
lens flares Block?

Lists the available lens flares used by this BSP's lens flare markers.

Field Type Comments
lens flare markers Block?

Points within the BSP where a lens flare will be rendered.

Field Type Comments
position
Point3D (3)
  • x: f32
  • y: f32
  • z: f32

The 3D position of the lens flare.

direction i component i8
direction j component i8
direction k component i8
lens flare index i8

Determines which flare from the lens flares block is rendered at this position.

clusters Block?
Field Type Comments
sky Index: u16

Sets which sky is visible when within this cluster. Indexes the skies block of the scenario tag, so a value of 0 would mean the first sky, 1 the second, etc. A value of -1 marks this cluster as indoor/interior for the purposes of certain sky tag fields.

It is unknown how exactly Tool determines which clusters are indoor when compiling a BSP, but it does validate that all sky faces in a cluster are of the same sky. For example, a cluster cannot contain both +sky0 and +sky1 materials.

When a player moves between clusters with different skies, there is no transition. The sky will abruptly change.

fog Index: u16
background sound Index: u16
sound environment Index: u16
weather Index: u16
transition structure bsp Index: u16
first decal index Index: u16 (little endian?)
  • Only set when the tag is compiled into a map cache.
decal count u16 (little endian?)
  • Only set when the tag is compiled into a map cache.
pad(24)
predicted resources Block?
PredictedResource
subclusters Block?
Field Type Comments
world bounds x f32 (min & max)
world bounds y f32 (min & max)
world bounds z f32 (min & max)
surface indices Block?
Field Type Comments
index i32
first lens flare marker index Index: u16
lens flare marker count u16
surface indices Block?
Field Type Comments
index i32
mirrors Block?
Field Type Comments
plane
Plane3D (4)
  • i: f32
  • j: f32
  • k: f32
  • d: f32
pad(20)
vertices Block?
Field Type Comments
point
Point3D (3)
  • x: f32
  • y: f32
  • z: f32
portals Block?
Field Type Comments
portal Index: u16
cluster data
TagDataOffset (4)
  • size: u32
  • external: u32
  • file offset: u32
  • pointer: u64
cluster portals Block?
Field Type Comments
front cluster Index: u16
back cluster Index: u16
plane index i32
centroid
Point3D (3)
  • x: f32
  • y: f32
  • z: f32
bounding radius f32
flags bitfield(32)
Flag Mask Comments
ai can simply not hear through all this amazing stuff darn it 0x1
pad(24)
vertices Block?
Field Type Comments
point
Point3D (3)
  • x: f32
  • y: f32
  • z: f32
pad(12)
breakable surfaces Block?
Field Type Comments
centroid
Point3D (3)
  • x: f32
  • y: f32
  • z: f32
radius f32
collision surface index i32
pad(28)
fog planes Block?
Field Type Comments
front region Index: u16
material type enum (little endian?)
  • Only set when the tag is compiled into a map cache.
Option Value Comments
dirt 0x0
sand 0x1
stone 0x2
snow 0x3
wood 0x4
metal hollow 0x5
metal thin 0x6
metal thick 0x7
rubber 0x8
glass 0x9
force field 0xa
grunt 0xb
hunter armor 0xc
hunter skin 0xd
elite 0xe
jackal 0xf
jackal energy shield 0x10
engineer skin 0x11
engineer force field 0x12
flood combat form 0x13
flood carrier form 0x14
cyborg armor 0x15
cyborg energy shield 0x16
human armor 0x17
human skin 0x18
sentinel 0x19
monitor 0x1a
plastic 0x1b
water 0x1c
leaves 0x1d
elite energy shield 0x1e
ice 0x1f
hunter shield 0x20
plane
Plane3D (4)
  • i: f32
  • j: f32
  • k: f32
  • d: f32
vertices Block?
Field Type Comments
point
Point3D (3)
  • x: f32
  • y: f32
  • z: f32
fog regions Block?
Field Type Comments
pad(36)
fog Index (fog palette)
weather palette Index (weather palette)
fog palette Block?
  • Maximum: 65534
Field Type Comments
name char[32]
pad(4)
fog scale function char[32]
pad(52)
pad(24)
weather palette Block?
Field Type Comments
name char[32]
pad(4)
particle system scale function char[32]
pad(44)
wind direction
Vector3D (3)
  • i: f32
  • j: f32
  • k: f32
wind magnitude f32
pad(4)
wind scale function char[32]
pad(44)
weather polyhedra Block?
Field Type Comments
bounding sphere center
Point3D (3)
  • x: f32
  • y: f32
  • z: f32
bounding sphere radius f32
pad(4)
planes Block?
Field Type Comments
plane
Plane3D (4)
  • i: f32
  • j: f32
  • k: f32
  • d: f32
pad(24)
pathfinding surfaces Block?
Field Type Comments
data i8
pathfinding edges Block?
Field Type Comments
midpoint i8
background sound palette Block?
Field Type Comments
name char[32]
pad(4)
scale function char[32]
pad(32)
sound environment palette Block?
Field Type Comments
name char[32]
pad(32)
sound pas data
TagDataOffset (4)
  • size: u32
  • external: u32
  • file offset: u32
  • pointer: u64
pad(24)
markers Block?

Named points with orientation within the BSP. They are similar to gbxmodel markers but are not to be confused with scenario cutscene flags. These markers become visible in Sapien when enabling snap to markers in the tool window.

Field Type Comments
name char[32]
rotation
Quaternion (4)
  • i: f32
  • j: f32
  • k: f32
  • w: f32
position
Point3D (3)
  • x: f32
  • y: f32
  • z: f32
detail objects Block?
Field Type Comments
cells Block?
Field Type Comments
no name i16
no name 1 i16
no name 2 i16
no name 3 i16
no name 4 i32
no name 5 i32
no name 6 i32
pad(12)
instances Block?
Field Type Comments
no name i8
no name 1 i8
no name 2 i8
no name 3 i8
no name 4 i16
counts Block?
Field Type Comments
no name i16
z reference vectors Block?
Field Type Comments
no name f32
no name 1 f32
no name 2 f32
no name 3 f32
bullshit u8
pad(3)
pad(12)
runtime decals Block?
  • Only set when the tag is compiled into a map cache.
Field Type Comments
position
Point3D (3)
  • x: f32
  • y: f32
  • z: f32
decal type Index: u16
yaw i8
pitch i8
pad(8)
pad(4)
leaf map leaves Block?
Field Type Comments
faces Block?
Field Type Comments
node index i32
vertices Block?
Field Type Comments
vertex
Point2D (2)
  • x: f32
  • y: f32
portal indices Block?
Field Type Comments
portal index i32
leaf map portals Block?
Field Type Comments
plane index i32
back leaf index i32
front leaf index i32
vertices Block?
Field Type Comments
point
Point3D (3)
  • x: f32
  • y: f32
  • z: f32

This information was partially generated using Invader tag definitions.

Acknowledgements

Thanks to the following individuals for their research or contributions to this topic:

  • Conscars (Collision BSP structure and phantom BSP research)
  • Galap (Researching the effect of cluster sky index on lighting)
  • Kavawuvi (Invader tag definitions)
  • MosesOfEgypt (Tag structure research; Research on weather polyhedra and portals)