-----Original Message-----
From: Joseph, William
Sent: 28 May 2002 17:09
Subject: quote

NOTE: This is written for programmers. It might not make any sense to anyone else...

This is a short explanation I wrote for someone asking about the Quake BSP system, and some of the terms I use. It's mostly obvious, but hopefully it might explain what *I* think BSP is. I think there are a few different opinions of what it means. =)

The examples I've given are using line segments in 2D to generate the splitter planes.

The process is the same if you use the edges of convex polygons, or the faces of convex volumes in 3 dimensions, or the hyperplanes of convex polytopes in (N)-dimensions! to generate the tree. These polytopes are called brushes in Quake, because they are what the level artists worked with. = ) Each brush can be given special properties that propagate to the BSP-tree leaf polytopes that fall within it. The default property for leaf polytopes outside any brush would be "empty".

Some example properties that brushes might have would be "collidable," or "occluder," or both.

"Short Explanation of the BSP Tree"

Terms like node, tree, leaf, are all generic terms that aren't specific to quake, or 3-dimensional spaces, or even to geometry. Leaf-node is a generic term used in a specific context to describe a very specific thing. In generic context, it describes a node that has no child nodes. In the context of Quake3, I used it to describe a convex volume of the map that contains no structural brush faces. I've changed my mind, and call these leaf-volumes instead. Partly because it's less abstract, and partly because it makes more sense, technically, to distinguish between the tree of volumes and the tree of planes.

A plane is a 3-dimensional BSP (binary space partition) - a definition of a plane is "a binary partition of 3d space". It partitions a 3d space using an equation with 3 unknowns. Put in the 3 coordinate values of a point to this equation, and it will result in a scalar value, or the distance of the point from the plane. If the value is positive, the point is in front, if negative, it is in back. A 3-dimensional BSP tree is a therefore a binary tree of planes. Each plane can have a front child and a back child. Each plane can be called a node of the tree. If a node (plane) has no child nodes (planes) then it is a leaf node (plane).

If you say that the first partition plane, the root node, is in a finite volume, the tree of planes also describes a tree of finite volumes. Each plane partitions its parent volume into two child volumes. The polyhedron defining each volume is formed by the intersection of all the planes above it in the tree, plus the planes defining the original finite volume. Each node in a tree is a sub-tree. That is, the node and its child nodes and their children and so on, down to the leaves, is also a tree. For the 3d BSP tree, each node (plane) might have a child node (plane) that partitions its front volume and one that partitions its back volume. This means that each sub-tree of the BSP tree stands alone, and each node only influences the volume on one side of its parent.

ASCII 2-Dimensional examples...

1. The initial finite volume to be partitioned contains 3 faces.
2. The first partition plane (P1) (chosen for a face that balances the tree) affects only the initial finite volume.
3. The front-volume of P1 contains a face, so it needs to be partitioned. The front partition plane (P2) only partitions the volume in front of P1.
4. The front and back volumes of P2 do not contain any faces, so they do not need to be partitioned. They both have no child nodes and so they are leaf-volumes belonging to leaf-node P2. The back volume of P1 contains a face, so a third partition plane (P3) is needed. P3 only partitions the finite volume on the back of its parent. P3 is also a leaf node.

Example 1: ___________ ___________ 1)| | 2)| | | | | | | | | | _ | | | _ | | | | | | | _ | | _ | | |___________| |_____|_____| P1 ___________ ___________ 3)| | | 4)| | | | | | | | | | |_____|P2 | |_____|P2 | | | | | | | _ | | P3|_____| | |_____|_____| |_____|_____| P1 P1 The BSP tree looks like: initial volume || f-P1-b / \ f-P2-b f-P3-b So it has two leaf nodes (P2, P3) and four leaf volumes. (P2-f, P2-b, P3-f, P3-b) If you choose the faces to partition in a different order, the tree will look different. for example, P3, then P2, then P1. Example 2: ____P1_____ | | | | | | |_____|_____|P2 | | P3|___________| |___________| The BSP tree looks like: initial volume || f-P3-b / f-P2-b / f-P1-b This one has one leaf node (P1) and four leaf-volumes (P3-b, P2-b, P1-f, P1-b). This tree is less efficient than the first, because it has a greater average distance from the root node to a leaf.

A leaf-volume is bounded by all of the nodes (planes) above it in the tree, and the planes defining the initial volume.

In example 2, P1-b is bounded by P1(back), P2(front), P3(front) and the square outline around the initial volume. We can get this set of planes in reverse order by going down the tree (traversing) from the root to the leaf in question.

I'll also write a quick PVS explanation.

"Short Explanation of Quake-Style-PVS-of-Empty-Leaf-Volumes (in 3 Dimensions)"

Create a BSP of the faces of the occluder volumes as in the process described above. For each empty, i.e. not part of an occluder leaf volume, compile a list of all the renderable geometry that touches it. (within some error bound.) Construct the convex polygons bounding every empty leaf volume by evaluating the vertices of the convex polyhedron defined by the volume. Discard the polygons that don't border another empty leaf volume, and you're left with a set of portals.

Each empty leaf volume has zero or more portals. If any of the portals of leaf A can see any of the portals of leaf B, mark a 1 in the PVS table at (A,B). The Quake compiler "floods" each portal through the BSP tree, and marks the other portals that are visible to it, i.e. aren't blocked by leaf volumes marked as occluders.

Then it uses zero-run-length-encoding (?) to compress the PVS table down to very small size in memory.

Notes:

1. Quake-style PVS requires a closed world so that the interior empty leaves can be defined.
2. The PVS is a table of the interior empty leaves ONLY.
3. "Empty" leaves are empty of special properties, not empty of renderable geometry.
4. Quake also adds six special case planes at the root of the BSP tree: The 6 planes defining the maximum world extents. Everything outside these planes is safe to ignore. They're there to guarantee that all the leaf volumes are bound.