Spectral surface quadrangulation

Shen Dong, Peer Timo Bremer, Michael Garland, Valerio Pascucci, John C Hart

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 PDE problems, especially fluid dynamics, and are best suited for defining Catmull-Clark subdivision surfaces. We describe a fundamentally new approach to the quadrangulation of manifold polygon meshes using Laplacian eigenfunctions, the natural harmonics of the surface. These surface functions distribute their extrema evenly across a mesh, which connect via gradient flow into a quadrangular base mesh. An iterative relaxation algorithm simultaneously refines this initial complex to produce a globally smooth parameterization of the surface. From this, we can construct a well-shaped quadrilateral mesh with very few extraordinary vertices. The quality of this mesh relies on the initial choice of eigenfunction, for which we describe algorithms and hueristics to efficiently and effectively select the harmonic most appropriate for the intended application.

Original languageEnglish (US)
Title of host publicationACM SIGGRAPH 2006 Papers, SIGGRAPH '06
Pages1057-1066
Number of pages10
DOIs
StatePublished - Dec 1 2006
EventACM SIGGRAPH 2006 Papers, SIGGRAPH '06 - Boston, MA, United States
Duration: Jul 30 2006Aug 3 2006

Publication series

NameACM SIGGRAPH 2006 Papers, SIGGRAPH '06

Other

OtherACM SIGGRAPH 2006 Papers, SIGGRAPH '06
CountryUnited States
CityBoston, MA
Period7/30/068/3/06

Fingerprint

Eigenvalues and eigenfunctions
Fluid dynamics
Parameterization
Geometry
Processing

Keywords

  • Morse theory
  • Morse-Smale complex
  • laplacian eigenvectors
  • quadrangular remeshing
  • spectral mesh decomposition

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Computer Vision and Pattern Recognition
  • Software

Cite this

Dong, S., Bremer, P. T., Garland, M., Pascucci, V., & Hart, J. C. (2006). Spectral surface quadrangulation. In ACM SIGGRAPH 2006 Papers, SIGGRAPH '06 (pp. 1057-1066). (ACM SIGGRAPH 2006 Papers, SIGGRAPH '06). https://doi.org/10.1145/1179352.1141993

Spectral surface quadrangulation. / Dong, Shen; Bremer, Peer Timo; Garland, Michael; Pascucci, Valerio; Hart, John C.

ACM SIGGRAPH 2006 Papers, SIGGRAPH '06. 2006. p. 1057-1066 (ACM SIGGRAPH 2006 Papers, SIGGRAPH '06).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Dong, S, Bremer, PT, Garland, M, Pascucci, V & Hart, JC 2006, Spectral surface quadrangulation. in ACM SIGGRAPH 2006 Papers, SIGGRAPH '06. ACM SIGGRAPH 2006 Papers, SIGGRAPH '06, pp. 1057-1066, ACM SIGGRAPH 2006 Papers, SIGGRAPH '06, Boston, MA, United States, 7/30/06. https://doi.org/10.1145/1179352.1141993
Dong S, Bremer PT, Garland M, Pascucci V, Hart JC. Spectral surface quadrangulation. In ACM SIGGRAPH 2006 Papers, SIGGRAPH '06. 2006. p. 1057-1066. (ACM SIGGRAPH 2006 Papers, SIGGRAPH '06). https://doi.org/10.1145/1179352.1141993
Dong, Shen ; Bremer, Peer Timo ; Garland, Michael ; Pascucci, Valerio ; Hart, John C. / Spectral surface quadrangulation. ACM SIGGRAPH 2006 Papers, SIGGRAPH '06. 2006. pp. 1057-1066 (ACM SIGGRAPH 2006 Papers, SIGGRAPH '06).
@inproceedings{f21260543307481682730854b36b17bf,
title = "Spectral surface quadrangulation",
abstract = "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 PDE problems, especially fluid dynamics, and are best suited for defining Catmull-Clark subdivision surfaces. We describe a fundamentally new approach to the quadrangulation of manifold polygon meshes using Laplacian eigenfunctions, the natural harmonics of the surface. These surface functions distribute their extrema evenly across a mesh, which connect via gradient flow into a quadrangular base mesh. An iterative relaxation algorithm simultaneously refines this initial complex to produce a globally smooth parameterization of the surface. From this, we can construct a well-shaped quadrilateral mesh with very few extraordinary vertices. The quality of this mesh relies on the initial choice of eigenfunction, for which we describe algorithms and hueristics to efficiently and effectively select the harmonic most appropriate for the intended application.",
keywords = "Morse theory, Morse-Smale complex, laplacian eigenvectors, quadrangular remeshing, spectral mesh decomposition",
author = "Shen Dong and Bremer, {Peer Timo} and Michael Garland and Valerio Pascucci and Hart, {John C}",
year = "2006",
month = "12",
day = "1",
doi = "10.1145/1179352.1141993",
language = "English (US)",
isbn = "1595933646",
series = "ACM SIGGRAPH 2006 Papers, SIGGRAPH '06",
pages = "1057--1066",
booktitle = "ACM SIGGRAPH 2006 Papers, SIGGRAPH '06",

}

TY - GEN

T1 - Spectral surface quadrangulation

AU - Dong, Shen

AU - Bremer, Peer Timo

AU - Garland, Michael

AU - Pascucci, Valerio

AU - Hart, John C

PY - 2006/12/1

Y1 - 2006/12/1

N2 - 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 PDE problems, especially fluid dynamics, and are best suited for defining Catmull-Clark subdivision surfaces. We describe a fundamentally new approach to the quadrangulation of manifold polygon meshes using Laplacian eigenfunctions, the natural harmonics of the surface. These surface functions distribute their extrema evenly across a mesh, which connect via gradient flow into a quadrangular base mesh. An iterative relaxation algorithm simultaneously refines this initial complex to produce a globally smooth parameterization of the surface. From this, we can construct a well-shaped quadrilateral mesh with very few extraordinary vertices. The quality of this mesh relies on the initial choice of eigenfunction, for which we describe algorithms and hueristics to efficiently and effectively select the harmonic most appropriate for the intended application.

AB - 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 PDE problems, especially fluid dynamics, and are best suited for defining Catmull-Clark subdivision surfaces. We describe a fundamentally new approach to the quadrangulation of manifold polygon meshes using Laplacian eigenfunctions, the natural harmonics of the surface. These surface functions distribute their extrema evenly across a mesh, which connect via gradient flow into a quadrangular base mesh. An iterative relaxation algorithm simultaneously refines this initial complex to produce a globally smooth parameterization of the surface. From this, we can construct a well-shaped quadrilateral mesh with very few extraordinary vertices. The quality of this mesh relies on the initial choice of eigenfunction, for which we describe algorithms and hueristics to efficiently and effectively select the harmonic most appropriate for the intended application.

KW - Morse theory

KW - Morse-Smale complex

KW - laplacian eigenvectors

KW - quadrangular remeshing

KW - spectral mesh decomposition

UR - http://www.scopus.com/inward/record.url?scp=34248397312&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34248397312&partnerID=8YFLogxK

U2 - 10.1145/1179352.1141993

DO - 10.1145/1179352.1141993

M3 - Conference contribution

AN - SCOPUS:34248397312

SN - 1595933646

SN - 9781595933645

T3 - ACM SIGGRAPH 2006 Papers, SIGGRAPH '06

SP - 1057

EP - 1066

BT - ACM SIGGRAPH 2006 Papers, SIGGRAPH '06

ER -