3D mesh simplification with feature preservation based on Whale Optimization Algorithm and Differential Evolution

Abstract

Large-scale 3D models consume large computing and storage resources. To address this challenging problem, this paper proposes a new method to obtain the optimal simplified 3D mesh models with the minimum approximation error. First, we propose a feature-preservation edge collapse operation to maintain the feature edges, in which the collapsing cost is calculated in a novel way by combining Gauss curvature and Quadratic Error Metrics (QEM). Second, we introduce the edge splitting operation into the mesh simplification process and propose a hybrid ‘undo/redo’ mechanism that combines the edge splitting and edge collapse operation to reduce the number of long and narrow triangles. Third, the proposed ‘undo/redo’ mechanism can also reduce the approximation error; however, it is impossible to manually choose the best operation sequence combination that can result in the minimum approximation error. To solve this problem, we formulate the proposed mesh simplification process as an optimization model, in which the solution space is composed of the possible combinations of operation sequences, and the optimization objective is the minimum of the approximation error. Finally, we propose a novel optimization algorithm, WOA-DE, by replacing the exploration phase of the original Whale Optimization Algorithm (WOA) with the mutate and crossover operations of Differential Evolution (DE) to compute the optimal simplified mesh model more efficiently. We conduct numerous experiments to test the capabilities of the proposed method, and the experimental results show that our method outperforms the previous methods in terms of the geometric feature preservation, triangle quality, and approximation error.

Keywords

3D mesh simplification geometric feature preservation ‘undo/redo’ mechanism objective optimization

1. Introduction

In computer graphics, we often utilize 3D meshes to describe object models. Because the drawing time and storage space are proportional to the number of facets, high-detail mesh models with thousands of facets are not practical. On the other hand, the objects in the virtual environment do not always need a high-detail description. To meet the requirements of computer analysis, display, and storage, the high-detail mesh model must be simplified.

Mesh simplification algorithms reduce the number of vertices and facets of 3D mesh models under the condition that the overall appearance and topological structure remain as constant as possible. In other words, mesh simplification uses fewer points and facets to approximate the origin 3D mesh model. Mesh simplification has broad application prospects in computer graphics, such as computer animation and virtual reality, and it is also the foundation for many advanced processing operations, including mesh segmentation [1], rendering [2], 3D reconstruction [3, 4], etc.

To the best of our knowledge, the earliest mesh simplification paper was by James Clark in 1976 [5]. Since then, many kinds of mesh simplification algorithms have been proposed. The QEM algorithm [6] is one of the most widely used mesh simplification algorithms, which can achieve an excellent balance between performance and computation time. However, there are still some challenging issues, that inspire the research motivations behind this manuscript.

•
First, the QEM algorithm only considers the distance from the new vertex to the adjacent planes, which can result in local oversimplification and the loss of important geometric features [7, 8].
•
Second, QEM-based algorithms may generate long and narrow triangles in the process of simplification, which can increase the numerical error, generate singular points, and result in a poor rendering effect of the surface [9].

To solve the above problems, we propose a new mesh simplification algorithm as follows.

•
We propose a feature-preservation edge collapse operation based on adding Gauss curvature to the calculation of collapsing cost. In this way, feature edges with large curvature can be retained in the mesh simplification process.
•
We introduce the edge splitting operation into the mesh simplification and combine the edge collapse operation and edge splitting operation to eliminate the long and narrow triangles.

The proposed mesh simplification process does not reduce or increase the number of facets monotonously, and we utilize the edge splitting operation to undo the edge collapse operation; therefore, we denote this method as the ‘undo/redo’ mechanism. The proposed ‘undo/redo’ mechanism can also reduce the approximation error. In this paper, we propose an optimal mesh simplification problem: for a given mesh model $M$ with $n$ facets and a user-specified number $m$ ( $m<n$ ), compute the optimal simplified mesh $M^{*}$ ( $n-m$ facets) with the minimum approximation error.

The approximation error is not related to the combination method, so it is impossible to manually select the best operation sequence combination that would lead to the minimum error. To search for the best combination, we model the proposed mesh simplification problem as an optimization problem, where the solution space is composed of the possible combinations of operation sequences, and the objective function is the Hausdorff distance.

In recent years, an increasing number of intelligent optimization algorithms have been proposed [10, 11, 12], and they are widely utilized to solve complex practical problems [13, 14, 15, 16] and multi-objective problems [17, 18, 19, 20]. Therefore, we propose a novel optimization algorithm, WOA-DE, by integrating the mutate and crossover mechanisms of DE [21] with the shrinking encircling and spiral updating position mechanisms of WOA [22] to improve the solution quality. The experimental results show that our method consistently outperforms the previous methods.

The contributions are as follows:

•
A feature-preservation edge collapse operation is proposed to preserve the geometric feature.
•
A new hybrid ‘undo/redo’ mechanism combining the edge splitting and edge collapse operation is proposed to reduce the number of long and narrow triangles and reduce the approximation error.
•
An optimized mesh simplification method is proposed to search for the best operation sequence combination to obtain the optimal simplified mesh model with the minimum approximation error.
•
A novel swarm intelligence optimization algorithm, WOA-DE, is proposed to balance the exploration ability and exploitation ability.

2. Related works

2.1 Mesh simplification algorithm

2.1.1 Vertex clustering

Rossignac first proposed a vertex clustering algorithm [23], that surrounds the original mesh model with a bounding box, and divides it into several small boxes by dividing its edges equally. Then for each box, it computes a new representative vertex by the weighted average of the original vertices, as shown in Fig. 1. This method is fast, but neither topology nor small-scale details are preserved. Later, Luebke [24] proposed a vertex clustering method based on the octree. Low [25] proposed changing the cell size according to the importance of vertices.

Figure 1.

Vertex clustering.

2.1.2 Region merging

Kalvin and Taylor [26] proposed a region merging algorithm by merging the approximate coplanar triangle facets into a plane. For a seed facet, if the vertices of its adjacent facet are within its bounded distance, the adjacent facet would be added to the seed facet, and this operation will be repeated iteratively until no superfacets appear. Then, the borders of superfacets are straightened, and the simplified results can be obtained by triangulating the area of these superfacet regions. This process is shown in Fig. 2. The region merging algorithm holds the user-specified error well and does not alter the topology of the mesh. However, holes appear in some superfacets.

Figure 2.

Region merging. (a) The original mesh. (b) Merge facets into superfaces. (c) Straighten borders. (d) Re-triangulate.

2.1.3 Geometric element decimation

Schroeder [27] proposed the vertex decimation algorithm, which successively removes vertices and generates a hierarchy of different levels of detail (LOD) in the process of simplification. It is efficient in time and space; however, the surface of the simplified mesh is very rough. Hoppe [28] defined an energy function to measure the quality of each simplified mesh and proposed the edge collapse operation, as shown in Fig. 3. The selection of edges is driven by an optimization process of the energy function. Later, Hoppe [29] proposed the progressive mesh, which provides multiresolution management, mesh compression, and enhances computational efficiency.

Figure 3.

Collapse the edge $e$ , its two related points $v_{1}$ , $v_{2}$ and two adjacent facets $f_{1}$ , $f_{2}$ are collapsed to the newly generated point $\overline{v}$ , and the edges related to $v_{1}$ , $v_{2}$ will be mapped to point $\overline{v}$ .

Based on the edge collapse operation, Garland and Heckbert [6] proposed the QEM to efficiently calculate the collapsing cost. Hanmann [30] proposed a triangle collapse algorithm based on calculating the curvature of triangles.

2.2 QEM mesh simplification algorithm

QEM algorithm [6] uses iterative contractions of vertex pairs to simplify 3D mesh models. The order of edge collapse depends on the error, which quantifies the distance from the point to the facets, in which the error of point $v$ is defined as the quadratic sum of the distance from point $v$ to the plane set associated with $v$ , which can be calculated by Eq. (1).

$\displaystyle\triangle(v)=\sum_{p\in\textit{plane}(v)}(p^{T}v)^{2}=\sum_{p\in% \textit{plane}(v)}v^{T}(pp^{T})v=v^{T}\left(\sum_{p\in\textit{plane}(v)}K_{p}% \right)v$ (1)

where $\textit{plane}(v)$ represents a collection of all triangle planes containing the vertex $v$ , and $p={(a,b,c,d)}^{T}$ denotes the plane equation of each triangle in $\textit{plane}(v)$ , where $ax+by+cz+d=0$ and $a^{2}+b^{2}+c^{2}=1$ .

$K_{p}$ represents the fundamental error quadric matrix of the plane $p$ , as shown in Eq. (2).

$\displaystyle K_{p}=pp^{T}=\left[\begin{array}[]{llll}a^{2}&ab&ac&ad\\ ab&b^{2}&bc&bd\\ ac&bc&c^{2}&cd\\ ad&bd&cd&d^{2}\\ \end{array}\right]$ (2)

Figure 4.

