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.

Lightmaps

Lightmaps are the visual representation of the BSP, and are stored in a separate representation from its collision data. The lightmaps data includes the renderable triangles and a precalculated radiosity bitmap.

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 artifact and implemented a feature to help spot it (collision_debug_phantom_bsp 1 in Sapien or standalone). 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. 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.
  4. Using phantom_tool or H1A Tool's fix-phantom-bsp option to compile your BSP will prevent phantom BSP at the cost of slightly increasing the tag size.
  5. If you do not have access to source JMS, and are trying to fix a BSP tag, the tool Ghostbuster may fix it but has known issues.

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 or H1A Tool's fix-phantom-bsp option also prevents this.

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.

Related commands

These commands are entered into the developer console.

Function

(collision_debug [boolean])

If enabled, the center of the view is used to test for collisions. A red normal-aligned marker will be shown where the ray from the center of view collides with a surface. The collision surface itself, whether BSP or model, will be outline in red. Information about the collision surface will be shown in the top left corner of the screen, including plane and surface indices from the BSP structure, material type, and how many degrees the surface's normal differs from vertical.

The types of surfaces which the test ray hits or ignores can be toggled with the collision_debug_flag_* commands. The maximum range of the ray is controlled with collision_debug_length.

(collision_debug_features [boolean])

Toggles the display of collision features near the camera, which can be spheres (red), cylinders (blue), or prisms (green). Collision size can be adjusted with collision_debug_width and collision_debug_height. The test point can be frozen in place using collision_debug_repeat.

(collision_debug_flag_structure [boolean])

Toggles if collision debug rays collide with the structure BSP. Collisions with model_collision_geometry BSPs are unaffected.

(collision_debug_phantom_bsp [boolean])

Causes a floating pink cube and label "phantom bsp" to appear whenever a test ray from the center of the screen intersects with phantom BSP. It can be helpful to pair this with collision_debug_spray.

(collision_debug_spray [boolean])

Setting this to true will cause collision ray tests to be performed in a dense grid from the viewport. This operates independently of the collision_debug setting, and only the destination hit markers are shown. Can be affected by collision flags, length, and frozen with collision_debug_repeat.

(debug_bsp [boolean])

Toggles the display of structure BSP node traversal for the camera location. At each level, the node and plane indices are shown as well as a + or - symbol indicating if the camera was on the front or back side of the plane.

(debug_camera [boolean])

Shows debug information about the camera in the top left corner, including:

  • 3D coordinates in world units
  • BSP leaf and cluster indices
  • Ground point coordinates and BSP surface index (point directly below the camera on the ground)
  • Facing direction (yaw angle)
  • Tag path of the shader pointed at by the camera. The surface must be collideable and this feature cannot be configured with collision debug flags.
(debug_portals [boolean])

Draws structure BSP portals as red outlines.

(debug_sound_environment [boolean])

If enabled, shows the tag path of the cluster's current sound_environment.

(debug_structure [boolean])

When enbled, all scenario_structure_bsp collision surfaces will be rendered with green outlines.

Structure and fields

Field Type Comments
lightmaps bitmap

TagDependency: bitmap

A reference to the bitmap storing the level's baked lightmaps. The level will not be visible without this.

vehicle floor float
  • Unit: 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 float
  • Unit: 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.

default ambient color ColorRGB
Field Type Comments
red float
green float
blue float
default distant light 0 color ColorRGB?
default distant light 0 direction Vector3D
Field Type Comments
i float
j float
k float
default distant light 1 color ColorRGB?
default distant light 1 direction Vector3D?
default reflection tint ColorARGB
Field Type Comments
alpha float
red float
green float
blue float
default shadow vector Vector3D?
default shadow color ColorRGB?
collision materials Block
  • HEK max count: 512
  • Read-only
  • Processed during compile
Field Type Comments
shader

TagDependency: shader

  • Non-null
material enum
  • Cache only
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
  • HEK max count: 1
  • Read-only
  • Processed during compile
Field Type Comments
bsp3d nodes Block
  • HEK max count: 131072

A 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.

  • Read-only
Field Type Comments
plane uint32

An index into the planes block. The plane divides 3D space into front and back half-spaces. A point can be tested against this plane to determine which half-space to descend into.

Tool will create new planes or use existing surface planes when generating the BSP tree based on a heuristic of how many surfaces remain in the node. For 1024 and above, axis-aligned planes based on vertex bounds are used. Otherwise, the surface within the remaining set whose plane minimizes the difference between front and back surface counts is used.

back child uint32
  • Flagged

Index of the BSP3D node representing space to the back of the dividing plane. A value of 0xFFFFFFFF is considered null and 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 uint32
  • Flagged

Similar to the back child field.

planes Block
  • HEK max count: 65536

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.

  • Read-only
Field Type Comments
plane Plane3D

A plane which divides 3D space in two.

