A Constrained Resampling Strategy for Mesh Improvement

In many geometry processing applications, it is required to improve an initial mesh in terms of multiple quality objectives. Despite the availability of several mesh generation algorithms with provable guarantees, such generated meshes may only satisfy a subset of the objectives. The conflicting nature of such objectives makes it challenging to establish similar guarantees for each combination, e.g., angle bounds and vertex count. In this paper, we describe a versatile strategy for mesh improvement by interpreting quality objectives as spatial constraints on resampling and develop a toolbox of local operators to improve the mesh while preserving desirable properties. Our strategy judiciously combines smoothing and transformation techniques allowing increased flexibility to practically achieve multiple objectives simultaneously. We apply our strategy to both planar and surface meshes demonstrating how to simplify Delaunay meshes while preserving element quality, eliminate all obtuse angles in a complex mesh, and maximize the shortest edge length in a Voronoi tessellation far better than the state‐of‐the‐art.     

Pseudo‐Spline Subdivision Surfaces

Pseudo‐splines provide a rich family of subdivision schemes with a wide range of choices that meet various demands for balancing the approximation power, the length of the support, and the regularity of the limit functions. Special cases of pseudo‐splines include uniform odd‐degree B‐splines and the interpolatory 2n‐point subdivision schemes, and the other pseudo‐splines fill the gap between these two families. In this paper we show how the refinement step of a pseudo‐spline subdivision scheme can be implemented efficiently using repeated local operations, which require only the data in the direct neighbourhood of each vertex, and how to generalize this concept to quadrilateral meshes with arbitrary topology. The resulting pseudo‐spline surfaces can be arbitrarily smooth in regular mesh regions and C¹ at extraordinary vertices as our numerical analysis reveals.     

Object Completion using k‐Sparse Optimization

We present a new method for the completion of partial globally‐symmetric 3D objects, based on the detection of partial and approximate symmetries in the incomplete input dataset. In our approach, symmetry detection is formulated as a constrained sparsity maximization problem, which is solved efficiently using a robust RANSAC‐based optimizer. The detected partial symmetries are then reused iteratively, in order to complete the missing parts of the object. A global error relaxation method minimizes the accumulated alignment errors and a non‐rigid registration approach applies local deformations in order to properly handle approximate symmetry. Unlike previous approaches, our method does not rely on the computation of features, it uniformly handles translational, rotational and reflectional symmetries and can provide plausible object completion results, even on challenging cases, where more than half of the target object is missing. We demonstrate our algorithm in the completion of 3D scans with varying levels of partiality and we show the applicability of our approach in the repair and completion of heavily eroded or incomplete cultural heritage objects.     

Compressed Manifold Modes for Mesh Processing

This paper introduces compressed eigenfunctions of the Laplace‐Beltrami operator on 3D manifold surfaces. They constitute a novel functional basis, called the compressed manifold basis, where each function has local support. We derive an algorithm, based on the alternating direction method of multipliers (ADMM), to compute this basis on a given triangulated mesh. We show that compressed manifold modes identify key shape features, yielding an intuitive understanding of the basis for a human observer, where a shape can be processed as a collection of parts. We evaluate compressed manifold modes for potential applications in shape matching and mesh abstraction. Our results show that this basis has distinct advantages over existing alternatives, indicating high potential for a wide range of use‐cases in mesh processing.     

Directional Field Synthesis,Design, and Processing

Direction fields and vector fields play an increasingly important role in computer graphics and geometry processing. The synthesis of directional fields on surfaces, or other spatial domains, is a fundamental step in numerous applications, such as mesh generation, deformation, texture mapping, and many more. The wide range of applications resulted in definitions for many types of directional fields: from vector and tensor fields, over line and cross fields, to frame and vector‐set fields. Depending on the application at hand, researchers have used various notions of objectives and constraints to synthesize such fields. These notions are defined in terms of fairness, feature alignment, symmetry, or field topology, to mention just a few. To facilitate these objectives, various representations, discretizations, and optimization strategies have been developed. These choices come with varying strengths and weaknesses. This report provides a systematic overview of directional field synthesis for graphics applications, the challenges it poses, and the methods developed in recent years to address these challenges.     

