Article

Designing quadrangulations with discrete harmonic forms

Authors:

D. Cohen-Steiner,

M. DesbrunAuthors Info & Claims

SGP '06: Proceedings of the fourth Eurographics symposium on Geometry processing

Pages 201 - 210

Published: 26 June 2006 Publication History

Abstract

We introduce a framework for quadrangle meshing of discrete manifolds. Based on discrete differential forms, our method hinges on extending the discrete Laplacian operator (used extensively in modeling and animation) to allow for line singularities and singularities with fractional indices. When assembled into a singularity graph, these line singularities are shown to considerably increase the design flexibility of quad meshing. In particular, control over edge alignments and mesh sizing are unique features of our novel approach. Another appeal of our method is its robustness and scalability from a numerical viewpoint: we simply solve a sparse linear system to generate a pair of piecewise-smooth scalar fields whose isocontours form a pure quadrangle tiling, with no T-junctions.

References

[1]

{ACSD*03} Alliez P., Cohen-Steiner D., Devillers O., Lévy B., Desbrun M.: Anisotropic polygonal remeshing. ACM Trans. Graph. 22, 3 (2003).

Digital Library

[2]

{AUGA05} Alliez P., Ucelli G., Gotsman C., Attene M.: Recent advances in remeshing of surfaces. STAR AIM@SHAPE, January 2005.

[3]

{BBK05} Botsch M., Bommes D., Kobbelt L.: Efficient linear system solvers for mesh processing. In IMA Conf. on Math. of Surfaces (2005), pp. 62--83.

Digital Library

[4]

{BMRJ04} Boier-Martin I., Rushmeier H., Jin J.: Parameterization of triangle meshes over quadrilateral domains. In Symp. on Geometry processing (2004), pp. 193--203.

Digital Library

[5]

{CSM03} Cohen-Steiner D., Morvan J.-M.: Restricted delaunay triangulations and normal cycle. In Proceedings of the Symp. on Computational Geometry (2003), pp. 312--321.

Digital Library

[6]

{DBG*06} Dong S., Bremer P.-T., Garland M., Pascucci V., Hart J. C.: Spectral surface quadrangulation. to appear at ACM SIGGRAPH'06, July 2006.

Digital Library

[7]

{DKG05} Dong S., Kircher S., Garland M.: Harmonic functions for quadrilateral remeshing of arbitrary manifolds. Computer Aided Design (Special Issue on Geometry Processing) 22, 4 (2005), 392--423.

[8]

{DKT05} Desbrun M., Kanso E., Tong Y.: Discrete differential forms for computational modeling. In Discrete Differential Geometry. ACM SIGGRAPH Course Notes, 2005.

Digital Library

[9]

{Ede00} Edelsbrunner H.: Mathematical problems in the reconstruction of shapes, 2000. Talk at MSRI's Workshop on Computational Algebraic Analysis (http://msri.mathnet.or.kr/).

[10]

{EW05} Erickson J., Whittlesey K.: Greedy optimal homotopy and homology generators. In SODA (2005), pp. 1038--1046.

Digital Library

[11]

{GH95} Grimm C., Hughes J.: Modeling surfaces of arbitrary topology. In Proceedings of ACM SIGGRAPH (July 1995), pp. 359--369.

Digital Library

[12]

{GY03} Gu X., Yau S.-T.: Global conformal parameterization. In Symposium on Geometry Processing (2003), pp. 127--137.

Digital Library

[13]

{JWYG04} Jin M., Wang Y., Yau S.-T., Gu X.: Optimal global conformal surface parameterization. In IEEE Visualization (2004), pp. 267--274.

Digital Library

[14]

{KLS03} Khodakovsky A., Litke N., Schröder P.: Globally smooth parameterizations with low distortion. ACM Trans. Graph. 22, 3 (2003), 350--357.

Digital Library

[15]

{KSS06} Kharevych L., Springborn B., Schröder P.: Discrete conformal mappings via circle patterns. ACM Trans. on Graphics 25, 2 (2006).

Digital Library

[16]

{MK04} Marinov M., Kobbelt L.: Direct anisotropic quad-dominant remeshing. In Proceedings of the Pacific Graphics (2004), pp. 207--216.

Digital Library

[17]

{PP93} Pinkall U., Polthier K.: Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2(1) (1993), 15--36.

[18]

{RLL*05} Ray N., Li W. C., Lévy B., Sheffer A., Alliez P.: Periodic global parameterization. Preprint found at www.loria.fr/~levy/publications/ (2005).

Digital Library

[19]

{TCR05} Toledo S., Chen D., Rotkin V.: TAUCS. Available at http://www.tau.ac.il/~stoledo/taucs, 2005.

[20]

{YZ04} Ying L., Zorin D.: A simple manifold-based construction of surfaces of arbitrary smoothness. ACM Trans. on Graphics 23, 3 (2004), 271--275.

