The exact Minkowski sum of polyhedra is of particular interest in many applications, ranging from image analysis and processing to computer-aided design and robotics. Its computation and implementation is a difficult and complicated task when nonconvex polyhedra are involved. We present the NCC-CVMS algorithm, an exact and efficient contributing vertices-based Minkowski sum algorithm for the computation of the Minkowski sum of a nonconvex--convex pair of polyhedra, which handles nonmanifold situations and extracts eventual polyhedral holes inside the Minkowski sum outer boundary. Our algorithm does not output boundaries that degenerate into a polyline or a single point. First, we generate a superset of the Minkowski sum facets through the use of the contributing vertices concept and by summing only the features (facets, edges, and vertices) of the input polyhedra which have coincident orientations. Secondly, we compute the 2D arrangements induced by the superset triangles intersections. Finally, we obtain the Minkowski sum through the use of two simple properties of the input polyhedra and the Minkowski sum polyhedron itself, that is, the closeness and the two-manifoldness properties. The NCC-CVMS algorithm is efficient because of the simplifications induced by the use of the contributing vertices concept, the use of 2D arrangements instead of 3D arrangements which are difficult to maintain, and the use of simple properties to recover the Minkowski sum mesh. We implemented our NCC-CVMS algorithm on the base of CGAL and used exact number types. More examples and results of the NCC-CVMS algorithm can be found at: http://liris.cnrs.fr/hichem.barki/mksum/NCC-CVMS

We present a new algorithm, based on the concept of contributing vertices, for the exact and efficient computation of the Minkowski difference of convex polyhedra. First, we extend the concept of contributing vertices for the Minkowski difference case. Then, we generate a Minkowski difference facets superset by exploiting the information provided by the computed contributing vertices. Finally, we compute the Minkowski difference polyhedron through the trimming of the generated superset. We compared our Contributing Vertices-based Minkowski Difference (CVMD) algorithm to a Nef polyhedra-based approach using Minkowski addition, complement, transposition, and union operations. The performance benchmark shows that our CVMD algorithm outperforms the indirect Nef polyhedra-based approach. All our implementations use exact number types, produce exact results, and are based on CGAL, the Computational Geometry Algorithms Library.

This paper presents a benchmarking system for the evaluation of robust mesh watermarking methods. The proposed benchmark has three different components: a ''standard'' mesh model collection, a software tool and two application-oriented evaluation protocols. The software tool integrates both geometric and perceptual measurements of the distortion induced by watermark embedding, and also the implementation of a variety of attacks on watermarked meshes. The two evaluation protocols define the main steps to follow when conducting the evaluation experiments. The efficiency of the benchmark is demonstrated through the evaluation and comparison of two recent robust algorithms.

In this paper, we present a new blind and robust 3-D mesh watermarking scheme that makes use of the recently proposed manifold harmonics analysis. The mesh spectrum coefficient amplitudes obtained by using this analysis are quite robust against various attacks, including connectivity changes. A blind 16-bit watermark is embedded through an iterative scalar Costa quantization of the low frequency coefficient amplitudes. The imperceptibility of the watermark is ensured since the human visual system has been proved insensitive to the mesh low frequency components modification. The embedded watermark is experimentally robust against both geometry and connectivity attacks. Comparison results with two state-of-the-art methods are provided.

We present an original approach for the computation of the Minkowski sum of a non-convex polyhedron without fold and a convex polyhedron, without decomposition and union steps-that constitute the bottleneck of convex decomposition-based algorithms. A non-convex polyhedron without fold is a polyhedron whose boundary is completely recoverable from three orthographic projections defined by three orthogonal basis vectors in Ropf3. First, we generate a superset of the Minkowski sum facets using the concept of contributing vertices we accommodate for a non-convex-convex pair of polyhedra. The generated superset guarantees that its envelope is the boundary of the Minkowski sum polyhedron. Secondly, we extract the Minkowski sum facets and handle the intersections among the superset facets by using 3D envelope computation. Our approach is limited to non-convex polyhedra without fold because of the use of 3D envelope computation to recover the Minkowski sum boundary. Models with holes are not handled by our method. The implementation of our algorithm uses exact number types, produces exact results, and is based on CGAL, the Computational Geometry Algorithms Library.

This paper describes a simple and efficient means for statistical detection of global and local mirror symmetry. The symmetry planes are selected from all the planes obtained after matching and pairing features extracted on 3D meshes. The original part of the proposed method is the way to extract significant symmetry planes with a 3D Hough transform built from the planes parameters. This method generates faster results compared to existing statistical methods for symmetry detection.

This paper presents a hierarchical watermarking framework for semiregular meshes. Three blind watermarks are inserted in a semiregular mesh with different purposes: a geometrically robust watermark for copyright protection, a high-capacity watermark for carrying a large amount of auxiliary information, and a fragile watermark for content authentication. The proposed framework is based on wavelet transform of the semiregular mesh. More precisely, the three watermarks are inserted in different appropriate resolution levels obtained by wavelet decomposition of the mesh: the robust watermark is inserted by modifying the norms of the wavelet coefficient vectors associated with the lowest resolution level; the fragile watermark is embedded in the high resolution level obtained just after one wavelet decomposition by modifying the orientations and norms of the wavelet coefficient vectors; the high-capacity watermark is inserted in one or several intermediate levels by considering groups of wavelet coefficient vector norms as watermarking primitives. Experimental results demonstrate the effectiveness of the proposed framework: the robust watermark is able to resist all common geometric attacks even with a relatively strong amplitude; the fragile watermark is robust to content-preserving operations, while being sensitive to other attacks of which it can also provide the precise location; the payload of the high-capacity watermark increases rapidly along with the number of watermarking primitives.

Three-dimensional (3-D) meshes have been used more and more in industrial, medical and entertainment applications during the last decade. Many researchers, from both the academic and the industrial sectors, have become aware of their intellectual property protection and authentication problems arising with their increasing use. This paper gives a comprehensive survey on 3-D mesh watermarking, which is considered an effective solution to the above two emerging problems. Our survey covers an introduction to the relevant state of the art, an attack-centric investigation, and a list of existing problems and potential solutions. First, the particular difficulties encountered while applying watermarking on 3-D meshes are discussed. Then we give a presentation and an analysis of the existing algorithms by distinguishing them between fragile techniques and robust techniques. Since attacks play an important role in the design of 3-D mesh watermarking algorithms, we also provide an attack-centric viewpoint of this state of the art. Finally, some future working directions are pointed out especially on the ways of devising robust and blind algorithms and on some new probably promising watermarking feature spaces.

An original hierarchical watermarking scheme for three-dimensional triangular meshes is proposed in this paper. A geometrically robust watermark and a high-capacity watermark are inserted in different resolution levels of the wavelet decomposition of a semi-regular mesh by modifying the norms of wavelet coefficients. Both watermarks are blind and invariant to similarity transformations. The robustness of the first watermark is achieved by synchronizing and quantizing watermark primitives according to edges lengths of the coarsest level, which are quite insensible to geometrical attacks. The high capacity of the second watermark is obtained by considering the permutation of the norms of a group of wavelet coefficients. Experiments have proven the high robustness of the first watermark under common geometrical attacks. To our knowledge, the capacity of the second method, which can attain the factorial of the candidate coefficients number, is the highest for 3D meshes in the literature.