scenario_structure_bsp

Edit

The scenario structure BSP tag, commonly just called the BSP, contains level geometry, weather data, material assignments, AI pathfinding information, lightmaps, and other data structures. You can think of the BSP as the "stage" where the game takes place objects are placed within it. Aside from sounds and bitmaps, the BSP tends to be one of the largest tags in a map. Singleplayer scenarios often use multiple BSPs which are switched between at loading zones.

The term "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:

• shader_transparent_chicago for flowing rivers or waterfalls
• shader_transparent_chicago_extended for waterfalls
• shader_transparent_water for lakes and oceans

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 even reference different skies. The level will contain a single large cluster if no portals were created.

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.

Indoor vs. outdoor clusters

Clusters are either outdoor/exterior or indoor/interior. When a cluster contains +sky faces it is an outdoor cluster and has a sky index of 0 or greater. Furthermore, any cluster from which an outdoor cluster is potentially visible will also be an outdoor cluster.

An indoor cluster is one where none of its potentially visible clusters are outdoor. These clusters have a sky index of -1 instead and use the indoor parameters of sky index 0 (the first sky), which always has the special role of doubling as the "indoor sky". For example, indoor clusters will use use its indoor fog color rather than its outdoor fog color.

When the game transitions between indoor and outdoor clusters the fog colour fades based on cumulative camera movement, not time. This effect can be seen easily in Danger Canyon: load it in Sapien and fly the camera through the hallways while debug_pvs 1 and rasterizer_wireframe 1 are enabled.

Potentially visible set

The potentially visible set data (PVS) is precomputed when a BSP is compiled and helps the engine determine which clusters are visible from each other. A cluster can "see" any other cluster behind portals visible from itself plus one level of clusters further. Any clusters beyond that will not be rendered.

Tool also takes into account the indoor sky's indoor fog opaque distance and indoor fog maximum density when computing the PVS. If the density is 1.0 (fully opaque) then Tool knows that indoor clusters cannot see beyond the opaque distance even if there are clusters within a line of sight. Tool logs the indoor maximum world units when the BSP is compiled (if there a sky referenced).

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. It is invalid for a cluster to be able to see multiple fog planes (see more).

Weather polyhedra

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

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

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

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 script functions and globals

The following are related functions that you can use in your scenario scripts and/or debug globals that you can enter into the developer console for troubleshooting.

(collision_debug [boolean])

(collision_debug_features [boolean])

(collision_debug_flag_structure [boolean])

(collision_debug_phantom_bsp [boolean])

(collision_debug_spray [boolean])

(debug_bsp [boolean])

(debug_camera [boolean])

(debug_portals [boolean])

(debug_sound_environment [boolean])

(debug_structure [boolean])

Structure and fields

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)