An improved loop subdivision to coordinate the smoothness and the number of faces via multi-objective optimization

Abstract

3D mesh subdivision is essential for geometry modeling of complex surfaces, which benefits many important applications in the fields of multimedia such as computer animation. However, in the ordinary adaptive subdivision, with the deepening of the subdivision level, the benefits gained from the improvement of smoothness cannot keep pace with the cost caused by the incremental number of faces. To mitigate the gap between the smoothness and the number of faces, this paper devises a novel improved mesh subdivision method to coordinate the smoothness and the number of faces in a harmonious way. First, this paper introduces a variable threshold, rather than a constant threshold used in existing adaptive subdivision methods, to reduce the number of redundant faces while keeping the smoothness in each subdivision iteration. Second, to achieve the above goal, a new crack-solving method is developed to remove the cracks by refining the adjacent faces of the subdivided area. Third, as a result, the problem of coordinating the smoothness and the number of faces can be formulated as a multi-objective optimization problem, in which the possible threshold sequences constitute the solution space. Finally, the Non-dominated sorting genetic algorithm II (NSGA-II) is improved to efficiently search the Pareto frontier. Extensive experiments demonstrate that the proposed method consistently outperforms existing mesh subdivision methods in different settings.

Keywords

3D mesh subdivision variable threshold multi-objective optimization

1. Introduction

3D mesh is one of the most popular input sources, which has been widely used in multimedia applications, including virtual reality [1], computer animation [2, 3], 3D reconstruction [4, 5], and computer vision [6, 7]. Meanwhile, with the development of 3D scanning [8], acquisition [9, 10], and modeling technologies [11, 12], more and more 3D models have been developed [13]. However, most of them are coarse mesh representations. To meet the increasing requirements (i.e., to efficiently smooth coarse surfaces) in real-world applications, mesh subdivision methods have received increasing attention from the community.

Mesh subdivision is fundamental in computer graphics, enabling the modelers to sculpt shapes in a coarse-to-fine manner [14]. In 1974, Chaikin put forward a rapid curve generation method and first introduce the concept of subdivision into graphics [15]. Then, Catmull-Clark [16] and Doo-shabin [17] further brought the arbitrary connectivity on parametric surfaces, which soon became the mainstream surface modeling technology. After that, many different subdivision schemes have been developed, e.g., Loop subdivision [18], Butterfly subdivision [19], and $\sqrt{3}$ subdivision [20].

The ordinary subdivision methods usually refine all the faces of mesh models, while subdividing all faces uniformly will cause an exponential increase in the number of faces and consume a large number of computation resources and storage space. Two different kinds of efforts to overcome the limitation of storage space are as follows.

(1) (1)
To reduce the 3D data amount, some researchers proposed to encode and compress the mesh models [21]. However, these methods are used for transmission, and the compressed mesh models would be recovered to the original states before the actual processing runtime.
(2)
To reduce the number of added faces, some adaptive subdivision algorithms propose to only refine a subset of the faces in the control mesh [22, 23]. In the initial iterations, these methods do increase the gaining of smoothness while adding fewer faces. However, with the deepening of the subdivision level, the cost of added faces outweighs the gain of smoothness.

However, the problem of mesh subdivision is non-trivial, especially considering that the number of faces and the smoothness are not only closely related but also contradictory to each other. Therefore, this problem cannot be directly solved by emphasizing either the smoothness or the number of faces independently. Instead, it requires improving the smoothness but with a few additional faces as possible. To address the above-mentioned problem, an improved Loop subdivision method is proposed to coordinate the smoothness and face number harmoniously as follows.

First, the resulting crack problem requires to be solved since that adaptive subdivision only subdivides a subset of faces. However, existing crack-solving methods are not suitable due to either the poor subdivision performance [24, 23] or the low computation efficiency [25, 26, 27, 28]. Different from the above-mentioned methods, a novel crack-solving method is proposed by only refining the three adjacent faces of the subdivided area, which can obtain a good crack-solving performance while adding fewer faces.

Second, rather than using a constant threshold in the existing adaptive subdivision, an adaptive Loop subdivision method with variable thresholds is proposed in this paper, where the variable thresholds can better fit the dynamics of the topological structure and smoothness of the surface.

Third, to find a good tradeoff between the smoothness and the number of faces in subdivided mesh models, the problem of adaptive subdivision is modeled as a multi-objective optimization problem (MOP), where the solution is the sequence of thresholds in subdivision iterations. Two main objectives are the smoothness of the whole mesh model and the storage space, respectively.

Finally, to address the newly discovered mesh subdivision problem, a novel multi-objective optimization algorithm, WOA/NSGA-II, is devised by integrating the mechanisms of the Whale Optimization Algorithm (WOA). Furthermore, the WOA/NSGA-II is applied to search the Pareto solution set.

Numerous experiments are performed to demonstrate the effectiveness of the proposed method for mesh subdivision, where the proposed improved Loop subdivision method outperforms existing methods: (1) when the smoothness is comparable, the proposed subdivision method achieves much fewer faces; (2) when the number of faces is same, the proposed subdivision method achieves better smoothness.
2. Related works

2.1 Mesh subdivision

2.1.1 Linear subdivision methods

Classic linear subdivision methods include approximating methods and interpolating methods, which are the combination of refinement operations. They have been studied from the theoretical perspective on the existence and continuity of the limit surface [29].

Loop et al. [18] proposed Loop subdivision to extend the quartic 3-direction box spline to the arbitrary triangle mesh. For each face, its three edges would be inserted a new vertex separately, and the new vertices would be connected. Kobbelt [20] proposed the $\sqrt{3}$ subdivision method, in which a new vertex would be inserted at the centroid of each face and then connected to the existing vertices. The approximating methods repositioned the existing vertices by the combination of the neighboring vertices. In contrast, the interpolating procedures do not reposition the existing vertices.

Dyb, Levin and Gregory proposed the Butterfly subdivision [19], which interpolates all the vertices of the initial control mesh and the new vertices generated in the subdivision process. Then, Denis et al. [30] proposed the modified Butterfly subdivision, which can generate $C_{1}$ continuous subdivision surfaces on any control mesh. The butterfly subdivision method can smooth the meshes while keeping the detailed features. Kobbelt [31] proposed an interpolatory subdivision for quadrilateral meshes with arbitrary topology, which computes the positions of the new vertices by simple affine combinations of vertices from the unrefined net.

2.1.2 Non-linear subdivision methods

The non-linear subdivision has been studied from a mathematical perspective. One general approach is to combine the linear subdivision with geometric optimization and apply the non-linear rule recursively arbitrary, akin to classic linear rules [32, 33].

Vaxman et al. [34] developed a nonlinear subdivision framework to generate the subdivision surfaces belonging to Möbius geometry, which transforms each one-ring to the canonical form by the Möbius-invariant operators and then applies a linear subdivision. Preiner et al. [35] introduced the Gaussian covariance matrix to sketch the probability distribution of the position of the spatial surface around the vertices, and then proposed a Gaussian-based nonlinear probabilistic subdivision operator to generate a smooth surface. Liu et al. [14] proposed the Neural Subdivision, a novel framework for data-driven coarse-to-fine geometry modeling. Non-linear subdivision can be regarded as a mechanism to maintain certain geometric invariants during subdivision, for example, circle-preserving [36], quad planarity [37], and developability [38].

2.2 Adaptive subdivision

In practical applications, not all regions need to be subdivided. For the parts which are already flat and smooth, the subdivision cannot improve the rendering effect but will increase storage space and calculation cost. Therefore, the adaptive subdivision is of great significance for promoting computation efficiency. In the adaptive subdivision, selecting the areas to be subdivided is important [18], computed an approximation error of the surface by comparing it with the limit surface. Kim et al. [39] proposed a novel error metric to compute the local discrete Gaussian curvature of the vertex. Shi et al. [23] proposed to use the dihedral angle between the adjacent faces as a simple approximation of surface curvature.

