Inside-outside determination is a basic building block for higher-level geometry processing operations. Generalized winding numbers provide a robust answer for triangle meshes, regardless of defects such as self-intersections, holes or degeneracies. In this paper, we further generalize the winding number to point clouds. Previous methods for evaluating the winding number are slow for completely disconnected surfaces, such as triangle soups or–in the extreme case– point clouds. We propose a tree-based algorithm to reduce the asymptotic complexity of generalized winding number computation, while closely approximating the exact value. Armed with a fast evaluation, we demonstrate the winding number in a variety of new applications: voxelization, signing distances, generating 3D printer paths, defect-tolerant mesh booleans and point set surfaces.
igl::fast_winding_number@article{Barill:FW:2018,
title = {Fast Winding Numbers for Soups and Clouds},
author = {Gavin Barill and Nia Dickson and Ryan Schmidt and David I.W. Levin and Alec Jacobson},
year = {2018},
journal = {ACM Transactions on Graphics},
}
This work is funded in part by NSERC Discovery Grants (RGPIN2017–05235 & RGPAS–2017–507938 & RGPIN–2017–05524, RGPAS–2017–507909), Connaught Funds NR2016–17, the Canada Research Chairs Program, and a gift by Adobe Systems Inc. We thank Micheal Tao for the derivations found in Appendix, as well as Sarah Kushner for help with figure creation.