Motivation
A painter starts with distant surfaces and paints nearer ones on top. A renderer could do the same at each pixel: the final opaque fragment written is the visible one. But a single number per polygon, such as its center depth, need not give an order valid at every pixel. Two sloping surfaces may exchange which is nearer across the image. A binary space partition (BSP) addresses the geometry behind the conflict: cut polygons that cross selected planes, then traverse the pieces in an order determined by the eye.
This is a model of an object-space visibility algorithm, not a claim that every graphics pipeline uses one. We use exact arithmetic, finitely many planar convex polygons and a fixed eye position. Smaller ray parameter means nearer. We consider opaque surfaces and a sample ray with a unique nearest intersection; degeneracies and finite precision need explicit policies.
A plane divides the problem
Write a partition plane as , where . Its positive and negative open half-spaces have and . Classify a convex polygon by the signs at its vertices. If it crosses the plane, clip it into two closed convex pieces, sharing their boundary on the plane. For a crossing edge to , its intersection is
Indeed . Strictly opposite endpoint signs ensure . Vertices already on the plane and edges lying in it require consistent duplicate removal and ownership; a zero denominator must not be used as an intersection formula. Carry per-vertex attributes with the same edge parameter when they represent affine data on the original polygon.
Definition 2.7.1
(A finite polygon BSP)
At each node choose the supporting plane of one remaining polygon fragment. Store all fragments lying in that plane at the node. Split each crossing fragment, then put the noncoplanar pieces into the corresponding positive and negative children. Repeat until no fragments remain. The tree is built for the scene; a later eye position determines the traversal order.
Proposition 2.7.2
(The construction terminates)
Let the input consist of finitely many convex polygons with distinct supporting planes. On every root-to-leaf path the node planes are distinct supporting planes of input polygons, so every path has at most nodes and the tree is finite. No balance and no bound on the number of fragments is claimed.
Proof
(Each node uses up its supporting plane)
Splitting by a plane replaces a polygon by pieces of that polygon, so every fragment keeps the supporting plane of the input polygon it came from. A node with plane stores every fragment lying in , so no fragment passed to its children has support . Hence a path never uses the same support plane twice and cannot exceed nodes. Each split of a convex polygon creates two pieces, so every node passes finitely many fragments to each of its two children. A binary tree whose paths have at most nodes is finite.
This argument does not promise a balanced tree or a small number of pieces: poor plane choices can cause substantial fragmentation.
Why the traversal works
Definition 2.7.3
(Back-to-front traversal)
For an eye lying on no node plane, the traversal of a node with plane visits first the child on the side of the plane opposite to , then draws the fragments stored at the node, then visits the child on the same side as . Each child is traversed by the same rule.
Theorem 2.7.4
(Back-to-front order along each ray)
Suppose the eye lies on neither a node plane nor any surface. For a ray from , its intersections with the fragments, listed in traversal order, appear in nonincreasing distance along that ray, apart from coincident intersections. Thus overwriting opaque color in that order returns the unique nearest intersection at each covered sample.
Proof
(One plane splits a ray into three ordered blocks)
Assume and parameterize the ray by , . Since is affine in , any intersection in the negative half-space can occur only after the ray crosses the plane, and any intersection in the positive half-space occurs before that crossing. If it never crosses, it never meets the negative half-space or plane. Consequently every far-child intersection is behind every node-plane intersection, which is behind every near-child intersection on that ray. The argument reverses signs for . Induct on the finite tree: each child orders its own intersections, and these three ordered blocks concatenate correctly. At a sample, the last opaque write is therefore the nearest, provided the nearest hit is unique.
Proof X-ray
What each assumption does in the traversal proof
The condition is spent once: it decides which child is the far one, and it is the only place where a strict side is needed. The key move is that is affine in . A single sign change along the ray means that the three blocks, far child, node plane, near child, occupy disjoint, ordered intervals of the ray parameter, so no distances ever have to be compared. Induction on the tree closes the argument, because each child is a smaller tree with the same property and its block of hits lies entirely inside its interval. The unique-nearest hypothesis is used only in the last sentence, to read the final overwrite as the visible surface. Nothing about Euclidean distances between arbitrary points, about the balance of the tree, or about the shapes of the fragments is used.
This statement concerns points on the same ray. It does not require every point in the far half-space to be farther in Euclidean distance than every point in the near half-space. Two fragments with disjoint projections may be drawn in either relative order. The polygon fragments stored at a node are coplanar; if they overlap at the same point, the image has an equal-depth tie and needs a separate rule.
If the eye lies on a partition plane, the strict-side rule is undefined. A ray not contained in that plane immediately enters one half-space and has no positive-distance intersection with node fragments in the plane; a ray contained in it is a separate degeneracy. An implementation must select and document a tie convention, or change the viewpoint, rather than divide by zero or pretend the eye is on a strict side.
Concept lensAlgorithmic
The order as a sign-driven tree walk
Traversal is an in-order walk of the binary tree in which the only test at a node is the sign of , computed once per node from the eye position. That sign picks which child to enter first. The whole painting order is produced by at most one sign test per node, with no ray, pixel or depth comparison, and it is the same object as the ray-by-ray order in the theorem.
Worked examples
Worked example 2.7.5
(A split and two viewpoints)
In the plane take partition line (the two-dimensional analogue of a plane). A segment from to crosses it at , giving . Store the negative piece – in the negative child and the positive piece – in the positive child. Assume a partition segment at the node covers the ray intersections considered.
For eye and ray , imagine three distinct small planar patches in three dimensions crossing that ray at , respectively, with the middle patch stored at the node. Their parameters are : negative child, node, positive child. Drawing in that order puts the patch at last. This ray need not hit the split segment above: traversal orders the intersections that actually occur and does not promise that every fragment is hit. Moving the eye to the negative side reverses the two child visits without rebuilding the tree.
The distinction between plane sign and ray distance is visible in the calculation: the sign locates each patch relative to the partition, while the ray parameter orders only the hits on this particular ray.
Worked example 2.7.6
(One tree, two eyes)
Work in the plane, where segments play the role of polygons. Let be with , let run from to , and let be with . The root stores and uses . For , and , so and . The piece – goes to the negative child; the piece – and the whole of , where , go to the positive child.
For the eye , , so the order is negative child, , positive child. The ray along toward decreasing meets at and at , and misses both pieces of , which have . The traversal visits the negative child (no hit), then at , then the positive child with at : the parameters are nonincreasing. For the eye , , so the positive child comes first. The same line now meets at and at , again in nonincreasing order, with the same tree.
Worked example 2.7.7
(An eye on a partition plane (boundary case))
Keep and from the previous example and put the eye at , so and the strict-side rule has no answer. The ray enters the positive half-space at once. It meets the line only at , outside because , and meets at , at . For this ray either child order gives the same image, since no node fragment can be hit at positive distance. The ray is contained in the plane: it meets along the whole interval , so there is no unique nearest hit. Such an edge-on view needs a declared convention, for instance discarding a polygon seen exactly edge-on, or a different eye position.
Where painter order can fail
Consider two depth functions and over the same projected interval , with smaller nearer. At , is nearer; at , is nearer. No ordering of the two whole polygons works at both samples. Their intersection at supplies a place to split; after splitting, the pieces can be ordered locally. Sorting their equal center depths cannot solve the disagreement. Equal-depth samples at the crossing still need a tie policy.
Counterexample mode
Sorting whole polygons by center depth
The claim: painting whole polygons from larger to smaller center depth always leaves the nearest surface at every sample. Both polygons above have center depth , so either order is a valid sort. If is drawn first and last, the sample shows , although makes nearer. If is drawn first, the sample shows , although makes nearer. Splitting both polygons at the crossing repairs the failure: is nearer on and on , so each pair of pieces has a valid local order.
The theorem also assumes opaque overwriting. Transparent surfaces generally both contribute and need an appropriate compositing rule, not the opaque last-write rule. Rasterization must apply compatible clipping and edge ownership to avoid cracks or double coverage. Exact geometric ordering alone does not prove a floating-point implementation is robust, nor does it handle curved or moving geometry without updating the representation and tree.
Common mistakes
Common mistake
(Reading the traversal as a distance order for all points)
Take the plane and the eye . The point lies in the far, negative half-space at distance , while lies in the near, positive half-space at distance . The far half-space therefore contains a point much closer to the eye than a point of the near half-space. The theorem orders hits only along one ray.
Common mistake
(Applying the intersection formula to an edge lying in the plane)
For the plane and the edge from to , , so and the formula for divides by zero. Classify vertices first: an edge with both endpoints on the plane belongs to the node's coplanar set and is not split, and an edge with one endpoint on the plane meets it only at that endpoint.
Practice with solutions
Quick check
(Let . Split the edge from to . Where is its intersection, and which part is on the negative side?)
Compute and first.
Solution · Answer
and , so and . Points from up to but excluding have negative sign; is on the plane. The remaining open part has positive sign.
Quick check
(An eye has . Give the three traversal blocks and justify the order for a ray crossing the plane.)
Which side is the far side now?
Solution · Answer
Visit the positive child, draw the node, then visit the negative child. Along a ray from the negative side, a positive-side hit can only occur after the plane crossing, so it is farther than a plane hit and any negative-side hit before the crossing. This is back-to-front, not an assertion about arbitrary pairs of points off the ray.
Quick check
(Two opaque fragments hit the same ray at parameters and . Their center depths lead to the order then . What color remains, and why is it wrong?)
Which fragment is written last?
Solution · Answer
The fragment at overwrites the one at , leaving the farther color. Back-to-front would draw first and last. A depth buffer can instead compare depths at the sample, under its own clear and tie conventions.
Quick check
(A node has two overlapping coplanar polygons at precisely the same ray distance. Does the theorem select a unique visible color?)
Check the unique-nearest hypothesis.
Solution · Answer
No. Their hits tie, so the unique-nearest hypothesis fails. One needs a declared tie rule or a scene representation that resolves the overlap; switching child order does not distinguish the two node fragments.