SGP09: Eurographics Symposium on Geometry Processing

Permanent URI for this collection

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

Browse

Now showing 1 - 20 of 27

Approximating Gradients for Meshes and Point Clouds via Diffusion Metric
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Luo, Chuanjiang; Safa, Issam; Wang, Yusu
The 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.
A Concise and Provably Informative Multi-Scale Signature Based on Heat Diffusion
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Sun, Jian; Ovsjanikov, Maks; Guibas, Leonidas
We propose a novel point signature based on the properties of the heat diffusion process on a shape. Our signature, called the Heat Kernel Signature (or HKS), is obtained by restricting the well-known heat kernel to the temporal domain. Remarkably we show that under certain mild assumptions, HKS captures all of the information contained in the heat kernel, and characterizes the shape up to isometry. This means that the restriction to the temporal domain, on the one hand, makes HKS much more concise and easily commensurable, while on the other hand, it preserves all of the information about the intrinsic geometry of the shape. In addition, HKS inherits many useful properties from the heat kernel, which means, in particular, that it is stable under perturbations of the shape. Our signature also provides a natural and efficiently computable multi-scale way to capture information about neighborhoods of a given point, which can be extremely useful in many applications. To demonstrate the practical relevance of our signature, we present several methods for non-rigid multi-scale matching based on the HKS and use it to detect repeated structure within the same shape and across a collection of shapes.
Diamond Hierarchies of Arbitrary Dimension
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Weiss, Kenneth; De Floriani, Leila
Nested 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).
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.
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.
Estimating the Laplace-Beltrami Operator by Restricting 3D Functions
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Chuang, Ming; Luo, Linjie; Brown, Benedict J.; Rusinkiewicz, Szymon; Kazhdan, Michael
We present a novel approach for computing and solving the Poisson equation over the surface of a mesh. As in previous approaches, we define the Laplace-Beltrami operator by considering the derivatives of functions defined on the mesh. However, in this work, we explore a choice of functions that is decoupled from the tessellation. Specifically, we use basis functions (second-order tensor-product B-splines) defined over 3D space, and then restrict them to the surface. We show that in addition to being invariant to mesh topology, this definition of the Laplace-Beltrami operator allows a natural multiresolution structure on the function space that is independent of the mesh structure, enabling the use of a simple multigrid implementation for solving the Poisson equation.
Fast, Exact, Linear Booleans
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Bernstein, Gilbert; Fussell, Don
We 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.
Feature preserving Delaunay mesh generation from 3D multi-material images
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Boltcheva, Dobrina; Yvinec, Mariette; Boissonnat, Jean-Daniel
Generating 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.
Filtering Relocations on a Delaunay Triangulation
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Manhaes de Castro, Pedro Machado; Tournois, Jane; Alliez, Pierre; Devillers, Olivier
Updating 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.
Frontmatter
(The Eurographics Association and Blackwell Publishing Ltd, 2009)
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.
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.
Isotopic Reconstruction of Surfaces with Boundaries
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Dey, Tamal K.; Li, Kuiyu; Ramos, Edgar A.; Wenger, Rephael
We present an algorithm for the reconstruction of a surface with boundaries (including a non-orientable one) in three dimensions from a sufficiently dense sample. It is guaranteed that the output is isotopic to the unknown sampled surface. No previously known algorithm guarantees isotopic or homeomorphic reconstruction of surfaces with boundaries. Our algorithm is surprisingly simple. It peels slivers greedily from an ?-complex of a sample of the surface. No other post-processing is necessary. We provide several experimental results from an implementation of our basic algorithm and also a modified version of it.
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, Wenping
We 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.
Localized Quadrilateral Coarsening
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Daniels, Joel; Silva, Claudio T.; Cohen, Elaine
In this paper we introduce a coarsening algorithm for quadrilateral meshes that generates quality, quad-only connectivity during level-of-coarsening creation. A novel aspect of this work is development and implementation of a localized adaptation of the polychord collapse operator to better control and preserve important surface components. We describe a novel weighting scheme for automatic deletion selection that considers surface attributes, as well as localized queue updates that allow for improved data structures and computational performance opportunities over previous techniques. Additionally, this work supports optional and intuitive user controls for tailored simplification results.
Manifold Homotopy via the Flow Complex
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Sadri, Bardia
It is known that the critical points of the distance function induced by a dense sample P of a submanifold ? of R?n are distributed into two groups, one lying close to ? itself, called the shallow, and the other close to medial axis of ?, called deep critical points. We prove that under (uniform) sampling assumption, the union of stable manifolds of the shallow critical points have the same homotopy type as ? itself and the union of the stable manifolds of the deep critical points have the homotopy type of the complement of ?. The separation of critical points under uniform sampling entails a separation in terms of distance of critical points to the sample. This means that if a given sample is dense enough with respect to two or more submanifolds of R?n, the homotopy types of all such submanifolds together with those of their complements are captured as unions of stable manifolds of shallow versus those of deep critical points, in a filtration of the flow complex based on the distance of critical points to the sample. This results in an algorithm for homotopic manifold reconstruction when the target dimension is unknown.
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.
Progressive Lossless Mesh Compression Via Incremental Parametric Refinement
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Valette, Sebastien; Chaine, Raphaelle; Prost, Remy
In this paper, we propose a novel progressive lossless mesh compression algorithm based on Incremental Parametric Refinement, where the connectivity is uncontrolled in a first step, yielding visually pleasing meshes at each resolution level while saving connectivity information compared to previous approaches. The algorithm starts with a coarse version of the original mesh, which is further refined by means of a novel refinement scheme. The mesh refinement is driven by a geometric criterion, in spirit with surface reconstruction algorithms, aiming at generating uniform meshes. The vertices coordinates are also quantized and transmitted in a progressive way, following a geometric criterion, efficiently allocating the bit budget. With this assumption, the generated intermediate meshes tend to exhibit a uniform sampling. The potential discrepancy between the resulting connectivity and the original one is corrected at the end of the algorithm. We provide a proof-of-concept implementation, yielding very competitive results compared to previous works in terms of rate/distortion trade-off.
Random Accessible Hierarchical Mesh Compression for Interactive Visualization
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Courbet, Clement; Hudelot, Celine
This 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.
Reconstruction of Multi-Label Domains from Partial Planar Cross-Sections
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Barequet, Gill; Vaxman, Amir
We 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.

Browse

Browsing SGP09: Eurographics Symposium on Geometry Processing by Title

Results Per Page

Sort Options