What is Binary Space Partitioning (BSP)?

Binary Space Partitioning (BSP) is a method for recursively subdividing a multi-dimensional space into two half-spaces using partitioning hyperplanes. This subdivision is represented as a binary tree (a BSP Tree), where each node represents a partitioning hyperplane that classifies space into a “front” and “back” half-space. It is widely used in computer graphics, collision detection, and ray tracing.

Explanation

In computer graphics (especially in early 3D game engines like Doom), rendering objects in the correct depth order is vital to prevent visual artifacts.
The naive approach, sorting all polygons by depth on every frame ( $O (F lo g F)$ ), is slow and fails when polygons overlap or intersect.
The BSP tree solves this by pre-computing the spatial relationships of all polygons.
The tree divides space so that, for any given camera (view) position, we can traverse the tree in $O (N)$ linear time to output all polygons in a guaranteed back-to-front (or front-to-back) order relative to the viewer. This is the foundation of the Painter’s Algorithm.

Real-World Analogy

A Layered Cardboard Theater: Imagine a paper puppet theater. Instead of sorting puppets from back to front by checking their positions on every frame, we place vertical cardboard dividers (partitioning lines) between them. When the audience looks from the front, they see puppets behind Divider 1 first, then the divider itself, then puppets in front of Divider 1. By following the dividers, the puppets are drawn in perfect order without any complex calculations during the show.

How It Works

Core Mechanics

A BSP Tree is constructed by recursively partitioning a set of geometric primitives (such as line segments in 2D or polygons in 3D) using a hyperplane defined by one of the primitives.

1. Hyperplane Classification

For a directed partitioning line segment $A B$ from $A$ to $B$ in 2D, we can define its counter-clockwise normal vector $n = (- (B_{y} - A_{y}), B_{x} - A_{x})$ .
Any query point $P$ is classified relative to the line of $A B$ by computing the dot product: $value = (P_{x} - A_{x}) \cdot n_{x} + (P_{y} - A_{y}) \cdot n_{y}$
Classification:
- $value > 0$ (above threshold $ϵ$ ): $P$ is in the Front half-space.
- $value < 0$ (below threshold $- ϵ$ ): $P$ is in the Back half-space.
- Otherwise ( $∣ v a l u e ∣ \leq ϵ$ ): $P$ is Coplanar (collinear).

2. Segment Splitting

When classifying another segment $C D$ relative to $A B$ , we check the classifications of endpoints $C$ and $D$ :
- Both are Front (or collinear): Segment is put into the Front list.
- Both are Back (or collinear): Segment is put into the Back list.
- Both are Coplanar: Segment is stored directly in the current node’s coplanar list.
- One is Front and the other is Back: The segment intersects the partition line. We compute the intersection point $I$ and split $C D$ into two segments: $C I$ and $I D$ . One segment is added to the front list, and the other is added to the back list.

3. View-Dependent Traversal (Painter’s Algorithm)

To render segments from back-to-front relative to a camera (eye) position:
- Determine which side of the partition hyperplane the camera is on.
- If the camera is in the Front half-space:
  1. Recursively traverse the Back subtree (further away).
  2. Draw the Coplanar segments of this node.
  3. Recursively traverse the Front subtree (closer).
- If the camera is in the Back half-space:
  1. Recursively traverse the Front subtree.
  2. Draw the Coplanar segments of this node.
  3. Recursively traverse the Back subtree.

Time & Space Complexity

Operation / Tree Type	BSP Tree (Arbitrary Splits)	KD-Tree (Axis-Aligned)	BVH (Bounding Volume Hierarchy)
Construction Time	$O (N^{2} lo g N)$ (due to splits)	$O (N lo g N)$	$O (N lo g N)$
Space Complexity	$O (N)$ average, $O (N^{2})$ worst-case	$O (N)$	$O (N)$
Depth Traversal	$O (N)$ (to visit all visible nodes)	$O (N)$	$O (N)$
Collision Query	$O (lo g N)$	$O (lo g N)$	$O (lo g N)$

