Approximate on‐Surface Distance Computation using Quasi‐Developable Charts

There is a vast number of applications that require distance field computation over triangular meshes. State‐of‐the‐art algorithms have quadratic or sub‐quadratic worst‐case complexity, making them impractical for interactive applications. While most of the research on this subject has been focused on reducing the computation complexity of the algorithms, in this work we propose an approximate algorithm that achieves similar results working in lower resolutions of the input meshes. The creation of lower resolution meshes is the essence of our proposal. The idea is to identify regions on the input mesh that can be unfolded into planar regions with minimal area distortion (i.e. quasi‐developable charts). Once charts are computed, their interior is re‐triangulated to reduce the number of triangles, which results in a collection of simplified charts that we call a base mesh. Due to the properties of quasi‐developable regions, we are able to compute distance fields over the base mesh instead of over the input mesh. This reduces the memory footprint and data processed for distance computations, which is the bottleneck of these algorithms. We present results that are one order of magnitude faster than current exact solutions, with low approximation errors.     

Semi‐supervised Mesh Segmentation and Labeling

Recently, approaches have been put forward that focus on the recognition of mesh semantic meanings. These methods usually need prior knowledge learned from training dataset, but when the size of the training dataset is small, or the meshes are too complex, the segmentation performance will be greatly effected. This paper introduces an approach to the semantic mesh segmentation and labeling which incorporates knowledge imparted by both segmented, labeled meshes, and unsegmented, unlabeled meshes. A Conditional Random Fields (CRF) based objective function measuring the consistency of labels and faces, labels of neighbouring faces is proposed. To implant the information from the unlabeled meshes, we add an unlabeled conditional entropy into the objective function. With the entropy, the objective function is not convex and hard to optimize, so we modify the Virtual Evidence Boosting (VEB) to solve the semi‐supervised problem efficiently. Our approach yields better results than those methods which only use limited labeled meshes, especially when many unlabeled meshes exist. The approach reduces the overall system cost as well as the human labelling cost required during training. We also show that combining knowledge from labeled and unlabeled meshes outperforms using either type of meshes alone.     

A Multiscale Metric for 3D Mesh Visual Quality Assessment

Many processing operations are nowadays applied on 3D meshes like compression, watermarking, remeshing and so forth; these processes are mostly driven and/or evaluated using simple distortion measures like the Hausdorff distance and the root mean square error, however these measures do not correlate with the human visual perception while the visual quality of the processed meshes is a crucial issue. In that context we introduce a full‐reference 3D mesh quality metric; this metric can compare two meshes with arbitrary connectivity or sampling density and produces a score that predicts the distortion visibility between them; a visual distortion map is also created. Our metric outperforms its counterparts from the state of the art, in term of correlation with mean opinion scores coming from subjective experiments on three existing databases. Additionally, we present an application of this new metric to the improvement of rate‐distortion evaluation of recent progressive compression algorithms.     

Tetrahedral Embedded Boundary Methods for Accurate and Flexible Adaptive Fluids

When simulating fluids, tetrahedral methods provide flexibility and ease of adaptivity that Cartesian grids find difficult to match. However, this approach has so far been limited by two conflicting requirements. First, accurate simulation requires quality Delaunay meshes and the use of circumcentric pressures. Second, meshes must align with potentially complex moving surfaces and boundaries, necessitating continuous remeshing. Unfortunately, sacrificing mesh quality in favour of speed yields inaccurate velocities and simulation artifacts. We describe how to eliminate the boundary‐matching constraint by adapting recent embedded boundary techniques to tetrahedra, so that neither air nor solid boundaries need to align with mesh geometry. This enables the use of high quality, arbitrarily graded, non‐conforming Delaunay meshes, which are simpler and faster to generate. Temporal coherence can also be exploited by reusing meshes over adjacent timesteps to further reduce meshing costs. Lastly, our free surface boundary condition eliminates the spurious currents that previous methods exhibited for slow or static scenarios. We provide several examples demonstrating that our efficient tetrahedral embedded boundary method can substantially increase the flexibility and accuracy of adaptive Eulerian fluid simulation.     

Multi‐Scale Geometry Interpolation

Interpolating vertex positions among triangle meshes with identical vertex‐edge graphs is a fundamental part of many geometric modelling systems. Linear vertex interpolation is robust but fails to preserve local shape. Most recent approaches identify local affine transformations for parts of the mesh, model desired interpolations of the affine transformations, and then optimize vertex positions to conform with the desired transformations. However, the local interpolation of the rotational part is non‐trivial for more than two input configurations and ambiguous if the meshes are deformed significantly. We propose a solution to the vertex interpolation problem that starts from interpolating the local metric (edge lengths) and mean curvature (dihedral angles) and makes consistent choices of local affine transformations using shape matching applied to successively larger parts of the mesh. The local interpolation can be applied to any number of input vertex configurations and due to the hierarchical scheme for generating consolidated vertex positions, the approach is fast and can be applied to very large meshes.     

Motorcycle Graphs: Canonical Quad Mesh Partitioning

We describe algorithms for canonically partitioning semi‐regular quadrilateral meshes into structured submeshes, using an adaptation of the geometric motorcycle graph of Eppstein and Erickson to quad meshes. Our partitions may be used to efficiently find isomorphisms between quad meshes. In addition, they may be used as a highly compressed representation of the original mesh. These partitions can be constructed in sublinear time from a list of the extraordinary vertices in a mesh. We also study the problem of further reducing the number of submeshes in our partitions—we prove that optimizing this number is NP‐hard, but it can be efficiently approximated.     

Embedded Implicit Stand-Ins for Animated Meshes: A Case of Hybrid Modelling

In this paper, we address shape modelling problems, encountered in computer animation and computer games development that are difficult to solve just using polygonal meshes. Our approach is based on a hybrid-modelling concept that combines polygonal meshes with implicit surfaces. A hybrid model consists of an animated polygonal mesh and an approximation of this mesh by a convolution surface stand-in that is embedded within it or is attached to it. The motions of both objects are synchronised using a rigging skeleton. We model the interaction between an animated mesh object and a viscoelastic substance, which is normally represented in an implicit form. Our approach is aimed at achieving verisimilitude rather than physically based simulation. The adhesive behaviour of the viscous object is modelled using geometric blending operations on the corresponding implicit surfaces. Another application of this approach is the creation of metamorphosing implicit surface parts that are attached to an animated mesh. A prototype implementation of the proposed approach and several examples of modelling and animation with near real-time preview times are presented.     

Implicit Hierarchical Quad‐Dominant Meshes

We present a method for producing quad‐dominant subdivided meshes, which supports both adaptive refinement and adaptive coarsening. A hierarchical structure is stored implicitly in a standard half‐edge data structure, while allowing us to efficiently navigate through the different level of subdivision. Subdivided meshes contain a majority of quad elements and a moderate amount of triangles and pentagons in the regions of transition across different levels of detail. Topological LOD editing is controlled with local conforming operators, which support both mesh refinement and mesh coarsening. We show two possible applications of this method: we define an adaptive subdivision surface scheme that is topologically and geometrically consistent with the Catmull–Clark subdivision; and we present a remeshing method that produces semi‐regular adaptive meshes.     

Error propagation control in Laplacian mesh compression

