SGP09: Eurographics Symposium on Geometry Processing
Permanent URI for this collection
Browse
Browsing SGP09: Eurographics Symposium on Geometry Processing by Issue Date
Now showing 1 - 20 of 27
Results Per Page
Sort Options
Item Stability of Curvature Measures(The Eurographics Association and Blackwell Publishing Ltd, 2009) Chazal, F.; Cohen-Steiner, D.; Lieutier, A.; Thibert, B.We address the problem of curvature estimation from sampled compact sets. The main contribution is a stability result: we show that the Gaussian, mean or anisotropic curvature measures of the offset of a compact set K with positive -reach can be estimated by the same curvature measures of the offset of a compact set K close to K in the Hausdorff sense. We show how these curvature measures can be computed for finite unions of balls. The curvature measures of the offset of a compact set with positive -reach can thus be approximated by the curvature measures of the offset of a point-cloud sample.Item Diamond Hierarchies of Arbitrary Dimension(The Eurographics Association and Blackwell Publishing Ltd, 2009) Weiss, Kenneth; De Floriani, LeilaNested simplicial meshes generated by the simplicial bisection decomposition proposed by Maubach [Mau95] have been widely used in 2D and 3D as multi-resolution models of terrains and three-dimensional scalar fields, They are an alternative to octree representation since they allow generating crack-free representations of the underlying field. On the other hand, this method generates conforming meshes only when all simplices sharing the bisection edge are subdivided concurrently. Thus, efficient representations have been proposed in 2D and 3D based on a clustering of the simplices sharing a common longest edge in what is called a diamond. These representations exploit the regularity of the vertex distribution and the diamond structure to yield an implicit encoding of the hierarchical and geometric relationships among the triangles and tetrahedra, respectively. Here, we analyze properties of d-dimensional diamonds to better understand the hierarchical and geometric relationships among the simplices generated by Maubach s bisection scheme and derive closed-form equations for the number of vertices, simplices, parents and children of each type of diamond. We exploit these properties to yield an implicit pointerless representation for d-dimensional diamonds and reduce the number of required neighbor-finding accesses from O(d!) to O(d).Item Discrete Critical Values: a General Framework for Silhouettes Computation(The Eurographics Association and Blackwell Publishing Ltd, 2009) Chazal, F.; Lieutier, A.; Montana, N.Many shapes resulting from important geometric operations in industrial applications such as Minkowski sums or volume swept by a moving object can be seen as the projection of higher dimensional objects. When such a higher dimensional object is a smooth manifold, the boundary of the projected shape can be computed from the critical points of the projection. In this paper, using the notion of polyhedral chains introduced by Whitney, we introduce a new general framework to define an analogous of the set of critical points of piecewise linear maps defined over discrete objects that can be easily computed. We illustrate our results by showing how they can be used to compute Minkowski sums of polyhedra and volumes swept by moving polyhedra.Item Feature preserving Delaunay mesh generation from 3D multi-material images(The Eurographics Association and Blackwell Publishing Ltd, 2009) Boltcheva, Dobrina; Yvinec, Mariette; Boissonnat, Jean-DanielGenerating realistic geometric models from 3D segmented images is an important task in many biomedical applications. Segmented 3D images impose particular challenges for meshing algorithms because they contain multi-material junctions forming features such as surface patches, edges and corners. The resulting meshes should preserve these features to ensure the visual quality and the mechanical soundness of the models. We present a feature preserving Delaunay refinement algorithm which can be used to generate high-quality tetrahedral meshes from segmented images. The idea is to explicitly sample corners and edges from the input image and to constrain the Delaunay refinement algorithm to preserve these features in addition to the surface patches. Our experimental results on segmented medical images have shown that, within a few seconds, the algorithm outputs a tetrahedral mesh in which each material is represented as a consistent submesh without gaps and overlaps. The optimization property of the Delaunay triangulation makes these meshes suitable for the purpose of realistic visualization or finite element simulations.Item Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram(The Eurographics Association and Blackwell Publishing Ltd, 2009) Yan, Dong-Ming; Levy, Bruno; Liu, Yang; Sun, Feng; Wang, WenpingWe propose a new isotropic remeshing method, based on Centroidal Voronoi Tessellation (CVT). Constructing CVT requires to repeatedly compute Restricted Voronoi Diagram (RVD), defined as the intersection between a 3D Voronoi diagram and an input mesh surface. Existing methods use some approximations of RVD. In this paper, we introduce an efficient algorithm that computes RVD exactly and robustly. As a consequence, we achieve better remeshing quality than approximation-based approaches, without sacrificing efficiency. Our method for RVD computation uses a simple procedure and a kd-tree to quickly identify and compute the intersection of each triangle face with its incident Voronoi cells. Its time complexity is O(mlog n), where n is the number of seed points and m is the number of triangles of the input mesh. Fast convergence of CVT is achieved using a quasi-Newton method, which proved much faster than Lloyd s iteration. Examples are presented to demonstrate the better quality of remeshing results with our method than with the state-of-art approaches.Item Filtering Relocations on a Delaunay Triangulation(The Eurographics Association and Blackwell Publishing Ltd, 2009) Manhaes de Castro, Pedro Machado; Tournois, Jane; Alliez, Pierre; Devillers, OlivierUpdating a Delaunay triangulation when its vertices move is a bottleneck in several domains of application. Rebuilding the whole triangulation from scratch is surprisingly a very viable option compared to relocating the vertices. This can be explained by several recent advances in efficient construction of Delaunay triangulations. However, when all points move with a small magnitude, or when only a fraction of the vertices move, rebuilding is no longer the best option. This paper considers the problem of efficiently updating a Delaunay triangulation when its vertices are moving under small perturbations. The main contribution is a set of filters based upon the concept of vertex tolerances. Experiments show that filtering relocations is faster than rebuilding the whole triangulation from scratch under certain conditions.Item Shape Analysis Using the Auto Diffusion Function(The Eurographics Association and Blackwell Publishing Ltd, 2009) Gebal, K.; Baerentzen, J. A.; Aanaes, H.; Larsen, R.Scalar functions defined on manifold triangle meshes is a starting point for many geometry processing algorithms such as mesh parametrization, skeletonization, and segmentation. In this paper, we propose the Auto Diffusion Function (ADF) which is a linear combination of the eigenfunctions of the Laplace-Beltrami operator in a way that has a simple physical interpretation. The ADF of a given 3D object has a number of further desirable properties: Its extrema are generally at the tips of features of a given object, its gradients and level sets follow or encircle features, respectively, it is controlled by a single parameter which can be interpreted as feature scale, and, finally, the ADF is invariant to rigid and isometric deformations.We describe the ADF and its properties in detail and compare it to other choices of scalar functions on manifolds. As an example of an application, we present a pose invariant, hierarchical skeletonization and segmentation algorithm which makes direct use of the ADF.Item Rotating Scans for Systematic Error Removal(The Eurographics Association and Blackwell Publishing Ltd, 2009) Abbasinejad, Fatemeh; Kil, Yong Joo; Sharf, Andrei; Amenta, NinaOptical triangulation laser scanners produce errors at surface discontinuities and sharp features. These systematic errors are anisotropic. We examine the causes of these errors theoretically, and we study the correlation of systematic error with edge size and orientation experimentally. We then present a novel processing method for removing systematic errors, by combining scans taken at several different orientations. We apply an anisotropic filter to the separate scans, and use it to weight the data in a final combination step. Unlike previous approaches, our method does not require access to the scanner s internal data or firmware. We demonstrate the technique on data from laser range scanners by two different manufacturers.Item Recovering Structure from r-Sampled Objects(The Eurographics Association and Blackwell Publishing Ltd, 2009) Aichholzer, O.; Aurenhammer, F.; Kornberger, B.; Plantinga, S.; Rote, G.; Sturm, A.; Vegter, G.For a surface in 3-space that is represented by a set S of sample points, we construct a coarse approximating polytope P that uses a subset of S as its vertices and preserves the topology of . In contrast to surface reconstruction we do not use all the sample points, but we try to use as few points as possible. Such a polytope P is useful as a seed polytope for starting an incremental refinement procedure to generate better and better approximations of based on interpolating subdivision surfaces or e.g. Bezier patches.Our algorithm starts from an r-sample S of . Based on S, a set of surface covering balls with maximal radii is calculated such that the topology is retained. From the weighted ?-shape of a proper subset of these highly overlapping surface balls we get the desired polytope. As there is a rather large range for the possible radii for the surface balls, the method can be used to construct triangular surfaces from point clouds in a scalable manner. We also briefly sketch how to combine parts of our algorithm with existing medial axis algorithms for balls, in order to compute stable medial axis approximations with scalable level of detail.Item Approximating Gradients for Meshes and Point Clouds via Diffusion Metric(The Eurographics Association and Blackwell Publishing Ltd, 2009) Luo, Chuanjiang; Safa, Issam; Wang, YusuThe gradient of a function defined on a manifold is perhaps one of the most important differential objects in data analysis. Most often in practice, the input function is available only at discrete points sampled from the underlying manifold, and the manifold is approximated by either a mesh or simply a point cloud. While many methods exist for computing gradients of a function defined over a mesh, computing and simplifying gradients and related quantities such as critical points, of a function from a point cloud is non-trivial.In this paper, we initiate the investigation of computing gradients under a different metric on the manifold from the original natural metric induced from the ambient space. Specifically, we map the input manifold to the eigenspace spanned by its Laplacian eigenfunctions, and consider the so-called diffusion distance metric associated with it. We show the relation of gradient under this metric with that under the original metric. It turns out that once the Laplace operator is constructed, it is easier to approximate gradients in the eigenspace for discrete inputs (especially point clouds) and it is robust to noises in the input function and in the underlying manifold. More importantly, we can easily smooth the gradient field at different scales within this eigenspace framework. We demonstrate the use of our new eigen-gradients with two applications: approximating / simplifying the critical points of a function, and the Jacobi sets of two input functions (which describe the correlation between these two functions), from point clouds data.Item Separatrix Persistence: Extraction of Salient Edges on Surfaces Using Topological Methods(The Eurographics Association and Blackwell Publishing Ltd, 2009) Weinkauf, T.; Guenther, D.Salient edges are perceptually prominent features of a surface. Most previous extraction schemes utilize the notion of ridges and valleys for their detection, thereby requiring curvature derivatives which are rather sensitive to noise. We introduce a novel method for salient edge extraction which does not depend on curvature derivatives. It is based on a topological analysis of the principal curvatures and salient edges of the surface are identified as parts of separatrices of the topological skeleton. Previous topological approaches obtain results including non-salient edges due to inherent properties of the underlying algorithms. We extend the profound theory by introducing the novel concept of separatrix persistence, which is a smooth measure along a separatrix and allows to keep its most salient parts only. We compare our results with other methods for salient edge extraction.Item Random Accessible Hierarchical Mesh Compression for Interactive Visualization(The Eurographics Association and Blackwell Publishing Ltd, 2009) Courbet, Clement; Hudelot, CelineThis paper presents a novel algorithm for hierarchical random accessible mesh decompression. Our approach progressively decompresses the requested parts of a mesh without decoding less interesting parts. Previous approaches divided a mesh into independently compressed charts and a base coarse mesh. We propose a novel hierarchical representation of the mesh. We build this representation by using a boundary-based approach to recursively split the mesh in two parts, under the constraint that any of the two resulting submeshes should be reconstructible independently.In addition to this decomposition technique, we introduce the concepts of opposite vertex and context dependant numbering. This enables us to achieve seemingly better compression ratios than previous work on quad and higher degree polygonal meshes. Our coder uses about 3 bits per polygon for connectivity and 14 bits per vertex for geometry using 12 bits quantification.Item Interior Distance Using Barycentric Coordinates(The Eurographics Association and Blackwell Publishing Ltd, 2009) Rustamov, R. M.; Lipman, Y.; Funkhouser, T.This paper introduces a framework for defining a shape-aware distance measure between any two points in the interior of a surface mesh. Our framework is based on embedding the surface mesh into a high-dimensional space in a way that best preserves boundary distances between vertices of the mesh, performing a mapping of the mesh volume into this high-dimensional space using barycentric coordinates, and defining the interior distance between any two points simply as their Euclidean distance in the embedding space. We investigate the theoretical properties of the interior distance in relation to properties of the chosen boundary distances and barycentric coordinates, and we investigate empirical properties of the interior distance using diffusion distance as the prescribed boundary distance and mean value coordinates. We prove theoretically that the interior distance is a metric, smooth, interpolating the boundary distances, and reproducing Euclidean distances, and we show empirically that it is insensitive to boundary noise and deformation and quick to compute. In case the barycentric coordinates are non-negative we also show a maximum principle exists. Finally, we use it to define a new geometric property, barycentroid of shape, and show that it captures the notion of semantic center of the shape.Item Frontmatter(The Eurographics Association and Blackwell Publishing Ltd, 2009)Item Multi-objective shape segmentation and labeling(The Eurographics Association and Blackwell Publishing Ltd, 2009) Simari, P.; Nowrouzezahrai, D.; Kalogerakis, E.; Singh, K.Shape segmentations designed for different applications show significant variation in the composition of their parts. In this paper, we introduce the segmentation and labeling of shape based on the simultaneous optimization of multiple heterogenous objectives that capture application-specific segmentation criteria. We present a number of efficient objective functions that capture useful shape adjectives (compact, flat, narrow, perpendicular, etc.) Segmentation descriptions within our framework combine multiple such objective functions with optional labels to define each part. The optimization problem is simplified by proposing weighted Voronoi partitioning as a compact and continuous parametrization of spatially embedded shape segmentations. Separation of spatially close but geodesically distant parts is made possible using multi-dimensional scaling prior to Voronoi partitioning. Optimization begins with an initial segmentation found using the centroids of a k-means clustering of surface elements. This partition is automatically labeled to optimize heterogeneous part objectives and the Voronoi centers and their weights optimized using Generalized Pattern Search. We illustrate our framework using several diverse segmentation applications: consistent segmentations with semantic labels, bounding volume hierarchies for path tracing, and automatic rig and clothing transfer between animation characters.Item Smoothing of Partition of Unity Implicit Surfaces for Noise Robust Surface Reconstruction(The Eurographics Association and Blackwell Publishing Ltd, 2009) Nagai, Yukie; Ohtake, Yutaka; Suzuki, HiromasaWe propose a novel method for smoothing partition of unity (PU) implicit surfaces consisting of sets of non-conforming linear functions with spherical supports. We derive new discrete differential operators and Laplacian smoothing using a spherical covering of PU as a grid-like data structure. These new differential operators are applied to the smoothing of PU implicit surfaces. First, Laplacian smoothing is performed for the vector field defined by the gradient of the PU implicit surface, which is then updated to reflect the smoothing of the gradient field. This process achieves a method for noise robust surface reconstruction from scattered points.Item Energy-Based Image Deformation(The Eurographics Association and Blackwell Publishing Ltd, 2009) Karni, Z.; Freedman, D.; Gotsman, C.We present a general approach to shape deformation based on energy minimization, and applications of this approach to the problems of image resizing and 2D shape deformation. Our deformation energy generalizes that found in the prior art, while still admitting an efficient algorithm for its optimization. The key advantage of our energy function is the flexibility with which the set of legal transformations may be expressed; these transformations are the ones which are not considered to be distorting. This flexibility allows us to pose the problems of image resizing and 2D shape deformation in a natural way and generate minimally distorted results. It also allows us to strongly reduce undesirable foldovers or self-intersections. Results of both algorithms demonstrate the effectiveness of our approach.Item Gromov-Hausdorff Stable Signatures for Shapes using Persistence(The Eurographics Association and Blackwell Publishing Ltd, 2009) Chazal, Frederic; Cohen-Steiner, David; Guibas, Leonidas J.; Memoli, Facundo; Oudot, Steve Y.We introduce a family of signatures for finite metric spaces, possibly endowed with real valued functions, based on the persistence diagrams of suitable filtrations built on top of these spaces. We prove the stability of our signatures under Gromov-Hausdorff perturbations of the spaces. We also extend these results to metric spaces equipped with measures. Our signatures are well-suited for the study of unstructured point cloud data, which we illustrate through an application in shape classification.Item Fast, Exact, Linear Booleans(The Eurographics Association and Blackwell Publishing Ltd, 2009) Bernstein, Gilbert; Fussell, DonWe present a new system for robustly performing Boolean operations on linear, 3D polyhedra. Our system is exact, meaning that all internal numeric predicates are exactly decided in the sense of exact geometric computation. Our BSP-tree based system is 16-28x faster at performing iterative computations than CGAL s Nef Polyhedra based system, the current best practice in robust Boolean operations, while being only twice as slow as the non-robust modeler Maya. Meanwhile, we achieve a much smaller substrate of geometric subroutines than previous work, comprised of only 4 predicates, a convex polygon constructor, and a convex polygon splitting routine. The use of a BSP-tree based Boolean algorithm atop this substrate allows us to explicitly handle all geometric degeneracies without treating a large number of cases.Item Reconstruction of Multi-Label Domains from Partial Planar Cross-Sections(The Eurographics Association and Blackwell Publishing Ltd, 2009) Barequet, Gill; Vaxman, AmirWe present a novel algorithm for reconstructing a subdivision of the three-dimensional space (given arbitrarily-oriented slices of it) into labeled domains. The input to the algorithm is a collection of nonparallel planar cross-sections of an unknown object, where the sections might cover only portions of the supporting planes. (The information in the rest of these planes is, thus, unknown. ) Each cross-section consists of a partition of the plane into closed labeled ( colored ) domains with no restrictions whatsoever on either their geometries or topologies, and without any assumptions about similarities between partitions of different sections. The problem is to reconstruct the original three-dimensional partition by interpolating simultaneously all the cross-sections, so that planar domains in the input are connected only to other domains of the same color, no two reconstructed spatial domains intersect, and no unnecessary gaps remain between the reconstructed colored domains.The problem of reconstructing multiple-labeled domains arises, for example, in medical imaging, where different types of tissues are scanned and reconstructed at the same time. Partial slices are typical, for example, in ultrasound scanning. In this work we use the three-dimensional straight-skeleton of the arrangement of the cross-sections. Since the sections might be partial, cells of the arrangement might be nonconvex. For this we use the unambiguous definition, as well as the implementation of the computation, of the straight skeleton of a three-dimensional polyhedron that we presented in a recent work [BEGV08]. First, we define these cells and compute their skeleton. Second, we compute overlays of portions of sampled contours in the cross-sections, using the cell skeletons to guide the reconstruction of the mesh.