# A New 3D Model Retrieval Method with Building Blocks

Authors: Mingquan Zhou; Qingsong Huo; Guohua Geng; Xiaojing Liu
Journal: International Journal of Computer Games Technology
 (2009)

---

## Abstract

As the numbers of 3D models available grow in many application fields, there is an increasing need for a search method to help people find them. Unfortunately, traditional search techniques are not always effective for 3D data. In this paper, we describe a novel method of interactive 3D model retrieval with building blocks. First, by using a cube block as the baseblock in a 3D virtual space, we may construct the query model with human-computer interaction method. Then through retrieving the polygon model of the database generated by the voxel model, we may get retrieval results in real time. Experiments are conducted to evaluate the performance of the proposed method.


---

## Body

## 1. Introduction

With the developments of computer graphics and the progress in
multimedia hardware technologies, 3D models are emerging in many application
fields such as game, medicine, and molecular biology and are playing more
important role in multimedia  data types. 3D model has gradually become the fourth multimedia data type after voice, image, and video.
Consequently, achieving effective and  efficient content-based 3D model retrieval
has now become a hotspot in the research of multimedia information retrieval   [1].
How to search useful and
the same theme of the
models usefully and effectively has become the main goal of 3D model retrieval. In order to provide
users with a convenient way of search, a mature retrieval system should have a good interactive
performance.Compared with
images and other 2D media, 3D models contain more rich information. Therefore, 3D model of content-based
retrieval system generally has a variety of query approaches [2, 3].
Some ways to retrieve of a desired model from a large selection of 3D
shape models have already been proposed, for example, the text-based search method, 2D hand-drawn draft search method, 3D hand-drawn draft search method, the example of 3D models search method, and interactive retrieval of 3D shape
models using physical objects [4–9].Currently,
the text-based search method is popular. It only needs to enter the keyword, but a text description is often too
limited and incorrect. The most important thing is that we must artificially mark models
firstly, and it is not realistic
to the mass of the models data. 2D hand-drawn
draft search method is
to produce an effective 2D visual draft for retrieval, and Princeton University presents a draft manual mapping 2D retrieval
interface [5]. Pu and Ramani [10]  retrieve  by drawing images. Cao et al.  [11] and Fonseca et al.  [12] retrieve by drawing 2D sketch according to the query model provided by the users. Although
users can express their intentions by drawing 2D sketch, it improves the users' requirements. It is very difficult to transform
3D models into 2D images especially for the users who are beginners of studying
computer graphics and computer-aided design. In order to input 3D models, Igarashi et al.  [13] design a 3D sketching tool Teddy. Hou and Ramani  [14] draw 3D part models and retrieve by cluster rules. Compared to the draft drawn 2D sketch, it
has more difficulty and more restrictions for drawing 3D sketch. Moreover, the 3D sketching
tool is, arguably, hard to use especially for a person who does not have a
talent for painting or drawing. Examples of 3D models require users to retrieve
the first sample to provide a 3D model. Users can easily operate, but without a suitable 3D model as the retrieval example, it is very
difficult to carry on.Siegl et al.  [15] employ an interactive approach to teaching and retrieving by using mobile AR-kits. Ichida et al.  [16]  implement a query interface for retrieval of 3D
shape models with physical objects by using the ActiveCube system. The
appearance of the ActiveCube system is shown in Figure 1.Appearance of the ActiveCube system.
(a)(b)The query
model of interactive retrieval of 3D shape models using physical objects is constructed
by the users themselves, without converting into images or 3D drawing sketch. The retrieval
interface is very simple, and users may participate in the query process. But the retrieval method must use physical objects as the
media; otherwise, it is unable to carry on. Furthermore, it is restricted by only six surfaces
of the connection and the number of physical objects. The expression of models is very weak. Is
there a better retrieval way? This paper proposes a new 3D model retrieval method with building
blocks.The rest of the paper is organized as follows: 3D model retrieval method
with building blocks is introduced in Section2. Section 3 gives experimental
results to show the effectiveness with the proposed search method. Section 4 presents
the method of retrieval optimization. Finally, conclusions are given in Section
5.


## 2. 3D Model Retrieval Method with Building Blocks

Building
blocks is a common Children's toy. By a few simple building blocks, it combines various characters, animals,
bridges, houses, towers, and so on. This paper is inspired by the building blocks
in the game and structures a virtual environment in the computer. It constructs
3D query models by building
blocks, expresses the users' expression, and realizes 3D models retrieval.


## 2.1. Retrieval Method Introduction

As shown in Figure2, the retrieval
system sample points to 3D polygon models and builds voxel model database. Then users construct  the query online model. Finally the system makes similarity
computations and gets the query result by contrasting the query model with the models of  voxel model database.Figure 2
System flow chart.


## 2.2. Generating Voxel Model

