Premium
A primal/dual representation for discrete Morse complexes on tetrahedral meshes
Author(s) -
Weiss Kenneth,
Iuricich Federico,
Fellegara Riccardo,
De Floriani Leila
Publication year - 2013
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/cgf.12123
Subject(s) - discrete morse theory , tetrahedron , adjacency list , topology (electrical circuits) , computer science , morse code , polygon mesh , mathematics , morse theory , algorithm , combinatorics , pure mathematics , geometry , telecommunications
We consider the problem of computing discrete Morse and Morse‐Smale complexes on an unstructured tetrahedral mesh discretizing the domain of a 3D scalar field. We use a duality argument to define the cells of the descending Morse complex in terms of the supplied (primal) tetrahedral mesh and those of the ascending complex in terms of its dual mesh. The Morse‐Smale complex is then described combinatorially as collections of cells from the intersection of the primal and dual meshes. We introduce a simple compact encoding for discrete vector fields attached to the mesh tetrahedra that is suitable for combination with any topological data structure encoding just the vertices and tetrahedra of the mesh. We demonstrate the effectiveness and scalability of our approach over large unstructured tetrahedral meshes by developing algorithms for computing the discrete gradient field and for extracting the cells of the Morse and Morse‐Smale complexes. We compare implementations of our approach on an adjacency‐based topological data structure and on the PR‐star octree, a compact spatio‐topological data structure.