Reconstruction Algorithms as a Suitable Basis for Mesh Connectivity Compression

Raphaëlle Chaine, Pierre-Marie Gandoin and Céline Roudet

Abstract-During a highly productive period running from 1995 to about 2002, the research in lossless compression of surface meshes mainly consisted in a hard battle for the best bitrates. But for a few years, compression rates seem stabilized around 1.5 bit per vertex for the connectivity coding of usual triangular meshes, and more and more work is dedicated to remeshing, lossy compression, or gigantic mesh compression, where memory access and CPU optimizations are the new priority. However, the size of 3D models keeps growing, and many application fields keep requiring lossless compression. In this paper, we present a new contribution for single-rate lossless connectivity compression, which first brings improvement over current state of the art bitrates, and secondly, does not constraint the coding of the vertex positions, offering therefore a good complementarity with the best performing geometric compression methods. The initial observation having motivated this work is that very often, most of the connectivity part of a mesh can be automatically deduced from its geometric part using reconstruction algorithms. This has already been used within the limited framework of projectable objects (essentially terrain models and GIS), but finds here its first generalization to arbitrary triangular meshes, without any limitation regarding the topological genus, the number of connected components, the manifoldness or the regularity. This can be obtained by constraining and guiding a Delaunay-based reconstruction algorithm so that it outputs the initial mesh to be coded. The resulting rates seem extremely competitive when the meshes are fully included in Delaunay, and are still good compared to the state of the art in the case of scanned models.

Note to Practitioners-A 3D triangle mesh is composed of a geometric part (the vertex coordinates) and a connectivity part (the description of the triangles). In this article, we show how to reencode such surface meshes in order to obtain near zero connectivity cost for some class of surface meshes (and very good rates in the general case), while guaranteeing in the same time state-of-the-art geometry encoding cost. This method can be useful in all application areas where the mesh size is a bottleneck (typically network or storage applications). The best results are obtained for meshes made from 3D scans (in contrast to CAD meshes). The main current limitations of the method are the computing times (about 1 second per 1000 points part of the mesh, for compression which can be done off-line) and the memory footprint.

Index Terms-Mesh, Compression, Reconstruction, Lossless, Connectivity

I. INTRODUCTION

For several years, meshes have played a leading role in computer graphics, and their ability to model the world throws them in the heart of advanced applications in all the fields Université de Lyon, Lyon, F-69003, France ; université Lyon 1, Villeurbanne, F-69622, France, université Lyon 2, Bron, F-69676, France, CNRS, UMR 5205, LIRIS, Villeurbanne, F-69622, France FirstName.LastName@liris.cnrs.fr of science, arts or leisure. If some of these applications can tolerate a limited loss of information (provided that this loss is well controlled and does not damage a certain visual realism), the others, for practical or even legal reasons, impose to work continuously with exact copies of original objects. In this case, the only way of optimizing the storage and the transmission of 3D information is to have recourse to lossless compression methods.

A mesh is defined by a set of points (we speak of the geometry of the mesh), and by a combinatorial structure describing the relations between these points, using geometric objects of higher dimensions: edges, facets (we speak of the connectivity or the topology of the mesh). To this fundamental information are sometimes added attributes allowing to improve the rendering: normals, colors or textures. If we put aside these attributes (they relate only to a subset of the meshes met in practice), all the difficulty for compressing 3D objects is to efficiently process both the geometry and the connectivity of a wide class of meshes. However, most of the methods proposed so far stress on one of these two aspects (usually the connectivity), generally to the detriment (or at least, not to the advantage) of the other one, which is constrained by a description order rarely optimal in terms of compression. In this article, we propose a new single-rate connectivity coder which is not only general and efficient, but also does not impose any constraint on the coding of the geometry. In particular, it is totally compatible with the position coders that currently propose the best compression rates.

We took it as given that very often, the main part of a mesh connectivity can be deduced from its vertex set using reconstruction methods. This remark has already been made in the past, but the problem was to find an effective way of describing the difference between the initial mesh and its reconstructed version. Indeed, within the framework of lossless compression, it is indispensable to be able to correct these errors in order to obtain a decoded mesh perfectly identical to the original mesh. But rather than describe the difference to the initial object at the end of the reconstruction phase, we suggest adapting an existing algorithm so that it can accept occasional codes modifying its default behavior at the moments when it would commit an "error" of reconstruction with regard to the initial mesh.

Having placed our work in the historical context of 3D compression and 3D reconstruction (Sec. II), we will expose the general principle of the method (Sec. III), first within the restricted framework of Delaunay meshes, then generalized to arbitrary triangular meshes (independent of the genus, the number of connected components, the regularity and the manifoldness). Then we will detail the coding techniques and optimization steps leading to better compression rates (Sec. IV), before presenting some comparative results and comments on the method performances (Sec. V).

II. CONTEXT AND PREVIOUS WORKS

A. Mesh Compression

As mentioned above, a mesh is composed of both a geometric part (the vertex positions), and a topological part (the vertex connectivity). Now, by looking at the whole scientific production in mesh compression since 1995 until now, we notice clearly that the connectivity coding has motivated most of the proposed methods. The usual scheme consists in describing the combinatorial structure by enumerating its vertices in a precise order, designed to minimize the size of the code: each vertex is coupled with a variable size symbol defining the way it is connected to the rest of the mesh. Consequently, the geometric coder has to work with this predefined order of the vertices, but it can exploit the connectivity to predict their location. The position of the currently transmitted vertex is estimated from its neighbors, and the prediction error is the sole information to be coded. But the order imposed by the connectivity coding is not necessarily favorable to this prediction, as shown by the results obtained on usual meshes by classical algorithms: the best of them reduce the connectivity information to less than 1 or 2 bits per vertex, while for the geometric part, the rates rarely go down under 90% of the initial size (except for very low quantizations). Among the works that follow this principle, we focus here in single-rate methods, which code and decode the mesh in one pass and do not allow progressive visualization [START_REF] Deering | Geometry compression[END_REF], [START_REF] Evans | Optimizing triangle strips for fast rendering[END_REF], [START_REF] Taubin | Geometric compression through topological surgery[END_REF], [START_REF] Gumhold | Real time compression of triangle mesh connectivity[END_REF], [START_REF] Touma | Triangle mesh compression[END_REF], [START_REF] Li | A dual graph approach to 3d triangular mesh compression[END_REF], [START_REF] Bajaj | Error resilient streaming of compressed vrml[END_REF], [START_REF] Bajaj | Single resolution compression of arbitrary triangular meshes with properties[END_REF], [START_REF] Gumhold | Tetrahedral mesh compression with the cut-border machine[END_REF], [START_REF] Rossignac | Edgebreaker : Connectivity compression for triangle meshes[END_REF], [START_REF] Rossignac | Wrap&zip : Linear decoding of planar triangle graphs[END_REF], [START_REF] King | Guaranteed 3.67v bit encoding of planar triangle graphs[END_REF], [START_REF] Isenburg | Mesh collapse compression[END_REF], [START_REF] Isenburg | Triangle fixer : Edge-based connectivity encoding[END_REF], [START_REF] Alliez | Valence-driven connectivity encoding for 3d meshes[END_REF], [START_REF] Lee | Angle-analyzer: A triangle-quad mesh codec[END_REF], [START_REF] Coors | Delphi : Geometry-based connectivity prediction in triangle mesh compression[END_REF], [START_REF] Kaelberer | Freelence -coding with free valences[END_REF], [START_REF] Jong | An efficient connectivity compression for triangular meshes[END_REF]. To understand how these methods compare, the reader can also refer to the following surveys [START_REF] Alliez | Recent Advances in Compression of 3D Meshes[END_REF], [START_REF] Gotsman | Simplification and Compression of 3D Meshes[END_REF], [START_REF] Peng | Technologies for 3d mesh compression : A survey[END_REF]. It is worth to mention here that the relative stability in compression rates observed these days can be explained by the new interest of the community for gigantic meshes: in this framework, the challenge is to improve the efficiency of the compression in terms of CPU and memory requirements rather than in terms of bitrates [START_REF] Isenburg | Out-of-core compression for gigantic polygon meshes[END_REF], [START_REF] Isenburg | Streaming meshes[END_REF], [START_REF] Isenburg | Streaming compression of triangle meshes[END_REF].

B. Prioritizing the Geometric Coding

After this first wave of works, in the knowledge that the geometry of a mesh weighs generally much more than its connectivity, the researchers began to propose methods giving the priority to geometric compression. Some of them deviate from the lossless framework by proposing algorithms that often impose a complete remeshing of the object before applying spectral decomposition tools like wavelets, subdivision schemes, or classic geometric methods of compression [START_REF] Gross | Efficient triangular surface approximations using wavelets and quadtree data structures[END_REF], [START_REF] Certain | Interactive multiresolution surface viewing[END_REF], [START_REF] Lounsbery | Multiresolution analysis for surfaces of arbitrary topological type[END_REF], [START_REF] Staadt | Multiresolution compression and reconstruction[END_REF], [START_REF] Guskov | Normal meshes[END_REF], [START_REF] Khodakovsky | Progressive geometry compression[END_REF], [START_REF] Khodakovsky | Normal mesh compression[END_REF], [START_REF] Karni | Spectral compression of mesh geometry[END_REF], [START_REF] Szymczak | Piecewise regular meshes : Construction and compression[END_REF], [START_REF] Attene | Swingwrapper : Retiling triangle meshes for better edgebreaker colmpression[END_REF].

