# Quadratic Error Metric Mesh Simplification Algorithm Based on Discrete Curvature

Authors: Li Yao; Shihui Huang; Hui Xu; Peilin Li
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Complex and highly detailed polygon meshes have been adopted for model representation in many areas of computer graphics. Existing works mainly focused on the quadric error metric based complex models approximation, which has not taken the retention of important model details into account. This may lead to visual degeneration. In this paper, we improve Garland and Heckberts’ quadric error metric based algorithm by using the discrete curvature to reserve more features for mesh simplification. Our experiments on various models show that the geometry and topology structure as well as the features of the original models are precisely retained by employing discrete curvature.


---

## Body

## 1. Introduction

There are lots of 3D models with complex polygon meshes in computer graphics application, such as virtual reality, computer aided design technology, and geographic information system. These models contain finely detailed, arbitrary topology surfaces with millions and mostly billions [1] of vertexes. In this regard, large amounts of storage, memory, computation, and bandwidth are required for transmitting and rendering these complex models. Under some constraint circumstances, the highly detailed models are not necessary; namely, we can use relatively simplified models to replace the original models. Retaining the key features by keeping less the vertexes and faces of the model is the essence of the surface simplification algorithm. In recent years, several geometric approaches have been proposed [2, 3]. However, highly detailed meshes usually associate with lots of features while few simplification methods are developed for them [4–9]. In this paper, we combine the quadric error metrics [2] with the discrete curvature to simplify highly detailed meshes while retaining the key features.The organization of the paper is as follows. We review existing approaches on mesh simplification in Section2. We present our method to enhance the quadric error metric algorithm in Section 3 and describe the whole mesh simplification algorithm in Section 4. Experiments have been implemented to compare the performance of our method with the others [10, 11].


## 2. Related Work

Most mesh simplification algorithms coarsen a mesh through edge transformation. Hoppe et al. [3] use an energy function to optimize the errors for edge collapse. However, this is a time-consuming approach that requires complicated mesh transformations: edge collapse, edge split, and edge swap. In order to reduce the time complexity, Garland and Heckbert [2] improve the edge collapse step by introducing the quadric error metric. However, their algorithm may not be adaptable under certain circumstances due to the features deficiency of the models. Then, Liu et al. [9] propose to maintain local features by introducing the concept of sharp degree to the error metrics to change the order of edge collapses in the simplification. However, this approach needs to set two different empirical selection parameters for each model while only a limited number of geometric features are maintained after multiple simplifications.A lot of algorithms related to discrete curvature are published in recent years. Kim et al. [12] define a new error metric based on the discrete curvature, so that LOD (Level of Detail) can be generated precisely and controlled efficiently. But the algorithm needs an accurate approximation of the folding faces and the saddle faces. Kim et al. [13] define a simplification criterion by a triplet of discrete curvature norm, distance metric, and smaller geometric error. However, the method needs to find the optimal position of a new vertex from an edge collapse with respect to discrete curvatures. Though curvature can well express characteristics of polyhedral surfaces, it is difficult to be used as a simplification criterion or adapted to other applications since it is not easy to be estimated accurately on polygonal surfaces. Kim et al. [14] propose an algorithm to implement the mesh simplification in a way that discrete curvature based error metric is used. The error metric is derived from the definition of discrete curvatures of triangle meshes.In this paper, we introduce the discrete curvature to the quadric error metrics [2] to retain detailed features in model simplification. Experiment shows that our approach reserves more features than existing algorithms without sacrificing effectiveness.


## 3. Fundamental Algorithm

The nature of the simplification algorithm is to minimize the number of vertexes and triangles of the original model while the original features of the model are still retained. The base operation of Garland and Heckberts’ simplification algorithm is edge collapse. Figure1 describes how edge collapse works. A vertex, two faces, and one side will be removed by an edge collapse iteratively until the desired result is reached.Figure 1
Edge contraction: the highlighted edge is contracted into a single point. The shaded triangles will degenerate and be removed during the contraction.


## 4. Quadric Error Metrics