There are also many adaptive subdivision methods. Huang [40] proposed a real-time rendering Loop subdivision surfaces method, which uses the GPU to refine the irregular faces recursively and handles the control meshes of arbitrary topologies. Niessner [41] proposed the feature-adaptive subdivision, which only subdivides the regions with high or infeasible processing costs and processes regular faces using the hardware tessellation. To solve the popping effect and shrinkage problem, Shi et al. [22, 23] proposed to deal with the extraordinary vertices in combination with the modified Butterfly rules, in which the position of the newly generated vertex will increase the moving distance of the original vertex.

2.3 Handling inconsistencies

As shown in Fig. 1, subdividing only one of the adjacent faces will result in adjacent faces in different subdivision levels and the incomplete neighborhoods of newly generated vertex, both of which will lead to the generation of cracks. The edge cracks are unavoidable in the adaptive subdivision. There are some methods proposed to solve this problem.

Figure 1.

The crack problem, in which the numbers denote the subdivision level that the faces belong to and the blue triangles denote the subdivided area.

2.3.1 The simple triangulation

The simple triangulation method [24, 23] removes the crack by bisecting the faces with lower subdivision levels. As shown in Fig. 2, according to the number of odd vertices in the faces, it splits the neighboring faces into two, three, or four sub-faces. This mechanism is direct and straightforward; however, it will change the connectivity of existing vertices, produce high valence vertices, and influence the render effect.

Figure 2.

The simple triangulation process.

2.3.2 The red-green triangulation

The red-green triangulation method [25, 26] bisects the faces with one crack (green triangulation) and divides the faces with more than one crack into four (red triangulation), as shown in Fig. 3. In each subdivision, the green triangulated faces will be checked whether they will have more than one crack after the subdivision; and if so, they would be red triangulated. Because the connectivity between the vertices is temporary, this method will not affect the connectivity of the selected region. It can avoid the occurrence of high valence extraordinary vertices and reduce the subdivision depth difference.

Figure 3.

The red-green triangulation process, in which (b) and (e) are two subdivision processes, (c) and (f) are refinement processes. In this figure, the pink faces denote the selected area, the blue faces denote the subdivided area, the green faces denote the green triangulation, and the red faces denote the red triangulation.

2.3.3 The incremental subdivision

The incremental subdivision method [27, 28] constructs an $r$ -ring neighborhood by expanding the selected area and conducting the same subdivision operation to the neighborhood as the selected area. Figure 4 shows two subdivision processes of incremental subdivision with $r=1$ . This method is suitable for all kinds of complex selected areas and could prevent producing high valence vertices.

Figure 4.

The incremental subdivision process, in which (b) and (d) are two subdivision processes. In this figure, the purple faces denote the 1-ring neighborhood of the selected area, and the other colors have the same meanings as the colors in Fig. 3.

3. The proposed improved adaptive Loop subdivision method

This section introduces the proposed adaptive Loop subdivision method with variable thresholds to generate a smooth mesh model with a small number of faces.

3.1 Preliminaries

In this subsection, some preliminaries are provided for the adaptive Loop subdivision.

Figure 5.

The subdivision regulations of the loop subdivision.

Some subdivision regulations of the Loop subdivision are shown in Fig. 5. Specifically, in the $i$ -th subdivision iteration, the splitting operation generates the vertices $e^{i+1}$ on the edges, which can be calculated as follows:

$\displaystyle e^{i+1}=\frac{1}{8}(3v_{2}^{i}+v_{1}^{i}+3v_{3}^{i}+v_{4}^{i}),$ (1)

where $v_{1}^{i}$ , $v_{2}^{i}$ , $v_{3}^{i}$ , and $v_{4}^{i}$ are defined as Fig. 5. Existing vertices will be repositioned by a linear combination of their neighbor vertices $v_{j}^{i}$ as follows:

$\displaystyle v^{i+1}=(1-n\beta_{n})v^{i}+\beta_{n}\sum_{j=0}^{n-1}v_{j}^{i},$ (2)

where $n$ indicates the valence of $v^{i}$ , and $\beta_{n}$ can be defined as:

$\displaystyle\beta_{n}=\begin{cases}{\displaystyle\frac{3}{16}}&(n=3)\\ {\displaystyle\frac{1}{n}}\left({\displaystyle\frac{5}{8}}-\left({% \displaystyle\frac{3}{8}}+{\displaystyle\frac{1}{4}}\cos{\displaystyle\frac{2% \pi}{n}}\right)^{2}\right)&(n>3)\end{cases}$ (3)

The dihedral angle between the adjacent faces is leveraged to measure the smoothness. The process of a typical adaptive Loop subdivision based on the dihedral angle can be summarized as follows.

(1) (1)

Compute the dihedral angle of all pairs of adjacent faces in the mesh model.

(2)

For a face $f$ , examine the dihedral angles between it and its three adjacent faces $f_{1}$ , $f_{2}$ , and $f_{3}$ . For example, if the dihedral angle between $f$ and $f_{1}$ is smaller than the pre-set threshold, $f$ and $f_{1}$ would be marked as ‘need to subdivide’.

(3)

Repeat Step (2) until all faces have been checked.

(4)

Subdivide the marked faces using the Loop subdivision scheme.

(5)

Repeat Steps (1)–(4) until a reasonable smoothness is reached.

3.2 Adaptive loop subdivision with variable thresholds

In adaptive mesh subdivision, pre-defined thresholds will affect both the smoothness and the number of faces of the mesh models. If the threshold is too small, the improvement of the smoothness will also be relatively small, making it difficult to meet users’ requirements; if the threshold is too large, the number of faces will significantly increase, consuming huge storage space and computational cost. This contradiction cannot be addressed by existing adaptive subdivision processes, considering that their subdivision regulation is consistent while the mean of dihedral angles and the topological structure of the 3D mesh model may change throughout the subdivision process. Furthermore, it is also difficult to determine an appropriate threshold from the input mesh model for ordinary users. In contrast, when using a different threshold in each subdivision iteration, the selected area will always change, and the surface smoothness and the number of faces in the subdivided mesh models will also be affected. Therefore, to satisfy the high requirements in both smoothness and storage space, variable thresholds can be used to reduce the number of added faces while also maintaining the smoothness of the subdivided mesh models. The main framework of the proposed variable threshold-based adaptive subdivision method can be summarized in Algorithm 3.2. It is worth mentioning that the tradeoff between the smoothness and the number of faces is common in subdivision methods, and the proposed adaptive subdivision methods with variable thresholds also can be used for other subdivision methods.

Adaptive Loop subdivision with variable thresholds

$M$ , a mesh model $S=\{t_{1},t_{2},\ldots,t_{n}\}$ , the sequence of threshold.

The subdivided mesh model.

$k=0$ ;

$k<$ max iterations each face $i\in M$ $j\in 3$ Compute the dihedral angle $d_{i,j}$ between face $f_{i}$ and its adjacent face $f_{i,j}$ ;

$d_{i,j}<t_{k}$ mark $f_{i}$ and $f_{i,j}$ as ‘need to subdivide’;

Subdivide the marked faces using the Loop subdivision scheme;

$k=k+1$ ;

Figure 6.

The subdivision process of the proposed crack-solving method, where the colors have the same meanings as the colors in Figs 3 and 4.

Figure 7.

The overall process of the proposed improved adaptive subdivision method, including the optimization process and the subdivision process. In the optimization process, the ‘Evaluation’ operation is implemented by the subdivision process.

3.3 Crack-solving method

In the proposed adaptive Loop subdivision method, thresholds are different in each subdivision iteration, i.e., selected regions will constantly change, and almost no region is available to be subdivided multiple times. In this case, previous crack-solving methods are usually not suitable (the poor performance of a simple triangulation, the high implementation complexity of red-green triangulation, and the large number of new faces generated by the incremental subdivision). Therefore, a novel crack-solving method is proposed to remove the cracks more efficiently by combining the red-green triangulation and the incremental subdivision.

For the red-green triangulation, the proposed crack-solving method retains its subdivision mechanism and gives up its requirement of recursive inspection. For the incremental subdivision, the proposed crack-solving method adopts the constructing transition area mechanism, while only refines three adjacent faces to save storage space. The twice subdivision process of the proposed crack-solving method is shown in Fig. 6. Specifically, in each subdivision, selected faces and three adjacent faces will be marked, which will then be divided into four faces. For the unmarked faces, if they have more than one crack, then they will be divided into four; otherwise, they will be bisected.

