3D Shape Retrieval Engine

Contact: Remco Veltkamp
A New Geometric Approach to 3D Shape Matching

Due to the recent improvements in laser scanning technology, 3D visualization and modelling, there is an increasing need for tools supporting the automatic search for 3D objects in archives. We have implemented a new geometric approach to 3D shape comparison and retrieval for arbitrary objects described by 3D polyhedral models that may contain gaps. To compare two objects geometrically we first apply principal components analysis to bring the objects in a standard pose, and enclose each object by a 3D grid. Then we generate for each object a signature representing a weighted point set, that contains for each non-empty grid cell a salient point. We implemented three methods to select in each grid cell a salient point:

  • (Gaussian curvature) choose the vertex in the cell with the highest Gaussian curvature, and choose as weight a measure for that curvature,
  • (Normal variation) choose the area-weighted mean of the vertices in the cell, and choose as weight a measure denoting the normal variation of the faces in the cell and
  • (Midpoint) choose the midpoint of all vertices in the cell, and choose as weight one.
Finally, we compute the similarity between two shapes by computing a new transportation distance between the two weighted point sets that, unlike the Earth Mover's Distance, satisfies the triangle inequality. This property makes it suitable for use in indexing very large collections of models.

Experimental results

To demonstrate the strength of our approach we implemented an experimental shape retrieval engine. The results below are obtained using

  • a database from Princeton (133 models collected from the web, as used in the paper "Matching 3D Models with Shape Distributions", by Rob Osada et al., International Conference on Shape Modeling and Applications (SMI 2001)
  • a database consisting of 684 VRML models, that we have collected from the word wide web
  • a database consisting of 102 "L-shaped" blocks that we have downloaded from the ShapeSearch.net website.
The demo pages below use the VRML format to show the query model and the retrieved 3D models. It is also possible to compare the weighted point sets of the query model and a retrievel model in VRML format. You need a plugin to view these VRML models, for example cortona.

Results on the Princeton database
Results on the Utrecht database
Results on the L-shaped blocks database
Test database

From our database containing 684 models we obtained a test database by classifying 512 models into six categories: 242 conventional air planes, 60 delta-jets, 45 multi-fuselages, 19 biplanes, 10 helicopters and 136 other models. This classification was purely on the basis of shape, not on the type of object. We did not classify the remaining 172 models, because it was not clear to which class these models should belong, looking at their shape. You may download here, the test database and our complete database.

The 'Princeton database' was kindly provided by the Princeton Shape Retrieval and Analysis Group.