Garland and Heckberts’ simplification algorithm is based on the iterative contraction of vertex pairs, which can be written asvi,vj→v-. The order of edge collapse depends on the error which quantifies the distance of point to the faces.Letv be a vertex in three-dimensional space which is vx,vy,vz,1T. And p represents a plane in three-dimensional space, whose equation is(1)ax+by+cz+d=0,with a2+b2+c2=1, and we denote p=a,b,c,dT.The distance from vertexv to the plane p is(2)D2=pTv2=pTvT·pTv=vTppTv=vTKpv,where Kp represents a 4×4 matrix as defined in the following formula:(3)Kp=ppT=a2abacadabb2bcbdacbcc2cdadbdcdd2.Garland and Heckbert [2] associate a set of planes with each vertex. The error of each vertex is defined as the sum of squared distances to all planes. This vertex belongs to(4)Δv=∑p∈planesvD2v=∑p∈planesvvTKpv=vT∑p∈planesvKpv,where planes (v) represents all the triangles that meet at that vertex.When an edge is contracted, the resulting quadric error isΔv-=Δvi+Δvj, where Δv- is the error for new vertex Δv-.


## 5. New Vertex Position

Selecting the new vertex’s location is crucial for maintaining the original model’s topology. The new vertexΔv-’s position needs to be determined for each pair contraction.Since the error functionΔv is quadratic as (4) shown, we can find v- by solving a quadratic equation:(5)∂Δv∂x=∂Δv∂y=∂Δv∂z=0.This is equivalent to solving the following equation:(6)Av-=q11q12q13q14q21q22q23q24q31q32q33q340001vxvyvz1=0001.On one hand, if matrixA is invertible, the optimal position of v- is v-=A-1b. On the other hand, if matrix A is not invertible, we can approximately set v- to vi, vj, or (vi+vj)/2.


## 6. Discrete Curvature

Garland and Heckberts’ algorithm [2] can quickly produce high quality approximations of polygonal surface models. Meanwhile, it is one of the fastest algorithms available for producing high quality approximations. But it cannot maintain the important features.Curvature indicates the degree of bending, namely, the features and the details of the curve. The magnitude of changes in a grid can be depicted by approximation discrete curvature, which reflects the surface characteristics of the grid. The curvature values of flat regions are small while the curvature values of edges, corners, and uneven regions are large. As the edges in 3D models do not have curvature, we can use the dot product of the faces’ normal vector to represent it:(7)cost⁡⁡vi,vj=vi-vj×max⁡f∈Tvi⋃Tvj⁡max⁡n∈Tvivj⁡f→·n→,where Tvi and Tvj are the set of triangles that contain vi and vj, respectively. And Tvivj is the set of triangles that contain both vi and vj. f→ and n→ represent the normal vector of the triangles that contains vi and edge vi,vj, respectively.Now we add the curvature to the quadric error metrics as(8)Δ′v-=Δvi+Δvj+costvi,vj.The order of edge collapses is according to the quadric error metrics. The larger the curvature is, the later the edge collapses will be. Equation (8) has the advantage that both geometric and detailed features of the models are taken into account.


## 7. Algorithm Summary

Distance or volume based error metric is not fit for simplification of irregular models because certain characteristic shapes may lose. Our simplification algorithm, however, classifies the folded edges to ensure that the areas with large curvature will not be simplified. Thus the shape characteristics of the original mesh could be well retained. Our simplification algorithm steps are as follows:Step 1.
Input the original model.Step 2.
Computecostvi,vj for all edges.Step 3.
Compute theΔv for all the vertices.Step 4.
Compute the optimal position ofv- or each edge vi,vj and its cost collapse.Step 5.
Remove the edge of least cost from the heap and collapse it.Step 6.
Update the cost of all relative edges.Step 7.
If simplification reaches desired level, go to Step8, else, go back to Step 5.Step 8.
Simplification ends.


## 8. Experiments and Analysis

