“Natural Boundary Conditions for Smoothing in Geometry Processing” by Stein, Grinspun, Wardetzky and Jacobson

  • ©Oded Stein, Eitan Grinspun, Max Wardetzky, and Alec Jacobson

Conference:


Type:


Title:

    Natural Boundary Conditions for Smoothing in Geometry Processing

Session/Category Title: Cutting, Zipping and Folding Surfaces

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    In geometry processing, smoothness energies are commonly used to model scattered data interpolation, dense data denoising, and regularization during shape optimization. The squared Laplacian energy is a popular choice of energy and has a corresponding standard implementation: squaring the discrete Laplacian matrix. For compact domains, when values along the boundary are not known in advance, this construction bakes in low-order boundary conditions. This causes the geometric shape of the boundary to strongly bias the solution. For many applications, this is undesirable. Instead, we propose using the squared Frobenius norm of the Hessian as a smoothness energy. Unlike the squared Laplacian energy, this energy’s natural boundary conditions (those that best minimize the energy) correspond to meaningful high-order boundary conditions. These boundary conditions model free boundaries where the shape of the boundary should not bias the solution locally. Our analysis begins in the smooth setting and concludes with discretizations using finite-differences on 2D grids or mixed finite elements for triangle meshes. We demonstrate the core behavior of the squared Hessian as a smoothness energy for various tasks.

