Mesh Simplification in Maya with Quadric Error Metrics

Harrison McKenzie Chapter

CalPoly, San Luis Obispo

Introduction

In Computer Graphics, polygonal models add huge amounts of detail and realism to a scene, be they in the form of characters, terrain, or mundane objects. Additionally, the triangles which compose polygonal meshes have many valuable properties with respect to physical simulation and collision detection.

While polygonal models have many good properties, the discretized nature of the surface takes a lot of data to represent. This translates into expensive rendering operations due to data transfer, and expensive physics computations.

In order to reduce the amount of data being processed, polygonal meshes may be simplified. The goal is to reduce the amount of data the mesh uses to represent an object while perserving the shape and character of the object.

The goal of this project is to create a plugin to Maya which makes it easy for artists to selectively reduce the complexity of some geometrical elements in a scene. In this project, a priority is placed on the application of this tool for creating resulting meshes useful for physical simulation.

Algorithm

This project leverages Michael Garland and Paul S. Heckbert work (Surface Simplification Using Quadric Error Metrics) to select which edges to collapse and where to place the resulting point after an edge collapse.

After the mesh is acquired, the plugin associates a matrix Q with all vertices using the Fundamental Error Quadric K matrix for all that vertices' faces. The cost for each potential edge collapse can be found as $v^t(Q_1 + Q_2)v$ where $v$ is the vertex location to collapse to.

Using these costs, a min-heap can be built which selects for the lowest cost edge to collapse. As collapses are performed, the integrity of the heap is ensured by readjusting the edges which have been affected by the edge collapse.

Implementation

This project is written in C++ using the Maya C++ API. It is built as a plugin which can be inserted into Maya, and then called from Maya's MEL command interface.

In the current implementation, the tool harvests the selected scene data from the Maya state, and uses it to generate sets of edge, face, and vertex data. Once this has been performed, the program does a selected number of collapses to the mesh, and writes it back to the Maya state.

Problems

The Maya API leans heavily on an RTTI (Run-time type information) system to find out information about Maya objects. As such, Maya forces the use of a convoluted system of iterator and function classes to operate upon objects. At run-time, the decision is made by RTTI if the (iterator | function) / object matching is valid.

Additionally, the API documentation is nearly non-existent. The best things that exist are the function and class documentation themselves, which are little more than the function prototypes. Further, that documentation is rife with occational copy/paste errors and misspellings.

Specifically to this project, Maya's organization of mesh components (vertices, edges, and faces) is difficult to work with when it is mutated. As all these components are indexed (a sound system, if by itself) an edge collapse can trigger a set of index remappings which are difficult to predict. As the documentation about the functionality is almost non-existent, its is very difficult to do consistently (I found there to be non-obvious edge case remappings based on experimentation in Maya). To make matters worse, the RTTI/Iterator system which Maya employs makes it difficult to store and compare some objects to one another. Even comparing two sets of MObjects (The base RTTI object handle), acquired in the same manner, produces unexpected results.

Conclusion

Though there were some stumbling blocks in the implementation of this tool (centered around Maya's API) it did end up working out and being useful; users may load the plugin, select a portion of the scene, and choose to collapse an amount of edges.

Pictures

Initialization of a triangulated sphere with backface culling Using the MEL shell to run the qem_simplify command to reduce by 10 edges First Results on 10 edge simplification; Using the tool to simplify 250 edges at a time

Downloads

Source

About this document ...

Mesh Simplification in Maya with Quadric Error Metrics

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 web.tex

The translation was initiated by on 2008-12-12