Degenerate Geometry =================== The basic :doc:`algorithm ` assumes that the split point ``p_s`` lands cleanly inside a single Voronoi cell. In rare cases, ``p_s`` can land exactly on a vertex, edge, or face of the Voronoi mesh, making the nearest-neighbor query ambiguous. This page describes how ``vortrace`` detects and resolves these degenerate cases. Split-point classification -------------------------- After computing the analytic split point between cells ``c`` and ``n``, ``vortrace`` queries the three nearest Voronoi generators (3-NN) at that position and builds the **equidistant set** -- all mesh generating points whose squared distance is within a tolerance of the nearest. The classification checks whether ``c`` or ``n`` appears in this set: - **If no** (Case 1): a third cell is strictly closer than ``c`` and ``n``. Insert it as an intermediate point and recurse into the two new sub-segments. - **If yes** (Case 2): the split point lies on the ``c``/``n`` boundary. Accumulate both half-segments and advance along the ray. Even if other points are equidistant, we can rely on the convexity of the Voronoi mesh to ignore them. Because the split point sits on the bisector of ``c`` and ``n`` by construction, both are equidistant at that location. Any cell that appears closer in the 3-NN result must lie between them. High-valence vertices ~~~~~~~~~~~~~~~~~~~~~ At a vertex where many cells meet, the 3-NN may not return ``c`` or ``n`` even though they are equidistant -- other generators at the same distance fill the top three slots. When neither ``c`` nor ``n`` appears in the initial 3-NN equidistant set and all three cells are equidistant, the search is expanded to 100-NN. If ``c`` or ``n`` is found in the expanded set, the split point is classified as a boundary (Case 2). Multiple equidistant intermediate cells (Case 1a) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ When several non-``c``/``n`` cells are equidistant at the split point (e.g. the ray crosses a Voronoi edge where three or more cells meet), the 3-NN cannot unambiguously identify which cell lies on the ray. ``vortrace`` resolves this in two stages. The algorithm finds the intermediate cell on **each side** independently: **Stage 1 — perturb along the ray.** The split point is perturbed by a small epsilon backward along the ray (toward ``c``'s side) to find the cell just before the split point (``sc``), and forward (toward ``n``'s side) to find the cell just after (``sn``). Each perturbation is accepted only if the result is unambiguous (a single clear nearest that is neither ``c`` nor ``n``). **Stage 2 — perpendicular cycling (per-side fallback).** If the along-ray perturbation for a given side is ambiguous — which happens when the ray lies along a Voronoi face on that side — the algorithm falls back to perpendicular cycling *for that side only*. The other side may have already resolved via Stage 1. The perpendicular directions have the form ``cross(dir, a*w1 + b*w2 + c*w3)`` for integer coefficients ``(a, b, c)`` and base vectors:: w1 = (1, 1, 0) / sqrt(2) w2 = (0, 1, 1) / sqrt(2) w3 = (1, 0, 1) / sqrt(2) The cross product with the ray direction keeps the perturbation perpendicular to the ray, while the combinatorial cycling through coefficients ensures that a sufficiently diverse set of directions is explored. The first perturbation that lands in a cell other than ``c`` or ``n`` is accepted. If ``sc == sn`` (the same cell on both sides), a single intermediate point is inserted. If ``sc != sn``, both are inserted at the split-point position and the zero-width segment between them is skipped during traversal. Specifically, the traversal list will look like ``current(c) → sc(s) → sn(s) → next(n)`` with sc and sn at the same point. Parallel bisectors ------------------ When the ray runs exactly along a Voronoi face (e.g. a ray at ``x = 0.5`` between generators at ``x = 0`` and ``x = 1``), the bisector plane is parallel to the ray and no analytic intersection exists. In this case, ``findSplitPointDistance`` falls back to a **binary search** along the current segment ``[s_lo, s_hi]``. At each step it queries the nearest neighbor at the midpoint: - If the midpoint lies in a third cell (neither ``c`` nor ``n``), that position is returned so that ``integrate()`` can insert the intermediate cell via the normal classification path. - If the midpoint lies in ``c`` or ``n``, the interval is narrowed toward the boundary. Once the interval width drops below ``1e-12``, the converged boundary position is returned. A warning is emitted to ``stderr`` whenever the parallel-bisector path is triggered. Endpoint clamping ----------------- Floating-point coincidence can place the analytic split point exactly at a segment endpoint (e.g. when the bisector passes through a RayPoint). To avoid zero-width segments, the split point is **clamped** to the open interior of the segment (offset inward by ``1e-15``). If the split point falls outside the segment by more than the tolerance, a runtime error is raised.