“Repulsive surfaces” by Yu, Brakensiek, Schumacher and Crane
Conference:
Type(s):
Title:
- Repulsive surfaces
Session/Category Title: Curves and Surfaces
Presenter(s)/Author(s):
Abstract:
Functionals that penalize bending or stretching of a surface play a key role in geometric and scientific computing, but to date have ignored a very basic requirement: in many situations, surfaces must not pass through themselves or each other. This paper develops a numerical framework for optimization of surface geometry while avoiding (self-)collision. The starting point is the tangent-point energy, which effectively pushes apart pairs of points that are close in space but distant along the surface. We develop a discretization of this energy for triangle meshes, and introduce a novel acceleration scheme based on a fractional Sobolev inner product. In contrast to similar schemes developed for curves, we avoid the complexity of building a multiresolution mesh hierarchy by decomposing our preconditioner into two ordinary Poisson equations, plus forward application of a fractional differential operator. We further accelerate this scheme via hierarchical approximation, and describe how to incorporate a variety of constraints (on area, volume, etc.). Finally, we explore how this machinery might be applied to problems in mathematical visualization, geometric modeling, and geometry processing.
References:
1. J. Barnes and P. Hut. 1986. A hierarchical O(N log N) force-calculation algorithm. Nature 324, 6096 (1986), 446–449.
2. Adam Bednorz and Witold Bednorz. 2019. Analytic sphere eversion using ruled surfaces. Differential Geometry and its Applications 64 (2019), 59–79.
3. S. Blatt. 2013. The Energy Spaces of the Tangent Point Energies. Journal of Topology and Analysis 5, 3 (2013), 261–270.
4. Simon Blatt and Philipp Reiter. 2015. Regularity theory for tangent-point energies: the non-degenerate sub-critical case. Adv. Calc. Var. 8, 2 (2015), 93–116.
5. Alexander I. Bobenko and Peter Schröder. 2005. Discrete Willmore Flow. In Proceedings of the Third Eurographics Symposium on Geometry Processing (Vienna, Austria) (SGP ’05). Eurographics Association, Goslar, DEU, 101–es.
6. Mario Botsch and Leif Kobbelt. 2004. A Remeshing Approach to Multiresolution Modeling. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (Nice, France) (SGP ’04). Association for Computing Machinery, New York, NY, USA, 185–192.
7. Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. 2004. Convex optimization. Cambridge university press.
8. 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. 594–603.
9. G. Buck and J. Orloff. 1995. A simple energy function for knots. Top. Appl. 61, 3 (1995).
10. Dorin Bucur and Giuseppe Butazzo. 2006. VARIATIONAL METHODS IN SHAPE OPTIMIZATION PROBLEMS.
11. Long Chen and Michael Holst. 2011. Efficient mesh optimization schemes based on Optimal Delaunay Triangulations. Computer Methods in Applied Mechanics and Engineering 200, 9 (2011), 967 — 984.
12. Albert Chern, Felix Knöppel, Ulrich Pinkall, and Peter Schröder. 2018. Shape from metric. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–17.
13. Sebastian Claici, Mikhail Bessmeltsev, Scott Schaefer, and Justin Solomon. 2017. Isometry-aware preconditioning for mesh parameterization. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 37–47.
14. Ulrich Clarenz, Udo Diewald, Gerhard Dziuk, Martin Rumpf, and R Rusu. 2004. A finite element method for surface restoration with smooth boundary conditions. Computer Aided Geometric Design 21, 5 (2004), 427–445.
15. Keenan Crane, Fernando de Goes, Mathieu Desbrun, and Peter Schröder. 2013a. Digital Geometry Processing with Discrete Exterior Calculus. In ACM SIGGRAPH 2013 courses (Anaheim, California) (SIGGRAPH ’13). ACM, New York, NY, USA, 126.
16. Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2013b. Robust Fairing via Conformal Curvature Flow. ACM Trans. Graph. 32, 4 (2013).
17. Mathieu Desbrun, Mark Meyer, Peter Schröder, and Alan H Barr. 1999. Implicit fairing of irregular meshes using diffusion and curvature flow. In Proceedings of the 26th annual conference on Computer graphics and interactive techniques. 317–324.
18. Marc Droske and Martin Rumpf. 2004. A level set formulation for Willmore flow. Interfaces and free boundaries 6, 3 (2004), 361–378.
19. Marion Dunyach, David Vanderhaeghe, Loïc Barthe, and Mario Botsch. 2013. Adaptive remeshing for real-time mesh deformation. In Eurographics 2013. The Eurographics Association.
20. Gerhard Dziuk. 2008. Computational parametric Willmore flow. Numer. Math. 111, 1 (2008), 55–80.
21. Ilya Eckstein, Jean-Philippe Pons, Yiying Tong, C.-C. Jay Kuo, and Mathieu Desbrun. 2007. Generalized Surface Flows for Mesh Processing. In Proceedings of the Fifth Eurographics Symposium on Geometry Processing (Barcelona, Spain) (SGP ’07). Eurographics Association, 183–192.
22. Matthew Elsey and Selim Esedoγlu. 2009. Analogue of the total variation denoising model in the context of geometry processing. Multiscale Modeling & Simulation 7, 4 (2009), 1549–1573.
23. Yu Fang, Minchen Li, Chenfanfu Jiang, and Danny M. Kaufman. 2021. Guaranteed Globally Injective 3D Deformation Processing. ACM Trans. Graph. (SIGGRAPH) 40, 4, Article 75 (2021).
24. George Francis, John M Sullivan, Rob B Kusner, Ken A Brakke, Chris Hartman, and Glenn Chappell. 1997. The minimax sphere eversion. In Visualization and mathematics. Springer, 3–20.
25. George K Francis and GK Francis. 1987. A topological picturebook. Vol. 2. Springer.
26. M. Freedman, Z. He, and Z. Wang. 1994. Mobius Energy of Knots and Unknots. Annals of Mathematics 139, 1 (1994), 1–50.
27. Mark Gillespie, Boris Springborn, and Keenan Crane. 2021. Discrete Conformal Equivalence of Polyhedral Surfaces. ACM Trans. Graph. 40, 4 (2021).
28. E. Giusti. 1973. Minimal Surfaces with Obstacles. Springer Berlin Heidelberg, Berlin, Heidelberg, 121–153.
29. Eitan Grinspun, Anil N Hirani, Mathieu Desbrun, and Peter Schröder. 2003. Discrete shells. In Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation. Citeseer, 62–67.
30. W. Hackbusch. 2015. Hierarchical matrices: algorithms and analysis. Vol. 49. Springer.
31. Rana Hanocka, Gal Metzer, Raja Giryes, and Daniel Cohen-Or. 2020. Point2Mesh: A Self-Prior for Deformable Meshes. ACM Trans. Graph. 39, 4, Article 126 (July 2020), 12 pages.
32. David Harmon, Daniele Panozzo, Olga Sorkine, and Denis Zorin. 2011. Interference-aware geometric modeling. ACM Transactions on Graphics (TOG) 30, 6 (2011), 1–10.
33. David Harmon, Etienne Vouga, Breannan Smith, Rasmus Tamstorf, and Eitan Grinspun. 2009. Asynchronous contact mechanics. In ACM SIGGRAPH 2009 papers. 1–12.
34. Behrend Heeren, Martin Rumpf, Max Wardetzky, and Benedikt Wirth. 2012. Time-discrete geodesics in the space of shells. In Computer Graphics Forum, Vol. 31. Wiley Online Library, 1755–1764.
35. Atsushi Ishii. 2008. Moves and invariants for knotted handlebodies. Algebraic & Geometric Topology 8, 3 (2008), 1403–1418.
36. Atsushi Ishii, Kengo Kishimoto, Hiromasa Moriuchi, and Masaaki Suzuki. 2012. A table of genus two handlebody-knots up to six crossings. Journal of Knot Theory and Its Ramifications 21, 04 (2012), 1250035.
37. Zhongshi Jiang, Scott Schaefer, and Daniele Panozzo. 2017. Simplicial complex augmentation framework for bijective maps. ACM Transactions on Graphics 36, 6 (2017).
38. Pushkar Joshi and Carlo Séquin. 2007. Energy minimizers for curvature-based surface functionals. Computer-Aided Design and Applications 4, 5 (2007), 607–617.
39. Michael Kazhdan, Jake Solomon, and Mirela Ben-Chen. 2012. Can mean-curvature flow be modified to be non-singular?. In Computer Graphics Forum, Vol. 31. Wiley Online Library, 1745–1754.
40. Leif P. Kobbelt, Jens Vorsatz, and Ulf Labsik. 1999. A Shrink Wrapping Approach to Remeshing Polygonal Surfaces. Computer Graphics Forum 18, 3 (1999), 119–130.
41. Sławomir Kolasiński, Paweł Strzelecki, and Heiko von der Mosel. 2015. Compactness and isotopy finiteness for submanifolds with uniformly bounded geometric curvature energies. arXiv:arXiv:1504.04538
42. Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated Quadratic Proxy for Geometric Optimization. ACM Trans. Graph. 35, 4, Article 134 (July 2016), 11 pages.
43. Robert B Kusner and John M Sullivan. 1998. Möbius-invariant knot energies. Ideal knots 19 (1998), 315–352.
44. Mateusz Kwaśnicki. 2017. Ten equivalent definitions of the fractional laplace operator. Fractional Calculus and Applied Analysis 20, 1 (Jan 2017).
45. Marc Lackenby. 2016. Elementary knot theory. arXiv preprint arXiv:1604.03778 (2016).
46. Silvio Levy and William P Thurston. 1995. Making waves: A guide to the ideas behind Outside In. Geometry Center.
47. Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M. Kaufman. 2020. Incremental Potential Contact: Intersection- and Inversion-free Large Deformation Dynamics. ACM Trans. Graph. (SIGGRAPH) 39, 4, Article 49 (2020).
48. Fernando C Marques and André Neves. 2014. Min-max theory and the Willmore conjecture. Annals of mathematics (2014), 683–782.
49. Tobias Martin, Pushkar Joshi, Miklós Bergou, and Nathan Carr. 2013. Efficient Nonlinear Optimization via Multi-scale Gradient Filtering. In Computer Graphics Forum, Vol. 32. Wiley Online Library, 89–100.
50. Matthew Moore and Jane Wilhelms. 1988. Collision detection and response for computer animation. In Proceedings of the 15th annual conference on Computer graphics and interactive techniques. 289–298.
51. Henry P Moreton and Carlo H Séquin. 1992. Functional optimization for fair surface design. ACM SIGGRAPH Computer Graphics 26, 2 (1992), 167–176.
52. Matthias Müller, Nuttapong Chentanez, Tae-Yong Kim, and Miles Macklin. 2015. Air meshes for robust collision handling. ACM Transactions on Graphics (TOG) 34, 4 (2015), 1–9.
53. Jun O’Hara. 1991. Energy of a knot. Topology 30, 2 (1991), 241–247.
54. Stanley Osher and Ronald Fedkiw. 2006. Level set methods and dynamic implicit surfaces. Vol. 153. Springer Science & Business Media.
55. U. Pinkall and K. Polthier. 1993. Computing discrete minimal surfaces and their conjugates. Experimental mathematics 2, 1 (1993), 15–36.
56. Robert J Renka and JW Neuberger. 1995. Minimal surfaces and Sobolev gradients. SIAM Journal on Scientific Computing 16, 6 (1995), 1412–1427.
57. Leonardo Sacht, Etienne Vouga, and Alec Jacobson. 2015. Nested cages. ACM Transactions on Graphics (TOG) 34, 6 (2015), 1–14.
58. Robert Glenn Scharein. 1998. Interactive topological drawing. Ph.D. Dissertation. University of British Columbia.
59. Patrick Schmidt, Marcel Campen, Janis Born, and Leif Kobbelt. 2020. Inter-surface maps via constant-curvature metrics. ACM Transactions on Graphics (TOG) 39, 4 (2020), 119–1.
60. Henrik Schumacher. 2017. On H2-gradient Flows for the Willmore Energy. arXiv preprint arXiv:1703.06469 (2017).
61. Lin Shi, Yizhou Yu, Nathan Bell, and Wei-Wen Feng. 2006. A Fast Multigrid Algorithm for Mesh Deformation. ACM Trans. Graph. 25, 3 (2006), 1108–1117.
62. Jason Smith and Scott Schaefer. 2015. Bijective parameterization with free boundaries. ACM Transactions on Graphics (TOG) 34, 4 (2015), 1–9.
63. Yousuf Soliman, Albert Chern, Olga Diamanti, Felix Knöppel, Ulrich Pinkall, and Peter Schröder. 2021. Constrained Willmore Surfaces. ACM Trans. Graph. 40, 4 (2021).
64. Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible surface modeling. In Symposium on Geometry processing, Vol. 4. 109–116.
65. Paweł Strzelecki and Heiko von der Mosel. 2013. Tangent-point repulsive potentials for a class of non-smooth m-dimensional sets in Rn. Part I: Smoothing and self-avoidance effects. J. Geom. Anal. 23, 3 (2013), 1085–1139.
66. Paweł Strzelecki and Heiko von der Mosel. 2018. Geometric curvature energies: facts, trends, and open problems. In New directions in geometric and applied knot theory. De Gruyter, Berlin, 8–35.
67. David Wells. 1997. The Penguin dictionary of curious and interesting numbers. Penguin.
68. Peter Wriggers and Giorgio Zavarise. 2004. Computational contact mechanics. Encyclopedia of computational mechanics (2004).
69. Zi Ye, Olga Diamanti, Chengcheng Tang, Leonidas Guibas, and Tim Hoffmann. 2018. A unified discrete framework for intrinsic and extrinsic Dirac operators for geometry processing. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 93–106.
70. Chris Yu, Henrik Schumacher, and Keenan Crane. 2021. Repulsive Curves. ACM Trans. Graph. 40, 2, Article 10 (May 2021), 21 pages.
71. Fuzhen Zhang. 2005. The Schur Complement and its Applications. Numerical Methods and Algorithms, Vol. 4. Springer, New York.
72. Yufeng Zhu, Robert Bridson, and Danny M. Kaufman. 2018. Blended Cured Quasi-Newton for Distortion Optimization. ACM Trans. Graph. 37, 4, Article 40 (2018), 14 pages.
