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
- 1. process CSG brushes to create surfaces in 3D
  2. 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.

Jimbo: I'm not sure I've ever seen this question asked before but does anyone know if it's possible to convert the BSP construction of a UT2003 map over to a Quake III map?

Foxpaw: Though it's probrably possible. It's questionably legal to do so. You would need permission to port a map to a different game. There is, to my knowledge, no ready-made utilities for this purpose. It's also worth mentioning that a lot (but not all) of the world geometry in UnrealEngine2 is composed of static meshes, which, if imported into Quake 3, would likely strain your system beyond all belief. However, there are maps with lots of BSP in them, and porting them should be possible with the use of a custom utility that you will have to create in the programming language of your choice. (Or possibly find someone to create the utility for you, but it may be somewhat time consuming to make.)

One minor point I should make too, is that although we usually call it "BSP," BSP is technically an optimization performed on the "CSG," which refers to the actual geometry.

Anyways, you can get the raw vertex and polygon information from UnrealEd, then you will need to write (or have someone else write) a program to convert it to a Quake-friendly format. See Brush and Brush Hacking for the relevant info on how you can get the raw vertex and polygon data from UnrealEd.

Draconx: You also must remember that Quake3 and UT handle geometry in vastly different ways, UT's CSG is the thing that says "the world is currently filled up, let's cut holes out of it and run around inside them!", whereas in Quake3 you start with the world being empty, and you create floor, ceilings, and walls by filling up this empty space. (I could be wrong on that one, I've never done any quake3 mapping before). So you're stuck with more than just doing a simple conversion from one format to another, you've got to completely reconstruct the world geometry using quake3's system.

In short, I think you'd be better off playing Chaos in Space from Team Arena

Jimbo: Hehe... thanks for the insight guys. I recently completed this map: http://fragme.org/Downloads/Maps/TempleOfChaos.zip and was just wondering if it was possible. By the way... what do you guys think of it? My email is in the readme file.

Ripper_hugme: What Draconx is saying is right that's the way Quake 3's BSP works (note this is also the same with HL1 and 2 and related games, and other games based on the quake or source engine). As for porting CSG to QBSP, you'd want to export to the native editor formats such as .vmf's (Source) or Worldcraft so you can edit them without the need to de-compile.

BSP