Skip to content

Benchmark

Jump to bottom
Jakub Ziolkowski edited this page Aug 25, 2026 · 4 revisions

Benchmark

Performance and correctness benchmarks for DiGi.Geometry.

All benchmarks live as [Fact] tests in the DiGi.Geometry.xUnit test project (DiGi.Test/DiGi.Geometry.xUnit/Facts/), so they can be re-run and re-verified at any time rather than treated as a one-off snapshot.

Test machine spec

Component Specification
CPU AMD Ryzen 9 9950X, 16 cores / 32 threads (Environment.ProcessorCount = 32)
RAM 61.4 GB
OS Windows 11 Pro (10.0.26200)
.NET SDK 10.0.400
Build config Release (unless noted)

Numbers are machine-specific — re-run the benchmarks on your own hardware before drawing conclusions for a different environment.

Vertex mean vs. area centroid — AverageAndCentroid_ScalingBenchmark

File: Facts/OptimizationPerformance.cs

Methods compared:

  • DiGi.Geometry.Planar.Query.Average(IEnumerable<Point2D>) — the vertex mean center, C = (1/n) · Σ Pᵢ; a single pass accumulating x/y (≈ 2 additions per vertex).
  • DiGi.Geometry.Planar.Query.Centroid(IEnumerable<Point2D>) — the area centroid (polygon centre of mass), C = 1/(6A) · Σ (Pᵢ + Pᵢ₊₁)(xᵢyᵢ₊₁ − xᵢ₊₁yᵢ); the shoelace-weighted sum (≈ 4 multiply-adds per vertex).

Both are O(n) single-pass queries. The benchmark sweeps the point count over {100, 1 000, 10 000, 100 000, 1 000 000} — a regular polygon inscribed in a circle of radius 10 centred on the origin — and reports the per-call time at each scale. A warm-up call precedes the measured loop (JIT), and the number of repeats is scaled inversely with the point count (repeats = Max(1, 2 000 000 / count)) so the total measured work stays comparable across scales. Each scale also asserts both queries resolve to the origin (correctness), so the timings compare equivalent work.

Context: DiGi.Geometry.Planar.Query.InternalPoint uses the area centroid as its primary internal-point candidate and the vertex mean (Average) as the intermediate fallback before the NetTopologySuite InteriorPoint path — this benchmark quantifies the cost of that fallback.

Results (Release build)

points Average (µs/call) Centroid (µs/call) ratio (Centroid / Average)
100 3.38 2.76 0.82×
1,000 28.59 26.50 0.93×
10,000 48.10 56.64 1.18×
100,000 251.16 709.93 2.83×
1,000,000 2,452.20 3,984.75 1.62×

Results (Debug build, for reference)

points Average (µs/call) Centroid (µs/call) ratio (Centroid / Average)
100 1.33 2.42 1.82×
1,000 12.83 22.80 1.78×
10,000 129.11 224.17 1.74×
100,000 1,304.80 2,629.66 2.02×
1,000,000 12,171.55 20,470.20 1.68×

Analysis

  • Both scale linearly — per-call time grows ~10× for each 10× increase in point count, confirming the O(n) single-pass behaviour of both queries with no scale-dependent surprise.
  • Average does strictly less work per vertex — ~2 additions versus the shoelace sum's ~4 multiply-adds — and, for a List<Point2D> input, it also avoids the internal ToArray() copy that Centroid incurs (its point2Ds as Point2D[] array fast-path misses for a List). So Average is both fewer FLOPs and one fewer O(n) allocation.
  • Debug (no JIT optimisation) shows that raw work gap uniformly: Average is ~1.7–2× faster at every size.
  • Release (JIT-optimised) tells a more nuanced story. At tiny inputs (≤ 1 000 points) both finish in a few µs and per-call enumeration / measurement overhead dominates, so the ratio is noise and can even invert (~0.8–0.9×). Average's advantage emerges in the mid-range (1.18× at 10 000, ~2.8× at 100 000) and stays positive at 1 000 000 (~1.5–2×), though that top row is the noisiest — only 2 timed repeats, run-to-run variance ≈ ±20%.
  • Takeaway for InternalPoint: on realistic polygons both centres are trivially cheap (single-digit µs), so the vertex mean is essentially free to try as an intermediate fallback. It is chosen there for correctness/robustness — being a convex combination of the vertices it lands strictly inside more often — and the modest constant-factor speed edge is a bonus, not the reason. The centroid is not slow; the ordering is a quality decision, and the timings just confirm the extra fallback adds negligible cost.

