Surface simplification using quadric error metrics

TLDR

Many computer graphics applications require highly detailed models, yet the necessary level of detail varies, so approximations are often used to reduce processing time. The algorithm iteratively contracts arbitrary vertex pairs, using quadric matrices to maintain surface error, and supports non‑manifold models to join unconnected regions. It rapidly produces high‑quality approximations that improve both visual fidelity and geometric error compared to previous methods. CR Categories: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling—surface and object representations.

Abstract

Many applications in computer graphics require complex, highly detailed models. However, the level of detail actually necessary may vary considerably. To control processing time, it is often desirable to use approximations in place of excessively detailed models. We have developed a surface simplification algorithm which can rapidly produce high quality approximations of polygonal models. The algorithm uses iterative contractions of vertex pairs to simplify models and maintains surface error approximations using quadric matrices. By contracting arbitrary vertex pairs (not just edges), our algorithm is able to join unconnected regions of models. This can facilitate much better approximations, both visually and with respect to geometric error. In order to allow topological joining, our system also supports non-manifold surface models. CR Categories: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling—surface and object representations