Polygon Mesh Repairing: an application perspective Marco Attene, Marcel Campen and Leif Kobbelt ACM Computing Surveys, Vol. 45, No. 2, Article 15 (33 pages), Feb 2013. Abstract
Nowadays, digital 3D models are in widespread and ubiquitous use, and each specific application dealing with 3D geometry has its own quality requirements that restrict the class of acceptable and supported models. This article analyzes typical defects that make a 3D model unsuitable for key application contexts, and surveys existing algorithms that process, repair, and improve its structure, geometry, and topology to make it appropriate to case-by-case requirements.
The analysis is focused on polygon meshes, which constitute by far the most common 3D object representation.
In particular, this article provides a structured overview of mesh repairing techniques from the point of view of the application context.
Different types of mesh defects are classified according to the upstream application that produced the mesh, whereas mesh quality requirements are grouped by representative sets of downstream applications where the mesh is to be used. The numerous mesh repair methods that have been proposed during the last two decades are analyzed and classified in terms of their capabilities, properties, and guarantees. Based on these classifications, guidelines can be derived to support the identification of repairing algorithms best-suited to bridge the compatibility gap between the quality provided by the upstream process and the quality required by the downstream applications in a given geometry processing scenario.
Download PDF (624 Kb) (c) ACM 2013. >>> Accompanying website |
Geometric Models with Weighted Topology Marco Attene and Silvia Biasotti Computers and Graphics, Vol. 35, No. 3, June 2011, Pages 542-548. Online version Abstract
This paper introduces the concept of weighted topology to model a 3D object whose connectivity and metric depend on a novel notion of weighted arc-length. The weighted arc-length between any two points of the shape takes into account the fact that a part of the object may be either weakly or strongly connected to another part. The new model is useful to treat problems which are intrinsically not robust to small topological changes. We describe an example implementation of the model and show how it can be exploited to (1) extend the applicability domain of existing segmentation algorithms and (2) improve the performances of a shape descriptor in a 3D object retrieval scenario. Download PDF (2.0 Mb) (c)Elsevier 2011. |
A lightweight approach to repairing digitized polygon meshes Marco Attene The Visual Computer, Vol. 26, N. 11, 1393-1406, 2010. Online version Abstract
When designing novel algorithms for geometric
processing and analysis, researchers often assume
that the input conforms to several requirements.
On the other hand, polygon meshes obtained from
acquisition of real-world objects typically exhibit several
defects, and thus are not appropriate for a widespread
exploitation.
In this paper, an algorithm is presented that strives
to convert a low-quality digitized polygon mesh to a
single manifold and watertight triangle mesh without
degenerate or intersecting elements. Differently from
most existing approaches that globally re-sample the
model to produce a fixed version, the algorithm presented
here attempts to modify the input mesh only
locally within the neighborhood of undesired configurations.
After having converted the input to a single combinatorial
manifold, the algorithm proceeds iteratively by
removing growing neighborhoods of undesired elements
and by patching the resulting surface gaps until
all the "defects" are removed. Though this heuristic
approach is not guaranteed to converge, it was
tested on more than 400 low-quality models and always
succeeded. Furthermore, with respect to similar
existing algorithms, it proved to be computationally
efficient and to produce more accurate results while
using fewer triangles.
Download PDF (1.5 Mb) (c) Springer 2010. >>> Download Software |
Characterization of 3D shape parts for semantic annotation Marco Attene, Francesco Robbiano, Michela Spagnuolo and Bianca Falcidieno Computer-Aided Design, Vol. 41, No. 10, pp. 756-763, 2009. Online version. Abstract
3D content stored in big databases or shared on the Internet is a precious resource for several applications,
but unfortunately it risks being underexploited due to the difficulty of retrieving it efficiently.
In this paper we describe a system called the ShapeAnnotator through which it is possible to perform non-trivial
segmentations of 3D surface meshes and annotate the detected parts through concepts expressed by an ontology.
Each part is connected to an instance that can be stored in a knowledge base to ease the retrieval process based on semantics.
Through an intuitive interface, users create such instances by simply selecting proper classes in the ontology; attributes
and relations with other instances can be computed automatically based on a customizable analysis of the underlying topology
and geometry of the parts. We show how our part-based annotation framework can be used in two scenarios, namely for the
creation of avatars in emerging Internet-based virtual worlds, and for product design in e-manufacturing.
Download PDF (2.0 Mb) (c) Elsevier 2009. >>> ShapeAnnotator Web Page |
Hierarchical Convex Approximation of 3D Shapes for Fast Region Selection Marco Attene, Michela Mortara, Michela Spagnuolo and Bianca Falcidieno Computer Graphics Forum, Vol. 27, No. 5, pp. 1323-1333, 2008. Abstract
Given a 3D solid model S represented by a tetrahedral mesh, we describe a novel algorithm to compute a hierarchy
of convex polyhedra that tightly enclose S. The hierarchy can be browsed at interactive speed on a modern PC
and it is useful for implementing an intuitive feature selection paradigm for 3D editing environments.
Convex parts often coincide with perceptually relevant shape components and, for their identification, existing methods rely on the boundary surface only. In contrast, we show that the notion of part concavity can be expressed and implemented more intuitively and efficiently by exploiting a tetrahedrization of the shape volume. The method proposed is completely automatic, and generates a tree of convex polyhedra in which the root is the convex hull of the whole shape, and the leaves are the tetrahedra of the input mesh. The algorithm proceeds bottomup by hierarchically clustering tetrahedra into nearly convex aggregations, and the whole process is significantly fast. We prove that, in the average case, for a mesh of n tetrahedra O(n log^2 n) operations are sufficient to compute the whole tree. Download PDF (PDF 13.2 Mb) (c) EUROGRAPHCS / Blackwell Publishing. |
Hierarchical Mesh Segmentation based on Fitting Primitives Marco Attene, Bianca Falcidieno and Michela Spagnuolo The Visual Computer 22(3): 181-193, 2006. Abstract
In this paper we describe a
hierarchical face clustering algorithm for triangle meshes based on
fitting primitives belonging to an arbitrary set. The method proposed is
completely automatic, and generates a binary tree of clusters, each of
which fitted by one of the primitives employed. Initially, each triangle
represents a single cluster; at every iteration, all the pairs of adjacent
clusters are considered, and the one that can be better approximated by
one of the primitives forms a new single cluster. The approximation error
is evaluated using the same metric for all the primitives, so that it
makes sense to choose which is the most suitable primitive to
approximate the set of triangles in a cluster.
Based on this approach, we
implemented a prototype which uses planes, spheres and cylinders, and have
experimented that for meshes made of 100k faces, the whole binary tree of
clusters can be built in about 8 seconds on a standard PC.
The framework here described has
natural application in reverse engineering processes, but it has been also
tested for surface de-nosing, feature recovery and character
skinning.
Download PDF (2.0 Mb) (c) Springer 2006. >>> Download Software |
Sharpen&Bend: Recovering curved sharp edges in triangle meshes produced by feature-insensitive sampling Marco Attene, Bianca Falcidieno, Jarek Rossignac and Michela Spagnuolo IEEE Transactions on Visualization and Computer Graphics, 11(2): pp. 181-192, 2005. Abstract
Various acquisition, analysis, visualization and compression
approaches sample surfaces of 3D shapes in a uniform fashion, without any
attempt to align the samples with sharp edges or to adapt the sampling
density to the surface curvature. Consequently, triangle meshes that
interpolate these samples usually chamfer sharp features and exhibit a
relatively large error in their vicinity. We present two new filters that
improve the quality of these re-sampled models. EdgeSharpener
restores the sharp edges by splitting the chamfer edges and forcing the
new vertices to lie on intersections of planes extending the smooth
surfaces incident upon these chamfers. Bender refines the resulting
triangle mesh using an interpolating subdivision scheme that preserves the
sharpness of the recovered sharp edges while bending their polyline
approximations into smooth curves. A combined Sharpen&Bend
post-processing significantly reduces the error produced by
feature-insensitive sampling processes. For example, we have observed that
the mean-squared distortion introduced by the SwingWrapper remeshing-based
compressor can often be reduced by 80% executing EdgeSharpener alone after
decompression. For models with curved regions, this error may be further
reduced by an additional 60% if we follow the EdgeSharpening phase by
Bender.
Download PDF (2.38 Mb) (c) IEEE 2005. |
SwingWrapper: Retiling Triangle Meshes for Better EdgeBreaker Compression Marco Attene, Bianca Falcidieno, Michela Spagnuolo and Jarek Rossignac ACM Transactions on Graphics, 22(4): pp. 982-996, 2003. Abstract
We focus on
the lossy compression of manifold triangle meshes. Our SwingWrapper
approach partitions the surface of an original mesh M into simply
connected regions, called triangloids. From these, we generate a new mesh
M'. Each triangle of M' is an approximation of a triangloid of M. By
construction, the connectivity of M' is fairly regular and can be
compressed to less than a bit per triangle using EdgeBreaker or one of the
other recently developed schemes. The locations of the vertices of M' are
compactly encoded with our new prediction technique, which uses a single
correction parameter per vertex. SwingWrapper strives to reach a
user-defined output file size rather than to guarantee a given error
bound. For a variety of popular models, a rate of 0.4 bits/triangle yields
an L2 distortion of about 0.01% of the bounding box diagonal. The proposed
solution may also be used to encode crude meshes for adaptive transmission
or for controlling subdivision surfaces.
Download PDF (777 Kb) (c) ACM 2003. |