A fixed-size companion test, AverageAndCentroid_PerformanceComparison (same file, 10 000 points), asserts both queries agree on the origin and that Average is not slower than Centroid beyond a generous noise margin, guarding against a future regression that would invert this relationship.

Polyhedron closure — Polyhedron_IsClosed_Benchmark

File: Facts/Polyhedron_IsClosed_Comparison.cs

Methods compared — four implementations of the same question, run on identical inputs in one process:

  • DiGi.Geometry.Spatial.Query.IsClosed<TPolygonalFace3D>(Polyhedron<TPolygonalFace3D>?, bool, double) — shipped. Every ring segment becomes a half-edge and no vertex is ever merged; two half-edges are compatible when their endpoints match pairwise within the tolerance in either traversal direction, and the solid is closed when the compatibility graph admits a perfect matching.
  • Facts.IsClosed_VertexWeld<TPolygonalFace3D>(...) — the previous implementation, kept verbatim in the test file. Welds face vertices into shared integer indices through a tolerance-sized spatial hash, then counts each edge by its (int, int) index pair.
  • Facts.IsClosed_Greedy<TPolygonalFace3D>(...) — the greedy two-pass edge matching proposed first on issue #1.
  • Facts.IsClosed_ComponentMatching<TPolygonalFace3D>(...) — the component perfect matching proposed second on the same issue.

Why it was replaced. Welding mutates topology, so the tolerance did not only forgive gaps — it destroyed genuine features. Raising it past the size of a real feature collapsed that feature and broke the edge counts, so closure was not monotonic: a solid closed at one tolerance could be reported open at a coarser one. The measured consequence is in the monotonicity table below.

Editable knobs — all at the top of the benchmark method's class in Facts/Polyhedron_IsClosed_Comparison.cs:

  • Polyhedron_IsClosed_Benchmark_Operations (600 000) — total half-edge evaluations each scenario aims for; the repeat count of every row is max(1, Operations / half-edges), so every figure is per call.
  • Polyhedron_IsClosed_Benchmark_Batches (5) — timed batches per measurement; the fastest is reported.
  • Polyhedron_IsClosed_Benchmark_WarmUp (60) — minimum warm-up calls before timing.
  • Polyhedron_IsClosed_Extrusion(int count) in Facts/Polyhedron.cs — the extrusion size.

Results (Release)

Per call, microseconds. Lower is better.

Scenario Half-edges Vertex weld (previous) Greedy edge matching Component matching Shipped Shipped / previous
500-gon extrusion 3 000 354.1 1 515.9 1 692.7 565.3 1.60×
9 800-face ellipsoid 29 400 6 389.4 15 226.9 27 946.5 3 829.2 0.60×
Open cube, 5 faces 20 2.3 3.6 4.9 4.1 1.76×
0.03 m step, tolerance 0.05 36 3.7 4.7 9.3 1.9 0.51×
0.1 m slot, tolerance 0.15 48 4.9 6.4 12.5 9.8 2.01×
Two thin slabs, tolerance 0.05 48 4.7 6.8 13.7 11.6 2.45×

Monotonicity of the default criterion

Swept over 1E-06, 1E-05, 0.0001, 0.001, 0.005, 0.01, 0.02, 0.03, 0.04, 0.05, 0.06, 0.09, 0.1, 0.11, 0.15, 0.2, 0.5; T = closed. A watertight solid must read T everywhere, and no row may ever go from T back to ..

