Andrei Zaharescu

Edmond Boyer

Radu Horaud Domaine

Topology-Adaptive Mesh Deformation for Surface Evolution, Morphing, and Multi-View Reconstruction

Keywords: Perception, cognition, interaction Mesh, surface, manifold mesh, triangulated mesh, mesh evolution, deformable objects, morphing, 3-D reconstruction Maillage, surface, variété, triangulation, évolution de maillage, objet déformable, morphing, reconstruction 3-D

Triangulated meshes have become ubiquitous discrete-surface representations. In this paper we address the problem of how to maintain the manifold properties of a surface while it undergoes strong deformations that may cause topological changes. We introduce a new self-intersection removal algorithm, TransforMesh, and we propose a mesh evolution framework based on this algorithm. Numerous shape modelling applications use surface evolution in order to improve shape properties, such as appearance or accuracy. Both explicit and implicit representations can be considered for that purpose. However, explicit mesh representations, while allowing for accurate surface modelling, suer from the inherent diculty of reliably dealing with self-intersections and topological changes such as merges and splits. As a consequence, a majority of methods rely on implicit representations of surfaces, e.g. level-sets, that naturally overcome these issues. Nevertheless, these methods are based on volumetric discretizations, which introduce an unwanted precision-complexity trade-o. The method that we propose handles topological changes in a robust manner and removes self intersections, thus overcoming the traditional limitations of meshbased approaches. To illustrate the eectiveness of TransforMesh, we describe several challenging applications: surface morphing and 3-D reconstruction.

Introduction

In the process of modeling shapes, several applications resort to surface evolution to improve shape properties. For instance, shape surfaces are evolved so that their appearances are improved, as when smoothing shapes, or so that they best explain given observations as in image based modeling. The interest arises in several elds related to shape modeling: computer vision, computer graphics, medical imaging and visualization among others. Surface evolution is usually formulated as an optimization process that seeks for a surface with a minimum energy with respect to the desired properties. To this aim, surfaces can be represented in dierent ways, from implicit to explicit representations, and deformed in an iterative way during optimization. Polygonal meshes, while being one of the most widely used representation when modeling shapes, are seldom used in such evolution schemes. The main reasons for that is the inherent diculty to handle topological changes and self-intersections that can occur during evolution.

In this paper, we introduce an intuitive and ecient algorithm, named Trans-forMesh, that performs self-intersection removal of triangular meshes, allowing for topological changes, e.g. splits and merges. The method assumes as input a proper oriented mesh a 2-D compact oriented manifold which experienced any connectivity preserving deformation. It computes the outside surface of the deformed mesh. To illustrate the approach and its interests, we propose a generic surface evolution framework based on TransforMesh and we present two applications: mesh morphing and variational multi-view 3-D reconstruction.

Literature Review

As a result of the large interest for surface evolution in many application domains, numerous surface deformation schemes have been proposed over the last decades. They roughly fall into two main categories with respect to the representation which is considered for surfaces: Eulerian or Lagrangian.

Eulerian methods formulate the evolution problem as time variation over sampled spaces, most typically xed grids. In such a formulation, the surface, also called the interface, is implicitly represented. One of the most successful methods in this category, the level set method [START_REF] Osher | Level Set Methods and Dynamic Implicit Surfaces[END_REF][START_REF] Osher | Front propagating with curvature dependent speed: algorithms based on the Hamilton-Jacobi formulation[END_REF], represents the interface as the zero level of a higher dimensional function. A typical function used is the signed distance of the explicit surface, discretized over the volume. At each iteration the whole implicit function is moved. The explicit surface is recovered by nding the 0-level set of the implicit function. A number of methods have been proposed to extract surfaces from volumetric data [START_REF] Ju | Dual contouring of hermite data[END_REF][START_REF] Kobbelt | Feature sensitive surface extraction from volume data[END_REF][START_REF] Lorensen | Marching cubes: A high resolution 3D surface construction algorithm[END_REF][START_REF] Ohtake | Dynamic mesh optimization for polygonized implicit surfaces with sharp features[END_REF].

Such an embedding within an implicit function allows to automatically handle topology changes, e.g. merges and/or splits. In addition, such methods allow for an easy computation of geometric properties such as curvatures and benet from viscosity solutions -robust numerical schemes to deal with the evolution.

These advantages explain the popularity of level set methods in computer vision [START_REF] Osher | Geometric Level Set Methods in Imaging, Vision, and Graphics[END_REF] as well as in other elds, such as computational uid dynamics [START_REF] Sussman | A level set approach for computing solutions to incompressible two-phase ow[END_REF] and computer animations of uids [START_REF] Enright | Animation and rendering of complex water surfaces[END_REF]. Nevertheless, implicit representations exhibit limitations resulting from the grid discretization. In particular, the precision/complexity trade-o inherent to the grid has a signicant impact on the computational eciency and the proposed narrow-band solutions [START_REF] Adalsteinsson | A fast level set method for propagating interfaces[END_REF] or octree INRIA based implementations [START_REF] Losasso | Spatially adaptive techniques for level set methods and incompressible ow[END_REF] only partially overcome this issue. In addition, as

shown by Enright et al. [START_REF] Enright | A hybrid particle level set method for improved interface capturing[END_REF], the level set method is strongly aected by mass loss, smearing of high curvature regions and by the inability to resolve very thin parts. Another limitation is that level set methods are not appropriate for tracking surface properties, such as color or texture, which can be desirable in many image-based approaches (i.e. motion tracking). Thus, while providing a solution for the intersection and topological issues within surfaces, implicit representations introduce a new set of issues for which careful solutions need to be crafted.

Lagrangian methods propose an approach where surfaces have explicit representations which are deformed over time. Such representations, meshes for instance, present numerous advantages, among which adaptive resolution and compact representation, as well as the ability to directly handle non-geometric properties over the surface, e.g. textures, without the necessity to reconstruct the interface. On the other hand, they raise two major issues when evolved over time, namely self-intersections and topology changes, which make them dicult to use in many practical scenarios. This is why non-intersections and xed topology were explicitly enforced [START_REF] Hernández | Silhouette and stereo fusion for 3-D object modeling[END_REF][START_REF] Park | A non-selfintersection adaptive deformable surface for complex doundary extraction from volumetric images[END_REF]. As a consequence, and in spite of their advantages, they have often been neglected in favor of implicit representations which provide practical solutions to such issues. Nevertheless, solutions have been proposed. McInerney and Terzopoulos [START_REF] Mcinerney | T-snakes: Topology adaptive snakes[END_REF] introduced topology adaptive deformable curves and meshes, called T-snakes and T-surfaces. However, in solving the intersection problem, the authors use a spatial grid, thus imposing a xed spatial resolution. In addition, only osetting motions, i.e. inating or deating, are allowed. Another heuristic method was proposed by Lauchaud et al. [START_REF] Lachaud | Deformable model with adaptive mesh and automated topology changes[END_REF] for mesh deformations. Merges and splits are performed in near boundary cases: when two surface boundaries are closer than a threshold and facing each other, an articial merge is introduced; a similar procedure is applied for a split, when the two surface boundaries are back to back. Self-intersections are avoided in practice by imposing a xed edge size. A similar method was also proposed by Duan et al. [START_REF] Duan | Shape reconstruction from 3D and 2D data using pde-based deformable surfaces[END_REF]. Alternatively, Pons and Boissonat [START_REF] Pons | Delaunay deformable models: Topologyadaptive meshes based on the restricted delaunay triangulation[END_REF] proposed a mesh approach based on a restricted 3-D Delaunay triangulation. A deformed mesh is obtained by triangulating the moved vertices and assuming that the tetrahedra categorization, i.e. inside and outside, remains after the deformation. While being a robust and elegant solution, it nevertheless relies on the assumption that the input mesh is suciently dense such that the Delaunay triangulation will not considerably change its layout.

