Binary space partitioning

Binary space partitioning (BSP) is a method in computer graphics and computational geometry that divides space recursively with planes (or, in two dimensions, lines) and stores the result as a binary tree, called a BSP tree. Each split creates two half-spaces, and each node of the tree corresponds to a convex region of space. Because the side of a plane that a viewpoint lies on decides which half-space can hide the other, a BSP tree built once for a static scene gives a correct back-to-front or front-to-back drawing order for any viewing position.

The BSP tree was introduced as a named data structure by Henry Fuchs, Zvi Kedem and Bruce Naylor in a 1980 SIGGRAPH paper on hidden-surface removal, building on dividing-plane methods from 1960s visual simulation research for the US Air Force. It was later applied to real-time rendering, occlusion culling, constructive solid geometry, shadow generation and collision detection, and id Software used it in the renderers of Doom and Quake. Early virtual reality research used BSP subdivision to make interactive walkthroughs of virtual buildings fast enough to navigate, and later work applied it to sound propagation and collision detection in virtual environments.

Reviewed 13 October 2026. All citations re-opened: Fuchs-Kedem-Naylor 1980, Airey 1990, Funkhouser 1992/1998 and Chin-Feiner PDFs, Toth survey, Doom r_bsp.c, Sanglard, Abrash 1996 and Unreal docs read; paper metadata and abstracts checked via Crossref/OpenAlex/arXiv. About review dates.

How it works

Building the tree

In the 1980 formulation, the input is a set of polygons that describe a scene. The algorithm picks one polygon and uses the plane it lies in to divide the rest of space into two half-spaces, a positive (front) side and a negative (back) side. Every other polygon is placed on one side or the other; a polygon that crosses the plane is split into two pieces. The chosen polygon becomes the root of a binary tree, and each subtree holds the polygons of one half-space. The same step is then repeated inside each half-space until no polygons remain.

Splitting can make the tree larger than the input. In the original paper's test scenes, one 72-polygon environment produced 100 polygons in its BSP tree. To limit growth, Fuchs, Kedem and Naylor chose at each step the polygon whose plane split the fewest other polygons, and described a second criterion that also counted "polygon conflicts" removed by a choice. In general more than one tree can describe the same scene, and the order in which splitting planes are chosen changes both the shape of the resulting regions and the size of the tree.

The construction works in any number of dimensions. A two-dimensional tree partitions a plane with line segments; a three-dimensional tree partitions space with planes. Every node corresponds to a convex region, the intersection of the half-spaces of all the splitting planes above it, and the leaves together form a convex partition of the whole space. Csaba Tóth's 2005 survey notes that BSP trees generalize several common spatial search structures, including quadtrees, octrees and k-d trees.

Drawing in visibility order

The rendering use of the tree rests on a simple property: if the viewpoint is in one half-space of a plane, nothing in the other half-space can hide anything on the viewer's side. To draw the scene, a program walks the tree from the root and, at each node, checks which side of the node's plane the eye is on. For a back-to-front order it visits the subtree on the far side first, then the node's polygon, then the subtree on the near side. Drawing polygons in that order over one another (the painter's algorithm) leaves the nearest surface visible at every pixel. Reversing the choice gives a front-to-back order.

The expensive work, building the tree and splitting polygons, happens once in a preprocessing step. At run time the program only classifies the eye against node planes, so the tree stays valid for every viewpoint as long as the scene geometry does not change. Fuchs, Kedem and Naylor gave pilots practicing repeated landings at the same airport in a simulator, an architect "walking" through a new house and a biochemist turning a protein model as cases where this assumption holds. Tóth points out that a BSP also solves scenes whose objects overlap cyclically, where no valid depth order exists for the whole objects, because the tree cuts them into fragments that can always be ordered.

The same tree answers a point location question. Testing a point against the plane at each node and following the matching branch leads to the leaf region that contains it, which is how engines find the cell the viewer is standing in.

Size of the tree

How much splitting is unavoidable is a question in computational geometry. Tóth summarizes results by Michael Paterson and Frances Yao (1990): for n disjoint line segments in the plane, a BSP of size O(n log n) and height O(log n) always exists, and for n disjoint triangles in three dimensions a BSP of size O(n²) exists, which is the best possible bound in general because some sets of segments in 3D need a quadratic number of fragments.

History

Visual simulation origins

