Abstract : In this paper, we propose a novel progressive lossless mesh compression algorithm based on Incremental Parametric Refinement, where the connectivity is uncontrolled in a first step, yielding visually pleasing meshes at each resolution level while saving connectivity information compared to previous approaches. The algorithm starts with a coarse version of the original mesh, which is further refined by means of a novel refinement scheme. The mesh refinement is driven by a geometric criterion, in spirit with surface reconstruction algorithms, aiming at generating uniform meshes. The vertices coordinates are also quantized and transmitted in a progressive way, following a geometric criterion, efficiently allocating the bit budget. With this assumption, the generated intermediate meshes tend to exhibit a uniform sampling. The potential discrepancy between the resulting connectivity and the original one is corrected at the end of the algorithm. We provide a proof-of-concept implementation, yielding very competitive results compared to previous works in terms of rate/distortion trade-off.

Abstract: In this paper, we propose a new algorithm to mesh implicit surfaces which produces meshes both with a good triangle aspect ratio as well as a good approximation quality. The number of vertices of the output mesh is defined by the end-user. For this goal, we perform a two-stage processing : an initialization step followed by an iterative optimization step. The initialization step consists in capturing the surface topology and allocating the vertex budget. The optimization algorithm is based on a variational vertices relaxation and triangulation update. In addition a gradation parameter can be defined to adapt the mesh sampling to the curvature of the implicit surface. We demonstrate the efficiency of the approach on synthetic models as well as real-world acquired data, and provide comparisons with previous approaches.

Abstract: In this paper, we propose a novel tetrahedral mesh generation algorithm, which takes volumic data (voxels) as an input. Our algorithm performs a clustering of the original voxels within a variational framework. A vertex replaces each cluster and the set of created vertices is triangulated in order to obtain a tetrahedral mesh, taking into account both the accuracy of the representation and the elements quality. The resulting meshes exhibit good elements quality with respect to minimal dihedral angle and tetrahedra form factor. Experimental results show that the generated meshes are well suited for Finite Element Simulations.

Abstract: In this paper, we present a novel method for medial axis approximation based on Constrained Centroidal Voronoi Diagram of discrete data (image, volume). The proposed approach is based on the shape boundary subsampling by a clustering approach which generates a Voronoi Diagram well suited for Medial Axis extraction. The resulting Voronoi Diagram is further filtered so as to capture the correct topology of the medial axis. The resulting medial axis appears largely invariant with respect to typical noise conditions in the discrete data. The method is tested on various synthetic as well as real images. We also show an application of the approximate medial axis to the sizing field for triangular and tetrahedral meshing.

Abstract: In this paper, we propose a generic framework for 3D surface remeshing. Based on a metric-driven Discrete Voronoi Diagram construction, our output is an optimized 3D triangular mesh with a user defined vertex budget. Our approach can deal with a wide range of applications, from high quality mesh generation to shape approximation. By using appropriate metric constraints the method generates isotropic or anisotropic elements. Based on point-sampling, our algorithm combines the robustness and theoretical strength of Delaunay criteria with the efficiency of entirely discrete geometry processing . Besides the general described framework, we show experimental results using isotropic, quadric-enhanced isotropic and anisotropic metrics which prove the efficiency of our method on large meshes, for a low computational cost.

Abstract: In this paper, we present a wavelet-based progressive compression method for isomorphic 3-D mesh sequence with constant connectivity. Our method reduces the spatial and temporal redundancy by using both spatial and temporal wavelet analysis. To encode geometry information, each mesh frame is decomposed into a base mesh and its spatial wavelet coefficients of each resolution level by spatial wavelet analysis filter bank. The spatially transformed sequence is decomposed into several sub-band signals by temporal wavelet analysis filter bank. The resulting signal is encoded by using an arithmetic coder. Since an isomorphic mesh sequence has the same connectivity over all frames, the connectivity information is encoded only for the first mesh frame. The proposed method enables both progressive representation and lossless compression in a single framework by multi-resolution wavelet analysis with a perfect reconstruction filter bank. Our method is compared with several conventional techniques including our previous work.