The methods proposed by Aftosmis et al. [START_REF] Aftosmis | Robust and ecient cartesian mesh generation for component-based geometry[END_REF] and Jung et al. [START_REF] Jung | Self-intersection removal in triangular mesh osetting[END_REF] are also related to our work. The algorithm in [START_REF] Aftosmis | Robust and ecient cartesian mesh generation for component-based geometry[END_REF] recovers the outside surface obtained from self-intersecting meshes. The output mesh is obtained by identifying facets, or part of facets, which are on the exterior. The algorithm [START_REF] Jung | Self-intersection removal in triangular mesh osetting[END_REF] uses the same idea, applied in the context of mesh osetting. As explained below in detail, we generalize these approaches to the more general situations of any mesh deformation.

As a hybrid method, the recent work of Wojtan et al. [START_REF] Wojtan | Deforming meshes that split and merge[END_REF] is representative, where the topological changes to the mesh are handled by rst identifying merging or splitting events at a particular grid resolution, and then locally creating new pieces of the mesh in the aected cells using a standard isosurface creation method. The topologically simplied portions of the mesh are stitched to the rest of the mesh at the cell boundaries. While the authors present very

RR n°7136

convincing results, they acknowledge some limitations, such as the restriction to a particular grid cell size, as well as some topological concerns related to matching exactly the extracted isosurface to the original mesh, among others.

In addition to the two above categories it is worth to mention also Solid modeling methods that provide practical tools to represent and manipulate surface primitives. Methods in this domain fall into two categories: Constructive Solid Geometry (CSG) [START_REF] Foley | Computer Graphics: Principles and Practice[END_REF][START_REF] Hubbard | Constructive solid geometry for triangulated polyhedra[END_REF] and Boundary Representation (B-Rep) [START_REF] Baumgart | Geometric Modeling for Computer Vision[END_REF][START_REF] Braid | Stepwise construction of polyhedra in geometric modelling[END_REF].

CSG methods represent shapes as a combination of elementary object shapes based on Boolean operations. Alternatively, B-Rep methods adopt the more natural approach to represent the object boundary using vertices, edges and facets [START_REF] Agrawal | A paradigm for the robust design of algorithms for geometric modeling[END_REF][START_REF] Rossignac | Encyclopedia of Electrical and Electronics Engineering, chapter Solid Modeling[END_REF]. Each representation has its advantages. While Boolean operations on CSG objects are straightforward, a lot of computational eort is required to render CSG objects [START_REF] Goldfeather | Fast constructive-solid geometry display in the pixel-powers graphics system[END_REF][START_REF] Rappoport | Interactive boolean operations for conceptual design of 3-D solids[END_REF]. On the other hand, it is much more dicult to implement Boolean operations on boundary representations (multiresolution surfaces) [START_REF] Biermann | Approximate boolean operations on free-form solids[END_REF][START_REF] Nathan Litke | Trimming for subdivision surfaces[END_REF], whereas interactive rendering is trivial. While these methods propose solution for computing Boolean operations of surfaces, to the best of our knowledge they do not deal with any extension needed to address self-intersecting meshes. Generally, the methods are more concerned with the rendering of the resulting geometry than with the generation of correct manifolds in the case of self-intersections.

Contributions

In this paper we propose a novel topology-adaptive self-intersection removal method for triangular meshes as well as an associated ecient algorithm, Trans-forMesh, with guaranteed convergence and numerical stability. We generalize previous work in this area [START_REF] Aftosmis | Robust and ecient cartesian mesh generation for component-based geometry[END_REF][START_REF] Jung | Self-intersection removal in triangular mesh osetting[END_REF] to any topology changes resulting from mesh deformation, including merges, splits, hole formations, and hole losses, e.g. Fig-

ure 7. The main contribution is that given an input mesh with self-intersections, the algorithm provides a 2-D compact oriented manifold that represents the outside skin of the input mesh. Such an input mesh is typically obtained by applying arbitrary deformations to its vertices, as is often the case with such techniques as surface evolution, surface morphing, or multi-view 3D reconstruction.

The vast majority of the mesh-based surface deformation algorithms available today are based on topology-preserving methods. Alternatively, we propose a topology-adaptive mesh evolution method that is entirely based on Trans-forMesh. Such topology-adaptive scheme is more general and hence better adapts to challenging applications such as 3D reconstruction using multiple images and non-rigid surface tracking.

Recent image-based reconstruction methods [START_REF] Seitz | A comparison and evaluation of multi-view stereo reconstruction algorithms[END_REF] make use of surface evolution to obtain accurate 3D models. Our approach contributes in this eld by providing an ecient unconstrained mesh-based solution that allows for facets of all sizes as well as for topology changes, with the goal of increasing precision without sacricing complexity. The robustness and exibility of the proposed framework is also validated in the context of mesh morphing, showing several topologically challenging examples.

The remainder of this article is organized as follows. Section 2 provides some background concepts on which our method resides. Section 3 describes in detail the TransforMesh algorithm. Various aspects of the algorithm, such that the topological changes that it can handle, convergence, numerical stability INRIA and time complexity are detailed in section 4. Section 5 describes the mesh evolution algorithm based on TransforMesh. Mesh morphing is described in section 6. Section 7 describes how our methodology is plugged into the task of 3D reconstruction. Finally, we conclude in section 8.

TransforMesh is available as an open-source software package (OSS) under a general public licence (GPL) at http://mvviewer.gforge.inria.fr/.

2 Background

Before we introduce the TransforMesh algorithm we precise the context within which it applies. We assume an initial mesh representing the surface of a real object to be deformed into a self-intersecting input mesh from which the Trans-forMesh algorithm extracts an output mesh. More precisely, we assume that the initial mesh represents a compact oriented 2-D manifold with possibly several components and we expect the output mesh to do the same. Consequently both initial and output meshes should satisfy the following properties: every edge belongs to exactly two at faces; every vertex is surrounded by a single cycle of edges and faces; faces are oriented and do not intersect except at edges and vertices. The deformation that the initial mesh underwent can then be any transformation that preserves the mesh graph structure, i.e. its connectivity.

Hence any vertex displacement eld that preserves edges is acceptable. Note that this excludes displacements that fuse neighboring vertices.

The TransforMesh algorithm relies on the identication of outside or exterior faces on the deformed input mesh. An exterior face on an oriented mesh is a boundary face that delimits interior and exterior regions and that is oriented towards an exterior region, i.e. its normal points outward. To further identify regions delimited by the mesh as interior or exterior we need a rule. Traditionally, interior and exterior regions are dened with an even-odd parity rule. Such rule simply consists of counting the number of intersections of a ray, emanating from a point, with the delimiting primitive. If this number is odd, the point belongs to an interior region, if not, the point is on the exterior. While ecient, this rule originally applies to simple primitives, e.g. simple closed curves in 2D and closed surfaces in 3D, and does not correctly handle more complex primitives in particular self-intersecting primitives. In that case, the winding rule allows regions to be better dierentiated by using the primitive's orientation.

This appears to be crucial when operating topological changes, such as merge and split, over regions.

The winding number of a point p with respect to an oriented primitive is the number of times the primitive winds or cycles around p. Cycles are counted positively or negatively depending on their orientations around the point. p is then outside when its winding number is 0, inside otherwise. Figure 1 depicts this principle in 2D.

To compute this number, two strategies can be followed. A rst strategy consists in computing the total signed angle, solid angle in 3D, made by a ray from the point under consideration to another point traveling along the primitive [START_REF] Carvalho | Point in polyhedron testing using spherical polygons[END_REF]. The sum will be equal to 0 for a point on the exterior and a multiple of 2π, 4π in 3D, for a point on the interior. Another strategy considers a ray from a point and its intersections with the primitive [START_REF] Foley | Computer Graphics: Principles and Practice[END_REF]. Each intersection is assigned a value +1 or -1 according to the sign of the dot product of the ray RR n°7136 The winding number at p can be obtained by summing the dot product signs with face normals along any ray from p.

direction with the normal to the primitive at the intersection. If this sign is negative the value is -1 and +1 otherwise, see Figure 2. The sum of these values will be 0 only for a point on the exterior. We use this strategy to verify whether a face is on the exterior. We take a ray from the center of the face towards its normal direction and we sum the values -1 and +1 obtained at the intersections with other faces along the ray. The face is on the exterior when this sum is 0.

We call then a valid face a face fully on the exterior without intersections with other faces and a partially valid face a face divided by intersections into sub-parts, some of which being on the exterior. Notice that valid faces can be found inside the mesh, as independent connected components may appear inside the mesh as a result of self-intersections. Although these components are valid parts of the resulting mesh, they are usually not considered in evolution processes that do rely on criteria applying on exterior surfaces only, distance or photo-consistency for example.

INRIA 3

The TransforMesh Algorithm

The TransforMesh algorithm removes self-intersection and adapts to topological changes in triangular meshes using an intuitive geometrically-driven solution. In essence, the approach preserves the surface consistency, i.e. 2-D manifoldness, by detecting self-intersections and considering the subset of the original surface that is still outside. In order to identify the corresponding faces in the mesh, the method consists in rst nding an initial seed face that is fully on the exterior, using the winding rule presented in the previous section, and then propagating the exterior label over the mesh faces by means of region growing. Figure 3 illustrates the algorithm, the dierent steps are detailed in the following.

Input triangular mesh:

A manifold mesh that is deformed and presents self-intersections Initialization:

1. Compute triangle intersections

Triangulate partially valid triangles using constrained 2D Delaunay

Main loop:

1. Find seed (valid) triangles 2. Propagate exterior region over:

2.2 Neighboring partially valid triangles

Neighboring valid triangles

Output triangular mesh:

Stitch triangles into a manifold mesh (1) (2.1) (2.2) (1) (2)
(2.1)

Input Mesh

Self Intersections

The rst step of the algorithm consists of identifying self-intersections, i.e. edges along which triangles of the mesh intersect.

This information will later on be needed in the computations, since it delimits the outside regions. In the general situation, one would have to perform O(n 2 ) checks, with n the number of triangles, to verify all triangle intersections, which can become expensive when the number of facets is large. In order to decrease the computational time, we use a bounding box test to determine which RR n°7136

bounding boxes (of triangles) intersect, and only for those perform a triangle intersection test. We use the fast box intersection method implemented in [START_REF] Kettner | Intersecting sequences of dD iso-oriented boxes[END_REF] and described in [START_REF] Zomorodian | Fast software for box intersection[END_REF]. The complexity of the method is then O(n log 3 (n)).

Valid Region Growing

The second step of the algorithm consists of identifying exterior triangles in the mesh. A valid region growing approach is used to propagate validity labels on triangles that composed the outside of the mesh. Alternatively, it can be viewed as a "painting" procedure, as it was originally described in [START_REF] Aftosmis | Robust and ecient cartesian mesh generation for component-based geometry[END_REF]. Following this idea, we present here the sub-steps of the region-growing procedure. First, in the Seed-triangle nding step, valid triangles are sought as starting triangles without intersections that reside on the exterior. In the next Valid triangle expansion step this information is propagated by expanding on neighboring valid triangles until triangles with intersections are reached. The Partially valid triangle traversal step details then how to traverse the valid sub-parts of intersection triangles as well as how to cross from one intersecting triangle to the other.

The local sub-parts are triangulated using a constrained 2-D Delaunay triangulation. The underlying idea that guides this step is to propagate the normal information from the seed triangles using the local geometry.

Seed-triangle nding A seed-triangle is dened as a non-visited valid triangle, found using the winding rule previously introduced. In other words, a seed-triangle is a triangle that is guaranteed to be on the exterior. This triangle is crucial, since it constitutes the starting point for the valid region growing. If found, the triangle will be marked as valid; otherwise, we assume that all outside triangles are identied and the algorithm jumps to the next stage (section 3.3). We have adopted the ecient AABB tree implementation described in [START_REF] Alliez | Aabb tree[END_REF] for the ray-to-triangles intersection test.

Valid triangle expansion Region growing over valid triangles is simply performed by checking neighbors of a valid triangle and stopping on the intersections: if the neighboring triangle is non-visited and has no intersections, then it is marked as valid; if the neighboring triangle is non-visited and has intersections, then it is marked as partially valid together with the entrance segment and direction, corresponding in this case to an oriented half-edge.

Partially-Valid triangle traversal In this step proper processing of regions containing intersections is ensured, with local geometry being generated. Let t be a partially valid triangle as marked during the valid triangle expansion step. We have previously calculated all the intersection segments between this triangle and all the other triangles. Let S t = {s ti } represent all the intersection segments between triangle t and the other triangles. In addition, let H t = {h tj |for j = 1..3} represent the triangle half-edges. A constrained 2-D triangulation performed in the triangle plane, using [START_REF] Hert | dD convex hulls and delaunay triangulations[END_REF], ensures that all segments in both S t and H t appear in the new triangular mesh structure and that propagation can be achieved in a consistent way. A ll-like traversal is performed from the entrance half-edge to adjacent triangles, stopping on constraint edges, as depicted in Choosing the correct side of continuation of the "ll" like region growing when crossing from a partially valid triangle to another is a crucial aspect in ensuring a natural handling of topological changes. The correct orientation is chosen such that, if the original normals are maintained, the two newly formed subtriangles would preserve the water-tightness constraint of the manifold. This condition can also be casted as follows: the normals of the two sub-triangles should be opposing each other when the two sub-triangles are "folded" on the common edge. A visual representation of the two cases is shown in Figure 5.

The triangles on the other side of the exit constraint edges will be marked as valid appropriately, based on whether they contain any intersections or not.

Note that it is possible to visit a partially valid triangle multiple times, depending on whether there are multiple isolated (non-connected) exterior components. However, each sub-triangle formed by the local re-triangulation is only visited once. The simplest example to image is a cross, formed out of two intersecting parallelepipeds. There will be intersecting triangles appearing on both sides.

Triangle Stiching

The region growing algorithm described previously will iterate until there are no more unmarked triangles to visit. At this stage, what remains to be done is to stitch together the 3-D triangle soup (G queue) in order to obtain a valid mesh which is manifold. We adopt a method similar in spirit to [START_REF] Gueziec | Cutting and stitching: Converting sets of polygons to manifold surfaces[END_REF][START_REF] Shin | Ecient topology construction from triangle soup[END_REF]. In most cases this is a straight forward operation, which consists of identifying the common vertices and edges between facets, followed by stitching. However, there are three special cases, in which performing a simple stitching will violate the mesh constraints and produce locally non-manifold structures. The special cases, shown in Figure 6, arise from performing stitching in places where the original structure should have been maintained. We adopt the naming convention from [START_REF] Gueziec | Cutting and stitching: Converting sets of polygons to manifold surfaces[END_REF], calling them the singular vertex case, the singular edge case and the singular face case. All cases are easily identied by performing local operations.

RR n°7136

Singular vertex case (Figure 6(a)). A vertex is shared by two or more dif- ferent regions. In this case, the manifold property stating that for each manifold point, there is a single neighborhood, does not hold. The algorithm to detect these cases proceeds simply by checking that all facets incident to a vertex are within one neighborhood. The steps are: starting from a facet of v, mark it visited and do the same with its non-visited neighbors that are also incident to v (neighboring triangles are chosen based on the available mesh connectivity); the process is repeated until all the neighboring facets are processed; if by doing so we exhausted all the neighboring facets, vertex v is non singular, otherwise it is singular, so a copy of it is created and added to all the remaining non-visited facets. The process is repeated until all the incident facets are visited.

Singular edge case (Figure 6(b)). An edge is shared by two or more dierent regions, hence the manifold property does not hold. Such cases are detected and repaired by the singular vertex detection step, which will correctly identify and duplicate the two vertices that form the singular edge.

Singular triangle case (Figure 6(c)). A triangle is shared by two or more dierent regions, hence the manifold property does not hold. Such cases are detected and repaired by the singular vertex detection step, which will correctly identify and duplicate the three vertices that form the singular triangle.

Given that the original input mesh does not contain any of the above singular simplex scenarios, they rarely occur in practice. Note however that there are situations where creases are formed on the mesh, usually when inverting mesh regions, that can degenerate into singular cases.

INRIA

Algorithm Analysis

Having introduced the algorithm in the previous section, we discuss in this section some of its most important aspects, including the handling of topological changes, the guarantee to obtain a valid mesh given a valid input mesh, the numerical stability and the time complexity.

Topological Changes

A nice feature of the algorithm is to correctly handle topological changes that result from the modication of the local geometry, i.e. faces that appear and disappear. We consider compact surfaces and in the general case, topological changes that can occur are: merge, split, hole formation and hole loss. They are depicted in Figure 7. Note that in 3D hole cases correspond to situations where a connected component is inside another connected component and that topological changes where handles appear or disappear are covered by the merge and split cases (see Figure 11 for examples). The partially valid triangle crossing technique described earlier in Section 3.2 and detailed in Figure 5 ensures a natural handling of these topological changes that plagued most of the mesh approaches until now. The merge case scenario, shown in Figure 7(a), coincides in spirit with the union Boolean set operation ∪ * . Less intuitive is the split operation, which will typically occur during a mesh evolution process, when certain parts will thin out up to the moment when some triangles from opposite sides will cross each other. Such a case is depicted in Figure 7

Guarantees

