Methods, systems, and data structures for performing searches on three dimensional objects

• US 8,429,174 B2
• Filed: 01/23/2004
• Issued: 04/23/2013
• Est. Priority Date: 01/25/2003
• Status: Active Grant

• Current Assignee: Purdue Research Foundation (The Trustees of Purdue University (d/b/a Purdue University))
• Original Assignee: Purdue Research Foundation (The Trustees of Purdue University (d/b/a Purdue University))
• Inventors: Ramani, Karthik, Iyer, Natraj, Lou, Kuiyang, Jayanti, Subramaniam
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Chau, Dung K
• Application Number:
  US10/763,741
• Publication Number:
  US 20040249809A1
• Time in Patent Office: 3,378 Days
• Field of Search: None
• US Class Current: 707/749
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 2111/02 CAD in a network environment, e.g. collaborative CAD or distributed simulation
• CPC Class Codes: G06F 2111/20 Configuration CAD, e.g. designing by assembling or positioning modules selected from libraries of predesigned modules
• CPC Class Codes: G06F 2119/20 Design reuse, reusability analysis or reusability optimisation
• CPC Class Codes: G06F 30/10 Geometric CAD
• CPC Class Codes: G06F 30/27 using machine learning, e.g. artificial intelligence, neural networks, support vector machines [SVM] or training a model
• CPC Class Codes: G06V 10/34 Smoothing or thinning of the pattern; Morphological operations; Skeletonisation
• CPC Class Codes: G06V 20/64 Three-dimensional objects
• CPC Class Codes: G06V 30/1988 Graph matching graphical image representation G06V30/18181

Abstract

Techniques are provided for searching on three dimensional (3D) objects across large, distributed repositories of 3D models. 3D shapes are created for input to a search system; optionally user-defined similarity criterion is used, and search results are interactively navigated and feedback received for modifying the accuracy of the search results. Search input can also be given by picking 3D models from a cluster map or by providing the orthographic views for the 3D model. Feedback can be given by a searcher as to which models are similar and which are not. Various techniques adjust the search results according to the feedback given by the searcher and present the new search results to the searcher.

Claims

1. A method for searching, comprising:

receiving a three dimensional object;

searching one or more data stores with the three dimensional object as a first search query;

presenting results from the search, wherein the results include an answer set;

dynamically receiving modifications for one or more items in the answer set; and

re-searching the one or more data stores with the modifications associated with the one or more items as a second search query.

2. The method of claim 1 further comprising, converting the three dimensional object into a graph skeleton defining a graph data structure, wherein the graph data structure is the first search query.

3. The method of claim 1 wherein the receiving the three dimensional object further includes interactively permitting the three dimensional object to be sketched.

4. The method of claim 1 wherein the receiving the three dimensional object further includes presenting a list of three dimensional models and permitting the three dimensional object to be formed from selective ones of the list of three dimensional models.

5. The method of claim 1 wherein the presenting the results further include grouping selective portions of the one or more items in the answer set into related clusters.

6. The method of claim 5 further comprising, selecting a cluster to allow further browsing within that selected cluster.

7. The method of claim 1 further comprising, receiving one or more filters which constrain the first or second search queries.

8. The method of claim 7, wherein one said filter comprises a total volume filter.

9. The method of claim 1 wherein the re-searching further includes identifying in the modifications for the one or more items information that identifies selective ones of the items that are more relevant to the first search query than selective other ones of the items.

10. A method of searching, comprising:

receiving a two dimensional object;

mapping the two dimensional object to a three dimensional representation;

searching one or more data stores with the three dimensional representation as a first search query; and

presenting one or more items in an answer set that is responsive to the first search query of the one or more data stores.

11. The method of claim 10 wherein the mapping further includes:

representing the two dimensional object as a two dimensional skeleton;

converting the two dimensional skeleton into a three dimensional skeleton; and

representing the three dimensional skeleton as a three dimensional graph structure, wherein the three dimensional graph structure is used as the first search query.

12. The method of claim 10 further comprising:

receiving relevance indications for a selective number of the one or more items in the answer set; and

searching the one or more data stores with the selective number of the one or more items and the relevance indications as a second search query.

13. The method of claim 12 retaining the relevance indications as preferences for subsequent search queries received and processed, where the retained relevance indications are used as filters to subsequent first queries.

14. The method of claim 10 further comprising organizing the answer set as a plurality of related clusters, wherein each related cluster includes a selective number of the one or more items.

15. The method of claim 10 wherein the mapping further includes:

converting the two dimensional object into a two dimensional skeleton;

generating candidate three dimensional vertices for each of two dimensions of the two dimensional skeleton;

generating candidate three dimensional edges from the candidate three dimensional vertices;

creating candidate three dimensional faces from the three dimensional edges on a same surface;

creating one or more three dimensional objects from the candidate three dimensional faces; and

associating the one or more three dimensional objects with the received two dimensional object as the three dimensional skeleton.