The heart of BSP & A brief history of VIS

[snake-biscuits]

After finding the last unknowns in respawn.titanfall.LevelInfo, we took the theory that RespawnBsp worldspawn meshes are sorted for rendering purposes.

I tried applying this knowledge to MRVN-Radiant, but had mixed success¹
Identifying the skybox textured meshes in LevelInfo led to maps rendering worse than before, with sky rendering as void.
This was clearly a vis issue.

MRVN-Radiant doesn't yet support static props, but Titanfall 2 skyboxes are exclusively props.
Titanfall: Online is currently having issues mounting materials w/ custom maps (oddly copied r1 maps are ok).
But also, placing a sky_camera in the world doesn't "just work"

VIS is probably part of the issue here.

Footnotes

1. MRVN-Radiant on GitHub: Pull Request 35: Loads of syntax cleaning & light refactor of Titanfall::EmitMeshes ↩

[snake-biscuits]

So, the VIS system. What is it, and why is it called that?
VIS is short for Visibility, a core function of BSP level systems since Doom¹²
I use the VIS abreviation because it's what the Quake compiler that handles VIS lumps is called: vis.exe³⁴.

VIS is in some ways, the heart of the BSP format.
It's (one of) the reason(s) we split the whole map up by planes. To pre-calculate a minimum amount of stuff to render.
Two terms that come up a lot w/ BSP are PVS & PAS. Un-abbreviated: Potentially Visible / Audible Set.
By "Set" we are referring to a collection of renderable objects, in Quake-based BSP engines these are often Visleaves or Visclusters

Visleaves are a collection of faces or mesh triangles (roughly equivalent to DOOM sectors¹²)
Visleaves are convex, so no Renderable Primitive within the leaf overlaps another.

This isn't entirely true, visleaves can also contain static prop geometry which needs depth sorting to render
PVS is also used when rendering entities, which means dynamic geo (playermodels, npcs etc.)
Quake-based BSP Engines do generally turn off "costly" (less so by modern standards) graphics options like depth tests & buffer clears

Visclusters are groups of visleaves, after Quake 2 most Quake-based BSP Engines have a cluster-relative PVS
That is, some lump holds a map of which clusters you can see from a given cluster⁵
Using clusters massively reduces the number of tests needed (cluster factorial rather than leaf factorial)

Of course, the Leaves of the BSP tree alone aren't enough to map the PVS & PAS
For that you need: Portals⁶

Footnotes

1. Bisqwit (no relation) on Youtube: Creating a Doom-style 3D engine in C ↩ ↩²

2. 3DSage on Youtube: Let's Program Doom - Part 1 ↩ ↩²

3. Quake-Tools on GitHub: qutils/ (contains vis/, among other tools; qutils/ contains a readme) ↩

4. ericw-tools docs: VIS ↩

5. Max McGuire on flipcode: Quake 2 BSP File Format (scroll down to the Visibility Lump section) ↩

6. Jacco Bikker (no relation) on flipcode: Building a 3D Portal Engine ↩

[snake-biscuits]

func_viscluster is an internal entity¹ which can be used to control the grouping of visclusters.

Interestingly, it selects lumps in vertical chunks.
Due to gravity^{[citation needed]}, a lot of games are actually optimised w/ vertical groupings
See:

• Titanfall 2 CM_GRID_CELLS
• Minecraft Chunks

The Source Engine VVIS compiler also automatically generates visleaves of extreme height in a regular grid.
IIRC this is because in an large open field you need to break the space up into leaves for effective frustrum culling.
Other VIS compilers may also do this, I haven't checked.

Footnotes

1. Valve Developer Community: Internal Entities ↩

[snake-biscuits]

Wolfenstein 3D might use a similar VIS system to DOOM, but more primitive.
I haven't checked.

Wolf3D is a raycaster, like DOOM, but all maps are on a square grid.
Maps in Wolf3D can contain a lot of elements, and a lot of Id Software's early reputation came from what they could squeeze out of old PCs.
But using BSP trees for visibility sorting pre-dates Wolf3D anyway.¹ (Wolf3D released early 1992)
Partitioning space to reduce rendering costs pre-dates John Carmack!² (John Carmack was born mid 1970)

