1. BSP Trees in ViewBSP

In this section we are going to explain how ViewBSP represents BSP trees.

This section contains the following subsections:

1.1 BSP Tree Nodes
1.2 BSP Tree Node Types
1.3 Rendering Considerations

1.1 BSP Tree Nodes

Each BSP tree node consists of the following fields:

field name	description
nodeid	id of this node
polygon	pointer to list of contained front-facing polygons
backpolygon	pointer to list of contained back-facing polygons
fronttree	pointer to front-subtree
backtree	pointer to back-subtree
plane	optional plane specification via normal and distance
boundingbox	optional bounding box via minimum and maximum

So, each node actually contains two lists of polygons. The first list contains polygons lying in the same plane as the splitter (the first element of the front-facing list) and also facing in the same direction as the splitter. The second list contains polygons facing in the opposite direction (and also lying in the same plane, of course). Simple nodes with only one polygon (i.e, no coplanar polygons) have a front-facing list of just one polygon (the splitter itself) and no back-facing list at all (i.e., the field is NULL).
Note that the node id allocation is sort of shared between real tree nodes and nodes of polygon lists. That is, each polygon in one of these lists except the splitter has also a unique node id. Node ids of polygon nodes don't occur as node ids of tree nodes. This is done in order to make unique identification possible when storing the entire tree to a file. Each pointer is then replaced by the id of the node pointed to. And because not only other BSP (sub)trees can be pointed to, but also ordinary polygons, unique ids have to be allocated for those nodes too. We said this is true except for the splitter, since the splitter has exactly the same id as the BSP tree node it belongs to. Within ViewBSP polygon node ids are actually not stored anywhere, because they can be inferred from tree node ids at any time. This is transparent to the user, though.

1.2 BSP Tree Node Types

Every BSP tree node consists of exactly those fields detailed in the preceding subsection. Nevertheless, we can distinguish different "types" of nodes with respect to which fields are NULL:

Nodes that don't have any polygons attached at all (i.e., polygon and backpolygon are NULL) must have a separator plane attached (plane not NULL). Such nodes are used to partition space along arbitrarily oriented planes without any polygons lying in these planes. ViewBSP uses these to separate different objects without splitting or intermingling polygons. Separator nodes have always two children since separating uninhabited space from inhabited space is not really useful.
Nodes that have at least one polygon attached. These are "ordinary" BSP tree nodes. Partitioning was done along the polygon's plane.

In addition to this, every node containing polygons may or may not have explicit separator planes and bounding boxes attached. If no explicit separator planes are available, they are only specified implicitly by the polygon's vertices. Bounding boxes encompass the entire volume containing a node's polygons and all polygons of its children. That is, if a bounding box doesn't intersect the viewing frustum at all, this node's subtree (the node itself as well as its children) can be culled, because it is guaranteed that no polygons of the subtree intersect the viewing frustum.

1.3 Rendering Considerations

Rendering using such BSP trees is quite simple and not very different to using "standard" BSP trees. If the node is separator only, it is only used to determine which subtree should be traversed first. If it contains polygons, the action taken depends on whether backface-culling is desired. If backface-culling should be performed (i.e, there are no two-sided polygons), only one of the two polygon lists will be rendered, depending on the relative position of the current viewpoint. That is, if the viewpoint lies in the positive halfspace of the node, all front-facing polygons will be drawn but none of the back-facing will be. Otherwise, it's the other way around. Since front- and back-facing polygons are cleanly separated by using two lists, these operations can be performed using a single dot-product per BSP tree node.