From the diagrammatic sketch, the subdivision effect of the proposed crack-solving method is similar to the results of the red-green triangulation and the incremental subdivision. Moreover, since the proposed crack-solving method combines the above two methods, it inherits a lot of their advantages, including pushing the extraordinary vertices outside the selected region and avoiding the high valence vertices and long faces with ripple. See more details in the experiment section.

3.4 An improved adaptive subdivision method

The main purpose of this paper is to optimize the smoothness and the face number (storage space) of the subdivided mesh models simultaneously. In the proposed method, the threshold sequences will influence the smoothness and face number of subdivided mesh models. In this way, the challenging problem of optimizing the smoothness and the storage space can be converted to select the appropriate threshold sequence, which leads to a smoother subdivided mesh model with fewer faces. In this paper, the proposed adaptive mesh subdivision problem is modeled as a MOP, which can be described as given a control mesh model and a user-defined subdivision level, computing the Pareto front of the storage space and smoothness of subdivided mesh models. The overall process of the proposed improved adaptive subdivision method is shown in Fig. 7.

3.4.1 Optimization fitness functions

The first optimization objective is the storage space. Specifically, the final number of faces for the subdivided mesh model is adopted to measure the storage space, which is referred to as Num in this paper.

The second optimization objective is the smoothness. The mean of dihedral angles corresponding to all edges in the subdivided mesh model is adopted to measure the smoothness of the whole 3D mesh model, which is referred to as MDA:

$\displaystyle\textit{MDA}=\frac{1}{3*\textit{Num}}\sum_{i=1}^{\textit{Num}}% \theta_{i_{1}}+\theta_{i_{2}}+\theta_{i_{3}},$ (4)

where $\theta_{i_{1}}$ , $\theta_{i_{2}}$ , and $\theta_{i_{3}}$ indicate the dihedral angles corresponding to three edges in the face $i$ .

3.4.2 Problem statement and solution space

In the proposed adaptive subdivision method, the dihedral angle threshold varies from each subdivision iteration. In this paper, the dihedral angle threshold of each iteration is combined into the sequence $S$ :

$\displaystyle S=(t_{1},t_{2},t_{3},\ldots,t_{d}),$ (5)

where $t_{i}$ indicates the threshold in the $i^{\text{th}}$ subdivision iteration, and $d$ is the final subdivision level. The possible threshold sequences $S$ constitute the solution space $\mathbb{S}$ . For each threshold sequence $S$ , the subdivided result obtained by applying $S$ as the threshold sequence is denoted as $M_{S}$ . Generally, a MOP can be described as Eq. (6).

$\displaystyle\text{Minimize}:y(x)=\{y_{1}=f_{1}(x),y_{2}=f_{2}(x),\ldots,y_{m}% =f_{m}(x)\},$ (6)

where $x\in R^{n}$ is a solution vector with $n$ variables, and $f_{m}(x)$ is the fitness function of $m$ -th objective.

In this paper, different threshold sequences will lead to the subdivided results with different smoothness and number of faces. Based on the MOP formulation, multi-objectives of the proposed improved mesh subdivision problem can be described using Eq. (7).

$\displaystyle\text{Minimize}:F(S)=\{f_{1}=\textit{MDA}(M_{S}),∼{}∼{}f_{2}=% \textit{Num}(M_{S})\},$ (7)

where $M_{S}$ indicates the solution. $f_{1}$ and $f_{2}$ are two fitness functions, which constitute the goal space.

4. Multi-objective optimization process

To address various kinds of complex problems in real-world applications, there are many nature-inspired optimization techniques [42, 43, 44, 45, 46]. Some problems involving two or more contradictory or interactive objectives can only be solved by the multi-optimization evolutionary algorithms (MOEA). In addition, MOEA is common and important in engineering applications, which has been widely adopted to solve complex problems [47], such as industrial design [48, 49], image analysis [50, 51, 52], task scheduling [53, 54, 55], structure optimization [56, 57, 58], civil engineering [59, 60, 61], and transportations problem [62, 51, 63]. To solve MOPs, many MOEAs have been proposed, e.g., SPEA2 [64], NSGA-II [65], MOEA/D [66, 67], and MOPSO [68].

4.1 The proposed WOA/NSGA-II

From the No-free-lunch theorem [69], it is known that no optimization algorithm can match all practical engineering and application problems perfectly. The proposed subdivision optimization problem is relatively complex due to the multi-dimensional solution vector and the large size of the search space. Moreover, the proposed adaptive mesh subdivision is not a linear problem, two different threshold sequences may lead to the same subdivision results with the same smoothness and the same number of faces. As a result, the proposed optimization problem requires higher search accuracy, and the original NSGA-II maybe not sufficient. To overcome the limitation of a single optimization algorithm, many researchers have proposed to modify or fuse different algorithms for different optimization problems. By doing this, new algorithms usually can obtain a better solution [70]. WOA [71] is a meta-heuristic optimization algorithm based on the simulation of humpback whale hunting behavior. Compared with other optimization algorithms, the advantages of WOA are intuitive: simple structure, easy to implement, fewer parameters. The good search performance of WOA has been demonstrated by many existing methods [72, 73, 74]. Moreover, the clear mechanism of WOA also enables it to be integrated into other optimization algorithms.

In this paper, WOA is proposed to be hybridized with NSGA-II, where the exploitation mechanism of WOA is utilized to improve the search accuracy of NSGA-II. The proposed WOA/NSGA-II algorithm takes NSGA-II as the baseline framework, while replaces the mutation operator of NSGA-II with the encircling prey and the spiral updating position operators of WOA. WOA/NSGA-II retains NSGA-II’s elite retention strategy, fast non-dominated sorting, crowding distance computation, and binary tournament selection mechanisms.

In the evolutionary process, WOA/NSGA-II first generates new solutions by the simulated binary crossover (SBX) operator. Then, it updates each individual in new solutions using the encircling prey mechanism and spiral updating position mechanism of WOA with the same probability. It is worth mentioning that, both in the encircling prey mechanism and the spiral updating position mechanism, the current optimal individual is necessary when updating the position of other individuals. While there is no concept of the optimal individual in the Pareto solution set of NSGA-II. To overcome the above-mentioned problem, the first Pareto front is regarded as the current optimal solution set and the corresponding current optimal individual will be selected from the first Pareto front. For example, for each individual $X_{i}(t)$ , the individual which is closest to $X_{i}(t)$ in the first Pareto front will be chosen as $X_{i}(t)$ ’s optimal solution $X^{*}_{i}(t)$ .

4.2 Optimizing the mesh subdivision process with WOA/NSGA-II

4.2.1 Initialization

In the proposed improved subdivision problem, thresholds are obtained within the range of the constant threshold of the ordinary methods. The population is defined in a fixed range, $[ct-fr,ct+fr]$ , where $c t$ is the pre-defined constant threshold, and $f r$ indicates the floating range, which is utilized to generate the random initial population. The initial population ${X}(0)=\{X_{i}(0)\}^{N_{p}}_{i=1}$ is randomly sampled in this fixed range:

$\displaystyle x_{i,j}(0)=ct-fr+\text{rand}[0,1]\cdot 2fr$ $\displaystyle i=1,2,\ldots,N_{p},j=1,2,\ldots,d.$ (8)

4.2.2 The sorting process

(1) Fast non-dominated sorting

Fast non-dominated sorting is based on the non-dominant information. For a solution, if it is not dominated by all other solutions, it will be considered as the first Pareto front (first rank); if it is only dominated by the first rank’s solutions, it will be considered as the second front (second rank); and so on. In this way, the domination conditions of the solution $X_{1}$ over solution $X_{2}$ can be defined as follows:

•
$X_{1}$ is not always worse than $X_{2}$ for all objective functions.
•
For all objective functions, there is at least one that makes $X_{1}$ absolutely superior to $X_{2}$ .

(2) Crowding distance computation

