Last updated: 2026-10-07

FDN

The Ray-Caster's Toolkit: Meet, Join, and Bisection

4.1 Constructive Solid Geometry and GA

Constructive Solid Geometry (CSG) builds complex shapes from primitive solids (spheres, planes, cylinders) combined by Boolean operations: union, intersection, and difference. Ray tracing a CSG scene requires finding where a ray \(\mathbf{r}(t) = \mathbf{o} + t\mathbf{d}\) intersects the boundary of a composite solid.

Traditional implementations handle each primitive type with bespoke intersection code and combine results via interval union/intersection on the parameter \(t\). Geometric algebra provides a unified framework: every primitive is a blade, every Boolean operation corresponds to a blade operation, and every intersection test reduces to a blade product.^[1,2] cf. GA absorbing vectors and quaternions

This chapter assumes the GA machinery already exists and focuses on wiring it into a working CSG traversal.

Some readers will want the classical, coordinate-based ray tracer built up first from nothing but tuples, matrices, and test-driven steps. It is the substrate this chapter's blades ultimately replace with something more unified, and ^[6] walks through that construction one passing test at a time.

4.2 The Meet and Join Operations

Given blades \(A\) and \(B\) representing geometric objects, the Join and Meet are defined via the outer and inner products of the dual:

\[ A \vee B = (A^* \wedge B^*)^* \quad \text{(Meet — intersection)} \] \[ A \wedge B \quad \text{(Join — smallest enclosing subspace)} \]

Definition 4.1 — Meet and Join

The Meet \(A \vee B\) is the largest blade contained in both \(A\) and \(B\) — geometrically, their intersection. The Join \(A \wedge B\) is the smallest blade containing both — their enclosing span. Both operations extend naturally to interval blades by applying containment on each factor.^{[1, §5.4]}

Fig. 4.1. Left: the Meet \(A \vee B\) of a ray blade and a surface blade gives their intersection point. Right: the Join \(A \wedge B\) of two points gives the line through them — and the bounding volume enclosing both, used for early rejection in CSG traversal.

4.3 Surfaces as Multivector Fields

A surface \(\mathcal{S}\) is defined implicitly as the zero set of a scalar-valued multivector function \(F\): like a signed distance field

\[ \mathcal{S} = \{ P \in \mathbb{R}^n \mid \langle F(P) \rangle_0 = 0 \} \]

where \(\langle \cdot \rangle_0\) extracts the scalar (grade-0) part. For standard primitives, \(F\) has a simple GA form:

// Sphere of radius r centred at c F_sphere(P) = (P - c)² - r² // scalar // Plane with normal n through point p F_plane(P) = (P - p) · n // scalar // Cylinder: axis through a with direction d, radius r F_cyl(P) = |(P-a) ∧ d|² - r²|d|² // scalar // Sign of F encodes inside (F < 0) vs outside (F > 0) sign(F(P)) = orientation of P relative to surface

The key insight is that the sign of \(F\) — specifically the sign of its scalar part when \(F\) is a multivector field — encodes which side of the surface a point lies on. This replaces the ad-hoc inside/outside tests of classical ray tracers with a single unified criterion.^{[2, §13.2]}

4.4 Guaranteed Zero-Finding by Bisection

Given a ray \(\mathbf{r}(t) = \mathbf{o} + t\mathbf{d}\) and a surface \(F\), we compose to get the scalar function \(g(t) = \langle F(\mathbf{r}(t)) \rangle_0\). The intermediate value theorem guarantees a root in \([t_a, t_b]\) whenever \(\text{sgn}(g(t_a)) \neq \text{sgn}(g(t_b))\).

1

Evaluate \(g\) at the near and far clip planes: \(g_\text{near} = g(t_\text{near})\), \(g_\text{far} = g(t_\text{far})\).
2

If \(\text{sgn}(g_\text{near}) = \text{sgn}(g_\text{far})\), the ray does not cross the surface in this interval — cull this primitive.
3

Otherwise, bisect: \(t_\text{mid} = (t_\text{near} + t_\text{far})/2\). Compute \(g_\text{mid} = g(t_\text{mid})\).
4

Recurse on the half-interval whose endpoints have opposite signs. Continue until the interval width falls below the tolerance \(\varepsilon\).
5

The midpoint of the final interval is the guaranteed intersection within tolerance \(\varepsilon\).

Interactive — Bisection zero-finding Ready

Iteration 0

Fig. 4.2. Interactive bisection demo. It starts from the single interval \([t_\text{near}, t_\text{far}]\) with no prior knowledge of how many roots it contains. Because \(g\) has the same sign at both endpoints here, the interval is ambiguous — it might hold zero, one, or several roots — so the first step splits it in half and re-checks each half's endpoint signs, rather than bisecting blindly. Once a sub-interval's endpoints disagree in sign it becomes a bracket and converges by ordinary bisection; a sub-interval that shrinks below tolerance with no sign change is culled (no root inside). \(g(t) = t^3 - 2t - 0.5\) has two roots here, so this subdivide-then-bisect process is what finds both — a ray can cross a surface more than once, and the algorithm must discover every crossing, not assume just one. Click "Bisect step" to advance one iteration, or "Auto-solve" to run to convergence.

4.5 CSG Tree Traversal with Interval Blades