Compute the position of $\overline{v}$ , where $Q_{v_{1}}=K_{p_{11}}+K_{p_{12}}+\linebreak K_{p_{13}}+K_{p_{14}}+K_{f_{1}}+K_{% f_{2}}$ , $Q_{v_{2}}=K_{p_{21}}+K_{p_{22}}+K_{p_{23}}+\linebreak K_{p_{24}}+K_{f_{1}}+K_{% f_{2}}$ .

Assume $Q_{v}=\sum_{p\in\textit{plane}(v)}K_{p}$ is the quadric error matrix of $v$ . For a given contraction ( $v_{1},v_{2}$ ) $\rightarrow\overline{v}$ , as shown in Fig. 4, the quadric error matrix of point $\overline{v}$ can be calculated by Eq. (3).

$\displaystyle Q_{\overline{v}}=Q_{v_{1}}+Q_{v_{2}}=\left[\begin{array}[]{cccc}% q_{11}&q_{12}&q_{13}&q_{14}\\ q_{21}&q_{22}&q_{23}&q_{24}\\ q_{31}&q_{32}&q_{33}&q_{34}\\ q_{41}&q_{42}&q_{43}&q_{44}\\ \end{array}\right]$ (3)

The quadric error of point $\overline{v}$ can be calculated by Eq. (4).

$\displaystyle\triangle(\overline{v})=\overline{v}^{T}(Q_{v_{1}}+Q_{v_{2}})% \overline{v}$ (4)

The best position of the new vertex $\overline{v}$ can be obtained by making $\triangle(\overline{v})$ reach the local minimum. If $Q_{\overline{v}}$ is invertible, the optimal position of $\overline{v}$ can be calculated by Eq. (5).

$\displaystyle\overline{v}={\left|\begin{array}[]{cccc}q_{11}&q_{12}&q_{13}&q_{% 14}\\ q_{21}&q_{22}&q_{23}&q_{24}\\ q_{31}&q_{32}&q_{33}&q_{34}\\ 0&0&0&0\\ \end{array}\right|}^{-1}\left|\begin{array}[]{c}0\\ 0\\ 0\\ 1\\ \end{array}\right|$ (5)

Otherwise, the position of $\overline{v}$ is chosen from $v_{1}$ , $v_{2}$ or $(v_{1}+v_{2})/2$ , and the position that has the smallest error is selected.

2.3 Improved mesh simplification algorithms

Although the QEM algorithm can simplify complex mesh models efficiently, it is difficult to measure an accurate geometric error for the high curvature and thin region with a small distance error metric, which would consequently lead to the loss of geometric features. Many algorithms have been proposed to solve this drawback of QEM.

Kim et al. [8] proposed utilizing the discrete curvature norm to measure geometric error and to better preserve the shape of the original mesh model. In addition, Kim et al. [31] proposed a new error metric based on the theory of local differential geometry, which is defined by unifying a distance error metric with the first and second-order discrete differentials to construct the discrete curvature error metrics.

To maintain the basic skeleton of 3D mesh models, Li et al. [32] proposed an improved edge collapse that takes the texture into consideration and makes use of the Canny operator to calculate the borders.

Wang et al. [7] proposed utilizing the square of volume variation as the error metric, and embedded a new normal constraint factor of triangles into the edge-collapse error matrix, which can adaptively control the density of the simplified mesh and maintain more geometric features of the original mesh models.

Tang et al. [33] introduced Gauss curvature to the QEM algorithm as a simplifying factor to preserve the significant characteristics of 3D mesh models. In this algorithm, the Gauss curvature threshold is computed first, and the edges with Gauss curvatures lower than the threshold are selected to collapse.

To avoid deleting the characteristic of the boundary, Mao et al. [34] proposed utilizing the mean quadratic error rather than the cumulative error as the collapsing cost, so that the subtle features would be preserved.

All the above algorithms aim to maintain the characteristics of 3D mesh models, but they do not comprehensively consider approximation error and feature preservation. Moreover, the global approximation error is not taken into consideration, so they cannot solve the optimal mesh simplification problem.

2.4 Edge splitting operation

Edge splitting is a typical operation in Delaunay tri- angulation as shown in Fig. 5. Dyer et al. [35] defined the non-Delaunay edges as the edges where the sum of two opposite angles is greater than $\pi$ , and proposed an algorithm to convert an arbitrary manifold triangle mesh to a Delaunay mesh by recursively splitting non-Delaunay edges.

Figure 5.

Edge splitting. For the non-Delaunay edge $e$ , split $e$ at a point $s$ which is the closest to the midpoint of edge $e$ , and connect the two opposite points $a$ , $b$ with $s$ . In this way, edge $e$ has been changed to two Delaunay edges. However, the other four remaining edges may become non-Delaunay edges because of the splitting point $s$ .

Liu et al. [36] proposed a method to compute the optimal position for the splitting point. As shown in Fig. 6, Liu et al. considered a butterfly-shaped local region of a non-Delaunay edge, and defined five intervals $I_{i}\in e,(i=0,\ldots,4)$ . Depending on the geometric structure of triangle $t_{i}$ and the position of edge $e$ , the interval $I_{0}$ is always non-empty, while the other intervals $I_{i},(i=1,\ldots,4)$ , may be empty.

Splitting edge $e$ at point $s\in I_{0}$ would produce two edges $(a,s)$ and $(s,b)$ . According to the empty circle characteristic of Delaunay triangulation, edges $(a,s)$ and $(s,b)$ are locally Delaunay. In addition, splitting edge $e$ at point $s\in I_{i},(i=1,\ldots,4)$ would make edge $e_{i}$ locally Delaunay. Therefore, to produce the maximal number of Delaunay edges by splitting $e$ at $s$ , an interval $I_{s}\in I_{0}$ needs to be found, which maximizes the number of intersections between $I_{s}$ and ${I_{1},\ldots,I_{4}}$ . Liu et al. [36] proposed constructing a set of candidate samples and finding the appropriate splitting point $s$ from them. In this way, Liu’s method constructs the Delaunay mesh model by adding significantly fewer splitting points than Dyer’s algorithm, and it also runs two times faster.

Figure 6.

The local geometry of a non-Delaunay edge $e$ . (a) The butterfly-shaped local region of $e$ . (b) $C_{\textit{adc}}$ (resp. $C_{\textit{bdc}}$ ) is the circumferential circle of $\triangle_{\textit{adc}}$ (resp. $\triangle_{\textit{bdc}}$ ). The interval $I_{0}$ is the intersection of $C_{\textit{adc}}$ , $C_{\textit{bdc}}$ and $e$ , defined as $I_{0}\triangleq C_{\textit{adc}}\cap C_{\textit{bdc}}\cap e$ . (c)–(f) $C_{i},(i=1,\ldots,4)$ is the circumferential circle of triangle $t_{i}$ . Interval $I_{i},(i=1,\ldots,4)$ is the difference set of circle $C_{i}$ and edge $e$ , defined as interval $I_{i}\triangleq e\setminus(e\cap C_{i})$ .

Liu et al. [37] proposed a Delaunay mesh simplification method, which abstracts the simplification process using a 2D Cartesian grid model and utilizes DE to compute a low-cost path. Liu’s work focuses on the optimal Delaunay mesh simplification problem.

In the previous mesh simplification algorithms, the vertices and facets are only deleted without opportunity for improvement. Besides, the above algorithms do not solve the problem of long and narrow triangles. The edge splitting operation can be regarded as the inverse operation of edge collapse. In this paper, we utilize the edge splitting operation to undo the edge collapse operation. We propose a hybrid mesh simplification approach that combines both the edge collapse and splitting operation, as shown in the following section.

3. The proposed mesh simplification method

To solve the above mentioned drawbacks of the QEM, we propose a new hybrid mesh simplification method that combines the edge collapse operation and edge splitting operation.

3.1 The feature-preservation edge collapse operation

The Gauss curvature can reflect the bending degree, and the Gauss curvature of the uneven area and the feature edge is large. Kim [38] proposed a method to estimate the Gauss curvature of the inner vertex and the boundary vertex in discrete 3D mesh models, as shown in Fig. 7.

Figure 7.

Gauss curvature of the inner vertex $v$ , (a) is the inner vertex, (b) is the boundary vertex.

The Gauss curvature calculation formulas of the inner vertex and the boundary vertex are shown in Eqs (6) and (7), respectively.

$\displaystyle C(v)=\frac{2\pi-\sum_{i=1}^{N}\theta_{i}}{\frac{1}{3}S_{\sum}(v)}$ (6) $\displaystyle C(v)=\frac{\pi-\sum_{i=1}^{N}\theta_{i}}{\frac{1}{3}S_{\sum}(v)}$ (7)

where $N$ is the number of adjacent triangles, $S_{\sum}(v)$ is the sum of each adjacent triangles’ area, and $\theta_{i}$ is the inner angle of triangle $f_{i}$ .

The Gauss curvature of an edge is related to the Gauss curvature of the points in the edge [33]. For edge $e$ , which contains two points, $v_{1}$ and $v_{2}$ , its Gauss curvature can be calculated with Eq. (8).

$\displaystyle C(e)=|C(v_{1})|\cdot\omega_{1}+|C(v_{2})|\cdot\omega_{2}$ (8)

