SGA Globe Rendering with Interval Arithmetic

Abstract

WeWe present a Spherical Geometric Algebra (SGA) engine for rendering planetary globes using interval arithmetic bisection instead of traditional ray-marching. This provides mathematically rigorous intersection guarantees at every pixel — no missed surfaces, no depth artefacts.

1. Introduction

TraditionalTraditional globe rendering uses ray-marching with fixed step sizes or sphere-tracing. Sphere tracing, introduced by Hart, advances each ray by a step equal to the current signed-distance-function value, which is always a safe step because the SDF value is by definition a lower bound on distance to the nearest surface[1]. That guarantee is what makes it far cheaper than naive fixed-step marching, but it is still a heuristic in one respect: the loop terminates on an epsilon threshold ("close enough counts as a hit"), so a ray can pass through a thin feature between samples, or accumulate enough numerical drift near a grazing angle — exactly the horizon case a globe renderer hits constantly — that the reported hit point and surface normal are wrong by more than the epsilon suggests. For a planetary globe, where the camera is usually close to the surface and rays graze it at shallow angles across most of the frame, that failure mode is not an edge case, it is the common case.

Our approach uses interval arithmetic for root-finding in the conformal geometric algebra G(4,1). Interval arithmetic, formalised by Moore, replaces a single floating-point evaluation of a function with an evaluation over a bounded interval, producing a bound that is guaranteed to contain the true result rather than an approximation of it[2]. Applied to ray-surface intersection, this turns "did we step past the surface without noticing" from a probabilistic risk into a decidable question: if the SDF's sign provably changes across an interval, a root exists inside it and bisection can isolate that root to any required precision without a fixed step count gambling on hitting it. Conformal geometric algebra provides the surface representations (spheres, planes, and their Boolean combinations) that this root-finding operates over, using the same blade/meet/join machinery as ConceptGA's algebraic foundations (see ConceptGA: Geometric Algebra for Concept Representation and Reasoning), applied here to spatial rather than conceptual objects; the standard reference for that conformal model is Dorst, Fontijne & Mann[3].

f(p) = 0  →  root finding via interval bisection

2. Architecture

2.1 Unified CSG Expression AST

TerrainTerrain and other scene geometry are expressed as a single Constructive Solid Geometry (CSG) tree — spheres, planes, and their unions, intersections, and differences — rather than as separate code paths for "the planet" and "everything else". Keeping one representation matters here specifically because it is the same tree that gets evaluated three different ways below: once per pixel on the GPU, once per ray on the CPU, and once per query for collision — and a shared AST is what guarantees those three evaluations agree with each other instead of drifting apart as the shader and the CPU code are edited independently over time.

csg_expr.rs → CSGExpr enum (Union, Intersection, Difference, Sphere, Plane, etc.)

The same AST compiles to three targets:

• GPU bytecode — a postfix stack machine consumed by the fragment shader, so per-pixel evaluation stays branch-light.
• CPU evaluator — interval arithmetic over the same tree, used for collision and raycast queries where a guaranteed-correct answer matters more than raw throughput.
• Collision — precise surface queries against the identical geometry the pixel the player is looking at was rendered from, so "what am I standing on" and "what did I just render" can never silently disagree.

2.2 Interval Arithmetic Bisection

Standard ray-marching advances a fixed or SDF-guided step and calls it a hit once the distance drops below some small epsilon:

while (steps < max) { p += step * dir; if (sdf(p) < eps) hit; }

That epsilon is doing real work, and it is exactly the assumption interval arithmetic lets us drop. Our approach splits the search into two phases so the expensive, precise part only runs where it is actually needed:

1. Coarse sign-change detection (32 samples along ray)
2. Interval bisection on sign-change interval (20 iterations)
3. Exact hit point with rigorous bounds

The first pass is cheap and merely locates a bracket where the SDF's sign changes — it doesn't need to be precise, only to not miss a bracket entirely, which is a much weaker requirement than "hit the surface". The second pass then bisects inside that bracket 20 times, which is enough iterations to shrink the interval to sub-millimetre width even at planetary scale, and because bisection on a sign change is guaranteed to converge to a root (unlike a fixed step that can simply overshoot), the result carries a provable bound rather than an epsilon-shaped hope. This gives three guarantees a heuristic marcher can't: no missed surfaces (a sign change, once found, cannot be lost), no duplicate hits (each bracket yields exactly one bisected root), and correct ordering (brackets are processed front-to-back along the ray, so the first root found really is the nearest surface).

3. Implicit Terrain SDF

TheThe globe itself is one SDF: a sphere of Earth's radius, displaced outward by a heightmap sampled at each point's latitude and longitude:

d(p) = |p| - (R_earth + height(lat, lon))

Two details fall out of this that are easy to get wrong. Elevation is scaled 2000× before being added (real terrain, at planetary radius, is imperceptibly thin — Everest is under 9km against a ~6,371km radius, well under a pixel of relief at any reasonable render distance), with a ceiling around 3900m of scaled height so the displaced surface still behaves numerically like a sphere rather than developing pathological spikes the interval bisection would have to bracket separately. And because the horizontal plane at any point on a sphere is tangent to the sphere, not aligned with the world's notion of "flat", a camera held level actually looks along a ray that grazes the surface rather than crossing it — exactly the shallow-angle case that motivated interval arithmetic over sphere tracing in the first place (see §1). The camera is pitched downward by a fixed 0.5 radians to keep the default view looking into the terrain rather than skimming its tangent.

4. Artefact Tracing

BecauseBecause interval bisection produces a provable bound rather than an approximate one, a discrepancy between the bisected result and what actually renders is informative rather than just noise — it means one of the assumptions behind the bound has been violated somewhere upstream. trace_artifacts() exploits this deliberately, re-running bisection with extra logging at flagged pixels to reveal:

• Floating-point edge cases — brackets narrow enough that 32-bit precision itself becomes the limiting factor, not the algorithm.
• CSG operator correctness — a union, intersection, or difference whose SDF value briefly disagrees with the shape it's meant to represent, usually at a seam between two primitives.
• Gradient/normal consistency — a surface normal computed at a point that doesn't actually lie where the geometry says it should, which is the visible symptom (shading that looks subtly wrong) of an upstream bug that bisection alone wouldn't otherwise surface.

5. Dual-Number Autodiff (Reverted)

SurfaceSurface normals are needed for shading at every hit point, and the natural way to get them analytically — rather than by numerical differencing — is dual-number automatic differentiation: evaluate the SDF with dual-number inputs and read the derivative straight out of the dual part, with no separate finite-difference passes. That was the first approach tried here, and it was reverted: WGSL, the shading-language target for the GPU path, does not support custom structs in its select() builtin, which the dual-number arithmetic depends on for branch-free evaluation across the CSG tree. Rather than restructure the shader around that limitation, normals are instead computed with six-evaluation finite differences (the SDF sampled at small offsets along each axis in both directions). This costs six extra SDF evaluations per normal instead of one dual-number pass, but it works uniformly across both the GPU and CPU targets without a language-specific workaround — a case where the theoretically cleaner technique lost to the one that actually compiles everywhere it needs to run.

6. Performance

References

1. Hart, J. C. (1996). Sphere tracing: A geometric method for the antialiased ray tracing of implicit surfaces. The Visual Computer, 12(10), 527–545. https://doi.org/10.1007/s003710050084
2. Moore, R. E. (1966). Interval Analysis. Prentice-Hall.
3. Dorst, L., Fontijne, D., & Mann, S. (2007). Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry. Morgan Kaufmann.