Fair Morse functions for extracting the topological structure of a surface mesh

Xinlai Ni, Michael Garland, John C Hart

Research output: Contribution to journalConference article

Abstract

Morse theory reveals the topological structure of a shape based on the critical points of a real function over the shape. A poor choice of this real function can lead to a complex configuration of an unnecessarily high number of critical points. This paper solves a relaxed form of Laplace's equation to find a "fair" Morse function with a user-controlled number and configuration of critical points. When the number is minimal, the resulting Morse complex cuts the shape into a disk. Specifying additional critical points at surface features yields a base domain that better represents the geometry and shares the same topology as the original mesh, and can also cluster a mesh into approximately developable patches. We make Morse theory on meshes more robust with teflon saddles and flat edge collapses, and devise a new "intermediate value propagation" multigrid solver for finding fair Morse functions that runs in provably linear time.

Original languageEnglish (US)
Pages (from-to)613-622
Number of pages10
JournalACM Transactions on Graphics
Volume23
Issue number3
DOIs
StatePublished - Dec 1 2004
EventACM Transactions on Graphics - Proceedings of ACM SIGGRAPH 2004 -
Duration: Aug 9 2004Aug 12 2004

Fingerprint

Laplace equation
Polytetrafluoroethylenes
Topology
Geometry

Keywords

  • Atlas generation
  • Computational topology
  • Morse theory
  • Surface parameterization
  • Texture mapping

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design

Cite this

Fair Morse functions for extracting the topological structure of a surface mesh. / Ni, Xinlai; Garland, Michael; Hart, John C.

In: ACM Transactions on Graphics, Vol. 23, No. 3, 01.12.2004, p. 613-622.

Research output: Contribution to journalConference article

@article{67b654e8001c4518a18088e8ccfd60df,
title = "Fair Morse functions for extracting the topological structure of a surface mesh",
abstract = "Morse theory reveals the topological structure of a shape based on the critical points of a real function over the shape. A poor choice of this real function can lead to a complex configuration of an unnecessarily high number of critical points. This paper solves a relaxed form of Laplace's equation to find a {"}fair{"} Morse function with a user-controlled number and configuration of critical points. When the number is minimal, the resulting Morse complex cuts the shape into a disk. Specifying additional critical points at surface features yields a base domain that better represents the geometry and shares the same topology as the original mesh, and can also cluster a mesh into approximately developable patches. We make Morse theory on meshes more robust with teflon saddles and flat edge collapses, and devise a new {"}intermediate value propagation{"} multigrid solver for finding fair Morse functions that runs in provably linear time.",
keywords = "Atlas generation, Computational topology, Morse theory, Surface parameterization, Texture mapping",
author = "Xinlai Ni and Michael Garland and Hart, {John C}",
year = "2004",
month = "12",
day = "1",
doi = "10.1145/1015706.1015769",
language = "English (US)",
volume = "23",
pages = "613--622",
journal = "ACM Transactions on Computer Systems",
issn = "0730-0301",
publisher = "Association for Computing Machinery (ACM)",
number = "3",

}

TY - JOUR

T1 - Fair Morse functions for extracting the topological structure of a surface mesh

AU - Ni, Xinlai

AU - Garland, Michael

AU - Hart, John C

PY - 2004/12/1

Y1 - 2004/12/1

N2 - Morse theory reveals the topological structure of a shape based on the critical points of a real function over the shape. A poor choice of this real function can lead to a complex configuration of an unnecessarily high number of critical points. This paper solves a relaxed form of Laplace's equation to find a "fair" Morse function with a user-controlled number and configuration of critical points. When the number is minimal, the resulting Morse complex cuts the shape into a disk. Specifying additional critical points at surface features yields a base domain that better represents the geometry and shares the same topology as the original mesh, and can also cluster a mesh into approximately developable patches. We make Morse theory on meshes more robust with teflon saddles and flat edge collapses, and devise a new "intermediate value propagation" multigrid solver for finding fair Morse functions that runs in provably linear time.

AB - Morse theory reveals the topological structure of a shape based on the critical points of a real function over the shape. A poor choice of this real function can lead to a complex configuration of an unnecessarily high number of critical points. This paper solves a relaxed form of Laplace's equation to find a "fair" Morse function with a user-controlled number and configuration of critical points. When the number is minimal, the resulting Morse complex cuts the shape into a disk. Specifying additional critical points at surface features yields a base domain that better represents the geometry and shares the same topology as the original mesh, and can also cluster a mesh into approximately developable patches. We make Morse theory on meshes more robust with teflon saddles and flat edge collapses, and devise a new "intermediate value propagation" multigrid solver for finding fair Morse functions that runs in provably linear time.

KW - Atlas generation

KW - Computational topology

KW - Morse theory

KW - Surface parameterization

KW - Texture mapping

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

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

U2 - 10.1145/1015706.1015769

DO - 10.1145/1015706.1015769

M3 - Conference article

AN - SCOPUS:12844249956

VL - 23

SP - 613

EP - 622

JO - ACM Transactions on Computer Systems

JF - ACM Transactions on Computer Systems

SN - 0730-0301

IS - 3

ER -