Binary Space Partitions and the Painter's Algorithm

Binary Space Partitions and the Painter’s Algorithm

Part 19 lifted planar ideas into three dimensions: supporting planes, convex hulls, and half-space descriptions became different views of the same boundary. This part asks a more operational question. Given a fixed collection of opaque polygons and a moving viewer, in what order should we draw the polygons so that nearer surfaces cover farther ones?

The classical answer combines a binary space partition (BSP) with the painter’s algorithm. A BSP recursively cuts space by hyperplanes. Once constructed, the tree supplies a viewpoint-dependent back-to-front order without sorting every polygon from scratch. The bargain is distinctly geometric: a splitting plane may cut a polygon, so clean ordering can require fragmentation.

From a set of polygons to a spatial decision tree

In two dimensions, a BSP node uses a line to partition the plane; in three dimensions, it uses a plane. More generally, a hyperplane divides \(\mathbb{R}^d\) into open positive and negative half-spaces plus the hyperplane itself. A node contains:

• a splitting hyperplane \(H\), usually chosen from the supporting plane of an input segment or polygon;
• geometry coplanar with \(H\);
• a front child containing objects in the positive half-space; and
• a back child containing objects in the negative half-space.

Construction is recursive. Choose a splitter, classify every remaining polygon, send one-sided polygons to the appropriate child, and split every straddling polygon into front and back fragments. Stop at empty sets, or at leaves under a chosen size threshold.

For an oriented plane \(H=(n,d)\), written \(n\cdot x+d=0\), classify a vertex \(p\) by the sign of

\[ s(p)=n\cdot p+d. \]

All positive signs mean front; all negative signs mean back; signs of both kinds mean the polygon straddles the plane. Values treated as zero are coplanar. Orientation determines the names “front” and “back,” but consistency—not the particular choice—is what matters.

Splitting a polygon

Fragmentation is not an implementation accident; it is what turns an ambiguous overlap into separable pieces. Walk around a polygon’s boundary and process each directed edge \(a\to b\). If both endpoints lie on the same side, copy the appropriate endpoint. If their signs differ, insert the intersection

\[ t=\frac{s(a)}{s(a)-s(b)},\qquad q=a+t(b-a) \]

into both output polygons, then continue on the new side. This is the same edge-by-edge clipping pattern used earlier for half-planes and convex windows. Remove consecutive duplicate vertices, and discard fragments with fewer than three distinct non-collinear vertices.

from enum import Enum, auto

class Side(Enum):
    FRONT = auto()
    BACK = auto()
    COPLANAR = auto()
    STRADDLING = auto()

def signed_distance(plane, p):
    nx, ny, nz, d = plane
    return nx*p[0] + ny*p[1] + nz*p[2] + d

def split_polygon(poly, plane, eps=1e-9):
    """Return (classification, front_vertices, back_vertices)."""
    raw = [signed_distance(plane, p) for p in poly]
    scale = max(1.0, max(abs(x) for p in poly for x in p))
    tol = eps * scale
    signs = [1 if s > tol else -1 if s < -tol else 0 for s in raw]

    has_front, has_back = 1 in signs, -1 in signs
    if not has_front and not has_back:
        return Side.COPLANAR, poly[:], poly[:]
    if not has_back:
        return Side.FRONT, poly[:], []
    if not has_front:
        return Side.BACK, [], poly[:]

    front, back = [], []
    for i, a in enumerate(poly):
        b = poly[(i + 1) % len(poly)]
        sa, sb = raw[i], raw[(i + 1) % len(poly)]
        ca, cb = signs[i], signs[(i + 1) % len(poly)]
        if ca >= 0: front.append(a)
        if ca <= 0: back.append(a)
        if ca * cb < 0:
            t = sa / (sa - sb)
            q = tuple(a[k] + t * (b[k] - a[k]) for k in range(3))
            front.append(q)
            back.append(q)
    return Side.STRADDLING, front, back

This compact code shows the combinatorial structure, not a production robustness policy. In particular, the tolerance should reflect coordinate scale and the uncertainty in the plane coefficients; exact or filtered predicates are preferable when topology must be certified.

Viewpoint-dependent painter traversal

The painter’s algorithm draws far geometry first and near geometry last. At a BSP node, classify the eye point \(e\) against the node plane. If the eye is in front, everything in the back subtree lies across the plane and must be visited first; then draw coplanar polygons; finally visit the front subtree. If the eye is behind, reverse the children. In pseudocode:

PAINT(node, eye):
    if node is empty: return
    if eye is in FRONT of node.plane:
        PAINT(node.back, eye)
        DRAW(node.coplanar)
        PAINT(node.front, eye)
    else:
        PAINT(node.front, eye)
        DRAW(node.coplanar)
        PAINT(node.back, eye)

Why is this correct? Every fragment in one open half-space is separated from every fragment in the other by the node plane. For an eye strictly in front, a viewing ray that encounters both sides must cross the back side before the plane and the front side afterward; therefore back fragments cannot be nearer than front fragments along that ray. The recursive calls establish the same property inside each half-space. Induction over the tree yields a back-to-front order.

This argument assumes ordinary perspective viewing and fragments that do not cross node planes. It does not promise a strict order between polygons whose projections do not overlap; either order is harmless. Nor does it solve transparency, where blending often demands a finer per-pixel order.

Construction quality: balance versus cuts

Any input polygon can donate a supporting plane, but the choice controls both query depth and fragmentation. A balanced splitter gives roughly equal front and back sets, while a low-cut splitter intersects few polygons. These goals can conflict.

A practical builder samples candidate planes, classifies bounding boxes before exact polygon tests, and scores the survivors. Terminating with small leaf buckets can be better than forcing a plane for every polygon. In a low-density scene—where any local region intersects only a small number of large objects—reasonable splitters tend to cut little geometry, and the tree remains compact. Architectural scenes with walls and rooms are a classic favorable case because meaningful planes already organize the environment.

The worst case is sobering. For \(n\) line segments in the plane, a BSP using input-supporting lines may require quadratic total fragments under bad geometry or bad choices, although important restricted families admit better bounds. In three dimensions, polygon splitting can cascade across many planes; quadratic size is possible and carefully chosen configurations can make naïve construction far worse in practice. Thus “one input polygon, one tree node” is false: complexity is measured in the generated fragments, not merely the original objects.

Degeneracies and robust sidedness

Geometry near a splitting plane needs one coherent policy. Classifying each polygon only by its centroid is invalid: the centroid may be in front while the boundary straddles. Test every vertex, and preserve a three-way sign result—positive, negative, or zero—rather than forcing near-zero values arbitrarily to one side.

Coplanar polygons deserve their own node bucket. Their internal drawing order depends on orientation and the eye side: consistently oriented, opaque faces can be separated into polygons facing with or against the node normal, while coincident or overlapping coplanar faces need an explicit application rule. Options include a stable input order, planar overlay, depth bias for display only, or rejecting duplicate surfaces. A numerical “nudge” does not repair ambiguous topology.

Robust implementations also:

• normalize or scale plane evaluations before applying a tolerance;
• compute intersection points once and reuse them in both fragments;
• snap only under a documented, topology-aware rule;
• remove zero-area slivers after splitting; and
• use filtered exact sidedness when inconsistent signs could crack a mesh.

If the eye lies on the splitting plane, neither subtree is globally farther. A deterministic fallback can use the viewing direction relative to the plane normal, but a camera exactly embedded in opaque geometry is usually an application-level degeneracy.

BSP, kd-tree, or BVH?

These structures look similar because all are trees, but they encode different promises. A BSP partitions space with arbitrary hyperplanes and may split primitives. A kd-tree also partitions space, normally with axis-aligned planes, and is often built over points or bounded primitives; implementations may duplicate straddling objects rather than cut them. A bounding-volume hierarchy partitions the object set: sibling bounding boxes may overlap, primitives remain intact, and traversal relies on bounds rather than a separating plane.

For static polygonal scenes, the BSP’s construction cost and extra fragments can be amortized over many viewpoints, making painter traversal, visibility tests, collision queries, and constructive solid geometry attractive. Dynamic scenes reverse the tradeoff. Moving a polygon can invalidate many classifications and fragments, whereas a BVH can often be refitted by updating ancestor bounds. Modern real-time renderers also have depth buffers, so they rarely need a BSP solely to establish visible-surface order. BSPs remain valuable when explicit spatial cells, front-to-back ordering, or plane-aligned topology is itself the desired result.

What to carry forward

A BSP turns recursive sidedness decisions into a reusable spatial ordering. Its central invariant is simple—no stored fragment crosses an ancestor’s plane—but achieving that invariant exposes the real engineering issues: fragmentation, splitter quality, degeneracies, and the cost of change. The painter traversal then becomes almost effortless: far child, coplanar bucket, near child, with “far” determined anew at every node.

Part 21 moves from ordering static surfaces to planning motion. Configuration spaces and Minkowski sums convert collision avoidance into geometry, while the same habits persist: transform the problem, classify robustly, and choose a decomposition whose complexity matches the scene.