Digital Library

Cited By

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
Liu JXin SGao XGao KXu KChen BTu C(2021)Computational Object-Wrapping Rope NetsACM Transactions on Graphics10.1145/347682941:1(1-16)Online publication date: 22-Sep-2021
https://dl.acm.org/doi/10.1145/3476829
Arora RSingh K(2021)Mid-Air Drawing of Curves on 3D Surfaces in Virtual RealityACM Transactions on Graphics10.1145/345909040:3(1-17)Online publication date: 15-Jul-2021
https://dl.acm.org/doi/10.1145/3459090
Show More Cited By

Index Terms

Designing quadrangulations with discrete harmonic forms

Index terms have been assigned to the content through auto-classification.

Recommendations

Finding hexahedrizations for small quadrangulations of the sphere

This paper tackles the challenging problem of constrained hexahedral meshing. An algorithm is introduced to build combinatorial hexahedral meshes whose boundary facets exactly match a given quadrangulation of the topological sphere. This algorithm is ...
Exploring quadrangulations

We present a framework for exploring topologically unique quadrangulations of an input shape. First, the input shape is segmented into surface patches. Second, different topologies are enumerated and explored in each patch. This is realized by an ...
Harmonic triangulations

We introduce the notion of harmonic triangulations: a harmonic triangulation simultaneously minimizes the Dirichlet energy of all piecewise linear functions. By a famous result of Rippa, Delaunay triangulations are the harmonic triangulations of planar ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SGP '06: Proceedings of the fourth Eurographics symposium on Geometry processing

June 2006

243 pages

ISBN:3905673363

Conference Chairs:
Alla Sheffer
University of British Columbia
,
Konrad Polthier
Freie Universität Berlin

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 26 June 2006

Check for updates

Qualifiers

Article

Conference

SGP '06

Sponsor:

SIGGRAPH
EUROGRAPHICS

SGP '06: Geometry processing

June 26 - 28, 2006

Sardinia, Cagliari, Italy

Acceptance Rates

SGP '06 Paper Acceptance Rate 21 of 79 submissions, 27%;

Overall Acceptance Rate 64 of 240 submissions, 27%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

101
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

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
Liu JXin SGao XGao KXu KChen BTu C(2021)Computational Object-Wrapping Rope NetsACM Transactions on Graphics10.1145/347682941:1(1-16)Online publication date: 22-Sep-2021
https://dl.acm.org/doi/10.1145/3476829
Arora RSingh K(2021)Mid-Air Drawing of Curves on 3D Surfaces in Virtual RealityACM Transactions on Graphics10.1145/345909040:3(1-17)Online publication date: 15-Jul-2021
https://dl.acm.org/doi/10.1145/3459090
Lyon MCampen MBommes DKobbelt L(2019)Parametrization quantization with free boundaries for trimmed quad meshingACM Transactions on Graphics10.1145/3306346.332301938:4(1-14)Online publication date: 12-Jul-2019
https://dl.acm.org/doi/10.1145/3306346.3323019
Solomon JVaxman A(2019)Optimal transport-based polar interpolation of directional fieldsACM Transactions on Graphics10.1145/3306346.332300538:4(1-13)Online publication date: 12-Jul-2019
https://dl.acm.org/doi/10.1145/3306346.3323005
Campen MBousseau AGutierrez D(2017)Partitioning surfaces into quadrilateral patchesProceedings of the European Association for Computer Graphics: Tutorials10.2312/egt.20171033(1-25)Online publication date: 24-Apr-2017
https://dl.acm.org/doi/10.2312/egt.20171033
Poranne RTarini MHuber SPanozzo DSorkine-Hornung O(2017)AutocutsACM Transactions on Graphics10.1145/3130800.313084536:6(1-11)Online publication date: 20-Nov-2017
https://dl.acm.org/doi/10.1145/3130800.3130845
Vaxman ACampen MDiamanti OBommes DHildebrandt KTechnion MPanozzo D(2017)Directional field synthesis, design, and processingACM SIGGRAPH 2017 Courses10.1145/3084873.3084921(1-30)Online publication date: 30-Jul-2017
https://dl.acm.org/doi/10.1145/3084873.3084921
Campen MZorin D(2017)Similarity maps and field-guided T-splinesACM Transactions on Graphics10.1145/3072959.307364736:4(1-16)Online publication date: 20-Jul-2017
https://dl.acm.org/doi/10.1145/3072959.3073647
Vaxman ACampen MDiamanti OPanozzo DBommes DHildebrandt KBen-Chen MMadeira JPatow G(2016)Directional field synthesis, design, and processingProceedings of the 37th Annual Conference of the European Association for Computer Graphics: State of the Art Reports10.5555/3059330.3059332(545-572)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/3059330.3059332
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten