How to calculate a hash of 3D object
Being inspired by general idea of 3D real object’s Digital Transformation issue coming from here https://3dpass.medium.com/3d-objects-as-passwords-440abd2aac08 I’ll try to attempt describing how to calculate a hash ID from 3D object. I’ve named it “Grid2d”.
First of all the calculated hash has to be reproducible i.e stable for different scans of the object within a noise of scanning. We don’t have any feedback to compare and get a single 100% working hash from each one 3D scan. So we need to get a sorted short list of hashes as a result. The algorithm will be stable if the hash value presents on the top of the list of each scan processed.
The simplest way to get some unique characteristics from surface of the object is to cut it into N slices and process each of them separately. The problem, therefore, now turns into 2D. By means of combining results from N slices, it is getting possible to calculate the final hash.
Prerequisites:
- The object must be simply connected (i.e without through holes)
- The object must not be the regular formed
- The colors and textures are ignored
1. The object orientation to meet the following conditions:
- The center of coordinates is at the center of mass of the object
- Cartesian coordinates coincide with main inertia vectors
In order to get it unambiguously the main inertia components have to be different, let say, by 10% (parameter #1 of algorithm). Objects like a sphere or a cylinder should be rejected. So axis X coincides with inertia vector corresponded to maximum inertia component, next axis Y and last axis Z corresponded to minimum inertia component.
2. Cutting the object by N planes uniformly spaced alongside the OX axis. Crosses of planes and object’s surface either produce N contours.
3. For each contour the following steps are performed:
3.1 Scale the contour to fit a square having sides equal to maximum size of contour alongside X or Y coordinates.
3.2 Select the number of cells in the square MxM (parameter #2 of the algorithm). Let us assume M=8 (like a chess board)
3.3 Find the set E of cells containing our contour. Because of noise we add to this set not only cells that contour passes through but the neighboring as well. Cells should be added to E if the contour is close to grid vertices less than 10% of cell size, by example (parameter #3 of the algorithm).
3.4 Generate all the possible polygons with vertices belonging to set E. Neighboring vertices have to be at a distance L, for example L=2 (parameter #4 of the algorithm). Vertices must not be close to each other at a distance less than L.
There are two polygons allowed are represented at the Drawing 1.
3.5 Calculate root mean square deviation (RMSD) from the polygon and the contour and do it for each polygon. In order to get it done we approximate the contour with splines and evaluate Q points uniformly spaced in approximating curve (parameter #5 of the algorithm). Also we need to evaluate Q points at the polygon. Spline approximation can be evaluated by splprep function from Python scipy package.
RMSD is:
Where Pi=(xi, yi) — point at countour, Ri — point at polygon.
3.6 Sort all the generated polygons by RMSD and take T best of them (parameter #6 of the algorithm).
4 Perform cartesian product of all the best polygons from each slice. The product of two polygons means concatination of their points (coordanates of vertices).
For example if:
We get:
So we’ve got the input data for sha256 (may be other hash function). The last step is trivial.
The output of Grid2d algorithm is a list of hashes sorted by its affinity to object’s surface. Parameters of the algorithm are to be figured out by experiments and tests.
