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

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.
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.
Multilevel Streaming for Out-of-Core Surface Reconstruction
(The Eurographics Association, 2007) Bolitho, Matthew; Kazhdan, Michael; Burns, Randal; Hoppe, Hugues; Alexander Belyaev and Michael Garland
Reconstruction of surfaces from huge collections of scanned points often requires out-of-core techniques, and most such techniques involve local computations that are not resilient to data errors. We show that a Poisson-based reconstruction scheme, which considers all points in a global analysis, can be performed efficiently in limited memory using a streaming framework. Specifically, we introduce a multilevel streaming representation, which enables efficient traversal of a sparse octree by concurrently advancing through multiple streams, one per octree level. Remarkably, for our reconstruction application, a sufficiently accurate solution to the global linear system is obtained using a single iteration of cascadic multigrid, which can be evaluated within a single multi-stream pass. We demonstrate scalable performance on several large datasets.
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.
Bayesian Surface Reconstruction via Iterative Scan Alignment to an Optimized Prototype
(The Eurographics Association, 2007) Huang, Qi-Xing; Adams, Bart; Wand, Michael; Alexander Belyaev and Michael Garland
This paper introduces a novel technique for joint surface reconstruction and registration. Given a set of roughly aligned noisy point clouds, it outputs a noise-free and watertight solid model. The basic idea of the new technique is to reconstruct a prototype surface at increasing resolution levels, according to the registration accuracy obtained so far, and to register all parts with this surface. We derive a non-linear optimization problem from a Bayesian formulation of the joint estimation problem. The prototype surface is represented as a partition of unity implicit surface, which is constructed from piecewise quadratic functions defined on octree cells and blended together using B-spline basis functions, allowing the representation of objects with arbitrary topology with high accuracy. We apply the new technique to a set of standard data sets as well as especially challenging real-world cases. In practice, the novel prototype surface based joint reconstruction-registration algorithm avoids typical convergence problems in registering noisy range scans and substantially improves the accuracy of the final output.
Delaunay Mesh Construction
(The Eurographics Association, 2007) Dyer, Ramsay; Zhang, Hao; Moeller, Torsten; Alexander Belyaev and Michael Garland
We present algorithms to produce Delaunay meshes from arbitrary triangle meshes by edge flipping and geometrypreserving refinement and prove their correctness. In particular we show that edge flipping serves to reduce mesh surface area, and that a poorly sampled input mesh may yield unflippable edges necessitating refinement to ensure a Delaunay mesh output. Multiresolution Delaunay meshes can be obtained via constrained mesh decimation. We further examine the usefulness of trading off the geometry-preserving feature of our algorithm with the ability to create fewer triangles. We demonstrate the performance of our algorithms through several experiments.
Shape Optimization Using Reflection Lines
(The Eurographics Association, 2007) Tosun, Elif; Gingold, Yotam I.; Reisman, Jason; Zorin, Denis; Alexander Belyaev and Michael Garland
Many common objects have highly reflective metallic or painted finishes. Their appearance is primarily defined by the distortion the curved shape of the surface introduces in the reflections of surrounding objects. Reflection lines are commonly used for surface interrogation, as they capture many essential aspects of reflection distortion directly, and clearly show surface imperfections that may be hard to see with conventional lighting. In this paper, we propose the use of functionals based on reflection lines for mesh optimization and editing. We describe a simple and efficient discretization of such functionals based on screen-space surface parameterization, and we demonstrate how such discrete functionals can be used for several types of surface editing operations.
Voronoi-based Variational Reconstruction of Unoriented Point Sets
(The Eurographics Association, 2007) Alliez, Pierre; Cohen-Steiner, David; Tong, Yiying; Desbrun, Mathieu; Alexander Belyaev and Michael Garland
We introduce an algorithm for reconstructing watertight surfaces from unoriented point sets. Using the Voronoi diagram of the input point set, we deduce a tensor field whose principal axes and eccentricities locally represent respectively the most likely direction of the normal to the surface, and the confidence in this direction estimation. An implicit function is then computed by solving a generalized eigenvalue problem such that its gradient is most aligned with the principal axes of the tensor field, providing a best-fitting isosurface reconstruction. Our approach possesses a number of distinguishing features. In particular, the implicit function optimization provides resilience to noise, adjustable fitting to the data, and controllable smoothness of the reconstructed surface. Finally, the use of simplicial meshes (possibly restricted to a thin crust around the input data) and (an)isotropic Laplace operators renders the numerical treatment simple and robust.
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.
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.
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.
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.
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.
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.
Triangulations with Locally Optimal Steiner Points
(The Eurographics Association, 2007) Erten, Hale; Uengoer, Alper; Alexander Belyaev and Michael Garland
We present two new Delaunay refinement algorithms, the second an extension of the first. For a given input domain (a set of points in the plane or a planar straight line graph), and a threshold angle a, the Delaunay refinement algorithms compute triangulations that have all angles at least a. Our algorithms have the same theoretical guarantees as the previous Delaunay refinement algorithms. The original Delaunay refinement algorithm of Ruppert is proven to terminate with size-optimal quality triangulations for a
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.
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.
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.
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.
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.

Browse

Browsing SGP07: Eurographics Symposium on Geometry Processing by Issue Date

Results Per Page

Sort Options