Motorcycle Graphs: Canonical Quad Mesh Partitioning
Loading...
Date
2008
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and Blackwell Publishing Ltd
Abstract
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.
Description
@article{10.1111:j.1467-8659.2008.01288.x,
journal = {Computer Graphics Forum},
title = {{Motorcycle Graphs: Canonical Quad Mesh Partitioning}},
author = {Eppstein, David and Goodrich, Michael T. and Kim, Ethan and Tamstorf, Rasmus},
year = {2008},
publisher = {The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {10.1111/j.1467-8659.2008.01288.x}
}