1、Shape DistributionsROBERT OSADA, THOMAS FUNKHOUSER, BERNARD CHAZELLE, and DAVID DOBKINPrinceton University1. INTRODUCTION Determining the similarity between 3D shapes is a fundamental task in shape-based recognition, retrieval, clustering, and classification. Its main applications have traditionally
2、 been in computer vision,mechanical engineering, and molecular biology. However, due to three recent developments, we believe that 3D model databases will become ubiquitous, and the applications of 3D shape analysis and matching will expand into a wide variety of other fields. First, improved modeli
3、ng tools and scanning devices are making acquisition of 3D models easier and less expensive, creating a large supply of publically available 3D data sets (e.g., the Protein Data Bank Holm and Sander 1998). Second, the World Wide Web is enabling access to 3D models constructed by people all over the
4、world, providing a mechanism for widespread distribution of high quality 3D models (e.g., ). Finally, 3D graphics hardware and CPUs have become fast enough and cheap enough that 3D data can be processed and displayed quickly on desktop computers, leading to a high demand for 3D models from a wide ra
5、nge of sources.Unfortunately, since most 3D file formats (VRML, 3D Studio, etc.) have been designed for visualization, they contain only geometric and appearance attributes, and usually lack semantic information that would facilitate automatic matching. Although it is possible to include meaningful
6、structure and semantic tags in some 3D file formats (the “layer” field associated with entities in Auto Cad models is a simple example), the vast majority of 3D objects available via the World Wide Web will not have them, and there are few standards regarding their use. In general, 3D models will be
7、 acquired with scanning devices, or output from geometric manipulation tools (file format conversion programs), and thus they will have only geometric and appearance information, usually completely devoid of structure or semantic information. Automatic shape-based matching algorithms will be useful
8、for recognition,retrieval, clustering, and classification of 3D models in such databases.Databases of 3D models have several new and interesting characteristics that significantly affect shape-based matching algorithms. Unlike images and range scans, 3D models do not depend on the configuration of c
9、ameras, light sources, or surrounding objects (e.g., mirrors). As a result, they do not contain reflections, shadows, occlusions, projections, or partial objects. This greatly simplifies finding matches between objects of the same type. For example, it is plausible to expect that the 3D model of a h
10、orse contains exactly four legs of roughly equal size. In contrast, any 2D image of the same horse may contain fewer than four legs (if some of the legs are occluded by tall grass), or it may contain “extra legs” appearing as the result of shadows on the barn and/or reflections in a nearby pond, or
11、some of the legs may appear smaller than others due to perspective distortions. These problems are vexing for traditional computer vision applications, but generally absent from 3D model matching.In other respects, representing and processing 3D models is more complicated than for sampled multimedia
12、 data. The main difficulty is that 3D surfaces rarely have simple parameterizations. Since 3D surfaces can have arbitrary topologies, many useful methods for analyzing other media (e.g.,Fourier analysis) have no obvious analogs for 3D surface models. Moreover, the dimensionality is higher, which mak
13、es searches for pose registration, feature correspondences, and model parameters more difficult, while the likelihood of model degeneracies is higher. In particular, most 3D models in large databases, such as the World Wide Web, are represented by “polygon soups”unorganized and degenerate sets of po
14、lygons. They seldom have any topology or solid modeling information; they rarely are manifold; and most are not even self-consistent. We conjecture that almost every 3D computer graphics model available today contains missing, wrongly oriented, intersecting, disjoint, and/or overlapping polygons . A
15、s a few classic examples, the Utah teapot is missing its bottom and rim,and the Stanford Bunny Stanford University Graphic Laboratory 1996 has several holes along its base. The problem with these degenerate representations is that most interesting geometric features and shape signatures are difficul
16、t to compute, and many others are ill-defined (e.g., what is the volume of a teapot with no bottom?). Meanwhile, fixing the degeneracies in such 3D models to form a consistent solid region and manifold surface is a difficult problem Barequet and Kumar 1997;Gueziec et al. 1998; Murali and Funkhouser 1997, often requiring human intervention to resolve ambiguities.Conclusions Although fuzzy-PLC systems, integrating fuzzy logic with the PLC, d
