A unified discrete framework for intrinsic and extrinsic Dirac operators for geometry processing

Spectral mesh analysis and processing methods, namely ones that utilize eigenvalues and eigenfunctions of linear operators on meshes, have been applied to numerous geometric processing applications. The operator used predominantly in these methods is the Laplace‐Beltrami operator, which has the often‐cited property that it is intrinsic, namely invariant to isometric deformation of the underlying geometry, including rigid transformations. Depending on the application, this can be either an advantage or a drawback. Recent work has proposed the alternative of using the Dirac operator on surfaces for spectral processing. The available versions of the Dirac operator either only focus on the extrinsic version, or introduce a range of mixed operators on a spectrum between fully extrinsic Dirac operator and intrinsic Laplace operator. In this work, we introduce a unified discretization scheme that describes both an extrinsic and intrinsic Dirac operator on meshes, based on their continuous counterparts on smooth manifolds. In this discretization, both operators are very closely related, and preserve their key properties from the smooth case. We showcase various applications of our operators, with improved numerics over prior work.     

Spectral Geometry Processing with Manifold Harmonics

We present an explicit method to compute a generalization of the Fourier Transform on a mesh. It is well known that the eigenfunctions of the Laplace Beltrami operator (Manifold Harmonics) define a function basis allowing for such a transform. However, computing even just a few eigenvectors is out of reach for meshes with more than a few thousand vertices, and storing these eigenvectors is prohibitive for large meshes. To overcome these limitations, we propose a band‐by‐band spectrum computation algorithm and an out‐of‐core implementation that can compute thousands of eigenvectors for meshes with up to a million vertices. We also propose a limited‐memory filtering algorithm, that does not need to store the eigenvectors. Using this latter algorithm, specific frequency bands can be filtered, without needing to compute the entire spectrum. Finally, we demonstrate some applications of our method to interactive convolution geometry filtering. These technical achievements are supported by a solid yet simple theoretic framework based on Discrete Exterior Calculus (DEC). In particular, the issues of symmetry and discretization of the operator are considered with great care.     

Trivariate Biharmonic B‐Splines

In this paper, we formulate a novel trivariate biharmonic B‐spline defined over bounded volumetric domain. The properties of bi‐Laplacian have been well investigated, but the straightforward generalization from bivariate case to trivariate one gives rise to unsatisfactory discretization, due to the dramatically uneven distribution of neighbouring knots in 3D. To ameliorate, our original idea is to extend the bivariate biharmonic B‐spline to the trivariate one with novel formulations based on quadratic programming, approximating the properties of localization and partition of unity. And we design a novel discrete biharmonic operator which is optimized more robustly for a specific set of functions for unevenly sampled knots compared with previous methods. Our experiments demonstrate that our 3D discrete biharmonic operators are robust for unevenly distributed knots and illustrate that our algorithm is superior to previous algorithms.     

Shape‐from‐Operator: Recovering Shapes from Intrinsic Operators

We formulate the problem of shape‐from‐operator (SfO), recovering an embedding of a mesh from intrinsic operators defined through the discrete metric (edge lengths). Particularly interesting instances of our SfO problem include: shape‐from‐Laplacian, allowing to transfer style between shapes; shape‐from‐difference operator, used to synthesize shape analogies; and shape‐from‐eigenvectors, allowing to generate ‘intrinsic averages’ of shape collections. Numerically, we approach the SfO problem by splitting it into two optimization sub‐problems: metric‐from‐operator (reconstruction of the discrete metric from the intrinsic operator) and embedding‐from‐metric (finding a shape embedding that would realize a given metric, a setting of the multidimensional scaling problem). We study numerical properties of our problem, exemplify it on several applications, and discuss its imitations.     

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.     

Efficient encoding of texture coordinates guided by mesh geometry

In this paper, we investigate the possibilities of efficient encoding of UV coordinates associated with vertices of a triangle mesh. Since most parametrization schemes attempt to achieve at least some level of conformality, we exploit the similarity of the shapes of triangles in the mesh and in the parametrization. We propose two approaches building on this idea: first, applying a recently proposed generalization of the parallelogram predictor, using the inner angles of mesh triangles corresponding to the UV‐space triangles. Second, we propose an encoding method based on discrete Laplace operator, which also allows exploiting the information contained in the mesh geometry to efficiently encode the parametrization. Our experiments show that the proposed approach leads to savings of up to 3 bits per UV vertex, without loss of precision.     

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.     

A local tangential lifting differential method for triangular meshes

In this note we present a local tangential lifting (LTL) algorithm to compute differential quantities for triangular meshes obtained from regular surfaces. First, we introduce a new notation of the local tangential polygon and lift functions and vector fields on a triangular mesh to the local tangential polygon. Then we use the centroid weights proposed by Chen and Wu [4] to define the discrete gradient of a function on a triangular mesh. We also use our new method to define the discrete Laplacian operator acting on functions on triangular meshes. Higher order differential operators can also be computed successively. Our approach is conceptually simple and easy to compute. Indeed, our LTL method also provides a unified algorithm to estimate the shape operator and curvatures of a triangular mesh and derivatives of functions and vector fields. We also compare three different methods : our method, the least square method and Akima’s method to compute the gradients of functions.     

A local tangential lifting differential method for triangular meshes

In this note we present a local tangential lifting (LTL) algorithm to compute differential quantities for triangular meshes obtained from regular surfaces. First, we introduce a new notation of the local tangential polygon and lift functions and vector fields on a triangular mesh to the local tangential polygon. Then we use the centroid weights proposed by Chen and Wu [4] to define the discrete gradient of a function on a triangular mesh. We also use our new method to define the discrete Laplacian operator acting on functions on triangular meshes. Higher order differential operators can also be computed successively. Our approach is conceptually simple and easy to compute. Indeed, our LTL method also provides a unified algorithm to estimate the shape operator and curvatures of a triangular mesh and derivatives of functions and vector fields. We also compare three different methods : our method, the least square method and Akima’s method to compute the gradients of functions.     

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.     

基于Laplace-Beltrami算子特征向量的三维模型特征点检测与分析

针对三维模型的特征点检测问题,提出一种基于Laplace-Beltrami算子的特征点检测算法.对于给定的三维网格模型,首先构造离散Laplace-Beltrami算子矩阵,求解特征值与特征向量,随后在不同频率的特征向量上检测局部极值点和鞍点,最后通过基于特征值的加权公式把检测结果结合起来,实现对特征点不同显著度的可视化.实验对选取自SHREC2010数据集的三维网格模型进行特征点检测,在VS2013平台上使用OpenGL进行可视化.结果表明,文中算法在三维网格模型上取得准确的检测结果,在高噪声的模型上具有鲁棒性,对等距模型能得到高度相似的结果,并且能通过分布式计算处理大尺寸的三维模型.     

A note to the integrable discretization of the mKdV and Schrödinger equations

An approach has been proposed to the integrable discretization of nonlinear evolution equations. Based on the bilinear formalism, we choose appropriate substitution from hyperbolic operator into continuous Hirota operators and obtain several new kinds of integrable system through seeking their 3-soliton solutions, such as the mKdV equation, the nonlinear Schrödinger equation and so on. By applying Adomian decompose method, we discuss the numerical analysis property to the discrete mKdV equation. In addition, we also point out the relations between the above discreted equations and some well-known equations.     

Monotonic argument‐dependent OWA operators

The ordered weighted averaging (OWA) operator introduced by Yager is one of the most popular aggregation technique. In this paper, we develop two kinds of argument‐dependent OWA (DOWA) operators including the pessimistic‐dependent OWA (PE‐DOWA) operator and optimistic‐dependent OWA (OP‐DOWA) operator, that point out that the PE‐DOWA operator is decreasing and the OP‐DOWA operator is increasing, and investigate some properties of our proposed monotonic DOWA operators in detail. Furthermore, we introduce the concept of original function in which a gradient vector generates the weights of the PE‐DOWA and OP‐DOWA operators. Meanwhile, we propose two classes of original functions including summing‐type original function and multiplying‐type original function and investigate the sufficient monotonic conditions for the DOWA operators generated by the original functions. Finally, we discuss the characteristics and properties of our proposed DOWA operators in detail and use a numerical example to illustrate the flexibility of our proposed operators.     

Fluid-structure interactions using different mesh motion techniques

In this work, we compare different mesh moving techniques for monolithically-coupled fluid-structure interactions in arbitrary Lagrangian–Eulerian coordinates. The mesh movement is realized by solving an additional partial differential equation of harmonic, linear-elastic, or biharmonic type. We examine an implementation of time discretization that is designed with finite differences. Spatial discretization is based on a Galerkin finite element method. To solve the resulting discrete nonlinear systems, a Newton method with exact Jacobian matrix is used. Our results show that the biharmonic model produces the smoothest meshes but has increased computational cost compared to the other two approaches.     

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.     

Part‐type Segmentation of Articulated Voxel‐Shapes using the Junction Rule

We present a part‐type segmentation method for articulated voxel‐shapes based on curve skeletons. Shapes are considered to consist of several simpler, intersecting shapes. Our method is based on the junction rule: the observation that two intersecting shapes generate an additional junction in their joined curve‐skeleton near the place of intersection. For each curve‐skeleton point, we construct a piecewise‐geodesic loop on the shape surface. Starting from the junctions, we search along the curve skeleton for points whose associated loops make for suitable part cuts. The segmentations are robust to noise and discretization artifacts, because the curve skeletonization incorporates a single user‐parameter to filter spurious curve‐skeleton branches. Furthermore, segment borders are smooth and minimally twisting by construction. We demonstrate our method on several real‐world examples and compare it to existing part‐type segmentation methods.     

Continuous Self‐Collision Detection for Deformable Surfaces Interacting with Solid Models

In this paper, we propose a new continuous self‐collision detection (CSCD) method for a deformable surface that interacts with a simple solid model. The method is developed based on the radial‐view‐based culling method. Our method is suitable for the deformable surface that has large contact region with the solid model. The deformable surface may consist of small round‐shaped holes. At the pre‐processing stage, the holes of the deformable surface are filled with ghost triangles so as to make the mesh of the deformable surface watertight. An observer primitive (i.e. a point or a line segment) is computed so that it lies inside the solid model. At the runtime stage, the orientations of triangles with respect to the observer primitive are evaluated. The collision status of the deformable surface is then determined. We evaluated our method for several animations including virtual garments. Experimental results show that our method improves the process of CSCD.     

Continuous Matching via Vector Field Flow

We present a new method for non‐rigid shape matching designed to enforce continuity of the resulting correspondence. Our method is based on the recently proposed functional map representation, which allows efficient manipulation and inference but often fails to provide a continuous point‐to‐point mapping. We address this problem by exploiting the connection between the operator representation of mappings and flows of vector fields. In particular, starting from an arbitrary continuous map between two surfaces we find an optimal flow that makes the final correspondence operator as close as possible to the initial functional map. Our method also helps to address the symmetric ambiguity problem inherent in many intrinsic correspondence methods when matching symmetric shapes. We provide practical and theoretical results showing that our method can be used to obtain an orientation preserving or reversing map starting from a functional map that represents the mixture of the two. We also show how this method can be used to improve the quality of maps produced by existing shape matching methods, and compare the resulting map's continuity with results obtained by other operator‐based techniques.     

Turbulent flow computations on a hybrid cartesian point distribution using meshless solver LSFD-U

This paper may be considered as a sequel to one of our earlier works pertaining to the development of an upwind algorithm for meshless solvers. While the earlier work dealt with the development of an inviscid solution procedure, the present work focuses on its extension to viscous flows. A robust viscous discretization strategy is chosen based on positivity of a discrete Laplacian. This work projects meshless solver as a viable cartesian grid methodology. The point distribution required for the meshless solver is obtained from a hybrid cartesian gridding strategy. Particularly considering the importance of an hybrid cartesian mesh for RANS computations, the difficulties encountered in a conventional least squares based discretization strategy are highlighted. In this context, importance of discretization strategies which exploit the local structure in the grid is presented, along with a suitable point sorting strategy. Of particular interest is the proposed discretization strategies (both inviscid and viscous) within the structured grid block; a rotated update for the inviscid part and a Green-Gauss procedure based positive update for the viscous part. Both these procedures conveniently avoid the ill-conditioning associated with a conventional least squares procedure in the critical region of structured grid block. The robustness and accuracy of such a strategy is demonstrated on a number of standard test cases including a case of a multi-element airfoil. The computational efficiency of the proposed meshless solver is also demonstrated.     

Evaluating Hex‐mesh Quality Metrics via Correlation Analysis

Hexahedral (hex‐) meshes are important for solving partial differential equations (PDEs) in applications of scientific computing and mechanical engineering. Many methods have been proposed aiming to generate hex‐meshes with high scaled Jacobians. While it is well established that a hex‐mesh should be inversion‐free (i.e. have a positive Jacobian measured at every corner of its hexahedron), it is not well‐studied that whether the scaled Jacobian is the most effective indicator of the quality of simulations performed on inversion‐free hex‐meshes given the existing dozens of quality metrics for hex‐meshes. Due to the challenge of precisely defining the relations among metrics, studying the correlations among different quality metrics and their correlations with the stability and accuracy of the simulations is a first and effective approach to address the above question. In this work, we propose a correlation analysis framework to systematically study these correlations. Specifically, given a large hex‐mesh dataset, we classify the existing quality metrics into groups based on their correlations, which characterizes their similarity in measuring the quality of hex‐elements. In addition, we rank the individual metrics based on their correlations with the accuracy and stability metrics for simulations that solve a number of elliptic PDE problems. Our preliminary experiments suggest that metrics that assess the conditioning of the elements are more correlated to the quality of solving elliptic PDEs than the others. Furthermore, an inversion‐free hex‐mesh with higher average quality (measured by any quality metrics) usually leads to a more accurate and stable computation of elliptic PDEs. To support our correlation study and address the lack of a publicly available large hex‐mesh dataset with sufficiently varying quality metric values, we also propose a two‐level perturbation strategy to generate the desired dataset from a small number of meshes to exclude the influences of element numbers, vertex connectivity, and volume sizes to our study.