Dawar KhanDong-Ming YanFan DingYixin Zhuangand Xiaopeng Zhang

Abstract Surface remeshing is widely required in modeling, animation, simulation, and many other computer graphics applications.Improving the elements’quality is a challenging task in surface remeshing.Existing methods often fail to efficiently remove poor-quality elements especially in regions with sharp features. In this paper,we propose and use a robust segmentation method followed by remeshing the segmented mesh.Mesh segmentation is initiated using an existing Live-wire interaction approach and is further refined using local mesh operations. The refined segmented mesh is finally sent to the remeshing pipeline,in which each mesh segment is remeshed independently.An experimental study compares our mesh segmentation method as well as remeshing results with representative existing methods.We demonstrate that the proposed segmentation method is robust and suitable for remeshing.

Keywords mesh generation;mesh segmentation;surface remeshing;triangulation

1 Introduction

In computer graphics,surface meshes are typically used for shape representation.However,these meshes are frequently generated in raw form,and as a result contain poor-quality elements.Furthermore,meshes generated,e.g.,from the output of automated laser scanning,are prone to errors.Such raw meshes are difficult to use directly in downstream applications.Thus,remeshing is useful at this stage to improve mesh quality[1].

A critical target for surface remeshing is feature preservation. Feature analysis and identification remain challenging problems because a rigorous definition of features for general objects is lacking despite extensive studies on these topics.In many remeshing algorithms,a user-given feature skeleton is required as an input for use in feature preservation[2,3].Several approaches include efficient feature functions for implicit feature preservation[4,5].These approaches can efficiently handle models,such as CAD models and man-made objects with clearly defined features,or models without minimal local features. Standard approaches still cannot automatically handle models with thin and sharp features.

Input meshes are typically segmented before remeshing to address the problem caused by thin and sharp features[2,6].Segmentation boundaries should split such thin and sharp regions into patches.Then,each patch is remeshed independently and they are finally stitched together.Two main problems,segmentation and stitching,must be solved in this type of approach. Automatic algorithms perform segmentation by grouping triangles,and the segmentation boundaries are defined by original edges of the input.Such boundaries are irregular if the input mesh quality is low,also affecting the final stitched result.

This study aims to improve the segmentation and remeshing outputs yet with minimal user input.The proposed method operates in two phases,mesh segmentation and surface remeshing.The segmentation method is based on active user interaction.The input mesh is segmented according to user-guided segmentation boundaries or curves.The segmentation boundaries are drawn by the user using Live-wire[7],which is especially useful for sharp-featured models.Live-wire is only used for drawing boundaries,and the mesh is segmented using the proposed method.The triangles touching the user-guided segmentation curves are processed with basic operations,including vertex relocation,edge flipping,edge splitting,edge collapsing,and face labeling.These operations are iterated until a robust segmentation is reached.Constraints are applied to avoid small triangles and prevent mesh structure destruction.Thus,we achieve a segmented mesh with only minor changes to the complexity,quality,and structure of the input mesh.The main contributions of this study are as follows:

?a robust segmentation mechanism that divides an input mesh following user-guided segmentation boundaries;

?a method of producing a segmented mesh with minor(negligible)changes in complexity and structure to the input mesh,which does not introduce small angles near the segmentation curves,thus providing a meaningful and more suitable segmentation for surface remeshing;

?a segment-based surface remeshing method with additional local region operators,which can generate a high-quality mesh.

2 Related work

The literature provides numerous surface remeshing methods.For example,representative works include mesh simplification-based methods[8,9],advancingfront-based method [10], Delaunay insertion methods[11], field-based approaches[12–14],and mesh optimization with either local operations[15–18]or global energy minimization. Global optimization approaches can be further classified as parametrization-based methods[2,19,20],discrete clustering methods[4],and direct 3D optimization methods[3,21–27].In this section,we brie fly review those remeshing methods most closely related to our proposed method,focusing on feature preservation.Alliez et al.[1]present a detailed study on surface remeshing.

