Assignment 2
Mesh Simplification

Introduction

To achieve the real-time performance, the most important issue is to reduce the number of polygons to be rendered. Mesh simplification is an essential technique to reduce the number of polygons of meshes designed from artists or from the 3D scanner. In this assignment, you are required to implement a mesh simplification application using LOD with APS metric for priprity of the simplification order and QEM for optimizing the replaced vertices.

Detail

The goal of mesh simplification is to preserve the shape, texture content, and geometric features of the mesh during the simplification process. The Quadric Error Metrics (QEM) proposed by M. Garland and P. Heckbert provides a metric to decive the order of simplification using geometric features. Also, the optimal vertex along the collapsed edge can be computed by the metric. The Appearance-Preserving Simplification (APS) proposed by Cohen et al. provides a metric that considers both the geometric features and the other appearance features such as texture mappings.

The goal of this assignment is to implement a mesh simplification framework using LOD, the edge collapse is used as the local simplification operator. The order of simplification is determined by APS, and the optimal replaced vertex of the collapsed edge is computed using QEM.

The measurement of local error using APS between each level of LOD is the basicest requirement. There will be extra bonus if you implement the global error measurement of APS between the current level of LOD and the original mesh, which requires a vertex hierarchy to keep the relations of the collapsed edges and vertices in all steps.

Requirement

• Greedy framework for LOD.
• Edge based data structure using Half-edge.
• APS for simplification order.
• QEM for optimizing the position of the replaced vertex.
• Bonus : Global error between current level of LOD and the original mesh.
• Bonus : Mesh simplification for multi-patches models.

A written report is also required which includes a short description of APS and QEM metrics, your program architecture, and some results.

Test data

The following two test models are in wavefront OBJ and Direct .X formats. Both of the models contain only one patch, and have boundaries. The test models can be downloaded here.

The Test.mtl and check_demo.tif are material and texture files for the two models.

Half of Armadillo model

Single patch, boundary.

	The mesh in the parameter domain.

Simple Surface

Single patch, boundary.

	The mesh in the parameter domain.

Related Links

Level-of-Detail for 3D Graphics
The official web for the book "Level-of-detail for graphics", lots of resources (papers, models, tools...) can be found there.

Surface Simplification Using Quadric Error Metrics, M. Garland and P. Heckbert, Proceedings of SIGGRAPH 97.

Quadric-Based Polygonal Surface Simplification, Michael Garland's Ph.D. dissertation, Computer Science Department, Carnegie Mellon University, 1999.
A more detail discussion of QEM can be found.

Appearance-Preserving Simplification, Cohen, Jonathan, Marc Olano, and Dinesh Manocha. Appearance-Preserving Simplfication. Proceedings of SIGGRAPH 98.

Source codes

Harvard's mesh library
A mesh library for developing 3D modeling applications written by Gu at Harvard University.

Level-of-Detail for 3D Graphics
List of source codes for LOD platform collected by book "Level-of-Detail for 3D Graphics".