Worst-case space complexity occurs when choosing poor partition hyperplanes that repeatedly split existing segments/polygons, causing the number of nodes to grow quadratically.

Implementation

import math
 
EPSILON = 1e-7
 
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __repr__(self):
        return f"({self.x}, {self.y})"
 
class Segment:
    def __init__(self, p1, p2, name):
        self.p1 = p1
        self.p2 = p2
        self.name = name
    def __repr__(self):
        return f"Segment[{self.name}: {self.p1} -> {self.p2}]"
 
class BSPNode:
    def __init__(self, partition_segment):
        self.partition = partition_segment
        self.coplanar = [partition_segment]
        self.front = None
        self.back = None
 
def get_intersection(s1, s2):
    """Finds intersection point of partitioning line s1 and segment s2."""
    a1 = s1.p2.y - s1.p1.y
    b1 = s1.p1.x - s1.p2.x
    c1 = a1 * s1.p1.x + b1 * s1.p1.y
    
    a2 = s2.p2.y - s2.p1.y
    b2 = s2.p1.x - s2.p2.x
    c2 = a2 * s2.p1.x + b2 * s2.p1.y
    
    det = a1 * b2 - a2 * b1
    if abs(det) < EPSILON:
        return None  # Parallel
        
    x = (b2 * c1 - b1 * c2) / det
    y = (a1 * c2 - a2 * c1) / det
    return Point(x, y)
 
def classify_point(line_seg, pt):
    """Classifies point pt relative to directed line_seg (FRONT, BACK, COPLANAR)."""
    dx = line_seg.p2.x - line_seg.p1.x
    dy = line_seg.p2.y - line_seg.p1.y
    # Normal vector: 90 degrees CCW
    nx = -dy
    ny = dx
    
    val = (pt.x - line_seg.p1.x) * nx + (pt.y - line_seg.p1.y) * ny
    if val > EPSILON:
        return "FRONT"
    elif val < -EPSILON:
        return "BACK"
    else:
        return "COPLANAR"
 
def build_bsp_tree(segments):
    """Constructs the BSP Tree from list of segments."""
    if not segments:
        return None
    
    # Choose the first segment as the partition plane
    partition = segments[0]
    node = BSPNode(partition)
    
    front_list = []
    back_list = []
    
    for seg in segments[1:]:
        c1 = classify_point(partition, seg.p1)
        c2 = classify_point(partition, seg.p2)
        
        if c1 == "COPLANAR" and c2 == "COPLANAR":
            node.coplanar.append(seg)
        elif (c1 == "FRONT" or c1 == "COPLANAR") and (c2 == "FRONT" or c2 == "COPLANAR"):
            front_list.append(seg)
        elif (c1 == "BACK" or c1 == "COPLANAR") and (c2 == "BACK" or c2 == "COPLANAR"):
            back_list.append(seg)
        else:
            # Segment crosses partition line -> Split
            ip = get_intersection(partition, seg)
            if ip is None:
                front_list.append(seg)
                continue
            
            if c1 == "FRONT":
                seg_front = Segment(seg.p1, ip, seg.name + "_F")
                seg_back = Segment(ip, seg.p2, seg.name + "_B")
            else:
                seg_back = Segment(seg.p1, ip, seg.name + "_B")
                seg_front = Segment(ip, seg.p2, seg.name + "_F")
                
            front_list.append(seg_front)
            back_list.append(seg_back)
            
    node.front = build_bsp_tree(front_list)
    node.back = build_bsp_tree(back_list)
    return node
 
def traverse_bsp_tree(node, eye, traversal_order):
    """Traverses the BSP Tree back-to-front relative to camera position."""
    if node is None:
        return
    
    side = classify_point(node.partition, eye)
    if side == "FRONT":
        traverse_bsp_tree(node.back, eye, traversal_order)
        traversal_order.extend(node.coplanar)
        traverse_bsp_tree(node.front, eye, traversal_order)
    else:
        traverse_bsp_tree(node.front, eye, traversal_order)
        traversal_order.extend(node.coplanar)
        traverse_bsp_tree(node.back, eye, traversal_order)
 