On the other hand, the works introduced by Gandoin and Devillers and improved by Peng and Kuo [START_REF] Devillers | Geometric compression for interactive transmission[END_REF], [START_REF] Gandoin | Progressive lossless compression of arbitrary simplicial complexes[END_REF], [START_REF] Peng | Geometry-guided progressive lossless 3d mesh coding with octree decomposition[END_REF] describe a progressive and lossless compression method, centered on the geometry, which interests us particularly within the framework of this article. Indeed, this method was originally designed to code an unstructured point cloud, with the underlying idea that in many cases, the connectivity information could be deduced from the geometry thanks to reconstruction algorithms. So, the first version of this method [START_REF] Devillers | Geometric compression for interactive transmission[END_REF] proposed a multiresolution compression algorithm for an unstructured point cloud, guaranteeing a theoretical minimal gain of n(log 2 n -2.4) (where n denotes the number of points), and very competitive practical performances, even compared to the best single-rate algorithms. The method was then extended to deal with the connectivity compression, while remaining centered on the geometry [START_REF] Gandoin | Progressive lossless compression of arbitrary simplicial complexes[END_REF]. Indeed, the kd-tree decomposition scheme involved in the heart of the geometric coder, is enriched with a connectivity coder that uses some of the classical mesh simplification operations introduced by Hoppe et al. [START_REF] Hoppe | Progressive meshes[END_REF], [START_REF] Popović | Progressive simplicial complexes[END_REF]). Eventually, the method has recently been resumed by Peng and Kuo [START_REF] Peng | Geometry-guided progressive lossless 3d mesh coding with octree decomposition[END_REF] who improve its performances by imposing a priority on the cell subdivision order in the octree, and by proposing a more effective prediction model for the point distribution in the sub-cells generated by a subdivision.

C. Compression and Reconstruction

The idea to entrust a reconstruction algorithm with the task of computing the connectivity of a mesh from its vertices has already been used in the context of mesh compression. Within the framework of terrain models, Kim et al. [START_REF] Kim | An improved TIN compression using Delaunay triangulation[END_REF] suggest transmitting only a fraction of the edges composing the object, and using constrained Delaunay triangulationin 2D, since the terrain models are projectable -to find the whole connectivity. Devillers and Gandoin [START_REF] Devillers | Geometric compression for interactive transmission[END_REF] also mention the compression of GIS as an application of their geometric coder, and develop an edge coder well suited for this context, which results in compression rates as low as 0.2 bits per vertex for the complete connectivity. Besides, Devillers et al. show that the minimal set to be transmitted to guarantee the exact reconstruction of the initial model by constrained Delaunay triangulation is constituted by the edges that are non locally Delaunay [START_REF] Devillers | Minimal set of constraints for 2D constrained Delaunay reconstruction[END_REF].

Unfortunately, the generalization from 2.5D to 3D meshes is not straightforward: since the mesh is not projectable any more, the use of the constrained Delaunay triangulation is impossible. Of course, it is possible to recourse to local projections of the mesh [START_REF] Gopi | Surface reconstruction based on lower dimensional localized delaunay triangulation[END_REF], but we are left with the problem (and the overcost) of joining the different parts together. Nevertheless, the idea to use a reconstruction method driven by a partial description of the connectivity remains extremely promising in terms of compression results. Provided that it could be possible to find a method both powerful and capable of taking advantage of partial connectivity data to guarantee an exact reconstruction whatever the initial model may be.

A first attempt to use a reconstruction algorithm to encode connectivity information has been proposed by Lewiner et al. [START_REF] Lewiner | Gencode : Geometry-driven compression in arbitrary dimension and co-dimension[END_REF]. The geometry is coded independently, through a kdtree based algorithm derived from [START_REF] Gandoin | Progressive lossless compression of arbitrary simplicial complexes[END_REF] and [START_REF] Botsch | Efficient high quality rendering of point sampled geometry[END_REF] and the connectivity is coded through an advancing front triangulation inspired of the ball-pivoting strategy [START_REF] Bernardini | The ball-pivoting algorithm for surface reconstruction[END_REF]. This algorithm requires a code for each edge of an active border that is initialized to a triangle. If the geometry of the mesh meets good sampling conditions, the entropy of each code will be extremely low. In Sec. V, we compare this method to ours regarding the compression rates.

D. Reconstruction by Convection

The problem of reconstructing a surface from a set of points has received considerable attention during the last decade [START_REF] Mencl | Interpolation and approximation of surfaces from three-dimensional scattered data points[END_REF]. Interesting and outstanding algorithms have been issued both in computer graphics and computational geometry, but we have decided to focus on the algorithms of the second category, since their combinatorial concerns are more suitable for lossless compression purposes. Most of computational geometry algorithms exploit the geometric properties of structures such as the Delaunay triangulation, the Voronoi diagram or the power diagram of the input point set, assuming auspicious properties on the way they were sampled on the surface (ε-sample [START_REF] Amenta | Surface reconstruction by voronoi filtering[END_REF]). A consistent set of facets can then be extracted from the geometric structure, sometimes using global heuristics or local analysis to solve ambiguities. The existing algorithms are numerous and an attempt to classify and distinguish them has recently been proposed in the state of the art by Cazals and Giesen [START_REF] Cazals | Delaunay triangulation based surface reconstruction : Ideas ans algorithms[END_REF]. Most of these algorithms produce triangular meshes, which makes them good candidates to use for compression purposes.

The convection algorithm we use in our method is based on a similar notion of flow as it was developed in the Wrap algorithm by Edelsbrunner [START_REF] Edelsbrunner | Surface reconstruction by wrapping finite point sets in space[END_REF], and the flow complex algorithm by Giesen and John [START_REF] Giesen | Surface reconstruction based on a dynamical system[END_REF]. Indeed, this reconstruction algorithm has been inspired from a surface convection process described by Zhao et al. [START_REF] Zhao | Fast surface reconstruction using the level set method[END_REF]. They use it to initialize their surface before running an energy minimization process in the level set framework. Given an evolving surface S enclosing an input point set P, the convection process makes each point of S move inwards, along the direction of its normal, towards its closest point in P. However, the numerical scheme they propose can be translated in the discrete setting of a 3D Delaunay triangulation, to make it depend on the geometry of the input data set only, and not on the precision of some grid around the surface. A demonstration of this result is presented by Chaine [START_REF] Chaine | A geometric convection approach of 3-d reconstruction[END_REF] together with a subsequent convection algorithm.

A Delaunay triangulation of P is a partition of space into tetrahedra so that the ball circumscribed to each tetrahedron does not contain any point of P. The convection process is run directly in the 3D Delaunay triangulation of P, with an evolving surface S composed of oriented Delaunay facets. S is initialized to the convex hull of P. An oriented facet of S that does not meet the oriented Gabriel property -i.e. the inwards half of its enclosing sphere is not empty -is attracted towards the 3 other facets of the incident Delaunay inner tetrahedra (see Fig. 1, for an illustration in 2D where the evolving surface is replaced by an evolving curve, and the Delaunay tetrahedra are replaced by Delaunay triangles). During the convection process, thin parts can appear (see Fig. 1, c andd), on which a surface embedded 2D version of the convection is run. A deeper explanation of this algorithm will be presented in Sec. III while revisiting it for compression purposes. An interesting property of the convection algorithm is that it is driven locally, in the Delaunay triangulation of the points, without involving a global heuristic. The topology of the evolving surface may change during the convection process, so that it can handle surfaces with boundaries and surfaces of high genus. A drawback of the convection process is that it can locally be stuck in presence of pockets [START_REF] Edelsbrunner | On the definition and the construction of pockets in macromolecules[END_REF] hiding facets, but a simple and local point density analysis permits to hollow them out [START_REF] Chaine | A geometric convection approach of 3-d reconstruction[END_REF].

III. PRINCIPLE OF THE COMPRESSION ALGORITHM

A. Introduction of the Convection Abilities

The benefit of using a 3D reconstruction method for compression purposes is double: first, this allows to obtain very low costs for the coding of the connectivity -ideally, a null cost if the reconstruction algorithm is able to find the exact structure of the original mesh by itself -, and secondly, unlike the previous methods of topological compression, no constraint is imposed on the order of the vertices to the geometric coder, which constitutes an important efficiency token.

The main difficulty consists in being able to help the reconstruction algorithm at a reasonable cost: indeed, it is highly improbable to design an algorithm capable of finding the complete connectivity of a mesh from its vertex set. It is thus necessary to be able to alter the course of the reconstruction process, by occasionally changing the default behavior of the algorithm to drive it in a sure way to a result known in advance: the structure of the initial mesh.

Among the plethora of available methods, the reconstruction by convection is distinguishable from others by two important assets: its qualities in terms of reconstruction -practical accuracy and faithfulness to the original model, handling of complex topologies, computation times -, and above all, its ability to be effectively driven by means of simple instructions.

The first asset guarantees that the algorithm will not need to be guided too often (small number of codes), the second guarantees that this can be done at lower cost (compactness of the codes).

In return, as many algorithms in computational geometry, the convection algorithm is based on a Delaunay triangulation, and it may be difficult to force it out of this structure. This imposes a condition over the initial mesh: all its facets have to belong to the 3D Delaunay triangulation of its vertex set. It is quite a strong property that is not verified by all the 3D objects met in practice. We will see in second stage (Sec. III-D) how to break it.

Intuitively, the reconstruction by convection consists in embedding the vertex set in a block of marble that will be sculpted gradually, facet after facet, tetrahedron after tetrahedron, until it takes on the shape of the object. The algorithm begins by preparing the sculpting material: an enclosing block which is nothing but the convex hull of the point cloud, as well as the network of galleries through which it is going to dig until the final shape is reached. This network is composed of the tetrahedra of the 3D Delaunay triangulation, and every stage towards the object shape consists in examining a new facet of the current surface and deciding if it is necessary or not to open it and excavate the inside of its associated tetrahedron. When a facet is opened, it is removed from the current surface of the 3D object under construction, and replaced by the three other facets of the excavated tetrahedron.

As mentioned above, the criterion that decides on this opening is purely local: it consists of observing whether the Gabriel half-sphere associated to the current oriented facet contains or not the fourth vertex of the tetrahedron. If it is the case, the oriented facet is opened and replaced in the current surface by the 3 other facets of the associated tetrahedron. (If this one is already excavated, the surface locally vanishes through the current facet.) Otherwise, it is maintained on the surface.