In order to verify the performance of the algorithm, we compare our algorithm with Garland and Heckberts’ [2] and Maximo et al.’s [11] methods.Figure2 is the original model of Bones. The model is simplified to 2,972 faces, 1,560 faces, and 786 faces. As shown in Figure 3, the first row is the result of our algorithm, the second row is the result of Garland and Heckberts’ algorithm, and the third row is the result of Maximo et al.’s algorithm [11]. The comparison demonstrates that our algorithm has a better result when increasing the amplitude of simplification. Garland and Heckberts’ results are so homogenized that the feature details are lost and the bones are fractured and deformed. With the increasing amplitude of simplification, the fracture and deformation are becoming more serious.Figure 2
Original model of bones (4,204 faces).Figure 3
Results of simplified Bones model.Maximo et al.’s algorithm has a better result for retaining model feature details. Figure4 shows the details of toes bones after simplification by these three algorithms. Maximo et al.’s result has fewer triangles in toes bones so that important features are lost.Figure 4
Details of simplified Bones model (1,560 faces).
(a)
Our method
(b)
Garland and Heckberts’ method
(c)
Maximo et al.’s methodFigure5 is the original Cow model. Figure 6 shows the comparison between our algorithm and Garland and Heckberts’ algorithm in Cow model. Figure 6 demonstrates the detailed comparison in 1,482 faces. Notice that features such as horns and hooves are still recognizable after our simplification.Figure 5
Original model of cow (5,804 faces).Figure 6
Details of simplified cow model (1,482 faces).
(a)
Proposed method
(b)
Garland and Heckberts’
(c)
Proposed method
(d)
Garland and Heckberts’Figure7 shows the original Person model. Figure 8 provides the results after simplification to different number of faces. The advantage of our algorithm is obvious. Figure 9 shows the details of hand. Our result retains more features than the other two.Figure 7
Person original model (32,574 faces).
(a)
The original model with line
(b)
The original model without lineFigure 8
Results of simplified Person model.Figure 9
Details of simplified Person model (776 faces).
(a)
Proposed method
(b)
Garland and Heckberts’ method
(c)
Maximo et al.’s methodThe time complexity of Garland and Heckberts’ algorithm isO(nlogn). Our algorithm is based on Garland and Heckberts’ method which computes the curvature cost for each edge during the initialization procedure. Our algorithm recomputes the cost of the relative edges and the quadric error metric during the pair contraction. So the time complexity of our algorithm is alsoO(nlogn).Finally, we compare the error on the Bones model by the metric Cignoni et al. [15] proposed. Specifically, the max error between the original model and simplified model is ES1,S2=max⁡p∈S1⁡ep,S2. And the mean error is ES1,S2=(1/S1)∫S1ep,S2ds, where ep,S2 represents the distance of the point p and the model S. Table 1 shows that both the max and mean error of proposed method are better than Garland and Heckberts’ and Maximo et al.s’ algorithm.Table 1
Error comparison.
Algorithm
Models
Bones (2,972 faces)
Bones (1,560 faces)
Bones (786 faces)
Max error
Mean error
Max error
Mean error
Max error
Mean error
Garland and Heckberts’
0.31
e
-
1
0.164
e
-
2
0.629
e
-
1
0.748
e
-
2
0.1112
0.162
e
-
1
Maximo et al.s’
0.73
e
-
1
0.019
e
-
2
0.262
0.67
e
-
2
0.271
0.22
e
-
1
Ours
0.775
e
-
2
0.232
e
-
3
0.123
e
-
1
0.125
e
-
2
0.201
e
-
1
0.285
e
-
2


## 9. Conclusion

We propose a surface simplification algorithm which is based on quadric error metrics and discrete curvature. Our algorithm takes both the geometry and the features into account to overcome the defect that the grids are too well-distributed in Garland and Heckberts’ simplified models. We achieve good performance in experiments.However, only a few initial methods [10, 16] so far are proposed to simplify highly detailed meshes that usually associate with attributes, such as colors and normal and texture information. In the further works, we will devote ourselves to studying the simplification of meshes with attributes.



---

*Source: 428917-2015-05-11.xml*