# A Voxel-Based Watermarking Scheme for Additive Manufacturing
## 2 Materials and Methods
### Voxelization and Distance Field Computation  
In the proposed watermarking method, the input model is presumed to be contained in a volumetric space, composed of voxels. In case that the model is expressed in a traditional polygonal representation, a voxelization computation [18] is triggered to decompose it into voxels. To achieve this goal, we enclose the model by using an axis-aligned bounding box (AABB). Then, the AABB is divided into voxels by using a regular grid. At the following step, the voxels are classified into two types: model voxels and void voxels. A voxel is regarded as a model voxel if it is in the interior of the model or intersected with the model's boundaries. Otherwise, it is regarded as a void voxel. After the classification process, the intensities of the void and model voxels are set to zero and one, respectively. At the following stage, we construct a distance field \(D(x\),\(y\),\(z)\) in the AABB to record the shortest distances from the model surface to all the voxels. \(D(x\),\(y\),\(z)\) expands like a wave, originating at the model surface \(\Gamma(x\),\(y\),\(z)\) and propagating inwards and outwards. Its travelling speed is proportional to the inverse of its gradient magnitude. Hence, the distance function is governed by the eikonal equation [19],  
\[\left(\frac{\partial D}{\partial x}\right)^{2}+\left(\frac{\partial D}{ \partial y}\right)^{2}+\left(\frac{\partial D}{\partial z}\right)^{2}=\frac{1 }{f^{2}},\,D(x,y,z)=0\,\textit{in}\,\,\Gamma,\,f=1. \tag{1}\]  
where \(f\) is the propagation speed of the distance field. We compute the distance field by using the revised fast marching method (RFMM), developed in the research of [20]. In the computation, all the voxels in the AABB are grouped into three sets: DONE, CLOSE, and FAR. DONE contains those voxels, whose final distances are computed. CLOSE keeps the voxels, which are adjacent to the voxels of DONE. Other voxels are stored in FAR. Initially, the voxels belonging to the model's boundary, \(\Gamma(x\),\(y\),\(z)\), are inserted into DONE and their distances are set to a purposefully selected value, for example zero. Then, the voxels adjacent to DONE are searched and stored in CLOSE. When inserting a voxel into CLOSE, we apply forward and backward differences to approximate the partial derivatives of Equation (1) and use the distances of its neighbors in DONE to convert Equation (1) into a quadratic polynomial. Then, the voxel's distance is set to the larger root of this quadratic polynomial. To speed up the computation, CLOSE is implemented by using a priority queue [21], such that the voxel belonging to CLOSE and having the smallest distance is  
Figure 1: Flowchart of the watermarking method. always at the top-most position of CLOSE. Since the voxels in FAR do not contact any voxels of DONE, their distances are set to infinite at the initial stage. Then, the computation is iteratively carried out. At each iteration, the top-most voxel of CLOSE is removed and inserted into DONE. Subsequently, those of its neighbors, which are in CLOSE or FAR, are searched and new distances of these neighboring voxels are calculated by using the method mentioned in the previous paragraph. If the new distance of a neighbor is shorter than its current one, the distance of this neighbor is replaced by the new distance. After this updating procedure, the neighbors, which were in FAR before the updating, are removed from FAR and inserted into CLOSE. Along with each distance modification and voxel insertion, positions of voxels in CLOSE are adjusted according to their distance values to ensure the top-most voxel always has the shortest distance in this set. These calculations are repeated until CLOSE becomes empty. The details of the RFMM can be found in the paper of [20]. The paper of [19] provides an alternative method for computing distance fields. Figure 2 shows some results, generated by the voxelization and distance field computation. The input model, displayed in part (a), is a bowl, formed by triangles.