# Two papers on quad meshes

I'd been holding off on putting them up on the ArXiv, but I see that my co-author Mike Goodrich has made available preprints of two of our papers with Ethan Kim and Rasmus Tamstorf, both of which came out of some consulting we did with Disney:

Motorcycle Graphs: Canonical Quad Mesh Partitioning, Proc. 6th European Symposium on Geometry Processing (SGP), 2008, concerns partitioning unstructured quadrilateral meshes with few irregularities into a small number of regular grids. The main application is to speed up graph isomorphism computations for finding matches between meshes that are combinatorially the same but geometrically different (the same model has been put into a scene in a different pose, or two models with different geometries have the same base shape).

Approximate Topological Matching of Quadrilateral Meshes, Proc. IEEE Int. Conf. on Shape Modeling and Applications (SMI), 2008, looks at the question of how much of a match we can recover when two models are similar but not isomorphic. Unsurprisingly, the problem of finding as large a match as possible is NP-complete, and we show that simple greedy heuristics that build up a match one quadrilateral at a time can be badly misled, but we describe a more sophisticated heuristic that extends the match by layers of as many quadrilaterals as it can and we prove that for models where the number of mismatches is small enough it will find the correct partial match.

Motorcycle Graphs: Canonical Quad Mesh Partitioning, Proc. 6th European Symposium on Geometry Processing (SGP), 2008, concerns partitioning unstructured quadrilateral meshes with few irregularities into a small number of regular grids. The main application is to speed up graph isomorphism computations for finding matches between meshes that are combinatorially the same but geometrically different (the same model has been put into a scene in a different pose, or two models with different geometries have the same base shape).

Approximate Topological Matching of Quadrilateral Meshes, Proc. IEEE Int. Conf. on Shape Modeling and Applications (SMI), 2008, looks at the question of how much of a match we can recover when two models are similar but not isomorphic. Unsurprisingly, the problem of finding as large a match as possible is NP-complete, and we show that simple greedy heuristics that build up a match one quadrilateral at a time can be badly misled, but we describe a more sophisticated heuristic that extends the match by layers of as many quadrilaterals as it can and we prove that for models where the number of mismatches is small enough it will find the correct partial match.