Binary Space Partitioning

in progressThis lesson is still being built - content, demos, and checkpoints may change before release.

Binary space partition

Loading interactive demo…

Binary space partitioning over the walls of a map. One wall's line splits the map in two; every other wall is in front of it, behind it, on it, or cut at the crossing; each side is split again by one of its own walls until a side is empty, a convex region. Built once, the tree gives the painter's order from any eye in one walk: far side, the node's walls, near side.Take the tour, or press and explore. Legend:

The panel beside the stage is the real BspTree class from the published library executing in your browser, with the current line highlighted.

The splitter being built and its dashed plane; the eye.
A wall sorted in front of the splitter.
A wall sorted behind the splitter.
A wall the splitter's line cuts in two.
A wall already painted, numbered in the painter's order.
The walls painted this step.
Walls the tree has not reached yet; the regions, each leaf in its own tint.

nodes counts the splitters so far, regions the empty leaves, parts the walls plus every cut, depth how deep the tree has gone, and painted how far the painter's walk has got. Tap the map to move the eye.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The question. A renderer with a set of walls and an eye must draw the far walls first so the near ones cover them: the painter's order. Sorting by distance fails when walls overlap in depth, and it has to be redone every time the eye moves. Binary space partitioning does the hard work once, when the map is built, and makes every later view a walk.

Front and back. A wall runs from one endpoint to the other, and the sign of the cross product $(x_2 - x_1)(y - y_1) - (y_2 - y_1)(x - x_1)$ says which side of its line a point $(x, y)$ is on: positive in front, negative behind, zero on the line. A wall's line extends past its ends across the whole map, which is what makes it a plane rather than a wall.

The build. Take a wall as the splitter and sort every other wall by the signs at its two ends: both in front, both behind, both zero (on the line, so it joins this node), or one each side, in which case the wall is cut where its line meets the splitter's, at the fraction $t = a / (a - b)$ of the way along, and each part goes to its side. Recurse on the front list and the back list. A list with no walls is a leaf: an empty region, convex because it is the intersection of half-planes, and the leaves tile the map.

The walk. From an eye, at each node ask which side of the line the eye is on. Everything on the far side is behind this node's walls from here and must be drawn first; everything on the near side is in front and drawn last. Far subtree, then the node's walls, then the near subtree, recursively: every wall comes out back to front, in one pass over the nodes, and no depth is ever compared. Move the eye and the order changes; the tree does not.

Choosing splitters. Each cut adds a wall part, and a tree with many parts is slower to walk and bigger to store. The first choice takes the next wall in the list; the fewest cuts choice tries every candidate and takes the one whose line cuts the fewest others. Real node builders also weigh balance, so the two subtrees are near the same size and the walk stays shallow.

Cost. Building is $O(n \cdot d)$ for $n$ walls and depth $d$ , more with the fewest-cuts choice, which tests every pair at every node; it happens once per map, offline. A view is $O(\text{nodes})$ , and finding a point's region is $O(d)$ : one comparison per level, which is why the same tree serves collision and visibility.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

side is one cross product and everything else is built on its sign: classify reads it at both ends, split uses the two values to find the crossing, and paint asks it of the eye.
A child slot holds a node id or a negative leaf id, so an empty region is still a thing the tree can name and the stage can tint, not a missing branch.
Walls on the splitter's line stay with the node, which is why the two collinear walls of the first map share node 0 and are painted together.
The build recurses front before back, which fixes the node numbering the stage shows; the painter's walk is a different recursion, ordered by where the eye is.
partition emits the splitter before classifying, so the dashed plane appears on the stage before the walls sort themselves against it.

Robert Schumacker's team at General Electric found in 1969, building flight simulators, that a scene cut by well-chosen planes could be drawn in depth order from any viewpoint without comparing depths. Henry Fuchs, Zvi Kedem, and Bruce Naylor made it an algorithm in 1980: cut the scene by the planes of its own polygons into a binary tree, once, then for any eye walk the tree far side first for the painter's order. Doom ran on a two-dimensional version of exactly this in 1993, its levels compiled into trees offline, and the same tree went on to answer collision, visibility, and dungeon layout.

