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]

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.

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.