# Demonstration
if __name__ == "__main__":
    s0 = Segment(Point(0, 1), Point(2, 1), "s0")
    s1 = Segment(Point(1, 0), Point(1, 2), "s1")  # Will be split by s0 at (1,1)
    s2 = Segment(Point(3, 0), Point(3, 2), "s2")  # Will be split by s0 at (3,1)
    
    tree = build_bsp_tree([s0, s1, s2])
    eye = Point(0, 3)  # Camera is above y = 1.0 (FRONT side of s0)
    
    traversal = []
    traverse_bsp_tree(tree, eye, traversal)
    
    print("Painter's Algorithm Traversal Order (Back-to-Front relative to camera at (0,3)):")
    for seg in traversal:
        print(seg)

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <memory>
 
constexpr double EPSILON = 1e-7;
 
struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
};
 
struct Segment {
    Point p1, p2;
    std::string name;
    Segment(Point p1, Point p2, std::string name) : p1(p1), p2(p2), name(name) {}
};
 
struct BSPNode {
    Segment partition;
    std::vector<Segment> coplanar;
    std::shared_ptr<BSPNode> front = nullptr;
    std::shared_ptr<BSPNode> back = nullptr;
    BSPNode(Segment seg) : partition(seg) {
        coplanar.push_back(seg);
    }
};
 
Point getIntersection(const Segment& s1, const Segment& s2) {
    double a1 = s1.p2.y - s1.p1.y;
    double b1 = s1.p1.x - s1.p2.x;
    double c1 = a1 * s1.p1.x + b1 * s1.p1.y;
 
    double a2 = s2.p2.y - s2.p1.y;
    double b2 = s2.p1.x - s2.p2.x;
    double c2 = a2 * s2.p1.x + b2 * s2.p1.y;
 
    double det = a1 * b2 - a2 * b1;
    if (std::abs(det) < EPSILON) {
        return Point(0, 0); // Parallel (handled by caller checking split)
    }
    double x = (b2 * c1 - b1 * c2) / det;
    double y = (a1 * c2 - a2 * c1) / det;
    return Point(x, y);
}
 
std::string classifyPoint(const Segment& line_seg, const Point& pt) {
    double dx = line_seg.p2.x - line_seg.p1.x;
    double dy = line_seg.p2.y - line_seg.p1.y;
    double nx = -dy;
    double ny = dx;
 
    double val = (pt.x - line_seg.p1.x) * nx + (pt.y - line_seg.p1.y) * ny;
    if (val > EPSILON) return "FRONT";
    if (val < -EPSILON) return "BACK";
    return "COPLANAR";
}
 
std::shared_ptr<BSPNode> buildBSPTree(const std::vector<Segment>& segments) {
    if (segments.empty()) return nullptr;
 
    Segment partition = segments[0];
    auto node = std::make_shared<BSPNode>(partition);
 
    std::vector<Segment> frontList;
    std::vector<Segment> backList;
 
    for (size_t i = 1; i < segments.size(); ++i) {
        const auto& seg = segments[i];
        std::string c1 = classifyPoint(partition, seg.p1);
        std::string c2 = classifyPoint(partition, seg.p2);
 
        if (c1 == "COPLANAR" && c2 == "COPLANAR") {
            node->coplanar.push_back(seg);
        } else if ((c1 == "FRONT" || c1 == "COPLANAR") && (c2 == "FRONT" || c2 == "COPLANAR")) {
            frontList.push_back(seg);
        } else if ((c1 == "BACK" || c1 == "COPLANAR") && (c2 == "BACK" || c2 == "COPLANAR")) {
            backList.push_back(seg);
        } else {
            Point ip = getIntersection(partition, seg);
            if (c1 == "FRONT") {
                frontList.push_back(Segment(seg.p1, ip, seg.name + "_F"));
                backList.push_back(Segment(ip, seg.p2, seg.name + "_B"));
            } else {
                backList.push_back(Segment(seg.p1, ip, seg.name + "_B"));
                frontList.push_back(Segment(ip, seg.p2, seg.name + "_F"));
            }
        }
    }
 
    node->front = buildBSPTree(frontList);
    node->back = buildBSPTree(backList);
    return node;
}
 
