SPB Git

Repository Public MIT

VALIDATION.md 15.6 KB

# ORIXGraph — Validation

Status on 2026-11-20: swift build and swift test pass from the package directory with zero warnings (Swift 6 language mode, strict concurrency). 117 tests in 20 suites, in debug and in release (swift test -c release -Xswiftc -enable-testing).

Every number below was printed by the test suite (PerformanceTests.swift, lines starting with PERF| and COUNT|) on the machine the suite was run on: an Apple Silicon Mac (Apple M5 Max, macOS 27.0), wall-clock time from ContinuousClock, best of 7 runs. Debug figures are from an unoptimised build with the other test suites running in parallel; they vary by tens of percent from run to run. Nothing here was estimated.

# 1. The cardinal rule and how it is tested

A graph must not misrepresent a function. The tests do not only count polylines; three independent checks are applied to the output (see Tests/ORIXGraphTests/Support.swift):

  • hiddenBreaks: between every pair of consecutive vertices the function is re-evaluated at 64 points. It must be defined everywhere (except at a reported hole) and climb gradually: if one of the 64 sub-steps carries more than half of a rise of 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.
  • spans: no segment may contain an analytically known discontinuity strictly between its two vertices.
  • uncovered: at 4000 abscissas, wherever the function is visible on screen some polyline or band must cover that abscissa.

plus maxScreenError (distance in pixels from the true curve to the polyline, 8 points per segment) and bounded (all coordinates inside the padded viewport).