The crowding distance is utilized when sorting the individuals with the same rank, where the crowding distance of each individual $i$ is the average distance between its solution and the two adjacent solutions on both sides of each objective. The crowding distance can be evaluated using Eq. (9) as follows,

$\displaystyle d_{i}=\sum_{j=1}^{m}\frac{|f_{j}^{i+1}-f_{j}^{i-1}|}{f_{j}^{\max% }-f_{j}^{\min}},$ (9)

where $f_{j}^{i}$ is the function value of the $j^{\text{th}}$ sub-objective of the $i^{\text{th}}$ solution, and $f_{j}^{\max}$ and $f_{j}^{\min}$ indicate the maximum and minimum value obtained by all solutions of the $j^{\text{th}}$ sub-objective, respectively.

(3) Crowded-comparison operator

The non-dominant rank and the crowding distance are utilized to determine the dominant relationship between any two individuals in the population. The comparison between $X_{1}$ and $X_{2}$ is based on the following conditions:

$\displaystyle\text{if }((r_{X_{1}}<r_{X_{2}})\land((r_{X_{1}}==r_{X_{2}})\land% (d_{X_{1}}>d_{X_{2}}))$ $\displaystyle X_{1}\succ X_{2},$ (10)

where $r_{X_{1}}$ denotes the non-dominant rank of $X_{1}$ and $d_{X_{1}}$ indicates the crowding distance of $X_{1}$ .
4.2.3 Exploration phase

The SBX operator is utilized as the exploration operation. For the two parent-individuals selected by the binary tournament selection procedure, $X_{1}$ and $X_{2}$ , their offspring $CX_{1}$ , and $CX_{2}$ are defined as:

$\displaystyle\begin{cases}cx_{1,j}=0.5[(1+\beta)x_{1,j}+(1-\beta)x_{2,j}],\\ cx_{2,j}=0.5[(1-\beta)x_{1,j}+(1+\beta)x_{2,j}],\end{cases}$ (11)

where $\beta$ is dynamically determined by the distribution index $\eta_{c}$ according to Eq. (12).

$\displaystyle\beta=\begin{cases}(2*r)^{1/(1+\eta_{c})}&\text{if }(r<0.5),\\ {\displaystyle\frac{1}{(2-2*r)}}^{1/(1+\eta_{c})}&\text{otherwise},\end{cases}$ (12)

where $r$ is randomly sampled from $U(0,1)$ .

4.2.4 Exploitation phase

In the exploration phase, the encircling prey operator and spiral updating position operator are utilized to update the individuals.

(1) Encircling prey phase

The encircling prey operator is clear and simple, which is defined as follows:

$\displaystyle X^{\prime}(t)=X^{*}(t)-A\cdot D,$ (13) $\displaystyle D=|C\cdot X^{*}(t)-X(t)|,$ (14)

where $X(t)$ denotes the individuals of $t^{\text{th}}$ generation, $X^{*}(t)$ denotes the best individual of $t^{\text{th}}$ generation, and $X^{\prime}(t)$ denotes the updated individuals. $A$ and $C$ are the coefficient vectors, which can be calculated as follows:

$\displaystyle A=2\alpha\cdot r-\alpha,$ (15) $\displaystyle C=2\cdot r,$ (16)

where $\alpha$ is linearly decreased from 2 to 0 along with iterations, and $r$ is randomly sampled from $U(0,1)$ .

(2) Spiral updating phase

The Spiral updating position operator represents another behavior of humpback whale, bubble-net attacking in a spiral. The spiral equation is shown in Eq. (18).

$\displaystyle X^{\prime}(t)=D^{\prime}\cdot e^{bl}\cdot\cos(2\pi l)+X^{*}(t),$ (17) $\displaystyle D^{\prime}=X^{*}(t)-X(t),$ (18)

where coefficient $l$ is randomly sampled from $U(-1,1)$ , and $b$ is a constant.

According to humpback whale habits, both the above operations have a 50% chance of being selected in the exploitation process, which is shown in Eq. (19).

$\displaystyle X^{\prime}(t)=\begin{cases}X^{*}(t)-A\cdot D&\text{if }(p<0.5),% \\ D^{\prime}\cdot e^{bl}\cdot\cos(2\pi l)+X^{*}(t)&\text{if }(p\geqslant 0.5),% \end{cases}$ (19)

where $p$ is randomly sampled from $U(0,1)$ .

4.2.5 The conditions for terminate

The terminate conditions are as follows: 1) the number of iterations reached the max iterations; 2) in consecutive $n_{t}$ iterations, the relative change of fitness function value

$\displaystyle\frac{f(t)-f(t+1)}{f(t)}$

always does not exceed threshold $t$ , in which the threshold $\tau$ is set as $1.0e^{-4}$ , and the fixed-parameter $n_{t}$ is set as 3 in the experiments. The pseudo-code of WOA/ NSGA-II is shown in Algorithm 4.2.5.

[!t] Improved adaptive mesh subdivision using WOA/ NSGA-II

$M$ , the input mesh model $c t$ , the user defined consistent threshold $d$ , subdivision depth.

A set of non-dominated solutions composed of the subdivided mesh models.

Initialize the first population $P(0)$ and calculate the multi-objective fitness of each individual;

$t=0$

$t<$ max iterationsSelect the individuals using binary tournament selection mechanism;

Generate the population $P^{\prime}(t)$ using SBX operator;

$Q(t)=\varnothing$

each individual $P^{\prime}(t)\in P^{\prime}(t)$ Update $a$ , $C$ , $A$ , $l$ , $p$ ;

Generate the population $P^{\prime\prime}_{i}(t)$ by updating $P_{i}^{\prime}(t)$ ;

$p<0.5$ Update $P^{\prime}_{i}(t)$ using encircling prey; Update $P^{\prime}_{i}(t)$ using spiral updating position;

$Q(t)=Q(t)\cup P^{\prime\prime}_{i}(t)$ ;

$R(t)=Q(t)\cup P(t)$ ;

Generate the subdivded mesh models using the population $R(t)$ and compute the multi-objective fitness of each individual;

Rank the solutions in the population $R(t)$ and compute their crowding distance;

Assign $R(t)$ into the new population $P(t+1)$ ;

Replace parent population by $P(t+1)$ ;

$t=t+1$ ;

5. Experiments

The mesh models used in experiments are from the animation/film industry, real mechanical engineering, and standard benchmark [75, 76]. The proposed method is compared with several classic and recent state-of-art methods in terms of the crack-solving effect, the number of faces, and the smoothness of the subdivided mesh models.

5.1 Implementation details

This subsection will analyze the parameters set in the manuscript from two aspects: the subdivision process and the optimization process, where all the parameters are listed in Table 1. In the mesh subdivision process, the thresholds and subdivision levels are closely related to the obtained subdivided result.

Table 1
The list of parameters

Process	Parameter	Value
Subdivision	Threshold	–
	Subdivision level	–
Optimization	The floating range $f r$	5
	The distribution index $\eta_{c}$	0.8
	The individual vector length $d$	–
	The population size $N_{p}$	30
	Number of tests	3

Table 2

The comparison of subdivision performance. $\textit{Num}_{0}$ denotes the face number in the original mesh model, level denotes the subdivision level, threshold denotes the threshold used in ordinary subdivision methods, $f r$ denotes the floating range, Num and MDA denote the face number and the smoothness in the subdivided mesh models respectively

Mesh	$\text{Num}_{0}$	Level	Threshold ( ${}^{\circ}$ )	$f r$ ( ${}^{\circ}$ )		Simple	Incremental	Red-green	Interpolatory	The proposed
						triangulation	subdivision	triangulation	scheme	method
Rabbit	902	5	10	5	Num	62882	88196	66470	139826	50924
					MDA	3.317	2.719	3.190	2.967	3.020
Pig	1208	5	10	5	Num	64508	88632	68238	150438	58638
					MDA	3.462	2.864	3.335	3.748	3.391
Horse	1848	5	10	5	Num	68526	90914	69710	91162	67552
					MDA	3.377	2.828	3.287	3.604	3.220
Hand	3026	5	10	5	Num	51084	75156	53908	98846	48178
					MDA	3.298	2.641	3.194	3.411	3.301
