Guillaume Gisbert
email: guillaume.gisbert@liris.cnrs.fr

Raphaëlle Chaine
email: raphaelle.chaine@liris.cnrs.fr

David Coeurjolly
email: david.coeurjolly@liris.cnrs.fr

Inpainting Holes In Folded Fabric Meshes

Keywords: Hole Filling, Surface Inpainting, Fabric Reconstruction

When scanning real shapes, occlusion issues may lead to holes in the reconstructed surface which must be solved using an inpainting technique. When dealing with fabrics with folds, reconstruction gets even more challenging because these occlusion problems become almost inevitable and strong assumptions are implied on the physical model of the inpainted surface. We propose a framework to fill holes in triangle mesh surfaces representing fabrics. The method leverages the developable nature of fabrics to recover the intrinsic geometry of the missing patch in 2D. Our inpainting strategy is then based on a variational method to smoothly incorporate the patch into the surface by minimizing an isometric energy. The proposed approach allows us to produce folds and creases which are difficult to obtain with general purpose hole filling techniques. Moreover, our approach remains relevant in the case where the model is not provided by the digitization of a real fabric as for the acquisition from ancient statues with draperies.

challenging task due to the presence of occlusions when capturing a fabric, and it implies a strong prior on the physical model of the inpainted surface, modeled hereafter as as-developableas-possible. In case the region to be completed does not fully correspond to real fabric, as in the case of a hole in the toga of a statue carved in stone, our approach remains valid as long as the developability defect is not too severe.

Loosely speaking, developable surfaces are the ones that can be flattened to the plane without any metric distortion. Developable surfaces meet a number of properties such as a null Gaussian curvature at each point except on crease edges, meaning that the curvature is null in at least one direction which is commonly called the ruling direction. They belong to the family of the ruled surfaces as they are surfaces containing a piece of straight line at each point.

All those properties are rather restrictive about the space of shapes they cover and fabrics do not fully check all of them. Their material usually allows some distortion and stretching which makes them not fully developable. However, we can consider that fibers of a non-elastic fabric correspond to constantlength curves embedded in the surface, hence the use of a con- trolled developability property in our approach. In the follow-

1
ing, we will refer to developable fabrics.

2

Our main contributions are: 1. We propose a method for filling holes in meshes approxi-4 mating a piece of fabric when these holes are homeomor-5 phic to disks. 2. Our approach favors the local developability of the inpaint-

7
ing surface but does not enforce it, allowing for some de-8 gree of distortion and stretching that are typical of clothes.

9

We demonstrate the effectiveness of our method by applying it 10 to holes on a variety of surfaces, including both real-world and

11
synthetic examples. Our results show that our approach can 12 produce high-quality reconstructions of holes in both cloth-like 13 and developable surfaces. Context-based methods. Some methods use the deep learning environment in a clever way allowing them to work solely on the input data. Point2Mesh [START_REF] Hanocka | Point2mesh: A selfprior for deformable meshes[END_REF] is a technique to reconstruct a watertight mesh from an input point cloud by optimizing the weights of a CNN to iteratively deform an initial mesh to shrink-wrap the given point cloud. The convolutional kernels are optimized globally to encourage self-similarities across the entire surface. Similarly, Hattori et al. [START_REF] Hattori | Deep mesh prior: Unsupervised mesh restoration using graph convolutional networks[END_REF] introduced Deep Image Prior, a method that tries to match a noisy mesh to the observed corrupted mesh using a graph convolutional network (CGN). The GCN's weight-sharing nature allows the unknown vertices to be mapped to a convincing surface even though no error metric is measured on them. While these self-prior methods use a deep learning framework, more traditional contextbased methods also exist, such as the work from Harary et al. [START_REF] Harary | Context-based coherent surface completion[END_REF]. For any given hole, several patches are proposed based on a multiscale signature. They introduced a dissimilarity between two patches to establish a coherence error that has to be minimized. Context-based methods are generally rather dependent on the mesh and require to have many features such as the one in the missing area for proper reconstruction.

Implicit surfaces. Modeling the surface as the zero set of an implicit function is a classical tool for many geometry processing tasks such as surface reconstruction or fairing [START_REF] Kazhdan | Poisson surface reconstruction[END_REF][START_REF] Barill | Fast winding numbers for soups and clouds[END_REF]. Specifically for hole filling, Davis et al. [START_REF] Davis | Filling holes in complex surfaces using volumetric diffusion[END_REF] applied a volumetric diffusion process to extend the ambient signed distance function defined by the input surface, into the hole. While this approach is well adapted to geometrically and topologically complex holes, the reconstructed surface is however not guaranteed to blend well with the observed surface. However, the authors propose to adapt the diffusion process to a given problem enforcing some properties (such as curvature). Branch et al. [START_REF] Branch | A hole-filling algorithm for triangular meshes using local radial basis function[END_REF] and Wue et al. [START_REF] Wu | An automatic hole-filling algorithm for polygon meshes[END_REF] use a radial basis function interpolator combined with an iso-surface algorithm to fill the hole.

Because the interpolating function cannot correctly fit surfaces with big holes, this technique is restricted to small areas. We can also mention the work from Tekumalla and Cohen [START_REF] Tekumalla | Reverse engineering point clouds to fit tensor product b-spline surfaces by blending local fits[END_REF] who use moving least square (MLS) instead. Overall, those methods tend to smooth the mesh in the damaged area and cannot render complex material behavior such as folds.

Variational approaches. Baumgärtner et al. [START_REF] Baumgärtner | Mesh denoising and inpainting using the total variation of the normal[END_REF] present an approach to solve mesh denoising and inpainting problems by regularizing the normal vector field using a discrete variant of the total variation. The missing area is first inpainted by solving a minimal surface problem before using their algorithm. This method performs well at preserving sharp features in the mesh.

Pernot et al. [START_REF] Pernot | Filling holes in meshes using a mechanical model to simulate the curvature variation minimization[END_REF] propose to fill holes while minimizing the curvature variation between the observed and inserted mesh. Features are not necessarily preserved but manual constraints can be added to help with the minimization. Bonneel et al.

[16] also begin by recovering the missing mesh [START_REF] Liepa | Filling Holes in Meshes[END_REF] before inferring differential properties on it. They solve a Mumford-Shah problem to obtain piecewise-smooth normals in the inpainted region and conform the mesh to them. These methods generally require a geometry to infer information. They are usually able to capture sharp features and propagate them in the inpainted mesh.

Developable surfaces.

Developable surfaces have been extensively studied in geometry and computer graphics. [17] provides an excellent reminder of the geometric properties of developable surfaces. They are widely used in architectural design, art and product manufacturing because of their aesthetic appeal and their ease of fabrication. In fact, such surfaces can be made by cutting sheets of any flat material and bending them to recreate the desired object. We can also mention that the Gauss map of a developable surface is unidimensional [18]. Typical developable surfaces are cones and cylinders but some more complex shapes like the oloid also fit in this category. For fabrication purposes, many methods [19,20,18] were designed to approximate a given surface by piecewise developable surfaces with a minimum number of pieces. Because of their flattenability, developable surfaces are the perfect choice for modeling some materials such as paper and metal sheet.

Hole-filling with developable constraints. Some holefilling techniques are specifically designed to work with developable surfaces such as the work from Frey [START_REF] Frey | Boundary triangulations approximating developable surfaces that interpolate a closed space curve[END_REF] who proposes to approximate the missing mesh by triangles whose vertices are the boundary points exclusively. They project the boundary on some 2d plane and simulate the bending process to obtain the sheet. Their method is specifically designed for the fabrication of thin, flat sheet materials such as metal and is not suitable for handling fabric materials. Rose et al. [START_REF] Rose | Developable Surfaces from Arbitrary Sketched Boundaries[END_REF] allows the user to draw a 3D polyline and propose a triangulation approximating a smooth developable surface within the polyline. The method is based on the fact that most edges in smooth developable surfaces are locally convex.

Fabric and cloth modeling. Simple triangulations of flat-58 tanable surfaces cannot render complex material behavior even 59 though they can maintain some properties such as developabil-60 ity. Clothes are often modeled as developable surfaces in the 61 sense that they are made from 2D patterns. However, the fab-62 ric usually allows some controlled stretching, making them not 63 exactly developable. To our knowledge, there is no specific in-64 painting approach for fabrics. However, many cloth and fabric 65 models have been developed for simulation purposes. 66 Some models are yarn-level, meaning that every single yarn 67 strand is simulated to produce an animation [START_REF] Yuksel | Stitch meshes for modeling knitted clothing with yarn-level detail[END_REF][START_REF] Sperl | Homogenized yarn-level cloth[END_REF]. These 68 techniques are computationally intensive and require several 69 hours of calculations even for animations of a few seconds, yet, 70 produce high-fidelity cloth representation and allow some be-71 havior observable only with those models. These models excel 72 at rendering knit patterns. More traditional models mesh-based 73 are still able to achieve high fidelity in real-time. Most modern 74 cloth simulation techniques rely on two terms [START_REF] Wu | A safe and fast repulsion method for gpu-based cloth self collisions[END_REF][START_REF] Wang | Gpu-based simulation of cloth wrinkles at submillimeter levels[END_REF][START_REF] Wu | A gpu-based multilevel additive schwarz preconditioner for cloth and deformable body simulation[END_REF]: a 75 planar elasticity term that enforces isometric constraints, com-76 mon choices being mass-spring systems and triangular finite el-77 ement models, and bending elasticity constraints. The quadratic 78 bending model from Bergou et al. [START_REF] Bergou | A quadratic bending model for inextensible surfaces[END_REF] is a popular option. 79 Our method relies on these fabric models and associated en-80 ergies. It also happens that fabrics are modeled by implicit 81 surfaces, without worrying about developability to solve untan-82 gling problems. Given a discrete model of a fabric surface with a hole to be 86 filled in, we need an inpainting model that supports the genera-87 tion of folds and wrinkles, as opposed to conventional inpaint-88 ing techniques that generally fill holes as smoothly as possible. 89 For this purpose, our approach proceeds in two steps. First, we 90 propose to compute an intrinsic representation of the missing 91 patch (length, area) as a planar patch constrained by the geo-92 metrical information from the hole contour. This piece of fabric 93 is subsequently deformed to fill the hole by taking inspiration 94 from approaches used in simulation.

95

In this paper, we deal with surfaces represented by meshes. 96 Without loss of generality, we suppose this surface has a single 97 The second step of our approach is to move the boundary of the patch back to its 3D position and to move the interior of the patch in an as-developable-as-possible way. The deformations of developable surfaces are isometric and conformal in the sense that they preserve lengths and angles. When bending a developable surface, there is a preferential direction at each point in which the curvature remains zero. This direction of the tangential plane is the ruling direction. The surface can bend in the orthogonal direction only. The ruling direction is specific to each surface point and depends on the deformation. The ruling directions of the points are unknown in advance and we propose a strategy to let them emerge gradually through a sequence of two steps of variational optimizations.

First, we deform the surface by using as-rigid-as-possible deformations that are famous for their editing possibilities (ARAP [START_REF] Sorkine | As-rigid-as-possible surface modeling[END_REF]). From our flat patch of surface, they can be used to move the boundary vertices toward their target position in 3D while trying to preserve lengths and zero curvature in all directions around all the vertices. They thus satisfy the requirements for the deformation of developable surfaces but locally overconstrain them by seeking rigidity in all directions.

In practice, it is not always possible for the deformed surface to remain flat in all directions. This results in the emergence of a field of ruling directions over the surface, here corresponding to the minimal curvature direction at each point (see figure 8). From this initial state, we then propose to further deform the surface in a second step, in order to re-enforce the ruling directions by minimizing a developability energy inspired by cloth simulation. This helps to cancel the residual curvature in the ruling direction and to curve the surface in the maximal cur-vature direction. During this second step, new folds may also emerge if necessary (see figure 8). In practice, we do not need to extract the ruling directions explicitly. Our approach is detailed in Section 3.3. Figure 1 illustrates the entire pipeline.

Estimation of the 2D patch

As discussed in the previous subsection, the objective is to compute a 2D shape from a given set of edge lengths and angles at the boundary 2. Note that in the case of fully developable surfaces, the set of edge lengths and angles corresponds to a valid closed polygon. In real case scenario when the input mesh is not fully developable. We compute a polygon that best satisfies lengths and angles constraints in the sense of isometric mesh parameterization algorithms. For that purpose, we directly apply such a parameterization algorithm on the triangle strip surrounding the hole.

Parameterization algorithms aim at finding a mapping from a surface S in R 3 to R 2 by giving each vertex a 2D coordinate. This kind of algorithm is suitable for our problem and is used to flatten the geometry. The difficulty is to find a bijective parameterization of the hole with no intersection of the unfolded boundary in the plane, while best preserving lengths and angles.

Various algorithms have been developed for mesh parameterization, preserving various quantities. In order to reduce angular distortion, we chose the Least-Squares Conformal Maps [START_REF] Lévy | Least squares conformal maps for automatic texture atlas generation[END_REF] method (LSCM). LSCM minimizes the following energy:

E LS CM (u, v) = X 1 2 |∇u ⊥ -∇v| 2 dA ,
where u and v are vectors of 2D coordinates, ⊥ denotes a counterclockwise 90°rotation and X is the domain to parameterize.

The method preserves the angles, but the lengths are only proportional to a scaling factor. By fixing two points, lengths can be accurately maintained. On the strips of triangles that we encountered in practice, the algorithm behaves well and produces a bijection, even in cases where the input deviates from the assumption of developability.

The resulting 2d polygon is filled using an algorithm inspired by the first steps of [START_REF] Liepa | Filling Holes in Meshes[END_REF] and provided by CGAL [START_REF]CGAL User and Reference Manual[END_REF]. The algorithm first performs an optimal triangulation before refining it by adding vertices and flipping edges. The triangle density in the patch is determined based on the boundary density.

3D embedding of the patch

Once the shape of the planar missing patch is estimated, its triangulation needs to be brought back in 3D while creating folds that locally preserve the developability of the surface. For that, we wish to optimize an energy that measures the developability of our surface. We would like to emphasize that the previous determination of the planar patch is essential for this task because it already provides an estimation of the triangles with their target size, shape, and connectivity, but not their 3D embedding. Indeed, a conventional hole-filling technique followed by a cloth simulation-inspired energy would not suffice as the first step would fill the surface without consideration for the developability of the surface.

Our energy model is inspired by cloth simulation models requiring an isometric term and a bending term. To ensure isometry, we simply enforce edge lengths to be preserved using an l 2 penalty:

E I = 1 2 e i ∈E (∥ êi ∥ -e ′ i ) 2 ,
where êi denotes the estimated edge length and e ′ i denotes the target length. The gradient of this energy with respect to the position of vertex v 1 is the following:

∇ v 1 E I = -(∥ ê 12 ∥ -e ′ 12 ). ê 12 ∥ ê 12 ∥ ,
If we use this isometric energy alone, the surface produced 48 is not regular enough in terms of curvature (see Section 4.3), 49 hence it usually comes with a term penalizing dihedral angles 50 which smooth the surface out. We use the quadratic bending 51 model from [START_REF] Bergou | A quadratic bending model for inextensible surfaces[END_REF], which is formulated as follows:

52 E B = 1 2 x T (L T M -1 L)x , ∇E B = x(L T M -1 L) ,
where x denotes the vertex position vector, L corresponds to the discrete Laplace-Beltrami matrix and M is the lumped mass matrix. Our final energy model is simply expressed as:

E = E I + λE B ,
where λ is a user-defined parameter used to tailor the optimiza-53 tion process to the specific requirements of the application. This 54 parameter serves as a pseudo-physical parameter that allows the 55 user to adjust the material rigidity.

56

In our setting, the variables of the energy minimization are 57 the vertex positions in the inpainted area. Of course, there is 58 not only one solution to the positioning of our patch in 3D. It is 59 quite possible to consider the flat patch, to bring up its boundary 60 in 3D and to locally optimize the energy directly from this state 61 (see Section 4.3). However, ARAP can be used to initialize 62 our energy with a state that helps the extension of the boundary 63 folds within the patch.

64

We minimize the energy using a gradient descent with a fixed 65 step size. More advanced optimization techniques such as pro-66 jective quasi-Newton solvers could have been used. In terms 67 of performance, our current approach can still fill hole meshes 68 with 3755 vertices in less than 3.73 seconds (see 4). Further-69 more, the simplicity of our method allows us to perform a sim-70 ple collision test during iterations as discussed in the next sec-71 tion.

72

As stated in the overall presentation of our approach, the op-73 timization proceeds in two steps. The gradient descent of the 74 developability energy is done only after applying the ARAP-75 optimization algorithm proposed in [START_REF] Sorkine | As-rigid-as-possible surface modeling[END_REF], initialized from the 76 planar patch and constrained by the hole vertex positions as il-77 lustrated in Figure 3. ARAP penalizes non-isometric deforma-78 tions and aims to keep the mesh as flat as possible. While this 79 behavior can be desired for some applications, it is not fully 80 prone to the emergence of folds and tends to smooth the mesh 81 out.

However, the ARAP minimization may be a local minimum for our proposed energy function, which may limit the emergence of further folds in the mesh. To inject more freedom during our optimization, we slightly modify the ARAP step. The idea is to provide ARAP with an initial patch of reduced size to limit the number of folds it will generate, allowing it to focus on essential folds induced by the boundary.

Self-intersection and collision

When performing the gradient descent on the vertex positions, self-intersections can occur. To overcome this, we added a repulsion energy as a soft constraint between close vertices v i and v j :

E C (i, j) = κ 2 max(r -v i -v j , 0) 2 ,
where κ is the repulsive strength and r is the collision radius threshold that should be adapted to the resolution of the mesh.

This classical approach is computationally efficient compared to other techniques, though it requires small steps and cannot resolve existing self-intersections. Because our energy is also minimized via a gradient descent, the displacement steps at each iteration are small enough to be used in combination with this additional optimization. This proved to be sufficient in our experiments. Also, to reduce time complexity, we use a spatial hashing data structure, ideal for fixed-radius near-neighbor queries in low dimensions.

Finally, we also provide the method with a simple object/cloth collision tool that projects colliding vertices to the nearest valid position. Specifically, at each time step, we check for any potential intersection between the patch vertices and the objects of the scene by using the signed distance function (SDF) and its gradient. We implemented the method with simple shapes such as spheres and cylinders but the method is immediately adaptable to any shape given with its SDF and SDF gradient.

Results and discussions

In this section, we present the results of our experiments and some comparisons with existing work. We implemented the method in C++ using OpenMP for parallel computation. We used Geometry Central [START_REF] Sharp | geometry-central[END_REF] as our primary geometry processing and meshes handling library and polyscope [START_REF] Sharp | [END_REF] for visualization. Additionally, LSCM was implemented using LibIGL Fig. 4. When inpainting a hole, we can provide external constraints to conform the surface to a geometrical proxy (green sphere or tubular structure).

[34], and the triangulation was performed using CGAL [START_REF]CGAL User and Reference Manual[END_REF]. 49 We share our code at: https://github.com/g-gisbert/ 50 Inpainting-Holes-In-Folded-Fabric-Meshes. To illustrate our approach, we have applied it to different 53 kinds of input mesh data. The meshes used for evaluation come 54 from real-world scanned fabrics, scanned statues, or produced 55 through a cloth simulation. First, we scanned two pieces of fab-56 ric (Scanned Fabric 1 and Scanned Fabric 2). After meshing 57 it, we created a hole in the area with lots of folds. The ex-58 ample Curtain was produced using the cloth simulation tool in 59 Blender. We also took the example of fully developable sur-60 faces (Paper1 and Paper2). Finally, we took the meshes of two 61 draped statues (Lucy and Caryatid), for which we deviate from 62 the situation of almost developability. First of all, results given in Figure 5 demonstrate the effec-65 tiveness of our method on various examples. Specifically, the 66 first row showcases our ability to address a common challenge 67 in hole-filling techniques -the presence of large holes. In this 68 case, we were able to successfully extend the folds from one 69 end to the other in Curtain. The results produced from Scanned 70 Fabric 1 and Scanned Fabric 2 create folds in the missing area 71 that are as convincing as those produced in the ground truth.

72

It took 3.70s in 3237 iterations to fill the hole with a patch 73 of 3755 vertices for Curtain, 6.08s in 8181 iterations and 2399 74 vertices for Scanned Fabric 1, and 1.12s in 5780 iterations and 75 703 vertices for Scanned Fabric 2.

76

In Figure 6 we have considered two examples [START_REF] Verhoeven | Dev2pq: Planar quadrilateral strip remeshing of developable surfaces[END_REF] of purely 77 developable surfaces. Even if the hole geometry is complex, 78 our method achieves high-quality results.

79

The Figure 7 shows experiments on scanned statues with 80 comparisons to alternative approaches. Although the drapery 81 looks realistic, they are not truly developable surfaces (the first 82

Input

Liepa [START_REF] Liepa | Filling Holes in Meshes[END_REF] Ours Fig. 5. Results of our method on some examples (resp. Curtain, Scanned Fabric 1, Scanned Fabric 2). Our method provides the emergence of convincing folds in the inpainted area while remaining consistent with the surrounding geometry. 6 it also has 2399 vertices in the inpainted area and takes about 3min to compute. [START_REF] Hanocka | Point2mesh: A selfprior for deformable meshes[END_REF] computes both in about 5h and works with 14000 vertices. Finally, our method fills each hole in about 5s with 2399 vertices. Our method is relatively efficient with a calculation time that is within an order of magnitude of seconds, even though techniques like [START_REF] Liepa | Filling Holes in Meshes[END_REF] can reach a triangulation 100 times faster. In contrast, our method is the only one to be able 1 to render realistic folds. An interesting point is that the ma-2 chine learning approach based on self-prior [START_REF] Hanocka | Point2mesh: A selfprior for deformable meshes[END_REF] failed to learn 3 the content of the patch from the remaining parts of the stat-4 ues, probably because the hole was too wide. The self-prior 5 approach seems to still struggle with capturing fine details. In Figure 9, we also present reconstruction results using an

Fig. 1 .

 1 Fig.1. Illustration of the overall pipeline: Given an input mesh of a developable fabric with a hole (a), the first step consists in estimating the missing 2D patch shape. For this, a parametrization algorithm is applied to flatten the triangle strip surrounding the hole, which is then triangulated in the 2D plane (b); The 3d geometry is subsequently restored in two steps, first by applying As-Rigid-As-Possible deformation to preserve some rigidity in every direction around the points (c), and second by optimizing a developability function in order to further curve the fabric model and its different folds. (d).

3

 3

6

 6

14 2. Related work 15 Various

 1415 techniques and methods have been developed to ad-16 dress the problem of hole filling or inpainting in meshes. Those 17 can be divided into multiple categories. 18 Generic mesh hole-filling. Liepa [1] proposed a popular and generic hole-filling method consisting in finding the 20 minimal area triangulation of the 3D contour. The triangula-21 tion is refined to match the triangle size of the input mesh and 22 smoothed using a fairing technique. Feng et al. [2] proposed 23 using different methods depending on the hole size. For small areas, a simple centroid triangulation is enough, for medium 25 areas they use a pipeline very similar to Liepa's [1] involving 26 minimum area triangulation, refinement and fairing, and for 27 big holes they use an advancing front method which consists 28 in adding mesh element iteratively from the boundary. 29 Learning-based approaches. Deep learning models rapidly improved at generating data and can be used to solve 31 the hole-filling task. Some methods discretize a point cloud 32 or a mesh on a regular voxel grid before using 3D convolu-33 tional neural networks to process the data [3]. While taking 34 advantage of powerful efficient architecture such as 3D-CNN, 35 these strategies are inherently subject to the loss of geometric 36 information because of the voxel grid resolution. Thus, many methods prefer to work directly with point clouds to exploit the full information available. Ren et al. [4] propose to use a multi-scale upsampling GAN to generate the missing points in a corrupted point cloud. Downsampling the input point cloud at different scales helps the reconstruction to be more robust and able to restore fine-grained details. These methods are however still struggling when the missing area is too large. While most learning-based approaches have the obvious disadvantage of requiring a lot of data, self-prior methods use only the input mesh.

Fig. 2 .

 2 Fig. 2. a) Initial surface mesh with a hole; b) The triangle strip around the hole boundary is first flattened using a parameterization algorithm preserving edge lengths and angles.

