Premium
Motorcycle Graphs: Canonical Quad Mesh Partitioning
Author(s) -
Eppstein David,
Goodrich Michael T.,
Kim Ethan,
Tamstorf Rasmus
Publication year - 2008
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/j.1467-8659.2008.01288.x
Subject(s) - polygon mesh , quadrilateral , computer science , t vertices , volume mesh , graph , mesh generation , algorithm , theoretical computer science , mathematics , computer graphics (images) , finite element method , physics , thermodynamics
We describe algorithms for canonically partitioning semi‐regular quadrilateral meshes into structured submeshes, using an adaptation of the geometric motorcycle graph of Eppstein and Erickson to quad meshes. Our partitions may be used to efficiently find isomorphisms between quad meshes. In addition, they may be used as a highly compressed representation of the original mesh. These partitions can be constructed in sublinear time from a list of the extraordinary vertices in a mesh. We also study the problem of further reducing the number of submeshes in our partitions—we prove that optimizing this number is NP‐hard, but it can be efficiently approximated.