Note that if all the facets of the initial object are in its 3D Delaunay triangulation, they are reachable by this sculpture process from the convex hull. The problem is to make sure that the algorithm will not dig a facet belonging to the initial mesh, or that, conversely, it will not be retained before having reached such a facet. Hence the need for additional codes allowing to modify the behavior of the convection algorithm, and to drive it towards the object to be coded. Even if the convection algorithm was designed to compute the structure of a sufficiently dense mesh with a good accuracy, it will most likely need occasional assistance to guarantee the perfect reconstruction of any mesh.

B. Compliant Meshes

Definition: A mesh is said to be compliant if all its facets are in the 3D Delaunay triangulation of its vertex set, and if it is a manifold (that is to say without borders nor thin parts).

To present our method in a progressive way, we focus in this section on compliant meshes only. Given such a mesh M, here is the general principle of the compression algorithm:

1 Build the 3D Delaunay triangulation D of the point set P, 2 Mark the facets of D belonging to the initial mesh M, 3 Initialize the current surface S with the convex hull of P (included in D), 4 Launch the convection process on S: every oriented facet f in S is examined in turn, and depending on whether its Gabriel half-sphere is empty or not, f is, by default, maintained on S or replaced by its 3 neighbors in D. To modify this default behavior of the convection reconstruction, it is necessary to locate the oriented facets of S for which the algorithm has to act differently. It is thus indispensable to define a completely deterministic traversal of the facets in S, so that the n th oriented facet met during the compression would also be the n th oriented facet met during the decompression. More generally, it is necessary to ensure the synchronization of the algorithms of compression and decompression so that the n th action of the coder matches the n th action of the decoder. Thanks to these reference marks, the behavior of the convection process can be safely altered in the following two circumstances: a) when the convection asks for the opening of a facet f that belongs to M, the coder forbids this opening, and codes the index of f (more exactly, the moment when f is met in the algorithm) to warn the decoder that at this precise moment of the reconstruction, it has to break the rules of the convection algorithm. We will call this a RDG event (Retain Despite the Geometry), b) at the end of this first step, it is possible that some oriented facets of S -those whose Gabriel half-spheres are empty and thus the convection did not decide to dig -, do not belong to M. Therefore, it is necessary to specify to the decompression algorithm that these oriented facets must be forced, against the convection rules: for each remaining oriented facet of S not belonging to M, the coder transmits its index (i.e. the moment when it is met) and locally relaunches the convection process by forcing its opening. We call this a ODG event (Open Despite the Geometry). Note that by thus delaying the enforced opening of facets in a second step, rather than opening them the first time they are met, some facets that were due to be forced can disappear by autointersection of S: in some cases, the convection process reaches and automatically opens the opposite side (or half-facet) of a facet previously encountered but not opened then. This permits to save some ODG codes.

Fig. 2 is a step by step illustration of the algorithm in 2D, in the case where the deterministic traversal of the facets is induced by a breadth-first traversal of the Delaunay triangulation, starting from the convex hull. To be more illustrative, time has been incremented at each step of the algorithm, but in practice, it is enough to increase it each time the convection is willing to open a facet or each time a retained facet is tested for confirmation.

A detailed description of step 4 can thus be given through a recursive function Convection applied to the current surface S. An other difference with the step by step example is also that the facets are yet visited through a depth first traversal of the Delaunay triangulation. For each oriented facet f , let f asso denote the oriented facet associated to f , that is to say the oriented facet constructed on the same vertices as f , but with the opposite orientation. When f and f asso are both in the surface S, that means they belong to a thin part of S.

Besides, let f 1 , f 2 and f 3 denote the 3 neighbors of f in the 3D Delaunay triangulation D, i.e. the 3 other facets of the tetrahedron that is removed when f is opened. Finally, we would like to draw the reader's attention to the fact that the reference marks transmitted to the decoder are not exactly absolute moments of events in the compression process, but rather intervals between two such moments (which explains the presence of the instructions "time ← 0" in the detailed algorithms). This well-known technique of differential coding allows to reduce the size of the transmitted codes.

S ← { f 1 , f 2 , f 3 }

Convection(S) end if end if end while

At the end of the compression algorithm, the convection has been driven towards the initial mesh M, and the correcting data have been stored for the decompression algorithm. However, a last stage remains that consists in cleaning thin parts possibly generated by the convection. Indeed, since we first assumed that the initial mesh was a manifold, it suffices to delete all these thin parts, that is to say each facet of S whose associated facet is also on S. In the algorithm described above, the thin parts exactly match the set S border .

C. Non Manifold Meshes

In this section, we are going to extend the previous algorithm to non manifold, thin parts meshes. It suffices to modify the final stage regarding the treatment of thin parts created by the algorithm. This stage is replaced by a new convection process, but this time in its 2D version, and on thin parts only. In this framework, the convection updates a curve C constituted by the edges composing the boundaries of the thin parts. The oriented edges of C are examined in turn: an oriented edge whose Gabriel half-circle is empty will be kept on C, whereas an oriented edge in the opposite case will be removed and replaced in C by the two other oriented edges of its incident triangle (e 1 and e 2 in the algorithm detailed below).

The general principle remains the same as in the 3D version of the algorithm, and each edge that is opened against the convection rules (ODG event) launches a new 2D convection process. Note that there is no set C border similar to the previous S border . Here is a detailed version of the portion of the compression algorithm dedicated to the processing of the thin

D. Non Delaunay Meshes

As previously described, the method can only be applied to meshes whose facets belong to the 3D Delaunay triangulation of their vertex set. Indeed, we saw that this structure constitutes the support of the convection algorithm, and that it is thus impossible for the current surface to reach a non Delaunay facet. Nevertheless, most of the meshes met in practice contain a fraction of non Delaunay facets (see the unfavorable case of Fig. 3). So, to make the method widely usable, it is necessary to manage the coding of such facets. A simple and efficient way to do this is to code explicitly all the non Delaunay facets of the initial mesh in the same time as its vertices, using the method of Gandoin and Devillers [START_REF] Gandoin | Progressive lossless compression of arbitrary simplicial complexes[END_REF] (which we will note GD in the following), or any other method efficient at coding sparse facets. More precisely, non Delaunay facets constitute patches on the surface of the mesh. Before launching the convection process, the connectivity of these patches is transmitted to the GD coder. Then, the algorithm previously described is applied to the mesh minus the non Delaunay facets. Consequently, even if the initial mesh is a manifold, the convection process is going to perform on a mesh with boundaries. As shown in the previous section, our method can handle this case, but the presence of boundaries induces a significant increase in the number of driving codes: indeed, each facet of the mesh will be reached twice, first through a facet oriented outwards, then through the associated oriented facet lying on the internal side of the object surface. We propose several heuristics in order to limit this phenomenon. The intuitive idea is to block the convection surface temporarily, when it is about to cross a patch -a facet opening is delayed if the tetrahedron behind it intersects the mesh -, so as to favor the discovery of the initial mesh facets from outside (see Fig. 4). Thus, transmitting the total number of mesh facets to the decoder will allow to stop the convection process as soon as they are all discovered, which will drastically reduce the number of corrective codes. In the decoding stage, the vertex set is first obtained from the GD decoder, as well as the non Delaunay patches connectivity. Then the mesh without the patches is reconstructed by the algorithm of driven convection. At last, the patches connectivity is merged into the reconstructed leaky mesh. We thus see that our method improves the results of the method of Gandoin and Devillers only for meshes whose facets are mainly Delaunay. In the limit case where all the mesh facets would be non Delaunay, we would come across the GD coder compression rates. 2D Example: the original curve to be coded is in red thick line, including non Delaunay patches (parts in solid line). The Delaunay triangulation is in black thin line. The current evolving convection curve, in orange thick line, is temporarily blocked (parts in solid line) to avoid intersecting the patches. The remaining hidden Delaunay edges of the original curve will thus be discovered later, when the convection process will be relaunched to intersect the patches.

IV. CODING AND OPTIMIZATION

We saw in Sec. III that the codes resulting from the compression algorithm are a sequence of positive or null integers, representing the number of facets met between two special interventions of the algorithm, that is to say between two facets for which the algorithm does not follow the rules of the reconstruction by convection (ODG and RDG events). To minimize the output size, we have chosen to transmit these numbers to an arithmetic coder, which is able to code a sequence of symbols in a nearly optimal way, given a probability model. Thus, if p(s) denotes the probability of appearance of the symbol s, the arithmetic coder will encode s on log 2 (1/p(s)) + ε. In particular, this entropic coder is capable of coding a symbol on a fractional number of bits.

The main difficulty consists in defining a good probability model for the integers to be coded. The first solution consists in computing statistical data for each mesh and transmitting the probability table in the header of the compressed file. But ideally, to save the transmission of such a table, we would like to model the behavior of the sequence to be coded for a wide class of meshes, or alternatively, to design an adaptive model recomputing the probability of a symbol each time it occurs. Several kinds of model can be used, according to the size of the context from which the probability is estimated. For the order-0 model, each integer has an absolute probability for the whole coding sequence, independent from the context. For the order-1 model, the probability of an integer depends on the value of the previously transmitted integer, and so on. We have finally opted for an adaptive order-1 model specifically designed to take advantage of the particular structure of the integer sequence. For instance, this model handles long runs of null integer frequently occurring in the sequence.

As a matter of fact, these runs often correspond to large patches of facets that have to be forced (ODG events) because the Gabriel criterion is too restrictive compared to the local density of the mesh. Statistics illustrate that the convection process is rarely wrong when it decides to open a facet; on the contrary, at the end of the convection, a lot of facets have been retained but do not belong to the initial mesh. To encourage the convection algorithm to open more facets, we have relaxed the Gabriel criterion under some conditions. Intuitively, a facet will be opened when its size is "big" with regard to the vertex density in its neighborhood [START_REF] Chaine | A geometric convection approach of 3-d reconstruction[END_REF]. By setting this ratio to a near optimal value, the improvements can be drastic, particularly in the case of poorly sampled meshes where the number of driving codes can be lowered by about 50%.