A CSG tree combines primitives via Boolean set operations. The interval-blade representation enables efficient traversal: before testing any primitive, we test whether the ray's interval blade can possibly intersect that branch's bounding volume.

Theorem 4.2 — Meet-based culling

Let \(V\) be a bounding volume blade for a CSG subtree. The ray interval \([t_\text{near}, t_\text{far}]\) can intersect \(V\) only if the Meet of the ray blade \(R\) and \(V\) is nonzero — i.e., \(R \vee V \neq 0\). If the Meet is null (\(R \vee V = 0\)), the ray and the bounding volume share no common subspace and the entire subtree may be culled.^[3]early-out before expensive tests

This gives a recursive tree traversal with early exit at every node:

CSG_Union ├── CSG_Intersection │ ├── Sphere_A // test Meet(ray, sphere_A) │ └── Sphere_B // ✓ sign change found └── CSG_Difference ├── Box_C // ✗ Meet(ray, BV) = 0 → CULLED └── Cylinder_D // ✗ parent culled → skip

The oriented volume represented by the blade carries sign information that tells the renderer not just whether an intersection exists, but also the orientation — whether the ray is entering or exiting the solid. This is essential for correct handling of the union and difference operations in CSG.^[2]

4.6 The Tangency Case Revisited

When \(\mathbf{r} \wedge \mathbf{n} = 0\) (ray is tangent to the surface), the sign of \(g\) does not change — the bisection algorithm correctly identifies "no crossing" and does not report an intersection. This is the geometric resolution of the tangency problem discussed in Chapter III: the null outer product is the bisection algorithm's natural cull signal for tangent rays. grazing rays trip up naive testers

Numerical robustness. The bisection algorithm is guaranteed to converge to within any tolerance \(\varepsilon\) in at most \(\lceil\log_2((t_\text{far}-t_\text{near})/\varepsilon)\rceil\) steps, regardless of the surface's algebraic degree. This robustness — unavailable to Newton-based root-finders — is the primary practical advantage of the interval approach for CSG rendering.^[4]

4.7 Interactive: Carving a Dent with CSG Difference

The CSG_Difference node in the tree above subtracts one primitive's solid region from another's. The diagram below does exactly that, with a sphere and a cone as the two primitives and \(F(P)\) the same inside-negative, outside-positive scalar field 4.3 defines: a finite, capped cone pokes into a sphere from one side, and the combined field \(\max(F_\text{sphere}, -F_\text{cone})\) is sampled along many rays from the centre by the same bracket-and-bisect method 4.4 walks through by hand. A toggle swaps that plain maximum for a smoothed one, rounding the join between the two surfaces into a single continuous dent instead of a sharp crease.

Try it yourself (interactive version loads if your browser runs JavaScript): sliders set how deep the cone reaches in and how wide its angle is, and a toggle switches between a hard CSG difference and a smoothed one. Without scripting: at zero poke depth the surface is the plain sphere; increasing it carves a conical dent whose edge is a sharp crease under "Hard" and a rounded, continuous join under "Smooth".

The Inverse & the Dual: Navigating Null Blades — the dual operation this chapter's meet and join formulas are built directly from.
CGA Worked Examples: Interval Arithmetic in Conformal Space — extends the "every primitive is a blade" idea used here for CSG to spheres and points in conformal space.
Computer Graphics and Transforms — the classical, matrix-based transform pipeline this chapter's unified blade approach to intersection testing is a more compact alternative to.
Quadrics and the Limits of the Blade — a different kind of limit on a single blade: this chapter's CSG difference can carve any dent via sampled implicit fields, but the resulting dented shape has no CGA blade of its own, the same way a sheared sphere doesn't.

References

Dorst, L., Fontijne, D., & Mann, S. (2007). Geometric Algebra for Computer Science. Morgan Kaufmann. §5.4, §11.
Keeter, S. (2020). Massively parallel rendering of complex closed-form implicit surfaces. ACM Trans. Graph. 39(4). doi:10.1145/3386569.3392397.
Hildenbrand, D. (2013). Foundations of Geometric Algebra Computing. Springer. Chapter 7.
Mitchell, D. P. (1990). Robust ray intersection with interval arithmetic. Proc. Graphics Interface '90, 68–74.
Gamito, M. N., & Maddock, S. C. (2004). Accurate multidimensional Poisson-disk sampling. ACM Trans. Graph. 28(6). (interval ray tracing methods).
Buck, J. (2019). The Ray Tracer Challenge: A Test-Driven Guide to Your First 3D Renderer. The Pragmatic Bookshelf.

Graduate Attributes

Directly developed

Digitally Fluent: Readers manipulate sliders to adjust geometric parameters and toggle between different rendering algorithms to observe immediate visual changes.
Critical Thinker: Readers compare the outcomes of hard and smoothed CSG operations to evaluate the trade-offs between sharp edges and continuous surfaces.

Modelled on this page

Subject Specialist: Complex geometric problems are translated into a unified algebraic framework using blades and multivector fields.
Researcher: Claims about numerical robustness and algorithmic convergence are supported by citations to established literature.
Confident Communicator: Abstract mathematical concepts are explained through concrete geometric interpretations and interactive visual examples.

University of Reading Graduate Attributes framework.