where $C(v_{1})$ and $C(v_{2})$ is the Gauss curvature of point $v_{1}$ and $v_{2}$ respectively, and $\omega_{i}$ is weight coefficient, which can be calculated as Eq. (9):

$\displaystyle\omega_{i}=\frac{S_{\sum}(v_{i})}{S_{\sum}(v_{1})+S_{\sum}(v_{2})}$ (9)

where $S_{\sum}(v_{i})$ is the area sum of the $v_{i}$ ’s surrounding triangles, as shown in Fig. 8.

Figure 8.

Gauss curvature of the edge $e$ . The region with blue dotted lines indicates the surrounding triangles of $v_{1}$ , and we denote its area as $S_{\sum}(v_{1})$ . While the region with red dotted lines indicates the surround triangles of $v_{2}$ , and we denote its area as $S_{\sum}(v_{2})$ .

The Quadric error of an edge can measure the approximation error of collapsing it. In each edge collapsing operation, we collapse the edge with the minimum Quadric error to obtain the best approximation result. However, we do not want to collapse the edges with significant features even if they have a small Quadric error.

To solve this problem, we propose a new edge collapsing operation based on adding the Gauss curvature into the collapsing cost to preserve the feature edges. The new collapsing cost is shown in Eq. (10).

$\displaystyle\textit{Cost}(e)=C(e)\cdot w+Q(e)$ (10)

where the weight $w$ is utilized to balance the Gauss curvature $C(e)$ and the Quadric error $Q(e)$ .

The overemphasis on the Gauss curvature will increase the approximation error. To reduce the approximation error as much as possible and retain the feature edges simultaneously, we propose to set the Gauss curvature two orders of magnitude lower than the Quadric error, and the weight can be calculated with Eq. (11). Therefore, only the edges with very large curvature would be retained without being collapsed.

$\displaystyle w=\frac{0.01\cdot Q_{\textit{avg}}}{C_{\textit{avg}}}$ (11)

where $Q_{\textit{avg}}=\frac{\sum_{i=1}^{n}Q(e)}{n}$ is the average Quadric error of all edges, and $C_{\textit{avg}}=\frac{\sum_{i=1}^{n}C(e)}{n}$ is the average Gauss curvature of all edges.

We sort all the edges into priority queue, $\textit{Queue}_{1}$ , from least to greatest according to their collapsing cost. In each edge collapsing operation, the edge $e_{\min}$ with the smallest collapsing cost would be chosen to collapse, and $\textit{Queue}_{1}$ will be locally updated to reflect the local geometry change around $e_{\min}$ , as shown in Fig. 9.

Figure 9.

After edge $e_{\min}$ is collapsed, only the order of its related edges $e_{3}$ ’, $e_{5}$ ’, $e_{6}$ ’, $e_{8}$ ’, $e_{9}$ ’ will be changed in sequence $\textit{Queue}_{1}$ , and the other edges will remain unchanged.

3.2 The edge splitting operation

In this paper, for irregular edges, we utilize the sum of the cotangent of their opposite angles to measure their irregularity degree.

Figure 10.

The irregularity degree of the edge. Edge $e$ is an irregular edge, $\alpha_{1}$ and $\alpha_{2}$ are opposite angles of it.

As shown in Fig. 10, for edge $e$ , its irregularity can be calculated by Eq. (12).

$\displaystyle I(e)=\textit{cot}(\alpha_{1})+\textit{cot}(\alpha_{2})$ (12)

If edge $e$ is more irregular, the sum of its opposite angles will be larger, and $I(e)$ will be smaller. To eliminate the irregular edges, we introduce the edge splitting operation into the mesh simplification process.

As described in Section 2.4, some original Delaunay edges do not satisfy the Delaunay conditions because of the edge splitting operation and require more times of edge splitting operation to settle. Therefore, selecting an appropriate splitting point is important. In this paper, we utilize Liu’s method [36] to select the appropriate splitting points.

First, we sort the edges into priority queue, $\textit{Queue}_{2}$ , from least to greatest according to their irregularity $I(e)$ . Then, in each edge splitting operation, the edge $e_{\min}$ with the minimum $I(e)$ would be chosen for splitting. Then, the mesh and the neighboring edges of $e_{\min}$ in $\textit{Queue}_{2}$ are updated.

3.3 The combination of edge collapse operation and edge splitting operation

For ordinary 3D mesh simplification problems, the ultimate goal is to obtain a simplified mesh model with a small approximation error, good geometric feature preservation, and few long and narrow triangles. To meet the above requirements simultaneously, in this paper, we combine the edge splitting operation with the edge collapse operation.

First, we conduct a preliminary experiment to verify the effect of introducing the edge splitting operation. We set up several combinations of edge splitting operations and edge collapse operations randomly, and carry out the operation sequences to mesh ‘Rabbit’ (simplify 100 facets of it), as shown in Fig. 11.

Figure 11.

The simplification process of the mesh model ‘Rabbit’. The horizontal-axis represents the number of operations, while the vertical-axis represents the number of facets in the mesh model. The upward edges represent applying the edge splitting operation to the mesh, while the downward edges represent applying the edge collapse operation to mesh. For example, the operation sequence of the yellow line is (3, 37, 20, 36), which means applying 3 times of edge splitting operation, 37 times of edge collapse operation, 20 times of edge splitting operation, and 36 times of edge collapse operation to mesh ‘Rabbit’ in proper order. The final obtained simplified mesh model has an approximation error as 0.32%.

From Fig. 11, we can observe that the proposed ‘undo/redo’ mechanism can indeed reduce the approximation error; however, there is no regularity between the combination method and the approximation error. Therefore, it is impossible to manually find the best combination that leads to the minimum approximation error among the infinite combinations of operation sequences.

Recently, meta-heuristic algorithms have been widely studied to solve global optimization problems [39, 40, 41], and the use of optimization algorithms could bring new solutions for certain complex problems [42, 43, 44].

To search for the best operation sequence combination from the infinite combinations of sequences, we model the proposed mesh simplification process as an optimization model, which will be discussed in the following section.

4. An optimization method for mesh simplification

To facilitate reading, we list the main notations used in this section in Table 1.

Table 1
Main notation in Section 4

$D(,)$	Hausdorff distance
$M$	The original mesh model
$M^{*}$	The optimal simplified mesh model
$n$	The amount of facets in $M$
$m$	The amount of simplified facets
$E_{\textit{split}_{i}}$	Executing the edge splitting operation $\textit{split}_{i}$ times
$E_{\textit{collapse}_{i}}$	Executing the edge collapse operation $\textit{collapse}_{i}$
	times
$d$	The length of the sequence
$S$	The operation sequence
$S^{*}$	The optimum combination sequence
$\vec{X}\in R^{d}$	Real vector
$S(\vec{X})\in R^{d}$	Sequence corresponding to $\vec{X}$
$M_{S}$	The simplified mesh obtained by applying $S$ to $M$
$M_{S(\vec{X})}$	The simplified mesh obtained by applying $S(\vec{X})$
	to $M$
$f(\vec{X})$	Objective function
$\vec{X}(t)$	$t$ -th population
$\vec{X}_{j}(t)$	$j$ -th agent of $\vec{X}(t)$
$\vec{X}^{*}(t)$	The optimum position obtained in $t$ -th iteration
$N_{p}$	Polulation size
$\textit{rand}[0,1]$	Random number between 0 and 1

4.1 Problem statement

In mesh simplification problems, the approximation error could quantitatively measure the difference between the simplified mesh model and the original mesh model. In this paper, we utilize the Hausdorff distance to measure the approximation error between simplified mesh model $M^{\prime}$ and original mesh model $M$ , which is shown in Eq. (13).

$\displaystyle D(M,M^{\prime})=\max\{\max\limits_{p\in M}d(p,M^{\prime}),\max% \limits_{p^{\prime}\in M^{\prime}}d(p^{\prime},M)\}$ (13)

where $d(p,M^{\prime})=\min\limits_{p^{\prime}\in M^{\prime}}d(p,p^{\prime})$ represents the shortest distance from point $p$ to mesh $M^{\prime}$ , and $d(p,p^{\prime})$ is the Euclidean distance between points $p$ and $p^{\prime}$ .

Our problem is a minimization problem: for the given 3D mesh model $M$ with $n$ facets and the user-specified target number of simplified facets $m$ ( $m<n$ ), we search for the optimal simplified mesh $M^{*}$ (with ( $n-m$ ) facets) that has the minimum Hausdorff distance, as shown in Eq. (14).

$\displaystyle M^{*}=\mathop{\arg\min}_{M^{\prime}}D(M,M^{\prime})$ (14)

4.2 Solution space

In the proposed ‘undo/redo’ mechanism, we alternate the edge collapse operation sequence and edge splitting operation sequence to continually eliminate the long and narrow triangles over time. In this way, a $d$ -dimension operation sequence $S$ can be formed in Eq. (15).

$\displaystyle S=(E_{\textit{split}_{1}},E_{\textit{collapse}_{1}},E_{\textit{% split}_{2}},E_{\textit{collapse}_{2}},\ldots,E_{\textit{split}_{1/2d}},E_{% \textit{collapse}_{1/2d}})$ (15)