The simplest approach to preserving features during remeshing is to predefine feature curves,either by the user or by automatic algorithms(e.g.,using dihedral angles)[3,28]. Such a scheme functions well for models with sharp features,such as CAD models or man-made objects.However,this scheme cannot be applied naturally to free-form objects. Various solutions(e.g.,feature-sensitive remeshing[29],implicit feature preservation[4,5])have been proposed to preserve features for general objects,especially for models with thin and sharp features.However,these solutions do not always successfully handle thin and sharp features,such as the ear of the Elk model.

A consequent remedy is to apply mesh segmentation prior to remeshing. Segmentationbased remeshing methods can be classified into two main types as follows.One type first defines a coarse mesh(or base mesh)over the input mesh,through mesh simplification.Then,the base mesh is mapped back to the original mesh and further subdivided to form a semi-regular output mesh[30].For example,Lee et al.[31]present a unified subdivision framework to approximate an arbitrary surface by a displaced subdivision surface.This scheme is simple but efficient for evaluating surface properties.However,this method may lose sharp features and suffer from distortion at times.Mansouri and Ebrahimnezhad[32]recently present an alternative curvature-adapted subdivision method,which achieves better results with lower distortion error and higher aspect ratios(AR).However,semi-regular remeshing cannot arbitrarily modify the mesh connectivity,which constantly causes distortion in highly curved regions.

The other type of approach first segments the input mesh into patches.Then,each patch is remeshed individually,and all the patches are finally stitched together in a post-processing step.Edwards et al.[6]use variational shape approximation[33]for segmentation and centroidal Voronoi tessellation[3]for remeshing.IsoChart[34],Exoskeleton[35],Livewire[7],and patch layout[36]can also be used to define the feature skeletons of input meshes.

However,the segmentation boundaries are not sufficiently smooth,especially for inputs with thin and poor-quality triangles,because most segmentation algorithms use triangles as primitives for clustering.Such boundaries lead to low triangle quality in the output mesh.A survey paper[37]provides additional details concerning mesh segmentation.In the present study,Live-wire[7]is used for initial segmentation due to its anisotropic nature that automatically captures thin and sharp features.This is followed by a refinement step to straighten the segmentation boundary to improve the remeshing quality after stitching.

3 Method

3.1 Overview

The pipeline of the proposed algorithm is illustrated in Fig.1. The input mesh is provided to Livewire[7];the segmentation curve is generated by user interaction. This segmentation curve along with the input mesh is further processed in the refinement phase.The refinement phase achieves an acceptably segmented mesh that is provided to the remeshing process.The remeshing method generates a high-quality mesh after applying several segmentbased and global operations to the mesh.The two main steps are further described in the following subsections.

3.2 Mesh segmentation

Our segmentation method starts with Live-wire[7]initialization.Live-wire is an efficient technique for curve drawing and mesh segmentation,especially for models with thin and sharp features,such as the lion’s or dog’s ears or the feline’s wings.However,it creates poor-quality elements(with short edges and small angles)near the segmentation curve.

We are not concerned with the segmented mesh produced by Live-wire.Instead,the segmentation curve is simply plotted over the input mesh.This curve leads to a similar segmentation to that provided by Live-wire for faces in the interiors of the segments.However,faces near the segmentation curve remain unlabeled–see the blue faces in Fig.2,which provides an abstract view of the mesh segmentation for a simple example.The leftmost and rightmost subif gures show the segmented meshes produced by Livewire and our method respectively.The central subfigure shows the Live-wire curve plotted in red over the input mesh.

Faces in the interior of the two segments are labeled in a manner similar to the result produced by Live-wire.Faces near the segmentation curve are left unlabeled(blue faces).At this stage,the curve is only a visualization and is not connected to the vertices. The unlabeled faces and their corresponding vertices and edges are processed using basic operations including vertex translation,edge flipping,edge splitting,edge collapsing,and face labeling(see Fig.1).We now brie fly describe each of these operations.

3.2.1Vertex translation

In the first step,we move the nearest vertices of the unlabeled faces to the segmentation curve.A vertexviis translatable to the nearest pointpon the curve if and only if satis fies the following conditions:

?Vertexviis nearest topamong the vertices in its one-ring neighborhood.