Scenario Vertex weld (previous) Shipped
500-gon extrusion TTTTTTTTTTTTTT... TTTTTTTTTTTTTTTTT
9 800-face ellipsoid TTTTT............ TTTTTTTTTTTTTTTTT
Open cube, 5 faces ................. .................
0.03 m step TTTTTTTTTTTTTTTTT TTTTTTTTTTTTTTTTT
0.1 m slot TTTTTTTTTTTTTTT.. TTTTTTTTTTTTTTTTT
Two thin slabs TTTTTTTTTTTTTTTTT TTTTTTTTTTTTTTTTT
Two stacked boxes TTTTTTTTTTTTTTTTT TTTTTTTTTTTTTTTTT
Box, top lifted 0.05 ..........TTTTTTT ..........TTTTTTT

Analysis

  • The correctness result is the ellipsoid row. The previous implementation reports an exactly watertight 9 800-face ellipsoid as open from a tolerance of 0.01 upwards, having reported it closed at every finer value — welding past the edge length of the tessellation collapses whole triangles. The 500-gon loses it at 0.15 and the slot solid at 0.2. All three are pinned by Polyhedron_IsClosed_Comparison_Monotonicity.
  • Both designs proposed on the issue are 3–7× slower than what shipped, and the gap is structural rather than incidental: each probes the 27 cells around every half-edge. The shipped fast path does one lookup per half-edge on a plain 64-bit key, and the full pass walks occupied cells rather than half-edges and probes only the 13 forward neighbours, so every unordered pair is still examined exactly once at a quarter of the lookups.
  • The fast path is a shortcut to the same answer, not a weaker one. Each half-edge carries one key derived from its two endpoints; a bucket of exactly two compatible half-edges is a matched pair, and once every half-edge is matched a perfect matching of the whole graph is in hand — which is the closure criterion itself. Anything it cannot resolve falls through to the full pass, so it can only save work, never decide wrongly.
  • Two hash details decide whether it fires at all. The cell index is rounded, not floored: flooring puts the cell boundary on every exact multiple of the tolerance, which is exactly where clean geometry sits, so a face at z = 0 whose neighbour reprojects to -1E-16 was keyed one cell apart and nearly every pair was split. And the three ordinates are mixed one at a time, each exclusive-or followed by a multiply: an exclusive-or of multiplied ordinates collided 108 of the 1 500 edge keys of the 500-gon, and combining two ordinates before the first multiply collided 694 of them — a polygon on a circle carries the vertex with its two ordinates swapped, and exclusive-or is symmetric. Either was enough to send the whole solid down the slow path.
  • Where the shipped predicate costs more, it is buying the right answer. The slot and thin-slab rows are solids whose features sit at the tolerance, so the fast path cannot resolve them and the full pass runs — roughly 2× the previous cost on inputs of a few dozen half-edges. That is the geometry the previous implementation answered incorrectly.
  • The remaining floor is the per-face clone chain, not the algorithm. Reading one face allocates through Planar<T>.Plane (a fresh Plane, plus Plane.AxisX, which recomputes a cross product, and AxisY), Planar<T>.Geometry2D (a deep clone of the whole 2D face including every Point2D) and PolygonalFace2D.Edges (which clones every ring a second time). Measured in isolation it is ~24 % of the previous implementation's time on both the 500-gon and the ellipsoid, and every implementation in the table pays it identically. Removing it needs GetX(bool clone) overloads on Planar<T> / IPlanar / PolygonalFace2D / IPolygonalFace2D and is deliberately out of scope — that is where any further gain has to come from.

Benchmarking note

Timings for this method are worthless without warm-up. Measured with a bare Stopwatch loop the same implementation reported 2 052 µs and 373 µs in two harnesses that differed only in how many calls preceded the timer, and the ranking of two implementations inverted between them. The benchmark therefore warms every implementation past the call count at which the runtime promotes it to optimised code, then reports the fastest of five batches. Treat the ratios, measured under identical in-process conditions, as the result and the absolute figures as environment-specific.

Terrain footprint cutting — Mesh3D_Difference_Performance

File: Facts/Mesh3DDifference.cs, Facts/Mesh3DDifferenceDenseCluster.cs

Methods compared:

  • DiGi.Geometry.Spatial.Query.Difference(Mesh3D, IEnumerable<IPolygonalFace2D>, double) — the whole operation being timed.
  • DiGi.Geometry.Planar.Query.Triangulate(Polygon, double) — the part that changed, measured through it.

