# Fragile Watermarking of 3D Models in a Transformed Domain
## 5 The Proposed Algorithm  
The developed algorithm has the objective to protect the shape and the structure of a 3D model, defined in terms of a mesh of polygons, providing a verification that allows for identification and localization of modifications to the model. In particular, the algorithm that will be presented in this section will protect:  
* vertex coordinates (i.e., the geometry of the model);
* the polygon structure, as defined by the corresponding vertex connections (that is, the topology). In the present embodiment, vertices' normal vectors are not considered because it was found that some 3D modeling software (e.g., Blender) alter them according to vertices' positions; thus,authentication data would be ob obsoleted by the modeling software at saving or loading time, inducing our verification procedure to flag vertices as forged. Nonetheless, protecting vertices will have as a side effect the protection of normals computed from them. To allow modifications that maintain the structure of the 3D model to the file representing it, the proposed method permits order alterations to the vertices and to the polygons as they are stored in the file. This provides independence, to some extent, from the particular file format. The method is composed of two main modules, namely an embedder and an extractor, and three companion modules, which are a key generator, a watermark generator, and a verifier. The interactions between the modules and the main data interchanged are shown in Figure 1.  
Each vertex is considered an Embedding Unit (EU); in the present embodiment, the vertex is defined by three spatial coordinates \((x,y,z)\) and by the polygons to which the vertex belongs; a detailed description of this structure and of the embedding procedure will be given at the end of this section and in Section 5.2. The use of the EU concept solves the problem in 3D models that is not present in audio and image samples, that is the lack of the total order of the vertices. A bird's eye-view of the various modules is the following:  
* Key generator: defines a secret KLT basis to specify an embedding space;
* Watermark generator: creates the watermark bit string to be stored in each EU;
* Embedder: stores the watermark in the 3D model, one vertex at a time, using the KLT basis and the watermark provided by the respective modules; a computational intelligence technique, described in Section 4, is used to alter the vertex components so that the KLT coefficients of the vertex data contain the watermark; the output is a 3D model storing the fragile watermark;
* Extractor: extracts the watermark present in a 3D model using the secret KLT basis provided by the key generator module;
* Verifier: compares the extracted watermark with the one that should be contained in the vertices, providing the localization of tampered areas. The input data are a 3D model composed of a set of vertices and a set of polygons. Each vertex is defined by three coordinates \((x,y,z)\); every component value is considered in binary format, float representation (four bytes) in the IEEE 754 format. Every polygon is defined by the sequence of the indexes of its vertices. The watermark Embedding Unit (EU) is defined by the vertex data \((x,y,z)\) along with a combined fingerprint of the \(t\) polygons to which the vertex belongs. The fingerprint of a polygon is computed as follows: for every pair of vertices \((\mathbf{v}_{i},\mathbf{v}_{i+1})\) encountered on the perimeter, a cryptographic hash (c. h.) function \(H\) is computed, \(H(\mathbf{v}_{i},\mathbf{v}_{i+1})=h_{i,i+1}\); thus, for a polygon of \(n\) vertices, \(n\) cryptographic hashes will be obtained \(h_{1,2},h_{2,3},\ldots,h_{n,1}\). To be independent from the starting vertex, these hashes are XORed \(q=h_{1,2}\oplus h_{2,3}\oplus\ldots\oplus h_{n,1}\), then a c. h. is computed on the result \(q\); the value \(H(q)\) is the fingerprint of a polygon.