Laplacian mesh compression, also known as high‐pass mesh coding, is a popular technique for efficiently storing both static and dynamic triangle meshes that gained further recognition with the advent of perceptual mesh distortion evaluation metrics. Currently, the usual rule of thumb that drives the decision for a mesh compression algorithm is whether or not accuracy in absolute scale is required: Laplacian mesh encoding is chosen when perceptual quality is the main objective, while other techniques provide better results in terms of mechanistic error measures such as mean squared error. In this work, we present a modification of the Laplacian mesh encoding algorithm that preserves its benefits while it substantially reduces the resulting absolute error. Our approach is based on analyzing the reconstruction stage and modifying the quantization of differential coordinates, so that the decoded result stays close to the input even in areas that are distant from anchor points. In our approach, we avoid solving an overdetermined system of linear equations and thus reduce data redundancy, improve conditioning and achieve faster processing. Our approach can be directly applied to both static and dynamic mesh compression and we provide quantitative results comparing our approach with the state of the art methods.     

Skeleton‐driven Adaptive Hexahedral Meshing of Tubular Shapes

We propose a novel method for the automatic generation of structured hexahedral meshes of articulated 3D shapes. We recast the complex problem of generating the connectivity of a hexahedral mesh of a general shape into the simpler problem of generating the connectivity of a tubular structure derived from its curve‐skeleton. We also provide volumetric subdivision schemes to nicely adapt the topology of the mesh to the local thickness of tubes, while regularizing per‐element size. Our method is fast, one‐click, easy to reproduce, and it generates structured meshes that better align to the branching structure of the input shape if compared to previous methods for hexa mesh generation.     

Animation‐Aware Quadrangulation

Geometric meshes that model animated characters must be designed while taking into account the deformations that the shape will undergo during animation. We analyze an input sequence of meshes with point‐to‐point correspondence, and we automatically produce a quadrangular mesh that fits well the input animation. We first analyze the local deformation that the surface undergoes at each point, and we initialize a cross field that remains as aligned as possible to the principal directions of deformation throughout the sequence. We then smooth this cross field based on an energy that uses a weighted combination of the initial field and the local amount of stretch. Finally, we compute a field‐aligned quadrangulation with an off‐the‐shelf method. Our technique is fast and very simple to implement, and it significantly improves the quality of the output quad mesh and its suitability for character animation, compared to creating the quad mesh based on a single pose. We present experimental results and comparisons with a state‐of‐the‐art quadrangulation method, on both sequences from 3D scanning and synthetic sequences obtained by a rough animation of a triangulated model.     

Localized Delaunay Refinement for Sampling and Meshing

The technique of Delaunay refinement has been recognized as a versatile tool to generate Delaunay meshes of a variety of geometries. Despite its usefulness, it suffers from one lacuna that limits its application. It does not scale well with the mesh size. As the sample point set grows, the Delaunay triangulation starts stressing the available memory space which ultimately stalls any effective progress. A natural solution to the problem is to maintain the point set in clusters and run the refinement on each individual cluster. However, this needs a careful point insertion strategy and a balanced coordination among the neighboring clusters to ensure consistency across individual meshes. We design an octtree based localized Delaunay refinement method for meshing surfaces in three dimensions which meets these goals. We prove that the algorithm terminates and provide guarantees about structural properties of the output mesh. Experimental results show that the method can avoid memory thrashing while computing large meshes and thus scales much better than the standard Delaunay refinement method.     

Constrainable Multigrid for Cloth

We present a new technique which can handle both point and sliding constraints in the multigrid (MG) framework. Although the MG method can theoretically perform as fast as O(N), the development of a clothing simulator based on the MG method calls for solving an important technical challenge: handling the constraints. Resolving constrains has been difficult in MG because there has been no clear way to transfer the constraints existing in the finest level mesh to the coarser level meshes. This paper presents a new formulation based on soft constraints, which can coarsen the constraints defined in the finest level to the coarser levels. Experiments are performed which show that the proposed method can solve the linear system up to 4–9 times faster in comparison with the modified preconditioned conjugate gradient method (MPCG) without quality degradation. The proposed method is easy to implement and can be straightforwardly applied to existing clothing simulators which are based on implicit time integration.     

A Parallel Approach to Compression and Decompression of Triangle Meshes using the GPU

