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]

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]

MEET A ∨ B Surface B Ray A A ∨ B (point) JOIN A ∧ B A B A ∧ B (line) bounding volume
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\):

\[ \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 genuine 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 — Join-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 Join of the ray blade \(R\) and \(V\) contains the origin — i.e., \(\langle R \wedge V \rangle_0 \neq 0\). If the Join does not contain the origin, the entire subtree may be culled.[3]

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 // ✗ Join ∧ BV → no origin → 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.

!

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]

References

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