SPB Git

Repository Public MIT

VALIDATION.md 15.6 KB 215 lines markdown

1<!--2ORIX Calc3File: Packages/ORIXGraph/VALIDATION.md4Description: What the graph engine guarantees, how it was verified, measured accuracy and performance, known limitations.56Author: Simon-Pierre Boucher7Contact: contact@spboucher.ai8-->9# ORIXGraph — Validation1011Status on 2026-11-20: `swift build` and `swift test` pass from the package directory with zero warnings (Swift 6 language mode,12strict concurrency). **117 tests in 20 suites**, in debug and in release (`swift test -c release -Xswiftc -enable-testing`).1314Every number below was printed by the test suite (`PerformanceTests.swift`, lines starting with `PERF|` and `COUNT|`) on the15machine the suite was run on: an Apple Silicon Mac (Apple M5 Max, macOS 27.0), wall-clock time from `ContinuousClock`,16best of 7 runs. Debug figures are from an unoptimised build with the other test suites running in parallel; they vary by17tens of percent from run to run. Nothing here was estimated.1819## 1. The cardinal rule and how it is tested2021*A graph must not misrepresent a function.* The tests do not only count polylines; three independent checks are applied to the22output (see `Tests/ORIXGraphTests/Support.swift`):2324- `hiddenBreaks`: between every pair of consecutive vertices the function is re-evaluated at 64 points. It must be defined25  everywhere (except at a reported hole) and climb gradually: if one of the 64 sub-steps carries more than half of a rise of26  more than 3 px, or the values leave the range of the two end points, the segment hides a jump or a pole and the test fails.27- `spans`: no segment may contain an analytically known discontinuity strictly between its two vertices.28- `uncovered`: at 4000 abscissas, wherever the function is visible on screen some polyline or band must cover that abscissa.2930plus `maxScreenError` (distance in pixels from the true curve to the polyline, 8 points per segment) and `bounded`31(all coordinates inside the padded viewport).3233| Function (800×600, x ∈ [−10, 10], y ∈ [−7.5, 7.5] unless noted) | Polylines | Reported discontinuities (checked against the analytic values) |34|---|---|---|35| `1/x` | 2 | pole at 0, limits −∞ / +∞; branches end on the clip boundary |36| `1/x`, `1/(x−1/3)` on a grid that misses the pole | 2 | pole located to 1e-12 |37| `tan(x)` | 7 | 6 poles at (k + ½)π, to 1e-12 |38| `tan(x)` on [0, 20π] | 21 | 20 poles, every branch monotone |39| `1/(x−1)^2`, `1/(x−1/3)^2` (even order, no sign change) | 2 | pole, limits +∞ / +∞; a finite spike `1/((x−1/3)²+10⁻⁴)` is *not* broken |40| `1/sin(x)` | 8 | 7 poles at kπ |41| `floor(x)` | 21 | 20 jumps exactly on the integers, limits n−1 / n; all pieces horizontal |42| `sign(x)` | 3 | one jump at 0; the middle polyline is the isolated point (0, 0) |43| `abs(x)/x` | 2 | jump at 0 |44| `sqrt(x)` | 1 | starts at exactly (0, 0); undefined interval [−10, 0] |45| `sqrt(x − 1/3)`, `sqrt(2 − x)` off the grid | 1 | boundary to 1e-15 |46| `ln(x)` | 1 | boundary at 0 with limit −∞; polyline extended down to the clip boundary |47| `x^(1/3)` | 1 | none (one piece through 0) |48| `sin(x)/x` | 1 | removable at 0, hole (0, 1) |49| `(x²−1)/(x−1)` | 1 | removable at 1, hole value 2 (to 1e-6) |50| `piecewise(x<1, x, x>2, x−1)` | 2 | undefined interval [1, 2] to 1e-9 |51| `sqrt(1−x²)` | 1 | from (−1, 0) to (1, 0) exactly, all vertices on the circle to 1e-12 |52| `exp(x)` | 1 | none; clipped at the top; `exp` on [0, 2000] (overflow to +∞) stays one bounded polyline |53| `sin(1/x)` on [−1, 1] | 2 + 1 band | band around 0 (inside |x| < 0.2), essential discontinuity at 0, lines outside accurate to < 0.5 px |54| `sin(1000x)` (aliases to a smooth fake sine on this grid) | 0 + 1 band of 800 columns | — ; same for exact multiples of the sampling frequency |55| `sin(100x)` (2.5 px per period) | 1 | none; stays a line, max error 0.21 px |5657A further 32 awkward functions (`gamma(x)`, `tan(1/x)`, `1/(x − floor(x))`, `tan(tan(x))`, `floor(sin(50x))`, `exp(1/x)`,58`ln(abs(x))`, `sqrt(sin(100x))`, `x!`, …) pass the same four checks (`AwkwardFunctions.staysHonest`).5960Implicit curves, parametric / polar curves and surfaces have their own versions of the rule:6162- `x² + y² = 25` at 400×400: one closed polyline, worst radial error below 0.02 units-per-pixel (the test's bound), polygon area = 25π ± 0.05.63- `xy = 1`: two open branches, every vertex has xy > 0. `1/x = y` on a shifted lattice: > 100 sign changes across the pole rejected, two branches.64- `tan(x) − y = 0`: 7 branches, > 500 false crossings rejected, no segment crosses a pole line. `floor(x) − y = 0`: 20 treads, no riser.65- `(x − y)² = 0`: nothing drawn **and** `reliable == false` with a reason; `sin(40x) = cos(40y)` at ±10: `reliable == false`.66- Unit circle, Lissajous (sin 3t, cos 2t), cardioid r = 1 − cos θ, rose r = cos 2θ (negative r → petals on the y axis): vertices on the true curve (1e-9 … 1e-12), closed flag set, < 0.3 px from the curve.67- (t, floor t), (t, 1/t), (t, tan t), (√t, t): broken at jumps / poles / domain boundary, located in t.68- z = 1/(x²+y²) and z = 1/x with 60 and 61 cells (vertex on / off the pole): no triangle covers the pole, z-range stays below 10 / 20; z = floor(x): only flat treads; z = √(1−x²−y²): hole outside the disc, vertices on the sphere to 1e-12.6970## 2. Measured accuracy and point counts (800×600)7172Smooth functions tested for < 0.5 px (`Accuracy.smoothFunctionsWithinHalfAPixel`): sin x, x², x³ − 3x, eˣ, e^(−x²),735e^(−x²/2), cos 3x + x/2, x⁵/100 − x³/3 + x, |x| − 2, √|x|, atan 5x, 7 sin x.7475| Function | Points | Evaluations | Polylines | Max error (px) |76|---|---|---|---|---|77| sin(x) | 801 | 1601 | 1 | 0.003 |78| x^2 | 381 | 1327 | 1 | 0.006 |79| x^3 − 3x | 621 | 2683 | 1 | 0.019 |80| exp(x) | 561 | 1535 | 1 | 0.003 |81| exp(−x^2) | 801 | 1601 | 1 | 0.006 |82| 1/x | 940 | 2413 | 2 | 0.017 |83| tan(x) | 1689 | 6179 | 7 | 0.016 |84| sqrt(x) | 402 | 1691 | 1 | 0.156 |85| ln(x) | 435 | 1876 | 1 | 0.027 |86| floor(x) | 1021 | 3949 | 21 | 0.000 |87| sin(x)/x | 802 | 1759 | 1 | 0.001 |88| sin(100x) | 7119 | 28628 | 1 | 0.211 |8990Rule of thumb: one point per pixel column (fewer where the curve is off screen), two evaluations per column, more only91where the curve bends, is steep or breaks. Extreme windows: `sin x` on [10⁹, 10⁹ + 10] and `x²` on [−10⁻⁹, 10⁻⁹] are within920.5 px; spans from 10⁻²⁰⁰ to 10²⁰⁰ sample normally; windows narrower than 4096 ulps are widened by `Viewport`.9394Analysis against analytic values (tolerances are those asserted by the tests):9596| Quantity | Result |97|---|---|98| roots of x³ − x; √2; cos x on [−10, 10] | 1e-12 … 1e-13 |99| extrema of x³ − 3x at ∓1; of sin x | x to 1e-9, y to 1e-12 |100| sin ∩ cos on [−2π, 2π] (4 points) | 1e-12 |101| tangent of x² at 1 | slope 2, intercept −1 to 1e-11 |102| ∫₀^π sin = 2; ∫ e^(−x²) on [−8, 8] = √π; ∫₋₁¹ sin x / x | 1e-12 |103| area between x and x² on [0, 1] = 1/6 | 1e-14 |104| arc length of y = x on [0, 1]; of a 60° circular arc; of x^1.5 on [0, 4] | 1e-12; 1e-9; 1e-7 |105| poles as roots / intersections (1/x, tan x, 1/x vs 2/x, tan x vs tan x + 1) | never reported |106| ∫ across a pole (1/x, 1/(x−0.3)², tan x, 1/sin x), across an undefined stretch | refused with a message |107| ticks | ≤ 25 major ticks for 77 184 combinations of span 10⁻³⁰⁰ … 10³⁰⁰, offset, pixel length and mode; degenerate, inverted and non-finite input included |108109## 3. Measured performance110111Best of 7, milliseconds. "Apple Silicon Mac, release build" and "debug build" as actually run (same machine, same session).112113| Task | Release | Debug | Output |114|---|---|---|---|115| explicit 1200×800 `sin(x)` | 0.113 | 5.8 | 1201 points, 2401 evaluations |116| explicit 1200×800 `x^2` | 0.077 | 3.7 | 539 points |117| explicit 1200×800 `x^3 − 3x` | 0.238 | 7.3 | 861 points |118| explicit 1200×800 `1/x` | 0.170 | 7.9 | 1394 points, 2 polylines |119| explicit 1200×800 `tan(x)` | 0.578 | 15.9 | 2395 points, 7 polylines |120| explicit 1200×800 `exp(−x^2)` | 0.100 | 5.6 | 1201 points |121| explicit 1200×800 `sqrt(x)` | 0.071 | 4.5 | 609 points |122| explicit 1200×800 `floor(x)` | 0.246 | 9.6 | 19 polylines |123| explicit 1200×800 `sin(x)/x` | 0.119 | 5.4 | 1202 points |124| explicit 1200×800 `sin(100x)` (refined to the cap) | 1.37 | 37.3 | 10073 points, 40379 evaluations |125| explicit 1200×800 `sin(1000x)` (all band) | 1.08 | 20.3 | 1200 band columns |126| implicit 400×400 `x² + y² = 25` | 0.57 | 10.7 | 384 points, 9053 evaluations |127| implicit 400×400 `sin(x) = cos(y)` | 2.05 | 31.2 | 2510 points, 30403 evaluations |128| implicit 400×400 `xy = 1` | 0.55 | 9.6 | 392 points |129| implicit 400×400 `tan(x) = y` | 1.63 | 22.8 | 1407 points |130| parametric 1200×800 (sin 3t, cos 2t) | 0.021 | 0.27 | 513 points |131| surface 60×60, precise normals | 0.61 | 11.4 | 3721 vertices, 7200 triangles |132| surface 60×60, grid normals | 0.28 | 6.4 | |133| painter projection + depth sort, 7200 triangles | 0.48 | 5.3 | |134| roots + extrema of x³ − 3x on [−10, 10] | 0.13 | 2.0 | |135| ∫ sin on [0, 2π] with shaded regions | 0.25 | 4.8 | |136| slider update (compile + sample 1200×800) `a sin(bx) + c` | 0.12 | 2.7 | 1201 points |137138The implicit target (400×400 px in < 50 ms) is met with a wide margin in release and also in debug on this machine; the debug139figure for `sin(x) = cos(y)` ranged from 28 to 50 ms over the runs made during development, so the test asserts 50 ms only for140release builds.141142## 4. How it works (short)143144- **Explicit sampler.** Uniform grid, one sample per pixel column (no jitter). Each column is tested at one interior point145  whose position varies from column to column (so that no frequency can alias with both the grid and the test points), and is146  bisected (up to 2⁶ pieces) while the screen distance to the chord exceeds 0.2 px; inside refined regions three points per147  piece are tested. Columns that rise by more than 8 px, or whose test fails, get 7 irregular probes: three or more reversals148  (or two that are not a single adverse step, decided with 8 more samples) mean aliasing and the column becomes a min/max149  band; inside a band every column is probed. At the refinement cap, a remaining gap is bisected down to adjacent doubles:150  if it shrinks the piece is continuous, otherwise one-sided limits are estimated from geometric sequences of samples and the151  break is classified (jump / pole / essential). Undefined samples are bracketed by bisection to adjacent doubles; an isolated152  undefined point with equal finite limits is a hole and is drawn through. Poles between two samples off the same edge are153  found by golden-section search on |f|. Polylines are clipped (not clamped) to the viewport ± one height.154- **Implicit.** Coarse lattice (8 px) → refine cells with a sign change, an undefined corner, or |F| small compared with its155  variation → marching squares at 2 px with propagation into neighbouring coarse cells. Every crossing is validated: F at the156  interpolated vertex must be far below both end values, otherwise the bracket is shrunk 16-fold and must have come down157  (zero) rather than stayed (jump) or grown (pole). Segments are stitched through shared lattice edges.158- **Surfaces.** Grid mesh; z-range by Tukey fences; triangles dropped when a vertex is undefined, when all three are clipped on159  the same side, or when an edge that climbs > 5 % of the z-range (or is clipped) fails the same shrinking-gap test.160161## 5. Known limitations (read before promising anything to users)162163Explicit curves164- **Sub-pixel features can be missed.** A spike, a dip or an even-order pole that lies wholly between two grid samples *and*165  is not hit by that column's test point is not seen when both neighbours look flat. (Odd poles and jumps change the level and166  are found; even poles are found when the neighbouring samples are already off screen or when a sample lands on them.)167- Classification is numerical. A logarithmic singularity is reported as a pole (it is an asymptote). A very slowly converging168  cusp (1 − x^0.01) may be labelled a pole or `.none`. A function that overflows doubles (exp(800)) is drawn up to the clip169  boundary and not labelled.170- Inside an aliased band the envelope comes from 31–39 samples per column and can fall slightly short of the true extremes; an171  undefined point inside a band is reported as `.essential` even when a limit exists (x·sin(1/x) at 0).172- Between one and about two oscillations per pixel the output alternates between short polylines and band columns; both are173  truthful but the picture is busy.174- Functions defined on a scattered set of points (negative base with a varying rational exponent: `x^x` for x < 0,175  `sin(x)^(1/x)`) produce many fragments; the continuity checks are meaningless there.176- Polylines are clipped to the viewport ± one viewport height; a clip point is an interpolated point, not a function value.177178Implicit curves and regions — **reliability is limited by the grid**179- Finest cell 2 px, coarse scan 8 px. A closed loop smaller than about 6 px, or two branches closer than a cell, can be missed180  or merged without any notice. Self-intersections and cusps are resolved only to one cell.181- Zero sets without a sign change (squares, |…| = 0, identities) cannot be traced; they are detected in most cases and182  flagged `reliable = false`, but the detection is a local search, not a proof.183- The validation of crossings uses thresholds (2 % of the end values, 16-fold bracket shrink). An equation that is continuous184  but extremely steep across one cell can lose a vertex; a jump whose two sides are very unequal can keep one.185- Curves stop up to one cell (2 px) short of the boundary of the domain of F.186- "Too dense" is declared when more than 30 % of the cells contain the curve or saddle cells abound; this is conservative and187  heuristic. Inequality fills are 2 px cells; a sliver thinner than 8 px that misses every coarse corner and centre is not shaded.188189Parametric / polar190- 512 initial samples: a loop or excursion shorter than one initial step whose midpoint falls on the chord is missed. Increase191  `CurveOptions.initialSamples` for long parameter ranges (spirals over many turns).192- Jump vs pole is decided by distance from the screen (≥ 1000 viewport sizes = pole).193194Analysis195- Roots, extrema and intersections come from a 2000-sample scan of the range: two roots closer than range/2000 can be merged or196  missed, as can an extremum narrower than that. Even-multiplicity roots are located to about 1e-6 … 1e-8, not 1e-12.197- The pole check before integration is the plotter's scan at 2048 columns: a pole too narrow for it (see "sub-pixel features")198  would not be refused. End-point singularities are integrated by tanh-sinh and carry a warning, never a "verified" badge.199- Arc length and the derivative curve use finite differences (4–8 evaluations per point, relative accuracy about 1e-8); the200  derivative curve returns NaN at kinks and within about 1e-16 of a singularity.201- Inflection points require a sign change of a finite-difference second derivative above the rounding noise; very flat202  inflections can be missed.2032043D205- Vertices outside the z-range are clamped to it; the cut edge of the surface is therefore accurate only to one cell.206- Jumps or poles smaller than 5 % of the z-range across one cell are bridged.207- The painter's algorithm sorts triangle centroids: correct for height fields seen from outside, not guaranteed for208  self-overlapping parametric surfaces.209210General211- `Task.isCancelled` is polled once per pixel column / lattice row / 4096 triangles; a single evaluation of a very expensive212  user expression (nested `integral(…)`) is not interruptible.213- Text parsing: with `splitUnknownIdentifiers` (default) an unknown multi-letter name is a product of letters (`amp` → a·m·p)214  unless it is already a variable of the context.215
Files main
Menu

Theme