skip to main content
research-article

Quadrilateral mesh simplification

Published: 01 December 2008 Publication History

Abstract

We introduce a simplification algorithm for meshes composed of quadrilateral elements. It is reminiscent of edge-collapse based methods for triangle meshes, but takes a novel approach to the challenging problem of maintaining the quadrilateral connectivity during level-of-detail creation. The method consists of a set of unit operations applied to the dual of the mesh, each designed to improve mesh structure and maintain topological genus. Geometric shape is maintained by an extension of a quadric error metric to quad meshes. The technique is straightforward to implement and efficient enough to be applied to real-world models. Our technique can handle models with sharp features, and can be used to re-mesh general polygonal, i.e. tri- and quad-dominant, meshes into quadonly meshes.

Supplementary Material

JPG File (a148-daniels-mp4_hi.jpg)
MOV File (a148-daniels-mp4_hi.mov)

References

[1]
Alliez, P., Cohen-Steiner, D., Devillers, O., Lévy, B., and Desbrun, M. 2003. Anisotropic polygonal remeshing. In ACM SIGGRAPH, 485--493.
[2]
Blacker, T., and Stephenson, M. 1991. Paving: A new approach to automated quadrilateral mesh generation. International Journal for Numerical Methods in Engineering (May), 811--847.
[3]
Borden, M., Benzley, S., and Shepherd, J. 2002. Hexahedral sheet extraction. In 11th International Meshing Roundtable, 147--152.
[4]
Bremer, P., Porumbescu, S., Joy, K., and Hamann, B. 2002. Automatic semi-regular mesh construction from adaptive distance fields. Curve and Surface Fitting: Saint-Malo.
[5]
Catmull, E., and Clark, J. 1978. Recursively generated b-spline surfaces on arbitrary topological meshes. Computer Aided Design 10, 6, 350--355.
[6]
Cignoni, P., Montani, C., and Scopigno, R. 1998. A comparison of mesh simplification algorithms. Computers and Graphics 22, 1 (February), 37--54.
[7]
Cohen-Steiner, D., Alliez, P., and Desbrun, M. 2004. Variational shape approximation. In ACM SIGGRAPH, 905--914.
[8]
Dewey, M. 2008. Automated Quadrilateral Coarsening by Ring Collapse. Master's thesis, Bringham Young University.
[9]
Dong, S., Kircher, S., and Garland, M. 2005. Harmonic functions for quadrilateral remeshing of arbitrary manifolds. Computer Aided Geometric Design 22, 5, 392--423.
[10]
Dong, S., Bremer, P.-T., Garland, M., Pascucci, V., and Hart, J. C. 2006. Spectral surface quadrangulation. In ACM SIGGRAPH, 1057--1066.
[11]
Eck, M., and Hoppe, H. 1996. Automatic reconstruction of b-spline surfaces of arbitrary topological type. In ACM SIGGRAPH, 325--334.
[12]
Edelsbrunner, H. 2006. Geometry and Topology for Mesh Generation. Cambridge University Press, New York, NY, USA.
[13]
Garland, M., and Heckbert, P. 1997. Surface simplification using quadric error metrics. In ACM SIGGRAPH, 209--216.
[14]
Guskov, I., Khodakovsky, A., Schröder, P., and Sweldens, W. 2002. Hybrid meshes: multiresolution using regular and irregular refinement. In ACM Symposium on Computational Geometry, 264--272.
[15]
Hoppe, H. 1999. New quadric metric for simplifying meshes with appearance attributes. In IEEE Visualization, 56--66.
[16]
Kalberer, F., Nieser, M., and Polthier, K. 2007. Quadcover: Surface parameterization using branched coverings. Computer Graphics Forum 26, 3, 375--384.
[17]
Kinney, P. 1997. Cleanup: Improving quadrilateral finite element meshes. In 6th International Meshing Roundtable, 437--447.
[18]
Kobbelt, L. 1996. Interpolatory subdivision on open quadrilateral nets with arbitrary topology. Computer Graphics Forum 15, 3, 409--420.
[19]
Krishnamurthy, V., and Levoy, M. 1996. Fitting smooth surface to dense polygon meshes. In ACM SIGGRAPH, 313--324.
[20]
Lai, Y.-K., Kobbelt, L., and Hu, S.-M. 2008. An incremental approach to feature aligned quad dominant remeshing. In ACM Solid and Physical Modeling Symposium.
[21]
Lindstrom, P., and Silva, C. 2001. A memory insensitive technique for large model simplification. In IEEE Visualization, 121--126.
[22]
Lindstrom, P. 2002. Out-of-core simplification of large polygonal meshes. In ACM SIGGRAPH, 259--262.
[23]
Luebke, D., Watson, B., Cohen, J. D., Reddy, M., and Varshney, A. 2002. Level of Detail for 3D Graphics. Elsevier Science Inc., New York, NY, USA.
[24]
Marinov, M., and Kobbelt, L. 2004. Direct anisotropic quaddominant remeshing. In Pacific Graphics, 207--216.
[25]
Marinov, M., and Kobbelt, L. 2006. A robust two-step procedure for quad-dominant remeshing. Computer Graphics Forum 25, 3, 537--546.
[26]
Murdoch, P., Benzley, S., Blacker, T., and Mitchell, S. 1997. The spatial twist continuum: A connectivity based method for representing all-hexahedral finite element meshes. Finite Element in Analysis and Design 28, 2 (December), 137--149.
[27]
Ni, X., Garland, M., and Hart, J. C. 2004. Fair morse functions for extracting the topological structure of a surface mesh. In ACM SIGGRAPH, 613--622.
[28]
Owen, S., Staten, M., Canann, S., and Saigal, S. 1999. Q-morph: An indirect approach to advancing front quad meshing. International Journal for Numerical Methods in Engineering (March), 1317--1340.
[29]
Shepherd, J. 2007. Topologic and Geometric Constraint-Based Hexahedral Mesh Generation. PhD thesis, University of Utah.
[30]
Shimada, K., and Gossard, D. C. 1995. Bubble mesh: automated triangular meshing of non-manifold geometry by sphere packing. In 3rd ACM Symposium on Solid Modeling and Applications, 409--419.
[31]
Shimada, K. 1993. Physically-based mesh generation: automated triangulation of surfaces and volumes via bubble packing. PhD thesis, Massachusetts Institute of Technology.
[32]
Shimada, K. 1999. Quadrilateral meshing with directionality control via close packing of square cells. SIAM Conference on Geometric Modeling.
[33]
Smith, J., and Boier-Martin, I. 2005. Combining metrics for mesh simplification and parameterization. In ACM SIGGRAPH Sketches, 135.
[34]
Staten, M. L., and Canann, S. A. 1997. Post refinement element shape improvement for quadrilateral meshes. ASME AMD: Trends in Unstructured Mesh Generation, 9--16.
[35]
Staten, M., Benzley, S., and Scott, M. 2008. A methodology for quadrilateral finite element mesh coarsening. Engineering with Computers, 241--251.
[36]
Takeuchi, S., Suzuki, H., Kimura, F., Kanai, T., and Shimada, K. 2000. Subdivision surface fitting with qem-based mesh simplification and reconstruction of approximated b-spline surfaces. In Pacific Graphics, 202.
[37]
Tong, Y., Alliez, P., Cohen-Steiner, D., and Desbrun, M. 2006. Designing quadrangulations with discrete harmonic forms. In Symposium on Geometry Processing, 201--210.
[38]
Viswanath, N., Shimada, K., and Itoh, T. 2000. Quadrilateral meshing with anisotropy and directionality control via close packing of rectangular cells. In 9th International Meshing Roundtable, 227--238.
[39]
Zhang, Y., Bajaj, C., and Guoliang, X. 2005. Surface smoothing and quality improvement of quadrilateral/hexahedral meshes with geometric flow. In 14th International Meshing Roundtable, 449--468.

Cited By

View all
  • (2024)Fast and Compact Partial Differential Equation (PDE)-Based Dynamic Reconstruction of Extended Position-Based Dynamics (XPBD) Deformation SimulationMathematics10.3390/math1220317512:20(3175)Online publication date: 11-Oct-2024
  • (2024)Differentiable Micro-Mesh Construction2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.00411(4294-4303)Online publication date: 16-Jun-2024
  • (2024)Learning Topological Operations on Meshes with Application to Block Decomposition of PolygonsComputer-Aided Design10.1016/j.cad.2024.103744175(103744)Online publication date: Oct-2024
  • Show More Cited By

Recommendations

Comments

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

Check for updates

Qualifiers

  • Research-article

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)74
  • Downloads (Last 6 weeks)15
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Fast and Compact Partial Differential Equation (PDE)-Based Dynamic Reconstruction of Extended Position-Based Dynamics (XPBD) Deformation SimulationMathematics10.3390/math1220317512:20(3175)Online publication date: 11-Oct-2024
  • (2024)Differentiable Micro-Mesh Construction2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.00411(4294-4303)Online publication date: 16-Jun-2024
  • (2024)Learning Topological Operations on Meshes with Application to Block Decomposition of PolygonsComputer-Aided Design10.1016/j.cad.2024.103744175(103744)Online publication date: Oct-2024
  • (2024)Numerical mass transfer simulations of Venturi-type solid phase oxygen control with mass exchanger in UPBEAT loopAnnals of Nuclear Energy10.1016/j.anucene.2024.110735207(110735)Online publication date: Nov-2024
  • (2023)Review of Three-Dimensional Model Simplification Algorithms Based on Quadric Error Metrics and Bibliometric Analysis by Knowledge MapMathematics10.3390/math1123481511:23(4815)Online publication date: 29-Nov-2023
  • (2023)An adaptive local refinement algorithm for quadrilateral meshInternational Conference on Algorithms, High Performance Computing, and Artificial Intelligence (AHPCAI 2023)10.1117/12.3011837(202)Online publication date: 7-Dec-2023
  • (2023)Singularity Structure Optimization for Hexahedral Mesh Via Dual OperationsJournal of Computing and Information Science in Engineering10.1115/1.406340224:2Online publication date: 10-Oct-2023
  • (2023)Edge‐Friend: Fast and Deterministic Catmull‐Clark Subdivision SurfacesComputer Graphics Forum10.1111/cgf.1486342:8Online publication date: 3-Aug-2023
  • (2023)A Visualization System for Hexahedral Mesh Quality Study2023 IEEE Visualization and Visual Analytics (VIS)10.1109/VIS54172.2023.00026(86-90)Online publication date: 21-Oct-2023
  • (2023)3-D EM Modeling of Medical Microwave Imaging Scenarios With Controllable AccuracyIEEE Transactions on Antennas and Propagation10.1109/TAP.2022.320924471:2(1640-1653)Online publication date: Feb-2023
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media