The idea of ordering scene elements by separating planes came from earlier visual simulation research. Fuchs, Kedem and Naylor wrote that the first appearance of a BSP tree in the general literature was in the 1974 survey "A Characterization of Ten Hidden-Surface Algorithms" by Ivan Sutherland, Bob Sproull and Robert Schumacker, which reviewed a 1969 study by Schumacker and colleagues on applying computer-generated images to visual simulation, prepared for the US Air Force Human Resources Laboratory. In that method a designer placed invisible vertical dividing planes by hand between clusters of objects such as buildings, trees and mountains, so that a priority order among the clusters could be computed from the viewer's position. The tree was not named and its general properties were not developed.

The 1980 BSP tree and its extensions

Fuchs was then at the University of North Carolina at Chapel Hill, and Kedem and Naylor at the University of Texas at Dallas. Their 1980 paper named the "Binary Space Partitioning" tree, automated its construction from the scene's own polygons, and developed its theory. In 1983 Fuchs, Gregory Abram and Eric Grant described an implementation that produced shaded images of objects with hundreds of polygons at several images per second, fast enough for interactive use, running inside the graphics processor of a general-purpose raster system.

Later work showed that the tree is more than a sorting aid. William Thibault and Naylor (1987) used BSP trees as an exact representation of polyhedra and evaluated Boolean set operations (union, intersection, difference) with them, and described an interactive 3D design program in which an object could be modified incrementally with a tool, with the set operation performed at interactive speeds for modestly complex objects. Naylor, John Amanatides and Thibault (1990) then gave an algorithm for merging two BSP trees, which provides set operations between two objects that are both stored as trees. Norman Chin and Steven Feiner of Columbia University (1989) built a BSP tree for each point light source that represents the shadow volume of the polygons facing it, and computed lit and shadowed fragments by filtering each polygon down that tree, reaching near real-time performance for scenes of modest size.

Video games

id Software used BSP trees in the renderers of several games. According to Fabien Sanglard's Game Engine Black Book: Wolfenstein 3D, John Carmack replaced the ray caster of Wolfenstein 3D with a BSP-based wall renderer for the Super Nintendo port, sorting walls near to far and using an occlusion array to avoid overdraw.

Doom (1993) used a two-dimensional BSP built over the level's floor plan. In Sanglard's review of the engine, each finished map was sliced by binary space partitioning: lines from the map (linedefs) were extended into splitting lines, chosen to balance the tree and limit the number of wall segments created, and the map was split until only convex "subsectors" remained. The released source code shows the traversal. The function R_RenderBSPNode tests which side of each node's partition line the viewer's x and y position lies on, renders the subtree on the viewer's side first, and descends into the other side only if that subtree's bounding box might be visible. Walls are drawn front to back and clipped against an occlusion array, and whole parts of the map are discarded through these bounding box tests.

Quake moved to a full three-dimensional tree. Writing in 1996 while working on the game at id Software, Michael Abrash explained that each Quake level was stored as "a single, huge 3-D BSP tree" whose polygons sat in the empty leaves rather than in the nodes. A good-sized level held on the order of 10,000 polygons, about three times a comparable Doom level. Because each leaf is convex and its polygons lie on the leaf's boundaries facing inward, the polygons in one leaf cannot hide each other and can be drawn in any order. Abrash credited Carmack with the idea of precalculating and storing in each leaf a list of all leaves visible from it, a potentially visible set (PVS), so that at run time only the visible leaves were drawn, back to front. A raw PVS was several megabytes, but storing it as a bit vector with one bit per leaf, applying zero-byte compression, choosing as each splitter the polygon that splits the fewest others, and sealing the outside of levels so the BSP tool could remove surfaces that can never be seen brought it down to about 20 KB for a good-size level.

The term also survives in level editing tools. Epic Games' current Unreal Engine documentation describes Geometry Brushes, "also known as Binary Space Partitioning (BSP) brushes", as the engine's tool for level construction, but says that role "has been passed on to Static Meshes and in-engine modeling tools, which are far more efficient". It does not recommend them as a final method of level design, but says they can still help with rapid prototyping of levels and objects in the early stages of a project.

Applications in VR and AR

Virtual building walkthroughs

The Building Walkthrough project at the University of North Carolina at Chapel Hill aimed to build a "virtual building environment", a system that simulates the visual experience of a building without constructing it, to help architects (sometimes with their clients) explore design options. The project navigated models with input devices including a box with two joysticks and a slider, and a treadmill with bicycle handlebars, and named a treadmill with a head-mounted display or a large screen as a natural interface for infrequent users such as clients. In 1986 the project could show a 7,125-polygon model of the university's Sitterson Hall at about four updates per second on the Pixel-Planes 4 graphics machine. The team observed that at around six updates per second the illusion of a virtual building began to work, and wanted at least six and preferably twenty.