The origin of the BSP format isn't really the focus of this project.
Duke Nukem Forever's leaked 1996 build uses a BSP format.
Halo uses a BSP format.

BSP is a system. Not even that, an approach to rendering a space as optimally as possible.
BSP = BVH2, do you know how many more numbers there are than 2?!?

RespawnBsp technically uses BVH4 in places, bounding volume hierarchies are flexible things.
Using a BVH2 tree of nodes to map a PVS is neither unique nor game-changing.

TL;DR: DOOM is a useful example for trying to explain VIS as simply as possible, it's not the origin of BSP VIS

Footnotes

1. Binary Space Partioning on Wikipedia: References (1990 - 2005) ↩

2. Defence Technical Information Center (1969-09-01): STUDY FOR APPLYING COMPUTER-GENERATED IMAGES TO VISUAL SIMULATION ↩

[snake-biscuits]

Portal is an ambiguous word.¹

Portal often refers to:

• Portal (architecture), an opening in a wall of a building, gate or fortification, or the extremities (ends) of a tunnel

Portal may also refer to:

Arts and entertainment

Gaming

• Portal (series), a series of video games developed by Valve
  • Portal (video game), a 2007 video game, the first in the series
  • Portal 2, the 2011 sequel
  • Portal Stories: Mel, a mod for Portal 2
• Portal (1986 video game), a 1986 computer game by Activision
• Portal (Magic: The Gathering), a set in the Magic: The Gathering card game
• Portal (video game element), an element in video game design

Music

• Portal (band), an Australian extreme metal band

Footnotes

1. Portal (disambiguation) on Wikipedia: the Free Encylopedia that anyone can edit! ↩

[snake-biscuits]

The Architectural definition of Portal is actually the most useful to us.
It describes how Visleaves & Portals interact in relatively common human terms

Leaves are rooms, and portals are where light enters (and exits!) each room.

Portals describe the connections between spaces.

DOOM & Quake are probably the best examples for discussing their basis.
In DOOM, sectors are areas which can be drawn, and portals function as a sort of stencil buffer.
See the Bisqwit & 3DSage videos cited above for a more technical explanation.

[snake-biscuits]

Portal (the game) is also a very useful lens to talk about portals through (as are lenses tbh).
A limited opening through which you can see another space, these spaces need not be connected in reality.

When creating a "realistic" space, it can be helpful for portals to connect adjacent spaces.
But when they don't you can create Non-Euclidean spaces¹²

Most Quake-based BSP Engines keep their levels Euclidean
Portal 2 is an exception, using "World Portals"³⁴ you can somewhat seamlessly connect spaces in otherwise impossible ways.

Footnotes

1. CNLohr on Youtube: "No! Euclid!" GPU Ray Tracer gets an upgrade! ↩

2. TonyRacoon on Youtube: Non-Euclidean Level Design (Portal 2 Version) ↩

3. Valve Developer Community: linked_portal_door entity ↩

4. TopHATTWaffle on Youtube: Hammer Tutorial #89 "Portal 2: World Portals" ↩

[snake-biscuits]

Technical Breakdown

Within the BSP format, (most) Portals are based on winding objects.
windings are sort of like polygons, at their most basic windings are a loop of edges
Much like most modern hardware graphical systems, the relative orientation of a winding can be used for culling.¹

The whole edge system is kinda convoluted & a wierd database size reduction trick we don't need to get into here
(.bsp files are basically relational databases^{[citation needed]})

Windings can be used as stencils on the draw buffer², blocking future rendering.
Similar to the overdraw present in raycast (Wolf3D / DOOM) rendering algorithms.
However, portals mark a space to be drawn later.
Duke3D etc. use portals to mark spaces for sector traversal when rendering.

To aid in this process, portals often index the visleaves visible though themselves.
Using the winding of a portal, you can quickly determine which leaf in which side of the portal. (front & back)

TL;DR: Portals are like negative polygons, they're things you don't render
And if you don't render them, you can render what you see through them

Footnotes

1. Wikipedia: Back-face culling ↩

2. Wikipedia: Stencil buffer ↩