More Web Proxy on the site http://driver.im/

research-article

Spectral quadrangulation with orientation and alignment control

Authors:

Hujun BaoAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 27, Issue 5

Article No.: 147, Pages 1 - 9

https://doi.org/10.1145/1409060.1409100

Published: 01 December 2008 Publication History

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.

Supplementary Material

JPG File (a147-huang-mp4_hi.jpg)

Download
13.86 KB

MOV File (a147-huang-mp4_hi.mov)

Download
465.67 MB

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]

Alliez, P., Cohen-Steiner, D., Devillers, O., Lévy, B., and Desbrun, M. 2003. Anisotropic polygonal remeshing. ACM Trans. Graph. 22, 3, 485--493.

Digital Library

[3]

Alliez, P., Ucelli, G., Gotsman, C., and Attene, M. 2005. Recent advances in remeshing of surfaces.

[4]

Boier-Martin, I., Rushmeier, H., and Jin, J. 2004. Parameterization of triangle meshes over quadrilateral domains. In SGP '04: Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, ACM, 193--203.

[5]

Botsch, M., and Pauly, M. 2007. Course 23: Geometric modeling based on polygonal meshes. In SIGGRAPH courses.

[6]

Davis, T. A. 2004. A column pre-ordering strategy for the unsymmetric-pattern multifrontal method. ACM Trans. Math. Softw. 30, 2, 165--195.

Digital Library

[7]

Dong, S., Kircher, S., and Garland, M. 2005. Harmonic functions for quadrilateral remeshing of arbitrary manifolds. Comput. Aided Geom. Des. 22, 5, 392--423.

Digital Library

[8]

Dong, S., Bremer, P.-T., Garland, M., Pascucci, V., and Hart, J. C. 2006. Spectral surface quadrangulation. ACM Trans. Graph. 25, 3, 1057--1066.

Digital Library

[9]

Edelsbrunner, H., Letscher, D., and Zomorodian, A. 2002. Topological persistence and simplification. Discrete Computer Geometry 28, 511--533.

Digital Library

[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]

Fisher, M., Schröder, P., Desbrun, M., and Hoppe, H. 2007. Design of tangent vector fields. In SIGGRAPH '07: ACM SIGGRAPH 2007 papers, ACM, 56.

[12]

Gu, X., and Yau, S.-T. 2003. Global conformal surface parameterization. In SGP '03: Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, Eurographics Association, 127--137.

Digital Library

[13]

Igarashi, T., Moscovich, T., and Hughes, J. F. 2005. As-rigid-as-possible shape manipulation. ACM Trans. Graph. 24, 3, 1134--1141.

Digital Library

[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]

Khodakovsky, A., Litke, N., and Schröder, P. 2003. Globally smooth parameterizations with low distortion. In SIGGRAPH '03: ACM SIGGRAPH 2003 Papers, ACM, 350--357.

[16]

Li, W.-C., Ray, N., and Lévy, B. 2006. Automatic and interactive mesh to t-spline conversion. In SGP '06: Proceedings of the fourth Eurographics symposium on Geometry processing, Eurographics Association, 191--200.

Digital Library

[17]

Marinov, M., and Kobbelt, L. 2004. Direct anisotropic quaddominant remeshing. In PG '04: Proceedings of the Computer Graphics and Applications, 12th Pacific Conference on (PG'04), IEEE Computer Society, 207--216.

Digital Library

[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]

Ray, N., Li, W. C., Lévy, B., Sheffer, A., and Alliez, P. 2006. Periodic global parameterization. ACM Trans. Graph. 25, 4, 1460--1485.

Digital Library

[22]

Shi, L., and Yu, Y. 2004. Inviscid and incompressible fluid simulation on triangle meshes: Research articles. Comput. Animat. Virtual Worlds 15, 3--4, 173--181.

[23]

Strang, G. 1999. The discrete cosine transform. SIAM Review 41, 1, 135--147.

Digital Library