Field Type Comments
vector Vector3D?

A 3-float normal vector.

w float

Distance from origin (along normal).

leaves Block
  • HEK max count: 65536

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.

  • Read-only
Field Type Comments
flags bitfield

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 uint16

Determines how many contiguous 2D BSP references belong to this leaf.

first bsp2d reference uint32

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
  • HEK max count: 131072

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.

  • Read-only
Field Type Comments
plane uint32
  • 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. A flagged plane index means its normal vector is opposite.

bsp2d node uint32
  • Flagged

The starting node for the 2D BSP on this plane. If flagged, then the index (masked to 0x7FFFFFFF) refers to a surface instead. Null if 0xFFFFFFFF.

bsp2d nodes Block
  • HEK max count: 65535
  • Read-only
Field Type Comments
plane Plane2D

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

Field Type Comments
vector Vector2D
Field Type Comments
i float
j float
w float
left child uint32
  • Flagged

refers to a BSP2D node if not signed and a surface if sign bit is set; null if 0xFFFFFFFF.

right child uint32
  • Flagged

refers to a BSP2D node if not signed and a surface if sign bit is set; null if 0xFFFFFFFF.

surfaces Block
  • HEK max count: 131072

Surfaces are planar collideable polygons. They are not necessarily triangular and may have up to 8 edges. BSP collision surfaces can be visualized in Sapien using debug_structure 1. These surfaces are not used for the rendered geometry.

  • Read-only
Field Type Comments
plane uint32
  • 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 uint32
flags bitfield
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.bit there cannot be more than 256 unique breakable surfaces in a BSP.

breakable surface int8

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 uint16
edges Block
  • HEK max count: 262144

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.

  • Read-only
Field Type Comments
start vertex uint32
end vertex uint32
forward edge uint32
reverse edge uint32
left surface uint32
right surface uint32
vertices Block
  • HEK max count: 131072

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

  • Read-only
Field Type Comments
point Point3D
Field Type Comments
x float
y float
z float
first edge uint32
nodes Block
  • HEK max count: 131072
  • Read-only
Field Type Comments
node stuff uint16[3]
world bounds x Bounds
Field Type Comments
min float
max float
world bounds y Bounds?
world bounds z Bounds?
leaves Block
  • HEK max count: 65536
  • Read-only
Field Type Comments
vertices uint16[3]
cluster uint16
surface reference count uint16
surface references int32
leaf surfaces Block
  • HEK max count: 262144
  • Read-only
Field Type Comments
surface int32
node int32
surfaces Block
  • HEK max count: 131072
  • Read-only
Field Type Comments
vertex0 index uint16
vertex1 index uint16
vertex2 index uint16
lightmaps Block
  • HEK max count: 128
  • Read-only
Field Type Comments
bitmap uint16
materials Block
  • HEK max count: 2048
  • Read-only
  • Processed during compile
Field Type Comments
shader

TagDependency: shader

  • Non-null
shader permutation uint16
flags bitfield
Flag Mask Comments
coplanar 0x1
fog plane 0x2
surfaces int32
surface count int32
centroid Point3D?
ambient color ColorRGB?
distant light count uint16
distant light 0 color ColorRGB?
distant light 0 direction Vector3D?
distant light 1 color ColorRGB?
distant light 1 direction Vector3D?
reflection tint ColorARGB?
shadow vector Vector3D?
shadow color ColorRGB?
plane Plane3D?
breakable surface uint16
do not screw up the model uint32
  • H1X only
  • Cache only

(Xbox only) if this isn't set to 1, then the world ends

rendered vertices count uint32
rendered vertices offset uint32
rendered vertices index pointer ptr32
  • H1X only
  • Cache only

(Xbox only) an indirect pointer to the rendered vertices

set this or die uint32
  • H1X only
  • Cache only

(Xbox only) if this isn't set to 3, then the visible lightmap UVs do not work

lightmap vertices count uint32
lightmap vertices offset uint32
lightmap vertices index pointer ptr32
  • H1X only
  • Cache only

(Xbox only) an indirect pointer to the lightmap vertices

uncompressed vertices TagDataOffset
Field Type Comments
size uint32
external uint32
file offset uint32
pointer ptr64
compressed vertices TagDataOffset?
lens flares Block
  • HEK max count: 256

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

  • Read-only
Field Type Comments
lens

TagDependency: lens_flare

lens flare markers Block
  • HEK max count: 65536

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

  • Read-only
Field Type Comments
position Point3D?

The 3D position of the lens flare.

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

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

clusters Block
  • HEK max count: 8192
  • Read-only
Field Type Comments
sky uint16

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 uint16
background sound uint16
sound environment uint16
weather uint16
transition structure bsp uint16
first decal index uint16
  • Cache only
decal count uint16
  • Cache only
predicted resources Block
  • HEK max count: 1024
  • Cache only
