skip to main content
10.1145/1457515.1409101acmconferencesArticle/Chapter ViewAbstractPublication Pagessiggraph-asiaConference Proceedingsconference-collections
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

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)Quadrilateral surface mesh generation with improved quality by combination of trianglesInternational Journal for Numerical Methods in Engineering10.1002/nme.7539125:16Online publication date: 27-May-2024
  • (2023)Unreal engine nanite foliage shadow imposterSecond International Conference on Applied Statistics, Computational Mathematics, and Software Engineering (ASCMSE 2023)10.1117/12.2692451(104)Online publication date: 23-Aug-2023
  • (2021)Q-zipACM Transactions on Graphics10.1145/3478513.348052340:6(1-13)Online publication date: 10-Dec-2021
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SIGGRAPH Asia '08: ACM SIGGRAPH Asia 2008 papers
December 2008
581 pages
ISBN:9781450318310
DOI:10.1145/1457515
  • Editor:
  • John C. Hart
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2008

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article

Funding Sources

Conference

SIGGRAPH '08
Sponsor:

Acceptance Rates

SIGGRAPH Asia '08 Paper Acceptance Rate 59 of 320 submissions, 18%;
Overall Acceptance Rate 178 of 869 submissions, 20%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

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

Other Metrics

Citations

Cited By

View all
  • (2024)Quadrilateral surface mesh generation with improved quality by combination of trianglesInternational Journal for Numerical Methods in Engineering10.1002/nme.7539125:16Online publication date: 27-May-2024
  • (2023)Unreal engine nanite foliage shadow imposterSecond International Conference on Applied Statistics, Computational Mathematics, and Software Engineering (ASCMSE 2023)10.1117/12.2692451(104)Online publication date: 23-Aug-2023
  • (2021)Q-zipACM Transactions on Graphics10.1145/3478513.348052340:6(1-13)Online publication date: 10-Dec-2021
  • (2021)Topological operations for editing the singularity on a hex meshEngineering with Computers10.1007/s00366-019-00888-w37:2(1357-1375)Online publication date: 1-Apr-2021
  • (2020)Cost Minimizing Local Anisotropic Quad Mesh RefinementComputer Graphics Forum10.1111/cgf.1407639:5(163-172)Online publication date: 12-Aug-2020
  • (2018)Generalized motorcycle graphs for imperfect quad-dominant meshesACM Transactions on Graphics10.1145/3197517.320138937:4(1-16)Online publication date: 30-Jul-2018
  • (2016)All-Hex Meshing of Multiple-Region Domains without CleanupProcedia Engineering10.1016/j.proeng.2016.11.055163(251-261)Online publication date: 2016
  • (2015)Robust All-quad Meshing of Domains with Connected RegionsProcedia Engineering10.1016/j.proeng.2015.10.125124(96-108)Online publication date: 2015
  • (2014)A Sketch-Based Modeling Framework Based on Adaptive MeshesProceedings of the 2014 27th SIBGRAPI Conference on Graphics, Patterns and Images10.1109/SIBGRAPI.2014.16(17-24)Online publication date: 26-Aug-2014
  • (2013)Integer-grid maps for reliable quad meshingACM Transactions on Graphics10.1145/2461912.246201432:4(1-12)Online publication date: 21-Jul-2013
  • Show More Cited By

View Options

Login options

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