ImplementationThere is a need for an accurate and efficient method of local surface comparison in computer graphics. A good metric is able to perceive subtle differences in surface geometry when two comparing two points. Two of the methods currently employed are spin images, a 2-D histogram of distance tangent plane and surface normal, and surface point signature, a modified version of spin images which measures distance and angle with surface normal. Another method is the 3-D point fingerprint which uses a geodesic measure to get a 2-D contour representation of concentric circles drawn about the point on a tangent plane. As with these other methods, the geodesic fans propose a metric that effectively measures the similarity between points.
Geodesic fans are neighborhoods at every vertex that are uniformly sampled and compare to find a degree of similarity. The geodesic measure allows for an accurate sampling across a variety of surfaces and takes into account the geometry and contour of the surface since the fans extend out on the actual surface instead of above it. In addition, a fan contains eight vectors or "spokes", which are each separated by 45 degrees so that each spoke has a negative partner and all eight spokes cover 360 degrees around the central vertex. By equally spacing spokes around the central vertex and consistently placing sample points along each spoke, the entire fan is uniformly sampled independent of fan size.
ImplementationAssuming that you have a near manifold surface comprised of triangles, the fans are created for every vertex on the model. The first spoke is found by intersecting the vector with the middle of the opposite edge of an adjacent triangle. The remaining spokes are created by finding vectors 45 degrees away from the first spoke and so on until all eight are found. Next, each spoke is extended a certain length, a fraction of the length of the bounding box diagonal. By default the value is 0.03 of the diagonal length, but this value can be change by the user. All intersections between the vector, as it travels along the surface, and the edges of adjacent triangles are recorded.
Once the fans are created, sampling is done by calculating the values at a predetermined number of points on each spoke. The number of samples on each spoke is set as a constant, currently ten, so that it is completely independent of the length of the spoke and the space between samples increases as the spoke length increases. The values collected at each sample point are one of three similarity metrics. The first metric is the depth or the distance between the point and the plane that contains the central vertex. The second is a function (referred to as TBN) representing the geometry of the surface where a dot product is taken between the initial direction of the current spoke and the difference between the sample position and the central vertex, between surface normal at the central vertex and the difference between the sample position and the central vertex, and between the cross product of the initial direction and the surface normal and the difference between the sample position and the central vertex . The final metric is the normal value at each sample point.
To find similarity, one point is selected and compared with all other points to find ones most similar to it. The difference between a fan’s sampling and the one you are comparing it to are totaled. These results are compared to the results of every other permutation of the fan with the comparing fan and the lowest value is used as the value which will represent that point. Each point is represented by one value. The closer that value is to zero, the more similar the two points are with respect to the current metric.
Three models were tested using the three different similarity metrics previously described. The values obtained by the metric were then normalized and assigned a color value based on its position between zero and one. Red is the most similar values and blue is the least similar. In general, as spindle length increases the differentiation between points becomes more apparent and the distribution of the points is more evenly distributed along the entire range of similarity metric values. Also, as fan size increases the distribution curve becomes more centered around the median value of the group instead of the minimum value. The similarity metrics that were most effective were TBN and the normal distribution. In both cases, points were matched better than when the depth equation was used.
The sphere model was tested at one point at a pole and one not at a pole. Spindle lengths of 0.03, 0.04, and 0.07 of the boundary area diagonal were used. Computation time remained almost constant as fan size increased and the average computation time for the depth was 0.045 seconds, TBN was 0.065 seconds, and the normals was 0.052 seconds. As seen in the figures below, the non-pole points are almost identical to the selected point while the pole points are all very different from the point. The one exception seems to be the depth metric which shows a larger area of differentiation even though the values are separated by less than 0.00001. This is because all of the depth values were normalized before they were translated into color values. As a result, even the slightest difference will show up in the visualization.
|
|
|
|
The seahorse model was tested at four separate points on the model's surface. Spindle lengths of 0.03, 0.04, and 0.07 of the boundary area diagonal were used. Computation time remained almost constant as fan size increased and the average computation time for the depth was 0.57 seconds, TBN was 0.922 seconds, and the normals was 0.686 seconds.
|
|
|
|
|
|
|
|
The bunny model was tested at four points on the body. Spindle lengths at various points between 0.02 and 0.08 of the boundary area diagonal were used. Computation time remained increased by 60 seconds for every fan size increase of 0.01 and the average computation time for the depth was 181.14 seconds, TBN was 142.81 seconds, and the normals was 223.19 seconds.
|
|
|
|
|
|
|
|
|
|
|
|
Local surface comparison using geodesic fans can provide a very specific point-by-point comparison of models in the application of object recognition. Currently, many of the methods used in object recognition focus on the overall shape of an object instead of individual values within the model. As a result, these methods return object matches which may be of a similar shape, but not necessarily the same type of object. The geodesic fan method could provide more reliable and exact results. Similarly, geodesic fans can provide a very specific point-by-point comparison of models in surface registration. Geometric models acquired from laser range scanners are initially a set of scans because the whole surface is not visible from a single point of view. Therefore, the scans must be registered to form a single model that covers most or the object’s entire surface. Lastly, geodesic fans can potentially be used in mesh manipulation, either to find and replace similar geometric features on a model’s mesh or to find similar points between two models.
Y.Sun, J.Palk, A.Koschan, D.L. Page, and M.A. Abidi, "Point Fingerprint: A New 3-D Object Representation Scheme," IEEE Trans. On Systems, Man and Cybernetics - Part B: Cybernetics, Vol. 33, No. 4, pp. 712-717, August 2003.
S.Zelinka and M.Garland, "Similarity-Based Surface Modelling Using Geodesic Fans" Eurographics Symposium on Geometry Processing (2004), Eurographics Association.