Skeleton-based Variational Mesh Deformations

In this paper, a new free-form shape deformation approach is proposed. We combine a skeleton-based mesh deformation technique with discrete differential coordinates in order to create natural-looking global shape deformations. Given a triangle mesh, we first extract a skeletal mesh, a two-sided Voronoibased approximation of the medial axis. Next the skeletal mesh is modified by free-form deformations. Then a desired global shape deformation is obtained by reconstructing the shape corresponding to the deformed skeletal mesh. The reconstruction is based on using discrete differential coordinates. Our method preserves fine geometric details and original shape thickness because of using discrete differential coordinates and skeleton-based deformations. We also develop a new mesh evolution technique which allow us to eliminate possible global and local self-intersections of the deformed mesh while preserving fine geometric details. Finally, we present a multi-resolution version of our approach in order to simplify and accelerate the deformation process. In addition, interesting links between the proposed free-form shape deformation technique and classical and modern results in the differential geometry of sphere congruences are established and discussed.     

GeoBrush: Interactive Mesh Geometry Cloning

We propose a method for interactive cloning of 3D surface geometry using a paintbrush interface, similar to the continuous cloning brush popular in image editing. Existing interactive mesh composition tools focus on atomic copy‐and‐paste of preselected feature areas, and are either limited to copying surface displacements, or require the solution of variational optimization problems, which is too expensive for an interactive brush interface. In contrast, our GeoBrush method supports real‐time continuous copying of arbitrary high‐resolution surface features between irregular meshes, including topological handles. We achieve this by first establishing a correspondence between the source and target geometries using a novel generalized discrete exponential map parameterization. Next we roughly align the source geometry with the target shape using Green Coordinates with automatically‐constructed cages. Finally, we compute an offset membrane to smoothly blend the pasted patch with C continuity before stitching it into the target. The offset membrane is a solution of a bi‐harmonic PDE, which is computed on the GPU in real time by exploiting the regular parametric domain. We demonstrate the effectiveness of GeoBrush with various editing scenarios, including detail enrichment and completion of scanned surfaces.     

An Operator Approach to Tangent Vector Field Processing

In this paper, we introduce a novel coordinate‐free method for manipulating and analyzing vector fields on discrete surfaces. Unlike the commonly used representations of a vector field as an assignment of vectors to the faces of the mesh, or as real values on edges, we argue that vector fields can also be naturally viewed as operators whose domain and range are functions defined on the mesh. Although this point of view is common in differential geometry it has so far not been adopted in geometry processing applications. We recall the theoretical properties of vector fields represented as operators, and show that composition of vector fields with other functional operators is natural in this setup. This leads to the characterization of vector field properties through commutativity with other operators such as the Laplace‐Beltrami and symmetry operators, as well as to a straight‐forward definition of differential properties such as the Lie derivative. Finally, we demonstrate a range of applications, such as Killing vector field design, symmetric vector field estimation and joint design on multiple surfaces.     

Isotropic Surface Remeshing Using Constrained Centroidal Delaunay Mesh

We develop a novel isotropic remeshing method based on constrained centroidal Delaunay mesh (CCDM), a generalization of centroidal patch triangulation from 2D to mesh surface. Our method starts with resampling an input mesh with a vertex distribution according to a user‐defined density function. The initial remeshing result is then progressively optimized by alternatively recovering the Delaunay mesh and moving each vertex to the centroid of its 1‐ring neighborhood. The key to making such simple iterations work is an efficient optimization framework that combines both local and global optimization methods. Our method is parameterization‐free, thus avoiding the metric distortion introduced by parameterization, and generating more well‐shaped triangles. Our method guarantees that the topology of surface is preserved without requiring geodesic information. We conduct various experiments to demonstrate the simplicity, efficacy, and robustness of the presented method.     

Localized Delaunay Refinement for Volumes

