Fast and Exact Winding Numbers for Triangle Meshes
ACM Transactions on Graphics · 03.07.2026 · 45 (4) · 1-8
DOI: 10.1145/3811339 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Graphics, online erschienen am 03.07.2026. Verfasst von Peiyuan Xie und 2 weiteren Autor:innen. Die Arbeit nennt 36 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: European Research Council.
Abstract (Originalsprache)
We revisit the computation of 3D generalized winding numbers, a useful measure for inside-outside classification on triangle meshes with gaps, self-intersections, and open boundaries. At the core of our new method is an analytical reduction of the surface integral that defines the winding number, resulting in a single ray-mesh intersection test and an elementary sum over boundary edges per evaluation. This construction is orders of magnitude more efficient than the state of the art in practice, which we show in an extensive performance benchmark. Conveniently, the method also reduces to the best-available asymptotic complexity in the worst case, and it introduces no approximations apart from floating-point errors. Our algorithm is conceptually simple to understand, straightforward to implement and debug, and it works reliably even on extremely noisy and corrupt input geometry.
Förderung
- European Research Council
Zitieren
APA
Xie, P., Hafner, C., & Wojtan, C. (2026). Fast and Exact Winding Numbers for Triangle Meshes. ACM Transactions on Graphics, 45(4), 1-8. https://doi.org/10.1145/3811339
Vancouver
Xie P, Hafner C, Wojtan C. Fast and Exact Winding Numbers for Triangle Meshes. ACM Transactions on Graphics. 2026;45(4):1-8. doi:10.1145/3811339
BibTeX
@article{Xie2026,
author = {Xie, Peiyuan and Hafner, Christian and Wojtan, Chris},
title = {Fast and Exact Winding Numbers for Triangle Meshes},
journal = {ACM Transactions on Graphics},
year = {2026},
volume = {45},
number = {4},
pages = {1--8},
doi = {10.1145/3811339}
}
EUVIMED