1 c = 0. 5 Fig. 3 .

 153 Fig.3. ARAP tends to reduce the overall bending in the mesh and produces unrealistic meshes (the quadratic error in edge lengths is 1.91 × 10 -3 , while the error in bending is 332.49). We introduce a scale factor c ∈ [0, 1] which uniformly reduces the edge lengths targeted by ARAP. Lowering the length values only for ARAP promotes fold emergence during the following isometric optimization, resulting in a more realistic mesh (error in edge lengths: 6.85×10 -4 , error in bending: 357.33). The developability energy from Stein et al.[19] does not produce satisfying results and is unable to make folds.

  If ARAP has no room to create folds in a given direction it will temporarily stretch the edge lengths in that direction. Not all edges are equally stretched depending on their orientation. During the second optimization step following ARAP, stretched edges can recover their initial lengths and further folds can emerge between the first ones. For this temporary reduction purpose, a parameter c ∈ [0, 1] is introduced to scale down the target edge lengths only for ARAP. This produces a satisfactory initial state for the algorithm, while promoting further emergence of folds when the edge lengths recover their initial target values during the second optimization step. Figure 3 illustrates the ARAP results for two different values of c demonstrating how the classic approach can become trapped in local minima.

51 4 . 1 .

 41 Selection of illustrative models 52

63 4 . 2 .

 42 Results analysis64

Fig. 6 .

 6 Fig. 6. Examples of purely developable surfaces reconstructed with our method (Paper1 and Paper2). The first two columns show the input meshes and the other two show the inpainted meshes.

6 4. 3 .

 63 Developability evaluation and ablation study 7 The problem of filling holes in fabric surfaces does not lead 8 to a unique developable solution. Hence, a geometric surface to 9 surface correspondence metric, such as the Hausdorff distance, 10 does not make much sense. Therefore, we illustrate the effects 11 of our approach with some quantitative data regarding the out-12 put surface quality. In the first step of as-rigid-as-possible op-13 timization, flatness is favored in all directions around the ver-14 tices. This results in a solution where both the mean curvature and the Gaussian curvature are minimized jointly, with some 16 constraints at the boundary. In the second step, only the local 17 developability property is reinforced, and a significant reduc-18 tion of the residual Gaussian curvature can be obtained. This is 19 what we observe on the graph of Figure 8, with a decrease in 20 the Gaussian curvature mean and its variance.

21

 21

Fig. 7 .

 7 Fig. 7. Comparison between different hole filling methods in Lucy (first row) and Caryatid (second row). The results are given for different techniques:Liepa[START_REF] Liepa | Filling Holes in Meshes[END_REF] (second column), Ambrosio Tortorelli [16] (third column), Self-prior[START_REF] Hanocka | Point2mesh: A selfprior for deformable meshes[END_REF] (fourth column), and our method (fifth column).

Fig. 8 .

 8 Fig. 8. Graph showing the evolution of the average Gaussian curvature and its variance on Curtain, Scanned Fabric 1 and Scanned Fabric 2 as a function of the number of iterations in the minimization process of the developability energy. The initial values are computed after applying ARAP. The top right figures show the distribution of the Gaussian curvature on the meshes. The bottom figures show the directions of minimum curvature (ruling directions) for respectively the initialization after ARAP and the minimization of our energy.

[ 16 ]

 16 Bonneel, N, Coeurjolly, D, Gueth, P, Lachaud, JO. Mumford-shah mesh 1 processing using the ambrosio-tortorelli functional. Computer Graphics 2 Forum (Proceedings of Pacific Graphics) 2018;37[START_REF] Harary | Context-based coherent surface completion[END_REF]. doi:10.1111/cgf.

4 [

 4 17] Lawrence, S. Developable surfaces: Their history and application. Nexus 5 Network Journal 2011;13. doi:10.1007/s00004-011-0087-z.

6 [

 6 18] Binninger, A, Verhoeven, F, Herholz, P, Sorkine-Hornung, O. De-7 velopable approximation via gauss image thinning. Computer Graphics 8 Forum 2021;40(5):289-300. doi:https://doi.org/10.1111/cgf.

10 [

 10 19] Stein, O, Grinspun, E, Crane, K. Developability of triangle meshes. 11 ACM Trans Graph 2018;37(4).

12 [

 12 20] Liu, HTD, Jacobson, A. Normal-driven spherical shape analogies. Com-13 puter Graphics Forum 2021;40(5):45-55. doi:https://doi.org/10.

Fig. 9 .

 9 Fig.9. Ablation study: Starting from the input contour of Figure3, if we minimize our energy on a planar reconstruction (a) instead of a ARAP surface, the surface will often converge toward specific solutions which do not feel natural(b). When removing the bending energy term from our energy (starting from an initial ARAP step with c = 0.5), although the lengths are well preserved (quadratic error in edge lengths: 2.61×10 -4 ), we obtain a highly distorted and unsatisfactory result (c).

Fig. 10 .

 10 Fig.10. Influence of noise in the flattening of the hole boundary (second row) and the resulting hole filling (third row). Each vertex of the input mesh has been randomly shifted by a 3D vector uniformly sampled in the unit square times σ (first row). The first column is free of noise, the second represents the result for σ, the third for 2σ and the last for 3σ.

  plausible locations. Finally, the method could be extended to work with holes containing islands or of different nature. Regarding the input data, we also want to address the challenge of working directly on point clouds when the borders of the holes are not clearly identified.

		Input	Input (zoomed)	Liepa et al. [1]	AT [16]	Point2Mesh [5]	Ours
	37
	38	nal displacement of the patch that better takes into account the
	39	developability defect, especially in terms of the area of fabrics.
	40	5. Conclusion
	41	In this paper, we proposed a novel framework for filling holes
	42	in fabric meshes. The method involves estimating the shape
	43	of the hole in a plane and then minimizing a cloth simulation-
	44	based energy in two steps to obtain the final 3D shape. The
		framework naturally captures the developable nature of fabrics

22

alternative initialization to ARAP resulting in outputs with lim-23 ited folds. Additionally, starting on from the ARAP surface, we 24 demonstrate in this figure the relevance of the bending term in 25 our energy model, when only keeping the isometric term.