We assume
that the entire 3D model is composed by the triangle meshT=(T1,T2,…,Tn).
A,B,C are the vertices. The vertex density or mesh density varies greatly. In order to effectively describe the
characteristics of 3D models, this paper samples points by subdividing triangle mesh.As shown in
Figure3, the triangle mesh (A,B,C) is to be subdivided, (B,C) is the longest side, and O3 is the midpoint of BC.
So the triangle mesh may be subdivided into two triangle meshes, and they are the triangle mesh (A,B,O3) and the triangle mesh (A,O3,C).
If the area of the triangle meshes
(A,B,O3) and (A,O3,C) is more than a threshold, we will continue subdividing the triangle
meshes
(A,B,O3) and (A,O3,C) as that of
the triangle mesh (A,B,C).
Iteration will not stop until the area of the subdivided triangle mesh is less
than the threshold T.
We call the center of  the subdivided triangle
mesh as the sampling points of the 3D model. In Figure 3, P1, P2, P3,
and P4
are sampling points. And all the sampling points of triangle meshes
constitute voxel model of polygon model. Figure 4(a)  is a chair model, and Figure 4(b) is a voxel model of chair
model.Figure 3
Triangle mesh and sampling points.Model chair and its voxel model.
(a)(b)


## 2.3. Construction of Query Model

This paper
uses a cube as the baseblock
of building blocks. We construct query model by building blocks with many baseblocks.
Construction interface is shown in Figure5. In the construction interface, each baseblock is expressed by a red cube.
The red cube has 6 surfaces, 8 angles, 22 sides, and 26 kinds of connections direction. We may build blocks in each
direction, and the yellow
translucent cube represents the next baseblock which will be built.Figure 5
Query model construction interface.The construction
process of query model is as follows.(1)
Click on any red block
in the interface, then we will see 26 semitransparent connected yellow baseblocks.(2)
When clicked, the
semitransparent baseblock becomes red baseblock.(3)
According to the
need of the constructing model, repeat (1), (2) and continue building blocks until we are satisfied. Through the
above process, we can get a satisfactory query model. Figures 6 and 7 are, respectively,
the constructing process of a plane model and a stool model.Figure 6
The constructing process of a plane model.Figure 7
The constructing process of a stool model.


## 2.4. Similarity Computations

We suppose
that the query model is constructed byn baseblocks according to the prior process, and
we describe the details of this similar calculation procedure in the following
set of steps.(1)
Bound the
query model constructed byn cube-blocks with bounding box, obtain the minimum size of its
bounding box, and denote with M.(2)
Pick one of polyhedral models, sample it with the method of   2.2, and obtain its voxel model and the
minimum size of its bounding box, denoting withN.(3)
Assume
that the  smallest boxM is segmented into a×b×c, and the smallest box N is  also
segmented into a×b×c. The
segmenting progress is shown in Figure 8.(4)
Assume
the number of points  of the voxel model is, respectively,P1,P2,…,Pn which fall into the baseblock. We compute the
total number of points which fall into the query model in accordance with  formula (1):(1)P'=∑i=1nPi,(2)Sim=P′P×100(%).(5)
Flip the smallest bounding box and repeat (3)–(5) until the six
flip manners are all processed. Receive maximumP'  and make similarity
computations in accordance with formula  (2).(6)
Repeat (2)–(5) operation until
the models of the database are all processed.(7)
According to high to low arrangement  order,  we will be able to get retrieval
results.Model of the split-sample map.
(a)(b)(c)


## 3. Experimental Results and Performance Evaluation

In this paper, the experimental data model is the
Princeton University 3D retrieval database PSB, which
contains a total of 1814 models.


## 3.1. Experimental Results

We construct the plane model
and stool as a query model with the method as described above. Their experimental results are shown in Figures9 and 10.Figure 9
The plane model experimental result.Figure 10
The stool model experimental result.


## 3.2. Performance Evaluation and Analysis

From Figures9 and 10 of the retrieval results, we can see that the plane
model retrieval result is better than that of the stool model. In order to
further test the accuracy of retrieval results, we use
recall rate (recall) and check rate (precision) to evaluate [17, 18]. The recall rate and the precision
rate are as follows:
(3)Recall=relevantcorrectlyretrievedAllrelevant,Precise=relevantcorrectlyretrievedAllretrieved.  According to the retrieval results of plane model and stool model, we first calculate their recall
rate and the precision rate and then draw precision-recall curve, as shown in Figure 11.Figure 11
Precision recall of the plane and the stool models.As can be seen from Figure11, the plane model precision
rate is far higher than that of the stool model. The precision rate of the stool is very low. How can we optimize the
results?


## 4. Retrieval Optimization

In order
to make retrieval results better, first of all, we use CPCA method [19, 20] to coordinate normalization
of the pretreatment for the model. Retrieve again and the new
result is shown in Figure 12.Figure 12
The new experimental result.Contrasting
Figure12 to Figure 10, we can see the
retrieval result clearly improved.To further contrast, we draw
the precision-recall curve of the stool model before and
after using the coordinate normalization, as shown in Figure13.Figure 13
Precision recall of stool model.As can be seen from Figure13, the retrieval accuracy has greatly improved after coordinate normalization.


## 5. Conclusion

In the analysis and comparison of 3D model retrieval
methods, we propose a new 3D model retrieval method with building
blocks. Without hardware supporting, we construct query models by
building blocks in the virtual environment.Compared with the previous retrieval methods, it is very easy to construct query models. Users can easily express their
intentions to query. The
retrieval method we provided opens up a 3D model of the new ideas retrieval
method, and it has a good retrieval performance at the same time.



---

*Source: 572030-2009-05-25.xml*