where $E_{\textit{split}_{i}}$ represents executing edge splitting operation $\textit{split}_{i}$ times to $M$ , and $E_{\textit{collapse}_{i}}$ represents executing edge collapse operation $\textit{collapse}_{i}$ times. According to the experimental process, we set $d$ as 30.

The solution space $\mathbb{S}$ is composed of the possible combinations of splitting operation sequences and collapse operation sequences. For any sequence $S\in\mathbb{S}$ , we denote $M_{S}$ as the simplified mesh obtained by applying $S$ to $M$ . The optimization objective of searching the optimum simplified mesh model with the minimum Hausdorff distance is equivalent to searching for the optimum operation sequence combination which could lead the simplified mesh with the minimum Hausdorff distance, as shown in Eq. (16):

$\displaystyle M_{S^{*}}=\mathop{\arg\min}_{S\in\mathbb{S}}D(M,M_{S})$ (16)

4.3 The proposed optimized mesh simplification approach

In the optimization algorithms, the solutions are all valued in the real field. Therefore, for the elements in the real vector $\vec{X}\in R^{d}$ , we round them down to the closest integers and obtain the corresponding operation sequence $S(\vec{X})$ (for example, $\vec{X}=$ (28.14, 33.97, 37.30…), and $S(\vec{X})=$ (28, 34, 37…)). In this way, the optimization objective can be specifically expressed as follows:

Let $f(\vec{X}):\Omega\in R^{d}\rightarrow R$ be a real-valued objective function, where $\vec{X}=(x_{1},x_{2},\ldots,x_{d})$ the variable, $x_{i}\in R$ , and the search domain $\Omega$ is non-empty and bounded in $R^{d}$ . The fitness function is shown in Eq. (17):

$\displaystyle f(\vec{X})=D(M,M_{S(\vec{X})}),\vec{X}\in R^{d}_{\geqslant 0}$ (17)

where $M_{S(\vec{X})}$ denotes the obtained mesh by applying the operation sequence $S(\vec{X})$ to $M$ .

To improve the algorithm’s efficiency, we apply the following constraints.

First, because the solutions are generated randomly, it is very likely that the number of edge splitting occurrences exceeds the number of edge collapse occurrences, and the simplification goal cannot be achieved. To avoid this situation in advance, we set a prejudgment to check whether the sequence $S(\vec{X})=(\ldots E_{\textit{split}_{i}},E_{\textit{collapse}_{i}}\ldots)$ satisfies the simplification condition, as shown in Eq. (1).

$\displaystyle(E_{\textit{collapse}_{1}}+\ldots+E_{\textit{collapse}_{1/2d}})-$ $\displaystyle(E_{\textit{split}_{1}}+\ldots+E_{\textit{split}_{1/2d}})% \geqslant m/2$ (18)

Only if $S(\vec{X})$ satisfies the simplification condition (the final number of simplified facets reaches $m$ ), it will be applied to $M$ ; otherwise, it will be skipped, and $f(\vec{X})=+\infty$ .

Second, in the process of executing the operation sequences, if the simplification goal is achieved, the follow-up operations will be skipped.

Third, if all the edges are not irregular edges (all the edges satisfy the Delaunay conditions), the remaining edge splitting operations are useless and unexpected, and they are skipped.

The optimization of the operation sequences of edge splitting and edge collapse is performed under the above constraints, which prevents the program from executing the operation sequences that do not satisfy the simplification condition, avoids unnecessary splitting and collapse operations in the process of program execution, and improves the efficiency.

4.4 The proposed swarm intelligence algorithm, WOA-DE

To solve the complex problems in real life, nature-inspired algorithms have been introduced, such as evolutionary process-based [45, 46], animal behavior-based [47, 48, 49], swarm intelligence-based [50, 51, 52], and memetic-based [53, 54] algorithms. They are very important in solving many large-scale and complex problems [55, 56, 57].

Among them, the Whale Optimization Algorithm (WOA) is a new meta-heuristic algorithm [22]. One of the main drawbacks of WOA is that it easily falls into a local optimum. To overcome this limitation, in this paper, WOA is hybridized with Differential Evolution (DE), which has good exploration ability. In the proposed method, we integrate the exploration mechanisms of DE with the exploitation mechanisms of WOA.

4.4.1 WOA

WOA simulates the social behavior of humpback whales, which has the advantages of simple concepts, easy implementation, few parameters, and no gradient information. Moreover, many papers and experiments have shown that WOA is better than some state-of-the-art algorithms in accuracy and stability [58, 22, 59]. However, WOA also has the disadvantages of low accuracy, slow convergence speed and easily falling into a local optimum.

Many papers have proposed improvements to the performance of WOA. Kaur and Arora [60] proposed chaotic WOA (CWOA) which utilized chaos theory to tune the main parameters of WOA to enhance its convergence speed. Ling et al. [61] proposed Lévy flight trajectory-based WOA (LWOA), which employed the Lévy flight trajectory to increase the diversity of the population. Bozorgi et al. [62] proposed improved WOA (IWOA and IWOA ${}^{+}$ ) by hybridizing the WOA’s operators with DE’s mutation operator. A self-adaption threshold $\lambda$ is set in IWOA. In the exploration part, when $\textit{rand}<\lambda$ , the mutation operator of DE will be executed; otherwise, the searching for prey operation of WOA will be executed. Based on this, IWOA ${}^{+}$ utilizes a new parameter to adaptively change the search mode (exploration or exploitation).

WOA searches the global optimum by encircling prey, spiral updating the position and searching for prey.

(1) Encircling prey ( $p<0.5$ and $|\vec{A}|>1$ )

The search agents update their positions towards the current best solution as shown in Eqs (19) and (20):

$\displaystyle\vec{D}=|\vec{C}\cdot\vec{X}^{*}(t)-\vec{X}(t)|$ (19) $\displaystyle\vec{X}(t+1)=\vec{X}^{*}(t)-\vec{A}\cdot\vec{D}$ (20)

where $\vec{X}(t)$ represents the position vector of agent in the $t$ -th iteration, and $\vec{X}^{*}(t)$ represents the best candidate solution in $t$ -th generation. The vector $\vec{A}$ and $\vec{C}$ can be calculated by Eqs (21) and (22):

$\displaystyle\vec{A}=2\vec{\alpha}\cdot\vec{r}-\vec{\alpha}$ (21) $\displaystyle\vec{C}=2\cdot\vec{r}$ (22)

where $\vec{r}$ is a random vector in $[0,1]$ , $\vec{\alpha}$ is linearly decreased from 2 to 0.

(2) Spiral updating position ( $p\geqslant 0.5$ )

Whales move upstream in a spiral position and spit out bubbles to prey. The spiral equation between the positions of the whales and prey is shown in Eq. (23).

$\displaystyle\vec{X}(t+1)=\vec{D^{\prime}}\cdot e^{bl}\cdot\textit{cos}(2\pi l% )+\vec{X}^{*}(t)$ (23)

where $\vec{D^{\prime}}=\vec{X^{*}}(t)-\vec{X}(t)$ represents the distance from an individual’s current position to the best individual, $b$ is a constant, and $l$ is a random number in $[-1,1]$ .

According to the habits of the whales, the probability of choosing the shrinking encircling mechanism or the spiral updating position during optimization is 50% ( $p$ is a random number in $[-1,1]$ ).

(3) Search for prey ( $|\vec{A}|>1$ )

Searching for prey is similar to encircling prey. The position of a search agent in the exploration phase is updated according to a randomly chosen search agent, which is shown in Eqs (24) and (25).

$\displaystyle\vec{D}=|\vec{C}\cdot\lx@stackrel{{\scriptstyle\longrightarrow}}{% {X_{\textit{rand}}}}-\vec{X}|$ (24) $\displaystyle\vec{X}(t+1)=\lx@stackrel{{\scriptstyle\longrightarrow}}{{X_{% \textit{rand}}}}-\vec{A}\cdot\vec{D}$ (25)

where $\lx@stackrel{{\scriptstyle\longrightarrow}}{{X_{\textit{rand}}}}$ is a random position vector chosen from the current population.

The pseudocode of WOA is shown in Algorithm 1.

[!htbp] Generate the initial population $X$

Calculate the fitness of each search agent in $X$

$X^{*}=$ the best search agent

$t<$ max iterations

$i=1$ to $N_{p}$

Update $a$ , $C$ , $A$ , $l$ , and $p$

$j=1$ to $n$ $p<0.5$ $|A|<1$

$D=|C\cdot X^{*}-X_{i}(t)|$ $X_{i,j}(t+1)=X_{j}^{*}-A\cdot D$

Select a random individual $X_{\textit{rand}}$

$D=|C\cdot X_{\textit{rand}}-X_{i}(t)|$

$X_{i,j}(t+1)=X_{\textit{rand,j}}-A\cdot D$

$D^{\prime}=|X^{*}-X_{i}(t)|$ $X_{i,j}(t+1)=D^{\prime}\cdot e^{bl}\cdot cos(2\pi l)+X^{*}_{j}$