Abstract: In this paper, we present a wavelet-based progressive compression method for 3-D dynamic meshes. Our method exploits the spatial and temporal redundancy. We encode the geometry of base mesh, the wavelet coefficients and the connectivity of each resolution level in order to reduce the spatial redundancy of intra meshes. For inter mesh coding, we encode the differences of geometry of base meshes and of their wavelet coefficients between adjacent frames to reduce the temporal redundancy. Our proposal is based on the wavelet-based multiresolution analysis which uses a perfect reconstruction filter bank and therefore it enables not only progressive representation but also lossless compression. The simulation results demonstrate that the proposed method is applicable to lossy and lossless compression of 3-D dynamic meshes.

Abstract: In this paper, we propose an adaptive polygonal mesh coarsening algorithm. This approach is based on the clustering of the input mesh triangles, driven by a discretized variationnal definition of centroidal tesselations. It is able to simplify meshes with high complexity i.e. meshes with a large number of vertices and high genus. We demonstrate the ability our scheme to simplify meshes according to local features such as curvature measures. We also introduce an initial sampling strategy which speeds up the algorithm, an on-the-fly checking step to guarantee the validity of the clustering, and a postprocessing step to enhance the quality of the approximating mesh. Experimental results show the efficiency of our scheme both in terms of speed and visual quality.

Abstract: Most of the meshes coming from a variety of source are over sampled and exhibit highly irregular connectivity that prevent efficient wavelet analysis. Remeshing comes as a solution to sampling and connectivity optimization with respect to the geometry. The main drawback of existing subdivision remeshing approaches is the lack of control either on the number of triangles or on the geometrical error. We propose a new remeshing scheme that directly produces wavelet-based multiresolution meshes which does not suffer from the previous limitations. We provide a finer control on the resulting number of triangles by using an adaptive subdivision scheme. We also show a lowering of the local resulting geometrical error by using a new curvature-based subdivision criterion.

Abstract: In this paper, we propose a robust watermarking method for 3-D triangle surface meshes. Most previous methods based on the wavelet analysis can process only semi-regular meshes. Our proposal can be ap- plied to irregular as well as regular meshes by using recently introduced irregular wavelet analysis scheme. L2-Norm of the wavelet coefficients is modified in various multi-resolution levels to embed the watermark. We also introduced a vertex and face re-ordering process as pre-processing in both watermark embedding and extraction for the robustness against connectivity reordering attacks. In addition, our proposal employs blind watermark detection scheme, which can extract the watermark without reference of cover mesh model. Through the simulations, we prove that our approach is robust against connectivity reordering as well as various kinds of geometrical attacks such as lossy compression and affine transform..

Abstract:This paper introduces a novel partitioning algorithm for 3D polygonal meshes. The proposed approach is based on protrusion conquest which, for a given model, takes into account both the computed protrusion and the connectivity. The only constraint on the input mesh is that it must consist of one connected component. Our algorithm provides a good way to decompose the mesh into preceptually significant parts. The parts are further modeled by ellipsoids and a connectivity graph between them. This semantic representation is compliant to the perceptual shape description defined by the emergent standard MPEG-7.

Sébastien Valette and Jean-Marc Chassery, Approximated Centroidal Voronoi Diagrams for Uniform Polygonal Mesh Coarsening, Computer Graphics Forum (Eurographics 2004 proceedings), Vol. 23, No. 3, September 2004, pp. 381-389. [PDF][Software]

Abstract: We present a novel clustering algorithm for polygonal meshes which approximates a Centroidal Voronoi Diagram construction. The clustering provides an efficient way to construct uniform tessellations, and therefore leads to uniform coarsening of polygonal meshes, when the output triangulation has many fewer elements than the input mesh. The mesh topology is also simplified by the clustering algorithm. Based on a mathematical framework, our algorithm is easy to implement, and has low memory requirements. We demonstrate the efficiency of the proposed scheme by processing several reference meshes having up to 1 million triangles and very high genus within a few minutes on a low-end computer.

Abstract: This paper extends Lounsbery s multiresolution analysis wavelet-based theory for triangular 3D meshes, which can only be applied to regularly subdivided meshes and thus involves a remeshing of the existing 3D data. Based on a new irregular subdivision scheme, the proposed algorithm can be applied directly to irregular meshes, which can be very interesting when one wants to keep the connectivity and geometry of the processed mesh completely unchanged. This is very convenient in CAD (Computer-Assisted Design), when the mesh has attributes such as texture and color information, or when the 3D mesh is used for simulations, and where a different connectivity could lead to simulation errors. The algorithm faces an inverse problem for which a solution is proposed. For each level of resolution, the simplification is processed in order to keep the mesh as regular as possible. In addition, a geometric criterion is used to keep the geometry of the approximations as close as possible to the original mesh. Several examples on various reference meshes are shown to prove the efficiency of our proposal.

