Winding Numbers on Discrete Surfaces

ACM Transactions on Graphics (SIGGRAPH 2023)

In the plane, the

*winding number*is the number of times a curve wraps around a given point. Winding numbers are a basic component of geometric algorithms such as point-in-polygon tests, and their generalization to data with noise or topological errors has proven valuable for geometry processing tasks ranging from surface reconstruction to mesh booleans. However, standard definitions do not immediately apply on surfaces, where not all curves bound regions. We develop a meaningful generalization, starting with the well-known relationship between winding numbers and harmonic functions. By processing the derivatives of such functions, we can robustly filter out components of the input that do not bound any region. Ultimately, our algorithm yields (i) a closed, completed version of the input curves, (ii) integer labels for regions that are meaningfully bounded by these curves, and (iii) the complementary curves that do not bound any region. The main computational cost is solving a standard Poisson equation, or for surfaces with nontrivial topology, a sparse linear program. We also introduce special basis functions to represent singularities that naturally occur at endpoints of open curves. Paper

Acknowledgements

This work was funded by an NSF CAREER Award (IIS 1943123), NSF Award IIS 2212290, a Packard Fellowship and gifts from Facebook Reality Labs, and Google, Inc.

Bibtex

@article{Feng:2023:WND,
author = {Feng, Nicole and Gillespie, Mark and Crane, Keenan},
title = {Winding Numbers on Discrete Surfaces},
journal = {ACM Trans. Graph.},
volume = {XX},
number = {X},
year = {2023},
publisher = {ACM},
address = {New York, NY, USA},
}

Supplement: Perspectives on Winding Numbers