Teaser Image

Abstract

It is increasingly common to model, simulate, and process complex materials based on loopy structures, such as in yarn-level cloth garments, which possess topological constraints between inter-looping curves. While the input model may satisfy specific topological linkages between pairs of closed loops, subsequent processing may violate those topological conditions. In this paper, we explore a family of methods for efficiently computing and verifying linking numbers between closed curves, and apply these to applications in geometry processing, animation, and simulation, so as to verify that topological invariants are preserved during and after processing of the input models. Our method has three stages: (1) we identify potentially interacting loop-loop pairs, then (2) carefully discretize each loop's spline curves into line segments so as to enable (3) efficient linking number evaluation using accelerated kernels based on either counting projected segment-segment crossings, or by evaluating the Gauss linking integral using direct or fast summation methods (Barnes–Hut or fast multipole methods). We evaluate CPU and GPU implementations of these methods on a suite of test problems, including yarn-level cloth and chainmail, that involve significant processing: physics-based relaxation and animation, user-modeled deformations, curve compression and reparameterization. We show that topology errors can be efficiently identified to enable more robust processing of loopy structures.

Paper

Video

Gallery

Sweater Analysis
Alien Sweater Drop
3x3 Chevron Stitch Pattern
Yarn Model Analysis (Fig. 9)
Sweater Drop Simulation (Fig. 12)
Chevron 3x3 Pattern Relaxation (Fig. 15)
 
Embedded Deformation of Knitted Glove
Double-Helix Ribbon
Rubber Band Simulation
Embedded Glove Deformation (Fig. 11)
Double-Helix Ribbon (Fig. 6)
Rubber Band Drop Simulation (Fig. 16)
 
Knitted Tube Twist Test
Packed Kusari Chainmail
Sheep Sweater Curve Reparameterization
Knitted Tube Twist Test (Fig. 13)
Packed Kusari Chainmail (Fig. 1)
Curve Reparameterization (Fig. 10)

Supplemental Implementation Details

Citation

bibtex
Ante Qu and Doug L. James. 2021. Fast Linking Numbers for Topology Verification of Loopy Structures. ACM Trans. Graph. 40, 4, Article 106 (August 2021), 19 pages.

Acknowledgements

We thank the anonymous reviewers for the constructive and detailed feedback. We thank Jonathan Leaf, Xinru Hua, Paul Liu, Gilbert Bernstein, and Madeleine Yip for helpful discussions, and Steve Marschner, Purvi Goel, and Jiayi Eris Zhang for proofreading the final manuscript. We also thank Cem Yuksel for the stitch mesh source code. Ante Qu's research was supported in part by the National Science Foundation (DGE-1656518). We acknowledge SideFX for donated Houdini licenses and Google Cloud Platform for donated compute resources. Mitsuba Renderer was also used to produce renders. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.