Update $X^{*}$ if there is a better solution

$t=t+1$

WOA pseudocode

4.4.2 DE

DE is a population-based search algorithm [21] for optimizing multivariate real-valued functions. Due to its simplicity, ease of implementation, few parameters and lack of use of the function’s gradient, DE has been recognized as a highly effective tool for a wide range of optimization problems [63], including constrained [64], multi-objective [65], multi-modal and dynamic optimization [66] even with non-differentiable functions [67, 68, 69].

In addition, many researchers have proposed improvements to the DE algorithms in the following aspects: the initialization method [70], generation strategy [71], parameter control method [72], etc. Moreover, according to different problem types, it is necessary to design a specific optimization mode to improve the optimization performance of DE; many researchers have proposed solutions for this problem [73, 74, 75].

The canonical DE/rand/1/bin form of DE generates new individuals by performing mutation and crossover operations.

(1) Mutation

The new candidate solutions are generated by adding an agent with a scaled difference of two randomly selected agents. In the $t$ -th iteration, a mutative agent of $X^{\prime}_{i}(t)$ is generated in Eq. (26):

$\displaystyle X^{\prime}_{i}(t)=X_{r_{1}}(t)+F(X_{r_{2}}(t)-X_{r_{3}}(t))$ (26)

where $r_{1},r_{2},r_{3}$ are distinct random integers and not equal to $i$ , $F$ is a scalar factor in the range (0, 1).

(2) Crossover

A binomial crossover builds a trial agent $U_{i}(t)$ by copying the elements from either mutative agent $X^{\prime}_{i}(t)$ or original agent $X_{i}(t)$ :