?The distance between vertexviand pointpis shorter than 40%of the shortest edge length in the one-ring neighborhood edges of unlabeled faces ofvi.Edges of labeled faces are excluded

Fig.1 Proposed user-guided segmentation with remeshing.In the basic operations(middle),red lines represent segmentation curves and the blue color shows unlabeled faces near the curve.

Fig.2 Simple example of mesh segmentation.Left:Live-wire segmentation includes small triangles near the segmentation boundary.Middle:Live-wire curve(red)plotted over the input mesh;blue triangles are unlabeled.Right:Our final segmentation.

from consideration.This condition helps to avoid distortion in the mesh structure and generation of short edges.

?Vertexvidoes not result in small angles(e.g.,＜20°)when translated top.

Vertices that satisfy these conditions are moved toward the curve,and the affected unlabeled faces are labeled according to their neighborhoods.

3.2.2Face labeling

Face labels determine the segment to which the face belongs.Face labeling is performed in parallel with all four other operations.Our main goal is to label the unlabeled faces in agreement with faces on either side of the curve.A face that lies completely on one side of the curve is labeled with the label of the faces on that side and the face is counted as part of that segment.

3.2.3Edge flipping

Edges that cross the segmentation curve are flipped to join the curve.An edge is flipable if its vertices lie on opposite sides of the curve(see Fig.3(left)).The two faces are labeled accordingly after edge flipping(see Fig.3(right)).Flipable edges are typically found after vertex translation and edge splitting.Edge flipping is executed whenever a flipable edge is found.

3.2.4Edge splitting

The previous steps do not suffice to label all faces as the segmentation curve may cross several non- flipable edges.Edge splitting is used to address this problem.Edge splitting may either be simple,as in Fig.4,or as complex,as in Fig.5.In either case,every second edge is split instead of splitting all edges.In particular,only one edge split is allowed for a single triangle.The remaining edges are treated via flipping and vertex translation.In edge splitting,the edge is split(see Fig.4(b),Fig.5(b))and the resultant new vertex is moved to the nearest point on the curve(see Fig.5(c)).Edge flipping(Fig.4(c),Fig.5(d))and face labeling(Fig.4(d),Fig.5(e))are consequently applied.

3.2.5Edge collapsing

Edge collapse may result in short edges near the curve.If small angles are produced(＜20°),the opposite edge is collapsed.Edge collapse is usually executed only once in the last steps of segmentation.If several edges are collapsed,then the previous steps are repeated(at least once)and the necessary operations are performed.

3.2.6Curve smoothing

Finally,a curve smoothing operation,which attempts to smooth the curve wherever required,is performed after all the faces have been labeled.

Fig.3 Edge flipping.Red:Segmentation curve.Left:Before flipping.Yellow edges are flipable.Centre:After flipping.Right:Face labeling after edge flipping.

3.3 Surface remeshing

Fig.4 Edge splitting(Case I).(a)Before splitting.(b)After splitting.(c)Edge flip.(d)Face labeling.

The next objective is to remesh the surface with a robust segmented mesh to improve quality.Our remeshing framework functions in two phases.Thefirst phase performs segmentation-based remeshing,while we apply global operations in the second phase and disregard the segmentation boundaries.In segmentation-based remeshing,the edges and vertices on the segmentation curve are locked,and each patch is segmented using an existing method:we use realtime adaptive remeshing(RAR)[17],selected as it is comparatively easy to control,simple to implement,and computationally efficient.RAR uses an adaptive sizing functionL(x)to compute the edge lengthLfor each edge.Any edge shorter than 4L/5 is collapsed;any edge longer than 4L/3 is split.The two operations(edge collapsing and edge splitting)along with edge flipping for valance optimization and vertex relocation are repeated;5–10 times are used in the original RAR method.