V. EXPERIMENTAL RESULTS

The table I shows the results of the method applied to some usual meshes (the rates are in bits per vertex). The objects fandisk, blob, and horse are there essentially for comparison purposes, since they have been used for example by Touma and Gotsman [START_REF] Touma | Triangle mesh compression[END_REF]. The Stanford bunny is also a very classical mesh, widely used in 3D compression for about ten years. However, these models are not very representative of today meshes, whose number of vertices is much higher. The last meshes are more typical of what can be found nowadays. The hand (see Fig. 5) and max planck (see Fig. 5) can be found on http://shapes.aim-at-shape.net, while the triple hecate (see Fig. 5) comes from Le Louvre C2RMF lab. The first remark is that the rates obtained for the models fandisk, blob, horse, ford, UNC powerplant are not especially competitive with regard to the best current methods (for example, [START_REF] Kaelberer | Freelence -coding with free valences[END_REF], whose algorithm yields 0.74 bpv for the fandisk, and 0.96 bpv for the horse). The main reason is that the vertex set of these meshes are clearly not ε-sample and therefore, not favorable to the convection algorithm (but note that on these meshes, we gain on the geometry coding by using the GD coder, as shown in [START_REF] Gandoin | Progressive lossless compression of arbitrary simplicial complexes[END_REF]). On the contrary, the hand and max planck are correctly sampled and give a quite good idea of what the method can achieve when the point densities are reasonable. The triple hecate and ajax models are highly compliant meshes, not only because their facets are fully in Delaunay, but also because they were constructed from a set of points, using some reconstruction algorithm similar to the convection process. However, this kind of mesh is more and more widespread since a large class of objects are obtained from scanning and reconstruction.

Besides, we can notice that the rates associated to the coding of non Delaunay facets are quite bad facing their small number, and heavy penalize the global rates. Indeed, the GD coder is not optimal for sparse connectivity, and it should be possible to find a better way to code this small set of facets.

The last column of the table shows the computing user times in seconds for the connectivity compression / decompression of the meshes on a Pentium IV 3.0 Ghz 2 Go RAM computer. Globally, these times probably higher compared to classical methods that explicitly encode the whole connectivity, using some surface-based traversal of the mesh vertices. One can incriminate the precomputation and the 3D traversal of the Delaunay triangulation required by the convection process. This constraint particularly intends our method to applications where storage space or network bandwidth are more limited resources than processing power. However, a second version of the algorithm could be developed where Delaunay computation is not explicit any more. The current version also encounters timings limitations when the mesh is not entirely included in Delaunay. This is due to intersection determinations between the Delaunay triangulation and non-Delaunay mesh facets.

We can compare our algorithm to the only other compression method using reconstruction through the 3 meshes we have in common: the method [44] obtains 1.19 bpv for the horse, 2.63 bpv for the fandisk, and 1.18 bpv for the bunny, which is globally slightly higher than the rates of the table I. Regarding the methods [START_REF] Alliez | Valence-driven connectivity encoding for 3d meshes[END_REF], [START_REF] Lee | Angle-analyzer: A triangle-quad mesh codec[END_REF], [START_REF] Kaelberer | Freelence -coding with free valences[END_REF], derived from the Touma and Gotsman's coding principle [START_REF] Touma | Triangle mesh compression[END_REF], they obtain rates around 1.5 bpv for usual meshes, and can achieve very low rates for highly regular meshes where vertex degrees are almost constant. We don't have any result of these algorithms for meshes fully included in Delaunay, but there is no particular reason why their rates would be better in such cases.

Another limitation of the algorithm is related to the memory footprint. Indeed, in its current implementation (using the CGAL library [START_REF]CGAL, Computational Geometry Algorithms Library[END_REF]), the method needs to store the entire Delaunay tetrahedralization enriched with additional infor-mation. The memory cost of this structure is 30 bytes per vertex (geometry: 12, OFF file production: 8, Delaunay tetrahedralization: 4, vertex density information: 4 + 2 booleans) and 35 bytes per tetrahedron (Delaunay tetrahedralization: 32, surface and compression information: 3), given that for meshes meeting good sampling conditions (ie. meshes whose local density of vertices is proportional to the distance to the skeleton), the number of tetrahedra is nearly proportional to the number of vertices [START_REF] Attali | A linear bound on the complexity of the delaunay triangulation of points on polyhedral surfaces[END_REF]. Practically, this limits our method to meshes containing about 10 millions of triangles. Nevertheless, out-of-core or even streaming adaptations are conceivable since it has been shown that the convection algorithm could be applied to a data stream organized in successive layers [START_REF] Allègre | A streaming algorithm for surface reconstruction[END_REF]. In the same way, the GD method used in this article to compress the non Delaunay facets is limited for now to meshes under about 1 million of vertices, but an out-of-core adaptation is currently studied. Therefore we cannot give the compression ratio of the non Delaunay submesh for the UNC powerplant.

Tab. I contains numerical information about 4 models generated by CAD softwares: fandisk, horse, ford and UNC powerplant. As said above, our method is clearly not appropriate for this kind of model. Indeed, CAD meshes are often characterized by large triangles whose size is absolutely not related to the distance to the skeleton (see Fig. 6 (a) and (b)). Moreover, many of these triangles do not belong to the 3D Delaunay triangulation, even if, in numerous models, a single flip into cocircular quadruplets or a slight perturbation over vertex coordinates would drastically reduce the ratio of non Delaunay facets. This situation particularly occurs in large planar regions containing a lot of coplanar quadruplets, as can be seen on Fig. 3. For this kind of model, some other lossless compression methods should give better results [START_REF] Touma | Triangle mesh compression[END_REF], [START_REF] Alliez | Valence-driven connectivity encoding for 3d meshes[END_REF], [START_REF] Gandoin | Progressive lossless compression of arbitrary simplicial complexes[END_REF], although none of them has been specially designed for this class of meshes.

VI. CONCLUSION AND FUTURE WORK

We have presented a new method of lossless single-rate connectivity compression based on a semiautomatic reconstruction process able to deduce most of the mesh connectivity from its sole vertex set, and occasionally guided through compact codes that alter its default behavior when necessary. This method is originally suitable for Delaunay embedded meshes. We have also described a generalization removing this constraint inherent to the convection algorithm, using a separated coding of non Delaunay patches, as well as heuristics minimizing the number of driving codes during the convection process. So the final algorithm is able to compress any kind of 3D mesh, including non manifold ones, without any constraint on the topological genus or the number of connected components. After a probabilistic modelling and an entropic coding of the output, the numerical results show a substantial improvement above the current state of the art, with an average rate of 1 bit per vertex, reaching below 0.1 bpv for well sampled meshes. In addition, the algorithm can be used in parallel with currently most performing geometric compression methods, which results in very competitive overall rates.

The main limitations of the method might be its computing times, relatively high compared to some of the state-of-theart algorithms, and its memory footprint, which exclude for now the compression of gigantic meshes on standard 32bit personal computers. As a result, the optimization of the compression, and above all, of the decompression algorithm remains a primary perspective for this work.

The compression rates could probably be improved through more accurate probability models for the entropic coder, and even more, through a better coding of the non Delaunay facets. Similarly, it could be possible to keep improving the behavior of the convection algorithm, by opening the facets more accurately, according to some smarter criterion than the local vertex distribution. However, we are currently working on the generalization of this work to multiresolution, which is surely the most important perspective of this paper. This will be made possible by progressive insertion of vertices in the convection surface [START_REF]Convection-driven dynamic surface reconstruction[END_REF], under the constraints imposed by a kd-tree type progressive geometric coder. About the GD coder, a last significant perspective consists in integrating it to the convection process, in order to improve the geometric prediction by using connectivity information.

Finally, we would like to add that the impressive results obtained with the most favorable models illustrate the relevance of the research fields focused on Delaunay meshes, in particular the methods that aim at producing such models from point clouds or from non Delaunay meshes [START_REF] Dyer | Delaunay mesh construction[END_REF], [START_REF]Voronoi-delaunay duality and delaunay meshes[END_REF]. The tenth visited facet has been opened (t=10) f) Production of a RDG event at t=11, against the convection rules g) RDG event at t=12 h) Two kinds of facets in S at stabilization of the convection process : red facets for which RDG events have occurred, and blue facets that have been retained (whereas some of them are not present in M) i) Each retained facet (in blue) is considered in turn. An ODG event is produced for the 27th facet of that kind at time t=249 (previously examined facets are green colored) j) The convection process is locally relaunched at the level of the opened facet k) The local convection process is stabilized l) ODG events combined with local convection processes are pursued until the initial mesh is reached. t Oi and t Ri denote time steps when further ODG and RDG events occur.

Fig. 1 .

 1 Fig.1. Geometric convection on a 2D point set : (a) the evolving curve C is initialized to the convex hull, (b) C locally evolves at the level of an edge if the half-circle associated to this edge is not empty, (c) result of the initial convection process, (d) the convection process is locally enhanced to hollow a pocket out.

  parts. It adds to the steps 1 to 4 described in the previous section: 5 Processing of thin parts Function Convection 2D(C : Curve): while C = / 0 do e ← pop first oriented edge in C if Gabriel half-circle of e is empty then push e at the end of C temp else if e ∈ M then {RDG event} output time time ← 0 push e at the end of C f inal else if e such that e asso ∈ C (resp. C temp ) then remove e asso from C (resp. C temp ) else push {e 1 , e 2 } at the end of C end if time ← time + 1 end if end if end while Main 2D function: C ← boundaries of S border C f inal ← / 0;C temp ← / 0;time ← 0 Convection 2D(C) while C temp = / 0 do e ← pop first oriented edge in C temp if e such that e asso ∈ C temp then remove e asso from C temp else if e ∈ M then push e at the end of C f inal time ← time + 1 else {ODG event} output time time ← 0 C ← {e 1 , e 2 } Convection 2D(C) end if end if end while

Fig. 3 .

 3 Fig. 3. Fandisk: complete (12946 facets), then showing the non Delaunay facets only (1104 facets representing 8.5% of the set)

Fig. 4 .

 4 Fig. 4.2D Example: the original curve to be coded is in red thick line, including non Delaunay patches (parts in solid line). The Delaunay triangulation is in black thin line. The current evolving convection curve, in orange thick line, is temporarily blocked (parts in solid line) to avoid intersecting the patches. The remaining hidden Delaunay edges of the original curve will thus be discovered later, when the convection process will be relaunched to intersect the patches.

Fig. 5 .Fig. 6 .

 56 Fig. 5. (a) triple hecate (detail): 75729 vertices and 151462 triangles coded with 0.04 bits per vertex, (b) max planck: 199169 vertices and 398043 triangles, 0.90 bits per vertex, (c) ajax: 273383 vertices and 547117 triangles, 0.14 bits per vertex, (d) hand: 327290 vertices and 654596 triangles, 0.19 bits per vertex. These models resulting from scans are usually characterized by a small number of non Delaunay triangles. The vertex density locally reflects the distance to the skeleton and these meshes are probably produced by Delaunay based reconstruction algorithms.

Fig. 2 .

 2 Fig. 2. a) Mesh M to be coded b) Delaunay triangulation of M vertices and initialization of S c) The first visited facet has been opened (t=1) d) The second facet has been retained (t=2) e)The tenth visited facet has been opened (t=10) f) Production of a RDG event at t=11, against the convection rules g) RDG event at t=12 h) Two kinds of facets in S at stabilization of the convection process : red facets for which RDG events have occurred, and blue facets that have been retained (whereas some of them are not present in M) i) Each retained facet (in blue) is considered in turn. An ODG event is produced for the 27th facet of that kind at time t=249 (previously examined facets are green colored) j) The convection process is locally relaunched at the level of the opened facet k) The local convection process is stabilized l) ODG events combined with local convection processes are pursued until the initial mesh is reached. t Oi and t Ri denote time steps when further ODG and RDG events occur.

ACKNOWLEDGMENT

This research takes place into the ACI projects Eros3D and Triangles, supported by the French Centre National de la Recherche Scientifique (CNRS). Some of the 3D models appearing in this paper are provided courtesy of AIM@Shape (IMATI and INRIA). The triple hecate model is provided courtesy of Christian Lahanier from C2RMF (Musée du Louvre, Département des Antiquités Etrusques et Romaines, marbre, MA 2594, C2RMF: FZ31452). The ajax model is provided courtesy of Jotero GbR. The algorithms have been implemented thanks to the CGAL (Computational Geometry Algorithms Library) library [55]. Finally, we would like to thank the anonymous reviewers for their constructive appreciations and helpful suggestions.

Her research interests include 3D digital image processing, geometric modeling and more precisely multiresolution analysis, remeshing and progressive compression of meshes.


Raphaëlle Chaine

Pierre-Marie Gandoin

Céline Roudet

Mesh Connectivity Compression Using Convection Reconstruction

Keywords: CR Categories: I.3.5 [Computing Methodologies]: Computer Graphics-Computational Geometry and Object Modeling Mesh, Compression, Reconstruction, Lossless, Connectivity

During a highly productive period running from 1995 to about 2002, the research in lossless compression of 3D meshes mainly consisted in a hard battle for the best bitrates. But for a few years, compression rates seem stabilized around 1.5 bit per vertex for the connectivity coding of usual meshes, and more and more work is dedicated to remeshing, lossy compression, or gigantic mesh compression, where memory and CPU optimizations are the new priority. However, the size of 3D models keeps growing, and many application fields keep requiring lossless compression. In this paper, we present a new contribution for single-rate lossless connectivity compression, which first brings improvement over current state of the art bitrates, and secondly, does not constraint the coding of the vertex positions, offering therefore a good complementarity with the best performing geometric compression methods. The initial observation having motivated this work is that very often, most of the connectivity part of a mesh can be automatically deduced from its geometric part using reconstruction algorithms. This has already been used within the limited framework of projectable objects (essentially terrain models and GIS), but finds here its first generalization to arbitrary triangular meshes, without any limitation regarding the topological genus, the number of connected components, the manifoldness or the regularity. This can be obtained by constraining and guiding a Delaunay-based reconstruction algorithm so that it outputs the initial mesh to be coded. The resulting rates seem extremely competitive when the meshes are fully included in Delaunay, and are still good compared to the state of the art in the general case.

Introduction

For several years, meshes have played a leading role in computer graphics, and their ability to model the world throws them in the heart of advanced applications in all the fields of science, arts or leisure. If some of these applications can tolerate a limited loss of information (provided that this loss is well controlled and does not damage a certain visual realism), the others, for practical or even legal reasons, impose to work continuously with exact copies of original objects. In this case, the only way of optimizing the storage and the transmission of 3D information is to have recourse to lossless compression methods.

A mesh is defined by a set of points (we speak of the geometry of the mesh), and by a combinatorial structure describing the relations between these points, using geometric objects of higher dimensions : edges, facets, polyhedra (we speak of the connectivity or the topology of the mesh). To this fundamental information are sometimes added attributes allowing to improve the rendering : normals, colors or textures. If we put aside these attributes (they relate only to a subset of the meshes met in practice), all the difficulty for compressing 3D objects is to process with an equal efficiency the geometry and the connectivity of a wide class of meshes. However, most of the methods proposed so far stress on one of these two aspects (usually the connectivity), generally to the detriment (or at least, not to the advantage) of the other one, which is constrained by a description order rarely optimal in terms of compression. In this article, we propose a new single-rate connectivity coder which is not only general and efficient, but also does not impose any constraint on the coding of the geometry. In particular, it is totally compatible with the position coders that currently propose the best compression rates.

We took it as given that very often, the main part of a mesh connectivity can be deduced from its vertex set using reconstruction methods. This remark has already been made in the past, but the problem was to find an effective way of describing the difference between the initial mesh and its reconstructed version. Indeed, within the framework of lossless compression, it is indispensable to be able to correct these errors in order to obtain a decoded mesh perfectly identical to the original mesh. But rather than describe the difference to the initial object at the end of the reconstruction phase, we suggest adapting an existing algorithm so that it can accept occasional codes modifying its default behavior at the moments when it would commit an "error" of reconstruction with regard to the initial mesh.

Having placed our work in the historical context of 3D compression and 3D reconstruction (Section 2), we will expose the general principle of the method (Section 3), first within a restricted framework, then generalized to arbitrary triangular meshes (regarding the genus, the number of connected components, the regularity and the manifoldness). Then we will detail the coding techniques and optimization steps leading to better compression rates (Section 4), before presenting some comparative results and comments on the method performances (Section 5).

Context and Previous Works 2.1 Mesh Compression

As mentioned above, a mesh is composed of both a geometric part (the vertex positions), and a topological part (the vertex connectivity). Now, by looking at the whole scientific production in mesh compression since 1995 until now, we notice clearly that the connectivity coding has motivated most of the proposed methods. The usual scheme consists in describing the combinatorial structure by enumerating its vertices in a precise order, designed to minimize the size of the code : each vertex is coupled with a variable size symbol defining the way it is connected to the rest of the mesh. Consequently, the geometric coder has to work with this predefined order of the vertices, but it can exploit the connectivity to predict their location. The position of the currently transmitted vertex is estimated from its neighbors, and the prediction error is the sole information to be coded. But the order imposed by the connectivity coding is not necessarily favorable to this prediction, as shown by the results obtained on usual meshes by classical algorithms : the best of them reduce the connectivity information to less than 1 or 2 bits per vertex, while for the geometric part, the rates rarely go down under 90% of the initial size (except for very low quantizations). Among the works that follow this principle, we focus here in single-rate methods, which code and decode the mesh in one pass and do not allow progressive visualization [START_REF] Deering | Geometry compression[END_REF][START_REF] Evans | Optimizing triangle strips for fast rendering[END_REF][START_REF] Taubin | Geometric compression through topological surgery[END_REF][START_REF] Gumhold | Real time compression of triangle mesh connectivity[END_REF][START_REF] Touma | Triangle mesh compression[END_REF][START_REF] Li | A dual graph approach to 3d triangular mesh compression[END_REF]Bajaj et al. 1999a;Bajaj et al. 1999b;[START_REF] Gumhold | Tetrahedral mesh compression with the cut-border machine[END_REF][START_REF] Rossignac | Edgebreaker : Connectivity compression for triangle meshes[END_REF][START_REF] Rossignac | Wrap&zip : Linear decoding of planar triangle graphs[END_REF][START_REF] King | Guaranteed 3.67v bit encoding of planar triangle graphs[END_REF][START_REF] Isenburg | Mesh collapse compression[END_REF][START_REF] Isenburg | Triangle fixer : Edge-based connectivity encoding[END_REF][START_REF] Alliez | Valence-driven connectivity encoding for 3d meshes[END_REF][START_REF] Lee | Angle-analyzer: A triangle-quad mesh codec[END_REF][START_REF] Coors | Delphi : Geometry-based connectivity prediction in triangle mesh compression[END_REF][START_REF] Kaelberer | Freelence -coding with free valences[END_REF][START_REF] Jong | An efficient connectivity compression for triangular meshes[END_REF]]. To understand how these methods compare, the reader can also refer to the following surveys [START_REF] Alliez | Recent Advances in Compression of 3D Meshes[END_REF][START_REF] Gotsman | Simplification and Compression of 3D Meshes[END_REF]Peng et al. 2005]. It is worth to mention here that the relative stability in compression rates observed these days can be explained by the new interest of the community for gigantic meshes : in this framework, the challenge is to improve the efficiency of the compression in terms of CPU and memory requirements rather than in terms of bitrates [START_REF] Isenburg | Out-of-core compression for gigantic polygon meshes[END_REF]Isenburg and Lindstrom 2005;Isenburg et al. 2005].

Prioritizing the Geometric Coding

After this first wave of works, in the knowledge that the geometry of a mesh weighs generally much more than its connectivity, the researchers began to propose methods giving the priority to geometric compression. Some of them deviate from the lossless framework by proposing algorithms that often impose a complete remeshing of the object before applying spectral decomposition tools like wavelets, subdivision schemes, or classic geometric methods of compression [START_REF] Gross | Efficient triangular surface approximations using wavelets and quadtree data structures[END_REF][START_REF] Certain | Interactive multiresolution surface viewing[END_REF][START_REF] Lounsbery | Multiresolution analysis for surfaces of arbitrary topological type[END_REF][START_REF] Staadt | Multiresolution compression and reconstruction[END_REF][START_REF] Guskov | Normal meshes[END_REF]Khodakovsky et al. 2000;[START_REF] Khodakovsky | Normal mesh compression[END_REF][START_REF] Karni | Spectral compression of mesh geometry[END_REF][START_REF] Szymczak | Piecewise regular meshes : Construction and compression[END_REF][START_REF] Attene | Swingwrapper : Retiling triangle meshes for better edgebreaker colmpression[END_REF]].

On the other hand, the works introduced by Gandoin and Devillers and improved by Peng and Kuo [Devillers and Gandoin 2000;[START_REF] Gandoin | Progressive lossless compression of arbitrary simplicial complexes[END_REF]Peng and Kuo 2005] describe a progressive and lossless compression method, centered on the geometry, which interests us particularly within the framework of this article. Indeed, this method was originally designed to code an unstructured point cloud, with the underlying idea that in many cases, the connectivity information could be deduced from the geometry thanks to reconstruction algorithms. So, the first version of this method [START_REF] Devillers | Geometric compression for interactive transmission[END_REF]] proposed a multiresolution compression algorithm for an unstructured point cloud, guaranteeing a theoretical minimal gain of n(log 2 n -2.4) (where n denotes the number of points), and very competitive practical performances, even compared to the best single-rate algorithms. The method was then extended to deal with the connectivity compression, while remaining centered on the geometry [START_REF] Gandoin | Progressive lossless compression of arbitrary simplicial complexes[END_REF]. Indeed, the kd-tree decomposition scheme involved in the heart of the geometric coder, is enriched with a connectivity coder that uses some of the classical mesh simplification operations introduced by Hoppe et al. [START_REF] Hoppe | Progressive meshes[END_REF]Popović and Hoppe 1997]). Eventually, the method has recently been resumed by Peng and Kuo [Peng and Kuo 2005] who improve its performances by imposing a priority on the cell subdivision order in the octree, and by proposing a more effective prediction model for the point distribution in the sub-cells generated by a subdivision.

Compression and Reconstruction

The idea to entrust a reconstruction algorithm with the task of computing the connectivity of a mesh from its vertices has already been used in the context of mesh compression. Within the framework of terrain models, [START_REF] Kim | An improved TIN compression using Delaunay triangulation[END_REF] suggest transmitting only a fraction of the edges composing the object, and using constrained Delaunay triangulation -in 2D, since the terrain models are projectable -to find the whole connectivity. Devillers and Gandoin [START_REF] Devillers | Geometric compression for interactive transmission[END_REF]] also mention the compression of GIS as an application of their geometric coder, and develop an edge coder well suited for this context, which results in compression rates as low as 0.2 bits per vertex for the complete connectivity. Besides, Devillers et al. show that the minimal set to be transmitted to guarantee the exact reconstruction of the initial model by constrained Delaunay triangulation is constituted by the edges that are non locally Delaunay [START_REF] Devillers | Minimal set of constraints for 2D constrained Delaunay reconstruction[END_REF]].

Unfortunately, the generalization from 2.5D to 3D meshes is not straightforward : since the mesh is not projectable any more, the use of the constrained Delaunay triangulation is impossible. Nevertheless, the idea to use a reconstruction method driven by a partial description of the connectivity remains extremely promising in terms of compression results. Provided that it could be possible to find a method both powerful and capable of taking advantage of partial connectivity data to guarantee an exact reconstruction whatever the initial model may be.

A first attempt to use a reconstruction algorithm to encode connectivity information has been proposed by [START_REF] Lewiner | Gencode : Geometry-driven compression in arbitrary dimension and co-dimension[END_REF]]. The geometry is coded independently, through a kdtree based algorithm derived from [START_REF] Gandoin | Progressive lossless compression of arbitrary simplicial complexes[END_REF] and [START_REF] Botsch | Delaunay triangulation based surface reconstruction : Ideas ans algorithms[END_REF]] and the connectivity is coded through an advancing front triangulation inspired of the ball-pivoting strategy [START_REF] Bernardini | The ball-pivoting algorithm for surface Figure 6: hand : 327290 vertices and 654596 facets coded with 0.19 bits per vertex reconstruction[END_REF]. This algorithm requires a code for each edge of an active border that is initialized to a triangle. If the geometry of the mesh meets good sampling conditions, the entropy of each code will be extremely low. In Section 5, we compare this method to ours regarding the compression rates.

Reconstruction by Convection

The problem of reconstructing a surface from a set of points has received considerable attention during the last decade [Mencl and Müller 1998]. Interesting and outstanding algorithms have been issued both in computer graphics and computational geometry, but we have decided to focus on the algorithms of the second category, since their combinatorial concerns are more suitable for lossless compression purposes. Most of computational geometry algorithms exploit the geometric properties of structures such as the Delaunay triangulation, the Voronoi diagram or the power diagram of the input point set, assuming auspicious properties on the way they were sampled on the surface (ε-sample [START_REF] Amenta | Surface reconstruction by voronoi filtering[END_REF]). A consistent set of facets can then be extracted from the geometric structure, sometimes using global heuristics or local analysis to solve ambiguities. The existing algorithms are numerous and an attempt to classify and distinguish them has recently been proposed in the state of the art by Cazals and [START_REF] Botsch | Delaunay triangulation based surface reconstruction : Ideas ans algorithms[END_REF]. Most of these algorithms produce triangular meshes, which makes them good candidates to use for compression purposes.

The convection algorithm we use in our method is based on a similar notion of flow as it was developped in the Wrap algorithm by Edelsbrunner [START_REF] Edelsbrunner | Surface reconstruction by wrapping finite point sets in space[END_REF]], and the flow complex algorithm by [START_REF] Giesen | Surface reconstruction based on a dynamical system[END_REF]. Indeed, this reconstruction algorithm has been inspired from a convection process described by Zhao et al. [H.K.Zhao et al. 2001]. They use it to ini-tialize their surface before running an energy minimization process in the level set framework. Given an evolving surface S enclosing an input point set P, the convection process makes each point of S move inwards, along the direction of its normal, towards its closest point in P. However, the numerical scheme they propose can be translated in Delaunay, to make it depend on the geometry of the input data set only, and not on the precision of some grid around the surface. A demonstration of this result is presented by Chaine [START_REF] Chaine | A geometric convection approach of 3-d reconstruction[END_REF]] together with a subsequent convection algorithm. A Delaunay triangulation of P is a partition of space into tetrahedra so that the ball circumscribed to each tetrahedron does not contain any point of P. The convection process is run directly in the 3D Delaunay triangulation of P, with an evolving surface S composed of oriented Delaunay facets. S is initialized to the convex hull of P. An oriented facet of S that does not meet the oriented Gabriel property -i.e. its inwards diametral half-sphere is not empty -is attracted towards the 3 inner facets in the incident Delaunay inner tetrahedra (see Fig. 1, for an illustration in 2D where the evolving surface is replaced by an evolving curve, and the Delaunay tetrahedra are replaced by Delaunay triangles). During the convection process, thin parts can appear (see Fig. 1, c andd), on which a 2D surface based version of the convection is run. A deeper explanation of this algorithm will be presented in Section 3 while revisiting it for compression purposes. An interesting property of the convection algorithm is that it is driven locally, in the Delaunay triangulation of the points, without involving a global heuristic. The topology of the evolving surface may change during the convection process, so that it can handle surfaces with boundaries and surfaces of high genus. A drawback of the convection process is that it can locally be stuck in presence of pockets [START_REF] Edelsbrunner | On the definition and the construction of pockets in macromolecules[END_REF]] hiding facets, but a simple and local point density analysis permits to hollow them out [START_REF] Chaine | A geometric convection approach of 3-d reconstruction[END_REF]].

3 Principle of the Compression Algorithm

Compliant Meshes

The benefit of using a 3D reconstruction method for compression purposes is double : first, this allows to obtain very low costs for the coding of the connectivity -ideally, a null cost if the reconstruction algorithm is able to find the exact structure of the original mesh by itself -, and secondly, unlike the previous methods of topologic compression, no constraint is imposed on the order of the vertices to the geometric coder, which constitutes an important efficiency token.

The main difficulty consists in being able to help the reconstruction algorithm at a reasonable cost : indeed, it is highly improbable to design an algorithm capable of finding the complete connectivity of a mesh from its vertex set. It is thus necessary to be able to alter the course of the reconstruction process, by occasionally changing the default behavior of the algorithm to drive it in a sure way to a result known in advance : the structure of the initial mesh.

Among the plethora of available methods, the reconstruction by convection is distinguishable from others by two important assets : its qualities in terms of reconstruction -practical accuracy and faithfulness to the original model, handling of complex topologies, computation times -, and above all, its ability to be effectively driven by means of simple instructions. The first asset guarantees that the algorithm will not need to be guided too often (small number of codes), the second guarantees that this can be done at lower cost (compactness of the codes).