$\displaystyle u_{i,j}(t)=\left\{\begin{array}[]{ll}x^{\prime}_{i,j}(t)&\text{% if }(\textit{rand}_{i,j}(t)[0,1]\leqslant\\ &C_{r}||j=j_{\textit{rand}})\\ x_{i,j}(t)&\text{otherwise}\\ \end{array}\right.$ (27)

where $C_{r}\in[0,1]$ is the crossover rate.

Generate the initial population $X$

Evaluate the fitness of each individual in $X$

$t<$ max iterations

i=1 to $N_{p}$

Select uniform randomly $r_{1}\neq r_{2}\neq r_{3}\neq i$

$j_{\textit{rand}}=\textit{rndint}(1,n)$

j=1 to $n$ $\textit{rndreal}_{j}[0,1]\leqslant C_{r}$ or $j=j_{\textit{rand}}$ $U_{i,j}(t)=X_{{r_{1}},j}(t)+F\dot{(}X_{{r_{2}},j}(t)-X_{{r_{3}},j}(t))$ $U_{i,j}(t)=X_{i,j}(t)$

calculate the fitness of $U_{i}(t)$

$U_{i}(t)$ is better than $X_{i}(t)$ Update individual $i$ , $X_{i}(t+1)=U_{i}(t)$

$U_{i}(t)$ is better than $X^{*}$ Update best individual $i$ , $X^{*}=U_{i}(t)$ $t=t+1$

DE pseudocode

(3) Selection

The selection operation chooses the better agent from the trial agent $U_{i}(t)$ and the original agent $X_{i}(t)$ as the agent of the next generation.

$\displaystyle X_{i}(t+1)=\left\{\begin{array}[]{ll}U_{i}(t)&\text{if }f(U_{i}(% t))<f(X_{i}(t))\\ X_{i}(t)&\text{otherwise}\\ \end{array}\right.$ (28)

The pseudocode of DE is shown in Algorithm 2.

4.4.3 The proposed WOA-DE

For a realistic problem, it cannot be expected that a metaheuristic black-box will suit all problems, and it is theoretically impossible to have ready-made off-the-shelf general & good solvers [76]. By modifying or combining memes, the new memes may be more durable and prone to propagation [77, 78].

Considering the probabilistic convergence and global optimality of DE [72], we utilize DE to improve the exploration ability of WOA. Compared with IWOA [62], our method is conceptually simpler; we directly replace the exploration phase of WOA with the mutate and crossover operations of DE and utilize the greedy selection operation of DE to select agents to enter the next generation.

The proposed mesh simplification is a high- dimensional problem, and each element of the solution will be rounded to an integer first. Therefore, the global search phase is more important for the proposed optimization problem. By replacing the exploration phase of WOA with DE, the proposed WOA-DE could balance the exploration and exploitation capabilities. The details of applying WOA-DE to mesh simplification problems are shown as follows.

(1) Initialize

The solutions $\vec{X}(0)=\{\vec{X}_{i}(0)\}^{N_{p}}_{i=1}$ are randomly initialized in bound space $\Omega$ , which is shown in Eq. (29).

$\displaystyle\Omega=\{\{x_{j}\}^{d}_{j=1}|0\leqslant x_{j}\leqslant m/2,x_{j}% \in R\}$ (29)

The initial population $\vec{X}(0)$ is generated uniformly and distributed on the closed interval $[0,m/2]$ , as shown in Eq. (4.4).

$\displaystyle x_{i,j}(0)=\textit{rand}[0,1]\cdot m/2$ $\displaystyle i=1,2,\ldots,N_{p},j=1,2,\ldots,d$ (30)

(2) Optimization

The optimization process includes the exploitation phase and exploration phase. In the exploitation phase, the agents are updated by the encircling prey and spiral updating position mechanisms of WOA, and in the exploration phase, the agents are updated by the mutation and crossover mechanisms of the canonical DE/rand/1/bin form of DE.

(3) Selection

Because the proposed mesh simplification problem is a minimization problem, the agent with the lowest objective value from the trial agent and the original agent is selected, and set to be the $i$ -th agent of the next generation in Eq. (31) :

$\displaystyle X_{i}(t+1)=\left\{\begin{array}[]{ll}U_{i}(t)&\text{if }f(U_{i}(% t))<f(X_{i}(t))\\ X_{i}(t)&\text{otherwise}\\ \end{array}\right.$ (31)

(4) Termination conditions

The algorithm will terminate when one of the following conditions is met: (1) the iteration number exceeds the user-specified max iterations; (2) the relative change of fitness $\frac{f(t)-f(t+1)}{f(t)}$ does not exceed threshold $\tau$ in consecutive $n_{c}$ iterations, where $f(t)$ is the minimum objective function value in $t$ -th generations. In our experiment, we use fixed parameters $n_{c}=5$ and $\tau=1.0e^{-4}$ .

The pseudocode of WOA-DE is shown in Algorithm 3.

[!htbp] Generate the initial population $X$

Calculate the fitness of each search agent in $X$ $X^{*}=$ the best search agent

$t<$ max iterations

$i=1$ to $N_{p}$ Select uniform randomly $r_{1}\neq r_{2}\neq r_{3}\neq i$

Update $a$ , $C$ , $A$ , $l$ and $p$

$j_{\textit{rand}}=\textit{rndint}(1,n)$

$j=1$ to $n$ $p<0.5$ $|A|<1$

$D=|C\cdot X^{*}-X_{i}(t)|$ $U_{i,j}(t)=X_{j}^{*}-A\cdot D$

$\textit{rndreal}_{j}[0,1]\leqslant C_{r}$ or $j=j_{\textit{rand}}$ $U_{i,j}(t)=X_{{r_{1}},j}(t)+F\dot{(}X_{{r_{2}},j}(t)-X_{{r_{3}},j}(t))$ $U_{i,j}(t)=X_{i,j}(t)$

$D^{\prime}=|X^{*}-X_{i}(t)|$ $U_{i,j}(t)=D^{\prime}\cdot e^{bl}\cdot\textit{cos}(2\pi l)+X^{*}_{j}$ calculate the fitness of $U_{i}(t)$

$U_{i}(t)$ is better than $X_{i}(t)$ Update individual $i$ , $X_{i}(t+1)=U_{i}(t)$

$U_{i}(t)$ is better than $X^{*}$ Update best individual $i$ , $X^{*}=U_{i}(t)$

$t=t+1$

WOA-DE pseudocode

Figure 12.

Feature preservation. Mesh (b) is the simplified model without Gauss curvature. Mesh (c) is the simplified model obtained by the QEM method. Mesh (d) is the simplified model obtained by Tang’s method. Mesh (e) is the simplified model obtained by Wang’s method. Mesh (f) is the simplified model obtained by Mao’s method. Mesh (g) is the simplified model obtained by our method. And their corresponding Gauss curvature distribution of vertices is shown in the second line, where the convex area is in red and the concave area is in green, and the color deepens along with the increasing of the absolute value of curvature.

5. Experimental results and discussions

We carried out the proposed approach on a wide range of 3D meshes, including mesh ‘Bunny’ from the Computer Graphics Laboratory of Stanford University, man-made meshes collected from the Thingi10K9 3D dataset [79], and some common and publicly available 3D models on the Internet.

We compare our approach with the QEM method [6], Tang’s method [33] (using the Gauss curvature as the threshold), Wang’s method [7] (using the square of the volume change as the collapsing cost) and Mao’s method [34] (using the mean quadratic error as the collapsing cost), and evaluate the results based on the following: geometric feature preservation, triangle quality, and approximation error.

5.1 Geometric feature preservation

The human visual system is sensitive to inflection points, sharp edges, and other geometric features. Therefore, the change in meaningful geometric features is also important for users when judging the quality of simplified 3D mesh models. Here, we utilize a standard manifold 3D mesh model ‘Rabbit’ as the example, which has a simple topological structure and clear visual features with only 902 facets. We simplify 300 facets of the mesh ‘Rabbit’, and the simplified results are shown in Fig. 12. We visualize the Gauss curvature of the vertices to show the features more intuitively.

Figure 12 shows that all methods maintain the overall mesh appearance. However, some of methods lose the details of the meaningful geometric feature ‘eye’. In the Gauss curvature distribution of mesh (b), the eye part is completely red, indicating that there is no concave part; compared with the original mesh, the details of ‘eye’ are lost. Although the approximation error of mesh (b) is minimal, we still believe that the error of mesh (b) is larger from the perspective of vision. Therefore, visual distortions are very important.

Table 2
Results and visual comparison

To preserve the geometric features, the proposed edge collapse operation adds Gauss curvature into the calculation of the collapsing cost. Figure 12g and n are the results of our method, and the introduction of Gauss curvature can indeed improve the feature preservation effect, especially for small-scale 3D models, because they have few faces and vertices, and because each edge may be the boundary, they are more difficult to simplify with feature preservation. Table 2 shows a visual comparison of the experimental results, which demonstrates that the proposed method can preserve geometric features well for both the small-scale mesh models and the large-scale mesh models.

Figure 13.

The triangle quality of four representative models, where the horizontal axis represents the range of $Q$ , and the vertical axis represents the proportion of triangles with quality in some range.

Figure 14.

The results of all the experiments.

Table 3

Comparison with state-of-art algorithms. $n$ is facets number in original mesh and $m$ is the number of simplified facts. Err and Err ${}^{*}$ are approximation errors and Err/Err ${}^{*}$ is the error ratio compared to our method

Mesh	$n$	$m$	QEM method		Tang’s method		Wang’s method		Mao’s method		Our method	Ranking of
			Err (%)	Err/Err ${}^{*}$	Err (%)	Err/Err ${}^{*}$	Err (%)	Err/Err ${}^{*}$	Err (%)	Err/Err ${}^{*}$	Err ${}^{*}$ (%)	our method
Chair	552	200	12.10	14.58	1.16	1.40	12.10	14.58	12.10	14.58	0.83	1
Human	694	100	0.32	1.33	0.34	1.42	0.53	2.22	0.48	1.99	0.24	1
Rabbit	902	300	0.98	1.11	1.16	1.32	1.46	1.65	1.27	1.44	0.88	1
Pig	1208	400	1.02	1.13	1.02	1.13	0.91	1.00	0.90	0.99	0.91	2
Cup	1500	600	0.41	1.11	0.55	1.49	0.84	2.23	0.65	1.74	0.37	1
Teddy	3192	1000	9.30	1.13	7.37	0.90	10.21	1.24	16.01	1.95	8.20	2
Dinosaur	4000	2000	75.75	1.27	76.61	1.29	96.34	1.62	81.33	1.37	59.53	1
Bones	4204	2500	7.25	1.30	8.18	1.46	10.92	1.95	8.87	1.58	5.60	1
Cow	5804	3000	0.77	3.35	0.33	1.43	0.66	2.00	0.77	2.25	0.23	1
Teapot	6320	3500	0.96	1.40	0.69	1.23	3.86	6.85	0.83	1.47	0.56	1
Kitten	49912	35000	5.94	1.22	5.21	1.07	14.05	2.90	7.37	1.52	4.85	1
Bunny	69662	40000	0.14	1.11	0.15	1.21	0.34	2.66	0.18	1.40	0.13	1
Plane	89381	60000	2.02	1.77	1.33	1.17	8.56	7.58	1.83	1.61	1.14	1
State of liberty	41062	20000	1.38	1.23	1.38	1.23	3.12	2.79	1.38	1.23	1.12	1

5.2 The quality of the triangles in the mesh

The long and narrow triangles will increase the numerical error and lower the rendering effect of the surface [80, 81]. In this paper, we combine the edge splitting operation to reduce the long and narrow triangles. The quality of the triangle can be calculated in Eq. (32).

$\displaystyle Q=\frac{4\sqrt{3}S}{l_{1}^{2}+l_{2}^{2}+l_{3}^{2}}$ (32)

where $S$ is the area of the triangle, and $l_{1}$ , $l_{2}$ and $l_{3}$ are the length of three edges of the triangle.

Here, we list the triangle quality of four representative meshes, the mesh ‘Bones’ (simplified 2500 facets), the mesh ‘Dinosaur’ (simplified 2000 facets), the mesh ‘Kitten’ (simplified 35000 facets), and the mesh ‘Bunny’ (simplified 40000 facets), which are shown in Fig. 13. We divide the triangles into different classes according to their quality $Q$ . In addition, we classify the triangles with $Q<$ 0.5 into a class and define them as low-quality triangles.

From Fig. 13, the simplified mesh models of our approach have more high-quality triangles, and fewer low-quality triangles than other methods. This shows that the proposed ‘undo/redo’ mechanism can indeed reduce the long and narrow triangles.

5.3 The approximation error

In this paper, we adopt the tool ‘Metro’ [82] to quickly compute the two-sided Hausdorff distance between the original mesh and the simplified mesh. Here, we list the comparison of the QEM algorithm, Tang’s method, Wang’s method, Mao’s method, and our method in terms of the approximation error, as shown in Table 3 and Fig. 14. According to the statistical ranking, our method ranks first for almost all cases.

Furthermore, we conduct experiments on meshes with varying target simplified facet numbers, and the four representative results are shown in Fig. 15. The experimental results show that our method consistently outperforms the other methods.

5.4 The performance of the proposed optimization algorithm

5.4.1 The effectiveness of the optimizer

In the proposed optimization problem, there is no concept of gradient or direction, so it is not feasible to approach the optimal solution manually. For this multidimensional and multimodal problem, we can only use the optimization algorithm to obtain the optimal solution. To verify the effectiveness of the optimizer, we continue the pre-experiment, in which we simplify the mesh ‘Rabbit’ using the proposed optimized mesh simplification algorithm. From Table 4, the result of the optimal operation sequence obtained by our method is much better than that of other random sequences, which proves the effectiveness of the optimizer.

Table 4
Comparison of optimal operation sequence and random operation sequences. $S_{1}=$ (0, 50) is sequence of QEM. $S_{2}$ to $S_{6}$ are random sequence, where $S_{2}=$ (26, 30, 20, 43, 9, 32), $S_{3}=$ (25, 39, 23, 33, 22, 4, 21, 41, 13, 37), $S_{4}=$ (21, 46, 22, 28, 5, 24), $S_{5}=$ (25, 75), $S_{6}=$ (3, 37, 20, 36). And $S^{*}=$ (0, 40, 10, 18, 20, 10, 0, 12) is the optimal operation sequence

Sequence	$S_{1}$	$S_{2}$	$S_{3}$	$S_{4}$	$S_{5}$	$S_{6}$	$S^{*}$
Err (%)	0.40	0.30	0.38	0.31	0.40	0.32	0.25

5.4.2 Comparison of optimization algorithms

Here, we conduct a simple experiment to test the performance of WOA-DE, in which we apply the proposed mesh simplification algorithm to several mesh models and utilize different optimization algorithms for optimization. The experimental results are shown in Table 5. Moreover, we list the convergence of different optimization algorithms, which are shown in Fig. 16. The performance of WOA-DE is better than that of DE and WOA.

Table 5
Comparison of errors of different optimization algorithms

Mesh	$n$	$m$	DE		WOA		WOA-DE
			Avg. (%)	Std.	Avg. (%)	Std.	Avg. (%)	Std.
Rabbit	902	300	0.9057	6.19e-5	0.9068	1.96e-4	0.8825	7.60e-5
Cow	5804	3000	0.2311	5.65e-6	0.2332	5.22e-6	0.2307	4.72e-6
Teapot	6320	3500	0.5889	3.73e-5	0.5920	6.72e-6	0.5670	4.40e-6
Kitten	49912	35000	4.8880	6.23e-4	4.8750	7.95e-4	4.8510	1.61e-4

Figure 15.

The approximation error plots of four representative models with different target numbers of simplified facets.

Figure 16.

Comparison of convergence of different optimization algorithms.

5.5 Time complexity

The computation time of our method can be calculated from two parts: the WOA-DE-based optimization process, and the specific mesh simplification process in each agent. For the WOA-DE, the computation time is dependent on the population size and iteration times. In each agent, we maintain two priority queues for edge splitting and edge collapse operations, which have a time complexity of $O(n\log n)$ . For the specific mesh simplification process, the computation time is proportional to the number of facets in the mesh model and the number of simplified facets. Because the proposed mesh simplification method utilizes the optimization algorithm, it is infeasible for real-time usage; however, it still has strong practicability for obtaining the optimal simplified mesh model.

5.6 Parameter setting

In the proposed WOA-DE algorithm, the parameters that need to be set manually are population size $N_{p}$ , crossover rate $C_{r}$ and mutation parameter $F$ .

$N_{p}$ : A larger group will increase the diversity but reduce the convergence rate. A smaller group can easily lead to the method falling into a local optimal. The running time is also linearly proportional to $N_{p}$ . To balance the population diversity and convergence rate, we set $N_{p}=100$ .

$F$ : A smaller $F$ will accelerate convergence, but it can easily lead to premature convergence. A larger $F$ will increase the possibility of the method jumping out of a local optimal solution; however, an $F$ that is too large will result in too much disturbance and low search efficiency.

$C_{r}$ : A lower $C_{r}$ will make the agents select more elements from the original agents in the crossover process, thereby lowering population diversity.

According to [83, 72], we tested the influence of different parameters on the approximation error and set $C_{r}$ as 0.8, 0.9, and 1 and $F$ as 0.5, 0.6, 0.7, 0.8, and 0.9. According to the experimental results, we set $C_{r}=$ 0.8 and $F=$ 0.5 to increase population diversity and avoid too much interference.

6. Conclusions and future work

This paper presents an optimized mesh simplification approach with three advantages: (1) a new edge collapsing operation that can preserve the geometric features in the process of edge collapsing; (2) an ‘undo/redo’ mechanism that can improve the quality of the triangles and reduce the approximation error; and (3) a WOA-DE based optimization method that can effectively compute the optimal simplified mesh model. Numerous experiments confirm the proposed idea.

In the future, we will extend the research with: First, GPUs can be used to accelerate the approach. Second, the proposed algorithm can be extended to multimedia information. Third, the new generation of AI can be applied to process 3D models.

Footnotes

Acknowledgments

This work is supported by the National Key R&D Program of China under Grant No 2017YFB0503004, the Science and Technology Major Project of Hubei Province (Next-Generation AI Technologies) under Grant No 2019AEA170 and Translational Medicine and Interdisciplinary Research Joint Fund of Zhongnan Hospital of Wuhan University under Grant No ZNJC201917.

References

Regli

Shokoufandeh

Bespalov

. Multi-scale segmentation and partial matching 3D models. Google Patents; 2011. US Patent 8,015,125.

Kato

Ushiku

Harada

. Neural 3d mesh renderer. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition; 2018. pp. 3907–3916.

Chen

Zhu

Cohen-Or

Shamir

. Extracting 3D objects from photographs using 3-sweep. Communications of the ACM. 2016; 59(12): 121–129.

Zhang

. Service-oriented feature-based data exchange for cloud-based design and manufacturing. IEEE Transactions on Services Computing. 2018; 11(2): 341–353.

Clark

. Hierarchical geometric models for visible-surface algorithms. Acm Siggraph Computer Graphics. 10(2): 267–267.

Garland

Heckbert

. Surface simplification using quadric error metrics. In: Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. ACM Press/Addison-Wesley Publishing Co.; 1997. pp. 209–216.

Wang

Zhang

. New mesh simplification algorithm based on edge collapse. Computer Engineering & Applications. 2013.

Kim

Levin

. Surface simplification using a discrete curvature norm. Computers & Graphics. 2002; 26(5): 657–663.

Siyan

Wenhe

Hao

. Triangle Regularity Measurement Based on Cosine Sum of Inner Angles and Mesh Optimization [J]. Mechanical Science and Technology. 2007; 4.

10.

Siddique

Adeli

. Spiral dynamics algorithm. International Journal on Artificial Intelligence Tools. 2014; 23(6): 1430001.

11.

Siddique

Adeli

. Harmony search algorithm and its variants. International Journal of Pattern Recognition and Artificial Intelligence. 2015; 29(8): 1539001.

12.

Siddique

Adeli

. Water drop algorithms. International Journal on Artificial Intelligence Tools. 2014; 23(6): 1430002.

13.

Yan

Zhang

Xie

. An optimizer ensemble algorithm and its application to image registration. Integrated Computer-Aided Engineering. 2019; 26(4): 311–327.

14.

Sarma

Adeli

. Fuzzy discrete multicriteria cost optimization of steel structures. Journal of Structural Engineering. 2000; 126(11): 1339–1347.

15.

Chen

Zhang

. A full migration BBO algorithm with enhanced population quality bounds for multimodal biomedical image registration. Applied Soft Computing. 2020; 93: 106335. Available from: https://www-sciencedirect-com.web.bisu.edu.cn/science/article/pii/S1568494620302751.

16.

Zhang

Jiang

. Experimental investigation and multi-objective optimization approach for low-carbon milling operation of aluminum. Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science. 2017; 231(15): 2753–2772.

17.

Zawidzki

Jankowski

. Multiobjective optimization of modular structures: Weight versus geometric versatility in a Truss-Z system. Computer-Aided Civil and Infrastructure Engineering. 2019; 34(11): 1026–1040.

18.

Soto

Adeli

. Many-objective control optimization of high-rise building structures using replicator dynamics and neural dynamics model. Structural and Multidisciplinary Optimization. 2017; 56(6): 1521–1537.

19.

Valenzuela

Jiang

Carrillo

Rojas

. Multi-objective genetic algorithms to find most relevant volumes of the brain related to alzheimer’s disease and mild cognitive impairment. International Journal of Neural Systems. 2018; 28(9): 1850022.

20.

Shen

. Shape generation of grid structures by inverse hanging method coupled with multiobjective optimization. Computer-Aided Civil and Infrastructure Engineering. 2018; 33(6): 498–509.

21.

Storn

Price

. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization. 1997; 11(4): 341–359.

22.

Mirjalili

Lewis

. The whale optimization algorithm. Advances in Engineering Software. 2016; 95: 51–67.

23.

Rossignac

Borrel

. Multi-resolution 3D approximations for rendering complex scenes. In: Modeling in Computer Graphics. Springer; 1993. pp. 455–465.

24.

Luebke

Erikson

. View-dependent simplification of arbitrary polygonal environments. In: Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques; 1997. pp. 199–208.

25.

Low

Tan

. Model simplification using vertex-clustering. In: Proceedings of the 1997 Symposium on Interactive 3D Graphics; 1997. pp. 75–ff.

26.

Kalvin

Taylor

. Superfaces: Polygonal mesh simplification with bounded error. IEEE Computer Graphics and Applications. 1996; 16(3): 64–77.

27.

Schroeder

Zarge

Lorensen

. Decimation of triangle meshes. In: Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques; 1992. pp. 65–70.

28.

Hoppe

Derose

Duchamp

Mcdonald

Stuetzle

. Mesh optimization. In: SIGGRAPH’93; 1993.

29.

Hoppe

. Progressive meshes. In: Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques; 1996. pp. 99–108.

30.

Hamann

. A data reduction scheme for triangulated surfaces. Computer Aided Geometric Design. 1994; 11(2): 197–214.

31.

Kim

. Discrete differential error metric for surface simplification. In: 10th Pacific Conference on Computer Graphics and Applications, 2002. Proceedings. IEEE; 2002. pp. 276–283.

32.

Wan

Lei

. Using Canny algorithm in QEM simplification for textured 3D models. In: Iet International Communication Conference on Wireless Mobile & Computing; 2012.

33.

Tang

Zhang

. Edge-Collapse Mesh Simplification Method Based on Gauss Curvature. In: 2011 International Conference on Internet of Things and 4th International Conference on Cyber, Physical and Social Computing. IEEE; 2011. pp. 660–662.

34.

Mao

Yang

Zhu

Yang

. A new mesh simplification algorithm based on quadric error metric. In: 2015 IEEE 5th International Conference on Consumer Electronics-Berlin (ICCE-Berlin). IEEE; 2015. pp. 463–466.

35.

Dyer

Zhang

Möller

. Delaunay mesh construction. In: Proceedings of the Fifth Eurographics Symposium on Geometry Processing, Barcelona, Spain, July 4–6, 2007; 2007. pp. 273–282.

36.

Liu

Fan

. Efficient construction and simplification of Delaunay meshes. ACM Transactions on Graphics. 2015; 34(6): 174.

37.

Liu

. Delaunay mesh simplification with differential evolution. In: SIGGRAPH Asia 2018 Technical Papers. ACM; 2018. pp. 263.

38.

Kim

Jeong

Kim

. LOD generation with discrete curvature error metric. In: Proceedings of Korea Israel Bi-National Conference; 1999. pp. 97–104.

39.

Mencía

Sierra

Mencía

Varela

. Evolutionary one-machine scheduling in the context of electric vehicles charging. Integrated Computer-Aided Engineering. 2019; 26(1): 49–63.

40.

Kociecki

Adeli

. Two-phase genetic algorithm for size optimization of free-form steel space-frame roof structures. Journal of Constructional Steel Research. 2013; 90: 283–296.

41.

Palacios

González-Rodríguez

Vela

Puente

. Satisfying flexible due dates in fuzzy job shop by means of hybrid evolutionary algorithms. Integrated Computer-Aided Engineering. 2019; 26(1): 65–84.

42.

Chen

Liu

Tang

. Multi-objective evolutionary triclustering with constraints of time-series gene expression data. Integrated Computer-Aided Engineering. 2019; 26(4): 399–410.

43.

Zhang

Chen

. A new haze removal approach for sky/river alike scenes based on external and internal clues. Multimedia Tools and Applications. 2020; 79: 2085–2107.

44.

D’Urso

Masi

Zuccaro

De Gregorio

. Multicriteria fuzzy analysis for a GIS-based management of earthquake scenarios. Computer-Aided Civil and Infrastructure Engineering. 2018; 33(2): 165–179.

45.

Liang

Quan

. A dividing-based many-objective evolutionary algorithm for large-scale feature selection. Soft Computing. 2020; 24(9): 6851–6870.

46.

Zhao

Guo

Zhou

Zhang

. A quantum-inspired genetic algorithm-based optimization method for mobile impact test data integration. Computer-Aided Civil and Infrastructure Engineering. 2018; 33(5): 411–422.

47.

Mirjalili

Lewis

. Grey wolf optimizer. Advances in Engineering Software. 2014; 69: 46–61.

48.

Yong

Zhou

. A novel bat algorithm based on cross boundary learning and uniform explosion strategy. Applied Mathematics-A Journal of Chinese Universities. 2019; 34(4): 480–502.

49.

Luo

Yong

. An efficient and robust bat algorithm with fusion of opposition-based learning and whale optimization algorithm. Intelligent Data Analysis. 2020; 24(3): 581–606.

50.

Li H He F Chen Y Luo J . Multi-objective self-organizing optimization for constrained sparse array synthesis. Swarm and Evolutionary Computation. 2020; 58: 100743.

51.

Hossain

Akhand

Shuvo

Siddique

Adeli

. Optimization of university course scheduling problem using particle swarm optimization with selective search. Expert Systems with Applications. 2019; 127: 9–24.

52.

Abualigah

Khader

Hanandeh

. A new feature selection method to improve the document clustering using particle swarm optimization algorithm. Journal of Computational Science. 2018; 25: 456–466.

53.

Sun

Miao

Gong

Zeng

Wang

. Interval multiobjective optimization with memetic algorithms. IEEE transactions on cybernetics. 2019.

54.

Schütze

Martín

Lara

Alvarado

Salinas

Coello

CAC

. The directed search method for multi-objective memetic algorithms. Computational Optimization and Applications. 2016; 63(2): 305–332.

55.

Alomari

Khader

Al-Betar

Abualigah

. Gene selection for cancer classification by combining minimum redundancy maximum relevancy and bat-inspired algorithm. International Journal of Data Mining and Bioinformatics. 2017; 19(1): 32–51.

56.

Pan

. Learning social representations with deep autoencoder for recommender system. World Wide Web. 2020; 23(4): 2259–2279.

57.

Hou

Zhou

Chen

. An efficient GPU-based parallel tabu search algorithm for hardware/software co-design. Front Comput Sci. 2020; 14(5): 145316.

58.

Aljarah

Faris

Mirjalili

. Optimizing connection weights in neural networks using the whale optimization algorithm. Soft Computing. 2018; 22(1): 1–15.

59.

Bhesdadiya

Jangir

Trivedi

Ladumor

. Training multi-layer perceptron in neural network using whale optimization algorithm. Indian J Sci Technol. 2016; 9(19): 28–36.

60.

Kaur

Arora

. Chaotic whale optimization algorithm. Journal of Computational Design and Engineering. 2018; 5(3): 275–284.

61.

Ling

Zhou

Luo

. Lévy flight trajectory-based whale optimization algorithm for global optimization. IEEE Access. 2017; 5: 6168–6186.

62.

Bozorgi

Yazdani

. IWOA: An improved whale optimization algorithm for optimization problems. Journal of Computational Design and Engineering. 2019; 6(3): 243–259.

63.

Yeoh

Caraffini

Homapour

Santucci

Milani

. A clustering system for dynamic data streams based on metaheuristic optimisation. Mathematics. 2019; 7(12): 1229.

64.

Elsayed

Sarker

Essam

. A self-adaptive combined strategies algorithm for constrained optimization using differential evolution. Applied Mathematics and Computation. 2014; 241: 267–282.

65.

Chikahiro

Ario

Pawlowski

Graczykowski

Holnicki-Szulc

. Optimization of reinforcement layout of scissor-type bridge using differential evolution algorithm. Computer-Aided Civil and Infrastructure Engineering. 2019; 34(6): 523–538.

66.

Cheng

Zhang

Caraffini

Neri

. Multicriteria adaptive differential evolution for global numerical optimization. Integrated Computer-Aided Engineering. 2015; 22(2): 103–107.

67.

Goudos

Deruyck

Plets

Martens

Joseph

. Optimization of power consumption in 4G LTE networks using a novel barebones self-adaptive differential evolution algorithm. Telecommunication Systems. 2017; 66(1): 109–120.

68.

Abderazek

Ferhat

Ivana

. Adaptive mixed differential evolution algorithm for bi-objective tooth profile spur gear optimization. The International Journal of Advanced Manufacturing Technology. 2017; 90(5–8): 2063–2073.

69.

Al-Dabbagh

Raja Abdullah

Hashim

. A new modified differential evolution algorithm scheme-based linear frequency modulation radar signal de-noising. Engineering Optimization. 2015; 47(6): 771–787.

70.

Poikolainen

Neri

Caraffini

. Cluster-based population initialization for differential evolution frameworks. Information Sciences. 2015; 297: 216–235.

71.

Wang

Cai

Zhang

. Enhancing the search ability of differential evolution through orthogonal crossover. Information Sciences. 2012; 185(1): 153–177.

72.

Neri

Tirronen

. Recent advances in differential evolution: A survey and experimental analysis. Artificial Intelligence Review. 2010; 33(1–2): 61–106.

73.

Caraffini

Kononova

Corne

. Infeasibility and structural bias in differential evolution. Information Sciences. 2019; 496: 161–179.

74.

Caraffini

Neri

. A study on rotation invariance in differential evolution. Swarm and Evolutionary Computation. 2019; 50: 100436.

75.

Das

Mullick

Suganthan

. Recent advances in differential evolution – an updated survey. Swarm and Evolutionary Computation. 2016; 27: 1–30.

76.

Moscato

Cotta

. An accelerated introduction to memetic algorithms. In: Handbook of Metaheuristics. Springer; 2019. pp. 275–309.

77.

Al-Dabbagh

Neri

Idris

Baba

. Algorithmic design issues in adaptive differential evolution schemes: Review and taxonomy. Swarm and Evolutionary Computation. 2018; 43: 284–311.

78.

Chalupa

Hawick

Walker

. Hybrid bridge-based memetic algorithms for finding bottlenecks in complex networks. Big Data Research. 2018; 14: 68–80.

79.

Zhou

Jacobson

. Thingi10k: A dataset of 10,000 3d-printing models. arXiv preprint arXiv:160504797. 2016.

80.

Liu

Chen

Song

. Quality improvement of surface triangular mesh using a modified Laplacian smoothing approach avoiding intersection. Plos One. 2017; 12(9): e0184206.

81.

Zhang

Duan

Xue

. A high-quality closed model generation approach for triangular mesh. Journal of Information &Computational Science. 2014; 11(10): 3433–3440.

82.

Cignoni

Rocchini

Scopigno

. Metro: measuring error on simplified surfaces. In: Computer Graphics Forum. Vol. 17. Wiley Online Library; 1998. pp. 167–174.

83.

Storn

. On the usage of differential evolution for function optimization. In: Fuzzy Information Processing Society, 1996. NAFIPS. 1996 Biennial Conference of the North American; 1996.

3D mesh simplification with feature preservation based on Whale Optimization Algorithm and Differential Evolution

Abstract

Keywords

1. Introduction

2.1 Mesh simplification algorithm

2.1.1 Vertex clustering

2.4 Edge splitting operation

3.1 The feature-preservation edge collapse operation

Table 1 Main notation in Section 4

4.4.1 WOA

(1) Encircling prey ( p < 0.5 and | A → | > 1 )

(2) Spiral updating position ( p ⩾ 0.5 )

(3) Search for prey ( | A → | > 1 )

(1) Mutation

(2) Crossover

(3) Selection

(1) Initialize

(2) Optimization

(3) Selection

(4) Termination conditions

5.1 Geometric feature preservation

Table 2 Results and visual comparison

5.4 The performance of the proposed optimization algorithm

5.4.1 The effectiveness of the optimizer

Table 5 Comparison of errors of different optimization algorithms

5.6 Parameter setting

6. Conclusions and future work

Footnotes

Acknowledgments

References

Table 1
Main notation in Section 4

(1) Encircling prey ( $p<0.5$ and $|\vec{A}|>1$ )

(2) Spiral updating position ( $p\geqslant 0.5$ )

(3) Search for prey ( $|\vec{A}|>1$ )

Table 2
Results and visual comparison

Table 5
Comparison of errors of different optimization algorithms