Given that the input mesh is a 2-D compact oriented manifold that has been deformed by a motion eld and assuming exact computations (see section 4. number of components depends on the number of seed triangles detected. The algorithm will always nish, because it does not revisit already traversed subparts. In addition, it is guaranteed to always nd the exterior surface, since it starts from a valid seed triangle, thus on the exterior, and it always rests that way, by propagating the normal information. The computed output is manifold by construction, since it traverses a valid input manifold and accounts for the manifold violations with the degenerate cases. It is compact, since the original input surface has no border and the algorithm does not build any, i.e. there is always a way outside a triangle intersection.

In addition, the 2-D manifold correctness is guaranteed by identifying and correcting all the possible 2-D manifold neighborhood violations when performing triangle stitching (singular vertex, singular edge and singular facet).

The algorithm preserves the geometry of the input mesh, with the exception of the self-intersection areas, where local triangulations redene the geometry.

Numerical Stability

The numerical stability is critical, in order to be able to guarantee that the output is valid. It is ensured by using exact arithmetic predicates when computing intersections, as well as disambiguating the boundary cases. The special boundary cases between two intersecting triangles are:

1. the intersection reduces to a point;

2. the intersection is a segment that lies on one of the original triangle edges; INRIA 3. the intersection is a 2-D polygon, i.e. the two triangles are co-planar.

We disambiguate the above boundary cases using the simulation of simplicity technique of virtual perturbations [START_REF] Edelsbrunner | Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms[END_REF]. It involves inducing a small vertex perturbation locally, which will force the triangle-triangle intersection into one of the classical cases: either the two triangles do not intersect or their intersection is a segment that does not lie on one of the original triangle edges. In practice, when such boundary situations occur, mesh osetting is performed for that purpose. The choice of using the simulation of simplicity technique to handle boundary cases is motivated by the targeted application, mesh evolution, where such boundary situations rarely occur and where the explicit handling of all special cases would penalize the algorithm. We note, however, that there are applications, e.g. CAD applications, where such situations can occur, as shown in Figure 8. In that case, one could advantageously consider the approach proposed by Mäntylä [START_REF] Mäntylä | Boolean operations of 2-manifolds through vertex neighborhood classication[END_REF], which treats all the possible scenarios explicitly, to disambiguate boundary cases. Other remarks are in order: The rst boundary case -when the intersection is a point-can alternatively be dealt with by considering the regularized intersection operation ∩ * , thus assuming that there is no intersection between the triangles.

Others numerical stability issues related to xed numerical precision, e.g.

newly computed intersection segments might not be strictly co-planar with the original triangles, are handled by using exact geometrical predicates.

See 4.6 for implementation details.

In practice, triangles having near-zero area are also eliminated, should they occur, by using two mesh operations: edge collapse and edge ip.

Time Complexity

The overall time complexity of the algorithm depends on the number n and relative sizes of facets and it is of O(n log 3 (n)) expected time (the average case).

This complexity is dominated by the number of operations required to determine intersections. Each triangle requires O(log 3 n) tests, thanks to the fast box intersection method used, described in [START_REF] Zomorodian | Fast software for box intersection[END_REF] and implemented in [START_REF] Kettner | Intersecting sequences of dD iso-oriented boxes[END_REF]. The complexity of the method is O(n log d (n) + k) for the running time and O(n) for the RR n°7136 space occupied, d the dimension (3 in the current case), and k the output complexity, i.e., the number of pairwise intersections of the triangles. In practice, more than 80% of the running time is spent computing the self-intersections.

Typically, the running time for performing the self-intersections test is under

1 second for a mesh with 50, 000 facets on a 2.6 GHz Intel Core2Duo, with no multi-threading, and where exact arithmetic is used for triangle intersections and where the self-intersections are in the range of 100.

Comparison with a Static Algorithm

Alternatively, one could use the valid triangle test, described in Section 2, in order to devise another static algorithm, which will test all the existing triangles and sub-triangles obtained from local Delaunay triangulations. The method will only choose the triangles that reside on the exterior, after which it will proceed to the nal triangle stitching step.

However, this static algorithm would take considerably longer time, since it requires the same initial time O(n log 3 n) to compute all the triangle intersections and local Delaunay triangulations, followed by the additional time required for the valid triangle test, which is not negligible. Nevertheless, it should be noticed that this static algorithm is much simpler to implement than the proposed one and could be of interest in some applications, e.g. for validation purposes.

Implementation Details

In our implementation we have made use of CGAL (Computational Geometry Algorithms) C++ library [START_REF] Board | CGAL-3.2 User and Reference Manual[END_REF], which provides guaranteed implementations for various algorithms. We have used the following CGAL modules: N-dimensional fast box intersections, 2-D constrained Delaunay triangulation, AABB trees, triangular meshes and support for exact arithmetic kernels.

Mesh evolution

A number of methods exist in the literature that deal with deformable surfaces, such as Kenneth Brakke's Evolver 1 , Wojtan and Turk's visco-elastic simula- tor [START_REF] Wojtan | Fast viscoelastic behavior with thin features[END_REF] or the work of Celniker and Gossard on deformable surfaces [START_REF] Celniker | Deformable curve and surface nite-elements for free-form shape design[END_REF]. Nevertheless, the above mentioned methods are all mesh-based topology preserving.

This might be or not a desired feature of the algorithm, depending on the target application. It is our goal, in the current section, to introduce an intuitive generic mesh evolution paradigm that is topology adaptive, based on Trans-forMesh. The main steps of the algorithm are presented in Figure 9. Within each evolution iteration, there are four steps. Firstly, a velocity vector eld F is computed for each vertex of the mesh M. This step is application specic. Secondly, the mesh is deformed using the computed velocity vector eld F and a small time step t, thresholded by a maximum movement α • e avg (v), where α is a user-set threshold (typically between 0.1-0.3) and e avg (v) represents the local average edge length for a vertex v. is attained by computing the discrete mesh Laplacian [START_REF] Delingette | Shape representation and image segmentation using deformable surfaces[END_REF][START_REF] Meyer | Discrete dierential geometry operators for triangulated 2-dimensional manifolds[END_REF], i.e. the discrete Laplace-Beltrami operator, ∆v for each vertex v of the mesh. Furthermore, the mesh is smoothed using v → v -β∆v. These four main steps are repeated until the mesh has reached the desired nal state, also application specic.

We will present below two examples, one for mesh morphing in section 6, demonstrating the ability of the algorithm to handle complex surface evolutions, and the other one for multi-view 3-D reconstruction in section 7. In both cases, the application specic information is detailed in order to compute the vector elds F morphing and F reconstruction , which plug directly within the generic mesh evolution framework presented in Figure 9.

Choosing the correct time step. The currently presented mesh evolution approach does not make any assumptions about choosing the right time-step.

This parameter is entirely application specic. The TransforMesh algorithm does not have any information about the temporal component. It is therefore entirely up to the user to choose a meaningful time-step t which will capture all the temporal dynamics. The only measure proposed in the generic evolution algorithm is to threshold the maximum vertex movement to α • e avg (v), in order to prevent both large jumps and to reduce the number of intersections.

Remeshing. The remeshing step is important and should theoretically occur at each timestep, due to the fact that some regions can become undersampled in areas where the speed vector eld is divergent or over-sampled in areas where the speed vector eld is convergent. More importantly, intersections can generate poorly shaped triangles, which would probably have an impact on the local numerical process applied to the mesh that produces the vector eld.

Surface morphing

A straightforward mesh evolution application of our algorithm is surface morphing, that is starting from a source surface S A and evolving it towards a destination surface S B . This will allow us to test thoroughly various cases of topology changes. Surface morphing has been widely described in the literature. We will adopt the method proposed by Breen and Whitaker [START_REF] Breen | A level-set approach for the metamorphosis of solid models[END_REF]. We will summarize the reasoning that leads the surface evolution equation.

RR n°7136

Generic Mesh Evolution using TransforMesh While Not Finished 1. Compute Velocity Vector Field F of velocities for each vertex of the mesh M, using application specic information.

2. Evolve Mesh M using the vector eld F and a small time-step t, thresholded by a maximum α • e avg (v), where α is a user-set threshold (typically set between 0.1-0.3) and e avg (v) is the local average edge length for a vertex v. b) Vertex Valence Optimization: perform edge swaps such that each vertex will be shared by 6 triangles [START_REF] Kobbelt | Multiresolution shape deformations for meshes with dynamic vertex connectivity[END_REF].

c) Perform Mesh Laplacian Smoothing: each vertex v is updated by v → v -β∆v, where ∆v represents the discrete mesh Laplacian [START_REF] Delingette | Shape representation and image segmentation using deformable surfaces[END_REF][START_REF] Meyer | Discrete dierential geometry operators for triangulated 2-dimensional manifolds[END_REF].

Figure 9: Generic mesh evolution algorithm using TransforMesh.

Methodology

A metric that quanties how much two surfaces overlap is dened (source surface S A and destination surface S B ). A natural choice of such a metric is the signed distance function γ B of the destination mesh S B ', dened as in the level set literature as being negative inside the shape S B , zero on the surface, and positive on the exterior. By considering the volume integral M S B (S A ) of any surface S A with respect to γ B (thus S B ), one can see that it will achieve the maximum when the two surfaces overlap. By taking the rst variation of the metric M S B (S A ) with respect to the surface S A and a small displacement eld and dierentiating with respect to the vector eld, one obtains the following evolution equation using a hill climbing strategy for each vertex x along its normal N(x):

F morphing = ∂S ∂t = -γ B (x)N(x) (1)
The evolution strategy described above will converge to a local minimum.

Given the surface of departure S A and the destination surface S B , S A will correctly nd all the connected components of S B that are included in the original surface S A . If S A represents a surface outside the destination surface S B , S A will converge to an empty surface. We keep this result in mind when choosing the initial surface S A . then the point p will evolve along its normal with a magnitude of (p -q) • N (p), thresholded by a maximum user set evolution magnitude.

In the general case, in order to calculate an exact distance function γ B , one would have to consider the distance from a query point to the each of the facets of the mesh (representing the surface S B ), keeping the closest distance. This process will take O(N F ), where N F represents the number of facets. This is a fairly expensive computation, which will have to be performed at each iteration throughout the evolution for every vertex.

There exists a large number of methods for computing 3-D distance elds.

For a recent survey, please consult [START_REF] Jones | 3D distance elds: A survey of techniques and applications[END_REF]. As per [START_REF] Jones | 3D distance elds: A survey of techniques and applications[END_REF], the methods can be classied according to two criteria. According to the rst criterion, they can be:

Chamfer methods, where the new distance of a voxel is computed from the distances of its neighbors by adding values from a distance template;

vector methods where each voxel stores a vector to its nearest surface point and the vector at an unprocessed voxel is computed from the vectors at its neighbors by means of a vector template and Eikonal solvers, where the distance of a voxel is computed by a rst or second order estimator from the distances of it's neighbors.

According to the second criterion, the distances can be propagated throughout the volume in a:

sweeping scheme, when the propagation starts in one corner of the volume and proceeds in a voxel-by-voxel, row-by-row fashion to the opposite end, typically requiring multiple passes in dierent directions, or in a wavefront scheme, when the distances are propagating from the initial surface in the order of increasing distances until all voxels are covered.

RR n°7136

For our testing purposes, we propose an approximation/heuristic using the distance to the closest vertex point, as illustrated in Figure 10. If for a point p ∈ S A , the closest point from S B is q, the evolution equation for point p is:

γ B (p) = (q -p) • N (p), (2)
where γ was introduced in (1). Note that the vector magnitude will be thresh- olded to a maximum of α • e avg (p), as per step 2 of the generic mesh evolution algorithm, described in Figure 9. The distance and sign from a query point are computed on the y, as supposed to being stored in a distance eld 3-D grid.

The computation time is reduced drastically due to the use of proper search structures. The search time for the nearest neighbor is O(log(N V )), where N V represents the number of vertices. There is an initial overhead of O(N V log(N V ))

of building the search tree. In practice, we have used the implementation of [START_REF] Hjaltason | Ranking in spatial databases[END_REF] available in CGAL. Note that if the target surface S B contains a good enough mesh resolution, this approximation is very close to the true signed distance function. Also, if the accuracy of distance eld computation is of concern, more exact implementations could be adopted [START_REF] Jones | 3D distance elds: A survey of techniques and applications[END_REF].

In the case of sucient sampling, the current approximation will return a vertex belonging to the closest triangle where the true projection would be.

Thus, the error bound is the distance between the vertex and the projection.

In practice, however, we do not use the actual distance, but its sign, in order to establish the direction of the evolution. This makes the current approximation t for our purpose. Alternatively, one could easily verify all the incident triangles to the closest vertex to establish the true distance function, if the application requires it, keeping in mind that the sucient sampling condition still applies.

The current heuristic only makes use of the mesh vertices of S B , together with their associated normals. This has the great advantage of being able to be applied in the current formulation, not only to meshes, but also to oriented 3-D points. This would allow one to morph an initial mesh S A towards a set of oriented 3-D points P B . If orientation information is not available, it can be estimated from neighboring points using principal component analysis [START_REF] Hoppe | Surface reconstruction from unorganized points[END_REF]. Alternatively, in the context of multi-view stereo, it can be obtained via a minimization scheme [START_REF] Furukawa | Accurate, dense and robust multi-view stereopsis[END_REF].

Results

In Figure 11 we present results obtained with four test cases, entitled "Genus 3", "Thoruses", "Knots In" and "Knots Out". As it can be observed, the algorithm successfully deals with merge and split operations as well as handling multiple connected components. The average computation time per iteration on a 2.6

GHZ Intel Core2Duo processor varies between 0.2 to 1.6 seconds, depending on the number of facets and on the number of intersections. More detailed statistics are presented in Table 1.

In terms of parameter settings with respect to the generalized mesh evolution framework depicted in Figure 9 within which we casted the current mesh morphing algorithm, we considered t = 1 for the timestep, α = 0. Additional results of mesh morphing are presented in Figure 12, with meshes obtained from 3-D reconstructions from multiple cameras, in the context nonrigid surface tracking [START_REF] Varanasi | Temporal surface tracking using mesh evolution[END_REF].

Multi-View 3-D Reconstruction

In this section we explain how our method ts into the multi-view/image-based 3D reconstruction pipeline. The problem of reconstructing an object from images gathered with a large number of cameras has received a lot of attention in the recent past [START_REF] Hernández | Silhouette and stereo fusion for 3-D object modeling[END_REF][START_REF] Pons | Multi-view stereo reconstruction and scene ow estimation with a global image-based matching score[END_REF][START_REF] Seitz | A comparison and evaluation of multi-view stereo reconstruction algorithms[END_REF][START_REF] Vu | Towards high-resolution large-scale multi-view stereo[END_REF][START_REF] Vu | Towards high-resolution large-scale multi-view stereo[END_REF]. It is interesting to notice that, until recently, there were only a handful of mesh-based solutions to the surface reconstruction problem. This is mainly due to the topological problems raised by existing mesh-evolution methods. In particular, topological-preserving approaches are ill adapted to the problem of surface reconstruction. Topological-adaptive al-RR n°7136 gorithms, such as TransforMesh provide a more exible solution that allows to better resolve for local details using topological changes.

