Edge Collapse Considering Triangular Mesh for Model Simplification

Abstract

Because of re-triangularization during the process of traditional edge collapse, this paper introduces a new edge collapsing method improved with the use of triangular mesh. We deal with a series of feature points, and directly establish the triangular mesh which meet the need of simplification, and avoid triangulating secondly. The experiment shows that this method can improve the convergence rate, and simplified effect, under condition of assurance of the triangle mesh approximation precision and the decrease of the amount of the triangular facets.

1 Introduction

The methods based on vertex decimation and edge collapse are generally using in mesh model simplification [1]. These algorithms revealed some defects in different with the deepening of application. The edge collapse is very similar to the vertex decimation, except for re-triangularizing the holes after simplification, as thus reduce the effect of model simplification. In order to avoid the above defect, there is a kind of improved edge collapse algorithms, namely triangle mesh method. The triangular facet is the deleted element in simplified process, refrain from re-triangularization consequently. Experimental results illustrate that the edge collapse method considering triangular mesh can directly improve simplified efficiency and maintain features of model.

2 Relation Work

The vertexes are firstly divided into simple vertex, complex vertex, boundary vertex, and interior point and angle point located in the edge feature according to the local geometric topological characteristics about the traditional edge collapse [2]. Then edge collapse algorithms first according to the model local geometry,and then according to all kinds of the error between the original model and simplified one, decided to the vertex that would be deleted. If the accuracy is smaller than the error threshold, the vertex was deleted, meanwhile make the holes cause by the deleted vertexes triangularized (Fig. 1).

Fig. 1

The principle of edge collapse algorithm

3 Improved Method

This paper proposed a new simplified algorithm of edge collapse integrated with triangular mesh. The main idea of this method is: adding the judgments to the feature edges and feature points among the mesh in each step of simplified operation of edge collapse, and maintain the feature point as decimating the edge, then all of the points linked with the deleted edge were connected with the candidate points, make the model still keep the features of triangular mesh.

3.1 Extracting the Edge Feature

Normally, edge weighted value is often used to extract the feature edges. Firstly, calculate the weighted value of every edge, and decide which feature edge by a threshold is. Here, two methods are introduced [3]:

• (1) SOD(Second Order Different) (See Fig. 2).

  Fig. 2

  

  The diagram of SOD method

The method is simple, the dihedral angle of each non-border edge,

$$ w\left( e \right) = \arccos \left( {\frac{{n_{i} }}{{\left\| {n_{i} } \right\|}} \cdot \frac{{n_{j} }}{{\left\| {n_{j} } \right\|}}} \right) $$

(1)

Here, $n_{i} ,\,n_{j}$ is the normal of two triangles linked to the edge e respectively. Given a angle threshold $\theta ,$ when $w(e) > \theta ,\,e$ is a feature edge.

• (2) ESOD(Extended Second Order Difference) (See Fig. 3).

  Fig. 3

  

  The diagram of ESOD method

ESOD is a method that consider the neighborhood of the edge e:

$$ w\left( e \right) = \arccos \left( {\frac{{n_{ 1} }}{{\left\| {n_{ 1} } \right\|}} \cdot \frac{{n_{ 2} }}{{\left\| {n_{ 2} } \right\|}}} \right) $$

(2)

Here, $n_{i} ,\,n_{j}$, is the normal of two terminal vertexes of the edge e respectively. Just like SOD, compare $w(e)$ and angle threshold $\theta ,$ if $w(e)$ is greater than $\theta ,\,e$ is feature edge.

Hubeli and Gross [4] analysis SOD and ESOD methods, and think that the SOD is easy and can get the important mesh characteristics when the model’ size is not large. Meanwhile, SOD is efficient, however, when dealing with more complex mesh, such as geographic mesh model, SOD method will mistake noise as feature. ESOD method compared with SOD, use more local information to determine the feature edge, enhance the capability of noise resistance and improve the accuracy of simplification.

3.2 Extracting the Feature Point

The method of angle deviation is used to extract feature point and maintain characteristic of mesh, meanwhile it can judge the top point [5]. Defined the angle deviation of vertex $v$ as:

