# A Watermarking Method for 3D Printing Based on Menger Curvature and K-Mean Clustering
## 3 The Proposed Algorithm
### Watermark Embedding  
A 3D printing model (3D triangle mesh) contains a number of facets, \(\mathbf{M}=\left\{\mathbf{F}_{i}|i\in[1,|\mathbf{M}|]\right\}\). Here, \(|\mathbf{M}|\) is the number of facets in a 3D triangle mesh \(\mathbf{M}\), and \(\mathbf{F}_{i}\) is the \(i^{th}\) facet. Each facet contains three vertices (three points), \(\mathbf{F}_{i}=\left\{v_{ij}\big{|}j\in[1,3]\right\}\) and a normal vector \(\mathbf{n}_{i}(nx_{i},ny_{i},nz_{i})\). The Menger curvature \(K_{i}\) of each facet \(\mathbf{F}_{i}\) is computed by its vertices and corresponding area as shown in Equation (2). \[K_{i}=\frac{4A_{i}}{|v_{i1}-v_{i2}|\times|v_{i2}-v_{i3}|\times|v_{i3}-v_{i1}|} \tag{2}\]  
Therein, \(A_{i}\) is the area of the facet. The \(|\mathbf{M}|\) facets in the 3D triangle mesh \(\mathbf{M}\) are divided into \(G\) groups; \(G=\left\{m_{g}\big{|}g\in[1,|G|]\right\}\) based on the value of the Menger curvature. Figure 3 shows the result of the facet clustering of the bunny triangle mesh based on Menger curvature. Facets in the same group will have the same color. After classifying \(|\mathbf{M}|\) facets into \(G\) groups, we find the maximum Menger curvature and minimum Menger curvature of each group and calculate the mean Menger curvature of each group. Assume that \(K_{max}^{Hg}\), \(K_{min}^{mg}\) and \(K_{mean}^{mg}\) are the maximum Menger curvature, minimum Menger curvature and mean Menger curvature of the group \(m_{g}\), respectively. The mean Menger curvature \(K_{mean}^{mg}\) of the group \(m_{g}\) is the average value of all Menger curvatures in the group \(m_{g}\) and calculated as shown in Equation (3) with \(\big{|}m_{g}\big{|}\) the number of facets in the group \(m_{g}\). \[K_{mean}^{mg}=\frac{\sum K_{i}\in m_{g}}{\big{|}m_{g}\big{|}} \tag{3}\]  
Next, we define \(\Delta_{mg}\) as the average value of \(K_{max}^{mg}\) and \(K_{min}^{m_{g}}\) as shown in Equation (4). \(\Delta_{mg}\) is the special value mentioned in Section 3.1 and used to change the value of the mean Menger curvature \(K_{mean}^{mg}\)  
\[\Delta_{mg}=\frac{K_{min}^{m_{g}}+K_{max}^{mg}}{2} \tag{4}\]  
Each group \(m_{g}\) is embedded in a watermark bit \(\omega_{g}\in\left\{0,1\right\}\)\(\left(g\in[1,|G|]\right)\) by changing the value of the mean Menger curvature of the group \(m_{g}\) on the reference of the average value \(\Delta_{mg}\). This means if \(\omega_{g}=0\), \(K_{mean}^{m_{g}}\) will be transformed into \(K_{mean}^{m_{g}*}\) that is smaller than \(\Delta_{mg}\). If \(\omega_{g}=1\), \(K_{mean}^{m_{g}*}\) will be transformed into \(K_{mean}^{m_{g}*}\) that is greater than \(\Delta_{mg}\):  
\[K_{mean}^{m_{g}*}=\left\{ \begin{array}{l}K_{mean}^{m_{g}*}>\Delta_{mg}\text{ if } \omega_{g}=1\\ K_{mean}^{m_{g}*}<\Delta_{mg}\text{ if }\omega_{g}=0\end{array} \right. \tag{5}\]  
Figure 3: (**a**) Original bunny triangle mesh and (**b**) facet clustering based on Menger curvature. To satisfy the above embedding condition, the watermarked mean curvature \(K_{mean}^{m_{g}*}\) will be changed as shown in Equations (6) and (7). \[\text{If }\omega_{g}=1,K_{mean}^{m_{g}*}=\left\{ \begin{array}{c}\Delta_{mg}+ \frac{\Delta_{mg}-K_{mean}^{m_{g}}}{2}\text{ if }K_{mean}^{m_{g}}<\Delta_{mg}\\ K_{mean}^{m_{g}}\text{ if }K_{mean}^{m_{g}}>\Delta_{mg}\end{array} \right. \tag{6}\]  
\[\text{If }\omega_{g}=0,K_{mean}^{m_{g}*}=\left\{ \begin{array}{c}\Delta_{mg}- \frac{K_{max}^{m_{g}}}{4}-\frac{K_{mean}^{m_{g}}}{4}\text{ if }K_{mean}^{m_{g}}>\Delta_{mg}\\ K_{mean}^{m_{g}}\text{ if }K_{mean}^{m_{g}}<\Delta_{mg}\end{array} \right. \tag{7}\]  
Figure 4 shows the change of the mean Menger curvature \(K_{mean}^{m_{g}}\) of the group \(m_{g}\) to \(K_{mean}^{m_{g}*}\) according to the watermark bit \(\omega_{g}\). The mean Menger curvature \(K_{mean}^{m_{g}*}\) is represented by the blue point. The watermarked mean Menger curvature \(K_{mean}^{m_{g}*}\) is represented by the red point. When \(\omega_{g}=0,K_{mean}^{m_{g}}\) will become less than \(\Delta_{mg}\) if it is equal or greater than \(\Delta_{mg}\).