void traverseBSPTree(const std::shared_ptr<BSPNode>& node, const Point& eye, std::vector<Segment>& traversalOrder) {
    if (!node) return;
 
    std::string side = classifyPoint(node->partition, eye);
    if (side == "FRONT") {
        traverseBSPTree(node->back, eye, traversalOrder);
        for (const auto& seg : node->coplanar) {
            traversalOrder.push_back(seg);
        }
        traverseBSPTree(node->front, eye, traversalOrder);
    } else {
        traverseBSPTree(node->front, eye, traversalOrder);
        for (const auto& seg : node->coplanar) {
            traversalOrder.push_back(seg);
        }
        traverseBSPTree(node->back, eye, traversalOrder);
    }
}
 
int main() {
    std::vector<Segment> segments = {
        Segment(Point(0, 1), Point(2, 1), "s0"),
        Segment(Point(1, 0), Point(1, 2), "s1"),
        Segment(Point(3, 0), Point(3, 2), "s2")
    };
 
    auto tree = buildBSPTree(segments);
    Point eye(0, 3);
    
    std::vector<Segment> traversal;
    traverseBSPTree(tree, eye, traversal);
 
    std::cout << "Painter's Algorithm Traversal Order (Back-to-Front relative to camera at (0,3)):\n";
    for (const auto& seg : traversal) {
        std::cout << "Segment[" << seg.name << ": (" << seg.p1.x << "," << seg.p1.y << ") -> (" << seg.p2.x << "," << seg.p2.y << ")]\n";
    }
    return 0;
}

When to Use

✅ Use BSP Trees When:

You are implementing a renderer for static 3D environments (like buildings, indoor levels, or mazes) where polygons need depth sorting or back-to-front rendering relative to a dynamic viewpoint.
You need to perform complex Constructive Solid Geometry (CSG) boolean operations (e.g., union, intersection, subtraction of 3D solids).
You need very fast ray casting or line-of-sight checks in a static, cluttered virtual scene.

❌ Do NOT Use BSP Trees When:

The scene is highly dynamic with objects moving on every frame. Rebuilding the tree or updating it when objects change coordinates is computationally too expensive.
You only need simple, axis-aligned spatial queries, as KD-Trees or BVHs have lower memory and construction overhead.

Axis-Aligned BSP (KD-Tree): Subdivisions are restricted to coordinate axes. Simplifies collision testing but cannot align boundaries with arbitrary polygon orientations.
Solid BSP: A variant where leaf nodes are explicitly marked as “Solid” (inside an object) or “Empty” (outside). Ideal for collision detection and CSG.
Octree: A specialized 3-dimensional partitioning scheme where space is divided evenly into 8 octants, rather than arbitrary hyperplanes.

Key Takeaways

BSP Trees recursively partition multi-dimensional space into half-spaces using arbitrary hyperplanes defined by geometric primitives.
Primitives that cross a partitioning plane are split into front/back segments to preserve strict spatial ordering.
They allow view-dependent traversal (Painter’s Algorithm) in $O (N)$ linear time, rendering polygons in perfect back-to-front depth order.

Table of Contents

Explorer

Binary Space Partitioning

Explanation

Real-World Analogy

How It Works

Core Mechanics

1. Hyperplane Classification

2. Segment Splitting

3. View-Dependent Traversal (Painter’s Algorithm)

Time & Space Complexity

Implementation

When to Use

✅ Use BSP Trees When:

❌ Do NOT Use BSP Trees When:

Variations & Related Concepts

Key Takeaways

More Learn

GitHub & Webs

Enjoying the Notes?

Graph View

Backlinks

Recently Updated