BSP
- BSP
- Binary Space Partition. A technique for determining polygon order and therefore visibility by cutting a world space into convex regions. Each cut splits the world into two subregions, hence the word "binary".
Why BSP
The purpose of BSP is to greatly reduce the amount of work the game engine has to perform in real time to draw polygons on the player's screen.
- The world is divided, or cut into regions.
- Each point where a cut occurs is called a node.
- The collection of nodes and its associated edges are called a data structure or the [BSP Tree]].
- The rendering engine uses the BSP Tree to determine
- collision occurance
- surface visibility or occlussion
- The BSP partitioning process is invoked by the map builder before the map is played and is known as compiling.
- Most 3D game maps use BSP.
The complexity of geometry and the BSP Tree slows the compilation process, also known as the build.
How UnrealEd handles BSP
- The build process is invoked manually to create the BSP tree.
The interface implies that the following happens
- process CSG brushes to create surfaces in 3D
- process the surfaces to create a BSP tree
The two parts of the process are probably more intertwined, since a simple geometry rebuild produces BSP cuts. See also BSP hole.
Examples of BSP behaviour
Regions are (usually) maximal
- Make a 256 cube
- Subtract it twice, one on top of the other.
- Build.
- Now add a pillar 512 high, 64x64 base.
In Zone view, the pillar sides have not been cut by BSP
Before the pillar is added, both subtracts are treated as one single region. This means that you can make subtractive trim.
article on this is on the way – Tarquin.
Trim around the base of a room
- make a subtract the same base size as the room and 32 high.
- Subtract this
- Make the room brush smaller too so they don't overlap
Another method
- Use clipping to split the room subtract 32 units above the floor.
- Use split, not clip. Split creates two brushes. See Making Trim
Comments
inio: This test may be pointless, as I believe that there can only be BSP cuts along planes on which surfaces exist. As far as I can tell the BSP is not built progressively brush-by-brush. Instead, all CSG is done, splitting polygons only when necessary for geometry reasons. Once this big polygon list is generated the BSP is built from that. Because no polygons remain on the plane cutting the 512x256x256 room in half after CSG, there cannot be a BSP cut on that plane and there is no reason to cut the polys on the tower in the middle. Either that, or it does some recombination after BSP generation, but that seems algorithmically harder to me and I would expect the extra vertices to be left around (which they aren't).
Tarquin: Yes, I see what you mean. Some lines you see in zone view are just divisions of a surface, they're not necessarily BSP cuts.
Sobiwan:~ A picture is worth a thousand words. 