[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.

Digital Library

[25]

Tong, Y., Alliez, P., Cohen-Steiner, D., and Desbrun, M. 2006. Designing quadrangulations with discrete harmonic forms. In SGP '06: Proceedings of the fourth Eurographics symposium on Geometry processing, Eurographics Association, 201--210.

Digital Library

[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]

Yoshizawa, S., Belyaev, A., and Seidel, H.-P. 2005. Fast and robust detection of crest lines on meshes. In SPM '05: Proceedings of the 2005 ACM symposium on Solid and physical modeling, ACM, 227--232.

Cited By

Shepherd KHiemstra RGu XHughes T(2024)Extraction of surface quad layouts from quad layout immersions: application to an isogeometric model of car crashEngineering with Computers10.1007/s00366-024-02007-w40:6(3683-3716)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s00366-024-02007-w
Bommes DZimmer HKobbelt L(2023)Mixed-Integer QuadrangulationSeminal Graphics Papers: Pushing the Boundaries, Volume 210.1145/3596711.3596740(249-258)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1145/3596711.3596740
Shepherd KGu XHiemstra RHughes T(2022)Quadrilateral layout generation and optimization using equivalence classes of integral curves: theory and application to surfaces with boundariesJournal of Mechanics10.1093/jom/ufac00238(128-155)Online publication date: 13-Apr-2022
https://doi.org/10.1093/jom/ufac002
Show More Cited By

Index Terms

Spectral quadrangulation with orientation and alignment control
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Quadrangulation through morse-parameterization hybridization

We introduce an approach to quadrilateral meshing of arbitrary triangulated surfaces that combines the theoretical guarantees of Morse-based approaches with the practical advantages of parameterization methods. We first construct, through an eigensolver ...
Spectral surface quadrangulation

Resampling raw surface meshes is one of the most fundamental operations used by nearly all digital geometry processing systems. The vast majority of this work has focused on triangular remeshing, yet quadrilateral meshes are preferred for many surface ...
Spectral quadrangulation with orientation and alignment control
SIGGRAPH Asia '08: ACM SIGGRAPH Asia 2008 papers

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. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 27, Issue 5

December 2008

552 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1409060

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2008

Published in TOG Volume 27, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

87
Total Citations
View Citations
753
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Shepherd KHiemstra RGu XHughes T(2024)Extraction of surface quad layouts from quad layout immersions: application to an isogeometric model of car crashEngineering with Computers10.1007/s00366-024-02007-w40:6(3683-3716)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s00366-024-02007-w
Bommes DZimmer HKobbelt L(2023)Mixed-Integer QuadrangulationSeminal Graphics Papers: Pushing the Boundaries, Volume 210.1145/3596711.3596740(249-258)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1145/3596711.3596740
Shepherd KGu XHiemstra RHughes T(2022)Quadrilateral layout generation and optimization using equivalence classes of integral curves: theory and application to surfaces with boundariesJournal of Mechanics10.1093/jom/ufac00238(128-155)Online publication date: 13-Apr-2022
https://doi.org/10.1093/jom/ufac002
Shepherd KGu XHughes T(2022)Feature-aware reconstruction of trimmed splines using Ricci flow with metric optimizationComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2022.115555402(115555)Online publication date: Dec-2022
https://doi.org/10.1016/j.cma.2022.115555
Akram MXu KChen G(2022)Structure simplification of planar quadrilateral meshesComputers & Graphics10.1016/j.cag.2022.10.001109(1-14)Online publication date: Dec-2022
https://doi.org/10.1016/j.cag.2022.10.001
Sun LArmstrong CRobinson TPapadimitrakis D(2021)Quadrilateral multiblock decomposition via auxiliary subdivisionJournal of Computational Design and Engineering10.1093/jcde/qwab0208:3(871-893)Online publication date: 13-May-2021
https://doi.org/10.1093/jcde/qwab020
Novello TPaixão JTomei CLewiner T(2021)Discrete line fields on surfacesTopology and its Applications10.1016/j.topol.2021.107603290(107603)Online publication date: Mar-2021
https://doi.org/10.1016/j.topol.2021.107603
Zheng XZhu YChen WLei NLuo ZGu X(2021)Quadrilateral mesh generation III : Optimizing singularity configuration based on Abel–Jacobi theoryComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2021.114146387(114146)Online publication date: Dec-2021
https://doi.org/10.1016/j.cma.2021.114146
Xu CLin HHu HHe Y(2021)Fast calculation of Laplace-Beltrami eigenproblems via subdivision linear subspaceComputers and Graphics10.1016/j.cag.2021.04.01997:C(236-247)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1016/j.cag.2021.04.019
Zhang CChai SLiu LFu X(2021)Quad Meshing with Coarse Layouts for Planar DomainsComputer-Aided Design10.1016/j.cad.2021.103084140:COnline publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1016/j.cad.2021.103084
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents