Spectral quadrangulation with orientation and alignment control

ABSTRACT

This paper presents a new quadrangulation algorithm, extending the spectral surface quadrangulation approach where the coarse quadrangular structure is derived from the Morse-Smale complex of an eigenfunction of the Laplacian operator on the input mesh. In contrast to the original scheme, we provide flexible explicit controls of the shape, size, orientation and feature alignment of the quadrangular faces. We achieve this by proper selection of the optimal eigenvalue (shape), by adaption of the area term in the Laplacian operator (size), and by adding special constraints to the Laplace eigenproblem (orientation and alignment). By solving a generalized eigen-problem we can generate a scalar field on the mesh whose Morse-Smale complex is of high quality and satisfies all the user requirements. The final quadrilateral mesh is generated from the Morse-Smale complex by computing a globally smooth parametrization. Here we additionally introduce edge constraints to preserve user specified feature lines accurately.

REFERENCES

• 1: Alford, R. M., Kelly, K. R., and Boore, D. M. 1974. Accuracy of finite-difference modeling of the acoustic wave equation. Geophysics 39, 6 (December), 834--842.
• 2: Pierre Alliez , David Cohen-Steiner , Olivier Devillers , Bruno Lévy , Mathieu Desbrun, Anisotropic polygonal remeshing, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 3: Alliez, P., Ucelli, G., Gotsman, C., and Attene, M. 2005. Recent advances in remeshing of surfaces.
• 4: Ioana Boier-Martin , Holly Rushmeier , Jingyi Jin, Parameterization of triangle meshes over quadrilateral domains, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057459]
• 5: Mario Botsch , Mark Pauly , Christian Rossl , Stephan Bischoff , Leif Kobbelt, Geometric modeling based on triangle meshes, ACM SIGGRAPH 2006 Courses, July 30-August 03, 2006, Boston, Massachusetts [doi>10.1145/1185657.1185839]
• 6: Timothy A. Davis, A column pre-ordering strategy for the unsymmetric-pattern multifrontal method, ACM Transactions on Mathematical Software (TOMS), v.30 n.2, p.165-195, June 2004 [doi>10.1145/992200.992205]
• 7: S. Dong , S. Kircher , M. Garland, Harmonic functions for quadrilateral remeshing of arbitrary manifolds, Computer Aided Geometric Design, v.22 n.5, p.392-423, July 2005 [doi>10.1016/j.cagd.2005.04.004]
• 8: Shen Dong , Peer-Timo Bremer , Michael Garland , Valerio Pascucci , John C. Hart, Spectral surface quadrangulation, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 9: Edelsbrunner, H., Letscher, D., and Zomorodian, A. 2002. Topological persistence and simplification. Discrete Computer Geometry 28, 511--533.
• 10: Edelsbrunner, H., Harer, J., and Zomorodian, A. 2003. Hierarchical morse-smale complexes for piecewise linear 2-manifolds. Discrete and Computational Geometry 30, 1, 87--107.
• 11: Matthew Fisher , Peter Schröder , Mathieu Desbrun , Hugues Hoppe, Design of tangent vector fields, ACM SIGGRAPH 2007 papers, August 05-09, 2007, San Diego, California
• 12: Xianfeng Gu , Shing-Tung Yau, Global conformal surface parameterization, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 13: Takeo Igarashi , Tomer Moscovich , John F. Hughes, As-rigid-as-possible shape manipulation, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 14: Kälberer, F., Nieser, M., and Polthier, K. 2007. Quadcover -- surface parameterization using branched coverings. Computer Graphics Forum 26, 3 (September), 375--384.
• 15: Andrei Khodakovsky , Nathan Litke , Peter Schröder, Globally smooth parameterizations with low distortion, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 16: Wan-Chiu Li , Nicolas Ray , Bruno Lévy, Automatic and interactive mesh to T-spline conversion, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 17: Martin Marinov , Leif Kobbelt, Direct Anisotropic Quad-Dominant Remeshing, Proceedings of the Computer Graphics and Applications, 12th Pacific Conference, p.207-216, October 06-08, 2004
• 18: Marinov, M., and Kobbelt, L. 2006. A robust two-step procedure for quad-dominant remeshing. Computer Graphics Forum 25, 3 (Sept.), 537--546.
• 19: Meyer, M., Desbrun, M., Schröder, P., and Barr, A. H. Discrete differential-geometry operators for triangulated 2-manifolds.
• 20: Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 1, 15--36.
• 21: Nicolas Ray , Wan Chiu Li , Bruno Lévy , Alla Sheffer , Pierre Alliez, Periodic global parameterization, ACM Transactions on Graphics (TOG), v.25 n.4, p.1460-1485, October 2006 [doi>10.1145/1183287.1183297]
• 22: Lin Shi , Yizhou Yu, Inviscid and incompressible fluid simulation on triangle meshes: Research Articles, Computer Animation and Virtual Worlds, v.15 n.3-4, p.173-181, July 2004 [doi>10.1002/cav.v15:3/4]
• 23: Gilbert Strang, The Discrete Cosine Transform, SIAM Review, v.41 n.1, p.135-147, March 1999 [doi>10.1137/S0036144598336745]
• 24: Timo Bremer, P., Edelsbrunner, H., Hamann, B., and Pascucci, V. 2004. A topological hierarchy for functions on triangulated surfaces. IEEE Transactions on Visualization and Computer Graphics 10, 385--396.
• 25: Y. Tong , P. Alliez , D. Cohen-Steiner , M. Desbrun, Designing quadrangulations with discrete harmonic forms, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 26: Vallet, B., and Lévy, B. 2007. Spectral geometry processing with manifold harmonics. Technical Report (April).
• 27: Vallet, B., and Lévy, B. 2008. Spectral geometry processing with manifold harmonics. Computer Graphics Forum 27, 2 (Apr.), 251--260.
• 28: Shin Yoshizawa , Alexander Belyaev , Hans-Peter Seidel, Fast and robust detection of crest lines on meshes, Proceedings of the 2005 ACM symposium on Solid and physical modeling, p.227-232, June 13-15, 2005, Cambridge, Massachusetts [doi>10.1145/1060244.1060270]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)

General Terms:
Design, Performance

Keywords:
Laplacian eigenfunctions, constrained optimization, quadrangular remeshing