A search engine for 3D models

Thomas A. Funkhouser, Patrick Min, Michael M. Kazhdan, Joyce Chen, J. Alex Halderman, David P. Dobkin, David Pokrass JacobsACM Trans. Graphics 2003 · DOI

TL;DR

This paper introduces a novel search engine for 3D models that goes beyond traditional text-based searches by incorporating shape-based queries. They developed a new, rotation-invariant shape descriptor using spherical harmonics, enabling efficient and robust shape matching, and integrated it with intuitive user interfaces like 2D and 3D sketching.

What Problem Does This Paper Address?

The increasing availability of 3D models on the web presents a challenge: how do we effectively find specific models? Traditional text-based search engines struggle with 3D data due to issues like inconsistent or missing annotations, and the inherent complexity of describing 3D shapes with words alone. The authors recognized the need for a "Google for 3D models" that leverages the visual and geometric properties of the models themselves for searching.

Methods

The core of their contribution lies in a new spherical harmonics shape descriptor. This method decomposes a 3D model into functions defined on concentric spheres and uses spherical harmonics to create a rotation-invariant representation. This descriptor is:

  • Discriminating: It captures fine details of shapes.
  • Robust: It's less sensitive to model degeneracies and doesn't require a canonical coordinate system or alignment of principal axes, which they found problematic in prior methods.
  • Efficient: It's fast to compute and allows for efficient indexing and searching.

They also developed intuitive query interfaces:

  • 3D Sketching: Using tools like Teddy, users can draw rough 3D shapes.
  • 2D Sketching: Users can draw 2D projections (front, side, top views) of objects.
  • Text Keywords: Standard keyword search is also supported.
  • Multimodal Queries: Combining text and sketches for more precise searches.

The system architecture involves offline crawling and indexing, followed by online querying and matching.

Datasets

The authors used a database of 17,834 VRML models downloaded from the web, augmented with 2,873 commercial models from vendors. For experimental evaluation, they specifically used a test database of 1890 "household" and "miscellaneous" objects provided by Viewpoint, which was annotated with descriptive keywords and clustered into 85 classes based on functional similarities.

Key Insights and Ideas

  • Shape is Crucial for 3D Search: Text alone is often insufficient for precise 3D model retrieval, especially for distinguishing between similar objects. Shape provides a complementary and often more powerful way to describe and find models.
  • Spherical Harmonics Shine: Their novel spherical harmonics descriptor significantly outperforms existing methods (Moments, EGI, Shape Histograms, D2 Shape Distributions) in precision and recall, particularly for classes with inconsistent principal axes.
  • User-Friendly Interfaces Matter: Simple, intuitive interfaces like 2D sketching are essential for broad adoption, even if they initially seem less powerful than 3D modeling tools.
  • Multimodal Search is Powerful: Combining text and shape queries leads to better results than either modality alone, allowing users to refine searches effectively.
  • Iterative Refinement is Key: Allowing users to iteratively refine searches by finding similar shapes significantly improves the efficiency and success rate of finding target objects.

Key Results

  • The spherical harmonics descriptor achieved 46-245% better performance (higher precision) compared to competing shape matching methods in precision-recall experiments.
  • The search engine can return query results from a repository of 20,000 models in under a second.
  • In experiments, combining text and 2D sketches resulted in better matches than using either alone, with the combination often yielding the best median ranks and highest percentage of results in the top 16.
  • Iterative searches using shape similarity were more effective than text-only iteration, leading to finding target objects in fewer iterations and less time.

Limitations and Future Work

  • 2D Sketching Limitations: The current 2D image matching method struggles with sketches that include interior details or texture, as it primarily focuses on boundary outlines. Future work could involve better image matching algorithms or providing users with more guidance on sketching.
  • New Query Interfaces: The authors suggest exploring constraint-based descriptions for queries, which could offer a more compact way to describe parameterized object classes.
  • Partial Object Matching: The current system matches whole objects. Future work could extend this to matching partial objects, enabling searches like finding a car within a city scene.
  • Integrating Other Attributes: Future matching algorithms could consider other 3D model attributes like color, texture, and animations.
  • Interactive Modeling Tools: Integrating shape-based matching into interactive sketching tools could revolutionize 3D model synthesis by allowing users to sketch rough ideas and have the system fill in details.
  • Broader Applications: The authors believe their shape-based query and indexing methods could be valuable in other domains like mechanical CAD, medicine, and molecular biology.

Summary updated

BibTeX
@article{funkhouser2003search,
  author = {Thomas A. Funkhouser and Patrick Min and Michael M. Kazhdan and Joyce Chen and J. Alex Halderman and David P. Dobkin and David Pokrass Jacobs},
  title = {{A search engine for 3D models}},
  journal = {ACM Trans. Graphics},
  year = {2003},
  doi = {10.1145/588272.588279},
}
Figure