Most state‐of‐the‐art compression algorithms use complex connectivity traversal and prediction schemes, which are not efficient enough for online compression of large meshes. In this paper we propose a scalable massively parallel approach for compression and decompression of large triangle meshes using the GPU. Our method traverses the input mesh in a parallel breadth‐first manner and encodes the connectivity data similarly to the well known cut‐border machine. Geometry data is compressed using a local prediction strategy. In contrast to the original cut‐border machine, we can additionally handle triangle meshes with inconsistently oriented faces. Our approach is more than one order of magnitude faster than currently used methods and achieves competitive compression rates.     

A Semi‐Lagrangian Closest Point Method for Deforming Surfaces

We present an Eulerian method for the real‐time simulation of intrinsic fluid dynamics effects on deforming surfaces. Our method is based on a novel semi‐Lagrangian closest point method for the solution of partial differential equations on animated triangle meshes. We describe this method and demonstrate its use to compute and visualize flow and wave propagation along such meshes at high resolution and speed. Underlying our technique is the efficient conversion of an animated triangle mesh into a time‐dependent implicit representation based on closest surface points. The proposed technique is unconditionally stable with respect to the surface deformation and, in contrast to comparable Lagrangian techniques, its precision does not depend on the level of detail of the surface triangulation.     

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.     

Hexahedral Meshing With Varying Element Sizes

Hexahedral (or Hex‐) meshes are preferred in a number of scientific and engineering simulations and analyses due to their desired numerical properties. Recent state‐of‐the‐art techniques can generate high‐quality hex‐meshes. However, they typically produce hex‐meshes with uniform element sizes and thus may fail to preserve small‐scale features on the boundary surface. In this work, we present a new framework that enables users to generate hex‐meshes with varying element sizes so that small features will be filled with smaller and denser elements, while the transition from smaller elements to larger ones is smooth, compared to the octree‐based approach. This is achieved by first detecting regions of interest (ROIs) of small‐scale features. These ROIs are then magnified using the as‐rigid‐as‐possible deformation with either an automatically determined or a user‐specified scale factor. A hex‐mesh is then generated from the deformed mesh using existing approaches that produce hex‐meshes with uniform‐sized elements. This initial hex‐mesh is then mapped back to the original volume before magnification to adjust the element sizes in those ROIs. We have applied this framework to a variety of man‐made and natural models to demonstrate its effectiveness.     

Extraction Of Feature Lines On Surface Meshes Based On Discrete Morse Theory

We present an approach for extracting extremal feature lines of scalar indicators on surface meshes, based on discrete Morse Theory. By computing initial Morse‐Smale complexes of the scalar indicators of the mesh, we obtain a candidate set of extremal feature lines of the surface. A hierarchy of Morse‐Smale complexes is computed by prioritizing feature lines according to a novel criterion and applying a cancellation procedure that allows us to select the most significant lines. Given the scalar indicators on the vertices of the mesh, the presented feature line extraction scheme is interpolation free and needs no derivative estimates. The technique is insensitive to noise and depends only on one parameter: the feature significance. We use the technique to extract surface features yielding impressive, non photorealistic images.     

Distortion-Free Steganography for Polygonal Meshes

We present a technique for steganography in polygonal meshes. Our method hides a message in the indexed rep‐resentation of a mesh by permuting the order in which faces and vertices are stored. The permutation is relative to a reference ordering that encoder and decoder derive from the mesh connectivity in a consistent manner. Our method is distortion‐free because it does not modify the geometry of the mesh. Compared to previous steganographic methods for polygonal meshes our capacity is up to an order of magnitude better. Our steganography algorithm is universal and can be used instead of the standard permutation steganography algorithm on arbitrary datasets. The standard algorithm runs in Ω (n² log² n log log n) time and achieves optimal O(nlog n) bit capacity on datasets with n elements. In contrast, our algorithm runs in O(n) time, achieves a capacity that is only one bit per element less than optimal, and is extremely simple to implement.