Graphics Reference
In-Depth Information
12. BEYOND GEOMETRY AND TOPOLOGY
12.2 QUALITATIVE ORGANIZATION OF COLLECTIONS OF
3D MODELS
An ever growing number of 3D models are produced and stored in online shape repositories (e.g.,
Trimble 3D warehouse, Turbosquid, see also section
13.2
). is demands techniques to organize
large, heterogeneous collections of 3D models, so as to understand their overall categorization and
summarize their content. e goal is to facilitate exploration and content search. Any organization
of these large collections must be built on a comparison method between the individual shapes,
and the success of the organization highly depends on how we choose the comparison strategy. e
key challenge is that shape can vary in different ways, and users may be interested in different types
of variations [
112
,
113
]. is is why a single measure is not likely to provide a good organization.
Moreover, the authors in [
106
] observe that
quantitative
measures may be unreliable, or at least
not informative enough, when the collections possess rich variation and highly dissimilar objects:
it is expected that a numerical distance between a table and a car is less informative than the
distance between two tables.
erefore, the idea in [
106
] is to use
qualitative
information derived from multiple quan-
titative measures. e so-called
quartets
are sought in the dataset, which are quadruplets of 3D
objects divided into two pairs. Each pair is made of two similar objects, which are clearly different
from the other pair (Figure
12.3
, left). Quartets incorporate several distance measures into qual-
itative, topological relations of closeness and separation between objects. ey are used to build
a so-called
categorization tree
, or
C-tree
, which organizes the collection so that 3D shapes reside
at the leaves, with the number of edge hops between them reflecting their degree of separation
(Figure
12.3
, middle). e C-tree must maintain the topological relations defined by quartets.
Given a 3D object
S
, the C-tree is used to partition all other objects in the collection into layers,
organized by their degree of separation around
S
(Figure
12.3
, right). is type of organization is
called the
Degree of Separation (DoS) chart
. e DoS enables the interactive exploration of shape
collections through a 2D display space. Once the user selects a query object among the leaves of
the C-tree, the rest of the objects are automatically repositioned to form a DoS chart around the
query: shapes close to the query in the C-tree will be located at the inner circles of the DoS chart,
thus giving the user an intuitive understanding of how the objects in the collection match with
the query.
From a technical standpoint, the main issues are defining reliable quartets and building the
C-tree out of them. e representation in Figure
12.4
(a) shows a quadruplet of objects
.a;b;c;d/
as the vertices of a square, with the six edges representing the distances between them, accord-
ing to different similarity metrics. A quadruplet is a candidate quartet if its four vertices remain
connected after removing the three edges corresponding to the largest distances; otherwise it is
discarded (Figure
12.4
(e)). en, the edge corresponding to the largest distance must be a bridge,
that is, its removal separates the four nodes into two pairs; otherwise, the quadruplet is discarded
again (Figure
12.4
(d)). ose candidate quartets (Figure
12.4
(b) and (c)) are further filtered by
imposing a threshold on the ratio of the remaining three edges, to ensure that there are well
Search WWH ::
Custom Search