Function (800×600, x ∈ [−10, 10], y ∈ [−7.5, 7.5] unless noted) Polylines Reported discontinuities (checked against the analytic values)
1/x 2 pole at 0, limits −∞ / +∞; branches end on the clip boundary
1/x, 1/(x−1/3) on a grid that misses the pole 2 pole located to 1e-12
tan(x) 7 6 poles at (k + ½)π, to 1e-12
tan(x) on [0, 20π] 21 20 poles, every branch monotone
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
1/sin(x) 8 7 poles at kπ
floor(x) 21 20 jumps exactly on the integers, limits n−1 / n; all pieces horizontal
sign(x) 3 one jump at 0; the middle polyline is the isolated point (0, 0)
abs(x)/x 2 jump at 0
sqrt(x) 1 starts at exactly (0, 0); undefined interval [−10, 0]
sqrt(x − 1/3), sqrt(2 − x) off the grid 1 boundary to 1e-15
ln(x) 1 boundary at 0 with limit −∞; polyline extended down to the clip boundary
x^(1/3) 1 none (one piece through 0)
sin(x)/x 1 removable at 0, hole (0, 1)
(x²−1)/(x−1) 1 removable at 1, hole value 2 (to 1e-6)
piecewise(x<1, x, x>2, x−1) 2 undefined interval [1, 2] to 1e-9
sqrt(1−x²) 1 from (−1, 0) to (1, 0) exactly, all vertices on the circle to 1e-12
exp(x) 1 none; clipped at the top; exp on [0, 2000] (overflow to +∞) stays one bounded polyline
sin(1/x) on [−1, 1] 2 + 1 band band around 0 (inside
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
sin(100x) (2.5 px per period) 1 none; stays a line, max error 0.21 px

A further 32 awkward functions (gamma(x), tan(1/x), 1/(x − floor(x)), tan(tan(x)), floor(sin(50x)), exp(1/x), ln(abs(x)), sqrt(sin(100x)), x!, …) pass the same four checks (AwkwardFunctions.staysHonest).

Implicit curves, parametric / polar curves and surfaces have their own versions of the rule:

  • 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.
  • 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.
  • tan(x) − y = 0: 7 branches, > 500 false crossings rejected, no segment crosses a pole line. floor(x) − y = 0: 20 treads, no riser.
  • (x − y)² = 0: nothing drawn and reliable == false with a reason; sin(40x) = cos(40y) at ±10: reliable == false.
  • 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.
  • (t, floor t), (t, 1/t), (t, tan t), (√t, t): broken at jumps / poles / domain boundary, located in t.
  • 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.

# 2. Measured accuracy and point counts (800×600)

Smooth functions tested for < 0.5 px (Accuracy.smoothFunctionsWithinHalfAPixel): sin x, x², x³ − 3x, eˣ, e^(−x²), 5e^(−x²/2), cos 3x + x/2, x⁵/100 − x³/3 + x, |x| − 2, √|x|, atan 5x, 7 sin x.

Function Points Evaluations Polylines Max error (px)
sin(x) 801 1601 1 0.003
x^2 381 1327 1 0.006
x^3 − 3x 621 2683 1 0.019
exp(x) 561 1535 1 0.003
exp(−x^2) 801 1601 1 0.006
1/x 940 2413 2 0.017
tan(x) 1689 6179 7 0.016
sqrt(x) 402 1691 1 0.156
ln(x) 435 1876 1 0.027
floor(x) 1021 3949 21 0.000
sin(x)/x 802 1759 1 0.001
sin(100x) 7119 28628 1 0.211

Rule of thumb: one point per pixel column (fewer where the curve is off screen), two evaluations per column, more only where the curve bends, is steep or breaks. Extreme windows: sin x on [10⁹, 10⁹ + 10] and x² on [−10⁻⁹, 10⁻⁹] are within 0.5 px; spans from 10⁻²⁰⁰ to 10²⁰⁰ sample normally; windows narrower than 4096 ulps are widened by Viewport.

Analysis against analytic values (tolerances are those asserted by the tests):

Quantity Result
roots of x³ − x; √2; cos x on [−10, 10] 1e-12 … 1e-13
extrema of x³ − 3x at ∓1; of sin x x to 1e-9, y to 1e-12
sin ∩ cos on [−2π, 2π] (4 points) 1e-12
tangent of x² at 1 slope 2, intercept −1 to 1e-11
∫₀^π sin = 2; ∫ e^(−x²) on [−8, 8] = √π; ∫₋₁¹ sin x / x 1e-12
area between x and x² on [0, 1] = 1/6 1e-14
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
poles as roots / intersections (1/x, tan x, 1/x vs 2/x, tan x vs tan x + 1) never reported
∫ across a pole (1/x, 1/(x−0.3)², tan x, 1/sin x), across an undefined stretch refused with a message
ticks ≤ 25 major ticks for 77 184 combinations of span 10⁻³⁰⁰ … 10³⁰⁰, offset, pixel length and mode; degenerate, inverted and non-finite input included

# 3. Measured performance

Best of 7, milliseconds. "Apple Silicon Mac, release build" and "debug build" as actually run (same machine, same session).

Task Release Debug Output
explicit 1200×800 sin(x) 0.113 5.8 1201 points, 2401 evaluations
explicit 1200×800 x^2 0.077 3.7 539 points
explicit 1200×800 x^3 − 3x 0.238 7.3 861 points
explicit 1200×800 1/x 0.170 7.9 1394 points, 2 polylines
explicit 1200×800 tan(x) 0.578 15.9 2395 points, 7 polylines
explicit 1200×800 exp(−x^2) 0.100 5.6 1201 points
explicit 1200×800 sqrt(x) 0.071 4.5 609 points
explicit 1200×800 floor(x) 0.246 9.6 19 polylines
explicit 1200×800 sin(x)/x 0.119 5.4 1202 points
explicit 1200×800 sin(100x) (refined to the cap) 1.37 37.3 10073 points, 40379 evaluations
explicit 1200×800 sin(1000x) (all band) 1.08 20.3 1200 band columns
implicit 400×400 x² + y² = 25 0.57 10.7 384 points, 9053 evaluations
implicit 400×400 sin(x) = cos(y) 2.05 31.2 2510 points, 30403 evaluations
implicit 400×400 xy = 1 0.55 9.6 392 points
implicit 400×400 tan(x) = y 1.63 22.8 1407 points
parametric 1200×800 (sin 3t, cos 2t) 0.021 0.27 513 points
surface 60×60, precise normals 0.61 11.4 3721 vertices, 7200 triangles
surface 60×60, grid normals 0.28 6.4
painter projection + depth sort, 7200 triangles 0.48 5.3
roots + extrema of x³ − 3x on [−10, 10] 0.13 2.0
∫ sin on [0, 2π] with shaded regions 0.25 4.8
slider update (compile + sample 1200×800) a sin(bx) + c 0.12 2.7 1201 points

The implicit target (400×400 px in < 50 ms) is met with a wide margin in release and also in debug on this machine; the debug figure for sin(x) = cos(y) ranged from 28 to 50 ms over the runs made during development, so the test asserts 50 ms only for release builds.

# 4. How it works (short)

  • Explicit sampler. Uniform grid, one sample per pixel column (no jitter). Each column is tested at one interior point whose position varies from column to column (so that no frequency can alias with both the grid and the test points), and is bisected (up to 2⁶ pieces) while the screen distance to the chord exceeds 0.2 px; inside refined regions three points per piece are tested. Columns that rise by more than 8 px, or whose test fails, get 7 irregular probes: three or more reversals (or two that are not a single adverse step, decided with 8 more samples) mean aliasing and the column becomes a min/max band; inside a band every column is probed. At the refinement cap, a remaining gap is bisected down to adjacent doubles: if it shrinks the piece is continuous, otherwise one-sided limits are estimated from geometric sequences of samples and the break is classified (jump / pole / essential). Undefined samples are bracketed by bisection to adjacent doubles; an isolated undefined point with equal finite limits is a hole and is drawn through. Poles between two samples off the same edge are found by golden-section search on |f|. Polylines are clipped (not clamped) to the viewport ± one height.
  • Implicit. Coarse lattice (8 px) → refine cells with a sign change, an undefined corner, or |F| small compared with its variation → marching squares at 2 px with propagation into neighbouring coarse cells. Every crossing is validated: F at the interpolated vertex must be far below both end values, otherwise the bracket is shrunk 16-fold and must have come down (zero) rather than stayed (jump) or grown (pole). Segments are stitched through shared lattice edges.
  • Surfaces. Grid mesh; z-range by Tukey fences; triangles dropped when a vertex is undefined, when all three are clipped on the same side, or when an edge that climbs > 5 % of the z-range (or is clipped) fails the same shrinking-gap test.

# 5. Known limitations (read before promising anything to users)

Explicit curves

  • Sub-pixel features can be missed. A spike, a dip or an even-order pole that lies wholly between two grid samples and is not hit by that column's test point is not seen when both neighbours look flat. (Odd poles and jumps change the level and are found; even poles are found when the neighbouring samples are already off screen or when a sample lands on them.)
  • Classification is numerical. A logarithmic singularity is reported as a pole (it is an asymptote). A very slowly converging cusp (1 − x^0.01) may be labelled a pole or .none. A function that overflows doubles (exp(800)) is drawn up to the clip boundary and not labelled.
  • Inside an aliased band the envelope comes from 31–39 samples per column and can fall slightly short of the true extremes; an undefined point inside a band is reported as .essential even when a limit exists (x·sin(1/x) at 0).
  • Between one and about two oscillations per pixel the output alternates between short polylines and band columns; both are truthful but the picture is busy.
  • Functions defined on a scattered set of points (negative base with a varying rational exponent: x^x for x < 0, sin(x)^(1/x)) produce many fragments; the continuity checks are meaningless there.
  • Polylines are clipped to the viewport ± one viewport height; a clip point is an interpolated point, not a function value.

Implicit curves and regions — reliability is limited by the grid

  • 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 missed or merged without any notice. Self-intersections and cusps are resolved only to one cell.
  • Zero sets without a sign change (squares, |…| = 0, identities) cannot be traced; they are detected in most cases and flagged reliable = false, but the detection is a local search, not a proof.
  • The validation of crossings uses thresholds (2 % of the end values, 16-fold bracket shrink). An equation that is continuous but extremely steep across one cell can lose a vertex; a jump whose two sides are very unequal can keep one.
  • Curves stop up to one cell (2 px) short of the boundary of the domain of F.
  • "Too dense" is declared when more than 30 % of the cells contain the curve or saddle cells abound; this is conservative and heuristic. Inequality fills are 2 px cells; a sliver thinner than 8 px that misses every coarse corner and centre is not shaded.

Parametric / polar

  • 512 initial samples: a loop or excursion shorter than one initial step whose midpoint falls on the chord is missed. Increase CurveOptions.initialSamples for long parameter ranges (spirals over many turns).
  • Jump vs pole is decided by distance from the screen (≥ 1000 viewport sizes = pole).

Analysis

  • Roots, extrema and intersections come from a 2000-sample scan of the range: two roots closer than range/2000 can be merged or missed, as can an extremum narrower than that. Even-multiplicity roots are located to about 1e-6 … 1e-8, not 1e-12.
  • The pole check before integration is the plotter's scan at 2048 columns: a pole too narrow for it (see "sub-pixel features") would not be refused. End-point singularities are integrated by tanh-sinh and carry a warning, never a "verified" badge.
  • Arc length and the derivative curve use finite differences (4–8 evaluations per point, relative accuracy about 1e-8); the derivative curve returns NaN at kinks and within about 1e-16 of a singularity.
  • Inflection points require a sign change of a finite-difference second derivative above the rounding noise; very flat inflections can be missed.

3D

  • Vertices outside the z-range are clamped to it; the cut edge of the surface is therefore accurate only to one cell.
  • Jumps or poles smaller than 5 % of the z-range across one cell are bridged.
  • The painter's algorithm sorts triangle centroids: correct for height fields seen from outside, not guaranteed for self-overlapping parametric surfaces.

General

  • Task.isCancelled is polled once per pixel column / lattice row / 4096 triangles; a single evaluation of a very expensive user expression (nested integral(…)) is not interruptible.
  • Text parsing: with splitUnknownIdentifiers (default) an unknown multi-letter name is a product of letters (amp → a·m·p) unless it is already a variable of the context.
Files main
Menu

Theme