SPB Git

Repository Public MIT

graph-engine.md 15.3 KB

# Graph engine (ORIXGraph and ORIXFeatureGraph)

Graphing is split in two packages. ORIXGraph is pure computation: expressions in, render-ready geometry out, with no SwiftUI, UIKit or CoreGraphics. ORIXFeatureGraph owns the state of the Graph environment and the one renderer that turns that geometry into pixels. The engine's public surface is in Packages/ORIXGraph/API.md; what it guarantees, the measured accuracy and the limits are in Packages/ORIXGraph/VALIDATION.md.

The rule the whole pipeline serves: a graph must not misrepresent a function. A curve is never joined across a pole or a jump, an oscillation faster than the pixels is drawn as a band and not as a fake line, and anything the engine could not establish is reported as a notice.

# Pipeline

flowchart TD
    Text["Entry text<br/>'a*sin(x)/x', 'x^2 + y^2 = 25', 'z = x*y'"] --> Parser["PlotParser.parse<br/>(ORIXExpression parser + EvalContext)"]
    Parser --> Item["PlotItem<br/>kind · parameters · domain · style"]
    Ctx["EvalContext<br/>angle mode · slider values · user functions"] --> Compile
    Item --> Compile["PlotItem.compiled(context:)<br/>CompiledExpression closures, NaN where undefined"]
    Compile --> Exp["Sampler.sampleExplicit / sampleExplicitX<br/>adaptive, discontinuity classification, aliased bands"]
    Compile --> Cur["Sampler.sampleParametric / samplePolar"]
    Compile --> Imp["ImplicitPlotter.plot / region<br/>adaptive marching squares, validated crossings"]
    Compile --> Sur["SurfacePlotter.mesh<br/>SurfaceMesh"]
    Exp --> Geo["PlotGeometry<br/>polylines · bands · discontinuities · holes · markers · fill · notices"]
    Cur --> Geo
    Imp --> Geo
    VP["Viewport<br/>window + pixel size"] --> Exp
    VP --> Cur
    VP --> Imp
    Geo --> R2["GraphRenderer (SwiftUI Canvas)<br/>grid · axes · curves · bands · holes · asymptote guides · regions"]
    Sur --> Norm["SurfaceMesh.normalized()<br/>cube [−1, 1]³"]
    Norm --> Paint["PainterRenderer.project<br/>Camera3D, far → near"]
    Paint --> R3["Surface3DView (SwiftUI Canvas)"]
    Compile --> An["GraphAnalysis<br/>roots · extrema · intersections · tangent · integral · arc length · trace · table"]
    An --> R2

GraphEngine.geometry(for:viewport:context:) is the single entry point from a PlotItem to a PlotGeometry. It is synchronous and thread-safe; geometryAsync and geometries are @concurrent wrappers that never run on the main actor and throw CancellationError.

# Engine source files

All under Packages/ORIXGraph/Sources/ORIXGraph/.

File Role
PlotParser.swift Entry text → PlotItem (explicit, x = g(y), parametric, polar, implicit, inequality, points, surface, parameter)
PlotItem.swift Plot definitions as pure data and their compilation to closures
Viewport.swift Visible window in function coordinates with its pixel size; screen mapping, pan, zoom, equal aspect, robust auto-fit
Sampler.swift Adaptive sampler for y = f(x)
CurveSampler.swift Adaptive sampler for parametric and polar curves
ImplicitPlotter.swift Implicit curves F(x, y) = 0 and inequality regions
Surface.swift 3D surfaces z = f(x, y), parametric surfaces, contours, inspection
Camera3D.swift Orbit camera matrices, point projection, painter's-algorithm ordering
Analysis.swift Roots, extrema, intersections, tangent, derivative curve, integrals with shading, arc length, trace, tables
Ticks.swift Axis ticks (1-2-5 steps or multiples of π), minimal-digit labels
Geometry.swift Value types shared by the samplers (points, polylines, envelope bands, discontinuities, notices)
Data.swift Scatter / series helpers, least-squares line for the fit overlay, CSV export
GraphEngine.swift Entry point, async wrappers, auto-fit of several items

# Stage 1 — text to PlotItem

PlotParser.parse(_:context:) uses the expression parser of ORIXExpression and classifies the line:

Text PlotItem.kind
sin(x), y = x^2, f(x) = x^2 .explicit
x = y^2 .explicitX
(cos(t), sin(2t)) .parametric
r = 1 - cos(θ) .polar
x^2 + y^2 = 25 .implicit(lhs:rhs:)
y < x^2, 1 < x < 2 .inequality(condition:boundaries:)
(1, 2), (3, 4) .points
z = x*y .surface
a = 3 .parameter(name:value:) (sets a slider; not drawable)

item.parameters lists the free identifiers; the UI creates one slider per name and injects the values through EvalContext.variables. item.compiled(context:) turns the expressions into Double closures that return NaN where the expression is undefined; compilation is repeated on every slider change.

# Stage 2 — sampling

# Explicit sampler (Sampler.sampleExplicit)

  • Grid: one sample per pixel column, no jitter. Each column is also 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.
  • Refinement: a column is bisected (up to 2⁶ pieces, SamplerOptions.maxDepth 6) while the screen distance to the chord exceeds 0.2 px (tolerance); inside refined regions three points per piece are tested.
  • Aliasing: 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: the column becomes a min/max EnvelopeBand, and inside a band every column is probed.
  • Discontinuity classification: 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 as .jump, .pole or .essential.
  • Domain: undefined samples are bracketed by bisection to adjacent doubles (.undefinedInterval). An isolated undefined point with equal finite limits is a .removable discontinuity: the curve is drawn through and a hole marker is emitted.
  • Even poles: poles between two samples off the same edge are found by golden-section search on |f|.
  • Clipping: polylines are clipped (not clamped) to the viewport ± one viewport height.

# Parametric and polar (CurveSampler)

512 initial samples (CurveOptions.initialSamples), refined by screen-space deviation up to depth 10, broken at undefined values and jumps. Jump versus pole is decided by distance from the screen (≥ 1000 viewport sizes = pole).

# Implicit curves and regions (ImplicitPlotter)

A coarse lattice (8 px) is scanned first; cells with a sign change, an undefined corner, or |F| small compared with its variation are refined, and marching squares runs at 2 px (ImplicitOptions.cellSize) 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 (a zero) rather than stayed (a jump) or grown (a pole). Segments are stitched through shared lattice edges. The result carries reliable and its reasons; inequality fills are 2 px cells.

# Stage 3 — geometry

PlotGeometry is the contract between engine and renderer, in function coordinates:

Field How it must be drawn
polylines Stroke each one separately; never join two. A single-point polyline is an isolated point
bands Fill the band polygon at reduced opacity; do not stroke a line through it
discontinuities Poles may get a dashed asymptote guide; removable ones get hole markers
holes, markers Open circles; scatter points
fill, strictBoundary Inequality region; dashed boundary for < / >
notices, isComplete Shown to the user (.aliased, .unreliable, .incomplete, .rejectedFalseContour, .info)

# Stage 4 — rendering (ORIXFeatureGraph)

All under Packages/ORIXFeatureGraph/Sources/ORIXFeatureGraph/.

  • GraphModel.swift holds entries, sliders, the viewport and the sampled geometry. Sampling runs off the main actor, one pass per entry at a time; a request that arrives meanwhile marks the entry dirty, the running pass is applied when it lands and the latest state is sampled next. Geometry is stored with the viewport it was sampled for and drawn through the current viewport, so pan and zoom follow the fingers while fresh samples are on their way.
  • GraphRenderer.swift is the one 2D renderer (grid, axes, curves, bands, holes, asymptote guides, regions, markers). It is shared by the interactive graph (GraphCanvasView.swift), the embeddable preview used by other environments (GraphPreview.swift, exposed through FeatureRegistry.graphPreview), the exports and the tests.
  • The render tests (Packages/ORIXFeatureGraph/Tests/ORIXFeatureGraphTests/RenderTests.swift) rasterise the renderer and inspect pixels: no stroke in the column of the asymptote of 1/x, none at any asymptote of tan x, no risers on floor(x).

# Analysis (GraphAnalysis)