Field Type Comments
type enum
Option Value Comments
bitmap 0x0
sound 0x1
resource index uint16
tag uint32
subclusters Block
  • HEK max count: 4096
  • Read-only
Field Type Comments
world bounds x Bounds?
world bounds y Bounds?
world bounds z Bounds?
surface indices Block
  • Read-only
Field Type Comments
index int32
first lens flare marker index uint16
lens flare marker count uint16
surface indices Block
  • HEK max count: 32768
  • Read-only
Field Type Comments
index int32
mirrors Block
  • HEK max count: 16
  • Read-only
Field Type Comments
plane Plane3D?
shader

TagDependency: shader

vertices Block
  • HEK max count: 512
  • Read-only
Field Type Comments
point Point3D?
portals Block
  • HEK max count: 128
  • Read-only
Field Type Comments
portal uint16
cluster data TagDataOffset?
cluster portals Block
  • HEK max count: 512
  • Read-only
Field Type Comments
front cluster uint16
back cluster uint16
plane index int32
centroid Point3D?
bounding radius float
flags bitfield
Flag Mask Comments
ai can simply not hear through all this amazing stuff darn it 0x1
vertices Block
  • HEK max count: 128
  • Read-only
Field Type Comments
point Point3D?
breakable surfaces Block
  • HEK max count: 256
  • Read-only
Field Type Comments
centroid Point3D?
radius float
collision surface index int32
fog planes Block
  • HEK max count: 32
  • Read-only
Field Type Comments
front region uint16
material type enum?
  • Cache only
plane Plane3D?
vertices Block
  • HEK max count: 2048
  • Read-only
Field Type Comments
point Point3D?
fog regions Block
  • HEK max count: 32
  • Read-only
Field Type Comments
fog uint16
weather palette uint16
fog palette Block
  • HEK max count: 32
  • Max: 65534
Field Type Comments
name TagString
Field Type Comments
buffer char[32]

Null-terminated string in 32-char buffer.

fog

TagDependency: fog

fog scale function TagString?
weather palette Block
  • HEK max count: 32
Field Type Comments
name TagString?
particle system

TagDependency: weather_particle_system

particle system scale function TagString?
wind

TagDependency: wind

wind direction Vector3D?
wind magnitude float
wind scale function TagString?
weather polyhedra Block
  • HEK max count: 32
  • Read-only
Field Type Comments
bounding sphere center Point3D?
bounding sphere radius float
planes Block
  • HEK max count: 16
  • Read-only
Field Type Comments
plane Plane3D?
pathfinding surfaces Block
  • HEK max count: 131072
  • Read-only
Field Type Comments
data int8
pathfinding edges Block
  • HEK max count: 262144
  • Read-only
Field Type Comments
midpoint int8
background sound palette Block
  • HEK max count: 64
Field Type Comments
name TagString?
background sound

TagDependency: sound_looping

scale function TagString?
sound environment palette Block
  • HEK max count: 64
Field Type Comments
name TagString?
sound environment

TagDependency: sound_environment

sound pas data TagDataOffset?
markers Block
  • HEK max count: 1024

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 TagString?
rotation Quaternion
Field Type Comments
i float
j float
k float
w float
position Point3D?
detail objects Block
  • HEK max count: 1
  • Processed during compile
Field Type Comments
cells Block
  • HEK max count: 262144
Field Type Comments
no name int16
no name 1 int16
no name 2 int16
no name 3 int16
no name 4 int32
no name 5 int32
no name 6 int32
instances Block
  • HEK max count: 2097152
Field Type Comments
no name int8
no name 1 int8
no name 2 int8
no name 3 int8
no name 4 int16
counts Block
  • HEK max count: 8388608
Field Type Comments
no name int16
z reference vectors Block
  • HEK max count: 262144
Field Type Comments
no name float
no name 1 float
no name 2 float
no name 3 float
bullshit uint8
  • Cache only
runtime decals Block
  • HEK max count: 6144
  • Cache only
  • Read-only
Field Type Comments
position Point3D?
decal type uint16
yaw int8
pitch int8
leaf map leaves Block
  • HEK max count: 65536
  • Read-only
Field Type Comments
faces Block
  • HEK max count: 256
  • Read-only
Field Type Comments
node index int32
vertices Block
  • HEK max count: 64
  • Read-only
Field Type Comments
vertex Point2D
Field Type Comments
x float
y float
portal indices Block
  • HEK max count: 256
  • Read-only
Field Type Comments
portal index int32
leaf map portals Block
  • HEK max count: 524288
  • Read-only
Field Type Comments
plane index int32
back leaf index int32
front leaf index int32
vertices Block
  • Read-only
Field Type Comments
point Point3D?

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)
  • Hari (Collision BSP compilation reversing)
  • Kavawuvi (Invader tag definitions)
  • MosesOfEgypt (Tag structure research; Research on weather polyhedra and portals)