Bones	4204	5	20	10	Num	69128	109188	73858	199260	66536
					MDA	6.179	4.632	5.849	6.760	5.983
Teddy	3192	5	10	5	Num	84968	128426	92388	254698	76084
					MDA	3.123	2.442	2.974	4.550	3.193
Cup	1500	6	10	5	Num	51010	75694	56596	204230	47658
					MDA	2.777	2.203	2.641	3.300	2.470
Cow	5804	5	20	10	Num	55956	88012	60506	137128	51530
					MDA	6.137	4.592	5.801	6.641	6.144
Dinosaur	4000	5	20	10	Num	57872	89376	62032	170590	51310
					MDA	6.387	4.876	6.024	6.410	6.303
Bearing	3322	5	10	5	Num	98556	152922	103750	539792	68886
					MDA	2.906	1.984	2.6824	5.204	2.745
Screw	7486	3	30	15	Num	138492	155806	121918	178398	106706
					MDA	12.592	10.040	13.285	19.732	11.935

•

Threshold: To obtain a smooth mesh model with an acceptable number of faces, the threshold of different meshes are set according to their face number and inherent smoothness, as shown in Table 2. And the threshold of the proposed method is always changing in the optimization process.

•

Subdivision level (individual vector length $d$ ): The subdivision level would also influence the subdivision performance, which would be set according to the face number and inherent smoothness of the original mesh. To verify the effectiveness of the proposed method, the subdivision level of the ordinary methods and the proposed method are set to be the same.

According to the practical implementation, there are only 3 parameters that need to be set manually in the proposed optimization process, including the floating range $f r$ , the population size $N_{p}$ , and the distribution index $\eta_{c}$ .

•

$f r$ : The floating range is utilized to generate the random initial population. A large floating range could increase the population diversity, while lower the convergence speed. In this paper, $f r$ is set to 5/10/15 according to the thresholds.

•

$N_{p}$ : The population size affects diversity, computational cost, and convergence accuracy. Large population size will increase the population diversity and improve the convergence accuracy; however, it also increases the running time. To balance the contradiction between population diversity and computational cost, $N_{p}$ is set to 30.

•

$\eta_{c}$ : The distribution indexes $\eta_{c}$ would determine the distribution of children solutions. If $\eta_{c}$ is too large, the children solutions would distribute near the parent solutions, lowering the population diversity. In contrast, if $\eta_{c}$ is too small, there will be too much diversity of offspring, and the computational efficiency would also be lower. $\eta_{c}$ is set as 0.8, 0.9, and 1 to test the influence of different parameters on Pareto front distribution. According to the experimental results, $\eta_{c}$ is set as 0.8.

It is worth mentioning that the experimental results in Table 2 are the average of 3 times of experiments.

5.2 The comparison of crack-solving effect

Figure 8.

Comparison of the crack-solving effect of simple triangulation, incremental subdivision, red-green triangulation, and our method, where the first line shows the results of the subdivision level 1, the second line shows the results of the subdivision level 2, and so on. In this experiment, the threshold is set as 10 ${}^{\circ}$ .

The crack-solving method will affect the connectivity and valence of the odd vertices, which are important for evaluating the quality of subdivided mesh models. Here, a simple experiment is conducted to compare the crack-solving effect of several methods. The manifold mesh model ‘Pig’ is selected as the test mesh, and the parameters setting of the proposed method is consistent with other methods. Figure 8 shows the distribution of faces in subdivision processes obtained by simple triangulation [24, 23], incremental subdivision [27, 28], red-green triangulation [25, 26], and the proposed method. It can be seen clearly that there are a lot of high valence vertices and extraordinary vertices in the results of simple triangulation. Compared with it, the faces are distributed more evenly in the results of other methods.

Furthermore, the valence of vertices is got accounted to compare these methods quantitatively. Figure 9 lists the valence comparison plots of mesh ‘Pig’, ‘Bone’, ‘Horse’ and ‘Dinosaur’, in which the vertices are divided into different classes according to their valence (the proportions of the other valences are too small, so they did not show in this figure).

Figure 9.

The comparison of the valence of vertices, where the horizontal axis represents the valence and the vertical axis represents the proportion of vertices with different valences.

Figure 10.

The Pareto front of four representative mesh models, where the green lines represent the optimization results of the proposed WOA/NSGA-II, and the dots with other colors represent the results of the other subdivision methods.

Figures 8 and 9 confirm that the most serious problem of simple triangulation is that it will produce high valence vertices, lowering the crack-solving effect and the smoothness. In contrast, the effectiveness of red-green triangulation is much better, which could avoid high valence vertices. However, it requires a complex hierarchical data structure to hold the previous states of vertices and faces to implement the recursion check. In this way, this method is computationally expensive. The implementation of the incremental subdivision is easier and more effective. However, it will produce much more faces in the process of removing the cracks. From Fig. 8, the face number of the incremental subdivision is about 1.3 times that of simple triangulation, which will occupy more storage space.

Compared with the previous methods, the superiority of the proposed method is obvious. First, as shown in Fig. 8, the faces are distributed evenly and well in the results of the proposed method, and there are almost no vertices with high valence and long faces with ripple. In addition, from Fig. 9, the ordinary vertices proportions of the proposed method are the same as or even better than that of the red-green triangulation and the incremental subdivision. All of these demonstrate that the proposed method can achieve the same or even better subdivision performance than the previous methods. Second, the proposed method only needs to search the adjacent faces of the selected region to remove the cracks, which is simpler and more efficient. Finally, compared with the incremental subdivision, the proposed method greatly reduces the number of added faces. To sum up, the proposed method could achieve a relatively good subdivision effect and overcome the problems existing in the previous methods.

5.3 The subdivision performance

In this subsection, the experiments are conducted to evaluate the subdivision performance of the proposed method, and the results are compared with the simple triangulation [24, 23], red-green triangulation [25, 26], incremental subdivision [27, 28], and interpolatory scheme [22, 23]. Here, the subdivision level of all methods is the same, and the thresholds of the proposed method are obtained by the optimization process while the other methods have the same thresholds. Table 2 lists the experimental results of the surface smoothness and the faces number, in which the results of the proposed method are only part of the results of the entire Pareto set. In most cases, when the smoothness of the subdivided mesh models is almost the same, the proposed method can greatly reduce the number of the added faces. In other cases, when the faces numbers of the mesh models are almost the same, the proposed method could achieve better smoothness.

Table 3
The comparison of running time. The experimental setting and relative parameters are consistent with those in Table 2, in which Simple denotes the running time of simple triangulation, Incre denotes the incremental subdivision, R-g denotes the red-green triangulation, Inter denotes the interpolatory scheme, Our denotes the proposed method. The running time of the proposed method includes the running time of a complete subdivision process and the running time of the whole optimization process

Mesh	Simple	Incre	R-g	Inter	Our
	T(s)	T(s)	T(s)	T(s)	T(s)	All T(s)	Iter
Rabbit	4.38	5.87	4.68	7.88	3.80	702.68	5
Pig	4.96	6.51	5.22	8.83	4.97	1086.36	4
Hand	5.01	7.02	5.27	7.79	5.14	1070.93	7
Bones	6.85	10.18	7.27	14.03	8.17	1663.79	4
Teddy	6.72	9.61	7.25	14.56	7.48	987.85	4
Cup	4.40	6.18	4.78	10.98	4.72	992.91	6
Cow	5.89	8.47	6.10	10.75	5.57	2015.97	8
Dinosaur	5.95	8.74	6.42	13.15	6.13	1269.80	5
Bearing	7.12	11.01	7.80	23.94	6.60	1590.98	6

To demonstrate the advantages of the proposed improved subdivision method statistically, more experiments are conducted on some models, including the mesh ‘Teddy’, ‘Pig’, ‘Rabbit’, and ‘Cup’. The distribution of the entire Pareto sets is shown in Fig. 10, where each subfigure includes three Pareto fronts of optimization. It can be seen that, in most cases, the results of the ordinary subdivision methods are all above on the Pareto front, which proves that the proposed improved subdivision method indeed optimizes the smoothness and face number simultaneously.