In [START_REF] Pons | Multi-view stereo reconstruction and scene ow estimation with a global image-based matching score[END_REF] the multi-view reconstruction problem is cast into an energy minimization problem using photometric constraints. It is well known that topological changes may take place during the minimization process, e.g., Figure 15. Surface evolution based on a level-set formulation is proposed in [START_REF] Pons | Multi-view stereo reconstruction and scene ow estimation with a global image-based matching score[END_REF]. Our contribution to this class of reconstruction methods is to extend such surface evolution approaches to meshes that allow to focus on the shape's surface instead of a bounding volume.

The method described below was applied both to visual hulls, e.g., [START_REF] Franco | Exact polyhedral visual hulls[END_REF] and to sparse point-based 3-D data, e.g., [START_REF] Zaharescu | Robust factorization methods using a gaussian/uniform mixture model[END_REF]. The former representation constitutes the initial mesh that needs be improved using photometric information from the available images. The latter representation can be easily turned into a rough mesh using [START_REF] Amenta | The power crust, unions of balls, and the medial axis transform[END_REF] for example.

Methodology

The initial meshed surface corresponds to an extended bounding box obtained using image silhouettes and a geometric approach that involves cone intersections in 3-D, i.e., [START_REF] Franco | Ecient polyhedral modeling from silhouettes[END_REF]. Such a mesh is only a coarse approximation of the observed surface. One main limitation of visual hull approaches is that they do not recover concave regions. The initial surface can be improved by considering photometric information in the images. The underlying principle is that, with a correct geometry, and under the Lambertian surface assumption, the mesh should be photo-consistent, i.e., its projections in the images should have similar photometric information [START_REF] Dyer | Photorealistic scene reconstruction by voxel coloring[END_REF].

The photometric constraints are casted into an energy minimization framework, using a similarity measure between pairs of cameras that are close to each other, as proposed by Pons et al. [START_REF] Pons | Multi-view stereo reconstruction and scene ow estimation with a global image-based matching score[END_REF]. The problem is solved in practice via gradient descent. E img is the derivative of the local photoconsistency term, in the normal direction, that can be computed using several methods. To compute such a derivative, we use one of the most ecient approaches [START_REF] Pons | Multi-view stereo reconstruction and scene ow estimation with a global image-based matching score[END_REF], based on the normalized cross-correlation. The evolution equation is in this case:

INRIA F reconstruction = ∂S ∂t = E img (x)N(x). (3)
In [START_REF] Pons | Multi-view stereo reconstruction and scene ow estimation with a global image-based matching score[END_REF] the surface evolution is implemented within the level-set framework.

We extended it to meshes using the TransforMesh algorithm. The level-set solution performs surface evolution using a coarse-to-ne approach in order to escape from local minima. Traditionally, in level-set approaches, the implicit function that embeds the surface S is discretized evenly on a 3-D grid. As a sideeect, all the facets of the recovered surface are of approximately equal triangle size. In contrast, mesh based approaches do not impose such a constraint and allow facets of all sizes on the evolving surface. This is particularly useful when starting from rough surface estimates, such as visual hulls, where the initial mesh contains triangles of all dimensions. In addition, the dimension of visual facets appears to be a relevant information since regions where the visual reconstruction is less accurate, i.e. concave regions on the observed surface, are described by bigger facets on the visual hull. Thus, we adopt an approach in which bigger triangles are processed rst, until they are stabilized, then the whole process is repeated at a ner scale.

The mesh evolution algorithm depicted in Figure 9 requires a number of parameters to be set in advance. In the case of 3-D reconstruction we used the following parameter settings in all our examples: t = 0.001 for the time step, α = 0.1 and e avg for the maximum movement amplitude and β = 0.

Results

We have tested the mesh evolution algorithm with the datasets provided by the Multi-View Stereo evaluation site [START_REF] Seitz | A comparison and evaluation of multi-view stereo reconstruction algorithms[END_REF] 2 . The ground-truth is obtained from laser-scans. Comparative and detailed results are extracted from the Middlebury website and are presented in Table 2. The table includes results from Furukawa and Ponce [START_REF] Furukawa | Accurate, dense and robust multi-view stereopsis[END_REF], Pons et al. [START_REF] Pons | Multi-view stereo reconstruction and scene ow estimation with a global image-based matching score[END_REF], Vu et al. [START_REF] Vu | Towards high-resolution large-scale multi-view stereo[END_REF] and Hernandez and Schmitt [START_REF] Hernández | Silhouette and stereo fusion for 3-D object modeling[END_REF]; all these methods yield state-of-the-art results. The dierences between all these methods are very small, ranging between 0.01mm to 0.1mm. methods is to provide a purely geometric mesh-based solution that is correct, that does not constrain meshes and that allows for facets of all sizes as well as for topological changes.

The TransforMesh algorithm was plugged into a generic mesh-evolution framework, thus allowing to address two challenging problems within a topologyadaptive approach: surface morphing and multi-view image-based 3-D reconstruction.

We provided both a detailed description of the proposed algorithm as well as an in-depth analysis of its convergence and performances (numerical stability and time complexity). In the case of surface morphing, we showed that TransforMesh can deal with challenging topological cases.

Figure 1 :

 1 Figure 1: Interior and exterior regions delimited by an oriented primitive. Apoint is on the exterior when it belongs to a region with a winding number wn equal to 0, on the interior otherwise.

Figure 2 :

 2 Figure 2: The winding number at p can be obtained by summing the dot product signs with face normals along any ray from p.

Figure 3 :

 3 Figure 3: Overview of TransforMesh.

Figure 4 :

 4 Figure 4: Partially valid triangle traversal. (a)The intersections with all other triangles are computed for each intersecting triangle. (b) close-up of the bottom triangle in (a). The local geometry is re-dened using a constrained 2-D Delaunay triangulation that ensures the presence of the original triangle edges and the intersection segments. The traversal starts at the entrance edge and stops on constraint edges thus marking T D1 , T D2 and T D3 as valid.

Figure 5 :

 5 Figure 5: The 2 partially valid triangle crossing cases.

Figure 6 :

 6 Figure 6: Special cases encountered while stitching a triangle soup.

  (b), in a mesh morphing scenario, where the initial surface has 1 connected component and the destination 2 connected components. The 2 other examples, hole formation and loss, are less frequent. While handled by the algorithm, we do not account for them in practice since, as mentioned earlier, inside valid faces are usually not considered in surface evolution processes.

Figure 7 :

 7 Figure 7: Topological changes (2-D simplied view).

Figure 8 :

 8 Figure 8: Two inverted cylinders example. Examples of a boundary case testing numerical stability and the solutions provided by the algorithm.

3 .

 3 Invoke TransforMesh on M in order to clean self-intersections and topological problems 4. Mesh Optimization a) Adaptive Remeshing: ensures that all edges are within a safety zone interval, i.e. ∀e ∈ M, e ∈ [e 1 , e 2 ], by performing edge swaps or edge collapses.

Figure 10 :

 10 Figure10: Mesh Morphing evolution step. The surface S A evolves from time t to time t + 1 towards S B . If for point p ∈ S A , the closest point in S B is q, then the point p will evolve along its normal with a magnitude of (p -q) • N (p),

2 Figure 11 :

 211 Figure 11: Mesh morphing examples. Dierent steps for various test cases. Each column corresponds to a test case. The rst row represents the rst iteration, whereas the last row represents the last iteration.

Figure 12 :

 12 Figure 12: Example of topological changes during mesh morphing in surface tracking. The source surface S t , shown to the left, is the result of a deformation of the original mesh S t at time t such that it matches closely the mesh S t+1 at t + 1, shown to the right. The mesh morphing process ensures the proper handling of topological changes (i.e. the whole formation in the arm region).

  Some of our reconstruction results are shown in Figure13and Figure14. While Vu et al.[START_REF] Vu | Towards high-resolution large-scale multi-view stereo[END_REF] used the same energy functional as part of their 3-D reconstruction pipeline, their improved results are mostly due to the fact that the mesh regularization term takes into account photo-consistency.

Figure 14 Figure 13 :Figure 14 :

 141314 Figure14shows the results obtained with our method when starting with very rough meshes that correspond to coarse triangulations obtained from a sparse set of 3-D points. An example of how TransforMeshhandles topological changes is shown in Figure15. This gure shows a typical evolution scenario where there are more topological problems at the beginning; As the algorithm converges, self-intersections barely occur.Finally, Figure16shows results obtained with the Man-dance sequence publicly available from the Multiple-video database of the PERCEPTION group at INRIA 3 .

Figure 15 :Figure 16 :

 1516 Figure 15: Example of topological changes during in 3-D reconstruction for the dinosaur sequence, introduced in Figure 14. The start-up surface, obtained from triangulated 3-D points via PowerCrust [6] contains several topological errors (i.e. the extra branch connecting the dinosaur's limbs). They are corrected during the surface evolution, ash shown in the right most image.

The 3 -

 3 D reconstruction method that we described and which is based on mesh evolution is extremely versatile. The method recovers a correct discrete surface geometry starting from very coarse approximations, such as visual hulls or sparse sets of 3-D points. The 3-D reconstruction results are of comparable quality with state-of-the-art methods recently developed by computer vision researchers.INRIA

  The adaptive remeshing step ensures that all edges are within a safety zone interval (e 1 , e 2 ), which is user-dened. This prevents edges from reaching close to zero sizes. In practice, this is obtained through edge collapse or edge swap operations. The vertex valence optimization step performs edge swaps in an attempt to ensure an overall vertex valence of 6[START_REF] Kobbelt | Multiresolution shape deformations for meshes with dynamic vertex connectivity[END_REF].Vertex valence is dened as the number of edges shared by a vertex. The ideal vertex valence of 6 is desirable because, assuming that the manifold is generally locally planar, it is equivalent to obtaining 60 • for each of the sharing triangle angles, thus optimizing for equilateral triangles. Alternatively, the vertex valence can also be improved by performing edge swaps only if it increases the minimum angle of either triangle adjacent to the edge. The Laplacian smoothing

	ensuring good mesh properties. Ideally, a mesh should consist of triangles as
	close to equilateral as possible, which allows for better computations of local
	mesh properties, e.g. curvatures and normals. To this purpose, a number of
	sub-steps are being performed: adaptive remeshing, vertex valence optimization
	and Laplacian smoothing.
	INRIA

Thirdly, TransforMesh is invoked in order to clean the potential self-intersections and topological problems introduced by the second step. The fourth step involves mesh optimization, with the goal of 1 http://www.susqu.edu/facstaff/b/brakke/evolver/evolver.html

Table 1 :

 1 Mesh morphing statistics for dierent datasets. The reported values

	Dataset	Genus 3	Thoruses	Knots In	Knots Out
	Iterations	54	37	119	430
	# Facets	4764.14	6296.33	13244.25	3873.11
	# Intersections	33.88	22.67	101.52	4.86
	Time (TransforMesh)	0.65 sec	0.81 sec	1.63 sec	0.18 sec
	Time (total)	1.42 sec	1.78 sec	3.58 sec	0.89 sec
	presented in the bottom four rows represent average values accumulated across
	the iterations. The running time is recorded on a 2.6 GHz Intel Core2Duo
	processor.

  where edgeSize(p 1 , p 2 ) is a function that computes the desired edge size such that it has p 1 pixels using images at scales p 2 . The initial scale s max is computed such that the largest edges of the initial mesh measure 5 pixels when projected into the images at scale s max . When the ner scale is reached, new iterations are run by decreasing e 2 from edgeSize(5, 1) to edgeSize(2, 1) in λ = √ 2 decrements.

		Temple Ring	Temple Sparse	Dino Ring	Dino Sparse
		Acc.	Compl.	Acc.	Compl.	Acc.	Compl.	Acc.	Compl.
	[50]	0.60	99.5%	0.90	95.4%	0.55	99.0%	0.71	97.7%
	[23]	0.47	99.6%	0.63	99.3% 0.28	99.8% 0.37	99.2%
	[26]	0.52	99.5%	0.75	95.3%	0.45	97.9%	0.60	98.52%
	[57]	0.45	99.8%			0.53	99.7%
	Us	0.55	99.2%	0.78	95.8%	0.42	98.6%	0.45	99.2%

1 for the smoothing term. The meshes have an adaptive mesh resolution. As mentioned earlier, we ran the algorithm at dierent scales, starting from scale s max to s min = 1 in λ = √ 2 decrements. For each scale s i , the input images and camera matrices are downscaled accordingly. The appropriate edge size interval is set to e 1 = edgeSize(1, 1) e 2i = edgeSize(5, i),

Table 2 :

 2 Middleburry 3-D Reconstruction Results. Accuracy (expressed in milimeters): the distance d (in mm) that brings 90% of the result R within the ground-truth surface G. Completeness: the percentage of G that lies within 1.25mm of R.

	RR n°7136

http://www.inria.fr ISSN 0249-6399

Acknowledgments

We thank Jean-Philippe Pons and Renaud Keriven for providing the source code for the gradient computation needed by multi-view 3D reconstruction.

This research was supported by the the EC Marie-Curie program through the VISION-TRAIN project. Une Méthode de Déformation de Maillage par Topologie Adaptative pour l'Evolution de Surfaces, le Morphing et la Reconstruction