26 4.4. Limitations 27 Although our method achieves high-fidelity reconstruction, 28 it comes with a few limitations. First of all, our optimization 29 steps are comparable to those used in cloth simulation. Thus, 30 the method is computationally intensive and would particularly 31 benefit from a GPU implementation that seems quite possible 32 to obtain. Secondly, a fundamental assumption in the method 33 is the developability of the triangle strip surrounding the hole. 34 That is, we use the exact vertex positions and angles to esti-35 mate the 2D patch making the process sensitive to noise (see 36 Figure 10). In some cases, it could be helpful to compute a fi-45 and yields high-fidelity reconstructions even for large holes.

most

Acknowledgements

This work is part of the e-Roma project from the French Agence Nationale de la Recherche (ANR-16-CE38-0009). It was funded, in whole or in part, by l'Agence Nationale de la Recherche (ANR), project StableProxies ANR-22-CE46-0006. For the purpose of open access, the author has applied a CC-BY public copyright licence to any Author Accepted Manuscript (AAM) version.

Our method demonstrates high fidelity in reconstructing both 47 fabrics and developable surfaces, even when the holes are sub-


Colin Weill-Duflos
email: colin.weill-duflos@univ-smb.fr

David Coeurjolly
email: david.coeurjolly@cnrs.fr

Fernando De Goes
email: fernando@pixar.com

Jacques-Olivier Lachaud
email: jacques-olivier.lachaud@univ-smb.fr

Fernando De Goes

Joint optimization of distortion and cut location for mesh parameterization using an Ambrosio-Tortorelli functional

Keywords: Mesh parameterization, UV mapping, Variational model, Ambrosio-Tortorelli functional, Joint distortion and cut

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Computing a UV map for a mesh is a classical problem in computer graphics. UV maps have many applications, the most direct being texture atlas creation for a 3D model. Given an input three-dimensional discrete surface, the task addressed in this paper is to define a low distortion mapping of the mesh geometry to the plane while minimizing the cut length. Such cuts, or seams, may be required for topological considerations (for shapes that are not homeomorphic to a disk), or may help to better minimize the UV distortion (different cuts may lead to different local minima of the distortion energy). The problem of finding cuts and the problem of computing the parameterization are often addressed separately: cutting can be considered as a topological discrete problem, while optimizing the distortion is a geometrical problem usually solved with variational approaches.

Our method aims at simultaneously optimizing those two problems using a variational model, so that instead of predicting the distortion, the cut can adapt itself to the distortion during the process. There already exist works exploring this direction: [START_REF] Poranne | Autocuts: Simultaneous distortion and cut optimization for uv mapping[END_REF] have proposed a variational method based on a per edge cut energy, [START_REF] Li | Optcuts: Joint optimization of surface cuts and parameterization[END_REF] have presented several edge merging/cutting operations and have used them during the optimization process to reduce a given functional.

Our contribution consists of employing a dedicated variant of Ambrosio-Tortorelli functional to achieve this joint optimization. This functional measures the smoothness of a function while allowing discontinuities: in our context, the function will be the parameterization itself (with a parallel between smoothness and distortion) and the discontinuities will correspond to the locations of cuts. Minimizing this functional gives us a simple framework to simultaneously optimize the distortion and find the cuts faster than previous simultaneous optimization methods.

Related Works

Distortion minimization. Given a mesh homeomorphic to a disk (to avoid any topological issues), there are several ways of defining a "good" parameterization depending on the distortion metric that is considered.

The survey by [START_REF] Sheffer | Mesh Parameterization Methods and Their Applications[END_REF] has described a few of these methods. Some works focus on finding conformal parameterization [START_REF] Lévy | Least squares conformal maps for automatic texture atlas generation[END_REF], while other focus on finding a parameterization as isometric as possible, using energies measuring per triangle distortion such as ARAP, as-rigid-as possible, [START_REF] Chao | A simple geometric model for elastic deformations[END_REF], Symmetric Dirichlet [START_REF] Smith | Bijective parameterization with free boundaries[END_REF], or MIPS, most isometric parameterization, [START_REF] Hormann | MIPS: An Efficient Global Parametrization Method[END_REF]. In the following, we focus on the Symmetric Dirichlet energy as introduced by [START_REF] Smith | Bijective parameterization with free boundaries[END_REF]. Once the distortion metric has been specified, minimizing this energy is a problem in itself. Most optimization processes consist of two steps: (i) initialize the parameterization (with methods like [START_REF] Tutte | How to draw a graph[END_REF], which guarantees a injective parameterization) and (ii) minimize the distortion energy. To minimize these energies, we rely on quasi-Newton methods, and we need ways to approximate the Hessian with a positive symmetric definite matrix (PSD). Note that [START_REF] Smith | Analytic eigensystems for isotropic distortion energies[END_REF] have provided a way to efficiently compute a PSD matrix approximating the Hessian for distortion energies.

Cutting methods. There are several works focusing on computing cuts for a parameterization. The method [START_REF] Sheffer | Seamster: Inconspicuous low-distortion texture seam layout[END_REF] searches for some high curvature point (likely to cause distortion) and then approximates a minimal path between these points. Recently, [START_REF] Zhu | Greedy cut construction for parameterizations[END_REF] have introduced a method that detects some feature points and connect them by approximating a Steiner tree problem. While these methods are efficient, our work aims at developing a method based on simultaneous optimization, in which little work has been done compared to these methods based on connecting high distortion points. [START_REF] Sharp | Variational surface cutting[END_REF] have also provided a variational approach to compute cuts minimizing the distortion. However, their work remains limited to conformal parameterizations, while we aim at reducing an isometric distortion.

Simultaneous cuts and distortion optimization. Recent works aim at simultaneously finding the cut and the parameterization. Notable works are AutoCuts [START_REF] Poranne | Autocuts: Simultaneous distortion and cut optimization for uv mapping[END_REF], a variational model using an energy which is the sum of a distortion energy (such as Symmetric Dirichlet) and a per-edge energy approaching the cut length measure. The parameterization is treated as a triangle soup with the per-edge energy deciding whether neighbor triangles are attached to each other or not. The process can be automated, but user input is necessary in order to guarantee the bijectivity of the resulting parameterization. The weight between each term has to be defined by the user, and there is no guarantee that the result can reach a distortion or a cut length below a chosen threshold. The OptCuts method [START_REF] Li | Optcuts: Joint optimization of surface cuts and parameterization[END_REF]) is based on a set of operations on the mesh topology such as cutting or merging, and uses a dual formulation of the energy problem to find the most appropriate operation to solve the problem. This method generally outperforms AutoCuts in terms of balance between distortion and cut length, with lower timings as well. This method can be adapted to guarantee bijectivity, and a distortion threshold to be reached can be set. Our method aims at providing a variational model, in a way similar to AutoCuts, but inspired by the Ambrosio-Tortorelli functional instead of using a handmade per-edge energy. We can then take inspiration from other Ambrosio-Tortorelli optimization related works to obtain an efficient and fast strategy to find our cuts.

Bijectivity. One of the problems of surface parameterization is to guarantee the bijectivity of the result. If the embedding proposed in [START_REF] Tutte | How to draw a graph[END_REF] is guaranteed to be valid, optimizing an energy such as Symmetric Dirichlet has no reason to maintain it. One needs to enforce the bijectivity during the distortion optimization. [START_REF] Smith | Bijective parameterization with free boundaries[END_REF] have decomposed the problem into two subproblems. First, we need to make sure that triangles are not flipped during the optimization, which is solved by adding a constraint on the distortion energy and a specific line search in the Quasi-Newton solver. Then we need to prevent overlaps of non-adjacent regions which can be detected for instance by preventing boundary edge crossings. [START_REF] Smith | Bijective parameterization with free boundaries[END_REF] have solved this problem using a barrier energy term. [START_REF] Su | Efficient bijective parameterizations[END_REF] have optimized this approach by building a shell around the initial parameterization to reduce the number of border edges and vertices. Alternatively, [START_REF] Jiang | Simplicial complex augmentation framework for bijective maps[END_REF] have proposed to triangulate the remaining space around the parameterization, which in turns guarantees local injectivity on the resulting triangulation. In our proposal, we mainly focus on speeding up the distortion/cut joint optimization. Our approach is fully compatible with existing strategies (either using [START_REF] Smith | Bijective parameterization with free boundaries[END_REF] or [START_REF] Jiang | Simplicial complex augmentation framework for bijective maps[END_REF]), if global bijectivity is required.

