Abstract: This paper describes the work that has been done during the first year of the 3-SHIRT project, which aims at developing innovative solutions in all the phases of content-based 3D shape retrieval, namely: shape analysis and segmentation, design of shape descriptors, shape indexing and matching, and evaluation.
Authors: U. Castellani, G.M. Cortelazzo, M. Cristani, E. Delponte, A. Fusiello, A. Giachetti, S. Mizzaro, F. Odone, E. Puppo, R. Scateni, P. Zanuttigh.
3-SHIRT: Three-Dimensional Shape Indexing and Retrieval Techniques.
EuroGraphics Italian Chapter 2008, 113-120.
Salerno, Italia, Luglio 2008
Abstract: Recent advances in acquisition and modelling techniques led to generating an exponentially increasing amount of 3D shapes available both over the Internet or in specific databases. While the number grows it becomes more and more difficult to keep an organized knowledge over the content of this repositories. It is commonly intended that in the near future 3D shapes and models will be indexed and searched using procedure and instruments mimicking the same operations performed on images while using algorithms, data structures and instruments peculiar to the domain. In this context it is thus important to have tools for automatic characterization of 3D shapes, and skeletons and partitions are the two most prominent ones among them. In this paper we will describe an experience of building some of this tools on the top of a popular and robust library for manipulating meshes (OpenMesh). The preliminary results we present are promising enough to let us expect that the sum of the tools will be a useful aid to improving indexing and retrieval of digital 3D objects. The work presented here is part of a larger project: Three-Dimensional Shape Indexing and Retrieval Techniques (3-SHIRT), in collaboration with the Universities of Genoa, Padua, Udine, and Verona.
Abstract: Understanding when a cloud of points in three-dimensional space can be, semantically, interpreted as a surface, and then being able to describe the surface, is an interesting problem in itself and an important task to tackle in several application fields. Finding a possible solution to the problem implies to answer to many typical questions about surface acquisition and mesh reconstruction: how one can build a metric telling whether a point in space belongs to the surface? Given data from 3D scanning devices, how can we tell apart (and eventually discard) points representing noise from signal? Can the reached insight be used to align point clouds coming from different acquisitions? Inside this framework, the present paper investigates the features of a new dimensional clustering algorithm. Unless standard clustering methods, the peculiarity of this algorithm is, using the local fractal dimension, to select subsets of lower dimensionality inside the global of dimension N. When applied to the study of discrete surfaces embedded in three dimensional space, the algorithm results to be robust and able to discriminate the surface as a subset of fractal dimension two, differentiating it from the background, even in the presence of an intense noise. The preliminary tests we performed, on points clouds generated from known surfaces, show that the recognition error is lower than 3 percent and does not affect the visual quality of the final result.
Abstract: A triangular mesh is the piecewise linear approximation of a sampled or analytical surface, when each patch is a triangle. The connectivity of the mesh can be easily represented using its dual graph. Each node of such a graph has at most three incident edges; if the surface is homeomorphic to a sphere, each node has exactly three incident edges. Several triangular meshes, representing the same surface, with an increasing number of triangles are a representation of the surface at different levels of detail (LOD). When the number of triangles from one LOD to another varies continuously we call such a structure a continuous level of detail (CLOD) approximation of the surface. Given a CLOD data structure we can extract, at each level, the mesh representing the surface and derive its dual graph. If we group the triangles forming each mesh in strips, to accelerate their rendering, we should use two colors for the dual graph’s edges to distinguish between the edges linking nodes belonging to the same strip or not. The main goal of this paper is to present a set of rules to recolor the dual graph of the mesh when passing from one LOD to the next and back. The operations used to change the mesh are a Vertex Split (VS) when the resolution increases, and an Edge Collapse (EC) when the resolution decreases. We can, then, use a local topological analysis to derive the rules allowing to recolor the graph, and to show that, under certain conditions, the recoloring is optimal. This allows to keep effectively an optimal triangle strip structure over the mesh, while changing its resolution.
Abstract: Triangle meshes are the most used representations for three-dimensional objects, and triangle strips are the organization of triangles mostly used for efficient rendering. Since the problem of optimal strip decomposition of a given mesh is NP-complete, many different heuristics have been proposed; the quality of the stripification is usually evaluated using standard indicators as the total number of strips, the number of isolated triangles, the cache coherence, the number of swap vertices. In this paper we present the Enhanced Tunnelling Algorithm (ETA), a stripification method working on the dual graph of a mesh. The method uses a sophisticated mechanism of dynamical update of identifiers, guided by a localization procedure. The algorithm adopts a modified search approach in the dual graph that accelerated the convergence speed of the algorithm. The ETA results efficient and robust, able to deal with datasets of any dimension. The quality of the stripification is remarkable: very few strips (not seldom just one), no isolated triangles, good cache coherence (ACMR value), good number of vertex per triangle.