SGP09: Eurographics Symposium on Geometry Processinghttps://diglib.eg.org/handle/10.2312/4382024-10-05T21:06:40Z2024-10-05T21:06:40Z271Separatrix Persistence: Extraction of Salient Edges on Surfaces Using Topological MethodsWeinkauf, T.Guenther, D.https://diglib.eg.org/handle/10.2312/CGF.v28i5pp1519-15282022-03-28T09:02:26Z2009-01-01T00:00:00Zdc.title: Separatrix Persistence: Extraction of Salient Edges on Surfaces Using Topological Methods
dc.contributor.author: Weinkauf, T.; Guenther, D.
dc.description.abstract: 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.
2009-01-01T00:00:00ZStability of Curvature MeasuresChazal, F.Cohen-Steiner, D.Lieutier, A.Thibert, B.https://diglib.eg.org/handle/10.2312/CGF.v28i5pp1485-14962022-03-28T09:02:35Z2009-01-01T00:00:00Zdc.title: Stability of Curvature Measures
dc.contributor.author: Chazal, F.; Cohen-Steiner, D.; Lieutier, A.; Thibert, B.
dc.description.abstract: 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.
2009-01-01T00:00:00ZDiscrete Critical Values: a General Framework for Silhouettes ComputationChazal, F.Lieutier, A.Montana, N.https://diglib.eg.org/handle/10.2312/CGF.v28i5pp1509-15182022-03-28T09:02:33Z2009-01-01T00:00:00Zdc.title: Discrete Critical Values: a General Framework for Silhouettes Computation
dc.contributor.author: Chazal, F.; Lieutier, A.; Montana, N.
dc.description.abstract: 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.
2009-01-01T00:00:00ZApproximating Gradients for Meshes and Point Clouds via Diffusion MetricLuo, ChuanjiangSafa, IssamWang, Yusuhttps://diglib.eg.org/handle/10.2312/CGF.v28i5pp1497-15082022-03-28T09:02:25Z2009-01-01T00:00:00Zdc.title: Approximating Gradients for Meshes and Point Clouds via Diffusion Metric
dc.contributor.author: Luo, Chuanjiang; Safa, Issam; Wang, Yusu
dc.description.abstract: 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.
2009-01-01T00:00:00ZEstimating the Laplace-Beltrami Operator by Restricting 3D FunctionsChuang, MingLuo, LinjieBrown, Benedict J.Rusinkiewicz, SzymonKazhdan, Michaelhttps://diglib.eg.org/handle/10.2312/CGF.v28i5pp1475-14842022-03-28T09:02:56Z2009-01-01T00:00:00Zdc.title: Estimating the Laplace-Beltrami Operator by Restricting 3D Functions
dc.contributor.author: Chuang, Ming; Luo, Linjie; Brown, Benedict J.; Rusinkiewicz, Szymon; Kazhdan, Michael
dc.description.abstract: 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.
2009-01-01T00:00:00ZFeature preserving Delaunay mesh generation from 3D multi-material imagesBoltcheva, DobrinaYvinec, MarietteBoissonnat, Jean-Danielhttps://diglib.eg.org/handle/10.2312/CGF.v28i5pp1455-14642022-03-28T09:02:30Z2009-01-01T00:00:00Zdc.title: Feature preserving Delaunay mesh generation from 3D multi-material images
dc.contributor.author: Boltcheva, Dobrina; Yvinec, Mariette; Boissonnat, Jean-Daniel
dc.description.abstract: 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.
2009-01-01T00:00:00ZFiltering Relocations on a Delaunay TriangulationManhaes de Castro, Pedro MachadoTournois, JaneAlliez, PierreDevillers, Olivierhttps://diglib.eg.org/handle/10.2312/CGF.v28i5pp1465-14742022-03-28T09:02:40Z2009-01-01T00:00:00Zdc.title: Filtering Relocations on a Delaunay Triangulation
dc.contributor.author: Manhaes de Castro, Pedro Machado; Tournois, Jane; Alliez, Pierre; Devillers, Olivier
dc.description.abstract: 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.
2009-01-01T00:00:00ZIsotropic Remeshing with Fast and Exact Computation of Restricted Voronoi DiagramYan, Dong-MingLevy, BrunoLiu, YangSun, FengWang, Wenpinghttps://diglib.eg.org/handle/10.2312/CGF.v28i5pp1445-14542022-03-28T09:02:23Z2009-01-01T00:00:00Zdc.title: Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram
dc.contributor.author: Yan, Dong-Ming; Levy, Bruno; Liu, Yang; Sun, Feng; Wang, Wenping
dc.description.abstract: 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.
2009-01-01T00:00:00ZMulti-objective shape segmentation and labelingSimari, P.Nowrouzezahrai, D.Kalogerakis, E.Singh, K.https://diglib.eg.org/handle/10.2312/CGF.v28i5pp1415-14252022-03-28T09:03:03Z2009-01-01T00:00:00Zdc.title: Multi-objective shape segmentation and labeling
dc.contributor.author: Simari, P.; Nowrouzezahrai, D.; Kalogerakis, E.; Singh, K.
dc.description.abstract: 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.
2009-01-01T00:00:00ZLocalized Quadrilateral CoarseningDaniels, JoelSilva, Claudio T.Cohen, Elainehttps://diglib.eg.org/handle/10.2312/CGF.v28i5pp1437-14442022-03-28T09:03:06Z2009-01-01T00:00:00Zdc.title: Localized Quadrilateral Coarsening
dc.contributor.author: Daniels, Joel; Silva, Claudio T.; Cohen, Elaine
dc.description.abstract: 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.
2009-01-01T00:00:00Z