Delaunay refinement, recognized as a versatile tool for meshing a variety of geometries, has the deficiency that it does not scale well with increasing mesh size. The bottleneck can be traced down to the memory usage of 3D Delaunay triangulations. Recently an approach has been suggested to tackle this problem for the specific case of smooth surfaces by subdividing the sample set in an octree and then refining each subset individually while ensuring termination and consistency. We extend this to localized refinement of volumes, which brings about some new challenges. We show how these challenges can be met with simple steps while retaining provable guarantees, and that our algorithm scales many folds better than a state‐of‐the‐art meshing tool provided by CGAL.     

Connectivity Editing for Quad‐Dominant Meshes

We propose a connectivity editing framework for quad‐dominant meshes. In our framework, the user can edit the mesh connectivity to control the location, type, and number of irregular vertices (with more or fewer than four neighbors) and irregular faces (non‐quads). We provide a theoretical analysis of the problem, discuss what edits are possible and impossible, and describe how to implement an editing framework that realizes all possible editing operations. In the results, we show example edits and illustrate the advantages and disadvantages of different strategies for quad‐dominant mesh design.     

A survey on Mesh Segmentation Techniques

We present a review of the state of the art of segmentation and partitioning techniques of boundary meshes. Recently, these have become a part of many mesh and object manipulation algorithms in computer graphics, geometric modelling and computer aided design. We formulate the segmentation problem as an optimization problem and identify two primarily distinct types of mesh segmentation, namely part segmentation and surface‐patch segmentation. We classify previous segmentation solutions according to the different segmentation goals, the optimization criteria and features used, and the various algorithmic techniques employed. We also present some generic algorithms for the major segmentation techniques.     

Mesh Segmentation via Spectral Embedding and Contour Analysis

We propose a mesh segmentation algorithm via recursive bisection where at each step, a sub-mesh embedded in 3D is first spectrally projected into the plane and then a contour is extracted from the planar embedding. We rely on two operators to compute the projection: the well-known graph Laplacian and a geometric operator designed to emphasize concavity. The two embeddings reveal distinctive shape semantics of the 3D model and complement each other in capturing the structural or geometrical aspect of a segmentation. Transforming the shape analysis problem to the 2D domain also facilitates our segmentability analysis and sampling tasks. We propose a novel measure of the segmentability of a shape, which is used as the stopping criterionfor our segmentation. The measure is derived from simple area- and perimeter-based convexity measures. We achieve invariance to shape bending through multi-dimensional scaling (MDS) based on the notion of inner distance. We also utilize inner distances to develop a novel sampling scheme to extract two samples along a contour which correspond to two vertices residing on different parts of the sub-mesh. The two samples are used to derive a spectral linear ordering of the mesh faces. We obtain a final cut via a linear search over the face sequence based on part salience, where a choice of weights for different factors of part salience is guided by the result from segmentability analysis.     

Reconstructing Animated Meshes from Time‐Varying Point Clouds

In this paper, we describe a novel approach for the reconstruction of animated meshes from a series of time‐deforming point clouds. Given a set of unordered point clouds that have been captured by a fast 3‐D scanner, our algorithm is able to compute coherent meshes which approximate the input data at arbitrary time instances. Our method is based on the computation of an implicit function in ?⁴ that approximates the time‐space surface of the time‐varying point cloud. We then use the four‐dimensional implicit function to reconstruct a polygonal model for the first time‐step. By sliding this template mesh along the time‐space surface in an as‐rigid‐as‐possible manner, we obtain reconstructions for further time‐steps which have the same connectivity as the previously extracted mesh while recovering rigid motion exactly. The resulting animated meshes allow accurate motion tracking of arbitrary points and are well suited for animation compression. We demonstrate the qualities of the proposed method by applying it to several data sets acquired by real‐time 3‐D scanners.     

Taylor Prediction for Mesh Geometry Compression

