General
Algorithm name: Grid2d, Author: Michael Co (3DPass Core developer and co-founder), Published: Dec 14, 2020
First of all, the hash calculated has to be reproducible i.e stable for different scans of the same 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 automatically. So we need to get a sorted short list of hashes as a result to get user the opportunity picking up the most stable one. The hash ID will be considered stable if the hash value presents on the top of the list every time new scan of the same object’s processed. The algorithm logic is flexible enough to adjust the definition level of processing to the 3D scanning resolution and accuracy which might differ depends on the scanning device
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 have the regular form
- The colors and textures are ignored
3D object shape processing
1. The object orientation has 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 sphere or cylinder should be rejected. So, the axis X coincides with the inertia vector corresponded to maximum inertia component, next axis Y and last axis Z corresponded to minimum inertia component.
2. Cutting the object with N planes
Let’s cut the object by N planes uniformly spaced alongside the OX axis. Then either crosses of planes and object’s surface produce N contours.
Drawing 1: Cutting the object with 3 planes:
3. For each contour the following steps will be 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).
Drawing 2: Set of cells allowed
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.
Drawing 3: Building a polygon
Down below are exposed two allowed polygons of the object represented in 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.
The 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.
Perform cartesian product of all the best polygons from each slice. The product of two polygons means concatination of their points (coordinates of vertices).
For example, if:
We get:
So, we’ve got the input data for sha256. The last step is trivial.
5. sha256 hashes creation
The output of Grid2d algorithm is a list of hashes sorted by its affinity to object’s surface.
Learn some examples and how to use the algorithm in practice..
pass3d is the application for Linux.
HASH ID strength
Since Hash ID is based on 3D object shape, its strength depends on how predictable the object shape is.
If an object had a ball shape, cube shape or some predictable and well-known-stuff- shape, then all of those seed-objects would give us weak strength HASH IDs. And most of them Grid2d is able to recognize and reject before the hash generating process got started.
If a random-shaped object was chosen like either a piece of natural rock or randomly deformed and hardened clay that has on its surface a lot of different turbulences, elevations and pits, elongation, needles and peaks, then it would give us a strong HASH ID.
If the object has a predictable shape it’s recommended to use mulli-object options as 2FA to get more uniqueness to it. For example, the ball has the most predictable shape of all shapes in the world. But if the biometric data was put in addition to, the combination of “ball + biometric data” becomes very strong and non predictable one. The same way it might be leveraged some different properties of the object like weight, clarity, density, etc.
Hash ID strength, as well, depends on 3D scanning resolution leveraged for taking scans from the object. If 3D scanning had been performed by a High Definition scanner, 3D model would’ve followed the shape of the object surface quite close. And that quality allows for Grid2d to recognize lots of tiny little details that might differentiate the object from others. The higher quality of scan you take, the more HASH ID strength you can potentially get.
Some examples:
3D object additional properties
Besides 3D shape, any real world object has some unique additional properties which might help reliably to authenticate it by several sights. Most important of them are the measurable ones, such as: weight, density, clarity, hardness, coloring, owner’s biometric data. And all of those properties can be revealed by lab measurements and scanning. Lab measurement equipment might represent smart devices (IoT) connected to 3DP network directly.