SGP05: Eurographics Symposium on Geometry Processing

Permanent URI for this collection

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

Browse

Now showing 1 - 20 of 25

An Adaptive MLS Surface for Reconstruction with Guarantees
(The Eurographics Association, 2005) Dey, Tamal K.; Sun, Jian; Mathieu Desbrun and Helmut Pottmann
Recent 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.
Atomic Volumes for Mesh Completion
(The Eurographics Association, 2005) Podolak, Joshua; Rusinkiewicz, Szymon; Mathieu Desbrun and Helmut Pottmann
The 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.
Data Structures for Simplicial Complexes: An Analysis And A Comparison
(The Eurographics Association, 2005) Floriani, Leila De; Hui, Annie; Mathieu Desbrun and Helmut Pottmann
In 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.
Discrete Willmore Flow
(The Eurographics Association, 2005) Bobenko, Alexander I.; Schröder, Peter; Mathieu Desbrun and Helmut Pottmann
The 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.
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 Pottmann
We 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.
Extraction and Simplification of Iso-surfaces in Tandem
(The Eurographics Association, 2005) Attali, Dominique; Cohen-Steiner, David; Edelsbrunner, Herbert; Mathieu Desbrun and Helmut Pottmann
The 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.
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 Pottmann
A 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.
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 Pottmann
We 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.
An Image Processing Approach to Surface Matching
(The Eurographics Association, 2005) Litke, Nathan; Droske, Marc; Rumpf, Martin; Schröder, Peter; Mathieu Desbrun and Helmut Pottmann
Establishing 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.
Modeling with Simplicial Diffeomorphisms
(The Eurographics Association, 2005) Velho, Luiz; Mathieu Desbrun and Helmut Pottmann
In 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.
Multiscale Features for Approximate Alignment of Point-based Surfaces
(The Eurographics Association, 2005) Li, Xinju; Guskov, Igor; Mathieu Desbrun and Helmut Pottmann
We 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.
Non-conforming Surface Rrepresentations
(The Eurographics Association, 2005) Alexa, Marc; Mathieu Desbrun and Helmut Pottmann
Surface 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.
Progressive Buffers: View-dependent Geometry and Texture for LOD Rendering
(The Eurographics Association, 2005) Sander, Pedro V.; Mitchell, Jason L.; Mathieu Desbrun and Helmut Pottmann
We 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.
Reconstruction of Solid Models from Oriented Point Sets
(The Eurographics Association, 2005) Kazhdan, Michael; Mathieu Desbrun and Helmut Pottmann
In 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.
Robust Global Registration
(The Eurographics Association, 2005) Gelfand, Natasha; Mitra, Niloy J.; Guibas, Leonidas J.; Pottmann, Helmut; Mathieu Desbrun and Helmut Pottmann
We 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.
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 Pottmann
In 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.
Smooth Feature Lines on Surface Meshes
(The Eurographics Association, 2005) Hildebandt, Klaus; Polthier, Konrad; Wardetzky, Max; Mathieu Desbrun and Helmut Pottmann
Feature 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.
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 Pottmann
We 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.
Streaming Compression of Triangle Meshes
(The Eurographics Association, 2005) Isenburg, Martin; Lindstrom, Peter; Snoeyink, Jack; Mathieu Desbrun and Helmut Pottmann
Current 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.
Subdivision Schemes and Attractors
(The Eurographics Association, 2005) Schaefer, Scott; Levin, David; Goldman, Ron; Mathieu Desbrun and Helmut Pottmann
Subdivision 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.

Browse

Browsing SGP05: Eurographics Symposium on Geometry Processing by Title

Results Per Page

Sort Options