In return, as many algorithms in computational geometry, the convection algorithm is based on a Delaunay triangulation, and it may be difficult to force it out of this structure. This imposes a condition over the initial mesh : all its facets have to belong to the 3D Delaunay triangulation of its vertex set. It is quite a strong property that is not verified by all the 3D objects met in practice. We will see in second stage (Section 3.3) how to break it.

Intuitively, the reconstruction by convection consists in embedding the vertex set in a block of marble that will be sculpted gradually, facet after facet, tetrahedron after tetrahedron, until it takes on the exact shape of the initial object. The algorithm begins by preparing the sculpting material : an enclosing block which is nothing else than the convex hull of the point cloud, as well as the network of galleries through which it is going to dig until the initial shape is reached. This network is composed of the tetrahedra of the 3D Delaunay triangulation, and every stage towards the object shape consists in examining a new facet of the current surface and deciding if it is necessary or not to open it and excavate the inside of its associated tetrahedron. When a facet is opened, it is removed from the current surface of the 3D object under construction, and replaced by the three other facets of the excavated tetrahedron.

As mentioned above, the criterion that decides on this opening is purely local : it consists in observing whether the Gabriel halfsphere associated to the current oriented facet contains or not the fourth vertex of the tetrahedron. If it is the case, the oriented facet is opened and replaced in the current surface by the 3 other facets of the associated tetrahedron. (If this one is already excavated, the surface locally vanishes through the current facet.) Otherwise, it is maintained on the surface.

Note that if all the facets of the initial object are in its 3D Delaunay triangulation, they are reachable by this sculpture process from the convex hull. The problem is to make sure that the algorithm will not dig a facet belonging to the initial mesh, or that, conversely, it will not be retained before having reached such a facet. Hence the need for additional codes allowing to modify the behavior of the convection algorithm, and to drive it towards the object to be coded. Even if the convection algorithm was designed to compute with a good accuracy the structure of a mesh sufficiently dense, it will most likely need occasional assistance to guarantee the perfect reconstruction of any mesh.

To present our method in a progressive way, we focus in this section on a mesh M verifying the following two assumptions : all its facets are in the 3D Delaunay triangulation of its vertex set, and it is manifold, that is to say without borders nor thin parts. (This is what we call a "compliant" mesh.)

Under these assumptions, here is the general principle of our compression algorithm :

1 4 Launch the convection process on S : every oriented facet f in S is examined in turn, and depending on whether its Gabriel half-sphere is empty or not, f is, by default, maintained on S or replaced by its 3 neighbors in D. To modify this default behavior of the convection reconstruction, it is necessary to locate the oriented facets of S for which the algorithm has to act differently. It is thus indispensable to define a completely deterministic traversal of the facets in S, so that the n th oriented facet met during the compression would also be the n th oriented facet met during the decompression. More generally, it is necessary to ensure the synchronization of the algorithms of compression and decompression so that the n th action of the coder matches the n th action of the decoder. Thanks to these reference marks, the behavior of the convection process can be safely altered in the following two circumstances : a) when the convection asks for the opening of a facet f that belongs to M, the coder forbids this opening, and codes the index of f (more exactly, the moment when f is met in the algorithm) to warn the decoder that at this precise moment of the reconstruction, it has to break the rules of the convection algorithm. We will call this a RDG event (Retain Despite the Geometry), b) at the end of this first step, it is possible that some oriented facets of S -those whose Gabriel half-spheres are empty and thus the convection did not decide to dig -, do not belong to M. Therefore, it is necessary to specify to the decompression algorithm that these oriented facets must be forced, against the convection rules : for each remaining oriented facet of S not belonging to M, the coder transmits its index (i.e. the moment when it has been met) and relaunch the convection process by forcing its opening. We will call this a ODG event (Open Despite the Geometry). Note that by relaunching the convection process locally, some facets that were due to be forced can disappear by autointersection of S.

A detailed description of step 4 can be given through a recursive function Convection applied to the current surface S. For each oriented facet f , let f asso denote the oriented facet associated to f , that is to say the oriented facet constructed on the same vertices as f , but with the opposite orientation. When f and f asso are both in the surface S, that means they belong to a thin part of S. Besides, let f 1 , f 2 and f 3 denote the 3 neighbors of f in the 3D Delaunay triangulation D, i.e. the 3 other facets of the tetrahedron that is removed when f is opened. Finally, we would like to draw the reader's attention to the that the reference marks transmitted to the decoder are not exactly absolute moments of events in the compression process, but rather intervals between two such moments (which explains the presence of the instructions "time ← 0" in the detailed algorithms). This well-known technique of differential coding allows to reduce the size of the transmitted codes.

if f ∈ M then push f at the end of S f inal time ← time + 1 else {ODG event} output time time ← 0 S ← { f 1 , f 2 , f 3 } Convection(S) end if end if end while
At the end of the compression algorithm, the convection has been driven towards the initial mesh M, and the correcting data have been stored for the decompression algorithm. However, a last stage remains that consists in cleaning thin parts possibly generated by the convection. Indeed, since we first assumed that the initial mesh was manifold, it suffices to delete all these thin parts, that is to say each facet of S whose associated facet is also on S. In the algorithm described above, the thin parts exactly match the set S border .

Non Manifold Meshes

In this section, we are going to adapt the previous algorithm to non manifold, thin parts meshes. It suffices to modify the final stage : it is no longer possible to delete the thin parts created by the algorithm, because facets belonging to the initial mesh could be lost. This stage is thus replaced by a new convection process, but this time in its 2D version, and on the thin parts only. In this framework, the convection updates a curve C constituted by the edges composing the boundaries of the thin parts. The oriented edges of C are examined in turn : an oriented edge whose Gabriel half-circle is empty will be kept on C, whereas an oriented edge in the opposite case will be removed and replaced in C by the two other oriented edges of its incident triangle (e 1 and e 2 in the algorithm detailed below).

The general principle remains the same as in the 3D version of the algorithm, and each edge that is opened against the convection rules (ODG event) launches a new 2D convection process. Note that there is no set C border similar to the previous S border . Here is a detailed version of the portion of the compression algorithm dedicated to the processing of the thin parts. It adds to the steps 1 to 4 described in the previous section :

Non Delaunay Meshes

As previously described, the method can only be applied to meshes whose facets all belong to the 3D Delaunay triangulation of their vertex set. Indeed, we saw that this structure constituted the support of the convection algorithm, and that it was thus impossible for the current surface to reach a non Delaunay facet. Nevertheless, most of the meshes met in practice contain a fraction of non Delaunay facets (see the unfavorable case of Fig. 2). So, to make the method widely usable, it is necessary to manage the coding of such facets. A simple and efficient way to do this is to code explicitely all the non Delaunay facets of the initial mesh in the same time as its vertices, using the method of Gandoin and Devillers [START_REF] Gandoin | Progressive lossless compression of arbitrary simplicial complexes[END_REF]], which we will note GD in the following. More precisely, non Delaunay facets constitute patches on the surface of the mesh. Before launching the convection process, the connectivity of these patches is transmitted to the GD coder. Then, the algorithm previously described is applied to the mesh minus the non Delaunay facets. Consequently, even if the initial mesh is manifold, the convection process is going to perform on a mesh with boundaries. As shown in the previous section, it is no theoretical problem, but risks though to result in a significant increase of the number of driving codes. Indeed, each facet of the mesh will be reached twice, first through a facet oriented outwards, then through the associated oriented facet lying on the internal side of the object surface. We propose several heuristics in order to limit this phenomenon. The intuitive idea is to block temporarily the convection surface when it is about to cross a patch -a facet opening is delayed if the tetrahedron behind it intersects the mesh -, so as to favor the discovery of the initial mesh facets from outside (see Fig. 3). Thus, transmitting the total number of mesh facets to the decoder will allow to stop the convection process as soon as they are all discovered, which will drastically reduce the number of corrective codes. In the decoding stage, the vertex set is first obtained from the GD decoder, as well as the patches connectivity. Then the mesh without the patches is reconstructed by the algorithm of driven convection. At last, the patches connectivity is merged into the reconstructed leaky mesh. We thus see that our method improves the results of the method of Gandoin and Devillers only for meshes whose facets are mainly Delaunay. In the limit case where all the mesh facets would be non Delaunay, we would come across the GD coder compression rates.

Figure 3: 2D Example : the original curve to be coded is in red thick line, including non Delaunay patches (parts in solid line). The Delaunay triangulation is in black thin line. The current evolving convection curve, in orange thick line, is temporarily blocked (parts in solid line) to avoid intersecting the patches. The hidden Delaunay edges of the original curve will thus be discovered later, when the convection process will be relaunched to intersect the patches.

Coding and Optimization

We saw in section 3 that the codes resulting from the compression algorithm are a sequence of positive or null integers, representing the number of facets met between two special interventions of the algorithm, that is to say between two facets for which the algorithm does not follow the rules of the reconstruction by convection (ODG and RDG events). To minimize the output size, we have chosen to transmit these numbers to an arithmetic coder, which is able to code a sequence of symbols in a nearly optimal way, given a probability model. Thus, if p(s) denotes the probability of appearance of the symbol s, the arithmetic coder will encode s on log 2 (1/p(s)) + ε. In particular, this entropic coder is capable of coding a symbol on a fractional number of bits.

The main difficulty consists in defining a good probability model for the integers to be coded. The first solution consists in computing statistical data for each mesh and transmitting the probability table in the header of the compressed file. But ideally, to save the transmission of such a table, we would like to model for a wide class of meshes the behavior of the sequence to be coded, or alternatively, to design an adaptive model recomputing the probability of a symbol each time it occurs. Several kinds of model can be used, according to the size of the context from which the probability is estimated. For the order-0 model, each integer has an absolute probability for the whole coding sequence, independent from the context. For the order-1 model, the probability of an integer depends on the value of the previously transmitted integer, and so on. We have finally opted for an adaptive order-1 model specifically designed to take advantage of the particular structure of the integer sequence. For instance, this model handles the long runs of null integer frequently occuring in the sequence.

