Abstract We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex $${\mathscr {A}}$$ A , and a map H from the underlying space of $${\mathscr {A}}$$ A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of $${\mathscr {A}}$$ A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use.

Abstract We consider the following setting: suppose that we are given a manifold M in $${\mathbb {R}}^d$$ R d with positive reach. Moreover assume that we have an embedded simplical complex $${\mathcal {A}}$$ A without boundary, whose vertex set lies on the manifold, is sufficiently dense and such that all simplices in $${\mathcal {A}}$$ A have sufficient quality. We prove that if, locally, interiors of the projection of the simplices onto the tangent space do not intersect, then $${\mathcal {A}}$$ A is a triangulation of the manifold, that is, they are homeomorphic.

We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex A, and a map H from the underlying space of A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use.

Delaunay has shown that the Delaunay complex of a finite set of points $$P$$ of Euclidean space $$\mathbb {R}^m$$ triangulates the convex hull of $$P,$$ provided that $$P$$ satisfies a mild genericity property. Voronoi diagrams and Delaunay complexes can be defined for arbitrary Riemannian manifolds. However, Delaunay’s genericity assumption no longer guarantees that the Delaunay complex will yield a triangulation; stronger assumptions on $$P$$ are required. A natural one is to assume that $$P$$ is sufficiently dense. Although results in this direction have been claimed, we show that sample density alone is insufficient to ensure that the Delaunay complex triangulates a manifold of dimension greater than 2.

We study a natural intrinsic definition of geometric simplices in Riemannian manifolds of arbitrary finite dimension, and exploit these simplices to obtain criteria for triangulating compact Riemannian manifolds. These geometric simplices are defined using Karcher means. Given a finite set of vertices in a convex set on the manifold, the point that minimises the weighted sum of squared distances to the vertices is the Karcher mean relative to the weights. Using barycentric coordinates as the weights, we obtain a smooth map from the standard Euclidean simplex to the manifold. A Riemannian simplex is defined as the image of the standard simplex under this barycentric coordinate map. In this work we articulate criteria that guarantee that the barycentric coordinate map is a smooth embedding. If it is not, we say the Riemannian simplex is degenerate. Quality measures for the "thickness" or "fatness" of Euclidean simplices can be adapted to apply to these Riemannian simplices. For manifolds of dimension 2, the simplex is non-degenerate if it has a positive quality measure, as in the Euclidean case. However, when the dimension is greater than two, non-degeneracy can be guaranteed only when the quality exceeds a positive bound that depends on the size of the simplex and local bounds on the absolute values of the sectional curvatures of the manifold. An analysis of the geometry of non-degenerate Riemannian simplices leads to conditions which guarantee that a simplicial complex is homeomorphic to the manifold.

We introduce a parametrized notion of genericity for Delaunay triangulations which, in particular, implies that the Delaunay simplices of δ-generic point sets are thick. Equipped with this notion, we study the stability of Delaunay triangulations under perturbations of the metric and of the vertex positions. We then show that, for any sufficiently regular submanifold of Euclidean space, and appropriate ε and δ, any sample set which meets a localized δ-generic ε-dense sampling criteria yields a manifold intrinsic Delaunay complex which is equal to the restricted Delaunay complex.

We present an algorithm for multi-scale partial intrinsic symmetry detection over 2D and 3D shapes, where the scale of a symmetric region is defined by intrinsic distances between symmetric points over the region. To identify prominent symmetric regions which overlap and vary in form and scale, we decouple scale extraction and symmetry extraction by performing two levels of clustering. First, significant symmetry scales are identified by clustering sample point pairs from an input shape. Since different point pairs can share a common point, shape regions covered by points in different scale clusters can overlap. We introduce the symmetry scale matrix (SSM), where each entry estimates the likelihood two point pairs belong to symmetries at the same scale. The pair-to-pair symmetry affinity is computed based on a pair signature which encodes scales. We perform spectral clustering using the SSM to obtain the scale clusters. Then for all points belonging to the same scale cluster, we perform the second-level spectral clustering, based on a novel point-to-point symmetry affinity measure, to extract partial symmetries at that scale. We demonstrate our algorithm on complex shapes possessing rich symmetries at multiple scales.

Abstract Spectral methods for mesh processing and analysis rely on the eigenvalues, eigenvectors, or eigenspace projections derived from appropriately defined mesh operators to carry out desired tasks. Early work in this area can be traced back to the seminal paper by Taubin in 1995, where spectral analysis of mesh geometry based on a combinatorial Laplacian aids our understanding of the low‐pass filtering approach to mesh smoothing. Over the past 15 years, the list of applications in the area of geometry processing which utilize the eigenstructures of a variety of mesh operators in different manners have been growing steadily. Many works presented so far draw parallels from developments in fields such as graph theory, computer vision, machine learning, graph drawing, numerical linear algebra, and high‐performance computing. This paper aims to provide a comprehensive survey on the spectral approach, focusing on its power and versatility in solving geometry processing problems and attempting to bridge the gap between relevant research in computer graphics and other fields. Necessary theoretical background is provided. Existing works covered are classified according to different criteria: the operators or eigenstructures employed, application domains, or the dimensionality of the spectral embeddings used. Despite much empirical success, there still remain many open questions pertaining to the spectral approach. These are discussed as we conclude the survey and provide our perspective on possible future research.

We undertake a study of the local properties of 2-Gabriel meshes: manifold triangle meshes each of whose faces has an open Euclidean diametric ball that contains no mesh vertices. We show that, under mild constraints on the dihedral angles, such meshes are Delaunay meshes: the open geodesic circumdisk of each face contains no mesh vertex.

Abstract We develop adaptive sampling criteria which guarantee a topologically faithful mesh and demonstrate an improvement and simplification over earlier results, albeit restricted to 2D surfaces. These sampling criteria are based on functions defined by intrinsic properties of the surface: the strong convexity radius and the injectivity radius. We establish inequalities that relate these functions to the local feature size, thus enabling a comparison between the demands of the intrinsic sampling criteria and those based on Euclidean distances and the medial axis.

In this paper, we are concerned with Delaunay triangulations of the vertex set of a piecewise flat (pwf) surface. We first propose the notion of well-formed Voronoi diagrams and establish a precise dual relationship between them and proper Delaunay triangulations on pwf surfaces. Then we provide an algorithm which, given any input manifold triangle mesh, constructs a Delaunay mesh: a manifold triangle mesh whose edges form an intrinsic Delaunay triangulation of its vertex set. Rather than relying on a geodesic Delaunay triangulation on the input mesh, our algorithm swaps the physical mesh edges based on the locally Delaunay criterion. We prove that when a physical edge that is not locally Delaunay is swapped, the surface area of the mesh is reduced. In order to ensure a proper Delaunay triangulation, some new vertices may need to be introduced, leading to a refinement scheme, and we detail the cases involved.

We derive piecewise linear and piecewise cubic box spline reconstruction filters for data sampled on the body centered cubic (BCC) lattice. We analytically derive a time domain representation of these reconstruction filters and using the Fourier slice-projection theorem we derive their frequency responses. The quality of these filters, when used in reconstructing BCC sampled volumetric data, is discussed and is demonstrated with a raycaster. Moreover, to demonstrate the superiority of the BCC sampling, the resulting reconstructions are compared with those produced from similar filters applied to data sampled on the Cartesian lattice.