Visual
Computing

Fast and Exact Winding Numbers for Triangle Meshes

Fast and Exact Winding Numbers (Teaser Image)

Authors

Affiliations

Publication

ACM Transactions on Graphics (Siggraph 2026)

Abstract

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.

Resources

Citation

@article{FastExactWindingNumbersXie26,
  author = {Xie, Peiyuan and Hafner, Christian and Wojtan, Chris},
  title = {Fast and Exact Winding Numbers for Triangle Meshes},
  year = {2026},
  volume = {45},
  number = {4},
  journal = {ACM Trans. Graph.},
  month = jul,
  articleno = {41},
  numpages = {8}
}

Acknowledgements

We thank Sadashige Ishida and Ryusuke Sugimoto for their insightful discussions and proofreading and other members of the ISTA Visual Computing Group for their general feedback. Special thanks to David Palmer, Yi-Lu Chen, Carmen Farr and Ladislav Trnka for their help with the fastforward video. This project was funded in part by the European Research Council (ERC Consolidator Grant 101045083 CoDiNA).

EU ERC