SGP07: Eurographics Symposium on Geometry Processing

Permanent URI for this collection

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

Browse

Now showing 1 - 20 of 28

Focal Surfaces of Discrete Geometry
(The Eurographics Association, 2007) Yu, Jingyi; Yin, Xiaotian; Gu, Xianfeng; McMillan, Leonard; Gortler, Steven; Alexander Belyaev and Michael Garland
The differential geometry of smooth three-dimensional surfaces can be interpreted from one of two perspectives: in terms of oriented frames located on the surface, or in terms of a pair of associated focal surfaces. These focal surfaces are swept by the loci of the principal curvatures radii. In this article, we develop a focal-surfacebased differential geometry interpretation for discrete mesh surfaces. Focal surfaces have many useful properties. For instance, the normal of each focal surface indicates a principal direction of the corresponding point on the original surface. We provide algorithms to robustly approximate the focal surfaces of a triangle mesh with known or estimated normals. Our approach locally parameterizes the surface normals about a point by their intersections with a pair of parallel planes.We show neighboring normal triplets are constrained to pass simultaneously through two slits, which are parallel to the specified parametrization planes and rule the focal surfaces. We develop both CPU and GPU-based algorithms to efficiently approximate these two slits and, hence, the focal meshes. Our focal mesh estimation also provides a novel discrete shape operator that simultaneously estimates the principal curvatures and principal directions.
Robust Statistical Estimation of Curvature on Discretized Surfaces
(The Eurographics Association, 2007) Kalogerakis, Evangelos; Simari, Patricio; Nowrouzezahrai, Derek; Singh, Karan; Alexander Belyaev and Michael Garland
A robust statistics approach to curvature estimation on discretely sampled surfaces, namely polygon meshes and point clouds, is presented. The method exhibits accuracy, stability and consistency even for noisy, non-uniformly sampled surfaces with irregular configurations. Within an M-estimation framework, the algorithm is able to reject noise and structured outliers by sampling normal variations in an adaptively reweighted neighborhood around each point. The algorithm can be used to reliably derive higher order differential attributes and even correct noisy surface normals while preserving the fine features of the normal and curvature field. The approach is compared with state-of-the-art curvature estimation methods and shown to improve accuracy by up to an order of magnitude across ground truth test surfaces under varying tessellation densities and types as well as increasing degrees of noise. Finally, the benefits of a robust statistical estimation of curvature are illustrated by applying it to the popular applications of mesh segmentation and suggestive contour rendering.
Surface Reconstruction using Local Shape Priors
(The Eurographics Association, 2007) Gal, Ran; Shamir, Ariel; Hassner, Tal; Pauly, Mark; Or, Daniel Cohen; Alexander Belyaev and Michael Garland
We present an example-based surface reconstruction method for scanned point sets. Our approach uses a database of local shape priors built from a set of given context models that are chosen specifically to match a specific scan. Local neighborhoods of the input scan are matched with enriched patches of these models at multiple scales. Hence, instead of using a single prior for reconstruction, our method allows specific regions in the scan to match the most relevant prior that fits best. Such high confidence matches carry relevant information from the prior models to the scan, including normal data and feature classification, and are used to augment the input point-set. This allows to resolve many ambiguities and difficulties that come up during reconstruction, e.g., distinguishing between signal and noise or between gaps in the data and boundaries of the model. We demonstrate how our algorithm, given suitable prior models, successfully handles noisy and under-sampled point sets, faithfully reconstructing smooth regions as well as sharp features.
Data-Dependent MLS for Faithful Surface Approximation
(The Eurographics Association, 2007) Lipman, Yaron; Cohen-Or, Daniel; Levin, David; Alexander Belyaev and Michael Garland
In this paper we present a high-fidelity surface approximation technique that aims at a faithful reconstruction of piecewise-smooth surfaces from a scattered point set. The presented method builds on the Moving Least-Squares (MLS) projection methodology, but introduces a fundamental modification: While the classical MLS uses a fixed approximation space, i.e., polynomials of a certain degree, the new method is data-dependent. For each projected point, it finds a proper local approximation space of piecewise polynomials (splines). The locally constructed spline encapsulates the local singularities which may exist in the data. The optional singularity for this local approximation space is modeled via a Singularity Indicator Field (SIF) which is computed over the input data points. We demonstrate the effectiveness of the method by reconstructing surfaces from real scanned 3D data, while being faithful to their most delicate features.
Generalized Surface Flows for Mesh Processing
(The Eurographics Association, 2007) Eckstein, Ilya; Pons, Jean-Philippe; Tong, Yiying; Kuo, C.-C. Jay; Desbrun, Mathieu; Alexander Belyaev and Michael Garland
Geometric flows are ubiquitous in mesh processing. Curve and surface evolutions based on functional minimization have been used in the context of surface diffusion, denoising, shape optimization, minimal surfaces, and geodesic paths to mention a few. Such gradient flows are nearly always, yet often implicitly, based on the canonical L2 inner product of vector fields. In this paper, we point out that changing this inner product provides a simple, powerful, and untapped approach to extend current flows. We demonstrate the value of such a norm alteration for regularization and volume-preservation purposes and in the context of shape matching, where deformation priors (ranging from rigid motion to articulated motion) can be incorporated into a gradient flow to drastically improve results. Implementation details, including a differentiable approximation of the Hausdorff distance between irregular meshes, are presented.
Ridge Based Curve and Surface Reconstruction
(The Eurographics Association, 2007) Suessmuth, Jochen; Greiner, Guenther; Alexander Belyaev and Michael Garland
This paper presents a new method for reconstructing curves and surfaces from unstructured point clouds, allowing for noise in the data as well as inhomogeneous distribution of the point set. It is based on the observation that the curve/surface is located where locally the point cloud has highest density. This idea is pursued by a differential geometric analysis of a smoothed version of the density function. More precisely we detect ridges of this function and have to single out the relevant parts. An efficient implementation of this approach evaluates the differential geometric quantities on a regular grid, performs local analysis and finally recovers the curve/surface by an isoline extraction or a marching cubes algorithm respectively. Compared to existing surface reconstruction procedures, this approach works well for noisy data and for data with strongly varying sampling rate. Thus it can be applied successfully to reconstruct surface geometry from time-of-flight data, overlapping registered point clouds and point clouds obtained by feature tracking from video streams. Corresponding examples are presented to demonstrate the advantages of our method.
Elastic Secondary Deformations by Vector Field Integration
(The Eurographics Association, 2007) Funck, Wolfram von; Theisel, Holger; Seidel, Hans-Peter; Alexander Belyaev and Michael Garland
We present an approach for elastic secondary deformations of shapes described as triangular meshes. The deformations are steered by the simulation of a low number of simple mass-spring sets. The result of this simulation is used to define time-dependent divergence-free vector fields whose numerical path line integration gives the new location of each vertex. This way the deformation is guaranteed to be volume-preserving and without self-intersections, giving plausible elastic deformations. Due to a GPU implementation, the deformation can be obtained in real-time for fairly complex shapes. The approach also avoids unwanted intersections in the case of collisions in the primary animation. We demonstrate its accuracy, stableness and usefulness for different kinds of primary animations/deformations.
Discrete Laplace operators: No free lunch
(The Eurographics Association, 2007) Wardetzky, Max; Mathur, Saurabh; Kaelberer, Felix; Grinspun, Eitan; Alexander Belyaev and Michael Garland
Discrete Laplace operators are ubiquitous in applications spanning geometric modeling to simulation. For robustness and efficiency, many applications require discrete operators that retain key structural properties inherent to the continuous setting. Building on the smooth setting, we present a set of natural properties for discrete Laplace operators for triangular surface meshes. We prove an important theoretical limitation: discrete Laplacians cannot satisfy all natural properties; retroactively, this explains the diversity of existing discrete Laplace operators. Finally, we present a family of operators that includes and extends well-known and widely-used operators.
Unconstrained Isosurface Extraction on Arbitrary Octrees
(The Eurographics Association, 2007) Kazhdan, Michael; Klein, Allison; Dalal, Ketan; Hoppe, Hugues; Alexander Belyaev and Michael Garland
This paper presents a novel algorithm for generating a watertight level-set from an octree. We show that the level- set can be efficiently extracted regardless of the topology of the octree or the values assigned to the vertices. The key idea behind our approach is the definition of a set of binary edge-trees derived from the octree s topology. We show that the edge-trees can be used define the positions of the isovalue-crossings in a consistent fashion and to resolve inconsistencies that may arise when a single edge has multiple isovalue-crossings. Using the edge-trees, we show that a provably watertight mesh can be extracted from the octree without necessitating the refinement of nodes or modification of their values.
Reconstruction of Deforming Geometry from Time-Varying Point Clouds
(The Eurographics Association, 2007) Wand, Michael; Jenke, Philipp; Huang, Qixing; Bokeloh, Martin; Guibas, Leonidas; Schilling, Andreas; Alexander Belyaev and Michael Garland
In this paper, we describe a system for the reconstruction of deforming geometry from a time sequence of unstructured, noisy point clouds, as produced by recent real-time range scanning devices. Our technique reconstructs both the geometry and dense correspondences over time. Using the correspondences, holes due to occlusion are filled in from other frames. Our reconstruction technique is based on a statistical framework: The reconstruction should both match the measured data points and maximize prior probability densities that prefer smoothness, rigid deformation and smooth movements over time. The optimization procedure consists of an inner loop that optimizes the 4D shape using continuous numerical optimization and an outer loop that infers the discrete 4D topology of the data set using an iterative model assembly algorithm. We apply the technique to a variety of data sets, demonstrating that the new approach is capable of robustly retrieving animated models with correspondences from data sets suffering from significant noise, outliers and acquisition holes.
Constraint-based Fairing of Surface Meshes
(The Eurographics Association, 2007) Hildebrandt, Klaus; Polthier, Konrad; Alexander Belyaev and Michael Garland
We propose a constraint-based method for the fairing of surface meshes. The main feature of our approach is that the resulting smoothed surface remains within a prescribed distance to the input mesh. For example, specifying the maximum distance in the order of the measuring precision of a laser scanner allows noise to be removed while preserving the accuracy of the scan. The approach is modeled as an optimization problem where a fairness measure is minimized subject to constraints that control the spatial deviation of the surface. The problem is efficiently solved by an active set Newton method.
Shape Reconstruction from Unorganized Cross-sections
(The Eurographics Association, 2007) Boissonnat, Jean-Daniel; Memari, Pooran; Alexander Belyaev and Michael Garland
In this paper, we consider the problem of reconstructing a shape from unorganized cross-sections. The main motivation for this problem comes from medical imaging applications where cross-sections of human organs are obtained by means of a free hand ultrasound apparatus. The position and orientation of the cutting planes may be freely chosen which makes the problem substantially more difficult than in the case of parallel cross-sections, for which a rich literature exists. The input data consist of the cutting planes and (an approximation of) their intersection with the object. Our approach consists of two main steps. First, we compute the arrangement of the cutting planes. Then, in each cell of the arrangement, we reconstruct an approximation of the object from its intersection with the boundary of the cell. Lastly, we glue the various pieces together. The method makes use of the Delaunay triangulation and generalizes the reconstruction method of Boissonnat and Geiger [BG93] for the case of parallel planes. The analysis provides a neat characterization of the topological properties of the result and, in particular, shows an interesting application of Moebius diagrams to compute the locus of the branching points. We have implemented our algorithm in C++, using the [CGAL] library. Experimental results show that the algorithm performs well and can handle complicated branching configurations.
Fast Normal Vector Compression with Bounded Error
(The Eurographics Association, 2007) Griffith, E. J.; Koutek, M.; Post, Frits H.; Alexander Belyaev and Michael Garland
We present two methods for lossy compression of normal vectors through quantization using base polyhedra. The first revisits subdivision-based quantization. The second uses fixed-precision barycentric coordinates. For both, we provide fast (de)compression algorithms and a rigorous upper bound on compression error. We discuss the effects of base polyhedra on the error bound and suggest polyhedra derived from spherical coverings. Finally, we present compression and decompression results, and we compare our methods to others from the literature.
Symmetry-Enhanced Remeshing of Surfaces
(The Eurographics Association, 2007) Podolak, Joshua; Golovinskiy, Aleksey; Rusinkiewicz, Szymon; Alexander Belyaev and Michael Garland
While existing methods for 3D surface approximation use local geometric properties, we propose that more intuitive results can be obtained by considering global shape properties such as symmetry. We modify the Variational Shape Approximation technique to consider the symmetries, near-symmetries, and partial symmetries of the input mesh. This has the effect of preserving and even enhancing symmetries in the output model, if doing so does not increase the error substantially. We demonstrate that using symmetry produces results that are more aesthetically appealing and correspond more closely to human expectations, especially when simplifying to very few polygons.
A Streaming Algorithm for Surface Reconstruction
(The Eurographics Association, 2007) Allegre, Remi; Chaine, Raphaelle; Akkouche, Samir; Alexander Belyaev and Michael Garland
We present a streaming algorithm for reconstructing closed surfaces from large non-uniform point sets based on a geometric convection technique. Assuming that the sample points are organized into slices stacked along one coordinate axis, a triangle mesh can be efficiently reconstructed in a streamable layout with a controlled memory footprint. Our algorithm associates a streaming 3D Delaunay triangulation data-structure with a multilayer version of the geometric convection algorithm. Our method can process millions of sample points at the rate of 50k points per minute with 350 MB of main memory.
Developable Surfaces from Arbitrary Sketched Boundaries
(The Eurographics Association, 2007) Rose, Kenneth; Sheffer, Alla; Wither, Jamie; Cani, Marie-Paule; Thibert, Boris; Alexander Belyaev and Michael Garland
We present a method for extracting a hierarchical, rigid skeleton from a set of example poses. We then use this skeleton to not only reproduce the example poses, but create new deformations in the same style as the examples. Since rigid skeletons are used by most 3D modeling software, this skeleton and the corresponding vertex weights can be inserted directly into existing production pipelines. To create the skeleton, we first estimate the rigid transformations of the bones using a fast, face clustering approach. We present an efficient method for clustering by providing a Rigid Error Function that finds the best rigid transformation from a set of points in a robust, space efficient manner and supports fast clustering operations. Next, we solve for the vertex weights and enforce locality in the resulting weight distributions. Finally, we use these weights to determine the connectivity and joint locations of the skeleton.
Laplace-Beltrami Eigenfunctions for Deformation Invariant Shape Representation
(The Eurographics Association, 2007) Rustamov, Raif M.; Alexander Belyaev and Michael Garland
A deformation invariant representation of surfaces, the GPS embedding, is introduced using the eigenvalues and eigenfunctions of the Laplace-Beltrami differential operator. Notably, since the definition of the GPS embedding completely avoids the use of geodesic distances, and is based on objects of global character, the obtained representation is robust to local topology changes. The GPS embedding captures enough information to handle various shape processing tasks as shape classification, segmentation, and correspondence. To demonstrate the practical relevance of the GPS embedding, we introduce a deformation invariant shape descriptor called G2-distributions, and demonstrate their discriminative power, invariance under natural deformations, and robustness.
Example-Based Skeleton Extraction
(The Eurographics Association, 2007) Schaefer, Scott; Yuksel, Can; Alexander Belyaev and Michael Garland
We present a method for extracting a hierarchical, rigid skeleton from a set of example poses. We then use this skeleton to not only reproduce the example poses, but create new deformations in the same style as the examples. Since rigid skeletons are used by most 3D modeling software, this skeleton and the corresponding vertex weights can be inserted directly into existing production pipelines. To create the skeleton, we first estimate the rigid transformations of the bones using a fast, face clustering approach. We present an efficient method for clustering by providing a Rigid Error Function that finds the best rigid transformation from a set of points in a robust, space efficient manner and supports fast clustering operations. Next, we solve for the vertex weights and enforce locality in the resulting weight distributions. Finally, we use these weights to determine the connectivity and joint locations of the skeleton.
As-Rigid-As-Possible Surface Modeling
(The Eurographics Association, 2007) Sorkine, Olga; Alexa, Marc; Alexander Belyaev and Michael Garland
Modeling tasks, such as surface deformation and editing, can be analyzed by observing the local behavior of the surface. We argue that defining a modeling operation by asking for rigidity of the local transformations is useful in various settings. Such formulation leads to a non-linear, yet conceptually simple energy formulation, which is to be minimized by the deformed surface under particular modeling constraints. We devise a simple iterative mesh editing scheme based on this principle, that leads to detail-preserving and intuitive deformations. Our algorithm is effective and notably easy to implement, making it attractive for practical modeling applications.
Dynamic Geometry Registration
(The Eurographics Association, 2007) Mitra, Niloy J.; Floery, Simon; Ovsjanikov, Maks; Gelfand, Natasha; Guibas, Leonidas; Pottmann, Helmut; Alexander Belyaev and Michael Garland
We propose an algorithm that performs registration of large sets of unstructured point clouds of moving and deforming objects without computing correspondences. Given as input a set of frames with dense spatial and temporal sampling, such as the raw output of a fast scanner, our algorithm exploits the underlying temporal coherence in the data to directly compute the motion of the scanned object and bring all frames into a common coordinate system. In contrast with existing methods which usually perform pairwise alignments between consecutive frames, our algorithm computes a globally consistent motion spanning multiple frames. We add a time coordinate to all the input points based on the ordering of the respective frames and pose the problem of computing the motion of each frame as an estimation of certain kinematic properties of the resulting space-time surface. By performing this estimation for each frame as a whole we are able to compute rigid inter-frame motions, and by adapting our method to perform a local analysis of the space-time surface, we extend the basic algorithm to handle registration of deformable objects as well. We demonstrate the performance of our algorithm on a number of synthetic and scanned examples, each consisting of hundreds of scans.

Browse

Browsing SGP07: Eurographics Symposium on Geometry Processing by Issue Date

Results Per Page

Sort Options