As a matter of fact, these runs often correspond to large patches of facets that have to be forced (ODG events) because the Gabriel criterion is too restrictive compared to the local density of the mesh. Statistics show that the convection process is rarely wrong when it decides to open a facet; on the contrary, at the end of the convection, a lot of facets have been retained but do not belong to the initial mesh. To encourage the convection algorithm to open more facets, we have relaxed the Gabriel criterion under some conditions. Intuitively, a facet will be opened when its size is "big" with regard to the vertex density in its neighborhood [START_REF] Chaine | A geometric convection approach of 3-d reconstruction[END_REF]]. By setting this ratio to a near optimal value, the improvements can be drastic, particularly in the case of poorly sampled meshes where the number of driving codes can be lowered by about 50%.

Experimental Results

The table 1 shows the results of the method applied to some usual meshes (the rates are in bits per vertex). The objects fandisk, blob, and horse are there essentially for comparison purposes, since they have been used for example by Touma and Gotsman [START_REF] Touma | Triangle mesh compression[END_REF]]. The Stanford bunny is also a very classical mesh, widely used in 3D compression for about ten years. However, these models are not very representative of today meshes, whose number of vertices is much higher. The last three meshes are more typical of what can be found nowadays. The hand (see Fig. 6) and max planck (see Fig. 5) can be found on http://shapes.aimat-shape.net, while the triple hecate (see Fig. 4 The first remark is that the rates obtained for the first three models are not especially competitive with regard to the best current methods (for example, [START_REF] Kaelberer | Freelence -coding with free valences[END_REF], whose algorithm yields 0.74 bpv for the fandisk, and 0.96 bpv for the horse). The main reason is that the vertex set of these meshes are clearly not ε-sample and therefore, not favorable to the convection algorithm (but note that on these meshes, we gain on the geometry coding by using the GD coder, as shown in [START_REF] Gandoin | Progressive lossless compression of arbitrary simplicial complexes[END_REF]). On the contrary, the hand and max planck are correctly sampled and give a quite good idea of what the method can achieve when the point densities are reasonable. The triple hecate and ajax models are highly compliant meshes, not only because their facets are fully in Delaunay, but also because they were constructed from a set of points, using some reconstruction algorithm similar to the convection process. However, this kind of mesh is more and more widespread since a large class of objects are obtained from scanning and reconstruction.

Besides, we can notice that the rates associated to the coding of non Delaunay facets are quite bad facing their small number, and heavy penalize the global rates. Indeed, the GD coder is not optimal for sparse connectivity, and it should be possible to find a better way to code this small set of facets.

The last column of the table shows the computing user times in seconds for the connectivity compression / decompression of the meshes on a Pentium IV 3.0 Ghz 2 Go RAM computer. Globally, these times are rather high compared to classical methods that explicitly encode the whole connectivity, using some traversal through the mesh vertices. One can incriminate the precomputation and the traversal of the Delaunay tetrahedrization required by the convection process. This constraint particularly intends our method to applications where storage space or network bandwidth are more limited resources than processing power. However, a second version of the algorithm could be developped where Delaunay computation is not explicit any more. The current version also encounters timings limitations when the mesh is not entirely included in Delaunay. This is due to intersection determinations between the Delaunay tetrahedrization and non-Delaunay mesh facets.

We can compare our algorithm to the only other compression method using reconstruction through the 3 meshes we have in common : the method [START_REF] Lewiner | Gencode : Geometry-driven compression in arbitrary dimension and co-dimension[END_REF]] obtains 1.19 bpv for the horse, 2.63 bpv for the fandisk, and 1.18 bpv for the bunny, which is globally slightly higher than the rates of the table 1. Regarding the methods [START_REF] Alliez | Valence-driven connectivity encoding for 3d meshes[END_REF][START_REF] Lee | Angle-analyzer: A triangle-quad mesh codec[END_REF][START_REF] Kaelberer | Freelence -coding with free valences[END_REF], derived from the Touma and Gotsman's coding principle [START_REF] Touma | Triangle mesh compression[END_REF]], they obtain rates around 1.5 bpv for usual meshes, and can achieve very low rates for highly regular meshes where vertex degrees are almost constant. We don't have any result of these algorithms for meshes fully included in Delaunay, but there is no particular reason why their rates would be better in such cases.

Another limitation of the algorithm concerns the memory footprint. This footprint is that of a Delaunay triangulation enriched with mesh information. The compression algorithm is implemented in CGAL [CGAL ] and the Delaunay tetrahedrization size is proportional to the number of Delaunay cells and the number of Delaunay vertices. Note that the Delaunay tetrahedrization of a surface based point set meeting good sampling conditions is nearly linear in the number of points.

Conclusion and Future Work

We have presented a new method of lossless single-rate connectivity compression based on a semiautomatic reconstruction process able to deduce most of the mesh connectivity from its sole vertex set, and occasionally guided through compact codes that alter its default behavior when necessary. This method is originally suitable for Delaunay embedded meshes. We have also described a generalization removing this constraint inherent to the convection algorithm, using a separated coding of non Delaunay patches, as well as heuristics minimizing the number of driving codes during the convection process. So the final algorithm is able to compress any kind of 3D mesh, including non manifold ones, without any constraint on the topological genus or the number of connected components. After a probabilistic modelization and an entropic coding of the output, the numerical results show a substancial improvement above the current state of the art, with an average rate of 1 bit per vertex, reaching below 0.1 bpv for well sampled meshes. In addition, the algorithm can be used in parallel with currently most performing geometric compression methods, which results in very competitive overall rates. The main limitations of the method are its computing times, relatively high compared to some of the stateof-the-art algorithms, and its memory footprint, which exclude for now the compression of gigantic meshes on standard 32-bit machines. As a result, the optimization of the compression, and above all, of the decompression algorithm remains a primary perspective for this work.

The compression rates could probably be improved through more accurate probability models for the entropic coder, and even more, through a better coding of the non Delaunay facets. Similarily, it could be possible to keep improving the behavior of the convection algorithm, by opening the facets more accurately, according to some smarter criterion than the local vertex distribution. However, we are currently working on the generalization of this work to multiresolution, which is surely the most important perspective of this paper. This will be made possible by progressive insertion of vertices in the convection surface [Allègre et al. 2005], under the constraints imposed by a kd-tree type progressive geometric coder. About the GD coder, a last significant perspective consists in integrating it to the convection process, in order to improve the geometric prediction by using connectivity information.

Acknowledgement

This research takes place into the ACI projects Art3D and Eros3D, supported by the French Centre National de la Recherche Scientifique (CNRS). Some of the 3D models appearing in this paper are provided courtesy of AIM@Shape (IMATI and INRIA). The triple hecate model is provided courtesy of Christian Lahanier from C2RMF (Musée du Louvre, département des Antiquités Etrusques et Romaines, marbre, MA 2594, C2RMF : FZ31452).

Figure 1 :

 1 Figure1: Geometric convection on a 2D point set : (a) the evolving curve C is initialized to the convex hull, (b) C locally evolves at the level of an edge iff the half-circle associated to this edge is not empty, (c) result of the initial convection process, (d) the convection process is locally enhanced to hollow a pocket out.

  Build the 3D Delaunay triangulation D of the point set P, 2 Mark the facets of D belonging to the initial mesh M, 3 Initialize the current surface S with the convex hull of P (included in D),

5

  Processing of thin parts Function Convection 2D(C : Curve) : while C = / 0 do e ← pop first oriented edge in C if Gabriel half-circle of e is empty then push e at the end of C temp else if e ∈ M then {RDG event} output time time ← 0 push e at the end of C f inal else if e such that e asso ∈ C (resp. C temp ) then remove e asso from C (resp. C temp ) else push {e 1 , e 2 } at the end of C end if time ← time + 1 end if end if end while Main 2D function : C ← boundaries of S border C f inal ← / 0;C temp ← / 0;time ← 0 Convection 2D(C) while C temp = / 0 do e ← pop first oriented edge in C temp if e such that e asso ∈ C temp then remove e asso from C temp else if e ∈ M then push e at the end of C f inal time ← time + 1 else {ODG event} output time time ← 0 C ← {e 1 , e 2 } Convection 2D(C) end if end if end while

Figure 2 :

 2 Figure 2: Fandisk : complete (12946 facets), then showing the non Delaunay facets only (1104 facets representing 8.5% of the set)

Figure 4 :

 4 Figure 4: triple hecate (detail) : 75729 vertices and 151462 facets coded with 0.04 bits per vertex

Figure 5 :

 5 Figure 5: max planck : 199169 vertices and 398043 facets coded with 0.90 bits per vertex

Table 1 :

 1 ) comes from Le Louvre C2RMF lab. Experimental results on usual meshes

	model	number of	connectivity	computing time
	(number	Delaunay	rate in bpv	in seconds
	of	(non Del.)	(Del. + non	(compression /
	vertices)	facets	Del. facets)	decompression)
	fandisk	11842	2.08	14.45s /
	(6475)	(1104)	(1.22 + 0.86)	14.48s
	blob	15226	2.68	16.69s /
	(8036)	(842)	(1.98 + 0.70)	14.64s
	horse	38173	2.00	26.38s /
	(19851)	(1525)	(1.48 + 0.52)	22.01s
	bunny	71890	0.08	17.60s /
	(35947)	(0)	(0.08 + 0.00)	13.66
	triple hecate	151462	0.04	46.30s /
	(75729)	(0)	(0.04 + 0.00)	37.15s
	max planck	391181	0.90	200.87s /
	(199169)	(6862)	(0.69 + 0.21)	156.75s
	hand	649922	0.19	341.52s /
	(327290)	(4674)	(0.11 + 0.08)	287.57s
	ajax	547117	0.14	153.63s /
	(273383)	(0)	(0.14 + 0.00)	117.13s