Table 4

The visual comparison of subdivision results

Original	Simple	Incremental	Red-green	Interpolatory	Our
mesh model	triangulation	subdivision	triangulation	schemes	method

5804 faces	55956 faces	88012 faces	60506 faces	137128 faces	51530 faces
	Smoothness $=$ 6.137	Smoothness $=$ 4.592	Smoothness $=$ 5.801	Smoothness $=$ 6.641	Smoothness $=$ 6.144

3026 faces	51084 faces	75156 faces	53908 faces	98846 faces	48178 faces
	Smoothness $=$ 3.298	Smoothness $=$ 2.641	Smoothness $=$ 3.194	Smoothness $=$ 3.411	Smoothness $=$ 3.301

1500 faces	51010 faces	75694 faces	56596 faces	204230 faces	47658 faces
	Smoothness $=$ 2.777	Smoothness $=$ 2.203	Smoothness $=$ 2.641	Smoothness $=$ 3.300	Smoothness $=$ 2.470

4204 faces	69128 faces	109188 faces	73858 faces	199260 faces	66536 faces
	Smoothness $=$ 6.179	Smoothness $=$ 4.632	Smoothness $=$ 5.849	Smoothness $=$ 6.760	Smoothness $=$ 5.893

To further verify the performance of the proposed method, the experiments are conducted on two real mesh models ‘Screw’ and ‘Bearing’, obtained from mechanical engineering and a benchmark of 3D [76]. The comparison of the smoothness and the number of faces is shown in Table 2. From Table 2, the proposed method could obtain better subdivision performance, proving that the proposed method is also appropriate for realistic 3D meshes. Figure 11 shows their subdivision process, through several subdivision iterations, the proposed method could obtain a good simulation.

Figure 11.

The subdivision process of mesh ‘Screw’ and mesh ‘Bearing’, in which (a) is the original mesh ‘Screw’, (b)-(d) are its results of subdivision level 1-3, respectively, (e) is the original mesh ‘Bearing’, and (f)-(h) are its results of subdivision level 3-5, respectively.

5.4 The analysis of the optimization algorithms

5.4.1 The comparison of optimization algorithms

Here, a controlled experiment is conducted to verify the optimization performance of the proposed WOA/NSGA-II, in which the experiment setting is the same as that of the experiment in Subsection 5.3, but the optimization algorithms are different, including the original NSGA-II, MOPSO, SPEA2, NSGA-III. The Pareto fronts of several methods are shown in Fig. 12. Moreover, we list the average of Pareto solution set and the corresponding standard deviation, which are shown in Table 5. To demonstrate the effectiveness of the proposed WOA/NSGA-II, the hypervolume indicator [77] is adopted to validate the performance of the Pareto solution set, where the results of objective functions are normalized to the range $[0,1]$ , and the reference point is set to $[1.1,1.1]$ . The hypervolume is defined as the area enclosed by all points in the solution set $S$ and the reference point in the target space, and if $S_{1}$ ’s hypervolume is larger than that of $S_{2}$ , the solution set $S_{1}$ is better than solution set $S_{2}$ . The results are shown in Table 5. Compared with the other methods, the hypervolume of the proposed WOA/NSGA-II is the largest for all meshes, indicating the proposed WOA/NSGA-II does improve the optimization performance and is more suitable for the proposed improved adaptive mesh subdivision problem.

Considering the above indicators, compared with the other methods, the proposed WOA/NSGA-II does improve the optimization performance, indicating that it is more suitable for the improved adaptive mesh subdivision problem.

Table 5
The comparison of average values of each objective function

Mesh	Algorithm	MDA		Num		Hypervolume
		Avg.	Std.	Avg.	Std.	Avg.	Std.
Cup	NSGA-II	2.60	6.82e-2	82323.87	4895.84	0.60	8.85e-2
	NSGA-III	2.81	7.21e-2	59593.15	5763.92	0.73	6.92e-3
	MOPSO	3.12	4.03e-2	57128.00	4388.37	0.75	8.46e-2
	SPEA2	2.54	7.15e-2	66415.68	4700.66	0.68	1.45e-1
	WOA/NSGA-II	2.49	6.83e-2	56883.33	4508.83	0.77	2.50e-3
Rabbit	NSGA-II	3.32	8.80e-1	97755.27	2938.02	0.77	5.81e-2
	NSGA-III	3.29	9.74e-2	78929.20	3457.47	0.72	1.25e-1
	MOPSO	3.32	6.55e-2	70581.13	2446.14	0.76	9.41e-2
	SPEA2	3.31	1.17e-1	73414.80	2513.60	0.64	7.32e-1
	WOA/NSGA-II	3.31	8.43e-2	71480.11	2383.22	0.78	1.22e-2
Teddy	NSGA-II	3.21	9.72e-2	105415.8	4742.09	0.74	1.80e-2
	NSGA-III	3.54	9.90e-2	96699.40	4448.18	0.78	4.31e-3
	MOPSO	3.14	7.95e-2	93911.60	3817.27	0.73	4.29e-1
	SPEA2	3.30	1.21e-1	80107.05	4941.22	0.68	3.12e-2
	WOA/NSGA-II	3.03	9.72e-2	91814.90	4712.80	0.80	1.05e-1
Pig	NSGA-II	3.20	1.92e-1	83670.90	10416.18	0.78	2.66e-1
	NSGA-III	3.10	2.30e-1	92299.90	11749.41	0.77	3.27e-1
	MOPSO	3.20	1.75e-1	85136.83	9052.40	0.76	9.89e-2
	SPEA2	3.06	2.72e-1	91325.70	11086.26	0.78	1.50e-1
	WOA/NSGA-II	3.12	2.07e-1	74986.17	10067.17	0.81	1.43e-1

Figure 12.

The optimization performance of different kinds of optimization algorithms.

5.4.2 The effectiveness of the optimizer

Although the above experiments show that using optimization algorithms can obtain better subdivision results, it is still necessary to verify whether other types of thresholds can achieve the same effect. Therefore, a simple control experiment is conducted to test the effects of different kinds of threshold sequences. Here, the mesh ‘Pig’ is utilized as the test mesh, and the subdivision level is set to 5. Threshold sequences include the optimal threshold sequence obtained by optimization algorithms, constant thresholds $10^{\circ}$ , $20^{\circ}$ , linear varying threshold sequences $20^{\circ}-2^{\circ}*t$ , $20^{\circ}-3^{\circ}*t$ , $30^{\circ}-2^{\circ}*t$ , $30^{\circ}-3^{\circ}*t$ , $30^{\circ}-5^{\circ}*t$ ( $t$ is the iteration number), and random threshold sequences. Figure 13 shows the results with and without optimization, where the results without optimization methods are also connected into a curve. The results show that the performance of using the optimizer is much better, indicating that it is necessary to use the optimizer.

Figure 13.

The subdivision effect of different kinds of thresholds.

5.5 Posteriori decision based on user’s preference

To facilitate the ordinary users choosing the appropriate solution from the Pareto solution set, a preference function is constructed to reflect the users’ requirements.

$\displaystyle Q(\alpha)=\alpha\times\frac{\textit{MDA}-\min(\textit{MDA})}{% \max(\textit{MDA})-\min(\textit{MDA})}$ $\displaystyle+(1-\alpha)\times\frac{\textit{Num}-\min(\textit{Num})}{\max(% \textit{Num})-\min(\textit{Num})},$ (20)

where MDA reflects the smoothness, Num reflects the number of faces, and $\alpha$ refers to users’ preference. By normalizing the two objective functions MDA and Num, they are unified to the same dimension.

In a minimization problem, if the user more emphasizes some target, he will want the value of this target smaller. Therefore, for the proposed improved subdivision problem, there are two typical users’ preferences as follows.

•

If the users put more emphasis on the smoothness and can accept a relatively large storage space, they should set $\alpha>0.5$ , and gradually increase $\alpha$ according to the importance of the smoothness.

•

If the users put more emphasis on the storage space and don’t have too many requirements for the smoothness, they should set $\alpha<0.5$ , and gradually decrease $\alpha$ according to the importance of storage space.

