Module sos 

P12.2 — Simulation of Simplicity for deterministic degeneracy resolution. P12.2 — Simulation of Simplicity (SoS) for deterministic degeneracy resolution.

When an exact predicate returns Sign::Zero, the input is degenerate (e.g. four coplanar points in orient_3d). Algorithms that branch on the sign need a deterministic non-zero answer — otherwise the output depends on floating-point noise or iteration order, breaking reproducibility.

Simulation of Simplicity (Edelsbrunner & Mücke, 1990) resolves this by symbolically perturbing the input so that all predicates return non-zero signs. The perturbation is infinitesimal (it does not change the topology of non-degenerate inputs) and deterministic (it depends only on the point ordering, not on memory layout or rounding).

How it works

For orient_3d(a, b, c, d), the 4×4 determinant is:

D = | ax  ay  az  1 |
    | bx  by  bz  1 |
    | cx  cy  cz  1 |
    | dx  dy  dz  1 |

When D = 0, perturb each coordinate M[i][j] (for j ∈ {x, y, z}) by ε^(2^(3i+j)). The perturbed determinant D(ε) is a polynomial in ε. Since D = 0, the sign of D(ε) for infinitesimally small ε > 0 is the sign of the first non-zero coefficient in the polynomial expansion, ordered by increasing power of ε.

The first-order coefficients are the cofactors C_{ij} of the original matrix. Each cofactor is a 2D orientation test of the three points ≠ i, projected onto the coordinate plane ≠ j. The 12 cofactors are evaluated in order of increasing ε power:

Order	(i, j)	Power	Cofactor
1	(0,0)	1	+orient_2d(b_yz, c_yz, d_yz)
2	(0,1)	2	−orient_2d(b_xz, c_xz, d_xz)
3	(0,2)	4	+orient_2d(b_xy, c_xy, d_xy)
4	(1,0)	8	−orient_2d(a_yz, c_yz, d_yz)
5	(1,1)	16	+orient_2d(a_xz, c_xz, d_xz)
6	(1,2)	32	−orient_2d(a_xy, c_xy, d_xy)
7	(2,0)	64	+orient_2d(a_yz, b_yz, d_yz)
8	(2,1)	128	−orient_2d(a_xz, b_xz, d_xz)
9	(2,2)	256	+orient_2d(a_xy, b_xy, d_xy)
10	(3,0)	512	−orient_2d(a_yz, b_yz, c_yz)
11	(3,1)	1024	+orient_2d(a_xz, b_xz, c_xz)
12	(3,2)	2048	−orient_2d(a_xy, b_xy, c_xy)

If all 12 cofactors are zero (all four points are collinear or identical), the configuration is fully degenerate and we return Sign::Positive as a deterministic constant. This is consistent with the SoS principle: the perturbation guarantees a total order, and for fully degenerate inputs any consistent sign is valid.

Zero-heap contract

orient_3d_sos is a predicate: it takes Point3 (Copy) and returns Sign (Copy). No Vec, String, or Box. The underlying orientation_2 is also zero-heap. This is a Tier-1 hot-path operation.

Functions

orient_3d_sos

3-D orientation with Simulation of Simplicity tie-breaking.