3D SEARCHING

 

Advances in computing power combined with interactive modeling software, which lets users create images as queries for searches have made 3Dsearch technology possible. The methodology used involves the following steps

" Query formulation

" Search process

" Search result

 QUERY FORMULATION

True 3D search systems offer two principal ways to formulate a query: Users can select objects from a catalog of images based on product groupings, such as gears or sofas; or they can utilize a drawing program to create a picture of the object they are looking for. or example, Princeton's 3D search engine uses an application to let users draw a 2D or b of the object they want to find.

The above picture shows the query interface of a 3D search system.

 SEARCH PROCESS

The 3D-search system uses algorithms to convert the selected or drawn image-based query into a a mathematical model that describes the features of the object being sought. This converts drawings and objects into a form that computers can work with. The search the system then compares the mathematical description of the drawn or selected object to those of 3D objects stored in a database, looking for similarities in the described features.

The key to the way computer programs look for 3D objects is the voxel (volume pixel). A voxel is a set of graphical data-such as position, color, and density-that defines the smallest cube-shaped building block of a 3D image. Computers can display 3D images only in two dimensions. To do this, 3D rendering software takes an object and slices it into 2D cross-sections. The cross-sections consist of pixels (picture elements), which are single points in a 2D image. To render the 3D image on a 2D screen, the computer determines how to display the 2D cross-sections stacked on top of each other, using the applicable interpixel and interslice distances to position them properly. The computer interpolates data to fill in interslice gaps and create a solid image.

Overview of System

The organization of our system is shown in Execution proceeds in four steps: crawling, indexing, querying and matching. The first two steps are performed off-line, while the last two are done for each user query. The following text provides an overview of each step and highlights its main features:

1) Crawling: We build a database of 3D models by crawling the Web. 3D data still represents a very small percentage of the Web, and high-quality models represent an equally small percentage of all 3D data. So, we have developed a focused crawler that incorporates a measure of 3D model “quality” into its page rank. Using this crawler, we have downloaded 17,834 VRML models from the Web. We augment this database with 2,873 commercial models provided by 3D vendors.

2) Indexing: We compute indices to retrieve 3D models efficiently based on text and shape queries. In particular, we have developed a new 3D shape descriptor based on spherical harmonics that is descriptive, concise, efficient to compute, robust to model degeneracies, and invariant to rotations.

3) Querying: We allow a user to search interactively for 3D models. Our system supports query methods based on text keywords, 2D sketching, 3D sketching, model matching, and iterative refinement. We find that methods based on both text and shape combine to produce better results than either one alone.

System Organization

4) Matching: For each user query, our web server uses its index to return the sixteen 3D models that best match the query. Our method answers 3D shape queries in less than a quarter of a second for our repository; and, in practice, it scales sub-linearly with the number of indexed models. The main research issue at the heart of this system is how to provide shape-based query interfaces and matching methods that enable easy and efficient retrieval of 3D models from a large repository. In the following two sections, we discuss these issues in detail for different query interfaces.

 

Sketch Query Of course, shape similarity queries are only possible when the user already has a representative 3D model. In some cases, he will be able to find one by using a text search. However, in other cases, he will have to create it from scratch (at least to seed the search). An interesting open question then is “What type of modeling tool should be used to create shapes for 3D retrieval queries?”. This question is quite different than the one asked in traditional geometric modeling research. Rather than providing a tool with which a trained user can create models with exquisite detail and/or smoothness properties, our goal is to allow novice users to specify coarse 3D shapes quickly. In particular, the interface should be easy to learn for first-time visitors to a website. Of course, this requirement rules out almost every 3D modeling tool available today.

Text Query Our system also supports searching for 3D models by matching keywords in their textual descriptions. To support this feature, we construct a representative document for each 3D model. The text in that document includes the model filename, the anchor and nearby text parsed from its referring Web page, and ASCII labels parsed from inside the model file. Each document is preprocessed by removing common words (stop words) that don’t carry much-discriminating information, such as “and”, “or”, “my”, etc. We use the SMART system’s stop list of 524 common words as well as words specific to our domain (e.g. “jpg”, “www”, “transform”, etc.). Next, the text is stemmed (normalized by removing inflectional changes) using the Porter stemmer. Finally, synonyms of the filename (without the extension) are added using Word-Net.

 

Multi-Model Query Since text and shape queries can provide orthogonal notions of similarity corresponding to function and form, our search engine allows them to be combined. We support this feature in two ways. First, text keywords and 2D/3D sketches may be entered in a single multimodal query. Second, text and shape information entered in successive queries can be combined so that a user can refine search terms adaptively.

 

New modeling tools: future 3D modeling systems should consider integrating shape based matching and retrieval methods into interactive sketching tools. For instance, consider a 3D model synthesis paradigm in which a user draws a rough sketch of a desired 3D model and the system “fills in the details” semi -automatically by suggesting matching detailed parts retrieved from a large database. In such a paradigm, the user could retain much of the creative control over model synthesis, while the system performs most of the tedious tasks required for providing model detail.