Follow Fortune's sweep through its beachline, event queue and numerical decisions. Switch tree backends and compare how they work.
Fortune’s Loom
A showcase of Fortune's algorithm and Apollonius diagrams, with the moving front, event queue, tree structures and arithmetic decisions all visible together. Compare beachline backends and precision policies, and inspect how degenerate cases are handled differently.
Compare implementation policies while keeping structural invariants and numerical limits visible.
Six beachline backendsOrdering and event lifetimeFormula provenancePrecision experiments
Feature set · 4 capabilities
Six beachline backendsA leaf-oriented representation and five arc-node tree policies share the execution interface while recording their own structural mutations.
Ordering and event lifetimeLexicographic event keys and stable event storage address distinct ordering and memory-lifetime failures.
Formula provenanceExpression DAGs retain construction arithmetic and record when comparisons require numerical evaluation.
Precision experimentsTarget-dependent arithmetic and explicit input quantization expose close decisions without claiming certified exact predicates.
Change the distance model and inspect the resulting curves, hidden sites and topology.
Additive-distance cellsBounded half-edge topologyIncremental analytic reuseGeometric comparisonsConceptual 3D sweep
Feature set · 5 capabilities
Additive-distance cellsApollonius construction evaluates pair curves and triple candidates, including curved bisectors and dominated sites.
Bounded half-edge topologyRetained polylines form twins, face cycles and viewport stitching that can be checked against direct metric winners.
Incremental analytic reuseAppend-only insertion retains surviving analytic candidates while the current topology pass globally rebuilds links.
Geometric comparisonsDelaunay, power-distance, multiplicatively weighted and higher-order studies reveal how changing the construction changes the problem.
Conceptual 3D sweepA sampled paraboloid envelope, patch adjacency and observed junction traces expose the higher-dimensional question without claiming a complete event solver.
Trace a geometric result back to the mutations and checks that produced it.
Mutation playbackSweep versus clippingMismatch inspectionNative and browser routesRegression examples
Feature set · 5 capabilities
Mutation playbackSnapshots connect insertions, removals and rotations to arcs, breakpoints, queue entries and edge traces.
Sweep versus clippingIndependently clipped reference cells remain distinct from sweep-derived edges in output comparisons.
Mismatch inspectionMatched, wrong and missing edges are classified within an explicit comparison tolerance.
Native and browser routesThe C++/Dear ImGui workbench and Emscripten edition expose supported studies with separate validation and arithmetic contracts.
Regression examplesDegeneracy presets, topology fixtures and repair checks accompany recorded results rather than relying on a clean final picture alone.
Separate available engines, unported viewers, runtime costs and numerical boundaries.
Live C++ browser routeExplicit native-only viewersNumerical limits remain visible
Feature set · 3 capabilities
Live C++ browser routeFortune, weighted geometry and the sampled 3D sweep are available through WebAssembly.
Explicit native-only viewersThe 3D/4D volume studies still require their desktop rendering and worker setup.
Numerical limits remain visibleLazy Exact is included, with formula provenance and documented simultaneous-event failures rather than an exactness guarantee.
Interactive feature guide · 15 chapters
Use and inspect Fortune’s Loom
Fortune is a geometric workbench centered on two constructions: the ordinary Voronoi sweep and its weighted Apollonius relative. Geometry, mutable structures and numerical decisions can be inspected together, including difficult inputs whose errors can be hidden by a clean final image. The conceptual 3D sweep then asks what survives when a line of arcs becomes an arrangement of surface patches. Fourier decomposition and the broader framework experiments have their own entrance in Theory Workbench.
Description · what it doesExplanation · how it worksTheory · equations & assumptions
Scan the descriptions and figures, or open a layer for the implementation and mathematical detail.
01
Capability family
The geometric frontier & its events
Relate the visible Voronoi construction to the changing neighborhoods that drive the sweep.
01 · Motivation
A diagram is only the visible result
A Voronoi diagram assigns each position to its nearest site. That definition fits in one sentence, and a final picture can look uncomplicated. Implementing Fortune's sweep requires a different level of detail: locating a changing arc, splitting it without losing its neighbors, invalidating predictions made from an earlier neighborhood, and preserving the meaning of a breakpoint while the tree beneath it rotates. These operations are the substance of this project.
I usually try to make an algorithm understandable with as little visual machinery as possible. Fortune’s Loom takes a deliberately denser route: the main viewport stays direct and interactive, while the beachline, event queue, tree mutations and numerical decisions remain visible beside it. The beauty is in seeing these parts agree as the construction unfolds.
The workbench presents geometry and implementation state together. A circle event can be followed from its defining sites to its queue entry, disappearing arc, tree mutation and emerging vertex. A tree is useful here because it explains an actual operation; the animation is useful because it identifies when that operation occurred. The result is a visual systems study of a difficult geometric algorithm, with the final tessellation as one of several outputs.
The original Crystal implementation and the C++ trees/beachline infrastructure were written without AI assistance. The Crystal recordings remain part of the project's history. The current C++ edition adds a common execution interface, multiple structural policies and explicit diagnostic comparisons; the older prototype's presentation does not establish the current engine's correctness.
Video The beachline, circle events, final edges and underlying tree evolve together during the native sweep.
Image The C++ workbench connects the geometric diagram, controls, event state and beachline structure. The browser edition compiles this application to WebAssembly.
02 · Sweep construction
The frontier turns geometry into events
For a site above a horizontal directrix, the points equally distant from the site and the directrix form a parabola. The beachline is assembled from the relevant portions of these parabolas. As the directrix descends, neighboring arc intersections move along Voronoi bisectors. The continuous picture therefore has a discrete structure: the active neighborhood changes at site arrivals and arc collapses.
The parabolas are temporary construction geometry. They are not the final Voronoi edges, and a moving breakpoint is not a new input point. Showing these roles simultaneously helps separate the input sites, the frontier, the prediction of a future event and the persistent edge trace. The original visualizer already emphasized this distinction through highlights linking an arc to its structural representation.
Fortune's classical event-driven formulation supplies the familiar O(n log n) algorithmic motivation when efficient search and event operations are maintained. The instrumented workbench records complete snapshots and performs additional checks, so its end-to-end recording cost is a different measurement. Smooth playback demonstrates inspectability; it is not an uninstrumented sweep benchmark.
Image Original Crystal capture: a highlighted parabolic arc is connected to the ordered beachline and tree below. Construction geometry is shown explicitly.
(x − xᵢ)² + (y − yᵢ)² = (y − ℓ)²
A point on the site's parabola has equal Euclidean distance to the focus (xᵢ, yᵢ) and the directrix y = ℓ. The site-event case yᵢ = ℓ is singular in the usual explicit parabola formula and needs a separate insertion rule.
03 · Geometry meets data structure
An insertion is more than adding a tree node
A general site arrival splits an existing arc and inserts the new site's arc between the surviving pieces. The same site may consequently appear in more than one beachline arc. Site identity and arc identity have different jobs: a site identifies geometric input, while an arc identifies one active piece of the frontier. Treating them as interchangeable makes deletion and event invalidation particularly fragile.
The implementation maintains a search structure together with explicit predecessor and successor links. The tree locates the arc above a new site; the threaded neighbors identify the local triples that can create circle events. A rotation changes the search structure while preserving the intended left-to-right order. A split or removal changes that order and must update both representations coherently.
Equal-height input is a useful stress case because the first row of parabolas is degenerate at arrival. The dedicated insertion rule places adjacent arcs instead of applying the ordinary formula at its singularity. The regression suite checks this first-row order across all six backends, making the exceptional path part of the tested implementation rather than an incidental feature of the drawing.
04 · Event lifetime
A future event can stop being true
Three neighboring arcs can predict a collapse at the bottom of a circumcircle. That prediction depends on their adjacency. Before the directrix reaches it, another event may split an arc or change its neighbors. A stored circle and event coordinate remain numerically plausible even though the corresponding removal is no longer valid.
The current engines re-evaluate a queued collapse against the current neighboring triple before removing an arc. The interface distinguishes pending, current and invalidated events so that a discarded prediction has a visible explanation. This is a general event-system issue expressed in geometry: queue order alone cannot establish that an event's prerequisites still hold.
Cocircular sites add another difficulty. Several consecutive arcs may collapse at a shared vertex, making a sequence of ordinary single-arc removals sensitive to tiny numerical differences. Grouped collapse handles the contiguous run together and opens the replacement edge from the common event. The ring and grid examples make this behavior visible because several geometric relationships become simultaneous.
Image Original Crystal capture: the candidate circle, its lower event position and the corresponding beachline neighborhood are visible together.
Image Original Crystal capture of related circle constructions near a vertex. These historical images document the explanatory approach, rather than serving as regression evidence.
02
Capability family
Data structures, ordering & arithmetic
Compare implementation policies while keeping structural invariants and numerical limits visible.
05 · Structural comparison
Two representations, six tree backends
The leaf-oriented representation stores arcs at leaves and breakpoints at internal nodes. The alternative places an arc at every node and derives breakpoints from neighboring arcs. Both represent the same geometric frontier, but their insertion, removal and bookkeeping requirements differ. Keeping both behind FortuneRunner makes the representation itself a subject of comparison.
The five arc-node policies are actual implementations with their own rotations and fix-ups. Switching from AVL to red-black or splay changes the maintained structure and recorded mutations, rather than merely rearranging a fixed picture. The shared threaded order provides a useful point of comparison when the tree shapes diverge.
Backend agreement supplies differential evidence, not an automatic oracle. The dedicated degeneracy regression checks structural snapshots for the arc backends and compares raw edge counts with the leaf implementation on square, ring and grid fixtures. Equal counts can still conceal different endpoints. The views and tests therefore distinguish structural checks from geometric output comparison.
Video A second beachline representation keeps the geometric sweep and its mutable tree visible together.
Representation
Policies
What the view exposes
Arcs at leaves
Leaf-oriented AVL
Separate breakpoint nodes, arc leaves and threaded neighbors
Arc at every node
AVL and red-black
Height/color-driven mutation strategies over the same arc order
Arc at every node
Treap and splay
Priority-based structure or access-driven restructuring
Arc at every node
Size-balanced tree
Subtree-size metadata and its balancing operations
06 · Failure and repair
Robustness is a set of concrete mechanisms
The robustness tests connect each known failure to a specific fix. This workbench retains historical changes so that a clean diagram can be related to particular implementation decisions. Grouped collapse and half-open edge direction disambiguation have regression examples where disabling the change reproduces a mismatch with the reference construction.
Queue ordering poses a separate problem. Epsilon-based equality can make a comparator non-transitive, violating the assumptions of an ordered container. The current event order is lexicographic over the represented keys: descending height, site before circle at a tie, ascending x and event identifier. It orders the computed values consistently without pretending those values are exact geometric event times.
Event storage is a lifetime problem rather than a precision problem. Nested insertion into a vector can invalidate a reference to an event currently being processed. The stable deque path addresses that failure. The historical vector experiment deliberately exposes undefined behavior and does not support a portable, repeatable wrong-result count. Separating these causes prevents numerical terminology from obscuring an ordinary memory-lifetime bug.
Case
Mechanism
What is checked
Equal-y sites
Explicit degenerate insertion
Correct initial arc order on the tested row
Cocircular collapse
Grouped removal at one vertex
Ring/grid raw-reference comparison fixtures
Ambiguous half-open edge
Third-site gate and fallback side rule
Bounded direction-disambiguation regression
Near event ties
Transitive lexicographic queue order
Container-order contract; not exact event coordinates
Nested event insertion
Stable deque storage
Retained references survive storage growth
07 · Predicate provenance
Retain the formula; state the numerical limit
Image Native capture: formula retention, propagated uncertainty and the defining atoms of a geometric event can be inspected together. This records the numerical provenance of a construction. Image Native capture with coordinates snapped to a coarse decimal grid. Red raw/reference mismatches expose the failure instead of letting an independently rebuilt cell image hide it.
Small rounding differences can change an orientation sign, an event order or a vertex construction. The side-by-side modes make those consequences visible. Analytic Double evaluates with ordinary double precision; Low Precision first quantizes site coordinates; the mode labelled Lazy Exact preserves formulas and refines selected close comparisons. Some test configurations recover under the latter policy after the coarse mode fails, but the name does not establish a general exactness guarantee.
Lazy Exact is available in the browser. LazyScalar retains an expression DAG, while the predicate layer uses tolerance bands, numerical evaluation and a tie policy. The supported MSVC target gives long double the same significand precision as double; the checked Emscripten target reports 53 and 113 bits respectively and passes a wider-addition runtime check. Formula retention, extra precision and certified exact geometry are different properties. More bits cannot repair a construction that already lost information or supply a missing policy for simultaneous events.
Low-precision mode rounds working site coordinates to a decimal grid. It is an input-quantization experiment that can bring degeneracies into view. It does not model every operation of a lower-precision processor. This distinction makes the control more informative: a changed diagram can be related to a changed input rather than an unspecified numerical implementation.
preserved construction → evaluated comparison → recorded decision
The expression and its provenance remain inspectable. Formula retention and additional numerical precision are separate from a guarantee that every geometric sign is correct.
Precision and difficult events
4 recordings＋
When precision changes the construction
Video A side-by-side sweep and structure comparison on a degenerate arrangement. The divergent intermediate geometry makes the numerical boundary visible.
Cocircular sites with lazy evaluation
Video Inspect a cocircular arrangement, the pending circle event and the changing tree under the recorded lazy-evaluation setting.
The low-precision boundary
Video The same class of cocircular input exposes the recorded low-precision behavior. Compare the geometry and event state, not just the final fill.
Inspect a difficult event sequence
Video Follow a difficult arrangement from the moving beachline through circle events to the resulting edges.
03
Capability family
Weighted cells & related constructions
Change the distance model and inspect the resulting curves, hidden sites and topology.
08 · The second central study
Apollonius changes the geometry and the topology
Replacing a point's distance with distance minus a site radius changes more than the appearance of the cells. Equal-radius pairs retain line bisectors, while unequal-radius pairs can produce hyperbola branches. Some sites become dominated and contribute no cell. Curved boundaries, hidden sites and multiple candidate vertices make weighted geometry a substantive extension of the sweep investigation.
The current Apollonius implementation evaluates analytic pair curves and triple-vertex candidates, then filters pair visibility against competing sites. It assembles the retained polylines into a bounded half-edge structure with twins, face cycles and viewport stitching. The insertion playback exposes nearest-site search, hidden tests, conflict discovery and repair. The retained analytic state supports real reuse, while the current topology is assembled globally after insertion.
The additive metric is also available as a direct winner overlay. This layer colors sampled positions from their metric values and can look clean even when a thin DCEL gap remains. The validation grid compares those direct winners with cell ownership and distinguishes disagreements, gaps and overlaps. Sampling density controls how much of the plane is tested; an empty discrepancy view is a finite check rather than a proof everywhere.
Image Native Apollonius capture: the weighted construction is the second central geometric investigation. Analytic candidate reuse and topology assembly have distinct implementation boundaries.
dᵢ(p) = ‖p − sᵢ‖ − rᵢ
The Apollonius cell chooses the site minimizing additive distance. Radius affects the comparison itself, so changing it can hide a site or change adjacency.
Three weighted constructions
3 recordings＋
Watch weighted cells emerge
Video Advance the Apollonius construction from weighted sites to curved cell boundaries and inspect the current event.
Weighted geometry at a degenerate arrangement
Video The Apollonius sweep advances through a structured arrangement while the detail panel exposes intermediate decisions.
A harder weighted arrangement
Video A weighted sweep with crowded intersections, event details and evolving cells. The recording shows the difficult case rather than certifying every boundary.
09 · Apollonius · algorithm and implementation boundary
From the paper's predicates to a visual implementation
Description · at a glance
The bundled reference is Emiris and Karavelas, The predicates of the Apollonius diagram: algorithmic analysis and implementation. It analyzes the geometric decisions needed by the dynamic construction of Karavelas and Yvinec, including difficult degeneracies. The workbench follows that insertion narrative, then makes a different engineering choice: construct and inspect analytic candidate geometry, sampled visible curves and a bounded DCEL.
This is a working partial construction on the demonstrated and tested inputs. Its difference from the complete reference is more than speed: local topology repair, exact predicate fallback and the treatment of thin or degenerate features are not equivalent. Those distinctions identify the next implementation steps without obscuring what the current system already exposes.
ExplanationA quick tour of the reference algorithmLocate → reject hidden sites → classify conflicts → repair the graph.＋
The combinatorial construction is Karavelas and Yvinec's Dynamic additively weighted Voronoi diagrams in 2D (2002). It represents the diagram through its dual graph and supports both insertion and deletion. The bundled predicates paper develops the numerical decisions that make that graph construction robust; these are related contributions with different roles.
Insertion begins by locating the new site's nearest neighbor in the existing diagram. A containment test can then reject a site with no cell. Otherwise, the algorithm finds an initial conflict on the neighboring boundary and follows connected conflicts through the diagram's skeleton before repairing the affected graph.
The hard part is classifying a whole edge's conflict, not merely checking its endpoints. A new disk can remove an interior interval while leaving both ends, or affect the ends while an interior interval survives. Finite and infinite edge predicates distinguish these cases. The reference develops exact decisions using algebraic predicates, inversion and infinitesimal perturbation; the latter resolves degeneracies consistently.
Cached geometry is reused; global scans and sampled affected-pair decisions remain
Topology
Re-emit all after-diagram halfedges, rebuild the viewport perimeter and relink faces
The conflict region is diagnostic; the current DCEL pass does not restrict surgery to it
Unbounded cells
Clip and stitch to a finite viewing box
A bounded presentation, not the reference graph compactified with a site at infinity
Numerical fallback
Padded interval-style filters; log unresolved cases and return the double sign
No complete exact fallback or symbolic perturbation cascade
Updates
The cached incremental kernel requires a new site appended at the end
Editing/rebuilding a scene is not equivalent to the reference online deletion algorithm
Theory / mathematicsWhy slower is not the only remaining limitationFinite sampling, unresolved signs and thin-cell topology require separate evidence.＋
Checking every stored point of a sampled curve is not a proof about the continuous curve between those points. The affected-pair shortcut can forward cached geometry after finding no sampled conflict; a sufficiently narrow newly occluded interval can escape that test. Increasing trace resolution can improve a particular case, but does not turn the test into an exact edge-conflict predicate.
A named thin-lens regression makes the topology issue concrete. Without the targeted repair, one triple-point tip has degree four and its partner degree two, producing extra outside-face cycles. The repair reassigns a branch and restores that fixture's expected topology. It is a bounded repair with before/after evidence, not a general replacement for robust analytic topology.
The random native invariant canary checks cell counts, connectivity and outside-face anomalies, but its failure mode currently logs warnings instead of failing the whole suite. Read these reports alongside the harder preset and repair assertions. Agreement with a rebuild using the same approximations is useful regression evidence, but it is not an independent exact oracle.
10 · 3D Fortune · conceptual exploration
From an ordered beachline to a beach surface
Description · at a glance
The 2D sweep works with a left-to-right sequence of parabolic arcs. Move the question into three dimensions and the sweep line becomes a plane: each active site contributes a paraboloid, and their lower envelope forms a beach surface. The concept mode displays that surface beside a top-down map of its competing patches.
The comparison explains why another coordinate is a structural change. A 2D arc has immediate neighbors in a sequence; a surface patch can border several other patches. Its adjacency becomes a graph that changes as the plane descends. The demo exposes those neighbors, highlights the newest paraboloid, records approximate patch births and disappearances, and accumulates traces near triple junctions.
This is an incomplete geometric illustration, available in both native and browser editions. It evaluates a sampled surface rather than maintaining a complete 3D Voronoi event algorithm. The useful result is seeing which part of the elegant 2D mechanism generalizes and which part needs a different data structure.
Pause the sweep and move the plane manually to compare one site's paraboloid with the current lower envelope.
Enable adjacency to compare the 2D chain of arcs with the 3D patch-neighbor graph.
Toggle the newest paraboloid, event markers and traced junctions to distinguish construction geometry from accumulated approximations.
Video The conceptual 3D sweep pairs a changing surface arrangement with its planar cell view. This is an exploratory display, not a complete 3D Fortune solver.
Theory / mathematicsThe geometry that does generalizeEqual distance to a site and the sweep plane produces a paraboloid.＋
For an active site s=(sₓ,sᵧ,s_z) above the plane z=ℓ, equating the Euclidean distance to s with the distance to the plane gives the height below. Taking the minimum over active sites produces the envelope used by the illustration.
Boundaries between two surface patches lie on pairwise bisector sheets. Triple junctions are related to the one-dimensional Voronoi edge skeleton; generic 3D Voronoi vertices require four equidistant sites. The current traces are samples near triple junctions, not a certified list of those edges or vertices.
The denominator becomes singular as the sweep plane reaches a site. The viewer activates sites after the plane passes and clips the displayed height.
ExplanationWhat the display measures, and what it does not solveA 72 × 72 sampled envelope exposes patch structure without exact event topology.＋
Visible feature
How the concept mode computes it
Boundary
Surface and ownership
Evaluate active paraboloids on a 72 × 72 grid; color the lowest one
Finite sampling and clipped display height
Adjacency graph
Neighboring grid samples with different owners identify patch neighbors
Narrow contacts can disappear at the current grid resolution
Patch events
A birth is logged after five owned samples appear; disappearance after the sampled area reaches zero
Observed threshold crossings, not analytically predicted event times
Edge traces
Accumulate cells containing at least three distinct owners while the sweep plays
Approximate junction samples, not connected and validated 3D topology
Theory / mathematicsA missing linear beachline order does not make events unsortableThe 2D data-structure recipe stops transferring directly; a priority queue remains possible.＋
A priority queue can still order predicted 3D events by sweep-plane height. Losing a left-to-right order among surface patches does not prove that event times cannot be sorted, or that every higher-dimensional sweep is impossible. The difficulty is predicting the relevant changes and updating a two-dimensional arrangement with a variable neighborhood.
The concept therefore motivates a boundary in this implementation rather than an impossibility theorem. An exact event engine would need explicit surface topology, robust event predicates and updates, and validation beyond the sampled patch map. The present demo intentionally leaves that machinery unimplemented.
11 · Comparative studies
Related constructions explain what changed
Delaunay, power, multiplicatively weighted and higher-order Voronoi studies provide comparison points for the central geometry. Their value is the change in question: adjacency can be examined through a dual construction; weights can alter the metric in different ways; a nearest-site decision can become a nearest-subset decision. These are distinct mathematical objects rather than interchangeable visual styles.
The Delaunay study relates site connections to Voronoi adjacency and circumcircle constructions. Degenerate configurations are particularly informative because a simple one-triangle/one-vertex picture requires care when several sites are cocircular. Weighted studies likewise distinguish curved additive-distance boundaries from the linear boundaries available to power-distance constructions.
These geometric relatives form a focused branch around the original construction. The separate Geometry + studies entrance opens the framework's broader collection: transforms, graphs, optimization and algorithm experiments. The Crystal AVL and red-black pages isolate ordinary tree operations from the moving geometric frontier.
Study
Question made visible
Ordinary Voronoi / Delaunay
Nearest-site regions, adjacency and circle constructions
Apollonius
Additive radii, curved bisectors and hidden sites
Power diagram
A squared-distance weight model with linear pair boundaries
Multiplicatively weighted regions
How scaling distance changes competition between sites
Higher-order regions
Which subset of sites is nearest, rather than which single site wins
04
Capability family
Recorded state, comparisons & validation
Trace a geometric result back to the mutations and checks that produced it.
12 · Recorded execution
The intermediate state is the explanation
A MutationObserver records the real insertions, removals and rotations. Snapshots retain node identities and links, neighboring arcs, breakpoints, edge traces, event queues and validation messages. Playback can connect a visual change to its originating mutation because those views share the recorded state.
The formula-preserving mode adds another level of inspection. Constructed values retain expression graphs with named input atoms, arithmetic operations and square roots. Comparison-forcing counts identify when a symbolic construction needed numerical evaluation. This makes a difficult coordinate or comparison traceable instead of reducing it immediately to an unexplained decimal.
The controls, geometry and timeline are meant to support the same investigation at different scales: inspect the whole diagram, pause at one event, locate its arcs in the tree and inspect the reason for the update. The surrounding searchable collections keep other studies accessible while the initial workbench remains centered on the sweep.
Video Original Crystal visualizer recording. The current C++ application develops the same goal of relating geometric change to internal state.
13 · Validation design
A correct filled image is not enough
The workbench can construct final cell polygons independently by clipping each site's viewport polygon against pairwise bisector half-planes. This produces a helpful reference picture, but it is a separate computation. If a sweep edge is wrong, the reference-filled image can still look correct. The interface therefore distinguishes the reference cells from the sweep-derived edge output.
The raw-sweep view retains the engine's edge construction with explicit endpoint welding and viewport resolution for unfinished rays. An A/B comparison identifies matched, wrong and missing edges within a configured tolerance. Raw here means sweep-derived with documented endpoint cleanup; it does not mean an untouched event trace. The clipping reference also uses floating-point calculations and tolerances.
Structural validation asks a complementary question. The arc validator checks agreement between tree and thread links, parents, head/tail and stored metadata. Some mutation snapshots occur before rebalancing, so it deliberately does not certify every AVL, treap or red-black balance condition. A clean structural ribbon, matching edge counts and matching geometry are three different kinds of evidence, and the project benefits from displaying them separately.
14 · Build, inspect, compare
A reproducible route through the workbench
The browser target compiles the current C++ engines and Dear ImGui application through Emscripten. The native and browser builds remain separate validation targets, including their arithmetic representations and available studies. Browser modes requiring unported desktop volume shaders or worker-thread behavior are excluded instead of being presented as working equivalents.
The checked browser core suite contains 26 applicable signature groups covering degeneracies, snapshots and event storage, topology fixtures and incremental/rebuild parity. Its 20 deterministic random Apollonius cases are useful canaries, but that random test currently logs invariant failures rather than always making them fatal. A successful process exit is therefore read together with the actual reports. The named preset and lens-repair checks provide harder assertions for their bounded cases.
A practical investigation begins with one ordinary sweep, then an equal-y or cocircular fixture, and then a backend change on the same sites. Compare the raw sweep with reference clipping before moving to weighted insertion. The question at each step is what state changed, what invariant was checked, and which computation produced the image. That route makes both the implemented strengths and the remaining research work visible.
The browser presentation uses the bundled Playfair Display and Fortune Mono Medium faces, the latter a licensed static weight-500 derivation of Source Code Pro, a high-density font atlas and a separately scaled framebuffer. Browser edition reports loaded fonts and actual backing dimensions and offers an explicit density override. The pointer and layout remain in CSS coordinates, so display sharpness can change without changing the meaning of the controls.
Pause at a site split and connect the two surviving arc pieces to their shared input site.
Inspect a pending circle event, then follow an insertion that invalidates its neighborhood.
Compare the same cocircular input across representations and inspect both structural reports and sweep-derived edges.
In weighted geometry, compare direct metric winners with DCEL ownership before interpreting the filled image.
Treat native tests, browser core tests, font/input tests and visual interaction checks as complementary evidence.
Image Current WebAssembly workbench at display density, with the medium-weight font, final sweep geometry, beachline tree and event history.
05
Capability family
Browser edition & native scope
Separate available engines, unported viewers, runtime costs and numerical boundaries.
15 · Availability and numerical boundaries
Which studies run in the browser?
The browser application compiles the C++ engines and Dear ImGui interface through Emscripten. Fortune, weighted geometry and the conceptual 3D sweep are available. The last is sampled geometry drawn through ImGui, so it has a different presentation path from the native volume viewers in Theory Workbench.
Lazy Exact is included. The regular twelve-site circle can still produce missing or misplaced raw-sweep spokes, even with that mode selected. Matched native and browser runs have shown this simultaneous-event boundary; different target arithmetic can change its appearance. This is an implementation limitation to inspect, not evidence that WebAssembly disables the mode.
Browser and desktop are separate validation targets. This Emscripten build tests 53 significand bits for double and 113 for long double, so “the browser has less precision” would be the wrong blanket explanation. Different arithmetic representations can change an event tie; unported desktop GLSL volume viewers and native worker paths are separate compatibility limits. A case that works on desktop still deserves a browser check.
Feature
Browser status
Reason or boundary
Fortune, weighted geometry and number modes
Available
Same engine paths, with target-dependent arithmetic and documented degeneracy limits
3D Fortune concept
Available
Sampled paraboloid envelope and patch analysis; not a complete 3D event solver
3D FFT volume, KLT eigenvolumes, voxel/JFA3D viewer
Excluded
Their shared desktop GLSL 330 volume renderer has not been ported to GLSL ES/WebGL2
4D FFT and 3D FFT filter bank
Excluded
Same unported volume renderer; larger transforms/filter-bank rebuilds also use native asynchronous workers
Standalone linear-programming interface
Excluded pending validation
No established CPU-solver incompatibility; this UI has not been validated for the browser
Original Crystal/SFML application
Separate native implementation
Crystal runtime, native SFML libraries, OS window and launcher need their own port
More recorded views · 12
Image Current C++ browser workbench: a recorded sweep event connects the geometric beachline to its tree and timeline. Image Earlier Crystal prototype: an arc disappears at its predicted circle event. Image Earlier Crystal prototype: beachline arcs and their tree nodes. Image Earlier Crystal prototype: competing circle events and their geometric context. Image alternate backend (arc representation) Image another hard case Image Apollonius done Image Apollonius in action Image desktop degenerate case (this fails in the web version).png Image desktop degenerate case (with inaccuracy estimation) Image low precision case failing Image low precision mode (replicating the failing mode in webASM)
From the Crystal prototype to an implementation laboratory
Earlier work → current system
The original Crystal/SFML project made the beachline and its tree visible together. Its video and event diagrams capture the starting point: understanding how a geometric transition becomes a concrete data-structure mutation.
I wrote the original Crystal implementation and the main C++ tree and beachline infrastructure without AI assistance.
The C++ project expands that investigation with multiple balance policies, recorded mutations, explicit comparisons and a wider study library. The earlier essay is preserved as an archive. Its broad correctness claims are superseded by the current raw/reference evidence and documented numerical limitations.
The visualizer records execution snapshots for playback; its frame rate is not an algorithm-throughput benchmark.
Filtered and formula-preserving arithmetic does not constitute certified exact predicates, constructions or event ordering. The weighted-diagram implementation remains incomplete.
Lazy Exact is available in WebAssembly. It retains formulas and refines selected comparisons, but does not certify exact constructions or event ordering. The regular 12-site cocircular case can fail in both native and browser runs.
The dense interface deliberately prioritizes a complete view of the algorithm. Dedicated visualizers elsewhere in the portfolio trade that generality for a more focused presentation.
The browser is a selected C++/WebAssembly port, not a desktop-parity guarantee. Arithmetic representations and enabled features differ by target; difficult inputs must be checked separately. The known cocircular failure is shared by both targets, not evidence of missing browser precision alone.
01 / 05