Function Method
roots, intersections 2000-sample scan with RootFinder.allRoots (Brent on each sign change); poles and jumps through zero are excluded, shared poles of two curves too
extrema Scan, golden-section refinement, then Brent on the Ridders derivative; no end points, plateaus or poles
inflections Sign change of a finite-difference second derivative (800 samples)
tangent, derivative, derivativeFunction Ridders differentiation with an error estimate; tangent throws .refused at corners and undefined points
integral, areaBetween The interval is first scanned for poles and undefined stretches with the plotter at 2048 columns and refused with a message if one is inside. Adaptive Gauss–Kronrod between jumps; tanh-sinh for end-point singularities (with a warning). Regions are split at roots / intersections for shading
arcLength Gauss–Kronrod on √(1 + f′²) with a finite-difference derivative
trace, pointsOfInterest, table Cursor with snapping to precomputed points; nil where undefined

Every PointOfInterest and estimate carries a VerificationReport; the UI shows a badge only when isVerified.

# 3D

  • SurfacePlotter.mesh builds a grid mesh of (columns + 1) × (rows + 1) vertices. The automatic z-range uses Tukey fences so that a pole cannot flatten the rest of the surface. A triangle is dropped when a vertex is undefined, when all three vertices are clipped on the same side, or when an edge that climbs more than 5 % of the z-range (or is clipped) fails the same shrinking-gap test as the 2D sampler. SurfaceMesh carries vertices, normals, indices, colorParameters, valid, clipped, zMin/zMax, droppedTriangles and notices.
  • SurfaceMesh.normalized() maps the mesh into the cube [−1, 1]³ so that the picture does not depend on axis units.
  • Camera3D is a pure-math orbit camera (yaw, pitch, distance) producing column-major view-projection matrices in the OpenGL clip-space convention, plus project(_:width:height:).
  • PainterRenderer.project projects every triangle and sorts them far to near by the depth of the triangle centroid (painter's algorithm); depthOrder returns the order alone.
  • Renderer. The app draws 3D with a SwiftUI Canvas painter's renderer over the engine's mesh (Surface3DView.swift), so the triangles the engine dropped stay holes in the picture. Surface triangles and contour segments are depth-sorted together; fills are not antialiased so that adjacent facets meet without seams. When triangles were dropped, Surface3DModel.swift surfaces a notice ("… cells are left open where the function is undefined, jumps or has a pole").
  • SurfacePlotter.contours traces level sets by marching squares with the same validated crossings as implicit curves; inspect returns height, gradient and normal at a point; parametricMesh handles (u, v) ↦ (x, y, z).

# Guarantees

As asserted by the test suite (Packages/ORIXGraph/Tests/ORIXGraphTests/Support.swift), three independent checks are applied to explicit plots, plus two bounds:

Check Meaning
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. A segment that hides a jump or a pole fails
spans No segment contains an analytically known discontinuity strictly between its two vertices
uncovered At 4000 abscissas, wherever the function is visible some polyline or band covers that abscissa
maxScreenError Distance in pixels from the true curve to the polyline, 8 points per segment; smooth functions are tested for < 0.5 px
bounded All coordinates lie inside the padded viewport

Implicit curves, parametric / polar curves and surfaces have their own versions of the rule (no contour across a pole or a jump; unreliable zero sets flagged reliable == false with a reason; no triangle across a pole).

# Documented limits

Stated in VALIDATION.md §5; the main ones:

  • Explicit curves. A spike, dip or even-order pole lying wholly between two grid samples and not hit by the column's test point is not seen when both neighbours look flat. Classification is numerical: a logarithmic singularity is reported as a pole; a very slowly converging cusp may be labelled a pole or .none. 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. Functions defined on a scattered set of points produce many fragments.
  • 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 notice. Zero sets without a sign change cannot be traced; their detection is a local search, not a proof. Curves stop up to one cell short of the boundary of the domain of F. A sliver thinner than 8 px that misses every coarse corner and centre is not shaded.
  • Parametric / polar. A loop or excursion shorter than one initial step whose midpoint falls on the chord is missed.
  • Analysis. Two roots closer than range/2000 can be merged or missed; even-multiplicity roots are located to about 1e-6 … 1e-8. A pole too narrow for the 2048-column scan would not be refused before integration. Arc length and the derivative curve use finite differences (relative accuracy about 1e-8).
  • 3D. Vertices outside the z-range are clamped, so the cut edge is accurate only to one cell. Jumps or poles smaller than 5 % of the z-range across one cell are bridged. Sorting triangle centroids is 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; one evaluation of a very expensive expression is not interruptible. With splitUnknownIdentifiers (default) an unknown multi-letter name is read as a product of letters unless it is already a variable of the context.
Files main
Menu

Theme