Abstract: This paper proposes a new lossy to lossless progressive compression scheme for triangular meshes, based on a wavelet multiresolution theory for irregular 3D meshes. Although remeshing techniques obtain better compression ratios for geometric compression, this approach can be very effective when one wants to keep the connectivity and geometry of the processed mesh completely unchanged. The simplification is based on the solving of an inverse problem. Optimization of both the connectivity and geometry of the processed mesh improves the approximation quality and the compression ratio of the scheme at each resolution level. We show why this algorithm provides an efficient means of compression for both connectivity and geometry of 3D meshes and it is illustrated by experimental results on various sets of reference meshes, where our algorithm performs better than previously published approaches for both lossless and progressive compression.

Abstract: In this paper we introduce a novel approach for progressive transmission of three-dimensional (3D) triangular meshes. This algorithm is based on a new reversing approach of the irregular mesh subdivision that enables a wavelet representation of any mesh geometry. In this paper, we show how to achieve progressive compression of 3D models by transmitting more and more wavelet coef cients computed from the original mesh vertices coordinates. The connectivity of the reconstructed mesh remains the same as the original one, but its geometry is progressively re ned by means of bitplane encoding. This approach processes directly oating point coordinates which is the most common representation for 3D meshes, and does not need quantization, which is a lossy transformation. Experimental results are given and demonstrate the efficiency of our encoding scheme versus other approaches.

Abstract: A new content based mesh design algorithm for video objects segmentation and tracking is proposed. The algorithm moves the mesh nodes along motion or luminance discontinuities in order to fit the objects boundaries. The motion inside adjacent triangular cells is estimated by competitive forward-backward matching. This approach allows the displacements of the nodes without the remeshing of occlusion regions : uncovered background nor background to be covered. The mesh is deformed under the minimization of an objective function. This function includes a motion energy, a spatial boundary energy and a temporal regularization energy. The motion energy is effective in textured regions while the boundary energy mainly operates in homogeneous one according to a boundary distance map. The temporal regularization energy keeps the objects tracking stable along the sequence due to its object-based approach. Experimental results with both synthetic and real world sequences prove the efficiency of the proposed approach and the cooperative action of the three energy terms.

Abstract: We consider the construction of a multiresolution triangular mesh for 3D model-based segmentation. In the 3D Snake approach this model needs to be both uniform and regular for convergence purposes. We propose here a remeshing algorithm to compute such a model from an arbitrary triangular mesh. The input mesh is first parametrized in 2D. the output mesh connectivity is fixed by a subdivided base mesh. Its geometry comes from the input mesh via the parametric domain tesselation with respect to uniformity constraints. Experiments were carried out with both synthetic and organ models. They prove the low geometry remeshing error and the uniformity of the resulting mesh.

Abstract: Wavemesh is a powerful scheme for 3D triangular mesh processing. In sharp contrast with other approaches using wavelets for mesh compression which apply only to meshes having subdivision connectivity, Wavemesh can simplify, approximate, and compress meshes even if they do not respect this constraint. Results clearly indicate that Wavemesh outperforms the other approaches in terms of progressive lossless compression. We propose in this paper an improvement for our scheme : higher efficiency for meshes with large subdivision connectivity sets, as shown by experimental results. Also, in some cases, the enhanced Wavemesh can even perform better than mono-resolution approaches in terms of connectivity compression.

Abstract: The new MPEG-4 standard will provide superior services for the user, as it introduces the video objects concept. However, there is no generic segmentation technique able to provide the segmentation maps for such a coding system. In this paper, we propose a novel mesh-based video segmentation and objects tracking algorithm with both robust motion estimation and modeling of motion of discontinuities. In addition, occlusions and uncovered regions are well managed. This allows the mesh deformation without the need to process remeshing in motion occlusion regions. The spatial properties of each frame are considered to make the mesh edges fit the image contents and a temporal smoothness constraint is also implemented. The proposed algorithm is able to segment multiple objects at the same time. Some experimental results are shown.

Abstract: We propose a new subdivision scheme derived from the Lounsbery's 1:4 face split, allowing multiresolution analysis of irregularly subdivided triangular meshes by the wavelet transforms. Some experimental results on real medical meshes prove the efficiency of this approach in multiresolution schemes. In addition we show the effectiveness of the proposed algorithm for lossless compression.