SGP07: Eurographics Symposium on Geometry Processing
Permanent URI for this collection
Robust Statistical Estimation of Curvature on Discretized Surfaces
[meta data] [files:
Kalogerakis, Evangelos
;
Simari, Patricio
;
Nowrouzezahrai, Derek
;
Singh, Karan
Focal Surfaces of Discrete Geometry
[meta data] [files:
Yu, Jingyi
;
Yin, Xiaotian
;
Gu, Xianfeng
;
McMillan, Leonard
;
Gortler, Steven
Discrete Laplace operators: No free lunch
[meta data] [files:
Wardetzky, Max
;
Mathur, Saurabh
;
Kaelberer, Felix
;
Grinspun, Eitan
Voronoi-based Variational Reconstruction of Unoriented Point Sets
[meta data] [files:
Alliez, Pierre
;
Cohen-Steiner, David
;
Tong, Yiying
;
Desbrun, Mathieu
Reconstruction of Deforming Geometry from Time-Varying Point Clouds
[meta data] [files:
Wand, Michael
;
Jenke, Philipp
;
Huang, Qixing
;
Bokeloh, Martin
;
Guibas, Leonidas
;
Schilling, Andreas
Data-Dependent MLS for Faithful Surface Approximation
[meta data] [files:
Lipman, Yaron
;
Cohen-Or, Daniel
;
Levin, David
Shape Reconstruction from Unorganized Cross-sections
[meta data] [files:
Boissonnat, Jean-Daniel
;
Memari, Pooran
A Streaming Algorithm for Surface Reconstruction
[meta data] [files:
Allegre, Remi
;
Chaine, Raphaelle
;
Akkouche, Samir
Multilevel Streaming for Out-of-Core Surface Reconstruction
[meta data] [files:
Bolitho, Matthew
;
Kazhdan, Michael
;
Burns, Randal
;
Hoppe, Hugues
Elastic Secondary Deformations by Vector Field Integration
[meta data] [files:
Funck, Wolfram von
;
Theisel, Holger
;
Seidel, Hans-Peter
Triangulations with Locally Optimal Steiner Points
[meta data] [files:
Erten, Hale
;
Uengoer, Alper
Unconstrained Isosurface Extraction on Arbitrary Octrees
[meta data] [files:
Kazhdan, Michael
;
Klein, Allison
;
Dalal, Ketan
;
Hoppe, Hugues
Linear Angle Based Parameterization
Zayer, Rhaleb
;
Levy, Bruno
;
Seidel, Hans-Peter
GPU-assisted Positive Mean Value Coordinates for Mesh Deformations
[meta data] [files:
Lipman, Yaron
;
Kopf, Johannes
;
Cohen-Or, Daniel
;
Levin, David
Developable Surfaces from Arbitrary Sketched Boundaries
[meta data] [files:
Rose, Kenneth
;
Sheffer, Alla
;
Wither, Jamie
;
Cani, Marie-Paule
;
Thibert, Boris
Generalized Surface Flows for Mesh Processing
[meta data] [files:
Eckstein, Ilya
;
Pons, Jean-Philippe
;
Tong, Yiying
;
Kuo, C.-C. Jay
;
Desbrun, Mathieu
Dynamic Geometry Registration
[meta data] [files:
Mitra, Niloy J.
;
Floery, Simon
;
Ovsjanikov, Maks
;
Gelfand, Natasha
;
Guibas, Leonidas
;
Pottmann, Helmut
Shape Optimization Using Reflection Lines
[meta data] [files:
Tosun, Elif
;
Gingold, Yotam I.
;
Reisman, Jason
;
Zorin, Denis
Constraint-based Fairing of Surface Meshes
[meta data] [files:
Hildebrandt, Klaus
;
Polthier, Konrad
Symmetry-Enhanced Remeshing of Surfaces
[meta data] [files:
Podolak, Joshua
;
Golovinskiy, Aleksey
;
Rusinkiewicz, Szymon
Laplace-Beltrami Eigenfunctions for Deformation Invariant Shape Representation
[meta data] [files:
Rustamov, Raif M.
Bayesian Surface Reconstruction via Iterative Scan Alignment to an Optimized Prototype
[meta data] [files:
Huang, Qi-Xing
;
Adams, Bart
;
Wand, Michael
Fast Normal Vector Compression with Bounded Error
[meta data] [files:
Griffith, E. J.
;
Koutek, M.
;
Post, Frits H.
Surface Reconstruction using Local Shape Priors
[meta data] [files:
Gal, Ran
;
Shamir, Ariel
;
Hassner, Tal
;
Pauly, Mark
;
Or, Daniel Cohen
Ridge Based Curve and Surface Reconstruction
[meta data] [files:
Suessmuth, Jochen
;
Greiner, Guenther
Browse
Recent Submissions
Item Robust Statistical Estimation of Curvature on Discretized Surfaces(The Eurographics Association, 2007) Kalogerakis, Evangelos; Simari, Patricio; Nowrouzezahrai, Derek; Singh, Karan; Alexander Belyaev and Michael GarlandA 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.Item Focal Surfaces of Discrete Geometry(The Eurographics Association, 2007) Yu, Jingyi; Yin, Xiaotian; Gu, Xianfeng; McMillan, Leonard; Gortler, Steven; Alexander Belyaev and Michael GarlandThe 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.Item Discrete Laplace operators: No free lunch(The Eurographics Association, 2007) Wardetzky, Max; Mathur, Saurabh; Kaelberer, Felix; Grinspun, Eitan; Alexander Belyaev and Michael GarlandDiscrete 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.Item 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 GarlandWe 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.Item 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 GarlandIn 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.Item Data-Dependent MLS for Faithful Surface Approximation(The Eurographics Association, 2007) Lipman, Yaron; Cohen-Or, Daniel; Levin, David; Alexander Belyaev and Michael GarlandIn 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.Item Shape Reconstruction from Unorganized Cross-sections(The Eurographics Association, 2007) Boissonnat, Jean-Daniel; Memari, Pooran; Alexander Belyaev and Michael GarlandIn 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.Item A Streaming Algorithm for Surface Reconstruction(The Eurographics Association, 2007) Allegre, Remi; Chaine, Raphaelle; Akkouche, Samir; Alexander Belyaev and Michael GarlandWe 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.Item Multilevel Streaming for Out-of-Core Surface Reconstruction(The Eurographics Association, 2007) Bolitho, Matthew; Kazhdan, Michael; Burns, Randal; Hoppe, Hugues; Alexander Belyaev and Michael GarlandReconstruction 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.Item Elastic Secondary Deformations by Vector Field Integration(The Eurographics Association, 2007) Funck, Wolfram von; Theisel, Holger; Seidel, Hans-Peter; Alexander Belyaev and Michael GarlandWe 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.Item As-Rigid-As-Possible Surface Modeling(The Eurographics Association, 2007) Sorkine, Olga; Alexa, Marc; Alexander Belyaev and Michael GarlandModeling 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.Item Triangulations with Locally Optimal Steiner Points(The Eurographics Association, 2007) Erten, Hale; Uengoer, Alper; Alexander Belyaev and Michael GarlandWe 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 aItem Unconstrained Isosurface Extraction on Arbitrary Octrees(The Eurographics Association, 2007) Kazhdan, Michael; Klein, Allison; Dalal, Ketan; Hoppe, Hugues; Alexander Belyaev and Michael GarlandThis 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.Item Linear Angle Based Parameterization(The Eurographics Association, 2007) Zayer, Rhaleb; Levy, Bruno; Seidel, Hans-Peter; Alexander Belyaev and Michael GarlandIn the field of mesh parameterization, the impact of angular and boundary distortion on parameterization quality have brought forward the need for robust and efficient free boundary angle preserving methods. One of the most prominent approaches in this direction is the Angle Based Flattening (ABF) which directly formulates the problem as a constrained nonlinear optimization in terms of angles. Since the original formulation of the ABF, a steady research effort has been dedicated to improving its efficiency. As for any well posed numerical problem, the solution is generally an approximation of the underlying mathematical equations. The economy and accuracy of the solution are to a great extent affected by the kind of approximation used. In this work we reformulate the problem based on the notion of error of estimation. A careful manipulation of the resulting equations yields for the first time a linear version of angle based parameterization. The error induced by this linearization is quadratic in terms of the error in angles and the validity of the approximation is further supported by numerical results. Besides performance speedup, the simplicity of the current setup makes re-implementation and reproduction of our results straightforward.Item GPU-assisted Positive Mean Value Coordinates for Mesh Deformations(The Eurographics Association, 2007) Lipman, Yaron; Kopf, Johannes; Cohen-Or, Daniel; Levin, David; Alexander Belyaev and Michael GarlandIn this paper we introduce positive mean value coordinates (PMVC) for mesh deformation. Following the observations of Joshi et al. [JMD*07] we show the advantage of having positive coordinates. The control points of the deformation are the vertices of a "cage" enclosing the deformed mesh. To define positive mean value coordinates for a given vertex, the visible portion of the cage is integrated over a sphere. Unlike MVC [JSW05], PMVC are computed numerically. We show how the PMVC integral can be efficiently computed with graphics hardware. While the properties of PMVC are similar to those of Harmonic coordinates [JMD*07], the setup time of the PMVC is only of a few seconds for typical meshes with 30K vertices. This speed-up renders the new coordinates practical and easy to use.Item Example-Based Skeleton Extraction(The Eurographics Association, 2007) Schaefer, Scott; Yuksel, Can; Alexander Belyaev and Michael GarlandWe 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.Item 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 GarlandWe 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.Item 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 GarlandGeometric 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.Item Dynamic Geometry Registration(The Eurographics Association, 2007) Mitra, Niloy J.; Floery, Simon; Ovsjanikov, Maks; Gelfand, Natasha; Guibas, Leonidas; Pottmann, Helmut; Alexander Belyaev and Michael GarlandWe 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.Item Shape Optimization Using Reflection Lines(The Eurographics Association, 2007) Tosun, Elif; Gingold, Yotam I.; Reisman, Jason; Zorin, Denis; Alexander Belyaev and Michael GarlandMany 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.Item Constraint-based Fairing of Surface Meshes(The Eurographics Association, 2007) Hildebrandt, Klaus; Polthier, Konrad; Alexander Belyaev and Michael GarlandWe 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.Item Symmetry-Enhanced Remeshing of Surfaces(The Eurographics Association, 2007) Podolak, Joshua; Golovinskiy, Aleksey; Rusinkiewicz, Szymon; Alexander Belyaev and Michael GarlandWhile 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.Item Laplace-Beltrami Eigenfunctions for Deformation Invariant Shape Representation(The Eurographics Association, 2007) Rustamov, Raif M.; Alexander Belyaev and Michael GarlandA 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.Item 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 GarlandThis 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.Item Fast Normal Vector Compression with Bounded Error(The Eurographics Association, 2007) Griffith, E. J.; Koutek, M.; Post, Frits H.; Alexander Belyaev and Michael GarlandWe 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.Item 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 GarlandWe 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.Item Delaunay Mesh Construction(The Eurographics Association, 2007) Dyer, Ramsay; Zhang, Hao; Moeller, Torsten; Alexander Belyaev and Michael GarlandWe 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.Item Ridge Based Curve and Surface Reconstruction(The Eurographics Association, 2007) Suessmuth, Jochen; Greiner, Guenther; Alexander Belyaev and Michael GarlandThis 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.