pith. sign in

arxiv: 2605.19200 · v1 · pith:VRXVIG7Znew · submitted 2026-05-18 · 💻 cs.GR · cs.CG

Spatially Accelerated Winding Numbers for Curved Geometry

Jacob Spainhour , Brad Whitlock , Kenneth Weiss This is my paper

Pith reviewed 2026-05-20 06:49 UTC · model grok-4.3

classification 💻 cs.GR cs.CG
keywords generalized winding numberNURBS curvestrimmed NURBS patchesbounding volume hierarchycontainment queriesspatial accelerationcurved geometrycomputer graphics
0
0 comments X

The pith

A bounding volume hierarchy with precomputed moments accelerates generalized winding number queries on NURBS curves and patches while preserving boundary accuracy.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The generalized winding number offers a robust scalar field for determining containment in complex curved shapes that may overlap or have gaps. Direct evaluation of this field on large sets of NURBS curves or trimmed patches is computationally expensive. The work organizes the input geometry inside a bounding volume hierarchy that holds precomputed moment data, allowing distant clusters to be approximated quickly while nearby primitives receive exact evaluation. An adaptive subdivision step applied to the NURBS during preprocessing improves the quality of the spatial partitions without altering the containment results. If successful, this yields sub-linear query times for containment checks on curved models that previously required linear work.

Core claim

We extend support for fast GWN evaluation over arbitrary collections of NURBS curves in 2D and trimmed NURBS patches in 3D via a Bounding Volume Hierarchy that stores efficiently precomputed moment data in the hierarchy nodes. When querying the hierarchy, approximations for far clusters are used alongside direct evaluation for nearby NURBS primitives, achieving sub-linear complexity while preserving the geometric features in the vicinity of the query point. Central to our performance improvements is an adaptive subdivision strategy for NURBS primitives during a preprocessing phase, creating better spatial partitions while retaining the same accuracy for containment decisions as a direct eval

What carries the argument

Bounding Volume Hierarchy that stores precomputed moment data for NURBS primitives, queried with approximations for distant clusters and exact evaluation for nearby ones.

If this is right

  • Containment queries on large collections of NURBS curves and patches run with sub-linear complexity.
  • Accuracy for points near the geometry matches that of direct evaluation.
  • The approach handles both non-watertight 2D curve collections and 3D trimmed patches.
  • Preprocessing creates spatial partitions that support the fast approximations without changing final containment results.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same hierarchy structure could support other point queries that benefit from moment-based approximations on parametric geometry.
  • Real-time applications involving repeated containment tests on curved CAD models become more practical.
  • The method might combine with existing mesh-based accelerators when mixed discrete and parametric inputs are present.

Load-bearing premise

The adaptive subdivision strategy for NURBS primitives during preprocessing creates better spatial partitions while retaining the same accuracy for containment decisions as direct evaluation.

What would settle it

Compare the approximated GWN value produced by the hierarchy query against the exact direct GWN value at a point very close to a curved NURBS boundary; any systematic difference would show the approximation introduces error.

Figures

Figures reproduced from arXiv: 2605.19200 by Brad Whitlock, Jacob Spainhour, Kenneth Weiss.

