28-Issue 5

Permanent URI for this collection

https://diglib.eg.org/handle/10.2312/147
Geometry Processing Proceedings

BibTeX (28-Issue 5)
                
@article{
not assigned,

journal = {Computer Graphics Forum},
title = {{
Frontmatter}},

author = {},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
not assigned}

}
                
@article{
10.1111:j.1467-8659.2009.01503.x,

journal = {Computer Graphics Forum},
title = {{
Energy-Based Image Deformation}},

author = {
Karni, Z.
 and 
Freedman, D.
 and 
Gotsman, C.
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01503.x}

}
                
@article{
10.1111:j.1467-8659.2009.01504.x,

journal = {Computer Graphics Forum},
title = {{
Fast, Exact, Linear Booleans}},

author = {
Bernstein, Gilbert
 and 
Fussell, Don
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01504.x}

}
                
@article{
10.1111:j.1467-8659.2009.01506.x,

journal = {Computer Graphics Forum},
title = {{
Diamond Hierarchies of Arbitrary Dimension}},

author = {
Weiss, Kenneth
 and 
De Floriani, Leila
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01506.x}

}
                
@article{
10.1111:j.1467-8659.2009.01505.x,

journal = {Computer Graphics Forum},
title = {{
Interior Distance Using Barycentric Coordinates}},

author = {
Rustamov, R. M.
 and 
Lipman, Y.
 and 
Funkhouser, T.
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01505.x}

}
                
@article{
10.1111:j.1467-8659.2009.01507.x,

journal = {Computer Graphics Forum},
title = {{
Progressive Lossless Mesh Compression Via Incremental Parametric Refinement}},

author = {
Valette, Sebastien
 and 
Chaine, Raphaelle
 and 
Prost, Remy
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01507.x}

}
                
@article{
10.1111:j.1467-8659.2009.01508.x,

journal = {Computer Graphics Forum},
title = {{
Random Accessible Hierarchical Mesh Compression for Interactive Visualization}},

author = {
Courbet, Clement
 and 
Hudelot, Celine
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01508.x}

}
                
@article{
10.1111:j.1467-8659.2009.01509.x,

journal = {Computer Graphics Forum},
title = {{
Rotating Scans for Systematic Error Removal}},

author = {
Abbasinejad, Fatemeh
 and 
Kil, Yong Joo
 and 
Sharf, Andrei
 and 
Amenta, Nina
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01509.x}

}
                
@article{
10.1111:j.1467-8659.2009.01510.x,

journal = {Computer Graphics Forum},
title = {{
Reconstruction of Multi-Label Domains from Partial Planar Cross-Sections}},

author = {
Barequet, Gill
 and 
Vaxman, Amir
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01510.x}

}
                
@article{
10.1111:j.1467-8659.2009.01513.x,

journal = {Computer Graphics Forum},
title = {{
Manifold Homotopy via the Flow Complex}},

author = {
Sadri, Bardia
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01513.x}

}
                
@article{
10.1111:j.1467-8659.2009.01512.x,

journal = {Computer Graphics Forum},
title = {{
Recovering Structure from r-Sampled Objects}},

author = {
Aichholzer, O.
 and 
Aurenhammer, F.
 and 
Kornberger, B.
 and 
Plantinga, S.
 and 
Rote, G.
 and 
Sturm, A.
 and 
Vegter, G.
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01512.x}

}
                
@article{
10.1111:j.1467-8659.2009.01511.x,

journal = {Computer Graphics Forum},
title = {{
Smoothing of Partition of Unity Implicit Surfaces for Noise Robust Surface Reconstruction}},

author = {
Nagai, Yukie
 and 
Ohtake, Yutaka
 and 
Suzuki, Hiromasa
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01511.x}

}
                
@article{
10.1111:j.1467-8659.2009.01516.x,

journal = {Computer Graphics Forum},
title = {{
Gromov-Hausdorff Stable Signatures for Shapes using Persistence}},

author = {
Chazal, Frederic
 and 
Cohen-Steiner, David
 and 
Guibas, Leonidas J.
 and 
Memoli, Facundo
 and 
Oudot, Steve Y.
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01516.x}

}
                
@article{
10.1111:j.1467-8659.2009.01515.x,

journal = {Computer Graphics Forum},
title = {{
A Concise and Provably Informative Multi-Scale Signature Based on Heat Diffusion}},

author = {
Sun, Jian
 and 
Ovsjanikov, Maks
 and 
Guibas, Leonidas
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01515.x}

}
                
@article{
10.1111:j.1467-8659.2009.01514.x,

journal = {Computer Graphics Forum},
title = {{
Isotopic Reconstruction of Surfaces with Boundaries}},

author = {
Dey, Tamal K.
 and 
Li, Kuiyu
 and 
Ramos, Edgar A.
 and 
Wenger, Rephael
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01514.x}

}
                
@article{
10.1111:j.1467-8659.2009.01517.x,

journal = {Computer Graphics Forum},
title = {{
Shape Analysis Using the Auto Diffusion Function}},

author = {
Gebal, K.
 and 
Baerentzen, J. A.
 and 
Aanaes, H.
 and 
Larsen, R.
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01517.x}

}
                
