The medial axis transform has long been known as an intrinsic shape representation supporting a variety of shape analysis and synthesis tasks. However, for a given shape, it is hard to obtain its faithful, concise and stable medial axis, which hinders the application of the medial axis. In this paper, we introduce the medial mesh, a new discrete representation of the medial axis. A medial mesh is a 2D simplicial complex coupled with a radius function that provides a piecewise linear approximation to the medial axis. We further present an effective algorithm for computing a concise and stable medial mesh for a given shape. Our algorithm is quantitatively driven by a shape approximation error metric, and progressively simplifies an initial medial mesh by iteratively contracting edges until the approximation error reaches a predefined threshold. We further demonstrate the superior efficiency and accuracy of our method over existing methods for medial axis simplification.

The medial axis transform (MAT) is an important shape representation for shape approximation, shape recognition, and shape retrieval. Despite years of research, there is still a lack of effective methods for efficient, robust and accurate computation of the MAT. We present an efficient method, called Q-MAT , that uses quadratic error minimization to compute a structurally simple, geometrically accurate, and compact representation of the MAT. We introduce a new error metric for approximation and a new quantitative characterization of unstable branches of the MAT, and integrate them in an extension of the well-known quadric error metric (QEM) framework for mesh decimation. Q-MAT is fast, removes insignificant unstable branches effectively, and produces a simple and accurate piecewise linear approximation of the MAT. The method is thoroughly validated and compared with existing methods for MAT computation.

Existing methods for surface quadrangulation cannot ensure accurate alignment with feature or boundary curves and tight control of local element size, which are important requirements in many numerical applications (e.g., FEA). Some methods rely on a prescribed direction field to guide quadrangulation for feature alignment, but such a direction field may conflict with a desired density field, thus making it difficult to control the element size. We propose a new spectral method that achieves both accurate feature curve alignment and tight control of local element size according to a given density field. Specifically, the following three technical contributions are made. First, to make the quadrangulation align accurately with feature curves or surface boundary curves, we introduce novel boundary conditions for wave-like functions that satisfy the Helmholtz equation approximately in the least squares sense. Such functions, called quasi-eigenfunctions , are computed efficiently as the solutions to a variational problem. Second, the mesh element size is effectively controlled by locally modulating the Laplace operator in the Helmholtz equation according to a given density field. Third, to improve robustness, we propose a novel scheme to minimize the vibration difference of the quasi-eigenfunction in two orthogonal directions. It is demonstrated by extensive experiments that our method outperforms previous methods in generating feature-aligned quadrilateral meshes with tight control of local elememt size. We further present some preliminary results to show that our method can be extended to generating hex-dominant volume meshes.

This paper introduces a particle-based approach for anisotropic surface meshing. Given an input polygonal mesh endowed with a Riemannian metric and a specified number of vertices, the method generates a metric-adapted mesh. The main idea consists of mapping the anisotropic space into a higher dimensional isotropic one, called "embedding space". The vertices of the mesh are generated by uniformly sampling the surface in this higher dimensional embedding space, and the sampling is further regularized by optimizing an energy function with a quasi-Newton algorithm. All the computations can be re-expressed in terms of the dot product in the embedding space, and the Jacobian matrices of the mappings that connect different spaces. This transform makes it unnecessary to explicitly represent the coordinates in the embedding space, and also provides all necessary expressions of energy and forces for efficient computations. Through energy optimization, it naturally leads to the desired anisotropic particle distributions in the original space. The triangles are then generated by computing the Restricted Anisotropic Voronoi Diagram and its dual Delaunay triangulation. We compare our results qualitatively and quantitatively with the state-of-the-art in anisotropic surface meshing on several examples, using the standard measurement criteria.

Centroidal Voronoi Tessellation (CVT) is a widely used geometric structure in applications including mesh generation, vector quantization and image processing. Global optimization of the CVT function is important in these applications. With numerical evidences, we show that the CVT function is highly nonconvex and has many local minima and therefore the global optimization of the CVT function is nontrivial. We apply the method of Monte Carlo with Minimization (MCM) to optimizing the CVT function globally and demonstrate its efficacy in producing much improved results compared with two other global optimization methods.

Abstract Updating a Delaunay triangulation when data points are slightly moved is the bottleneck of computation time in variational methods for mesh generation and remeshing. Utilizing the connectivity coherence between two consecutive Delaunay triangulations for computation speedup is the key to solving this problem. Our contribution is an effective filtering technique that confirms most bi‐cells whose Delaunay connectivities remain unchanged after the points are perturbed. Based on bi‐cell flipping, we present an efficient algorithm for updating two‐dimensional and three‐dimensional Delaunay triangulations of dynamic point sets. Experimental results show that our algorithm outperforms previous methods.

Abstract We propose a new isotropic remeshing method, based onCentroidal Voronoi Tessellation (CVT). Constructing CVT requires to repeatedly computeRestricted 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 akd‐tree to quickly identify and compute the intersection of each triangle face with its incident Voronoi cells. Its time complexity isO(mlogn), wherenis the number of seed points andmis 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.

Centroidal Voronoi tessellation (CVT) is a particular type of Voronoi tessellation that has many applications in computational sciences and engineering, including computer graphics. The prevailing method for computing CVT is Lloyd's method, which has linear convergence and is inefficient in practice. We develop new efficient methods for CVT computation and demonstrate the fast convergence of these methods. Specifically, we show that the CVT energy function has 2nd order smoothness for convex domains with smooth density, as well as in most situations encountered in optimization. Due to the 2nd order smoothness, it is possible to minimize the CVT energy functions using Newton-like optimization methods and expect fast convergence. We propose a quasi-Newton method to compute CVT and demonstrate its faster convergence than Lloyd's method with various numerical examples. It is also significantly faster and more robust than the Lloyd-Newton method, a previous attempt to accelerate CVT. We also demonstrate surface remeshing as a possible application.