SGP05: Eurographics Symposium on Geometry Processing
Permanent URI for this collection
Example-Based 3D Scan Completion
[meta data] [files:
Pauly, Mark
;
Mitra, Niloy J.
;
Giesen, Joachim
;
Gross, Markus
;
Guibas, Leonidas J.
An Adaptive MLS Surface for Reconstruction with Guarantees
[meta data] [files:
Dey, Tamal K.
;
Sun, Jian
Surface Reconstruction for Noisy Point Clouds
[meta data] [files:
Mederos, Boris
;
Amenta, Nina
;
Velho, Luiz
;
Figueiredo, Luiz Henrique de
Triangulating Point Set Surfaces with Bounded Error
[meta data] [files:
Scheidegger, Carlos E.
;
Fleishman, Shachar
;
Silva, Claudio T.
Smooth Feature Lines on Surface Meshes
[meta data] [files:
Hildebandt, Klaus
;
Polthier, Konrad
;
Wardetzky, Max
Streaming Compression of Triangle Meshes
[meta data] [files:
Isenburg, Martin
;
Lindstrom, Peter
;
Snoeyink, Jack
Setting the Boundary Free: A Composite Approach to Surface Parameterization
[meta data] [files:
Zayer, Rhaleb
;
Rössl, Christian
;
Seidel, Hans-Peter
Progressive Buffers: View-dependent Geometry and Texture for LOD Rendering
[meta data] [files:
Sander, Pedro V.
;
Mitchell, Jason L.
Extraction and Simplification of Iso-surfaces in Tandem
[meta data] [files:
Attali, Dominique
;
Cohen-Steiner, David
;
Edelsbrunner, Herbert
Data Structures for Simplicial Complexes: An Analysis And A Comparison
[meta data] [files:
Floriani, Leila De
;
Hui, Annie
Sparse Low-degree Implicits with Applications to High Quality Rendering, Feature Extraction, and Smoothing
[meta data] [files:
Ohtake, Yutaka
;
Belyaev, Alexander
;
Alexa, Marc
Subdivision Schemes and Attractors
[meta data] [files:
Schaefer, Scott
;
Levin, David
;
Goldman, Ron
A Geometric Construction of Coordinates for Convex Polyhedra using Polar Duals
[meta data] [files:
Ju, Tao
;
Schaefer, Scott
;
Warren, Joe
;
Desbrun, Mathieu
Global Registration of Multiple 3D Point Sets via Optimization-on-a-Manifold
[meta data] [files:
Krishnan, Shankar
;
Lee, Pei Yean
;
Moore, John B.
;
Venkatasubramanian, Suresh
Robust Global Registration
[meta data] [files:
Gelfand, Natasha
;
Mitra, Niloy J.
;
Guibas, Leonidas J.
;
Pottmann, Helmut
An Image Processing Approach to Surface Matching
[meta data] [files:
Litke, Nathan
;
Droske, Marc
;
Rumpf, Martin
;
Schröder, Peter
Multiscale Features for Approximate Alignment of Point-based Surfaces
[meta data] [files:
Li, Xinju
;
Guskov, Igor
Browse
Recent Submissions
Item Surface Tiling with Differential Topology(The Eurographics Association, 2005) Edelsbrunner, Herbert; Mathieu Desbrun and Helmut PottmannA challenging problem in computer-aided geometric design is the decomposition of a surface into four-sided regions that are then represented by NURBS patches. There are various approaches published in the literature and implemented as commercially available software, but all fall short in either automation or quality of the result. At Raindrop Geomagic, we have recently taken a fresh approach based on concepts from Morse theory. This by itself is not a new idea, but we have some novel ingredients that make this work, one being a rational notion of hierarchy that guides the construction of a simplified decomposition sensitive to only the major critical points.Item Example-Based 3D Scan Completion(The Eurographics Association, 2005) Pauly, Mark; Mitra, Niloy J.; Giesen, Joachim; Gross, Markus; Guibas, Leonidas J.; Mathieu Desbrun and Helmut PottmannWe present a novel approach for obtaining a complete and consistent 3D model representation from incomplete surface scans, using a database of 3D shapes to provide geometric priors for regions of missing data. Our method retrieves suitable context models from the database, warps the retrieved models to conform with the input data, and consistently blends the warped models to obtain the final consolidated 3D shape. We define a shape matching penalty function and corresponding optimization scheme for computing the non-rigid alignment of the context models with the input data. This allows a quantitative evaluation and comparison of the quality of the shape extrapolation provided by each model. Our algorithms are explicitly designed to accommodate uncertain data and can thus be applied directly to raw scanner output. We show on a variety of real data sets how consistent models can be obtained from highly incomplete input. The information gained during the shape completion process can be utilized for future scans, thus continuously simplifying the creation of complex 3D models.Item Template-Based Mesh Completion(The Eurographics Association, 2005) Kraevoy, Vladislav; Sheffer, Alla; Mathieu Desbrun and Helmut PottmannMeshes generated by range scanners and other acquisition tools are often incomplete and typically contain multiple connected components with irregular boundaries and complex holes. This paper introduces a robust algorithm for completion of such meshes using a mapping between the incomplete mesh and a template model. The mapping is computed using a novel framework for bijective parameterization of meshes with gaps and holes. We employ this mapping to correctly glue together the components of the input mesh and to close the holes. The template is used to fill in the topological and geometric information missing in the input. The completed models are guaranteed to have the same topology as the template. Furthermore, if no appropriate template exists or if only topologically correct completion is required a standard canonical shape can be used as a template. As part of our completion method we propose a boundary-mapping technique useful for mesh editing operations such as merging, blending, and detail transfer. We demonstrate that by using this technique we can automatically perform complex editing operations that previously required a large amount of user interaction.Item An Adaptive MLS Surface for Reconstruction with Guarantees(The Eurographics Association, 2005) Dey, Tamal K.; Sun, Jian; Mathieu Desbrun and Helmut PottmannRecent work have shown that moving least squares (MLS) surfaces can be used effectively to reconstruct surfaces from possibly noisy point cloud data. Several variants of MLS surfaces have been suggested, some of which have been analyzed theoretically for guarantees. These analyses, so far, have assumed uniform sampling density. We propose a new variant of the MLS surface that, for the first time, incorporates local feature sizes in its formulation, and we analyze it for reconstruction guarantees using a non-uniform sampling density. The proposed variant of the MLS surface has several computational advantages over existing MLS methods.Item Atomic Volumes for Mesh Completion(The Eurographics Association, 2005) Podolak, Joshua; Rusinkiewicz, Szymon; Mathieu Desbrun and Helmut PottmannThe increased use of scanned geometry for applications in computer graphics and 3D hardcopy output has highlighted the need for general, robust algorithms for reconstruction of watertight 3D models given partial polygonal meshes as input. We present an algorithm for 3D hole filling based on a decomposition of space into atomic volumes, which are each determined to be either completely inside or completely outside the model. By defining the output model as the union of interior atomic volumes we guarantee that the resulting mesh is watertight. Individual volumes are labeled as "inside" or "outside" by computing a minimum-cost cut of a graph representation of the atomic volume structure, patching all the holes simultaneously in a globally sensitive manner. User control is provided to select between multiple topologically distinct, yet still valid, ways of filling holes. Finally, we use an octree decomposition of space to provide output-sensitive computation time. We demonstrate the ability of our algorithm to fill complex, non-planar holes in large meshes obtained from 3D scanning devices.Item Surface Reconstruction for Noisy Point Clouds(The Eurographics Association, 2005) Mederos, Boris; Amenta, Nina; Velho, Luiz; Figueiredo, Luiz Henrique de; Mathieu Desbrun and Helmut PottmannWe show that a simple modification of the power crust algorithm for surface reconstruction produces correct outputs in presence of noise. This is proved using a fairly realistic noise model. Our theoretical results are related to the problem of computing a stable subset of the medial axis. We demostrate the effectiveness of our algorithm with a number of experimental results.Item Triangulating Point Set Surfaces with Bounded Error(The Eurographics Association, 2005) Scheidegger, Carlos E.; Fleishman, Shachar; Silva, Claudio T.; Mathieu Desbrun and Helmut PottmannWe introduce an algorithm for constructing a high-quality triangulation directly from Point Set Surfaces. Our algorithm requires no intermediate representation and no post-processing of the output, and naturally handles noisy input data, typically in the form of a set of registered range scans. It creates a triangulation where triangle size respects the geometry of the surface rather than the sampling density of the range scans. Our technique does not require normal information, but still produces a consistent orientation of the triangles, assuming the sampled surface is an orientable two-manifold. Our work is based on using Moving Least-Squares (MLS) surfaces as the underlying representation. Our technique is a novel advancing front algorithm, that bounds the Hausdorff distance to within a user-specified limit. Specifically, we introduce a way of augmenting advancing front algorithms with global information, so that triangle size adapts gracefully even when there are large changes in surface curvature. Our results show that our technique generates high-quality triangulations where other techniques fail to reconstruct the correct surface due to irregular sampling on the point cloud, noise, registration artifacts, and underlying geometric features, such as regions with high curvature gradients.Item Reconstruction of Solid Models from Oriented Point Sets(The Eurographics Association, 2005) Kazhdan, Michael; Mathieu Desbrun and Helmut PottmannIn this paper we present a novel approach to the surface reconstruction problem that takes as its input an oriented point set and returns a solid, water-tight model. The idea of our approach is to use Stokes' Theorem to compute the characteristic function of the solid model (the function that is equal to one inside the model and zero outside of it). Specifically, we provide an efficient method for computing the Fourier coefficients of the characteristic function using only the surface samples and normals, we compute the inverse Fourier transform to get back the characteristic function, and we use iso-surfacing techniques to extract the boundary of the solid model. The advantage of our approach is that it provides an automatic, simple, and efficient method for computing the solid model represented by a point set without requiring the establishment of adjacency relations between samples or iteratively solving large systems of linear equations. Furthermore, our approach can be directly applied to models with holes and cracks, providing a method for hole-filling and zippering of disconnected polygonal models.Item Non-conforming Surface Rrepresentations(The Eurographics Association, 2005) Alexa, Marc; Mathieu Desbrun and Helmut PottmannSurface geometry is commonly represented by a collection of primitives. Conforming representations consist of primitives meeting at their boundaries (e.g., in a triangle mesh two triangles are incident upon an edge). Without the restriction to conforming elements there are no dependencies among primitives, leading to more degrees of freedom for each primitive. This yields more efficient and flexible algorithms for reconstruction, processing, and rendering, as well as compact and accurate representations.Item Discrete Willmore Flow(The Eurographics Association, 2005) Bobenko, Alexander I.; Schröder, Peter; Mathieu Desbrun and Helmut PottmannThe Willmore energy of a surface, R(H2 -K)dA, as a function of mean and Gaussian curvature, captures the deviation of a surface from (local) sphericity. As such this energy and its associated gradient flow play an important role in digital geometry processing, geometric modeling, and physical simulation. In this paper we consider a discrete Willmore energy and its flow. In contrast to traditional approaches it is not based on a finite element discretization, but rather on an ab initio discrete formulation which preserves the Möbius symmetries of the underlying continuous theory in the discrete setting. We derive the relevant gradient expressions including a linearization (approximation of the Hessian), which are required for non-linear numerical solvers. As examples we demonstrate the utility of our approach for surface restoration, n-sided hole filling, and non-shrinking surface smoothing.Item Smooth Feature Lines on Surface Meshes(The Eurographics Association, 2005) Hildebandt, Klaus; Polthier, Konrad; Wardetzky, Max; Mathieu Desbrun and Helmut PottmannFeature lines are salient surface characteristics. Their definition involves third and fourth order surface derivatives. This often yields to unpleasantly rough and squiggly feature lines since third order derivatives are highly sensitive against unwanted surface noise. The present work proposes two novel concepts for a more stable algorithm producing visually more pleasing feature lines: First, a new computation scheme based on discrete differential geometry is presented, avoiding costly computations of higher order approximating surfaces. Secondly, this scheme is augmented by a filtering method for higher order surface derivatives to improve both the stability of the extraction of feature lines and the smoothness of their appearance.Item Streaming Compression of Triangle Meshes(The Eurographics Association, 2005) Isenburg, Martin; Lindstrom, Peter; Snoeyink, Jack; Mathieu Desbrun and Helmut PottmannCurrent mesh compression schemes encode triangles and vertices in an order derived from systematically traversing the connectivity graph. These schemes struggle with gigabyte-sized mesh input where the construction and the usage of the data structures that support topological traversal queries become I/O-inefficient and require large amounts of temporary disk space. Furthermore they expect the entire mesh as input. Since meshes cannot be compressed until their generation is complete, they have to be stored at least once in uncompressed form. We radically depart from the traditional approach to mesh compression and propose a scheme that incrementally encodes a mesh in the order it is given to the compressor using only minimal memory resources. This makes the compression process essentially transparent to the user and practically independent of the mesh size. This is especially beneficial for compressing large meshes, where previous approaches spend significant memory, disk, and I/O resources on pre-processing, whereas our scheme starts compressing after receiving the first few triangles.Item Setting the Boundary Free: A Composite Approach to Surface Parameterization(The Eurographics Association, 2005) Zayer, Rhaleb; Rössl, Christian; Seidel, Hans-Peter; Mathieu Desbrun and Helmut PottmannIn the last decade, surface mesh parameterization has emerged as a standard technique in computer graphics. The ever increasing need for processing large and highly detailed data sets fosters the development of efficient parameterization techniques that can capture the geometry of the input meshes and produce low distortion planar maps. We present a set of novel techniques allowing for low distortion parameterization. In particular, we address one of the major shortcomings of linear methods by allowing the parametric representation to evolve freely on the plane without any fixed boundary vertices. Our method consists of several simple steps, each solving a linear problem. Our results exhibit a fair balance between high-quality and computational efficiency.Item Progressive Buffers: View-dependent Geometry and Texture for LOD Rendering(The Eurographics Association, 2005) Sander, Pedro V.; Mitchell, Jason L.; Mathieu Desbrun and Helmut PottmannWe introduce a view-dependent level of detail rendering system designed with modern GPU architectures in mind. Our approach keeps the data in static buffers and geomorphs between different LODs using per-vertex weights for seamless transition. Our method is the first out-of-core system to support texture mapping, including a mechanism for texture LOD. This approach completely avoids LOD pops and boundary cracks while gracefully adapting to a specified framerate or level of detail. Our method is suitable for all classes of GPUs that provide basic vertex shader programmability, and is applicable for both out-of-core or instanced geometry. The contributions of our work include a preprocessing and rendering system for view-dependent LOD rendering by geomorphing static buffers using per-vertex weights, a vertex buffer tree to minimize the number of API draw calls when rendering coarse-level geometry, and automatic methods for efficient, transparent LOD control.Item Extraction and Simplification of Iso-surfaces in Tandem(The Eurographics Association, 2005) Attali, Dominique; Cohen-Steiner, David; Edelsbrunner, Herbert; Mathieu Desbrun and Helmut PottmannThe tandem algorithm combines the marching cube algorithm for surface extraction and the edge contraction algorithm for surface simplification in lock-step to avoid the costly intermediate step of storing the entire extracted surface triangulation. Beyond this basic strategy, we introduce refinements to prevent artifacts in the resulting triangulation, first, by carefully monitoring the amount of simplification during the process and, second, by driving the simplification toward a compromise between shape approximation and mesh quality. We have implemented the algorithm and used extensive computational experiments to document the effects of various design options and to further fine-tune the algorithm.Item Data Structures for Simplicial Complexes: An Analysis And A Comparison(The Eurographics Association, 2005) Floriani, Leila De; Hui, Annie; Mathieu Desbrun and Helmut PottmannIn this paper, we review, analyze and compare representations for simplicial complexes. We classify such representations, based on the dimension of the complexes they can encode, into dimension-independent structures, and data structures for three- and for two-dimensional simplicial complexes. We further classify the data structures in each group according to the basic kinds of the topological entities they represent. We present a description of each data structure in terms of the entities and topological relations encoded, and we evaluate it based on its expressive power, on its storage cost and on the efficiency in supporting navigation inside the complex, i.e., in retrieving topological relations not explicitly encoded. We compare the various data structures inside each category based on the above features.Item Modeling with Simplicial Diffeomorphisms(The Eurographics Association, 2005) Velho, Luiz; Mathieu Desbrun and Helmut PottmannIn this paper we introduce a new framework for geometric modeling that combines implicit and parametric surface representations with volumetric warpings. The framework is based on dynamic, adaptive simplicial decompositions of the embedding space and conforming piecewise diffeomorphisms.Item Sparse Low-degree Implicits with Applications to High Quality Rendering, Feature Extraction, and Smoothing(The Eurographics Association, 2005) Ohtake, Yutaka; Belyaev, Alexander; Alexa, Marc; Mathieu Desbrun and Helmut PottmannWe propose a new surface representation delivering an accurate approximation to a set of points scattered over a smooth surface by Sparse Low-degree IMplicits (SLIM). The SLIM surface representation consists of a sparse multi-scale set of nonconforming surface primitives which are blended along view rays during the rendering phase. This new representation leads to an interactive real-time visualization of large-size models and delivers a better rendering quality than standard splatting techniques based on linear primitives. Further, SLIM allows us to achieve a fast and accurate estimation of surface curvature and curvature derivatives and, therefore, is very suitable for many non-photorealistic rendering tasks. Applications to ray-tracing and surface smoothing are also considered.Item Subdivision Schemes and Attractors(The Eurographics Association, 2005) Schaefer, Scott; Levin, David; Goldman, Ron; Mathieu Desbrun and Helmut PottmannSubdivision schemes generate self-similar curves and surfaces. Therefore there is a close connection between curves and surfaces generated by subdivision algorithms and self-similar fractals generated by Iterated Function Systems (IFS). We demonstrate that this connection between subdivision schemes and fractals is even deeper by showing that curves and surfaces generated by subdivision are also attractors, fixed points of IFS's. To illustrate this fractal nature of subdivision, we derive the associated IFS for many different subdivision curves and surfaces without extraordinary vertices, including B-splines, piecewise Bezier, interpolatory four-point subdivision, bicubic subdivision, three-direction quartic box-spline subdivision and Kobbelt's p3-subdivision surfaces. Conversely, we shall show how to build subdivision schemes to generate traditional fractals such as the Sierpinski gasket and the Koch curve, and we demonstrate as well how to control the shape of these fractals by adjusting their control points.Item Swept Volumes of many Poses(The Eurographics Association, 2005) Wallner, Johannes; Yang, Qinmin; Mathieu Desbrun and Helmut PottmannWe consider the swept volume A(X) of a rigid body X which assumes a general set A of positions. A special case of this is a one-parameter motion of X, where the set of poses is curve-like. Here we consider a full-dimensional subset A of the motion group. Such a set of poses can be seen as the tolerance zone of an imprecisely defined pose. Alternatively, a set of poses may be obtained by by measurements or simulation. We analyze the geometric properties of such sets of poses and give algorithms for computing the boundary deltaA(X) in the case that A is a discrete pose cloud. The dimension of the problem, which equals six a priori, is reduced to two.Item A Geometric Construction of Coordinates for Convex Polyhedra using Polar Duals(The Eurographics Association, 2005) Ju, Tao; Schaefer, Scott; Warren, Joe; Desbrun, Mathieu; Mathieu Desbrun and Helmut PottmannA fundamental problem in geometry processing is that of expressing a point inside a convex polyhedron as a combination of the vertices of the polyhedron. Instances of this problem arise often in mesh parameterization and 3D deformation. A related problem is to express a vector lying in a convex cone as a non-negative combination of edge rays of this cone. This problem also arises in many applications such as planar graph embedding and spherical parameterization. In this paper, we present a unified geometric construction for building these weighted combinations using the notion of polar duals. We show that our method yields a simple geometric construction for Wachspress's barycentric coordinates, as well as for constructing Colin de Verdière matrices from convex polyhedra - a critical step in Lovasz's method with applications to parameterizations.Item Global Registration of Multiple 3D Point Sets via Optimization-on-a-Manifold(The Eurographics Association, 2005) Krishnan, Shankar; Lee, Pei Yean; Moore, John B.; Venkatasubramanian, Suresh; Mathieu Desbrun and Helmut PottmannWe propose a novel algorithm to register multiple 3D point sets within a common reference frame using a manifold optimization approach. The point sets are obtained with multiple laser scanners or a mobile scanner. Unlike most prior algorithms, our approach performs an explicit optimization on the manifold of rotations, allowing us to formulate the registration problem as an unconstrained minimization on a constrained manifold. This approach exploits the Lie group structure of SO3 and the simple representation of its associated Lie algebra so3 in terms of R3. Our contributions are threefold. We present a new analytic method based on singular value decompositions that yields a closed-form solution for simultaneous multiview registration in the noise-free scenario. Secondly, we use this method to derive a good initial estimate of a solution in the noise-free case. This initialization step may be of use in any general iterative scheme. Finally, we present an iterative scheme based on Newton's method on SO3 that has locally quadratic convergence. We demonstrate the efficacy of our scheme on scan data taken both from the Digital Michelangelo project and from scans extracted from models, and compare it to some of the other well known schemes for multiview registration. In all cases, our algorithm converges much faster than the other approaches, (in some cases orders of magnitude faster), and generates consistently higher quality registrations.Item Robust Global Registration(The Eurographics Association, 2005) Gelfand, Natasha; Mitra, Niloy J.; Guibas, Leonidas J.; Pottmann, Helmut; Mathieu Desbrun and Helmut PottmannWe present an algorithm for the automatic alignment of two 3D shapes (data and model), without any assumptions about their initial positions. The algorithm computes for each surface point a descriptor based on local geometry that is robust to noise. A small number of feature points are automatically picked from the data shape according to the uniqueness of the descriptor value at the point. For each feature point on the data, we use the descriptor values of the model to find potential corresponding points. We then develop a fast branch-and-bound algorithm based on distance matrix comparisons to select the optimal correspondence set and bring the two shapes into a coarse alignment. The result of our alignment algorithm is used as the initialization to ICP (iterative closest point) and its variants for fine registration of the data to the model. Our algorithm can be used for matching shapes that overlap only over parts of their extent, for building models from partial range scans, as well as for simple symmetry detection, and for matching shapes undergoing articulated motion.Item An Image Processing Approach to Surface Matching(The Eurographics Association, 2005) Litke, Nathan; Droske, Marc; Rumpf, Martin; Schröder, Peter; Mathieu Desbrun and Helmut PottmannEstablishing a correspondence between two surfaces is a basic ingredient in many geometry processing applications. Existing approaches, which attempt to match two meshes directly in 3D, can be cumbersome to implement and it is often hard to produce accurate results in a reasonable amount of time. In this paper, we present a new variational method for matching surfaces that addresses these issues. Instead of matching two surfaces directly in 3D, we apply well-established matching methods from image processing in the parameter domains of the surfaces. A matching energy is introduced that can depend on curvature, feature demarcations or surface textures, and a regularization energy controls length and area changes in the induced non-rigid deformation between the two surfaces. The metric on both surfaces is properly incorporated into the formulation of the energy. This approach reduces all computations to the 2D setting while accounting for the original geometries. Consequently a fast multiresolution numerical algorithm for regular image grids can be used to solve the global optimization problem. The final algorithm is robust, generically much simpler than direct matching methods, and very fast for highly resolved triangle meshes.Item Multiscale Features for Approximate Alignment of Point-based Surfaces(The Eurographics Association, 2005) Li, Xinju; Guskov, Igor; Mathieu Desbrun and Helmut PottmannWe introduce a novel method for approximate alignment of point-based surfaces. Our approach is based on detecting a set of salient feature points using a scale-space representation. For each feature point we compute a signature vector that is approximately invariant under rigid transformations. We use the extracted signed feature set in order to obtain approximate alignment of two surfaces. We apply our method for the automatic alignment of multiple scans using both scan-to-scan and scan-to-model matching capabilities.