“Fast linking numbers for topology verification of loopy structures” by Qu and James

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.

1. Zin Arai. 2013. A rigorous numerical algorithm for computing the linking number of links. Nonlinear Theory and Its Applications, IEICE 4, 1 (2013), 104–110.Google Scholar
2. David Baraff and Andrew Witkin. 1998. Large Steps in Cloth Simulation. In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’98). Association for Computing Machinery, New York, NY, USA, 43–54. Google ScholarDigital Library
3. David Baraff, Andrew Witkin, and Michael Kass. 2003. Untangling Cloth. ACM Trans. Graph. 22, 3 (July 2003), 862–870. Google ScholarDigital Library
4. Jernej Barbič and Doug L. James. 2010. Subspace Self-Collision Culling. ACM Trans. on Graphics (SIGGRAPH 2010) 29, 4 (2010), 81:1–81:9.Google Scholar
5. Gavin Barill, Neil G. Dickson, Ryan Schmidt, David I. W. Levin, and Alec Jacobson. 2018. Fast winding numbers for soups and clouds. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–12.Google ScholarDigital Library
6. Josh Barnes and Piet Hut. 1986. A hierarchical O(N log N) force-calculation algorithm. Nature 324, 6096 (1986), 446–449.Google ScholarCross Ref
7. Julien Basch. 1999. Kinetic Data Structures. Ph.D. Dissertation. Stanford University, Stanford, CA, USA. Advisor(s) Guibas, Leonidas J. AAI9943622.Google Scholar
8. Mitchell Berger. 2009. Topological Quantities: Calculating Winding, Writhing, Linking, and Higher Order Invariants. Lecture Notes in Mathematics 1973 (03 2009). Google ScholarCross Ref
9. Miklós Bergou, Basile Audoly, Etienne Vouga, Max Wardetzky, and Eitan Grinspun. 2010. Discrete Viscous Threads. ACM Trans. Graph. 29, 4, Article 116 (July 2010), 10 pages. Google ScholarDigital Library
10. Miklós Bergou, Max Wardetzky, Stephen Robinson, Basile Audoly, and Eitan Grinspun. 2008. Discrete Elastic Rods. ACM Transactions on Graphics (SIGGRAPH) 27, 3 (aug 2008), 63:1–63:12.Google ScholarDigital Library
11. Gilbert Louis Bernstein and Chris Wojtan. 2013. Putting Holes in Holey Geometry: Topology Change for Arbitrary Surfaces. ACM Trans. Graph. 32, 4, Article 34 (July 2013), 12 pages. Google ScholarDigital Library
12. Enrico Bertolazzi, Riccardo Ghiloni, and Ruben Specogna. 2019. Efficient computation of linking number with certification. arXiv preprint arXiv:1912.13121 (2019).Google Scholar
13. Robert Bridson, Ronald Fedkiw, and John Anderson. 2002. Robust Treatment of Collisions, Contact and Friction for Cloth Animation. In Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques (San Antonio, Texas) (SIGGRAPH ’02). Association for Computing Machinery, New York, NY, USA, 594–603. Google ScholarDigital Library
14. Tyson Brochu, Essex Edwards, and Robert Bridson. 2012. Efficient Geometrically Exact Continuous Collision Detection. ACM Trans. Graph. 31, 4, Article 96 (July 2012), 7 pages. Google ScholarDigital Library
15. Hervé Brönnimann, Andreas Fabri, Geert-Jan Giezeman, Susan Hert, Michael Hoffmann, Lutz Kettner, Sylvain Pion, and Stefan Schirra. 2021. 2D and 3D Linear Geometry Kernel. In CGAL User and Reference Manual (5.2.1 ed.). CGAL Editorial Board. https://doc.cgal.org/5.2.1/Manual/packages.html#PkgKernel23Google Scholar
16. Martin Burtscher and Keshav Pingali. 2011. An efficient CUDA implementation of the tree-based Barnes Hut N-body algorithm. In GPU Computing Gems Emerald Edition, Wen mei W. Hwu (Ed.). Morgan Kaufmann, Boston, 75 — 92. Google ScholarCross Ref
17. Cris Cecka and Simon Layton. 2015. FMMTL: FMM Template Library A Generalized Framework for Kernel Matrices. In Numerical Mathematics and Advanced Applications – ENUMATH 2013, Assyr Abdulle, Simone Deparis, Daniel Kressner, Fabio Nobile, and Marco Picasso (Eds.). Springer International Publishing, Cham, 611–620.Google Scholar
18. Johnny T. Chang, Jingyi Jin, and Yizhou Yu. 2002. A practical model for hair mutual interactions. In Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation. 73–80.Google ScholarDigital Library
19. Hongwei Cheng, Leslie Greengard, and Vladimir Rokhlin. 1999. A Fast Adaptive Multipole Algorithm in Three Dimensions. J. Comput. Phys. 155, 2 (1999), 468 — 498. Google ScholarDigital Library
20. Nicolas Clauvelin, Wilma K. Olson, and Irwin Tobias. 2012. Characterization of the Geometry and Topology of DNA Pictured As a Discrete Collection of Atoms. Journal of Chemical Theory and Computation 8, 3 (2012), 1092–1107. Google ScholarCross Ref
21. Paul De Casteljau. 1959. Outillages méthodes calcul. Andr e Citro en Automobiles SA, Paris (1959).Google Scholar
22. Tamal K. Dey, Fengtao Fan, and Yusu Wang. 2013. An efficient computation of handle and tunnel loops via Reeb graphs. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1–10. Source code here: https://web.cse.ohio-state.edu/~dey.8/handle/ReebHanTun-download/reebhantun.html.Google ScholarDigital Library
23. Tamal K. Dey, Kuiyu Li, and Jian Sun. 2009. Computing handle and tunnel loops with knot linking. Computer-Aided Design 41, 10 (2009), 730 — 738. Google ScholarDigital Library
24. Herbert Edelsbrunner and Afra Zomorodian. 2001. Computing linking numbers of a filtration. In Algorithms in Bioinformatics, Olivier Gascuel and Bernard M. E. Moret (Eds.). Springer, Springer, Berlin, Heidelberg, 112–127.Google Scholar
25. Francisco R. Feito and Juan Carlos Torres. 1997. Inclusion test for general polyhedra. Computers & Graphics 21, 1 (1997), 23 — 30. Google ScholarCross Ref
26. F. Brock Fuller. 1978. Decomposition of the linking number of a closed ribbon: a problem from molecular biology. Proceedings of the National Academy of Sciences 75, 8 (1978), 3557–3561.Google ScholarCross Ref
27. Leslie Greengard and Vladimir Rokhlin. 1987. A fast algorithm for particle simulations. J. Comput. Phys. 73, 2 (1987), 325 — 348. Google ScholarDigital Library
28. Chen Greif, Shiwen He, and Paul Liu. 2015. SYM-ILDL: Incomplete LDLT Factorization of Symmetric Indefinite and Skew-Symmetric Matrices. CoRR abs/1505.07589 (2015). arXiv:1505.07589 http://arxiv.org/abs/1505.07589Google Scholar
29. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.Google Scholar
30. Leonidas Guibas, An Nguyen, Daniel Russel, and Li Zhang. 2002. Collision Detection for Deforming Necklaces. In Proceedings of the Eighteenth Annual Symposium on Computational Geometry (Barcelona, Spain) (SCG ’02). Association for Computing Machinery, New York, NY, USA, 33–42. Google ScholarDigital Library
31. Runbo Guo, Jenny Lin, Vidya Narayanan, and James McCann. 2020. Representing Crochet with Stitch Meshes. In Symposium on Computational Fabrication (Virtual Event, USA) (SCF ’20). Association for Computing Machinery, New York, NY, USA, Article 4, 8 pages. Google ScholarDigital Library
32. David Harmon, Daniele Panozzo, Olga Sorkine, and Denis Zorin. 2011. Interference-Aware Geometric Modeling. ACM Trans. Graph. 30, 6 (Dec. 2011), 1–10. Google ScholarDigital Library
33. Edmond S.L. Ho and Taku Komura. 2009. Character Motion Synthesis by Topology Coordinates. Computer Graphics Forum 28, 2 (2009), 299–308. Google ScholarCross Ref
34. Edmond S.L. Ho, Taku Komura, Subramanian Ramamoorthy, and Sethu Vijayakumar. 2010. Controlling humanoid robots in topology coordinates. In 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems. 178–182. Google ScholarCross Ref
35. Libo Huang, Torsten Hädrich, and Dominik L. Michels. 2019. On the Accurate Large-Scale Simulation of Ferrofluids. ACM Trans. Graph. 38, 4, Article 93 (July 2019), 15 pages. Google ScholarDigital Library
36. Geoffrey Irving, Joseph M. Teran, and Ronald Fedkiw. 2004. Invertible Finite Elements for Robust Simulation of Large Deformation. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Grenoble, France) (SCA ’04). Eurographics Association, Goslar, DEU, 131–140. Google ScholarDigital Library
37. Alec Jacobson, Ladislav Kavan, and Olga Sorkine-Hornung. 2013. Robust Inside-Outside Segmentation Using Generalized Winding Numbers. ACM Trans. Graph. 32, 4, Article 33 (July 2013), 12 pages. Google ScholarDigital Library
38. Jonathan M. Kaldor, Doug L. James, and Steve Marschner. 2008. Simulating Knitted Cloth at the Yarn Level. In ACM SIGGRAPH 2008 Papers (Los Angeles, California) (SIGGRAPH ’08). Association for Computing Machinery, New York, NY, USA, Article 65, 9 pages. Google ScholarDigital Library
39. Jonathan M. Kaldor, Doug L. James, and Steve Marschner. 2010. Efficient Yarn-Based Cloth with Adaptive Contact Linearization. In ACM SIGGRAPH 2010 Papers (Los Angeles, California) (SIGGRAPH ’10). Association for Computing Machinery, New York, NY, USA, Article 105, 10 pages. Google ScholarDigital Library
40. Danny M. Kaufman, Rasmus Tamstorf, Breannan Smith, Jean-Marie Aubry, and Eitan Grinspun. 2014. Adaptive Nonlinearity for Collisions in Complex Rod Assemblies. ACM Trans. Graph. 33, 4, Article 123 (July 2014), 12 pages. Google ScholarDigital Library
41. Theodore Kim. 2020. A Finite Element Formulation of Baraff-Witkin Cloth. Computer Graphics Forum 39, 8 (2020), 171–179. Google ScholarDigital Library
42. Theodore Kim, Fernando De Goes, and Hayley Iben. 2019. Anisotropic Elasticity for Inversion-Safety and Element Rehabilitation. ACM Trans. Graph. 38, 4, Article 69 (July 2019), 15 pages. Google ScholarDigital Library
43. Konstantin Klenin and Jörg Langowski. 2000. Computation of writhe in modeling of supercoiled DNA. Biopolymers: Original Research on Biomolecules 54, 5 (2000), 307–317. <307::AID-BIP20>3.0.CO;2-Y Google ScholarCross Ref
44. Brad A. Krajina, Audrey Zhu, Sarah C. Heilshorn, and Andrew J. Spakowitz. 2018. Active DNA Olympic Hydrogels Driven by Topoisomerase Activity. Phys. Rev. Lett. 121 (Oct 2018), 148001. Issue 14. Google ScholarCross Ref
45. Jonathan Leaf, Rundong Wu, Eston Schweickart, Doug L. James, and Steve Marschner. 2018. Interactive Design of Periodic Yarn-Level Cloth Patterns. ACM Trans. Graph. 37, 6, Article 202 (Dec. 2018), 15 pages. Google ScholarDigital Library
46. Hammad Mazhar, Tim Osswald, and Dan Negrut. 2016. On the use of computational multi-body dynamics analysis in SLS-based 3D printing. Additive Manufacturing 12 (2016), 291–295. Special Issue on Modeling & Simulation for Additive Manufacturing. Google ScholarCross Ref
47. Charles A. Micchelli and Hartmut Prautzsch. 1989. Uniform refinement of curves. Linear Algebra Appl. 114–115 (1989), 841–870. Google ScholarCross Ref
48. John Milnor. 1954. Link groups. Annals of Mathematics (1954), 177–195.Google Scholar
49. Edward L. F. Moore. 2006. Computational topology of spline curves for geometric and molecular approximations. Ph.D. Dissertation. University of Connecticut. Advisor(s) Peters, Thomas J.Google Scholar
50. Vidya Narayanan, Lea Albaugh, Jessica Hodgins, Stelian Coros, and James Mccann. 2018. Automatic Machine Knitting of 3D Meshes. ACM Trans. Graph. 37, 3, Article 35 (Aug. 2018), 15 pages. Google ScholarDigital Library
51. Vidya Narayanan, Kui Wu, Cem Yuksel, and James McCann. 2019. Visual Knitting Machine Programming. ACM Trans. Graph. 38, 4, Article 63 (July 2019), 13 pages. Google ScholarDigital Library
52. Florian T. Pokorny, Johannes A. Stork, and Danica Kragic. 2013. Grasping objects with holes: A topological approach. In 2013 IEEE International Conference on Robotics and Automation. 1100–1107. Google ScholarCross Ref
53. Dale Rolfsen. 1976. Knots and links. Publish or Perish, Berkeley, CA.Google Scholar
54. David Salesin, Jorge Stolfi, and Leonidas Guibas. 1989. Epsilon Geometry: Building Robust Algorithms from Imprecise Computations. In Proceedings of the Fifth Annual Symposium on Computational Geometry (Saarbruchen, West Germany) (SCG ’89). Association for Computing Machinery, New York, NY, USA, 208–217. Google ScholarDigital Library
55. Andrew Selle, Michael Lentine, and Ronald Fedkiw. 2008. A Mass Spring Model for Hair Simulation. ACM Trans. Graph. 27, 3 (Aug. 2008), 1–11. Google ScholarDigital Library
56. Jonathan Richard Shewchuk. 1997. Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates. Discrete & Computational Geometry 18, 3 (Oct. 1997), 305–363.Google Scholar
57. Zachary Sierzega, Jeff Wereszczynski, and Chris Prior. 2020. WASP: A software package for correctly characterizing the topological development of ribbon structures. bioRxiv (2020). Google ScholarCross Ref
58. Jonas Spillmann and Matthias Teschner. 2008. An Adaptive Contact Model for the Robust Simulation of Knots. Computer Graphics Forum 27, 2 (2008), 497–506. Google ScholarCross Ref
59. Alessandro Tasora, Radu Serban, Hammad Mazhar, Arman Pazouki, Daniel Melanz, Jonathan Fleischmann, Michael Taylor, Hiroyuki Sugiyama, and Dan Negrut. 2016. Chrono: An Open Source Multi-physics Dynamics Engine. In High Performance Computing in Science and Engineering, Tomáš Kozubek, Radim Blaheta, Jakub Šístek, Miroslav Rozložník, and Martin Čermák (Eds.). Springer International Publishing, Cham, 19–49.Google Scholar
60. Adriaan Van Oosterom and Jan Strackee. 1983. The Solid Angle of a Plane Triangle. IEEE Transactions on Biomedical Engineering BME-30, 2 (1983), 125–126. Google ScholarCross Ref
61. Pascal Volino and Nadia Magnenat-Thalmann. 2006. Resolving Surface Collisions through Intersection Contour Minimization. In ACM SIGGRAPH 2006 Papers (Boston, Massachusetts) (SIGGRAPH ’06). Association for Computing Machinery, New York, NY, USA, 1154–1159. Google ScholarDigital Library
62. Monan Wang and Jiaqi Cao. 2021. A review of collision detection for deformable objects. Computer Animation and Virtual Worlds (2021).Google Scholar
63. Kui Wu, Xifeng Gao, Zachary Ferguson, Daniele Panozzo, and Cem Yuksel. 2018. Stitch Meshing. ACM Trans. Graph. 37, 4, Article 130 (July 2018), 14 pages. Google ScholarDigital Library
64. Kui Wu, Hannah Swan, and Cem Yuksel. 2019. Knittable Stitch Meshes. ACM Trans. Graph. 38, 1, Article 10 (Jan. 2019), 13 pages. Google ScholarDigital Library
65. Kui Wu and Cem Yuksel. 2017. Real-time Fiber-level Cloth Rendering. In ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D 2017) (San Francisco, CA). ACM, New York, NY, USA, 8. Google ScholarDigital Library
66. Rundong Wu, Joy Xiaoji Zhang, Jonathan Leaf, Xinru Hua, Ante Qu, Claire Harvey, Emily Holtzman, Joy Ko, Brooks Hagan, Doug James, François Guimbretière, and Steve Marschner. 2020. Weavecraft: An Interactive Design and Simulation Tool for 3D Weaving. ACM Trans. Graph. 39, 6, Article 210 (Nov. 2020), 16 pages. Google ScholarDigital Library
67. Christopher Yu, Henrik Schumacher, and Keenan Crane. 2020. Repulsive Curves. ACM Trans. Graph. (2020). Conditionally accepted preprint.Google Scholar
68. Cem Yuksel, Jonathan M. Kaldor, Doug L. James, and Steve Marschner. 2012. Stitch Meshes for Modeling Knitted Clothing with Yarn-Level Detail. ACM Trans. Graph. 31, 4, Article 37 (July 2012), 12 pages. Google ScholarDigital Library
69. Dmitry Zarubin, Vladimir Ivan, Marc Toussaint, Taku Komura, and Sethu Vijayakumar. 2012. Hierarchical Motion Planning in Topological Representations. In Proceedings of Robotics: Science and Systems. Sydney, Australia. Google ScholarCross Ref
70. Liangjun Zhang, Young J. Kim, Gokul Varadhan, and Dinesh Manocha. 2007. Generalized penetration depth computation. Computer-Aided Design 39, 8 (2007), 625 — 638. Solid and Physical Modeling 2006. Google ScholarDigital Library
71. Changxi Zheng and Doug L. James. 2012. Energy-Based Self-Collision Culling for Arbitrary Mesh Deformations. ACM Trans. Graph. 31, 4, Article 98 (July 2012), 12 pages. Google ScholarDigital Library