Discrete 2‐Tensor Fields on Triangulations

Geometry processing has made ample use of discrete representations of tangent vector fields and antisymmetric tensors (i.e., forms) on triangulations. Symmetric 2‐tensors, while crucial in the definition of inner products and elliptic operators, have received only limited attention. They are often discretized by first defining a coordinate system per vertex, edge or face, then storing their components in this frame field. In this paper, we introduce a representation of arbitrary 2‐tensor fields on triangle meshes. We leverage a coordinate‐free decomposition of continuous 2‐tensors in the plane to construct a finite‐dimensional encoding of tensor fields through scalar values on oriented simplices of a manifold triangulation. We also provide closed‐form expressions of pairing, inner product, and trace for this discrete representation of tensor fields, and formulate a discrete covariant derivative and a discrete Lie bracket. Our approach extends discrete/finite‐element exterior calculus, recovers familiar operators such as the weighted Laplacian operator, and defines discrete notions of divergence‐free, curl‐free, and traceless tensors–thus offering a numerical framework for discrete tensor calculus on triangulations. We finally demonstrate the robustness and accuracy of our operators on analytical examples, before applying them to the computation of anisotropic geodesic distances on discrete surfaces.     

Guided Mesh Normal Filtering

The joint bilateral filter is a variant of the standard bilateral filter, where the range kernel is evaluated using a guidance signal instead of the original signal. It has been successfully applied to various image processing problems, where it provides more flexibility than the standard bilateral filter to achieve high quality results. On the other hand, its success is heavily dependent on the guidance signal, which should ideally provide a robust estimation about the features of the output signal. Such a guidance signal is not always easy to construct. In this paper, we propose a novel mesh normal filtering framework based on the joint bilateral filter, with applications in mesh denoising. Our framework is designed as a two‐stage process: first, we apply joint bilateral filtering to the face normals, using a properly constructed normal field as the guidance; afterwards, the vertex positions are updated according to the filtered face normals. We compute the guidance normal on a face using a neighboring patch with the most consistent normal orientations, which provides a reliable estimation of the true normal even with a high‐level of noise. The effectiveness of our approach is validated by extensive experimental results.     

Semi‐sharp Creases on Subdivision Curves and Surfaces

We explore a method for generalising Pixar semi‐sharp creases from the univariate cubic case to arbitrary degree subdivision curves. Our approach is based on solving simple matrix equations. The resulting schemes allow for greater flexibility over existing methods, via control vectors. We demonstrate our results on several high‐degree univariate examples and explore analogous methods for subdivision surfaces.     

Fast and Memory‐Efficient Voronoi Diagram Construction on Triangle Meshes

Geodesic based Voronoi diagrams play an important role in many applications of computer graphics. Constructing such Voronoi diagrams usually resorts to exact geodesics. However, exact geodesic computation always consumes lots of time and memory, which has become the bottleneck of constructing geodesic based Voronoi diagrams. In this paper, we propose the window‐VTP algorithm, which can effectively reduce redundant computation and save memory. As a result, constructing Voronoi diagrams using the proposed window‐VTP algorithm runs 3–8 times faster than Liu et al.'s method [ LCT11 ], 1.2 times faster than its FWP‐MMP variant and more importantly uses 10–70 times less memory than both of them.     

Efficient Volumetric PolyCube‐Map Construction

PolyCubes provide compact representations for closed complex shapes and are essential to many computer graphics applications. Existing automatic PolyCube construction methods usually suffer from poor quality or time‐consuming computation. In this paper, we provide a highly efficient method to compute volumetric PolyCube‐maps. Given an input tetrahedral mesh, we utilize two novel normal‐driven volumetric deformation schemes and a polycube‐allowable mesh segmentation to drive the input to a volumetric PolyCube structure. Our method can robustly generate foldover‐free and low‐distortion PolyCube‐maps in practice, and provide a flexible control on the number of corners of Polycubes. Compared with state‐of‐the‐art methods, our method is at least one order of magnitude faster and has better mapping qualities. We demonstrate the efficiency and efficacy of our method in PolyCube construction and all‐hexahedral meshing on various complex models.     

