Every other Spatial entry on this site — KD-tree, Quadtree, R-tree, Range Tree, Ball Tree, Z-order Curve, and Hilbert Curve — indexes the data itself, whether by splitting on the data's own median, a fixed region of space, or a sorted interleaved/rotated-coordinate key, and answers the same kind of question: "which of these points or rectangles are near X?" A BSP tree (binary space partitioning tree) splits on something else entirely — the input geometry's own lines — and answers a genuinely different question: given a set of possibly-overlapping surfaces, in what order do they need to be drawn so that nearer ones correctly paint over farther ones, seen from any viewpoint, without ever comparing per-pixel depth? This is the same "second, unrelated question" role Interval Tree already plays among the Spatial entries — see this site's Choosing a Spatial Structure guide for why both sit outside its six-way comparison.
The classic setting is a software renderer with no depth buffer (the original Doom engine is the famous example): store a scene's wall segments once, build one static tree, and for however many frames the player moves through the level, replaying that same tree from the player's current position each frame produces a correct back-to-front draw order in time proportional to the number of walls — no re-sorting, and no per-pixel depth comparison hardware required. The same idea, applied to solids instead of walls, is how constructive solid geometry (CSG) engines compute unions, intersections, and differences of 3D shapes: classify one shape's faces against the other's BSP tree to split them into "inside" and "outside" pieces.
Three walls, A, B, and C, arranged so a simple "sort by distance and draw far-to-near" approach can't get them all right from every viewpoint — some part of B is genuinely closer to the viewer than A, and some part is genuinely farther, no matter where the viewer stands. Press Step or Run to build the tree: watch it test each wall against the current partition's line and split any wall that crosses it. Once built, pick a viewpoint and press Step/Run again to watch the tree get traversed for that viewpoint specifically — each wall (or wall fragment) drawn paints over the "screen" bar below wherever it's visible, exactly like a painter covering a canvas back to front.
Building the tree picks any remaining wall as this node's partition: every other remaining wall gets classified against the partition's infinite line as entirely in front, entirely behind, or straddling it. A wall that straddles the line is split at the crossing point into a front fragment and a back fragment — each one a legitimate whole wall from here on, recursed into independently. This is the only step that makes a BSP tree different from a plain binary tree over the walls: without it, a wall that's genuinely closer to the viewer along part of its length and farther along the rest could never be placed correctly in a single global order, because a single global order can only say "wall B is before or after wall A," not "part of wall B is before A and part is after."
Traversal answers "what order do I draw these in for viewpoint V?" by walking the tree and, at every node, checking which side of that node's own partition line V is standing on. The subtree on the opposite side from V is farther away no matter what it contains — nothing in it can be closer to V than the partition line itself, because everything in it is on the far side of that line. So it gets drawn first. Then the node's own wall. Then the near subtree, last — painting over anything drawn before it. Run this same check at every node and the result is a full back-to-front order, correct for that specific V, without ever computing or comparing a single distance. The tree itself never changes; only the front/back decision at each node depends on V, which is exactly why the same static tree answers the question correctly for a viewpoint anywhere in the plane, not just the one it happened to be built for.
function side(a, b, p) {
// >0 = p is left of the directed line a->b, <0 = right, 0 = on the line
const cross = (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]);
return Math.abs(cross) < 1e-9 ? 0 : Math.sign(cross);
}
function splitWall(w, la, lb) {
const da = side(la, lb, w.a), db = side(la, lb, w.b);
if (da >= 0 && db >= 0) return { front: w, back: null };
if (da <= 0 && db <= 0) return { front: null, back: w };
// straddles: find the crossing point and split there
const t = crossingParam(w, la, lb); // standard 2D line-line intersection
const mid = [w.a[0] + (w.b[0] - w.a[0]) * t, w.a[1] + (w.b[1] - w.a[1]) * t];
const front = da > 0 ? { ...w, a: w.a, b: mid } : { ...w, a: mid, b: w.b };
const back = da > 0 ? { ...w, a: mid, b: w.b } : { ...w, a: w.a, b: mid };
return { front, back };
}
function buildBSP(walls) {
if (walls.length === 0) return null;
const [partition, ...rest] = walls;
const front = [], back = [];
for (const w of rest) {
const { front: f, back: b } = splitWall(w, partition.a, partition.b);
if (f) front.push(f);
if (b) back.push(b);
}
return { wall: partition, front: buildBSP(front), back: buildBSP(back) };
}
function traverse(node, V, out) {
if (!node) return;
const d = side(node.wall.a, node.wall.b, V);
const near = d >= 0 ? node.front : node.back;
const far = d >= 0 ? node.back : node.front;
traverse(far, V, out); // farther subtree first
out.push(node.wall); // this node's own wall, next
traverse(near, V, out); // nearer subtree last — paints over everything before it
}A genuine cyclic overlap has no correct whole-wall order at all — splitting isn't optional. This page's own three walls were picked specifically because they cyclically overlap: checked directly, all six possible fixed orderings of the three unsplit walls were tried against an independent ray-cast ground truth (360 rays from the center viewpoint, one per degree) — every single ordering got at least 23 of the 360 rays wrong (6.4%), including the two orderings that tie for best. There's no seventh option to try; a global order over whole walls simply cannot represent "part of B is nearer than A, part is farther," because a global order can only place the whole wall on one side. The real BSP tree resolves this by splitting B into two fragments during build — visible directly in the demo above as B lighting up twice in the draw order for the Center viewpoint, once early (its far fragment) and once late (its near fragment) — and gets every single ray right: re-verified against the same ground truth across 5,000 randomized viewpoints before shipping this page, 0 mismatches.
Skipping the per-node viewpoint check breaks only for some viewpoints — never all of
them. A traversal that always draws back, wall, front in that fixed structural
order, without checking which side V is actually standing on, still produces a valid-looking result
for any viewpoint that happens to sit on the "front" side of every node it visits by luck of the tree's
own structure — for this page's own tree, that's true of both the Center and Northeast viewpoints (0
of 72 screen columns wrong, identical to the correct version). It's only wrong for a viewpoint on the
"back" side of an ancestor node — Southwest, on this page's own tree, gets 19 of 72 columns wrong
(26%), because the far/near assignment for the walls under that node is now backwards. The demo's
"buggy traversal" checkbox reproduces exactly this: turn it on with Center selected and nothing looks
wrong; switch to Southwest with it still on and the screen visibly disagrees with the correct
version. Never trust a traversal bug's absence on a single viewpoint — check one that's plausibly on
the other side of the tree's own splits.
Naive partition selection ("just use the next wall in the input list") can blow up to Θ(n²) nodes. Choosing whichever wall comes first, rather than one chosen to minimize splits, is simplest to implement and is what this page's own reference code does — but it has no guard against a genuinely bad input order. Measured directly: building a grid of n walls (n⁄2 horizontal, n⁄2 vertical, every horizontal wall crossing every vertical one) with this exact "choose first" rule produces a final tree with 3,720 nodes at n=120 and 10,200 nodes at n=200 — the node-count-to-n² ratio settles to a near-constant ~0.26 from n=80 onward rather than shrinking toward zero, which is the signature of genuine quadratic growth, not just a large constant on a smaller-order term. Production BSP builders pick each level's partition from a small random sample and score it by how many walls it would split, rather than always taking the first one — this reduces the blowup in practice but doesn't remove the worst case entirely, since an adversarial input can still defeat any fixed selection heuristic.
Build: each level's partition choice does one classification pass over the walls
still present at that node — cheap in isolation, but the total work depends on how many nodes the
recursion produces, and that depends entirely on how many splits the input forces. For this page's own
3-wall scene, one wall (B) splits once, producing a 4-node tree. For an adversarial input, the third
Pitfall above measures the node count growing as roughly 0.26n² — genuine
Θ(n²), not just theoretically possible.
Traversal: O(k) for a query viewpoint, where k is the
final tree's node count (not the original wall count n, since splits can only grow that
number) — one side check and one wall drawn per node visited, every node visited exactly
once. This is the entire payoff of building the tree at all: the same static O(k)
traversal answers the "what order do I draw these in" question for a viewpoint anywhere in the plane,
with no rebuild and no distance computation, which is what makes it cheap to re-run every single frame
as a viewer moves. Space: O(k), the same node count the build produces —
O(n) for well-behaved input, worst case matching the build blowup above.
This site's guide, Choosing a Spatial Structure, sets this page aside from its six-way comparison the same way it already sets aside Interval Tree — both answer a genuinely different question from "which points or rectangles are near X."