Mumford-Shah related optimization. The Mumford-Shah functional was first introduced for image processing [START_REF] Mumford | Optimal approximations by piecewise smooth functions and associated variational problems[END_REF], as a tool for image restoration and segmentation. It gives a way to represent an image as a piecewise-smooth function with a set of discontinuities. Since this functional is difficult to optimize (see next section), a lot of approximations of this functional have been proposed in the literature. We focus here on one relaxation of this functional, called Ambrosio-Tortorelli functional [START_REF] Ambrosio | Approximation of functional depending on jumps by elliptic functional via γ-convergence[END_REF]. It has seen many applications in image processing since then, some direct such as segmentation, denoising, and some variants designed for inpainting, magnification, deblurring, or image registration. While this functional has remained largely ignored in geometry processing, it has been used recently for mesh processing applications [START_REF] Coeurjolly | Piecewise smooth reconstruction of normal vector field on digital data[END_REF][START_REF] Bonneel | Mumford-Shah Mesh Processing using the Ambrosio-Tortorelli Functional[END_REF][START_REF] Liu | Mesh denoising via a novel Mumford-Shah framework[END_REF].

The article is organized as follows. First, we briefly recall the Ambrosio-Tortorelli functional in the continuous setting (Section 3). Then, we relate the functional to the mesh parametrization problem and we propose a new discretization scheme. This discretization induces a fast joint distortion/cut optimization algorithm (Section 4). Finally, Section 5 details an experimental validation of the proposed approach.

The Ambrosio-Tortorelli functional

Our joint distortion/cut variational model takes inspiration from the Ambrosio-Tortorelli functional.

As detailed below, it can represent in the same framework the parameterization itself and the cut loci as functions.

In order to describe the Ambrosio-Tortorelli functional, it is necessary to introduce the Mumford-Shah functional [START_REF] Mumford | Optimal approximations by piecewise smooth functions and associated variational problems[END_REF]. The Mumford-Shah functional allows us, given an arbitrary function g, to find a new function u that will try to be as close as possible to g while also trying to be as smooth as possible everywhere except along a set K of discontinuities. This functional is commonly used in image processing, with a direct use in denoising: we want a smooth output close to the original input image, but we do not want to oversmooth meaningful image contours, so the function should have discontinuities along these contours. Ideally, the set K delineates these features. The functional is defined as:

MS(K, u) := α Ω\K |u -g| 2 + Ω\K |∇u| 2 + λH 1 (K ∩ Ω) , (1)
where Ω is the domain, g is the input data defined on Ω, u is the regularized data, K is the set of discontinuities, H 1 is the Hausdorff measure, and (α, λ) are two real numbers corresponding to the weights given to the fitting and cut length terms respectively. Increasing coefficient α forces the output to be closer to the input, while increasing coefficient λ induces fewer discontinuities.

the first term of this functional describes the fitting of u to the input data g, the second term expresses the regularity of u while the third term measures the length of the discontinuities. Minimizing these three terms simultaneously lets us find a compromise between input fitting, smoothness of the result and how much discontinuity is allowed. Coefficients α and λ let us control this compromise.

However, this functional is hard to optimize since it is difficult to manipulate a set of discontinuities. Ambrosio and Tortorelli (1990) have provided a relaxation of the Mumford-Shah functional, as it approximates its minimizer with two smooth functions, instead of one smooth function and one set of discontinuities. It can be defined as:

AT ϵ (u, v) := α Ω |u -g| 2 + Ω |v∇u| 2 + λ Ω ϵ|∇v| 2 + 1 4ϵ (1 -v) 2 ,
where function v is from domain Ω to [0, 1], and ϵ is a real positive number. [START_REF] Ambrosio | Approximation of functional depending on jumps by elliptic functional via γ-convergence[END_REF] have proven that this functional Γ-converges toward the Mumford-Shah functional as ϵ tends to 0. Function v converges to an indicator function of the space where discontinuities are not allowed: it is set to 1 where u is smooth, and to 0 where u can have discontinuities. A large value for ϵ will give a diffuse result, and as we decrease ϵ the function will be less and less diffuse and takes values closer to 0 and 1. The main interest of this formulation is that AT ϵ minimizers are the same as MS ones when ϵ tends to zero. Furthermore, for a given ϵ, an efficient alternating minimization scheme can be designed (see Alg. 1): by fixing v (respectively u) the resulting expression is convex quadratic in u (respectively v). We can thus find the minimizing u or v with a single step of a Newton method. We clarify the gradients and Hessian operators for the discretization of this functional in the next section.

Algorithm 1: Optimization method for the Ambrosio-Tortorelli functional Data: ϵ 1 the starting epsilon, ϵ 2 the ending epsilon, n a fixed number of optimization steps Result: v and u approximation of the functional minimizer

ϵ ← ϵ 1 while ϵ > ϵ 2 do for i ← 0 to n do v ← min v (AT ϵ (u, v)) u ← min u (AT ϵ (u, v)) end ϵ ← ϵ/2 end 4.
Our discrete AT inspired model for joint parameterization/cuts

Discretization

We work on a three-dimensional surface, specifically a triangle mesh, defined by a set V of vertices and a set F of triangular faces. We denote as n f the number of triangles of the mesh, and n v the number of vertices.

Functions u and v must be discretized. Standard discretizations make u and v defined per vertex, but this approach tends to smooth the functions. This is not desirable, especially for v. We thus prefer u and v be discretized not at the same place on the mesh. Since u represents our parameterization, it is natural to sample it at either vertices or triangle corners: u is then linearly interpolated on each triangle as expected.

Our approach consists in sampling v at faces instead, and u at vertices. This means we let some faces free to have as much distortion as needed in order to let other faces place themselves freely, acting as if there was a cut along these faces: on these faces, v is close to zero. We then have to cut alongside the distorted faces. These faces can be seen as being pulled on, the cuts then releasing the tension (see figure 1).

We can also notice that the gradient term in the Ambrosio-Tortorelli formula serves as a measure of distortion, acting as a weighted Dirichlet energy formulation ( |v∇u| 2 ). It then makes sense to see Ambrosio-Tortorelli as a process trying to reduce as much as possible this energy while allowing some exceptions: all we need then is a way to transform those exceptions into cuts. We also use Symmetric Dirichlet instead of Dirichlet, for local injectivity reasons, rescaled to be 0 when minimal. Since the gradient term already takes into account the distortion, and we do not have any data to be close to, we drop the first term of the functional, the fitting term. The formulation below expresses the energy per triangle f :

E f (u, v) := A f (v 2 + γ) |∇u f | 2 + |∇u f | -2 2 -1 Ψ f (u) +A f λ ϵ|∇v f | 2 + 1 4ϵ (1 -v f ) 2 = A f (v 2 + γ)Ψ f (u) -λϵv f (Lv f ) + λ 4ϵ (1 -v f ) 2 , (2)
where A f denotes the area of face f , ∇u f is the usual constant gradient over a triangle of the linearly interpolated u function sampled at triangle vertices. Furthermore, v f denotes simply the sampled value of function f on face f , |∇v f | 2 is the squared norm of the gradient of v within f , whose integral over the face

f is approximated as -A f v(f )Lv f ,

Optimization

Optimizing this functional is done by alternating two steps, as seen previously: one step has u fixed and one step has v fixed:

• At v fixed, the only non-constant term is the distortion term. We optimize this term using the quasi-Newton method from [START_REF] Smith | Analytic eigensystems for isotropic distortion energies[END_REF]: we compute a modified Hessian (guaranteed to be SPD) of the distortion energy as well as its gradient. We can then compute how we want to modify the current parameterization, and we use a line search to avoid triangle flip (following [START_REF] Smith | Bijective parameterization with free boundaries[END_REF], using the implementation provided by [START_REF] Jacobson | libigl: A simple C++ geometry processing library[END_REF]). We repeat until the gradient norm falls under a threshold.

• At u fixed, the expression is convex quadratic as seen for AT previously in Eq.( 2). We can put the energy to optimize at this step under the form

E := v T M Ψ(u)v + λ 1 4ϵ (v T M v -2M v) -ϵv T Lv + c , (3)
which is of the form E = v T Hv + 2b T v + c (with c a constant term that can be ignored). Its minimum can be found at -H -1 b. We need the expression of H and b:

H = λ 4ϵ I n -ϵλL + M Ψ(u), b = - λ 4ϵ M 1 n , (4)
where L is a face Laplacian matrix (we used the DEC Laplacian on the dual mesh as in Desbrun et al. ( 2005)), Ψ(u) is a diagonal matrix containing the distortion of each face (the i-th diagonal term corresponds to the i-th face), M is a face mass matrix, for example containing the area of each face on the diagonal, and finally I n is the identity n f × n f matrix and 1 n is a n f -row vector filled with ones.

While on the second step finding the minimum only requires one iteration, the quasi-Newton of the first step has to be iterated multiple times before convergence (sometimes hundreds of times), making it much more time consuming than the second step.

Cutting

The scalar function v is used as a support for the cut extraction. Indeed, for triangles with values close to 1, the distortion term of the energy fully applies and is minimized during the optimization. On the contrary, triangles with values close to zero correspond to discontinuities in the energy minimization and thus will be used to delineate the precise location of cuts (see Figure 3).

We thus need a way to convert this scalar information into sequences of edges corresponding to cuts.

To do so, we employ a simple strategy: we first define patches of triangles as simply connected components of traingles with values v lower than 0.5. Thanks to the Ambrosio-Tortorelli formulation with ϵ tending to zero, this simple process allows us to define thin strips of triangles. For each patch, we take the two farthest points belonging to this patch and find the shortest path between them: this defines the cut for this patch as a path of edges. The distance used is the distance on the underlying graph, with a weight of 0 for edges already belonging to the border. This trick forces the cut to go through the border if it is possible, to avoid having a cut parallel to an already existing border. Finally, we only keep cuts with lengths that are above 20% the length of the longest cuts, in order to avoid too small cuts.

This method was chosen for its simplicity and its effectiveness at capturing most of the areas to cut through without inducing too lengthy cuts, as seen on Figure 3. Depending on the application, one could be interested in iterating over this process: solve the AT functional to retrieve u and v, extract some long cuts, and iterate. However, in the following experiments, we only consider a single step for best performances.

OptCut Ours

Figure 2: Visualization of the parameterizations evaluated in table 1 for the armadillo, the camelhead, the duck and planck meshes. Bottom row are our parameterizations, top are optcuts'.

Overall algorithm

Algorithm 2 gives an overall description of our method. This method can be run multiple times, for example if the cutting methods missed some places to cut. We can also use more complex energy when solving for u, for example, if we need to incorporate some border energy for border injectivity. This only changes the Projected_Newton_Solver part, which needs to incorporate the Hessian and gradient of the additional energies.

Results

This section gathers several experiments that show the potential of our method for mesh texture mapping.

We first compare our approach to the state-of-the-art OptCuts method [START_REF] Li | Optcuts: Joint optimization of surface cuts and parameterization[END_REF], both quantitatively and qualitatively. Then we examine the influence of the 4 parameters of our method. We finally show how our method can easily integrate user constraints in its formulation, like cutting in less visible zones or create a tighter UV map that fits a bounding box.

Note that the results presented here are of disk-like topology, as our method has a strong dependence on the initial cut. Indeed the method does not allow us to contest the edges included in the initial cut (we have not found a satisfying way to merge already cut edges). Furthermore the initial cut puts a strong constraint on the parameterization and consecutively on the evolution of v.

Influence of parameters

There are four parameters to tune: λ, ϵ 1 , ϵ 2 and n the number of iterations between each change of ϵ (see the algorithm 1). We ended up using the following parameters by default: ϵ 1 = 0.1,ϵ 2 = 0.01 and n = 3.

Algorithm 2: Pseudocode of our method for optimizing our model, which outputs the resulting parameterization Data: (V, F ) a triangular mesh, ϵ 1 the starting epsilon, ϵ 2 the ending epsilon, n a fixed number of optimization steps

Result: U parameterization Function Compute_AT_Parameterization(F, u) u ← Tutte(V, F); v ← vec(1) ; ϵ ← ϵ 1 ; while ϵ > ϵ 2 do for i ← 0 to n do u ← Projected_Newton_Solver( u, v) ; // Compute parameterization using symmetric Dirichlet weighted by V v ← H -1 b ; end ϵ ← ϵ/2 end cuts ← Compute_Cuts( F, V, v) ; F, V ← Cut(F, V, cuts) ; u ← Projected_Newton_Solver( u) ;
// Compute final parameterization using non weighted symmetric Dirichlet

return u; end Function Compute_Cuts( F, V, v) S ← {}; for f in F do if v (f ) < 0.5 then S ← S ∪ {f }; end end cuts ← {}; foreach CC connected component in S do P 1, P 2 ← Get_Farthest_Points( CC ); cuts ← cuts ∪ Get_Shortest_Path( CC, P1, P2 ); end return cuts; end (a) (b) (c) (d)
Figure 3: Our cutting method chooses the longest path among each patch of "deformable faces" (in magenta on (a) and ( c) ). While it may not capture all of the area suggested (such as on the camelhead (d) ), it is quite effective at capturing most of it and may filter some artifacts such as the loop at the base of the neck of the camel. This results in 12 iterations of alternate optimization. We also use λ = 1.

Parameter λ can be considered as a cost for cuts and influence the final balance between distortion energy and the length of cuts. We choose λ = 1, but it may have to be changed depending on the number of cuts needed. Figure 6 illustrates the difference resulting from different λ. The three other parameters serve as convergence parameters: the wider the difference between ϵ 1 and ϵ 2 , the more the problem starts from a diffuse and global point of view and ends at a local one. Parameter n governs how many iterations are necessary before convergence at a certain ϵ. Parameters ϵ 1 and ϵ 2 were chosen so that the starting problem is global and ends at a point where v seems reduced to one triangle wide lines along distorted faces, as seen on 4.

We choose n = 3, as it was the smallest value at which function v clearly distinguishes between rigid (v close to 1) and non-rigid faces (v close to 0). Higher values could be chosen in order to let v converge to a better solution. However, no significant difference was observed in tests with higher n. This could be due to the fact that, after ϵ changes its value for the first time, the number of steps for convergence is quite small (see figure 5): it seems that its impact happens at higher ϵ values and but ends up being erased with smaller ϵ values. This could also be due to the cutting method which is not refined enough to capture the difference a more precise v would make. It would make more sense to improve the cut before increasing the computation time significantly with a higher n.

We can also run the method several time to extend the cuts. Subsequent runs are usually faster than the initial ones, but the cuts added are also smaller. As seen on figure 7, they tend to prolong the initial choices instead of adding new isolated cuts.

Comparison to state-of-the-art methods