Actually, for the mesh subdivision tasks, its fundamental purpose is to improve the smoothness of the mesh surface, and the storage space is an additional consideration. Therefore, it will be a good choice to select the suitable smoothness range first, and then select the solution with a smaller number of faces in the corresponding solutions from the Pareto front.

5.6 Computational complexity

The proposed method is implemented in C++. The time is measured on the Intel Core i5-10400F CPU 2.90 GHz. To compare the computational complexity of several approaches in detail, their CPU running time is listed in Table 3. Table 3 confirms that in the subdivision process, the running time is closely related not only to the number of faces and the smoothness in the original mesh models but also to the threshold sequences. In each subdivision process, the operations such as inserting vertices, re-positioning vertices, and solving the cracks are all linear. Therefore, the time complexity of the subdivision process is $O(n)$ . For the optimization process, the running time is proportional to the iteration count and population size.

Besides, different methods have different computational complexity. From Table 3, for all meshes, the running time of simple triangulation is basically the shortest, while the interpolatory scheme needs additional operations to maintain the position of vertices stable, so it generates more faces and consumes a longer time. The incremental subdivision will generate more faces than the red-green triangulation, therefore the running time of incremental subdivision is longer than that of red-green triangulation. Compared with ordinary methods, our method costs more time because of the optimization process, and once found the optimal threshold sequence, the running time of the subdivision process of our method would be also very short. It is worth mentioning that our algorithm terminates due to the convergence of the fitness functions. Therefore, the proposed method is still practical to obtain a high-quality subdivided mesh model to meet the requirements of users.

6. Conclusions

This paper presents a novel adaptive Loop subdivision method via multi-objective optimization, which has three main advantages: 1) a novel crack-solving method that can remove the crack efficiently and save storage space; 2) an adaptive Loop subdivision method with variable thresholds that can balance the smoothness and the number of faces; and 3) a WOA/NSGA-II-based optimization method that can effectively compute the Pareto front. In particular, the proposed method is very effective for small-scale coarse models with less sharp features.

In future work, we will further extend this research by: 1) accelerating the proposed adaptive subdivision method with GPU; 2) adapting neural networks to 3D mesh processing; and 3) extending the proposed algorithm to more multimedia applications.

Footnotes

Acknowledgments

This work is supported by the National Natural Science Foundation of China (Grant No. 62072348), the Science and Technology Major Project of Hubei Province (Next-Generation AI Technologies) (Grant No. 2019AEA170), and Translational Medicine and Interdisciplinary Research Joint Fund of Zhongnan Hospital of Wuhan University (Grant No. ZNJC201917).

References

Krichenbauer

Yamamoto

Taketomi

Sandor

Kato

. Augmented reality versus virtual reality for 3D object manipulation. IEEE Transactions on Visualization and Computer Graphics. 2018; 24(2): 1038-1048.

Egger

Smith

WAP

Tewari

Wuhrer

Zollhoefer

Beeler

, et al. 3D morphable face models – past, present, and future. ACM Transactions on Graphics. 2020; 39(5).

Bauchet

Lafarge

. Kinetic shape reconstruction. ACM Transactions on Graphics. 2020; 39(5): 1-14.

Yang

Yan

Xiao

. Surface reconstruction via fusing sparse-sequence of depth images. IEEE Transactions on Visualization and Computer Graphics. 2017; 24(2): 1190-1203.

Yan

Yang

Liao

Xiao

. Texture mapping for 3D reconstruction with RGB-D sensor. in: CVPR 2018. 2018; 4645-4653.

Min

Xiao

Bao

. Mobile landmark search with 3D models. IEEE Transactions on Multimedia. 2014; 16(3): 623-636.

Paturkar

Gupta

Bailey

. 3D reconstruction of plants under outdoor conditions using image-based computer vision. in: communications in computer and information science,recent trends in image processing and pattern recognition – 2nd international conference. 2018; 284-297.

Chen

Zhu

Cohen-Or

Shamir

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

Liu

. Fast and adaptive 3D reconstruction with extensively high completeness. IEEE Transactions on Multimedia. 2017; 19(2): 266-278.

10.

Hanocka

Metzer

Giryes

Cohen-Or

. Point2Mesh: A self-prior for deformable meshes. ACM Transactions on Graphics. 2020; 39(4).

11.

Henderson

Ferrari

. Learning single-image 3D reconstruction by generative modelling of shape, pose and shading. International Journal of Computer Vision. 2020; 128(4): 835-854.

12.

Marinic-Kragic

Perii

Vuina

Urkovi

. Superimposed RBF and B-spline parametric surface for reverse engineering applications. Integrated Computer-Aided Engineering. 2019; 27(1): 17-35.

13.

Zuo

Wang

Zheng

Cheng

. SparseFusion: Dynamic human avatar modeling from sparse RGBD images. IEEE Transactions on Multimedia. 2020; 99.

14.

Liu

HTD

Kim

Chaudhuri

Aigerman

Jacobson

. Neural subdivision. ACM Transactions on Graphics. 2020; 39(4).

15.

George, Merrill, Chaikin. An algorithm for high-speed curve generation. Computer Graphics & Image Processing. 1974; 3(4): 346-349.

16.

Catmull

Clark

. Recursively generated b-spline surfaces on arbitrary topological meshes. Computer Aided Design. 1978; 10(6): 350-355.

17.

Doo

Sabin

. Behaviour of recursive division surfaces near extraordinary points. Computer Aided Design. 1978; 10(6): 356-360.

18.

Loop

. Smooth subdivision surface based on triangles. Master’s thesis, Department of Mathematic, University of Utah, USA. 1987.

19.

Dyn

Levine

Gregory

. A butterfly subdivision scheme for surface interpolation with tension control. ACM Transactions on Graphics. 1990; 9(2): 160-169.

20.

Kobbelt

. 3-subdivision. in: Proceedings of the ACM SIGGRAPH Conference on Computer Graphics. 2000; 103-112.

21.

Florea

Munteanu

Schelkens

. Wavelet-based L∞ semi-regular mesh coding. IEEE Transactions on Multimedia. 2017; 19(2): 236-250.

22.

Shi

Lin

Luo

Wang

. Interpolatory and mixed loop schemes. Computer Graphics Forum. 2008; 27(7): 1829-1835.

23.

Shi

Wang

Zhong

Lan

, et al. A fast and accurate dihedral interpolation loop subdivision scheme. in: Ninth International Conference on Graphic and Image Processing (ICGIP 2017). 2018; 120.

24.

Amresh

Farin

Razdan

. Adaptive subdivision schemes for triangular meshes. in: Hierarchical and Geometrical Methods in Scientific Visualization. 2003; 319-327.

25.

Bank

Sherman

Weiser

. Some refinement algorithms and data structures for regular local mesh refinement. Journal of Scientific Computing. 1983; 3-17.

26.

Koschier

Lipponer

Bender

. Adaptive tetrahedral meshes for brittle fracture simulation. in: Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 2015; 57-66.

27.

Pakdel

Samavati

. Incremental subdivision for triangle meshes. International Journal on Computer Science and Engineering. 2007; 3(1): 80-92.

28.

Husain

Rahim

MSM

Al-Rodhaan

Khan

Al-Dhelaan

. Iterative adaptive subdivision surface approach to reduce memory consumption in rendering process (IteAS). Journal of intelligent and fuzzy systems: Applications in Engineering and Technology. 2015; 28(1).

29.

Karciauskas

Peters

. A new class of guided C2 subdivision surfaces combining good shape with nested refinement. Comput Graphics Forum. 2018; 37(6): 84-95.

30.

Zorin

Schroder

Sweldens

. Interpolating subdivision for meshes with arbitrary topology. in: SIGGRAPH 1996. 1996; 189-192.

31.

Kobbelt

. Interpolatory subdivision on open quadrilateral nets with arbitrary topology. Comput Graphics Forum. 1996; 15: 409-420.

32.

Floater

Micchelli

. Nonlinear stationary subdivision. Journal of Approximation Theory. 1998.

33.

Schaefer

Vouga

Goldman