@article{
10.1111:j.1467-8659.2009.01518.x,

journal = {Computer Graphics Forum},
title = {{
Multi-objective shape segmentation and labeling}},

author = {
Simari, P.
 and 
Nowrouzezahrai, D.
 and 
Kalogerakis, E.
 and 
Singh, K.
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01518.x}

}
                
@article{
10.1111:j.1467-8659.2009.01520.x,

journal = {Computer Graphics Forum},
title = {{
Localized Quadrilateral Coarsening}},

author = {
Daniels, Joel
 and 
Silva, Claudio T.
 and 
Cohen, Elaine
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01520.x}

}
                
@article{
10.1111:j.1467-8659.2009.01519.x,

journal = {Computer Graphics Forum},
title = {{
Semi-regular Quadrilateral-only Remeshing from Simplified Base Domains}},

author = {
Daniels, Joel
 and 
Silva, Claudio T.
 and 
Cohen, Elaine
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01519.x}

}
                
@article{
10.1111:j.1467-8659.2009.01521.x,

journal = {Computer Graphics Forum},
title = {{
Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram}},

author = {
Yan, Dong-Ming
 and 
Levy, Bruno
 and 
Liu, Yang
 and 
Sun, Feng
 and 
Wang, Wenping
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01521.x}

}
                
@article{
10.1111:j.1467-8659.2009.01523.x,

journal = {Computer Graphics Forum},
title = {{
Filtering Relocations on a Delaunay Triangulation}},

author = {
Manhaes de Castro, Pedro Machado
 and 
Tournois, Jane
 and 
Alliez, Pierre
 and 
Devillers, Olivier
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01523.x}

}
                
@article{
10.1111:j.1467-8659.2009.01522.x,

journal = {Computer Graphics Forum},
title = {{
Feature preserving Delaunay mesh generation from 3D multi-material images}},

author = {
Boltcheva, Dobrina
 and 
Yvinec, Mariette
 and 
Boissonnat, Jean-Daniel
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01522.x}

}
                
@article{
10.1111:j.1467-8659.2009.01524.x,

journal = {Computer Graphics Forum},
title = {{
Estimating the Laplace-Beltrami Operator by Restricting 3D Functions}},

author = {
Chuang, Ming
 and 
Luo, Linjie
 and 
Brown, Benedict J.
 and 
Rusinkiewicz, Szymon
 and 
Kazhdan, Michael
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01524.x}

}
                
@article{
10.1111:j.1467-8659.2009.01527.x,

journal = {Computer Graphics Forum},
title = {{
Discrete Critical Values: a General Framework for Silhouettes Computation}},

author = {
Chazal, F.
 and 
Lieutier, A.
 and 
Montana, N.
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01527.x}

}
                
@article{
10.1111:j.1467-8659.2009.01526.x,

journal = {Computer Graphics Forum},
title = {{
Approximating Gradients for Meshes and Point Clouds via Diffusion Metric}},

author = {
Luo, Chuanjiang
 and 
Safa, Issam
 and 
Wang, Yusu
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01526.x}

}
                
@article{
10.1111:j.1467-8659.2009.01525.x,

journal = {Computer Graphics Forum},
title = {{
Stability of Curvature Measures}},

author = {
Chazal, F.
 and 
Cohen-Steiner, D.
 and 
Lieutier, A.
 and 
Thibert, B.
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01525.x}

}
                
@article{
10.1111:j.1467-8659.2009.01528.x,

journal = {Computer Graphics Forum},
title = {{
Separatrix Persistence: Extraction of Salient Edges on Surfaces Using Topological Methods}},

author = {
Weinkauf, T.
 and 
Guenther, D.
},
year = {
2009},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2009.01528.x}

}

Browse

Recent Submissions

Now showing 1 - 27 of 27
  • Thumbnail Image
    Item
    Frontmatter
    (The Eurographics Association and Blackwell Publishing Ltd, 2009)
  • Thumbnail Image
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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).
  • Thumbnail Image
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    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.
  • Thumbnail Image
    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, 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.
  • Thumbnail Image
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    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.
  • Thumbnail Image
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    Semi-regular Quadrilateral-only Remeshing from Simplified Base Domains
    (The Eurographics Association and Blackwell Publishing Ltd, 2009) Daniels, Joel; Silva, Claudio T.; Cohen, Elaine
    Semi-regular meshes describe surface models that exhibit a structural regularity that facilitates many geometric processing algorithms. We introduce a technique to construct semi-regular, quad-only meshes from input surface meshes of arbitrary polygonal type and genus. The algorithm generates a quad-only model through subdivision of the input polygons, then simplifies to a base domain that is homeomorphic to the original mesh. During the simplification, a novel hierarchical mapping method, keyframe mapping, stores specific levels-of-detail to guide the mapping of the original vertices to the base domain. The algorithm implements a scheme for refinement with adaptive resampling of the base domain and backward projects to the original surface. As a byproduct of the remeshing scheme, a surface parameterization is associated with the remesh vertices to facilitate subsequent geometric processing, i.e. texture mapping, subdivision surfaces and spline-based modeling.
  • Thumbnail Image
    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, 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.
  • Thumbnail Image
    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, 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.
  • Thumbnail Image
    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-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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    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.
  • Thumbnail Image
    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.