Wavejets: A Local Frequency Framework for Shape Details Amplification

Detail enhancement is a well‐studied area of 3D rendering and image processing, which has few equivalents for 3D shape processing. To enhance details, one needs an efficient analysis tool to express the local surface dynamics. We introduce Wavejets, a new function basis for locally decomposing a shape expressed over the local tangent plane, by considering both angular oscillations of the surface around each point and a radial polynomial. We link the Wavejets coefficients to surface derivatives and give theoretical guarantees for their precision and stability with respect to an approximate tangent plane. The coefficients can be used for shape details amplification, to enhance, invert or distort them, by operating either on the surface point positions or on the normals. From a practical point of view, we derive an efficient way of estimating Wavejets on point sets and demonstrate experimentally the amplification results with respect to noise or basis truncation.     

Sparse Non‐rigid Registration of 3D Shapes

Non‐rigid registration of 3D shapes is an essential task of increasing importance as commodity depth sensors become more widely available for scanning dynamic scenes. Non‐rigid registration is much more challenging than rigid registration as it estimates a set of local transformations instead of a single global transformation, and hence is prone to the overfitting issue due to underdetermination. The common wisdom in previous methods is to impose an ?₂‐norm regularization on the local transformation differences. However, the ?₂‐norm regularization tends to bias the solution towards outliers and noise with heavy‐tailed distribution, which is verified by the poor goodness‐of‐fit of the Gaussian distribution over transformation differences. On the contrary, Laplacian distribution fits well with the transformation differences, suggesting the use of a sparsity prior. We propose a sparse non‐rigid registration (SNR) method with an ?₁‐norm regularized model for transformation estimation, which is effectively solved by an alternate direction method (ADM) under the augmented Lagrangian framework. We also devise a multi‐resolution scheme for robust and progressive registration. Results on both public datasets and our scanned datasets show the superiority of our method, particularly in handling large‐scale deformations as well as outliers and noise.     

Geometric Flows of Curves in Shape Space for Processing Motion of Deformable Objects

We introduce techniques for the processing of motion and animations of non‐rigid shapes. The idea is to regard animations of deformable objects as curves in shape space. Then, we use the geometric structure on shape space to transfer concepts from curve processing in ?ⁿ to the processing of motion of non‐rigid shapes. Following this principle, we introduce a discrete geometric flow for curves in shape space. The flow iteratively replaces every shape with a weighted average shape of a local neighborhood and thereby globally decreases an energy whose minimizers are discrete geodesics in shape space. Based on the flow, we devise a novel smoothing filter for motions and animations of deformable shapes. By shortening the length in shape space of an animation, it systematically regularizes the deformations between consecutive frames of the animation. The scheme can be used for smoothing and noise removal, e.g., for reducing jittering artifacts in motion capture data. We introduce a reduced‐order method for the computation of the flow. In addition to being efficient for the smoothing of curves, it is a novel scheme for computing geodesics in shape space. We use the scheme to construct non‐linear “Bézier curves” by executing de Casteljau's algorithm in shape space.     

Polyline‐sourced Geodesic Voronoi Diagrams on Triangle Meshes

This paper studies the Voronoi diagrams on 2‐manifold meshes based on geodesic metric (a.k.a. geodesic Voronoi diagrams or GVDs), which have polyline generators. We show that our general setting leads to situations more complicated than conventional 2D Euclidean Voronoi diagrams as well as point‐source based GVDs, since a typical bisector contains line segments, hyperbolic segments and parabolic segments. To tackle this challenge, we introduce a new concept, called local Voronoi diagram (LVD), which is a combination of additively weighted Voronoi diagram and line‐segment Voronoi diagram on a mesh triangle. We show that when restricting on a single mesh triangle, the GVD is a subset of the LVD and only two types of mesh triangles can contain GVD edges. Based on these results, we propose an efficient algorithm for constructing the GVD with polyline generators. Our algorithm runs in O(nNlogN) time and takes O(nN) space on an n‐face mesh with m generators, where N = max{m, n}. Computational results on real‐world models demonstrate the efficiency of our algorithm.     