. Nonlinear subdivision through nonlinear averaging. Computer Aided Geometric Design. 2008; 25(3): 162-180.

34.

Vaxman

Müller

Weber

. Canonical möbius subdivision. ACM Transactions on Graphics. 2018; 37(6): 1-15.

35.

Preiner

Boubekeur

Wimmer

. Gaussian-product subdivision surfaces. ACM Transactions on Graphics. 2019; 38(4).

36.

Sabin

Dodgson

. A circle-preserving variant of the fourpoint subdivision scheme. in: Mathematical Methods for Curves and Surfaces: Tromsø 2004, Modern Methods in Mathematics. Nashboro. 2005; 275-286.

37.

Bobenko

Pottmann

, Rö rig

. Multi-Nets. Classification of discrete and smooth surfaces with characteristic properties on arbitrary parameter rectangles. Discrete and Computational Geometry. 2020; 63(3): 624-655.

38.

Rabinovich

Hoffmann

Sorkine-Hornung

. The shape space of discrete orthogonal geodesic nets. ACM Transactions on Graphics. 2018; 37(6).

39.

Kim

Jeong

Kim

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

40.

Huang

Feng

Nießner

Cui

Yang

. Feature-adaptive rendering of loop subdivision surfaces on modern GPUs. Journal of Computer Science and Technology. 2014; 29(6): 1014-1025.

41.

Niessner

Loop

Meyer

Derose

. Feature-adaptive GPU rendering of catmull-clark subdivision surfaces. ACM Transactions on Graphics. 2012; 31(4CD): 1-11.

42.

Luo

Zeng

Liang

. A novel whale optimization algorithm with filtering disturbance and non-linear step. International Journal of Bio-Inspired Computation. doi: 10.1504/IJBIC202010036562.

43.

Soubhik, Chakraborty. Nature-inspired computing: Physics and chemistry-based algorithms. Computing Reviews. 2018.

44.

Siddique

Adeli

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

45.

Hossain

Akhand

MAH

Shuvo

MIR

Siddique

Adeli

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

46.

Yan

Zhang

Xie

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

47.

Chen

Pan

. MLFS-CCDE: Multi-objective large-scale feature selection by cooperative coevolutionary differential evolution. Memetic Computing. 2021; 13(1).

48.

Lee

Chew

. Multi-objective compass for discrete optimization via simulation. in: Proceedings of the 2011 Winter Simulation Conference, WSC 2011. 2011; 4070-4079.

49.

Liang

Zeng

. 3D mesh simplification with feature preservation based on whale optimization algorithm and differential evolution. Integrated Computer-Aided Engineering. 2020; 27(4): 417-435.

50.

Zhang

. DRCDN: Learning deep residual convolutional dehazing networks. The Visual Computer. 2020; 36(9): 1797-1808.

51.

Thurnhofer-Hemsi

Lopez-Rubio

Roe-Vellve

Molina-Cabello

. Multiobjective optimization of deep neural networks with combinations of Lp-norm cost functions for 3D medical image super -resolution. Integrated Computer-Aided Engineering. 2020; 27(3): 233-251.

52.

Quan

. A multi-phase blending method with incremental intensity for training detection networks. The Visual Computer. 2021; 37(2): 245-259.

53.

Tang

Leung

Tong

Vasilakos

Qian

. Robust order scheduling in the fashion industry: A multi-objective optimization approach. IEEE Transactions on Industrial Informatics. 2018; 14(1): 253-264.

54.

Thurnhofer-Hemsi

López-Rubio

Roé-Vellvé

Molina-Cabello

. Multiobjective optimization of deep neural networks with combinations of Lp-norm cost functions for 3D medical image super-resolution. Integrated Computer-Aided Engineering. 2020; 27(3): 233-251.

55.

Cai

Cheng

. A semi-transparent selective undo algorithm for multi-user collaborative editors. 2021; 15(5): 155209.

56.

Sarma

Adeli

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

57.

Sarma

Adeli

. Bilevel parallel genetic algorithms for optimization of large steel structures. Computer-Aided Civil and Infrastructure Engineering. 2001.

58.

Sarma

Adeli

. Life-cycle cost optimization of steel structures. International Journal of Numerical Methods in Engineering. 2002; 55(12): 1451-1462.

59.

Soto

Adeli

. Many-objective control optimization of high-rise building structures using replicator dynamics and neural dynamics model. Structural and Multidisciplinary Optimization. 2017; (1): 1-17.

60.

Soto

Adeli

. Vibration control of smart base-isolated irregular buildings using neural dynamic optimization model and replicator dynamics. Engineering Structures. 2018; 156: 322-336.

61.

Soto

Adeli

. Semi-active vibration control of smart isolated highway bridge structures using replicator dynamics. Engineering Structures. 2019; 186: 536-552.

62.

Wei

Jin

Yang

. Strategic network expansion of urban rapid transit systems: A bi-objective programming model. Computer-Aided Civil and Infrastructure Engineering. 2019; 34(5): 431-443.

63.

Song

Schonfeld

Zhang

Wang

. Mountain railway alignment optimization considering geological impacts: A cost-hazard bi-objective model. Computer-Aided Civil and Infrastructure Engineering. 2020.

64.

Zitzler

Laumanns

Thiele

. SPEA2: Improving the strength pareto evolutionary algorithm. Technical Report Gloriastrasse. 2001.

65.

Deb

Agrawal

Pratap

Meyarivan

. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. in: 6th International Conference on Parallel Problem Solving from Nature, PPSN 2000. 2000; 1917; 849-858.

66.

Zhang

. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation. 2007; 11(6): 712-731.

67.

Chen

Zhang

. A full migration BBO algorithm with enhanced population quality bounds for multimodal biomedical image registration. Applied Soft Computing. 2020; 93: 106335.

68.

Vieira

Mendonça

Farinha

Sousa

JMC

. Modified binary PSO for feature selection using SVM applied to mortality prediction of septic patients. Applied Soft Computing Journal. 2013; 13(8): 3494-3504.

69.

Pepyne

. Simple explanation of the no-free-lunch theorem and its implications. Journal of Optimization Theory and Applications. 2002; 115(3): 549-570.

70.

Wang

Gandomi

Yang

Alavi

. A new hybrid method based on krill herd and cuckoo search for global optimisation tasks. International Journal of Bio-Inspired Computation. 2016; 8(5): 286-299.

71.

Seyedali

Andrew

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

72.

Aljarah

Faris

Mirjalili

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

73.

Mostafa

Hassanien

Houseni

Hefny

. Liver segmentation in MRI images based on whale optimization algorithm. Multimedia Tools and Applications. 2017; 76(23): 24931-24954.

74.

Mafarja

Mirjalili

. Whale optimization approaches for wrapper feature selection. Applied Soft Computing. 2017; 62.

75.

Zhou

Jacobson

. Thingi10K: A dataset of 10,000 3D-printing models. arXiv.2016.

76.

Chen

Golovinskiy

Funkhouser

. A benchmark for 3D mesh segmentation. ACM Transactions on Graphics (Proc SIGGRAPH). 2009; 28(3).

77.

Zitzler

Brockhoff

Thiele

. The hypervolume indicator revisited: On the design of pareto-compliant indicators via weighted integration. in: Evolutionary Multi-Criterion Optimization, EMO. 2007; 862-876.

An improved loop subdivision to coordinate the smoothness and the number of faces via multi-objective optimization

Abstract

Keywords

1. Introduction

2.1 Mesh subdivision

2.1.1 Linear subdivision methods

2.1.2 Non-linear subdivision methods

2.2 Adaptive subdivision

2.3 Handling inconsistencies

3.1 Preliminaries

3.4 An improved adaptive subdivision method

3.4.1 Optimization fitness functions

4.1 The proposed WOA/NSGA-II

4.2 Optimizing the mesh subdivision process with WOA/NSGA-II

4.2.1 Initialization

5. Experiments

5.1 Implementation details

Table 1 The list of parameters

5.4.1 The comparison of optimization algorithms

Table 5 The comparison of average values of each objective function

6. Conclusions

Footnotes

Acknowledgments

References

Table 1
The list of parameters

Table 5
The comparison of average values of each objective function