Figure 1
Figure 1. Figure 1: The Generalized Winding Number (GWN) facilitates containment queries for non-watertight shapes by treating each piece of the boundary repre [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: We show the 0 th order and 2 nd order Taylor expansions utilized by our agglomeration strategy to represent the GWN field of a single cluster of 2D curves and 3D NURBS trimmed surfaces, with each approximation centered at the centroid of the components shapes. We view the approximation near the boundaries (top), and the error in their far field (bottom). On these error plots, we also show the radius at whi… view at source ↗
Figure 3
Figure 3. Figure 3: We use numerical quadrature to efficiently and accurately evaluate [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: We demonstrate how subdividing parametric NURBS input influ [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: On our representative samples of 2D SVG shapes (left) and 3D CAD shapes (right), we compare the distribution of evaluation times across subdivision [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: On the same representative set of 3D CAD shapes from Figure 5, we consider runtime performance as a function of various metrics. Each point [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: We show the results of our agglomeration strategy across the order [PITH_FULL_IMAGE:figures/full_fig_p008_7.png] view at source ↗
Figure 9
Figure 9. Figure 9: On a 2D slice of the 3D shape in Figure 3, we consider the influence [PITH_FULL_IMAGE:figures/full_fig_p009_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Using a 2D shape composed of 38 Bézier curves, we compare the absolute error of our agglomeration strategy with [PITH_FULL_IMAGE:figures/full_fig_p010_10.png] view at source ↗
Figure 12
Figure 12. Figure 12: We evaluate the approximate GWN field computed via our ag [PITH_FULL_IMAGE:figures/full_fig_p011_12.png] view at source ↗
Figure 11
Figure 11. Figure 11: We consider the utility of the rounded GWN scalar field as a proxy [PITH_FULL_IMAGE:figures/full_fig_p011_11.png] view at source ↗
Figure 13
Figure 13. Figure 13: Across our representative 2D and 3D datasets, we evaluate the GWN on a grid of [PITH_FULL_IMAGE:figures/full_fig_p012_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: We compare our proposed algorithm to the GWN of a cloud of [PITH_FULL_IMAGE:figures/full_fig_p012_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: We compare our proposed algorithm to triangulations of a 3D shape, whose GWN is computed using the agglomeration method of Barill et al [PITH_FULL_IMAGE:figures/full_fig_p013_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Performance of our proposed algorithm in 2D (left) and 3D (right) using Taylor expansions of order 2 and [PITH_FULL_IMAGE:figures/full_fig_p014_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: Average per-query runtime (serial) for 2D direct GWN algorithms [PITH_FULL_IMAGE:figures/full_fig_p015_17.png] view at source ↗
read the original abstract

The generalized winding number (GWN) is a scalar field that supports robust containment queries on curved geometry, including non-watertight, overlapping, and nested boundary representations. While queries can be easily parallelized over samples, direct evaluation on parametric curves and surfaces remains costly for large and complex models. Fast, state-of-the-art GWN approaches leverage a spatial index to approximate the GWN, typically coupled with a Taylor expansion which approximates the GWN contribution for far clusters of geometric primitives. However, such methods operate only on discrete inputs such as triangle meshes and point clouds, and would introduce containment errors near boundaries if applied to curved input. We extend support for fast GWN evaluation over arbitrary collections of NURBS curves in 2D and trimmed NURBS patches in 3D via a Bounding Volume Hierarchy that stores efficiently precomputed moment data in the hierarchy nodes. When querying the hierarchy, approximations for far clusters are used alongside direct evaluation for nearby NURBS primitives, achieving sub-linear complexity while preserving the geometric features in the vicinity of the query point. Central to our performance improvements is an adaptive subdivision strategy for NURBS primitives during a preprocessing phase, creating better spatial partitions while retaining the same accuracy for containment decisions as a direct evaluation. We demonstrate the performance and accuracy of our approach across a large collection of 2D and 3D datasets.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper claims to extend fast generalized winding number (GWN) evaluation from discrete meshes to arbitrary collections of NURBS curves in 2D and trimmed NURBS patches in 3D. It constructs a Bounding Volume Hierarchy storing precomputed moment data, applies Taylor expansions for far-field cluster approximations during queries, and uses direct evaluation for nearby primitives. An adaptive subdivision step in preprocessing is presented as the key to tighter spatial partitions that retain the same containment accuracy as direct parametric evaluation, yielding sub-linear query complexity while preserving local geometric features.

Significance. If the central claim holds, the work would meaningfully extend prior BVH-accelerated GWN methods (limited to triangles and point clouds) to curved parametric inputs common in CAD and graphics. The hybrid far/near strategy and moment precomputation are concrete strengths that could enable practical speed-ups for large non-watertight or nested models without sacrificing robustness near boundaries.

major comments (1)
  1. [Abstract and §4] Abstract (paragraph on central performance improvements) and §4 (Preprocessing): the claim that adaptive subdivision of NURBS primitives 'retains the same accuracy for containment decisions as a direct evaluation' is load-bearing for the sub-linear query guarantee and boundary preservation. No invariance proof, error bound on geometric deviation, or explicit before/after comparison of GWN integrals or sign is supplied; if the curvature or knot-insertion threshold permits local deviation, far-field Taylor approximations could be applied too early or the winding-number sign could flip within machine epsilon of a trimmed edge.
minor comments (2)
  1. Notation for the moment tensors stored in BVH nodes is introduced without an explicit recurrence or storage-cost table; a small table comparing memory per primitive before and after subdivision would clarify the preprocessing overhead.
  2. Figure captions for the 3D trimmed-patch examples do not indicate the query-point distances at which the hybrid switch occurs; adding this would help readers assess the near-field region size.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed and constructive review of our manuscript. The primary concern raised pertains to the justification of accuracy preservation under adaptive NURBS subdivision. We address this point directly below and outline the revisions we will make.

read point-by-point responses

  1. Referee: [Abstract and §4] Abstract (paragraph on central performance improvements) and §4 (Preprocessing): the claim that adaptive subdivision of NURBS primitives 'retains the same accuracy for containment decisions as a direct evaluation' is load-bearing for the sub-linear query guarantee and boundary preservation. No invariance proof, error bound on geometric deviation, or explicit before/after comparison of GWN integrals or sign is supplied; if the curvature or knot-insertion threshold permits local deviation, far-field Taylor approximations could be applied too early or the winding-number sign could flip within machine epsilon of a trimmed edge.

    Authors: We thank the referee for identifying this critical aspect. Our adaptive subdivision employs exact knot insertion on the NURBS primitives, an operation that mathematically preserves the original geometry with no approximation or deviation introduced. Consequently, direct parametric evaluation of the subdivided pieces produces containment decisions that are identical to those obtained from the unsplit NURBS, as the underlying curve or surface representation remains unchanged. This exact equivalence ensures that near-field queries retain full accuracy and that far-field Taylor approximations are applied only where the original method would permit them. We acknowledge that the original manuscript would be strengthened by an explicit invariance argument and supporting material. In the revised version we will expand §4 with a short proof sketch based on the properties of B-spline knot insertion, an error analysis confirming zero geometric deviation, and a numerical before/after comparison of GWN values and signs on representative trimmed patches near boundaries. revision: yes

Circularity Check

0 steps flagged

No circularity in algorithmic extension for GWN on NURBS

full rationale

The paper describes a constructive method that builds a BVH over NURBS curves and patches, precomputes moment data in nodes, and applies adaptive subdivision during preprocessing to enable sub-linear queries with direct evaluation near the query point. All load-bearing steps are explicit algorithmic choices (hierarchy construction, moment storage, far-field Taylor approximation for distant clusters) whose correctness and accuracy claims are presented as direct consequences of the design rather than reductions to fitted parameters, self-definitions, or unverified self-citations. The assertion that subdivision retains containment equivalence is an engineering claim internal to the algorithm and does not create a circular derivation chain; the overall contribution remains self-contained against external benchmarks such as direct NURBS evaluation.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

The approach rests on the standard definition of generalized winding numbers extending to parametric curves and the validity of moment-based far-field approximations when clusters are sufficiently distant.

free parameters (1)
  • adaptive subdivision threshold
    Criterion used during preprocessing to decide when to split NURBS primitives for better spatial partitioning.
axioms (2)
  • domain assumption Generalized winding number definition applies unchanged to NURBS curves and trimmed patches
    Invoked when claiming that direct evaluation on nearby primitives yields the same containment decision as the original GWN.
  • domain assumption Moment summation provides a valid far-field approximation for clusters of parametric primitives
    Used to justify replacing direct evaluation with precomputed data for distant hierarchy nodes.

pith-pipeline@v0.9.0 · 5775 in / 1363 out tokens · 57409 ms · 2026-05-20T06:49:01.274529+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    2023), 115742

    Direct immersogeometric fluid flow and heat transfer analysis of objects represented by point clouds.Computer Methods in Applied Mechanics and Engineering404 (Feb. 2023), 115742. doi:10.1016/j.cma.2022.115742 A. Bao, E. Shen, and J. Wang

    work page doi:10.1016/j.cma.2022.115742 2023

  2. [2]

    arXiv:2510.25159 [cs.GR] https://arxiv.org/abs/2510.25159 G

    Fast and robust point containment queries on trimmed surface. arXiv:2510.25159 [cs.GR] https://arxiv.org/abs/2510.25159 G. Barill, N. Dickson, R. Schmidt, D. I. W. Levin, and A. Jacobson

    work page arXiv

  3. [3]

    doi:10.1145/3197517.3201337 J

    Fast winding numbers for soups and clouds.ACM Transactions on Graphics37, 4, Article 43 (July 2018), 12 pages. doi:10.1145/3197517.3201337 A. Capps, R. Carson, B. Corbett, N. Elliott, J. Essman, B. Gunney, B. Han, C. Harrison, R. Hornung, M. Larsen, A. Moody, E. Pauli, R. Settgast, J. Spainhour, L. Taylor, K. Weiss, C. White, B. Whitlock, M. Yang, and G. ...

    work page doi:10.1145/3197517.3201337 2018

  4. [4]

    doi:10.1016/j.cad.2020.102944 D

    Spectral mesh-free quadrature for planar regions bounded by rational parametric curves.Computer-Aided Design130 (2020). doi:10.1016/j.cad.2020.102944 D. Gunderman, K. Weiss, and J. A. Evans

    work page doi:10.1016/j.cad.2020.102944 2020

  5. [5]

    Gunderman, K

    High-accuracy mesh-free quadrature for trimmed parametric surfaces and volumes.Computer-Aided Design141 (2021), 103093. doi:10.1016/j.cad.2021.103093 Y. Hu, T. Schneider, X. Gao, Q. Zhou, A. Jacobson, D. Zorin, and D. Panozzo

    work page doi:10.1016/j.cad.2021.103093 2021

  6. [6]

    Multi-view relighting using a geometry-aware network , year =

    TriWild: Robust triangulation with curve constraints.ACM Trans. Graph.38, 4, Article 52 (July 2019), 15 pages. doi:10.1145/3306346.3323011 A. Jacobson, L. Kavan, and O. Sorkine

    work page doi:10.1145/3306346.3323011 2019

  7. [7]

    doi:10.1145/2461912.2461916 A

    Robust inside-outside segmentation using generalized winding numbers.ACM Transactions on Graphics32, 4 (2013), 1–12. doi:10.1145/2461912.2461916 T. Karras

    work page doi:10.1145/2461912.2461916 2013

  8. [8]

    Graph.44, 4, Article 75 (July 2025), 9 pages

    Closed-form generalized winding numbers of rational parametric curves for robust containment queries.ACM Trans. Graph.44, 4, Article 75 (July 2025), 9 pages. doi:10.1145/3730886 C. Martens and M. Bessmeltsev

    work page doi:10.1145/3730886 2025

  9. [9]

    One-shot method for computing generalized winding numbers.Computer Graphics Forum44 (2025). Issue

    work page 2025

  10. [10]

    doi:10.1111/cgf.70194 Open Cascade

    work page doi:10.1111/cgf.70194

  11. [11]

    doi:10.1080/16864360.2016.1223443 R

    Generating point clouds for slicing free-form objects for 3D printing.Computer-Aided Design and Applications 14, 2 (2017), 242–249. doi:10.1080/16864360.2016.1223443 R. Sawhney and K. Crane

    work page doi:10.1080/16864360.2016.1223443 2017

  12. [12]

    Graphics39, 4 (2020)

    Monte Carlo geometry processing: A grid-free approach to PDE-based methods on volumetric domains.ACM Trans. Graphics39, 4 (2020). T. W. Sederberg, G. T. Finnigan, X. Li, H. Lin, and H. Ipson

    work page 2020

  13. [13]

    InACM SIGGRAPH 2008 Papers(Los Angeles, California)(SIGGRAPH ’08)

    Watertight trimmed NURBS. InACM SIGGRAPH 2008 Papers(Los Angeles, California)(SIGGRAPH ’08). Association for Computing Machinery, New York, NY, USA, Article 79, 8 pages. doi:10.1145/1399504.1360678 J. Spainhour, D. Gunderman, and K. Weiss

    work page doi:10.1145/1399504.1360678 2008

  14. [14]

    doi:10.1145/3658228 P

    Robust containment queries over collections of rational parametric curves via generalized winding numbers.ACM Transactions on Graphics43, 4, Article 38 (July 2024), 14 pages. doi:10.1145/3658228 J. Spainhour and K. Weiss

    work page doi:10.1145/3658228 2024

  15. [15]

    doi:10.1145/3797957 K

    Robust containment queries over collections of trimmed NURBS surfaces via generalized winding numbers.ACM Transactions on Graphics 45, 3, Article 26 (April 2026), 21 pages. doi:10.1145/3797957 K. Weiss, G. Zagaris, R. Rieben, and A. Cook

    work page doi:10.1145/3797957 2026

  16. [16]

    doi:10.1111/cgf.14362

    Delaunay meshing and repairing of NURBS models.CG Forum40, 5 (2021), 125–142. doi:10.1111/cgf.14362

    work page doi:10.1111/cgf.14362 2021