SGP06: Eurographics Symposium on Geometry Processing

Permanent URI for this collection

https://diglib.eg.org/handle/10.2312/441

Browse

Now showing 1 - 20 of 26

Partial Matching of 3D Shapes with Priority-Driven Search
(The Eurographics Association, 2006) Funkhouser, T.; Shilane, P.; Alla Sheffer and Konrad Polthier
Priority-driven search is an algorithm for retrieving similar shapes from a large database of 3D objects. Given a query object and a database of target objects, all represented by sets of local 3D shape features, the algorithm produces a ranked list of the c best target objects sorted by how well any subset of k features on the query match features on the target object. To achieve this goal, the system maintains a priority queue of potential sets of feature correspondences (partial matches) sorted by a cost function accounting for both feature dissimilarity and the geometric deformation. Only partial matches that can possibly lead to the best full match are popped off the queue, and thus the system is able to find a provably optimal match while investigating only a small subset of potential matches. New methods based on feature distinction, feature correspondences at multiple scales, and feature difference ranking further improve search time and retrieval performance. In experiments with the Princeton Shape Benchmark, the algorithm provides significantly better classification rates than previously tested shape matching methods while returning the best matches in a few seconds per query.
Loop Subdivision with Curvature Control
(The Eurographics Association, 2006) Ginkel, I.; Umlauf, G.; Alla Sheffer and Konrad Polthier
In this paper the problem of curvature behavior around extraordinary points of a Loop subdivision surface is addressed. A variant of Loop s algorithm with small stencils is used that generates surfaces with bounded curvature and prescribed elliptic or hyperbolic behavior. We present two different techniques that avoid the occurrence of hybrid configurations, so that an elliptic or hyperbolic shape can be guaranteed. The first technique uses a symmetric modification of the initial control-net to avoid hybrid shapes in the vicinity of an extraordinary point. To keep the difference between the original and the modified mesh as small as possible the changes are formulated as correction stencils and spread to a finite number of subdivision steps. The second technique is based on local optimization in the frequency domain. It provides more degrees of freedom and so more control over the global shape.
Nonobtuse Remeshing and Mesh Decimation
(The Eurographics Association, 2006) Li, J. Y. S.; Zhang, H.; Alla Sheffer and Konrad Polthier
Quality meshing in 2D and 3D domains is an important problem in geometric modeling and scientific computing. We are concerned with triangle meshes having only nonobtuse angles. Specifically, we propose a solution for guaranteed nonobtuse remeshing and nonobtuse mesh decimation. Our strategy for the remeshing problem is to first convert an input mesh, using a modified Marching Cubes algorithm, into a rough approximate mesh that is guaranteed to be nonobtuse. We then apply iterative "deform-to-fit" via constrained optimization to obtain a high-quality approximation, where the search space is restricted to be the set of nonobtuse meshes having a fixed connectivity. With a detailed nonobtuse mesh in hand, we apply constrained optimization again, driven by a quadric-based error, to obtain a hierarchy of nonobtuse meshes via mesh decimation.
A Decomposition-based Representation for 3D Simplicial Complexes
(The Eurographics Association, 2006) Hui, Annie; Vaczlavik, Lucas; Floriani, Leila De; Alla Sheffer and Konrad Polthier
We define a new representation for non-manifold 3D shapes described by three-dimensional simplicial complexes, that we call the Double-Level Decomposition (DLD) data structure. The DLD data structure is based on a unique decomposition of the simplicial complex into nearly manifold parts, and encodes the decomposition in an efficient and powerful two-level representation. It is compact, and it supports efficient topological navigation through adjacencies. It also provides a suitable basis for geometric reasoning on non-manifold shapes. We describe an algorithm to decompose a 3D simplicial complex into nearly manifold parts. We discuss how to build the DLD data structure from a description of a 3D complex as a collection of tetrahedra, dangling triangles and wire edges, and we present algorithms for topological navigation. We present a thorough comparison with existing representations for 3D simplicial complexes.
Rectangular Multi-Chart Geometry Images
(The Eurographics Association, 2006) Carr, Nathan A.; Hoberock, Jared; Crane, Keenan; Hart, John C.; Alla Sheffer and Konrad Polthier
Many mesh parameterization algorithms have focused on minimizing distortion and utilizing texture area, but few have addressed issues related to processing a signal on the mesh surface.We present an algorithm which partitions a mesh into rectangular charts while preserving a one-to-one texel correspondence across chart boundaries. This mapping permits any computation on the mesh surface which is typically carried out on a regular grid, and prevents seams by ensuring resolution continuity along the boundary. These features are also useful for traditional texture applications such as surface painting where continuity is important. Distortion is comparable to other parameterization schemes, and the rectangular charts yield efficient packing into a texture atlas. We apply this parameterization to texture synthesis, fluid simulation, mesh processing and storage, and locating geodesics.
Robust Reconstruction of Watertight 3D Models from Non-uniformly Sampled Point Clouds Without Normal Information
(The Eurographics Association, 2006) Hornung, Alexander; Kobbelt, Leif; Alla Sheffer and Konrad Polthier
We present a new volumetric method for reconstructing watertight triangle meshes from arbitrary, unoriented point clouds. While previous techniques usually reconstruct surfaces as the zero level-set of a signed distance function, our method uses an unsigned distance function and hence does not require any information about the local surface orientation. Our algorithm estimates local surface confidence values within a dilated crust around the input samples. The surface which maximizes the global confidence is then extracted by computing the minimum cut of a weighted spatial graph structure. We present an algorithm, which efficiently converts this cut into a closed, manifold triangle mesh with a minimal number of vertices. The use of an unsigned distance function avoids the topological noise artifacts caused by misalignment of 3D scans, which are common to most volumetric reconstruction techniques. Due to a hierarchical approach our method efficiently produces solid models of low genus even for noisy and highly irregular data containing large holes, without loosing fine details in densely sampled regions. We show several examples for different application settings such as model generation from raw laser-scanned data, image-based 3D reconstruction, and mesh repair.
Selectively Refinable Subdivision Meshes
(The Eurographics Association, 2006) Puppo, Enrico; Alla Sheffer and Konrad Polthier
We introduce RGB triangulations, an extension of red-green triangulations that can support selective refinement over subdivision meshes generated through quadrisection of triangles. Our purpose is to define a mechanism based on local operators that act on subdivision meshes while supporting operations similar to those available in Continuous Level Of Detail models. Our mechanism permits to take an adaptive mesh at intermediate level of subdivision and process it through both refinement and coarsening operations, by remaining consistent with an underlying Loop subdivision scheme. Our method does not require any hierarchical data structure, being based just on color codes and level numbers assigned to elements of a mesh, which can be encoded in a standard topological data structure with a small overhead.
Poisson Surface Reconstruction
(The Eurographics Association, 2006) Kazhdan, Michael; Bolitho, Matthew; Hoppe, Hugues; Alla Sheffer and Konrad Polthier
We show that surface reconstruction from oriented points can be cast as a spatial Poisson problem. This Poisson formulation considers all the points at once, without resorting to heuristic spatial partitioning or blending, and is therefore highly resilient to data noise. Unlike radial basis function schemes, our Poisson approach allows a hierarchy of locally supported basis functions, and therefore the solution reduces to a well conditioned sparse linear system. We describe a spatially adaptive multiscale algorithm whose time and space complexities are proportional to the size of the reconstructed model. Experimenting with publicly available scan data, we demonstrate reconstruction of surfaces with greater detail than previously achievable.
Spherical Barycentric Coordinates
(The Eurographics Association, 2006) Langer, Torsten; Belyaev, Alexander; Seidel, Hans-Peter; Alla Sheffer and Konrad Polthier
We develop spherical barycentric coordinates. Analogous to classical, planar barycentric coordinates that describe the positions of points in a plane with respect to the vertices of a given planar polygon, spherical barycentric coordinates describe the positions of points on a sphere with respect to the vertices of a given spherical polygon. In particular, we introduce spherical mean value coordinates that inherit many good properties of their planar counterparts. Furthermore, we present a construction that gives a simple and intuitive geometric interpretation for classical barycentric coordinates, like Wachspress coordinates, mean value coordinates, and discrete harmonic coordinates. One of the most interesting consequences is the possibility to construct mean value coordinates for arbitrary polygonal meshes. So far, this was only possible for triangular meshes. Furthermore, spherical barycentric coordinates can be used for all applications where only planar barycentric coordinates were available up to now. They include Bézier surfaces, parameterization, free-form deformations, and interpolation of rotations.
Overfitting Control for Surface Reconstruction
(The Eurographics Association, 2006) Lee, Yunjin; Lee, Seungyong; Ivrissimtzis, Ioannis; Seidel, Hans-Peter; Alla Sheffer and Konrad Polthier
This paper proposes a general framework for overfitting control in surface reconstruction from noisy point data. The problem we deal with is how to create a model that will capture as much detail as possible and simultaneously avoid reproducing the noise of the input points. The proposed framework is based on extra-sample validation. It is fully automatic and can work in conjunction with any surface reconstruction algorithm. We test the framework with a Radial Basis Function algorithm, Multi-level Partition of Unity implicits, and the Power Crust algorithm.
PriMo: Coupled Prisms for Intuitive Surface Modeling
(The Eurographics Association, 2006) Botsch, Mario; Pauly, Mark; Gross, Markus; Kobbelt, Leif; Alla Sheffer and Konrad Polthier
We present a new method for 3D shape modeling that achieves intuitive and robust deformations by emulating physically plausible surface behavior inspired by thin shells and plates. The surface mesh is embedded in a layer of volumetric prisms, which are coupled through non-linear, elastic forces. To deform the mesh, prisms are rigidly transformed to satisfy user constraints while minimizing the elastic energy. The rigidity of the prisms prevents degenerations even under extreme deformations, making the method numerically stable. For the underlying geometric optimization we employ both local and global shape matching techniques. Our modeling framework allows for the specification of various geometrically intuitive parameters that provide control over the physical surface behavior. While computationally more involved than previous methods, our approach significantly improves robustness and simplifies user interaction for large, complex deformations.
Defining and Computing Curve-skeletons with Medial Geodesic Function
(The Eurographics Association, 2006) Dey, Tamal K.; Sun, Jian; Alla Sheffer and Konrad Polthier
Many applications in geometric modeling, computer graphics, visualization and computer vision benefit from a reduced representation called curve-skeletons of a shape. These are curves possibly with branches which compactly represent the shape geometry and topology. The lack of a proper mathematical definition has been a bottleneck in developing and applying the the curve-skeletons. A set of desirable properties of these skeletons has been identified and the existing algorithms try to satisfy these properties mainly through a procedural definition. We define a function called medial geodesic on the medial axis which leads to a methematical definition and an approximation algorithm for curve-skeletons. Empirical study shows that the algorithm is robust against noise, operates well with a single user parameter, and produces curve-skeletons with the desirable properties. Moreover, the curveskeletons can be associated with additional attributes that follow naturally from the definition. These attributes capture shape eccentricity, a local measure of how far a shape is away from a tubular one.
Probabilistic Fingerprints for Shapes
(The Eurographics Association, 2006) Mitra, Niloy J.; Guibas, Leonidas; Giesen, Joachim; Pauly, Mark; Alla Sheffer and Konrad Polthier
We propose a new probabilistic framework for the efficient estimation of similarity between 3D shapes. Our framework is based on local shape signatures and is designed to allow for quick pruning of dissimilar shapes, while guaranteeing not to miss any shape with significant similarities to the query model in shape database retrieval applications. Since directly evaluating 3D similarity for large collections of signatures on shapes is expensive and impractical, we propose a suitable but compact approximation based on probabilistic fingerprints which are computed from the shape signatures using Rabin s hashing scheme and a small set of random permutations. We provide a probabilistic analysis that shows that while the preprocessing time depends on the complexity of the model, the fingerprint size and hence the query time depends only on the desired confidence in our estimated similarity. Our method is robust to noise, invariant to rigid transforms, handles articulated deformations, and effectively detects partial matches. In addition, it provides important hints about correspondences across shapes which can then significantly benefit other algorithms that explicitly align the models. We demonstrate the utility of our method on a wide variety of geometry processing applications.
Error Bounds and Optimal Neighborhoods for MLS Approximation
(The Eurographics Association, 2006) Lipman, Yaron; Cohen-Or, Daniel; Levin, David; Alla Sheffer and Konrad Polthier
In recent years, the moving least-square (MLS) method has been extensively studied for approximation and reconstruction of surfaces. The MLS method involves local weighted least-squares polynomial approximations, using a fast decaying weight function. The local approximating polynomial may be used for approximating the underlying function or its derivatives. In this paper we consider locally supported weight functions, and we address the problem of the optimal choice of the support size. We introduce an error formula for the MLS approximation process which leads us to developing two tools: One is a tight error bound independent of the data. The second is a data dependent approximation to the error function of the MLS approximation. Furthermore, we provide a generalization to the above in the presence of noise. Based on the above bounds, we develop an algorithm to select an optimal support size of the weight function for the MLS procedure. Several applications such as differential quantities estimation and up-sampling of point clouds are presented. We demonstrate by experiments that our approach outperforms the heuristic choice of support size in approximation quality and stabilit
On Transfinite Barycentric Coordinates
(The Eurographics Association, 2006) Belyaev, Alexander; Alla Sheffer and Konrad Polthier
A general construction of transfinite barycentric coordinates is obtained as a simple and natural generalization of Floater's mean value coordinates [Flo03, JSW05b]. The Gordon-Wixom interpolation scheme [GW74] and transfinite counterparts of discrete harmonic and Wachspress-Warren coordinates are studied as particular cases of that general construction. Motivated by finite element/volume applications, we study capabilities of transfinite barycentric interpolation schemes to approximate harmonic and quasi-harmonic functions. Finally we establish and analyze links between transfinite barycentric coordinates and certain inverse problems of differential and convex geometry.
Hierarchical Error-Driven Approximation of Implicit Surfaces from Polygonal Meshes
(The Eurographics Association, 2006) Kanai, Takashi; Ohtake, Yutaka; Kase, Kiwamu; Alla Sheffer and Konrad Polthier
This paper describes an efficient method for the hierarchical approximation of implicit surfaces from polygonal meshes. A novel error function between a polygonal mesh and an implicit surface is proposed. This error function is defined so as to be scale-independent from its global behavior as well as to be area-sensitive on local regions. An implicit surface tightly-fitted to polygons can be computed by the least-squares fitting method. Furthermore, this function can be represented as the quadric form, which realizes a compact representation of such an error metric. Our novel algorithm rapidly constructs a SLIM (Sparse Low-degree IMplicit) surface which is a recently developed non-conforming hierarchical implicit surface representation. Users can quickly obtain a set of implicit surfaces with arbitrary resolution according to errors from a SLIM surface.
Size Functions for 3D Shape Retrieval
(The Eurographics Association, 2006) Biasotti, S.; Giorgi, D.; Spagnuolo, M.; Falcidieno, B.; Alla Sheffer and Konrad Polthier
This paper sketches a technique for 3D model retrieval built on size functions, a mathematical tool to compare shapes. Size functions are introduced for the first time to discriminate among 3D objects, through the proposal of an innovative method to construct size graphs independently of the underlying triangulation. We demonstrate the potential of our approach in a series of comparative experiments with respect to existing techniques.
Folding Meshes: Hierarchical Mesh Segmentation based on Planar Symmetry
(The Eurographics Association, 2006) Simari, Patricio; Kalogerakis, Evangelos; Singh, Karan; Alla Sheffer and Konrad Polthier
Meshes representing real world objects, both artist-created and scanned, contain a high level of redundancy due to (possibly approximate) planar reflection symmetries, either global or localized to different subregions. An algorithm is presented for detecting such symmetries and segmenting the mesh into the symmetric and remaining regions. The method, inspired by techniques in Computer Vision, has foundations in robust statistics and is resilient to structured outliers which are present in the form of the non symmetric regions of the data. Also introduced is an application of the method: the folding tree data structure. The structure encodes the non redundant regions of the original mesh as well as the reflection planes and is created by the recursive application of the detection method. This structure can then be unfolded to recover the original shape. Applications include mesh compression, repair, skeletal extraction of objects of known symmetry as well as mesh processing acceleration by limiting computation to non redundant regions and propagation of results.
Designing Quadrangulations with Discrete Harmonic Forms
(The Eurographics Association, 2006) Tong, Y.; Alliez, P.; Cohen-Steiner, D.; Desbrun, M.; Alla Sheffer and Konrad Polthier
We introduce a framework for quadrangle meshing of discrete manifolds. Based on discrete differential forms, our method hinges on extending the discrete Laplacian operator (used extensively in modeling and animation) to allow for line singularities and singularities with fractional indices. When assembled into a singularity graph, these line singularities are shown to considerably increase the design flexibility of quad meshing. In particular, control over edge alignments and mesh sizing are unique features of our novel approach. Another appeal of our method is its robustness and scalability from a numerical viewpoint: we simply solve a sparse linear system to generate a pair of piecewise-smooth scalar fields whose isocontours form a pure quadrangle tiling, with no T-junctions.
Automatic and Interactive Mesh to T-Spline Conversion
(The Eurographics Association, 2006) Li, Wan-Chiu; Ray, Nicolas; Lévy, Bruno; Alla Sheffer and Konrad Polthier
In Geometry Processing, and more specifically in surface approximation, one of the most important issues is the automatic generation of a quad-dominant control mesh from an arbitrary shape (e.g. a scanned mesh). One of the first fully automatic solutions was proposed by Eck and Hoppe in 1996. However, in the industry, designers still use manual tools (see e.g. cyslice). The main difference between a control mesh constructed by an automatic method and the one designed by a human user is that in the second case, the control mesh follows the features of the model. More precisely, it is well known from approximation theory that aligning the edges with the principal directions of curvature improves the smoothness of the reconstructed surface, and this is what designers intuitively do. In this paper, our goal is to automatically construct a control mesh driven by the anisotropy of the shape, mimicking the mesh that a designer would create manually. The control mesh generated by our method can be used by a wide variety of representations (splines, subdivision surfaces ...). We demonstrate our method applied to the automatic conversion from a mesh of arbitrary topology into a T-Spline surface. Our method first extracts an initial mesh from a PGP (Periodic Global Parameterization). To facilitate user-interaction, we extend the PGP method to take into account optional user-defined information. This makes it possible to locally tune the orientation and the density of the control mesh. The user can also interactively remove edges or sketch additional ones. Then, from this initial control mesh, our algorithm generates a valid T-Spline control mesh by enforcing some validity constraints. The valid T-Spline control mesh is finally fitted to the original surface, using a classic regularized optimization procedure. To reduce the L-infinite approximation error below a user-defined threshold, we iteratively use the T-Spline adaptive local refinement.

Browse

Browsing SGP06: Eurographics Symposium on Geometry Processing by Issue Date

Results Per Page

Sort Options