Initially,the mesh quality is improved without destroying sharp features when the vertices on the curve are locked.The first phase of segment-based RAR execution is repeated 10 times to generate an intermediate mesh. However,this mesh still has small angles and low-quality elements,so it is further processed in the second phase.The vertices on the segmentation boundaries are now unlocked,and further smoothing operations are applied.Each triangle with an angle＜30°is flagged as a bad triangle,and vertices of this triangle and in the onering neighborhood of each of its vertices are flagged as bad vertices;these vertices form a local region around the bad triangle.In each local region,the bad triangle is treated with edge-based operations[5],while the vertices in the local regions are also relocated for quality improvement.We calculate the new positionpias the Laplacian centerciof the one ring aroundviwhen relocating a vertexvi.The vertex is relocated topiif it does not lead to bad angles.Otherwise,the process is repeated with a new value forpiset topi=ci+k·?d,wheredis a small distance calculated asd=1,1/2,1/4,1/6,...,∈for a tiny value∈,whilekrepresents the direction(left,right,up,down,etc.)of vertex movement aroundci.Thus,the optimal position for vertex translation nearciis achieved.These operations are executed until all small angles are removed and a mesh with high-quality results.

Fig.5 Edge splitting and consecutive operations(Case II).(a)Before splitting.(b)After splitting the middle edge.(c)New vertex translated to the curve.(d)Edges flipped.(e)Face labeling.

4 Experiments

4.1 Methodology

In this section,we present experiments performed to evaluate the proposed method. We compare our results with those of the other most relevant segmentation-based methods.We performed the

experiments using an Intel Core i7 at 3.60 GHz with 16 GB RAM and 64-bit Windows 7 operating system.In the following subsections,we measured the remeshing quality in terms ofQminandQavg,the minimal and average triangle quality respectively.For a trianglet,the qualityQ(t)is defined as

whereAtis the area of trianglet,ptis its halfperimeter,andhtis the length of its longest edge[38].

4.2 Segmentation results

We compared our segmentation results with those of Live-wire segmentation[7]by segmenting five mesh models with both methods.Figure 6 illustrates the input and segmented meshes. It shows that no small angles exist near the segmentation curve in our results,while Live-wire results do not have this property.Table 1 summarizes quantitative results.We first give the number of vertices and other mesh quality parameters for the input mesh,and then the same parameters are recorded for the Live-wire mesh and our output mesh.Our segmentation has a comparatively minor change in the number of vertices and other mesh quality parameters.

4.3 Remeshing results

We conducted further experiments by remeshing several models with our own method and the RAR method[17].Both methods were used for uniform and adaptive remeshing.Mesh quality values were recorded for each experiment.The output meshes along with the histograms of the frequency distributions of the aspect ratios(AR)of the triangles are depicted in Figs.7 and 8 for uniform and adaptive meshing respectively.Aspect ratio is widely used in the literature as a parameter for measuring triangle quality[39],and is the ratio of the circumradius of a triangle to twice its inradius:

Fig.7 Remeshing results,uniform density.Triangles with small angle(＜ 30°)are shown in red.Left:RAR results.Right:Our results.

wherea,b,andcare the lengths of the triangle’s edges andS=(a+b+c)/2.The AR for an equilateral triangle is equal to one;a higher AR suggests lower triangle quality.Figures 7 and 8 show that our method significantly improves the ARs of triangles and mesh structure.Models with sharp features such as the lion’s ears,in Fig.7,undergo considerable improvement.

Quantitative results for uniform remeshing are given in Table 2;those for adaptive remeshing are in Table 3.In both cases our results show a significant improvement in mesh quality.

Fig.8 Remeshing results,adaptive mesh.Triangles with small angle(＜ 30°)are shown in red.Left:RAR results.Right:Our results.

5 Conclusions and future work

We have proposed a segmentation-based remeshing framework that obtains a high-quality mesh with good aspect ratios.Our method works in two steps,mesh segmentation and remeshing.The segmentation method considers the segmentation curve as a user input.It generates a segmented mesh with no bad elements near the segmentation curve and only minor changes in mesh structure.In future,we will consider parallelizing of the method.We also hope to improve mesh quality for non-obtuse remeshing.

Table 2 Comparative remeshing results,uniform density

Table 3 Comparative remeshing results,adaptive density

Acknowledgements

This work was partially funded by the National Natural Science Foundation of China(Nos.61772523,61372168,61620106003,and 61331018).The first author was supported by a Chinese Government Scholarship.