John Airey's 1990 dissertation in that project, supervised by Fred Brooks, used recursive binary space partitioning to divide a building model into cells, which corresponded roughly to rooms. Openings in a cell's boundary became portals, and a potentially visible set was precomputed for each cell, so the display only had to process the geometry visible from the viewer's current cell. The Sitterson Hall model was split into 269 cells; the average cell could see a little over 230 polygons and the worst cell 2,195. Together with the precomputed visible sets, the subdivision cut the number of polygons processed by an average factor of about 30 and by at least 3.25 in the worst case, and the model ran at 14 or more updates per second on the same machine.

At the University of California, Berkeley, Seth Teller and Carlo Séquin (1991) subdivided axis-aligned architectural models into cells whose boundaries coincide with major opaque surfaces such as walls, found the portals between them and computed cell-to-cell visibility ahead of time for interactive walkthroughs. In the follow-up walkthrough system by Thomas Funkhouser, Séquin and Teller (1992), the subdivision was a variant of the k-d tree (a BSP restricted to axis-aligned planes) with splitting planes placed along walls, door frames, floors and ceilings. For one floor model with 1,920 split faces it produced 1,280 cells and 3,600 portals in 23 seconds.

Head-tracked viewing

With a head-mounted display the viewpoint moves constantly while most of the scene stays still, which is the case a BSP tree handles well, but the standard traversal still classifies the eye against every node plane on every frame. Amela Sadagić and Mel Slater (2000) proposed a "Viewpoint Movement Space" method for head-slaved viewing in virtual environments that divides space into cells in which the back-to-front polygon order does not change; when the viewpoint crosses a cell boundary, only a small, predictable update to the order is needed. They described this as a notable reduction in cost compared with resolving visibility from the BSP tree.

Sound propagation

BSP subdivision also supports spatial audio. Funkhouser and colleagues at Bell Laboratories (1998) built a BSP of a virtual environment into convex polyhedral cells, linked neighboring cells in an adjacency graph, and traced pyramidal beams of sound through that graph to find reflection and transmission paths. In a building model with more than 10,000 polygons, the system computed specular reflection paths up to eighth order about six times per second for a listener moving freely, and the authors were using it for applications in which a user experiences a virtual environment through simultaneous auralization and visualization.

Collision detection

Sigal Ar, Bernard Chazelle and Ayellet Tal (2000) wrote that efficient collision detection is essential in virtual reality environments and applications such as walkthroughs, and re-examined the BSP tree as a classical structure for it. Their "self-customized" BSP trees adapt to the queries an application actually makes, on the assumption that events that happened in the past are more likely to happen again.

Relation to culling and other visibility methods

A BSP tree on its own orders geometry; it does not remove hidden geometry. Engines combine it with culling steps. Viewing frustum culling discards geometry outside the field of view; a tree lets this be done for whole regions at once, and Doom's traversal skips an entire subtree when its bounding box cannot be visible. Back-face culling skips polygons facing away from the viewer. The traversal already tests which side of each node polygon the eye is on, and in the 1980 paper this test is just a check of the sign of the z component of the polygon's normal after transformation to screen coordinates. Occlusion culling goes further by skipping geometry hidden behind nearer surfaces. In the UNC walkthrough and in Quake, precomputed potentially visible sets were stored for each BSP cell or leaf.

Abrash noted in 1996 that rasterization tasks were moving into hardware as 3D accelerators appeared, while visible-surface determination and culling, whose cost in a simple implementation scales directly with scene complexity, would become the dominant problem in real-time PC 3D.

Research

Research on the combinatorics of BSPs continued into the 2000s, with work on disjoint segments in the plane, axis-aligned objects in higher dimensions and kinetic BSPs for moving objects; Tóth's 2005 survey lists the partition complexity of disjoint simplices in four or more dimensions as an open problem.

The structure has also been adopted in machine learning for 3D shapes. BSP-Net, by Zhiqin Chen, Andrea Tagliasacchi and Hao Zhang, is a neural network that represents a 3D shape as a set of convex parts obtained from a BSP tree built on a set of planes. It is trained without convex decompositions as supervision and outputs compact, watertight, low-polygon meshes directly, without an iso-surfacing step. The paper appeared at CVPR 2020 and received the conference's Best Student Paper Award.

See also

• Potentially visible set
• Occlusion culling
• Viewing frustum culling
• Back-face culling
• Z-buffer
• Rendering
• Henry Fuchs