$$ d\left( v \right) = b\pi - \sum {\varphi_{i} } $$

(3)

Here, $\varphi_{i}$ is the angle of all triangles linked to $v$, and $v$ is the vertex of those angles. As shown in Fig. 5, when the vertex $v$ is interior point, the value of $b$ is taken at 2, when the vertex $v$ locate on the mesh boundary, $b$ for 1. Extracted top point through setting the threshold value of $d\left( v \right)$ (Fig. 4).

Fig. 4

The diagram of vertex $v$

Fig. 5

The angle deviation of vertex $v$

According to the vertex normal calculated by above mentioned ESOD methods, we will be able to extract the feature edges of the model, combined with simple threshold method to determine the type of mesh vertices, extracting the point of the features edges, finally get most of the feature points, and then find the top points as long as by using the angle deviation, just doing like that, we can complete the extracted feature points on the model. For references, follow the given guidelines.

4 Analysis of the Simplified Accuracy

As usually, the original model is sampled firstly, and then use the set of the sampling point to approximate the simplified error of calculated model, so here take 50 % of the set of any origin model. The error metric can be written as:

$$ E_{\hbox{max} } \left( {M_{1} ,M_{2} } \right) = \mathop {\hbox{max} }\limits_{v \subset m} \,\,d_{v} \left( {M_{2} } \right) $$

(4)

$$ E_{evg} \left( {M_{1} ,M_{2} } \right) = \frac{{\sum\limits_{i = 1}^{m} {\left( {d_{v} \left( {M_{2} } \right) \cdot s_{i} } \right)} }}{{\sum\limits_{i = 1}^{m} {s_{i} } }} $$

(5)

Here, $M_{1}$ is the original model, $M_{2}$ is the simplified model, $m$ is the set of sample points of $M_{1} ,\,d_{v} \left( {M_{2} } \right)$ is the distance from the sampling point to the simplified model $M_{2} ,\,s_{i}$ is triangle area of sampling points on $M_{1} \cdot E_{\hbox{max} } \left( {M_{1} ,M_{2} } \right)$ is the maximum error for the simplified model. $E_{evg} \left( {M_{1} ,M_{2} } \right)$ is its average error.

5 Experiment Results

We apply our method to the Stanford university graphics laboratory Cow model (Fig. 6a). (a) is the original model shown in software MeshLab [6]. Firstly we use traditional edge collapse algorithm and our method to simplify Cow model. The number of triangle facets in the original model is 4762. (b),(c),(d) are the simplified model, whose simplification radio is 50, 70, 90 % respectively. The left columns of Fig. 6 are the results of traditional edge collapse algorithms, the right columns are results of our algorithm.

Fig. 6

The experimental results of simplified cow mesh. a The original mesh of cow. b The number of triangular facets is 2,908. c The number of triangular facets is 1,726. d The number of triangular facets is 620

Compared the left column and right one of Fig. 6, we can see the mesh of cow head in the left column is uniform after simplified; features are not particularly obvious, while the right column cow eyes were simplified less, clearer than the left column. The cow nipple in the left column has been deleted when simplified rate of 90 %, and cow nipples still holds in the right columns.

Table 1 lists the maximum error of simplified cow model algorithm based on edge collapse and our algorithm; Table 2 is the average error.

Table 1 The maximum errors of simplified cow model (cm)

Table 2 The average errors of simplified cow model (cm)

The data of Tables 1 and 2 shows that the average errors of the simplified model got by our method generally slightly are smaller than edge collapse algorithm and the errors gap between two methods are larger with the simplified rate increasing. All this certifies that the accuracy of our method is in proportion to the simplified rate. It is thus clear that our method has a good practical and application.

6 Conclusion

This paper study the simplification method triangular mesh model, and discuss the mesh simplification based on edge collapse, and briefly describes the feature edges extraction, model features maintaining, calculate the accuracy of simplification, finally we verify our method by a test. Experimental results show that improved methods used in this paper are basically achieve the desired effect, keep the mesh stability, improved accuracy, can simplify the grid model quickly and meet the need of model accuracy.