In this paper, we introduce a new formalism for mesh geometry prediction. We derive a class of smooth linear predictors from a simple approach based on the Taylor expansion of the mesh geometry function. We use this method as a generic way to compute weights for various linear predictors used for mesh compression and compare them with those of existing methods. We show that our scheme is actually equivalent to the Modified Butterfly subdivision scheme used for wavelet mesh compression. We also build new efficient predictors that can be used for connectivity‐driven compression in place of other schemes like Average/Dual Parallelogram Prediction and High Degree Polygon Prediction. The new predictors use the same neighbourhood, but do not make any assumption on mesh anisotropy. In the case of Average Parallelogram Prediction, our new weights improve compression rates from 3% to 18% on our test meshes. For Dual Parallelogram Prediction, our weights are equivalent to those of the previous Freelence approach, that outperforms traditional schemes by 16% on average. Our method effectively shows that these weights are optimal for the class of smooth meshes. Modifying existing schemes to make use of our method is free because only the prediction weights have to be modified in the code.     

Exact and Robust (Self‐)Intersections for Polygonal Meshes

We present a new technique to implement operators that modify the topology of polygonal meshes at intersections and self‐intersections. Depending on the modification strategy, this effectively results in operators for Boolean combinations or for the construction of outer hulls that are suited for mesh repair tasks and accurate mesh‐based front tracking of deformable materials that split and merge. By combining an adaptive octree with nested binary space partitions (BSP), we can guarantee exactness (= correctness) and robustness (= completeness) of the algorithm while still achieving higher performance and less memory consumption than previous approaches. The efficiency and scalability in terms of runtime and memory is obtained by an operation localization scheme. We restrict the essential computations to those cells in the adaptive octree where intersections actually occur. Within those critical cells, we convert the input geometry into a plane‐based BSP‐representation which allows us to perform all computations exactly even with fixed precision arithmetics. We carefully analyze the precision requirements of the involved geometric data and predicates in order to guarantee correctness and show how minimal input mesh quantization can be used to safely rely on computations with standard floating point numbers. We properly evaluate our method with respect to precision, robustness, and efficiency.     

Hierarchical Deformation of Locally Rigid Meshes

We propose a method for calculating deformations of models by deforming a low‐resolution mesh and adding details while ensuring that the details we add satisfy a set of constraints. Our method builds a low‐resolution representation of a mesh by using edge collapses and performs an as‐rigid‐as‐possible deformation on the simplified mesh. We then add back details by reversing edge‐collapses so that the shape of the mesh is locally preserved. While adding details, we deform the mesh to match the predicted positions of constraints so that constraints on the full‐resolution mesh are met. Our method operates on meshes with arbitrary triangulations, satisfies constraints over the full‐resolution mesh and converges quickly.     

Hierarchical Convex Approximation of 3D Shapes for Fast Region Selection

Given a 3D solid model S represented by a tetrahedral mesh, we describe a novel algorithm to compute a hierarchy of convex polyhedra that tightly enclose S. The hierarchy can be browsed at interactive speed on a modern PC and it is useful for implementing an intuitive feature selection paradigm for 3D editing environments. Convex parts often coincide with perceptually relevant shape components and, for their identification, existing methods rely on the boundary surface only. In contrast, we show that the notion of part concavity can be expressed and implemented more intuitively and efficiently by exploiting a tetrahedrization of the shape volume. The method proposed is completely automatic, and generates a tree of convex polyhedra in which the root is the convex hull of the whole shape, and the leaves are the tetrahedra of the input mesh. The algorithm proceeds bottom‐up by hierarchically clustering tetrahedra into nearly convex aggregations, and the whole process is significantly fast. We prove that, in the average case, for a mesh of n tetrahedra O(n log² n) operations are sufficient to compute the whole tree.     

Spectral Mesh Processing

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.     

Discovery of Intrinsic Primitives on Triangle Meshes

The discovery of meaningful parts of a shape is required for many geometry processing applications, such as parameterization, shape correspondence, and animation. It is natural to consider primitives such as spheres, cylinders and cones as the building blocks of shapes, and thus to discover parts by fitting such primitives to a given surface. This approach, however, will break down if primitive parts have undergone almost‐isometric deformations, as is the case, for example, for articulated human models. We suggest that parts can be discovered instead by finding intrinsic primitives, which we define as parts that posses an approximate intrinsic symmetry. We employ the recently‐developed method of computing discrete approximate Killing vector fields (AKVFs) to discover intrinsic primitives by investigating the relationship between the AKVFs of a composite object and the AKVFs of its parts. We show how to leverage this relationship with a standard clustering method to extract k intrinsic primitives and remaining asymmetric parts of a shape for a given k. We demonstrate the value of this approach for identifying the prominent symmetry generators of the parts of a given shape. Additionally, we show how our method can be modified slightly to segment an entire surface without marking asymmetric connecting regions and compare this approach to state‐of‐the‐art methods using the Princeton Segmentation Benchmark.     