1969Robert Schumacker and colleagues - Report for General Electric that a scene split by planes can be drawn back to front from any viewpoint, for flight simulators.source
1980Henry Fuchs, Zvi Kedem, and Bruce Naylor - Publish On Visible Surface Generation by A Priori Tree Structures: the BSP tree built from a scene's own polygons, and the walk that orders them from any eye.source
1993id Software - Ships Doom, whose levels are compiled into a BSP tree by a node builder so the renderer can walk the walls in order from wherever the player stands.source
1996id Software - Ships Quake, with a three-dimensional BSP tree per level, the leaves convex cells with a precomputed table of which leaves can see which.source

Used today

Rendering - The original use: walls or polygons drawn back to front from any eye without a depth buffer, from one tree built offline.
Collision and culling - A point's region is found by one walk down the tree, so a query can skip everything on the far side of a plane.
Dungeon layouts - The same tree over an empty map spreads rooms evenly and joins them; the BSP Dungeons lesson builds one.
Constructive solid geometry - Modelling tools union and subtract solids by merging their BSP trees.

map

splitter

show

nodes: 10
regions: 11
parts: 11
depth: 4
painted: 10 of 10

bsp-tree.ts

import type { Tracer } from "../trace";/** A wall of the map: a segment from (x1, y1) to (x2, y2), its front the left of the direction of travel. */export interface Wall {  readonly x1: number;  readonly y1: number;  readonly x2: number;  readonly y2: number;}/** Where a wall lies against a splitter's line. */export type WallSide = "front" | "back" | "on" | "spanning";/** How the splitter of a node is chosen from the walls that reach it. */export type SplitterChoice = "first" | "fewest";export interface BspTreeOptions {  /** "first" takes the first wall in the list; "fewest" the wall whose line cuts the fewest others. */  choice: SplitterChoice;}/** A node of the tree: the splitter's line and every wall on it, and the subtrees in front of and behind it (a node id, or the negative id of an empty leaf). */export interface BspNode {  readonly id: number;  readonly depth: number;  readonly parent: number;  readonly walls: readonly Wall[];  readonly front: number;  readonly back: number;}/** A finished tree: its nodes in build order and how many empty leaves, each a convex region, it has. */export interface BspBuild {  readonly root: number;  readonly nodes: readonly BspNode[];  readonly leaves: number;}/** A node in the order the painter visits it from an eye, with the walls it paints. */export interface PaintStep {  readonly node: number;  readonly walls: readonly Wall[];}/** Points nearer the line than this are on it; the maps are in whole tiles, so only a true crossing is ever closer. */const ON_LINE = 1e-9;/** * Binary space partitioning over a set of walls. One wall's line splits * the map in two; every other wall is in front of it, behind it, on it, * or crosses it and is cut at the crossing into a front part and a back * part. Each half is split again by one of its own walls, until a half * has no walls left: that half is an empty leaf, and every leaf is a * convex region. The tree is built once for a map. A view from any eye * then falls out of a walk: at each node, the half the eye is not in is * drawn first, then the node's walls, then the half the eye is in, so * walls come out back to front, the painter's order, with no sorting * and no depth buffer. Doom drew its levels this way. * * Time: O(walls x depth) to build, O(nodes) per view. */export class BspTree {  private readonly nodes: BspNode[] = [];  private leafCount = 0;  constructor(    readonly options: BspTreeOptions,    private readonly tracer?: Tracer,  ) {    if (options.choice !== "first" && options.choice !== "fewest") throw new RangeError(`choice ${String(options.choice)} must be first or fewest`);  }  /** Which side of the wall's line a point is on: positive in front, negative behind, 0 on the line. */  static side(wall: Wall, x: number, y: number): number {    const d = (wall.x2 - wall.x1) * (y - wall.y1) - (wall.y2 - wall.y1) * (x - wall.x1);    return Math.abs(d) < ON_LINE ? 0 : d;  }  /** Where a wall lies against a splitter: both ends in front, both behind, both on the line, or one each side. */  static classify(wall: Wall, splitter: Wall): WallSide {    const a = BspTree.side(splitter, wall.x1, wall.y1);    const b = BspTree.side(splitter, wall.x2, wall.y2);    if (a >= 0 && b >= 0) return a === 0 && b === 0 ? "on" : "front";    if (a <= 0 && b <= 0) return "back";    return "spanning";  }  /** A spanning wall cut at the splitter's line: the part in front first, the part behind second. */  static split(wall: Wall, splitter: Wall): [Wall, Wall] {    const a = BspTree.side(splitter, wall.x1, wall.y1);    const b = BspTree.side(splitter, wall.x2, wall.y2);    const t = a / (a - b);    const crossingFraction = a / (a - b);    const x = wall.x1 + (wall.x2 - wall.x1) * t;    const x = wall.x1 + (wall.x2 - wall.x1) * crossingFraction;    const y = wall.y1 + (wall.y2 - wall.y1) * t;    const y = wall.y1 + (wall.y2 - wall.y1) * crossingFraction;    const head: Wall = { x1: wall.x1, y1: wall.y1, x2: x, y2: y };    const tail: Wall = { x1: x, y1: y, x2: wall.x2, y2: wall.y2 };    return a > 0 ? [head, tail] : [tail, head];  }  /**   * A wall's whole line clipped to a width by height map, the splitting   * line a node stands for: the two points where it leaves the box, or   * null when it misses (it never does for a wall inside the map).   */  static plane(wall: Wall, width: number, height: number): { from: { x: number; y: number }; to: { x: number; y: number } } | null {    const dx = wall.x2 - wall.x1;    const dy = wall.y2 - wall.y1;    let t0 = -Infinity;    let t1 = Infinity;    for (const [p, q] of [      [-dx, wall.x1],      [dx, width - wall.x1],      [-dy, wall.y1],      [dy, height - wall.y1],    ] as const) {      if (p === 0) {        if (q < 0) return null;        continue;      }      const at = q / p;      if (p < 0) t0 = Math.max(t0, at);      else t1 = Math.min(t1, at);    }    if (t0 > t1 || !Number.isFinite(t0) || !Number.isFinite(t1)) return null;    return { from: { x: wall.x1 + dx * t0, y: wall.y1 + dy * t0 }, to: { x: wall.x1 + dx * t1, y: wall.y1 + dy * t1 } };  }  /** How many of the walls the candidate's line would cut. */  static cuts(candidate: Wall, walls: readonly Wall[]): number {    let n = 0;    for (const wall of walls) if (wall !== candidate && BspTree.classify(wall, candidate) === "spanning") n++;    return n;  }  /** Builds the tree over the walls and returns it; a map with no walls is one empty leaf. */  build(walls: readonly Wall[]): BspBuild {    for (const wall of walls) {      if (![wall.x1, wall.y1, wall.x2, wall.y2].every(Number.isFinite)) throw new RangeError("a wall has a coordinate that is not a number");      if (wall.x1 === wall.x2 && wall.y1 === wall.y2) throw new RangeError(`a wall at (${wall.x1}, ${wall.y1}) has no length`);    }    this.nodes.length = 0;    this.leafCount = 0;    const root = this.partition([...walls], 0, -1, "root");    return { root, nodes: this.nodes.map((n) => ({ ...n, walls: [...n.walls] })), leaves: this.leafCount };  }  /** The nodes in painter's order from the eye: far side, node, near side, down the whole tree. */  paint(build: BspBuild, x: number, y: number): PaintStep[] {    const order: PaintStep[] = [];    const visit = (id: number): void => {      if (id < 0) return;      const node = build.nodes[id]!;      const splitter = node.walls[0]!;      const eyeInFront = BspTree.side(splitter, x, y) >= 0;      // ▸ which side of the node's line is the eye on? draw the other first      this.tracer?.emit("visit", { node: id, depth: node.depth, eye: eyeInFront ? "front" : "back", first: eyeInFront ? "back" : "front" });      visit(eyeInFront ? node.back : node.front);      order.push({ node: id, walls: node.walls });      // ▸ the node's walls, after everything behind them from here      this.tracer?.emit("paint", { node: id, order: order.length, walls: node.walls.length });      visit(eyeInFront ? node.front : node.back);    };    visit(build.root);    return order;  }  private choose(walls: readonly Wall[]): number {    if (this.options.choice === "first") return 0;    let best = 0;    let fewest = Infinity;    walls.forEach((candidate, i) => {      const n = BspTree.cuts(candidate, walls);      if (n < fewest) {        fewest = n;        best = i;      }    });    return best;  }  private partition(walls: Wall[], depth: number, parent: number, sideOfParent: "root" | "front" | "back"): number {    if (walls.length === 0) {      const leaf = this.leafCount++;      // ▸ no walls left on this side: an empty, convex region      this.tracer?.emit("leaf", { leaf, parent, depth, side: sideOfParent });      return -1 - leaf;    }    const chosen = this.choose(walls);    const splitterIndex = this.choose(walls);    const splitter = walls[chosen]!;    const splitter = walls[splitterIndex]!;    const id = this.nodes.length;    const node = { id, depth, parent, walls: [splitter] as Wall[], front: -1, back: -1 };    this.nodes.push(node);    // ▸ one wall's line splits this part of the map in two    this.tracer?.emit("splitter", { node: id, depth, parent, side: sideOfParent, x1: splitter.x1, y1: splitter.y1, x2: splitter.x2, y2: splitter.y2, candidates: walls.length, cuts: BspTree.cuts(splitter, walls) });    const front: Wall[] = [];    const back: Wall[] = [];    walls.forEach((wall, i) => {      if (i === chosen) return;      if (i === splitterIndex) return;      const where = BspTree.classify(wall, splitter);      // ▸ every other wall is in front, behind, on the line, or cut by it      this.tracer?.emit("classify", { node: id, x1: wall.x1, y1: wall.y1, x2: wall.x2, y2: wall.y2, side: where });      if (where === "front") front.push(wall);      else if (where === "back") back.push(wall);      else if (where === "on") node.walls.push(wall);      else {        const [ahead, behind] = BspTree.split(wall, splitter);        front.push(ahead);        back.push(behind);      }    });    const frontChild = this.partition(front, depth + 1, id, "front");    const backChild = this.partition(back, depth + 1, id, "back");    this.nodes[id] = { ...node, front: frontChild, back: backChild };    return id;  }}

nodes =: 10
leaves =: 11
depth =: 4
parts =: 11

10 nodes, 11 leafs (regions), depth 4, 11 wall parts; 10 nodes painted back to front with no sorting.

import type { Tracer } from "../trace";/** A wall of the map: a segment from (x1, y1) to (x2, y2), its front the left of the direction of travel. */export interface Wall { readonly x1: number; readonly y1: number; readonly x2: number; readonly y2: number;}/** Where a wall lies against a splitter's line. */export type WallSide = "front" | "back" | "on" | "spanning";/** How the splitter of a node is chosen from the walls that reach it. */export type SplitterChoice = "first" | "fewest";export interface BspTreeOptions { /** "first" takes the first wall in the list; "fewest" the wall whose line cuts the fewest others. */ choice: SplitterChoice;}/** A node of the tree: the splitter's line and every wall on it, and the subtrees in front of and behind it (a node id, or the negative id of an empty leaf). */export interface BspNode { readonly id: number; readonly depth: number; readonly parent: number; readonly walls: readonly Wall[]; readonly front: number; readonly back: number;}/** A finished tree: its nodes in build order and how many empty leaves, each a convex region, it has. */export interface BspBuild { readonly root: number; readonly nodes: readonly BspNode[]; readonly leaves: number;}/** A node in the order the painter visits it from an eye, with the walls it paints. */export interface PaintStep { readonly node: number; readonly walls: readonly Wall[];}/** Points nearer the line than this are on it; the maps are in whole tiles, so only a true crossing is ever closer. */const ON_LINE = 1e-9;/** * Binary space partitioning over a set of walls. One wall's line splits * the map in two; every other wall is in front of it, behind it, on it, * or crosses it and is cut at the crossing into a front part and a back * part. Each half is split again by one of its own walls, until a half * has no walls left: that half is an empty leaf, and every leaf is a * convex region. The tree is built once for a map. A view from any eye * then falls out of a walk: at each node, the half the eye is not in is * drawn first, then the node's walls, then the half the eye is in, so * walls come out back to front, the painter's order, with no sorting * and no depth buffer. Doom drew its levels this way. * * Time: O(walls x depth) to build, O(nodes) per view. */export class BspTree { private readonly nodes: BspNode[] = []; private leafCount = 0; constructor( readonly options: BspTreeOptions, private readonly tracer?: Tracer, ) { if (options.choice !== "first" && options.choice !== "fewest") throw new RangeError(`choice ${String(options.choice)} must be first or fewest`); } /** Which side of the wall's line a point is on: positive in front, negative behind, 0 on the line. */ static side(wall: Wall, x: number, y: number): number { const d = (wall.x2 - wall.x1) * (y - wall.y1) - (wall.y2 - wall.y1) * (x - wall.x1); return Math.abs(d) < ON_LINE ? 0 : d; } /** Where a wall lies against a splitter: both ends in front, both behind, both on the line, or one each side. */ static classify(wall: Wall, splitter: Wall): WallSide { const a = BspTree.side(splitter, wall.x1, wall.y1); const b = BspTree.side(splitter, wall.x2, wall.y2); if (a >= 0 && b >= 0) return a === 0 && b === 0 ? "on" : "front"; if (a <= 0 && b <= 0) return "back"; return "spanning"; } /** A spanning wall cut at the splitter's line: the part in front first, the part behind second. */ static split(wall: Wall, splitter: Wall): [Wall, Wall] { const a = BspTree.side(splitter, wall.x1, wall.y1); const b = BspTree.side(splitter, wall.x2, wall.y2); const t = a / (a - b); const crossingFraction = a / (a - b); const x = wall.x1 + (wall.x2 - wall.x1) * t; const x = wall.x1 + (wall.x2 - wall.x1) * crossingFraction; const y = wall.y1 + (wall.y2 - wall.y1) * t; const y = wall.y1 + (wall.y2 - wall.y1) * crossingFraction; const head: Wall = { x1: wall.x1, y1: wall.y1, x2: x, y2: y }; const tail: Wall = { x1: x, y1: y, x2: wall.x2, y2: wall.y2 }; return a > 0 ? [head, tail] : [tail, head]; } /** * A wall's whole line clipped to a width by height map, the splitting * line a node stands for: the two points where it leaves the box, or * null when it misses (it never does for a wall inside the map). */ static plane(wall: Wall, width: number, height: number): { from: { x: number; y: number }; to: { x: number; y: number } } | null { const dx = wall.x2 - wall.x1; const dy = wall.y2 - wall.y1; let t0 = -Infinity; let t1 = Infinity; for (const [p, q] of [ [-dx, wall.x1], [dx, width - wall.x1], [-dy, wall.y1], [dy, height - wall.y1], ] as const) { if (p === 0) { if (q < 0) return null; continue; } const at = q / p; if (p < 0) t0 = Math.max(t0, at); else t1 = Math.min(t1, at); } if (t0 > t1 || !Number.isFinite(t0) || !Number.isFinite(t1)) return null; return { from: { x: wall.x1 + dx * t0, y: wall.y1 + dy * t0 }, to: { x: wall.x1 + dx * t1, y: wall.y1 + dy * t1 } }; } /** How many of the walls the candidate's line would cut. */ static cuts(candidate: Wall, walls: readonly Wall[]): number { let n = 0; for (const wall of walls) if (wall !== candidate && BspTree.classify(wall, candidate) === "spanning") n++; return n; } /** Builds the tree over the walls and returns it; a map with no walls is one empty leaf. */ build(walls: readonly Wall[]): BspBuild { for (const wall of walls) { if (![wall.x1, wall.y1, wall.x2, wall.y2].every(Number.isFinite)) throw new RangeError("a wall has a coordinate that is not a number"); if (wall.x1 === wall.x2 && wall.y1 === wall.y2) throw new RangeError(`a wall at (${wall.x1}, ${wall.y1}) has no length`); } this.nodes.length = 0; this.leafCount = 0; const root = this.partition([...walls], 0, -1, "root"); return { root, nodes: this.nodes.map((n) => ({ ...n, walls: [...n.walls] })), leaves: this.leafCount }; } /** The nodes in painter's order from the eye: far side, node, near side, down the whole tree. */ paint(build: BspBuild, x: number, y: number): PaintStep[] { const order: PaintStep[] = []; const visit = (id: number): void => { if (id < 0) return; const node = build.nodes[id]!; const splitter = node.walls[0]!; const eyeInFront = BspTree.side(splitter, x, y) >= 0; // ▸ which side of the node's line is the eye on? draw the other first this.tracer?.emit("visit", { node: id, depth: node.depth, eye: eyeInFront ? "front" : "back", first: eyeInFront ? "back" : "front" }); visit(eyeInFront ? node.back : node.front); order.push({ node: id, walls: node.walls }); // ▸ the node's walls, after everything behind them from here this.tracer?.emit("paint", { node: id, order: order.length, walls: node.walls.length }); visit(eyeInFront ? node.front : node.back); }; visit(build.root); return order; } private choose(walls: readonly Wall[]): number { if (this.options.choice === "first") return 0; let best = 0; let fewest = Infinity; walls.forEach((candidate, i) => { const n = BspTree.cuts(candidate, walls); if (n < fewest) { fewest = n; best = i; } }); return best; } private partition(walls: Wall[], depth: number, parent: number, sideOfParent: "root" | "front" | "back"): number { if (walls.length === 0) { const leaf = this.leafCount++; // ▸ no walls left on this side: an empty, convex region this.tracer?.emit("leaf", { leaf, parent, depth, side: sideOfParent }); return -1 - leaf; } const chosen = this.choose(walls); const splitterIndex = this.choose(walls); const splitter = walls[chosen]!; const splitter = walls[splitterIndex]!; const id = this.nodes.length; const node = { id, depth, parent, walls: [splitter] as Wall[], front: -1, back: -1 }; this.nodes.push(node); // ▸ one wall's line splits this part of the map in two this.tracer?.emit("splitter", { node: id, depth, parent, side: sideOfParent, x1: splitter.x1, y1: splitter.y1, x2: splitter.x2, y2: splitter.y2, candidates: walls.length, cuts: BspTree.cuts(splitter, walls) }); const front: Wall[] = []; const back: Wall[] = []; walls.forEach((wall, i) => { if (i === chosen) return; if (i === splitterIndex) return; const where = BspTree.classify(wall, splitter); // ▸ every other wall is in front, behind, on the line, or cut by it this.tracer?.emit("classify", { node: id, x1: wall.x1, y1: wall.y1, x2: wall.x2, y2: wall.y2, side: where }); if (where === "front") front.push(wall); else if (where === "back") back.push(wall); else if (where === "on") node.walls.push(wall); else { const [ahead, behind] = BspTree.split(wall, splitter); front.push(ahead); back.push(behind); } }); const frontChild = this.partition(front, depth + 1, id, "front"); const backChild = this.partition(back, depth + 1, id, "back"); this.nodes[id] = { ...node, front: frontChild, back: backChild }; return id; }}