28-Issue 5

Permanent URI for this collection

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

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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Rotating Scans for Systematic Error Removal
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Abbasinejad, Fatemeh; Kil, Yong Joo; Sharf, Andrei; Amenta, Nina
Optical 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.
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.
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.
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.
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.
Frontmatter
(The Eurographics Association and Blackwell Publishing Ltd, 2009)
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.
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, Hiromasa
We 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.
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.

Browse

Browsing 28-Issue 5 by Issue Date

Results Per Page

Sort Options