Geodesic Polar Coordinates on Polygonal Meshes

Geodesic Polar Coordinates (GPCs) on a smooth surface S are local surface coordinates that relates a surface point to a planar parameter point by the length and direction of a corresponding geodesic curve onS . They are intrinsic to the surface and represent a natural local parameterization with useful properties. We present a simple and efficient algorithm to approximate GPCs on both triangle and general polygonal meshes. Our approach, named DGPC, is based on extending an existing algorithm for computing geodesic distance. We compare our approach with previous methods, both with respect to efficiency, accuracy and visual qualities when used for local mesh texturing. As a further application we show how the resulting coordinates can be used for vector space methods like local remeshing at interactive frame‐rates even for large meshes.     

Variational 3D Shape Segmentation for Bounding Volume Computation

We propose a variational approach to computing an optimal segmentation of a 3D shape for computing a union of tight bounding volumes. Based on an affine invariant measure of e-tightness, the resemblance to ellipsoid, a novel functional is formulated that governs an optimization process to obtain a partition with multiple components. Refinement of segmentation is driven by application-specific error measures, so that the final bounding volume meets pre-specified user requirement. We present examples to demonstrate the effectiveness of our method and show that it works well for computing ellipsoidal bounding volumes as well as oriented bounding boxes.     

Mesh Snapping: Robust Interactive Mesh Cutting Using Fast Geodesic Curvature Flow

This paper considers the problem of interactively finding the cutting contour to extract components from a given mesh. Some existing methods support cuts of arbitrary shape but require careful and tedious input from the user. Others need little user input however they are sensitive to user input and need a postprocessing step to smooth the generated jaggy cutting contours. The popular geometric snake can be used to optimize the cutting contour, but it cannot deal with the topology change. In this paper, we propose a geodesic curvature flow based framework to overcome all these problems. Since in many cases the meaningful cutting contour on a 3D mesh is locally shortest in the sense of some weighted curve length, the geodesic curvature flow is an ideal tool for our problem. It evolves the cutting contour to the nearby local minimum. We should mention that the previous numerical scheme, discretized geodesic curvature flow (dGCF) is too slow and has not been applied to mesh segmentation. With a careful observation to dGCF, we devise here a fast computation scheme called fast geodesic curvature flow (FGCF), which only needs to solve a smaller and easier problem. The initial cutting contour is generated by a variant of random walks algorithm, which is very fast and gives reasonable cutting result with little user input. Experiment results on the benchmark mesh segmentation data set show that our proposed framework is robust to user input and capable of producing good results reflecting geometric features and human shape perception.     

A Sketch-Based User Interface for Reconstructing Architectural Drawings

We present a framework for interactive sketching that allows users to create three‐dimensional (3D) architectural models quickly and easily from a source drawing. The sketching process has four steps. (1) The user calibrates a viewing camera by specifying the origin and vanishing points of the drawing. (2) The user outlines surface polygons in the drawing. (3) A 3D reconstruction algorithm uses perceptual constraints to determine the closest visual fit for the polygon. (4) The user can then adjust aesthetic controls to produce several stylistic effects in the scene: a smooth transition between day and night rendering, a horizon knockout effect and entourage figures. The major advantage of our approach lies in the combination of perception‐based techniques, which allow us to minimize unnecessary interactions, and a hinging‐angle scheme, which shows significant improvement in numerical stability over previous optimization‐based 3D reconstruction algorithms. We also demonstrate how our reconstruction algorithm can be extended to work with perspective images, a feature unavailable in previous approaches.     

Approximating Gradients for Meshes and Point Clouds via Diffusion Metric

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.