Fast Winding Numbers for Soups and Clouds

GRAND Seminar Thursday, April 26, 12 Noon, Room: 4201

Alec Jacobson
Assistant Professor
Department of Computer Science
University of Toronto

Host:

Yotam Gingold

Abstract:

"Well, are you in or are you out?" -- Jodi Kramer, Dazed and Confused, 1993
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.

Short Bio:

Alec Jacobson is an Assistant Professor and Canada Research Chair in the Department of Computer Science at University of Toronto. Before that he was a post-doctoral researcher at Columbia University working with Prof. Eitan Grinspun. He received a PhD in Computer Science from ETH Zurich advised by Prof. Olga Sorkine-Hornung, and an MA and BA in Computer Science and Mathematics from the Courant Institute of Mathematical Sciences, New York University. His thesis on real-time deformation techniques for 2D and 3D shapes was awarded the ETH Medal and the Eurographics Best PhD award. Leveraging ideas from differential geometry and finite-element analysis, his work in geometry processing improves exposure of geometric quantities, while his novel user interfaces reduce human effort and increase exploration. He has published several papers in the proceedings of SIGGRAPH. He leads development of the widely used geometry processing library, libigl, winner of the 2015 SGP software award. In 2017, he received the Eurographics Young Researcher Award.