Ray Cast Visual Search (RCVS). Fast and simple algorithm for searching 3D objects with similar shapes
For me, these two models are quite similar, but in fact they don’t have obvious characteristics to measure this similarity. These models have different numbers of vertices, edges and polygons. They are of different sizes, rotated differently and both have the same transforms (Location = [0,0,0], Rotation in radians = [0,0,0], Scale = [1,1,1]). So how to determine their similarity?
If these models were equally oriented in space, they could be scaled to the common size of Bounding Box, then move the origin of local coordinates to its center, convert models to voxel representation and compare the lists of voxels.
If these models were arbitrarily oriented along the coordinate axes, they could be scaled to the common size of Bounding Box, then move the origin of local coordinates to its center, render them from six sides and compare sets of images among themselves.
In order to achieve rotation invariance, I decided to turn to a spherical coordinate system.
First, I calculated the distances to the voxels from the origin, collected the distances in ordered lists and compared these lists. This yielded good results, but it took a long time to convert models to voxel representation of enough resolution and to compare large lists.
Short description of RCVS
Instead of voxelization and rendering, my method is based on Ray Casting. The model is placed inside the icosahedral spherical polyhedron, rays are casted from its polygons towards the model surface and their lengths are collected in lists.
Lists of these lengths are sorted and compared with each other. Sorting eliminates rotation, since for the same or close in geometry models rays lengths will coincide within the margin of error, but differ in order.
Comparison results for Suzanne Monkey models:
Suzanne_lo
Suzanne_lo | 1
Suzanne_lo_rot_rand | 0.9878376875939173
Suzanne_lo_rot_90 | 0.9800766750109137
Suzanne_hi_rot_rand | 0.9761078629585936
Suzanne_hi | 0.9730722945028376
Suzanne_hi_rot_90 | 0.9680325422930756
Skull | 0.7697333228143514
Ceramic_Teapot_rot_rand | 0.6634783235048608
Ceramic_Teapot | 0.6496529954470333
Grenade_MK2 | 0.5275616759076022Detailed description of RCVS
Before comparing 3D models (hereinafter referred to as objects), each one goes through the preparation phase (I implemented this part on Python in Blender):
- The origin of the local coordinates of the components of the object is set at the center of mass from the volume.
2. The object fits into the unit sphere centered at the origin of the local coordinates of object components.
3. Scale transformations are applied.
4. An icosahedral spherical polyhedron (hereinafter referred to as the icosphere) of unit radius with normals directed inward is built around the object. The number of icosphere polygons on which tests were carried out: 80, 320, 1280, 5120, 22480. The optimal number of icosphere polygons by time consumption and accuracy in the tests was determined to be 1280.
5. Rays are casted from each polygon of the icosphere towards the object surface with outside facing normals and their lengths are collected in lists.
6. Object normals are recalculated to point inside the mesh.
7. Rays are casted from each polygon of the icosphere towards the object surface with outside facing normals and their lengths are collected in lists. (This writes the internal geometry and/or fills the blind spots of previous rays).
8. Lengths of rays sent from opposite polygons are arranged in lists, where the first two values are from step 5 and the second two are from step 7. Each list is sorted by the smallest length value from step 5 so that the values from steps 5 and 7 match each other in pairs.
9. The list of lists of all rays lengths is sorted by the first value. This list has 4 columns and the number of rows equal to half the number of polygons in the icosphere.
10. List of rays lengths is written to file.
The list of rays lengths looks something like this:
0.00271218840585662 0.2112752957162676 0.00271218840585662 0.2112752957162676
0.004740002405006037 0.210980921765861 0.004740002405006037 0.2109809188911709
0.00660892842734402 0.2066613370130234 0.00660892842734402 0.2066613370130234
…
0.2692299271137439 0.2725085782639611 0.2692299271137439 0.2725085782639611
0.2705489991382905 0.2707842753523402 0.270548999138295 0.2707843056356914
0.2709498404192674 0.271036677664217 0.2709498404192674 0.271036642944409When all the objects got their lists of rays lengths they can be compared (I wrote this part on Rust):
- Setting the threshold value of the acceptable error. In the tests, the best value was determined to be 0.01, the error within 1%.
- Creating the compliance score variable.
- For each row in the first list, searching for a row from the second, for which the sum of deviations does not exceed the error multiplied by the number of values. If such a string is found, it is not involved in further search. The pairwise absolute difference of the values from the two lists is calculated and subtracted from 1, the arithmetic mean of these values is added to the score.
- When all the lines of the first list are passed, the score value is divided by the number of lines. The calculated value is the result of a comparison.
- If the objects are similar in shape (regardless of their scale and rotation), the result is close to 1.
Bananas, Vitruvian Man, and restrictions of RCVS
The algorithm works great for finding objects close in geometry, for example, high- and low-polygon variants of the same model, sometimes it copes well with objects that are similar in meaning, for example, with teapots or guitars of various shapes. However, since the number of models to which the same list of rays lengths will correspond can be approximately estimated at n!(n2)!, there is a significant probability that objects visually dissimilar in geometry will have a score of coincidence in the range 0.5–0.9. During the tests, such things happened with bananas, which coincided with airplanes and people in different poses by 0.7, which in turn coincided with tigers and dogs by “impressive” 0.85.
To refine search should take into account the size and / or rotation of objects.