Cutting building outlines out of a terrain surface in plan view, at the sizes, sampling steps and building densities the terrain service and the building store answer with. The surface is a sloped lattice in PL-1992 coordinates; each case differs in how the lattice resolution compares to the buildings, because that ratio — not the triangle count — is what drives the cost.

The "before" column is the previous implementation, which triangulated a clipped remainder with NetTopologySuite.Triangulate.ConformingDelaunayTriangulationBuilder and clipped each Delaunay triangle back with an NTS Intersection, recursing on the fragments. The "after" column is ear clipping via NetTopologySuite.Triangulate.Polygon.PolygonTriangulator, which uses only the corners the remainder already has. See issue #2.

Editable knobs: lattice origin, cell size and cell count, and outline count, per case in Mesh3D_Difference_Measure(size, count, buildings, lines) and Mesh3D_Difference_MeasureDense(lines). RNG seeds are fixed constants — 20260822 for the scattered cases, 20260825 for the dense one.

Results (Release build, benchmark run in isolation, three runs)

Case Triangles in Outlines Conforming Delaunay Ear clipping Speed-up
10 m lattice, finer than the buildings 20 000 1 000 1306 / 1402 / 1293 ms 685 / 670 / 790 ms ~1.9×
50 m lattice, coarser — holed remainders 800 250 114 / 117 / 130 ms 35 / 33 / 35 ms ~3.3×
100 m lattice, dense touching terraces 200 1 000 ConstraintEnforcementException 96 / 88 / 103 ms —

Output triangle count on the 50 m case fell from 3 133 to 2 657 (−15 %).

Analysis

  • The coarse lattice is the hard case, not the fine one. When the surface is sampled more finely than the buildings, a cut leaves simple convex remainders that never reach a triangulator at all — the fan in Difference.cs handles them. When it is coarser, whole buildings fall inside single triangles, so every remainder carries holes and the general triangulator runs on all of them. The stored counties are sampled at 10 m to 100 m, so both regimes occur in production.
  • Constraint enforcement was a dead end, not a slow path. The conforming Delaunay triangulator inserts Steiner points and enforces the constraints by splitting; on a remainder carrying narrow slivers — which is what neighbouring footprints leave — the splitting fails to converge and NTS throws. Ear clipping has no constraints to enforce, so the third case goes from unusable to 0.1 s.
  • Fewer triangles out. Ear clipping cuts the remainder directly instead of clipping a Delaunay cover of it, so it produces no fragments that need re-clipping and re-triangulating.
  • Winding is part of the contract. PolygonHoleJoiner always emits a clockwise ring, and every triangle produced here ends up in a rendered mesh where the way a triangle turns is the side that is lit. Triangulate_Winding guards it.

Benchmarking note

These figures are only comparable because each was measured with the benchmark [Fact] run alone (dotnet test … --filter "FullyQualifiedName~Mesh3D_Difference_Performance"). The same 10 m case reports 983 ms when read off a full-suite run against 1306–1402 ms in isolation, because xUnit runs collections in parallel and the rest of the suite competes for cores. The offset is not constant, so an in-suite figure and an isolated figure cannot be compared at all — doing so here would have made a 1.9× improvement look like a regression. The thresholds asserted inside the [Fact] are deliberately loose enough to pass the contaminated in-suite run, since that is how CI executes them.

Adding a new benchmark

  1. Add a [Fact] under Facts/ in DiGi.Geometry.xUnit, following the repo's test conventions (partial class Facts, XML <summary>, explicit types, warm-up-then-Stopwatch).
  2. Expose the sweep size(s) as a single const/static readonly field at the top of the class so the benchmark can be scaled up for a stress run and back down for fast everyday runs.
  3. Warm up (small input) before timing to exclude JIT cost.
  4. Assert cross-implementation agreement (result values / counts) so timing covers equivalent work.
  5. Run in Release for representative numbers, and capture the current machine spec.
  6. Record the machine spec, fully namespace-qualified method names, the result table(s), and the analysis on this page.

See also: the DiGi.ComputeSharp Benchmark page (GPU vs. CPU), which follows the same standard.

Clone this wiki locally