3D Skeletons: A State‐of‐the‐Art Report

Given a shape, a skeleton is a thin centered structure which jointly describes the topology and the geometry of the shape. Skeletons provide an alternative to classical boundary or volumetric representations, which is especially effective for applications where one needs to reason about, and manipulate, the structure of a shape. These skeleton properties make them powerful tools for many types of shape analysis and processing tasks. For a given shape, several skeleton types can be defined, each having its own properties, advantages, and drawbacks. Similarly, a large number of methods exist to compute a given skeleton type, each having its own requirements, advantages, and limitations. While using skeletons for two‐dimensional (2D) shapes is a relatively well covered area, developments in the skeletonization of three‐dimensional (3D) shapes make these tasks challenging for both researchers and practitioners. This survey presents an overview of 3D shape skeletonization. We start by presenting the definition and properties of various types of 3D skeletons. We propose a taxonomy of 3D skeletons which allows us to further analyze and compare them with respect to their properties. We next overview methods and techniques used to compute all described 3D skeleton types, and discuss their assumptions, advantages, and limitations. Finally, we describe several applications of 3D skeletons, which illustrate their added value for different shape analysis and processing tasks.     

Mesh Denoising using Extended ROF Model with L1 Fidelity

This paper presents a variational algorithm for feature‐preserved mesh denoising. At the heart of the algorithm is a novel variational model composed of three components: fidelity, regularization and fairness, which are specifically designed to have their intuitive roles. In particular, the fidelity is formulated as an L₁ data term, which makes the regularization process be less dependent on the exact value of outliers and noise. The regularization is formulated as the total absolute edge‐lengthed supplementary angle of the dihedral angle, making the model capable of reconstructing meshes with sharp features. In addition, an augmented Lagrange method is provided to efficiently solve the proposed variational model. Compared to the prior art, the new algorithm has crucial advantages in handling large scale noise, noise along random directions, and different kinds of noise, including random impulsive noise, even in the presence of sharp features. Both visual and quantitative evaluation demonstrates the superiority of the new algorithm.     

Retargeting 3D Objects and Scenes with a General Framework

In this paper, we introduce an interactive method suitable for retargeting both 3D objects and scenes. Initially, the input object or scene is decomposed into a collection of constituent components enclosed by corresponding control bounding volumes which capture the intra‐structures of the object or semantic grouping of objects in the 3D scene. The overall retargeting is accomplished through a constrained optimization by manipulating the control bounding volumes. Without inferring the intricate dependencies between the components, we define a minimal set of constraints that maintain the spatial arrangement and connectivity between the components to regularize the valid retargeting results. The default retargeting behavior can then be easily altered by additional semantic constraints imposed by users. This strategy makes the proposed method highly flexible to process a wide variety of 3D objects and scenes under an unified framework. In addition, the proposed method achieved more general structure‐preserving pattern synthesis in both object and scene levels. We demonstrate the effectiveness of our method by applying it to several complicated 3D objects and scenes.     

Approximate Symmetry Detection in Partial 3D Meshes

Symmetry is a common characteristic in natural and man‐made objects. Its ubiquitous nature can be exploited to facilitate the analysis and processing of computational representations of real objects. In particular, in computer graphics, the detection of symmetries in 3D geometry has enabled a number of applications in modeling and reconstruction. However, the problem of symmetry detection in incomplete geometry remains a challenging task. In this paper, we propose a vote‐based approach to detect symmetry in 3D shapes, with special interest in models with large missing parts. Our algorithm generates a set of candidate symmetries by matching local maxima of a surface function based on the heat diffusion in local domains, which guarantee robustness to missing data. In order to deal with local perturbations, we propose a multi‐scale surface function that is useful to select a set of distinctive points over which the approximate symmetries are defined. In addition, we introduce a vote‐based scheme that is aware of the partiality, and therefore reduces the number of false positive votes for the candidate symmetries. We show the effectiveness of our method in a varied set of 3D shapes and different levels of partiality. Furthermore, we show the applicability of our algorithm in the repair and completion of challenging reassembled objects in the context of cultural heritage.