References:


    1. E. D. Andersen and K. D. Andersen. 2000. The mosek interior point optimizer for linear programming: An implementation of the homogeneous algorithm. In High Performance Optimization. Kluwer Academic Publishers, 197–232.
    2. James Andrews, Pushkar Joshi, and Nathan Carr. 2011. A linear variational system for modeling from curves. Comput. Graph. Forum 30, 6, 1850–1861.
    3. Omri Azencot, Maks Ovsjanikov, Frédéric Chazal, and Mirela Ben-Chen. 2015. Discrete derivatives of vector fields on surfaces—an operator approach. ACM Trans. Graph. 34, 3 (May 2015), Article 29, 13 pages. 
    4. Ilya Baran and Jovan Popović. 2007. Automatic rigging and animation of 3D characters. ACM Trans. Graph. 26, 3 (2007), 72:1–72:8. 
    5. Christopher Batty. 2010. Simulating Viscous Incompressible Fluids with Embedded Boundary Finite Difference Methods. Ph.D. Dissertation. University of British Columbia.
    6. M. Belkin and P. Niyogi. 2004. Semi-supervised learning on Riemannian manifolds. Mach. Learn. 56, 1–3 (2004), 209–239. 
    7. Miklos Bergou, Max Wardetzky, David Harmon, Denis Zorin, and Eitan Grinspun. 2006. A quadratic bending model for inextensible surfaces. In Proceedings of the 4th Eurographics Symposium on Geometry Processing (SGP’06). 227–230. 
    8. Morten Bojsen-Hansen and Chris Wojtan. 2016. Generalized non-reflecting boundaries for fluid re-simulation. ACM Trans. Graph. 35, 4 (2016), Article 96. 
    9. F. L. Bookstein. 1989. Principal warps: Thin-plate splines and the decomposition of deformations. IEEE Trans. Pattern Anal. Mach. Intell. 11, 6, 567–585. 
    10. Mario Botsch and Leif Kobbelt. 2004. A remeshing approach to multiresolution modeling. In Proceedings of the 2nd Eurographics Symposium on Geometry Processing (SGP’04). 189–196. 
    11. M. Botsch and L. Kobbelt. 2005. Real-time shape editing using radial basis functions. Comp. Graph. Forum 24, 3 (2005), 611–621.
    12. D. Braess. 2002. Finite Elements: Theory, Fast Solvers, and Applications in Solid Mechanics (2nd ed.; Vol. 13). Cambridge University Press.
    13. D. Braess, A. S. Pechstein, and J. Schöberl. 2017. An equilibration based a posteriori error estimate for the biharmonic equation and two finite element methods. arXiv:1705.07607.
    14. A. Bronstein, Y. Choukroun, R. Kimmel, and M. Sela. 2016. Consistent discretization and minimization of the l1 norm on manifolds. In Proceedings of the 4th International Conference on 3D Vision (3DV’16).
    15. Chen Cao, Derek Bradley, Kun Zhou, and Thabo Beeler. 2015. Real-time high-fidelity facial performance capture. ACM Trans. Graph. 34, 4, Article 46. 
    16. Chen Cao, Yanlin Weng, Shun Zhou, Yiying Tong, and Kun Zhou. 2014. Facewarehouse: A 3D facial expression database for visual computing. IEEE Trans. Vis. Comput. Graph. 20, 3, 413–425. 
    17. Renjie Chen and Ofir Weber. 2015. Bounded distortion harmonic mappings in the plane. ACM Trans. Graph. 34, 4, Article 73. 
    18. Daniel Cohen-Steiner and Mathieu Desbrun. 2002. Hindsight: LSCM and DNCP Are One and the Same. Technical Report. INRIA-USC.
    19. M. I. Comodi. 1989. The Hellan-Herrmann-Johnson method: Some new error estimates and postprocessing. Math. Comput. 52, 185 (1989), 17–29.
    20. Richard Courant and David Hilbert. 1924. Methoden der Mathematischen Physik I. Knight, Berlin, Germany.
    21. Keenan Crane. 2009. A Cotangent Laplacian for Surfaces with Boundary. Technical Report. INRIA-USC.
    22. Fernando de Goes, Beibei Liu, Max Budninskiy, Yiying Tong, and Mathieu Desbrun. 2014. Discrete 2-tensor fields on triangulations. Comp. Graph. Forum 33, 5, 13–24.
    23. Mathieu Desbrun, Mark Meyer, and Pierre Alliez. 2002. Intrinsic parameterizations of surface meshes. Comp. Graph. Forum 21, 3 (2002), 209–218.
    24. 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 ACM SIGGRAPH Conference. 
    25. Stephan Didas and Joachim Weickert. 2004. Higher Order Variational Methods for Noise Removal in Signals and Images. Diploma Thesis. Saarland University, Saarbrücken.
    26. Stephan Didas, Joachim Weickert, and Bernhard Burgeth. 2009. Properties of higher order nonlinear diffusion filtering. J. Math. Imag. Vis. 35, 3 (2009), 208–226. 
    27. David L. Donoho and Carrie Grimes. 2003. Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data. Proc. Natl. Acad. Sci. U S A 100, 10, 5591–5596.
    28. Lawrence C. Evans. 1998. Partial Differential Equations. American Mathematical Society, Providence, RI.
    29. Carlos A. Felippa. 2017. Advanced Finite Element Methods—Course Notes. Retrieved from https://www.colorado.edu/engineering/CAS/courses.d/AFEM.d/.
    30. Mark Finch, John Snyder, and Hugues Hoppe. 2011. Freeform vector graphics with controlled thin-plate splines. ACM Trans. Graph. 30, 6, Article 166. 
    31. M. Fisher, P. Schröder, M. Desbrun, and H. Hoppe. 2007. Design of tangent vector fields. ACM Trans. Graph. 26, 3 (2007), Article 56. 
    32. Bengt Fornberg. 1988. Generation of finite difference formulas on arbitrarily spaced grids. Math. Comput. 51, 184, 699–706.
    33. A. Garg, E. Grinspun, M. Wardetzky, and D. Zorin. 2007. Cubic shells. Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 91–98. 
    34. I. M. Gelfand and S. V. Fomin. 1963. Calculus of Variations. Prentice Hall.
    35. T. G. Georgiev. 2004. Photoshop healing brush: A tool for seamless cloning. In Proceedings of the ECCV ACV Workshop. 1–8.
    36. Mariano Giaquinta and Stefan Hildebrandt. 1996. Calculus of Variations I. Springer.
    37. Y. I. Gingold, P. Davidson, J. Han, and D. Zorin. 2006. A direct texture placement and editing interface. In Proceedings of the 19th Annual ACM Symposium on User Interface Software and Technology. 23–32. 
    38. A. Godil, A. Axenopoulos, P. Daras, T. Furuya, and R. Ohbuchi. 2009. SHREC 2009: Shape retrieval contest of partial 3D models. In Proceedings of the Eurographics Workshop on 3D Object Retrieval. 
    39. Lei He and Scott Schaefer. 2013. Mesh denoising via L0 minimization. ACM Trans. Graph. 32, 4, Article 64. 
    40. Klaus Hildebrandt, Christian Schulz, Christoph Von Tycowicz, and Konrad Polthier. 2011. Interactive surface modeling using modal analysis. ACM Trans. Graph. 30, 5, 119. 
    41. Ronald Hoppe, Dietrich Braess, and Christopher Linsenmann. 2016. A two-energies principle for the biharmonic equation and an a posteriori error estimator for an interior penalty discontinuous Galerkin approximation. ESAIM. Available at https://www.esaim-m2an.org.
    42. Jin Huang, Xiaohan Shi, Xinguo Liu, Kun Zhou, Li-Yi Wei, Shang-Hua Teng, Hujun Bao, Baining Guo, and Heung-Yeung Shum. 2006. Subspace gradient domain mesh deformation. ACM Trans. Graph. 25, 3 (2006), 1126–1134. 
    43. Alec Jacobson, Ilya Baran, Jovan Popović, and Olga Sorkine. 2011. Bounded biharmonic weights for real-time deformation. ACM Trans. Graph. 30, 4 (2011), Article 78. 
    44. A. Jacobson, Z. Deng, L. Kavan, and J. P. Lewis. 2014. Skinning: Real-time shape deformation. In ACM SIGGRAPH 2014 Courses. 
    45. Alec Jacobson, Daniele Panozzo, Christian Shuller, Olga Diamanti, Qingnan Zhou. Sebastian Koch, Jeremie Dumas, et al. 2017. Libigl: A Simple C++ Geometry Processing Library. Retrieved from http://libigl.github.io/libigl.
    46. Alec Jacobson, Elif Tosun, Olga Sorkine, and Denis Zorin. 2010. Mixed finite elements for variational surface modeling. In Proceedings of the 8th Eurographics Symposium on Geometry Pressing (SGP’10).
    47. Alec Jacobson, Tino Weinkauf, and Olga Sorkine. 2012. Smooth shape-aware functions with controlled extrema. In Proceedings of the 10th Eurographics Symposium on Geometry Processing (SGP’12).
    48. Ben Jones, Nils Thuerey, Tamar Shinar, and Adam W. Bargteil. 2016. Example-based plastic deformation of rigid bodies. ACM Trans. Graph. 35, 4, Article 34. 
    49. Ladislav Kavan, Dan Gerszewski, Adam Bargteil, and Peter-Pike Sloan. 2011. Physics-inspired upsampling for cloth simulation in games. ACM Trans. Graph. 34, 4, Article 93. 
    50. Kwang I. Kim, Florian Steinke, and Matthias Hein. 2009. Semi-supervised regression using Hessian energy with an application to semi-supervised dimensionality reduction. In Advances in Neural Information Processing Systems. 
    51. Bishnu P. Lamichhane. 2011. A stabilized mixed finite element method for the biharmonic equation based on biorthogonal systems. J. Comp. Appl. Math. 235, 17, 5188–5197.
    52. E. Landreneau and S. Schaefer. 2010. Poisson-based weight reduction of animated meshes. Comp. Graph. Forum 29, 6 (2010), 1945–1954.
    53. Stamatios Lefkimmiatis, Aurélien Bourquard, and Michael Unser. 2012. Hessian-based norm regularization for image restoration with biomedical applications. IEEE Trans. Image Process. 21, 3 (2012), 983–995. 
    54. B. Lévy, S. Petitjean, N. Ray, and J. Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. 21, 3 (2002), 362–371. 
    55. W. L. Li. 2000. Free vibrations of beams with general boundary conditions. J. Sound Vib. 237, 4 (2000), 709–725.
    56. Yaron Lipman, Raif Rustamov, and Thomas Funkhouser. 2010. Biharmonic distance. ACM Trans. Graph. 29, 3 (2010), Article 27. 
    57. Beibei Liu, Yiying Tong, Fernando De Goes, and Mathieu Desbrun. 2016. Discrete connection and covariant derivative for vector field analysis and design. ACM Trans. Graph. 35, 3, Article 23. 
    58. X. Y. Liu, C.-H. Lai, and K. A. Pericleous. 2015. A fourth-order partial differential equation denoising model with an adaptive relaxation method. Int. J. Comput. Math. 92, 3 (2015), 608–622. 
    59. Marius Lysaker, Arvid Lundervold, and Xue-Cheng Tai. 2003. Noise removal using fourth-order partial differential equation with applications to medical magnetic resonance images in space and time. IEEE Trans. Image Process. 12, 12, 1579–1590. 
    60. Marius Lysaker and Xue-Cheng Tai. 2006. Iterative image restoration combining total variation minimization and a second-order functional. Int. J. Comput. Vis. 66, 1, 5–18. 
    61. Patrick Mullen, Yiying Tong, Pierre Alliez, and Mathieu Desbrun. 2008. Spectral conformal parameterization. In Proceedings of the 6th Eurographics Symposium on Geometry Processing (SGP’08). 
    62. Ulrich Pinkall and Konrad Polthier. 1993. Computing discrete minimal surfaces and their conjugates. Experiment. Math. 2, 1 (1993), 15–36.
    63. Jean Marc Roth. 2009. Higher Order Anisotropic Smoothing of Images. Ph.D. Dissertation. Saarland University.
    64. Leonid I. Rudin, Stanley Osher, and Emad Fatemi. 1992. Nonlinear total variation based noise removal algorithms. Phys. D: Nonlinear Phenom. 60, 1 (1992), 259–268. 
    65. Raif M. Rustamov. 2011. Multiscale Biharmonic Kernels. Retrieved from https://diglib.eg.org/handle/10.1111/v30i5pp1521-1531.
    66. R. Scholz. 1978. A mixed method for 4th order problems using linear finite elements. RAIRO Anal. Numér. 1, 85–90.
    67. Olga Sorkine, Yaron Lipman, Daniel Cohen-Or, Marc Alexa, Christian Rössl, and Hans-Peter Seidel. 2004. Laplacian surface editing. In Proceedings of the 2nd Eurographics Symposium on Geometry Processing (SGP’04). 179–188. 
    68. Boris Springborn, Peter Schröder, and Ulrich Pinkall. 2008. Conformal equivalence of triangle meshes. ACM Trans. Graph. 27, 3, Article 77. 
    69. Gabriele Steidl. 2006. A note on the dual treatment of higher-order regularization functionals. Computing 76, 1–2 (2006), 135–148. 
    70. Gabriele Steidl, Stephan Didas, and Julia Neumann. 2005. Relations between higher order TV regularization and support vector regression. In Proceedings of the International Conference on Scale-Space Theories in Computer Vision. 515–527. 
    71. Florian Steinke and Matthias Hein. 2009. Non-parametric regression between manifolds. In Advances in Neural Information Processing Systems. 1561–1568. 
    72. Daniel Sýkora, Ladislav Kavan, Martin Čadík, Ondřej Jamriška, Alec Jacobson, Brian Whited, Maryann Simmons, and Olga Sorkine-Hornung. 2014. Ink-and-ray: Bas-relief meshes for adding global illumination effects to hand-drawn characters. ACM Trans. Graph. 33, 2, Article 16. 
    73. Demetri Terzopoulos. 1984. Multilevel reconstruction of visual surfaces: Variational principles and finite-element representations. In Multiresolution Image Processing and Analysis. Springer, 237–310.
    74. Demetri Terzopoulos. 1988. The computation of visible-surface representations. IEEE Trans. Pattern Anal. Mach. Intell. 10, 4 (1988), 417–438. 
    75. E. Tosun, Y. I. Gingold, J. Reisman, and D. Zorin. 2007. Shape optimization using reflection lines. In Proceedings of the 5th Eurographics Symposium on Geometry Processing (SGP’07). 
    76. Yu Wang, Alec Jacobson, Jernej Barbič, and Ladislav Kavan. 2015. Linear subspace design for real-time shape deformation. ACM Trans. Graph. 34, 4, Article 57. 
    77. Yu Wang, Alec Jacobson, Jernej Barbič, and Ladislav Kavan. 2017. Error in “Linear Subspace Design for Real-Time Shape Deformation”. Technical Report.
    78. Ofir Weber, Roi Poranne, and Craig Gotsman. 2012. Biharmonic coordinates. In Comput. Graph. Forum, 31, 2409–2422. 
    79. Tino Weinkauf, Yotam Gingold, and Olga Sorkine. 2010. Topology-based smoothing of 2D scalar fields with -continuity. Comput. Graph. Forum 29, 3 (2010), 1221–1230. 
    80. Li Xu, Cewu Lu, Yi Xu, and Jiaya Jia. 2011. Image smoothing via L0 gradient minimization. ACM Trans. Graph. 30, 6, Article 174. 
    81. Y.-L. You and M. Kaveh. 2000. Fourth-order partial differential equations for noise removal. IEEE Trans. Image Process. 9, 10 (2000), 1723–1730. 
    82. Jing Yuan, Christoph Schnörr, and Gabriele Steidl. 2009. Total-variation based piecewise affine regularization. In Proceedings of the International Conference on Scale Space and Variational Methods in Computer Vision. 552–564. 
    83. Hao Zhang, Oliver van Kaick, and Ramsay Dyer. 2007. Spectral methods for mesh processing and analysis. In Proceedings of the Eurographics State-of-the-Art Report. 1–22
    84. Kun Zhou, Jin Huang, John Snyder, Xinguo Liu, Hujun Bao, Baining Guo, and Heung-Yeung Shum. 2005. Large mesh deformation using the volumetric graph Laplacian. ACM Trans. Graph, 24, 3 (2005), 496–503. 
    85. Kun Zhou, Weiwei Xu, Yiying Tong, and Mathieu Desbrun. 2010. Deformation transfer to multi-component objects. Comp. Graph. Forum 29, 2 (2010), 319–325

ACM Digital Library Publication:


Overview Page: