ARAP Revisited Discretizing the Elastic Energy using Intrinsic Voronoi Cells

As-rigid-as-possible (ARAP) surface modelling is widely used for interactive deformation of triangle meshes. We show that ARAP can be interpreted as minimizing a discretization of an elastic energy based on non-conforming elements defined over dual orthogonal cells of the mesh. Using the intrinsic Voronoi cells rather than an orthogonal dual of the extrinsic mesh guarantees that the energy is non-negative over each cell. We represent the intrinsic Delaunay edges extrinsically as polylines over the mesh, encoded in barycentric coordinates relative to the mesh vertices. This modification of the original ARAP energy, which we term iARAP, remedies problems stemming from non-Delaunay edges in the original approach. Unlike the spokes-and-rims version of the ARAP approach it is less susceptible to the triangulation of the surface. We provide examples of deformations generated with iARAP and contrast them with other versions of ARAP. We also discuss the properties of the Laplace-Beltrami operator implicitly introduced with the new discretization.     

Semi-Supervised Learning on Riemannian Manifolds

We consider the general problem of utilizing both labeled and unlabeled data to improve classification accuracy. Under the assumption that the data lie on a submanifold in a high dimensional space, we develop an algorithmic framework to classify a partially labeled data set in a principled manner. The central idea of our approach is that classification functions are naturally defined only on the submanifold in question rather than the total ambient space. Using the Laplace-Beltrami operator one produces a basis (the Laplacian Eigenmaps) for a Hilbert space of square integrable functions on the submanifold. To recover such a basis, only unlabeled examples are required. Once such a basis is obtained, training can be performed using the labeled data set. Our algorithm models the manifold using the adjacency graph for the data and approximates the Laplace-Beltrami operator by the graph Laplacian. We provide details of the algorithm, its theoretical justification, and several practical applications for image, speech, and text classification.     

基于Laplace谱嵌入和Mean Shift的 三角网格一致性分割

针对现有网格分割算法对模型姿态及噪声敏感的不足,提出一种基于Laplace谱嵌入和Mean Shift聚类的网格一致性分割算法。采用Laplace-Beltrami算子,将3维空域中的网格模型转化成高维Laplace谱域中的标准型,降低了姿态变化和噪声对分割算法的影响,并增强了网格的结构可分性;在高维谱域中,采用非参数核聚类MeanShift算法,获取模型有视觉意义的语义区域。实验结果表明:该算法可以快速有效地实现具有分支结构三角网格模型的有意义分割且对模型姿态和噪声具有较好的鲁棒性。     

Point-based manifold harmonics

This paper proposes an algorithm to build a set of orthogonal Point-Based Manifold Harmonic Bases (PB-MHB) for spectral analysis over point-sampled manifold surfaces. To ensure that PB-MHB are orthogonal to each other, it is necessary to have symmetrizable discrete Laplace-Beltrami Operator (LBO) over the surfaces. Existing converging discrete LBO for point clouds, as proposed by Belkin et al. [CHECK END OF SENTENCE], is not guaranteed to be symmetrizable. We build a new point-wisely discrete LBO over the point-sampled surface that is guaranteed to be symmetrizable, and prove its convergence. By solving the eigen problem related to the new operator, we define a set of orthogonal bases over the point cloud. Experiments show that the new operator is converging better than other symmetrizable discrete Laplacian operators (such as graph Laplacian) defined on point-sampled surfaces, and can provide orthogonal bases for further spectral geometric analysis and processing tasks.     

Shape Analysis Using the Auto Diffusion Function

Scalar functions defined on manifold triangle meshes is a starting point for many geometry processing algorithms such as mesh parametrization, skeletonization, and segmentation. In this paper, we propose the Auto Diffusion Function (ADF) which is a linear combination of the eigenfunctions of the Laplace-Beltrami operator in a way that has a simple physical interpretation. The ADF of a given 3D object has a number of further desirable properties: Its extrema are generally at the tips of features of a given object, its gradients and level sets follow or encircle features, respectively, it is controlled by a single parameter which can be interpreted as feature scale, and, finally, the ADF is invariant to rigid and isometric deformations.
We describe the ADF and its properties in detail and compare it to other choices of scalar functions on manifolds. As an example of an application, we present a pose invariant, hierarchical skeletonization and segmentation algorithm which makes direct use of the ADF.     

基于泊松标量场的任意亏格网格切割

网格切割在图形处理领域有着广泛的应用,为了更加有效和简单地得到同胚于圆盘的开网格,提出一种基于泊松标量场的三角网格切割算法.对于给定的任意网格,通过求解泊松方程构造标量场来选取临界点,并采用最速下降法给出临界点到边界或者初始点的切割路径;对于亏格不为零的网格,基于Morse理论,通过构造一个调和标量场来得到鞍点,并将它们连接到边界.该方法把任意亏格网格切割成与圆盘同胚的单边界网格,减小了在网格展开过程中产生的扭曲.实验结果表明,在给定临界点的情况下,采用文中算法得到的切割路径能很好地逼近最短路径,而且不受网格限制,适用于任意亏格的开或闭网格.     

Direct Discretization Method for the Cahn–Hilliard Equation on an Evolving Surface

We propose a simple and efficient direct discretization scheme for solving the Cahn–Hilliard (CH) equation on an evolving surface. By using a conservation law and transport formulae, we derive the CH equation on evolving surfaces. An evolving surface is discretized using an unstructured triangular mesh. The discrete CH equation is defined on the surface mesh and its dual surface polygonal tessellation. The evolving triangular surfaces are then realized by moving the surface nodes according to a given velocity field. The proposed scheme is based on the Crank–Nicolson scheme and a linearly stabilized splitting scheme. The scheme is second-order accurate, with respect to both space and time. The resulting system of discrete equations is easy to implement, and is solved by using an efficient biconjugate gradient stabilized method. Several numerical experiments are presented to demonstrate the performance and effectiveness of the proposed numerical scheme.     

Sparse Approximation of 3D Meshes Using the Spectral Geometry of the Hamiltonian Operator

The discrete Laplace operator is ubiquitous in spectral shape analysis, since its eigenfunctions are provably optimal in representing smooth functions defined on the surface of the shape. Indeed, subspaces defined by its eigenfunctions have been utilized for shape compression, treating the coordinates as smooth functions defined on the given surface. However, surfaces of shapes in nature often contain geometric structures for which the general smoothness assumption may fail to hold. At the other end, some explicit mesh compression algorithms utilize the order by which vertices that represent the surface are traversed, a property which has been ignored in spectral approaches. Here, we incorporate the order of vertices into an operator that defines a novel spectral domain. We propose a method for representing 3D meshes using the spectral geometry of the Hamiltonian operator, integrated within a sparse approximation framework. We adapt the concept of a potential function from quantum physics and incorporate vertex ordering information into the potential, yielding a novel data-dependent operator. The potential function modifies the spectral geometry of the Laplacian to focus on regions with finer details of the given surface. By sparsely encoding the geometry of the shape using the proposed data-dependent basis, we improve compression performance compared to previous results that use the standard Laplacian basis and spectral graph wavelets.     

High-resolution compact numerical method for the system of 2D quasi-linear elliptic boundary value problems and the solution of normal derivatives on an irrational domain with engineering applications

In this paper, we present a novel approach to attain fourth-order approximate solution of 2D quasi-linear elliptic partial differential equation on an irrational domain. In this approach, we use nine grid points with dissimilar mesh in a single compact cell. We also discuss appropriate fourth-order numerical methods for the solution of the normal derivatives on a dissimilar mesh. The method has been protracted for solving system of quasi-linear elliptic equations. The convergence analysis is discussed to authenticate the proposed numerical approximation. On engineering applications, we solve various test problems, such as linear convection–diffusion equation, Burgers’equation, Poisson equation in singular form, NS equations, bi- and tri-harmonic equations and quasi-linear elliptic equations to show the efficiency and accuracy of the proposed methods. A comprehensive comparative computational experiment shows the accuracy, reliability and credibility of the proposed computational approach.

     

Gradient field based inhomogeneous volumetric mesh deformation for maxillofacial surgery simulation

This paper presents a novel inhomogeneous volumetric mesh deformation approach by gradient field manipulation, and uses it for maxillofacial surgery simulation. The study is inspired by the state-of-the-art surface deformation techniques based on differential representations. Working in the volumetric domain instead of on only the surface can preserve the volumetric details much better, avoid local self-intersections, and achieve better deformation propagation because of the internal mesh connections. By integrating the mesh cell material stiffness parameter into our new discrete volumetric Laplacian operator, it is very convenient to incorporate inhomogeneous materials into the deformation framework. In addition, the system matrix for solving the volumetric harmonic field to handle the local transformation problem is the same used for Poisson reconstruction equation, thus it requires solving essentially only one global linear system. The system is easy to use, and can accept explicit rotational constraints, or only translational constraints to drive the deformation. One typical maxillofacial surgery case was simulated by the new methodology with inhomogeneous material estimated directly from CT data, and compared to the commonly used finite element method (FEM) approach. The results demonstrated that the deformation methodology achieved good accuracy, as well as interactive performance. Therefore, the usage of our volumetric mesh deformation approach is relevant and suitable for daily clinical practice.     

Harmonic point cloud orientation

In this work we propose a new method for estimating the normal orientation of unorganized point clouds. Consistent assignment of normal orientation is a challenging task in the presence of sharp features, nearby surface sheets, noise, undersampling, and missing data. Existing approaches, which consider local geometric properties often fail when operating on such point clouds as local neighborhood measures inherently face issues of robustness. Our approach circumvents these issues by orienting normals based on globally smooth functions defined on point clouds with measures that depend only on single points. More specifically, we consider harmonic functions, or functions which lie in the kernel of the point cloud Laplace-Beltrami operator. Each harmonic function in the set is used to define a gradient field over the point cloud. The problem of normal orientation is then cast as an assignment of cross-product ordering between gradient fields. Global smoothness ensures a highly consistent orientation, rendering our method extremely robust in the presence of imperfect point clouds.     

A Riemannian approach to graph embedding

In this paper, we make use of the relationship between the Laplace-Beltrami operator and the graph Laplacian, for the purposes of embedding a graph onto a Riemannian manifold. To embark on this study, we review some of the basics of Riemannian geometry and explain the relationship between the Laplace-Beltrami operator and the graph Laplacian. Using the properties of Jacobi fields, we show how to compute an edge-weight matrix in which the elements reflect the sectional curvatures associated with the geodesic paths on the manifold between nodes. For the particular case of a constant sectional curvature surface, we use the Kruskal coordinates to compute edge weights that are proportional to the geodesic distance between points. We use the resulting edge-weight matrix to embed the nodes of the graph onto a Riemannian manifold. To do this, we develop a method that can be used to perform double centring on the Laplacian matrix computed from the edge-weights. The embedding coordinates are given by the eigenvectors of the centred Laplacian. With the set of embedding coordinates at hand, a number of graph manipulation tasks can be performed. In this paper, we are primarily interested in graph-matching. We recast the graph-matching problem as that of aligning pairs of manifolds subject to a geometric transformation. We show that this transformation is Pro-crustean in nature. We illustrate the utility of the method on image matching using the COIL database.     

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.     

A Nyström-based finite element method on polygonal elements

We consider families of finite elements on polygonal meshes, that are defined implicitly on each mesh cell as solutions of local Poisson problems with polynomial data. Functions in the local space on each mesh cell are evaluated via Nyström discretizations of associated integral equations, allowing for curvilinear polygons and non-polynomial boundary data. Several experiments demonstrate the approximation quality of interpolated functions in these spaces.     

G1连续几何偏微分方程Bézier曲面的构造

基于三角形和四边形网格上Laplace-Beltrami算子、高斯曲率和平均曲率的离散及其收敛性分析,提出了一种使用四阶几何流构造几何偏微分方程Bézier曲面的方法.使用该方法构造出的Bézier曲面既具有几何偏微分方程曲面的最优性质,同时又满足G1连续性.算法收敛性的数值实验表明该方法是有效的.     

Centroidal Voronoi diagrams for isotropic surface remeshing

This paper proposes a new method for isotropic remeshing of triangulated surface meshes. Given a triangulated surface mesh to be resampled and a user-specified density function defined over it, we first distribute the desired number of samples by generalizing error diffusion, commonly used in image halftoning, to work directly on mesh triangles and feature edges. We then use the resulting sampling as an initial configuration for building a weighted centroidal Voronoi diagram in a conformal parameter space, where the specified density function is used for weighting. We finally create the mesh by lifting the corresponding constrained Delaunay triangulation from parameter space. A precise control over the sampling is obtained through a flexible design of the density function, the latter being possibly low-pass filtered to obtain a smoother gradation. We demonstrate the versatility of our approach through various remeshing examples.     

Weighted minimal hypersurface reconstruction

Many problems in computer vision can be formulated as a minimization problem for an energy functional. If this functional is given as an integral of a scalar-valued weight function over an unknown hypersurface, then the sought-after minimal surface can be determined as a solution of the functional's Euler-Lagrange equation. This paper deals with a general class of weight functions that may depend on surface point coordinates as well as surface orientation. We derive the Euler-Lagrange equation in arbitrary dimensional space without the need for any surface parameterization, generalizing existing proofs. Our work opens up the possibility of solving problems involving minimal hypersurfaces in a dimension higher than three, which were previously impossible to solve in practice. We also introduce two applications of our new framework: We show how to reconstruct temporally coherent geometry from multiple video streams, and we use the same framework for the volumetric reconstruction of refractive and transparent natural phenomena, bodies of flowing water.     

Spectral mesh deformation

In this paper, we present a novel spectral method for mesh deformation based on manifold harmonics transform. The eigenfunctions of the Laplace–Beltrami operator give orthogonal bases for parameterizing the space of functions defined on the surfaces. The geometry and motion of the original irregular meshes can be compactly encoded using the low-frequency spectrum of the manifold harmonics. Using the spectral method, the size of the linear deformation system can be significantly reduced to achieve interactive computational speed for manipulating large triangle meshes. Our experimental results demonstrate that only a small spectrum is needed to achieve undistinguishable deformations for large triangle meshes. The spectral mesh deformation approach shows great performance improvement on computational speed over its spatial counterparts.     

Spectral Mesh Simplification

The spectrum of the Laplace-Beltrami operator is instrumental for a number of geometric modeling applications, from processing to analysis. Recently, multiple methods were developed to retrieve an approximation of a shape that preserves its eigenvectors as much as possible, but these techniques output a subset of input points with no connectivity, which limits their potential applications. Furthermore, the obtained Laplacian results from an optimization procedure, implying its storage alongside the selected points. Focusing on keeping a mesh instead of an operator would allow to retrieve the latter using the standard cotangent formulation, enabling easier processing afterwards. Instead, we propose to simplify the input mesh using a spectrum-preserving mesh decimation scheme, so that the Laplacian computed on the simplified mesh is spectrally close to the one of the input mesh. We illustrate the benefit of our approach for quickly approximating spectral distances and functional maps on low resolution proxies of potentially high resolution input meshes.     

On the inclusion of the recombination term in discretizations of the semiconductor device equations

In this paper we consider the semiconductor device equations for stationary problems where the recombination term cannot be neglected. We illustrate our ideas by deriving systematically discretizations of the two continuity equations and of the Poisson equation in the case of one space dimension. This approach leads to finite difference schemes for the continuity equations which are related to the Scharfetter-Gummel scheme. For the Poisson equation we obtain a new finite difference scheme which reduces to a scheme of Mock if the mesh is uniform and the recombination is zero.