We choose to compare our method to the current implementation of OptCuts method [START_REF] Li | Optcuts: Joint optimization of surface cuts and parameterization[END_REF]. Note that it performs better than when described in the original paper due to some recent optimizations. We were unable to compare our method to AutoCuts [START_REF] Poranne | Autocuts: Simultaneous distortion and cut optimization for uv mapping[END_REF], since we failed to reproduce their results: the convergence speed was much too slow and was not producing results close to the ones displayed in their paper. After discussions with the author, we learned that their results were obtained using a proprietary solver, whose current version is not compatible with their code. However, it seems that the current implementation of OptCuts performs better than AutoCuts in most cases, so the comparison with OptCuts is a good test for our approach. Table 1 sums up parameterization results obtained by OptCuts and our approach, in terms of computation speed, final distortion and final cut length. We use OptCuts distortion measures and cut length, respectively:

E d := 1 t∈F |A t | t∈F |A t |Ψ(t) , E s := 1 t∈F |A t | i∈S |e i | . (5)
Our method almost always outperforms OptCuts in terms of speeds. However OptCuts is often better in terms of cut length for distortion reduction (better means less cut length for the lowest distortion). Since our method does not allow targeting for a fixed distortion (while OptCuts does), we used our method first and then set OptCuts targeting the same distortion value we obtained. Bear in mind that the lowest distortion that a mesh can attain is 4 as it is the minimum of Symmetric Dirichlet energy, so a change from 4.2 to 4.1 is actually quite significant.

Assisted cutting

We wish to take into account some user input when choosing cuts. For example, some edges may be favored over others based on their visibility (less visible edges are preferred). To take this constraint into account, we can define λ as a scalar over the surface instead of a constant, and with a value depending on the user input. We tested this approach using visibility computed with libigl ambient occlusion [START_REF] Jacobson | libigl: A simple C++ geometry processing library[END_REF]). Figure 8 illustrates how it affects the resulting distribution of v: areas to cut are more prone to be placed in low visibility areas such as cracks.

Packing constraints for the atlas

It may be desirable for a UV map to be as tight as possible in order to take less memory space. We follow Autocuts method [START_REF] Poranne | Autocuts: Simultaneous distortion and cut optimization for uv mapping[END_REF] for fitting a parameterization within a predefined bounding rectangle. Figure 9 shows how UV map are then much more compact. However we observe a significant increase in the convergence time, depending on how tight the bounding box is: thee harder it is to fit the parameterization in the box, the longer it takes (sometimes taking 10 times as long as without).

Discussion and perspectives

We have presented a new variational model to compute a UV parameterization of a triangle mesh with a joint optimization of distortion and cuts. It is a discrete variant of the Ambrosio-Tortorelli functional, which offers theoretical guarantees for solving problems involving a penalization in the length of discontinuities. We have shown that this approach is effective in practice, faster than other simultaneous optimization methods, with quality often close to the state-of-the-art Optcuts method, and incorporates easily other constraints in its formulation like border injectivity, assisted cutting or compact texture maps. We can also note that the loci of deformable faces may have an arbitrary topology, so cuts can take various shapes. Finally, the code is available at https://github.com/Lieunoir/UV-AT.

In order to measure the distortion, we only tested the Symmetric Dirichlet energy, which was the closest to the original gradient term in the Ambrosio Tortorelli functional. As future works, other energies could be evaluated (such as ARAP), as they may not behave in the same way as Symmetric Dirichlet.

A limitation of the current cutting method is that it does not preserve the topology defined by v: if any cycle is present, we ignore it. It also does not capture all of the region defined by the underlying patch (if the region is a tree it will only choose the longest branch), meaning we have to run the method again to capture it all. Our current cutting method is well adapted to a semi-supervised setting where the user can decide to refine further, but cuts following the topology induced by v could indeed be interesting in an unsupervised model. In some cases, our method is not able to run properly because the energy diverges in the initialization. This problem comes from numerical issues of floating-point arithmetic. It is addressed by [START_REF] Shen | Progressive embedding[END_REF], giving a alternative to Tutte's embedding for initialization. We have not run our method with this initialization, but we can safely assume that it does not affect significantly the results.

One way to improve the convergence speed would be to include some speedup optimization techniques.

In particular, we could use the methods proposed by [START_REF] Liu | Progressive parameterizations[END_REF] or [START_REF] Liu | Surface multigrid via intrinsic prolongation[END_REF]. We could also look for other ways to optimize the Mumford-Shah functional that would yield better results or give them faster: our alternate Ambrosio-Tortorelli optimization method is among the costliest ones. For instance, the recent competitive gradient and mirror descent algorithms [START_REF] Schäfer | Competitive gradient descent[END_REF][START_REF] Schäfer | Competitive mirror descent[END_REF] seem to be particularly efficient in optimizing this type of functional, which are block-convex but not globally convex.

Figure 1 :

 1 Figure 1: Parameterization at different stages of the method on the bunny head and face mesh: the initial parameterization (a, d), we then allow some faces (in magenta) to have distortion (b, e) so the other have more freedom of movement. We then compute cuts along these faces, giving us the result (c, f).

  with Lv f the DEC Laplacian of v on the dual mesh (see[START_REF] Desbrun | Discrete exterior calculus[END_REF]), γ is a fixed constant, necessary to avoid a null coefficient in front of the distortion term: it would lead to instability during the optimization. Results presented here use γ = 10 -7 . Finally, Ψ f (u) is the distortion measure of the face f .

Figure 4 :

 4 Figure 4: Evolution of v during the iterations of the function Compute_AT_Parameterization of Algorithm 2 as the ϵ decreases. Starting from a smooth discontinuity map (a), v becomes sharper as ϵ tends to zero.

Figure 5 :

 5 Figure5: Evolution of our energy (defined in 2) when using n = 10 on various meshes (meaning ϵ changes every 10 iterations). After the first change of ϵ, it only takes a few iterations for the energy to converge.

Figure 6 :

 6 Figure 6: Results on the bunnyhead and hand meshes for λ = {3, 1, 0.1} (reps. from left to right). Lower λ parameter implies longer cuts.

Figure 7 :

 7 Figure7: Results after multiple runs of our algorithm. This enables us to capture some natural cuts that our algorithm may have missed. After a few runs cuts our method converges, and the cuts stop expanding.

Figure 8 :Figure 9 :

 89 Figure 8: Optimized function v without (left) and with (right) the ambient occlusion (AO) taken into account (middle). When ambient occlusion is enabled, the faces identified as cut loci are guided to regions with lower visibility.

Table 1 :

 1 Quantitative comparison between OptCuts method and our method, in terms of computation time, distortion and cut length. The bimba, hand, cat, armadillo, duck, planck, venus, tooth and circular box meshes come from the available input mesh in OptCuts[START_REF] Li | Optcuts: Joint optimization of surface cuts and parameterization[END_REF] repository.

	Model	bunnyhead camelhead bimba hand	cat	armadillo duck1 planck1 venus tooth circular box
	OptCut's time	2.5s	89s	13s	0.60s	0.65s	29s	2.08s	1.19s	0.61s	25.4s	22s
	Our time	1.6s	38s	6s	0.13s 0.11s 6.1s	0.77s 1.32s	0.36s 2.1s	3.8s
	Initial distortion	9.10	7.45	7.64	10.04 6.67	10.3	5.59	9.03	8.78	4.26	5.28
	OptCut's distortion	4.36	4.26	4.50	5.2	4.38	5.22	4.49	4.54	4.37	4.24	4.53
	Our distortion	4.39	4.26	4.50	5.3	4.50	5.22	4.49	4.56	4.39	4.25	4.54
	OptCut's cut length 2.88	2.93	2.01	4.5	1.28	2.07	1.09	1.61	1.70	0.24	1.13
	Our cut length	3.82	2.56	1.90	5.6	1.76	4.25	1.31	2.33	2.94	0.10	1.50

Acknowledgements

This work is supported by the French National Research Agency in the framework of the « France 2030 » program (ANR-15-IDEX-0002), by the LabEx PERSYVAL-Lab (ANR-11-LABX-0025-01) and by the StableProxies project (ANR-22-CE46-0006).