Scale-aware shape manipulation

A novel representation of a triangular mesh surface using a set of scale-inva~iant measures is proposed. The measures consist of angles of the triangles （triangle angles） and dihedral angles along the edges （edge angles） which are scale and rigidity independent. The vertex coordinates for a mesh give its scale-invariant measures, unique up to scale, rotation, and translation. Based on the representation of mesh using scale-invariant measures, a two-step iterative deformation algorithm is proposed, which can arbitrarily edit the mesh through simple handles interaction. The algorithm can explicitly preserve the local geometric details as much as possible in different scales even under severe editing operations including rotation, scaling, and shearing. The efficiency and robustness of the proposed algorithm are demonstrated by examples.     

Discrete heat kernel determines discrete Riemannian metric

The Laplace–Beltrami operator of a smooth Riemannian manifold is determined by the Riemannian metric. Conversely, the heat kernel constructed from the eigenvalues and eigenfunctions of the Laplace–Beltrami operator determines the Riemannian metric. This work proves the analogy on Euclidean polyhedral surfaces (triangle meshes), that the discrete heat kernel and the discrete Riemannian metric (unique up to a scaling) are mutually determined by each other. Given a Euclidean polyhedral surface, its Riemannian metric is represented as edge lengths, satisfying triangle inequalities on all faces. The Laplace–Beltrami operator is formulated using the cotangent formula, where the edge weight is defined as the sum of the cotangent of angles against the edge. We prove that the edge lengths can be determined by the edge weights unique up to a scaling using the variational approach.The constructive proof leads to a computational algorithm that finds the unique metric on a triangle mesh from a discrete Laplace–Beltrami operator matrix.     

基于曲面基本型的网格平滑与特征增强方法

曲面基本型描述了网格曲面的局部微分特征,针对该特征进行处理,提出一种网格平滑与特征增强方法。通过修改曲面离散基本型以平滑与增强网格特征,在约束最小二乘意义下通过重建曲面得到新网格,并结合稀疏矩阵线性系统求解器进行实时响应处理。实验结果表明,该方法简单高效,具有较好的降噪效果,可在一定程度上防止体积收缩与形状畸变。     

基于边长的三维形状插值

形状插值在计算机图形学和几何处理中是一个极其重要而基础的问题,在计算机动画等领域有 着广泛应用。注意到在平面三角网格和三维四面体网格插值问题中,对边长平方插值等价于对回拉度量进行插 值,因此具有等距扭曲和共形扭曲同时有界的良好性质。通过将其推广至曲面三角网格,提出了一种完全基于 边长的曲面三角网格插值算法。给定边长,在重建网格阶段,使用牛顿法对边长误差能量进行优化。并且给出 了其海森矩阵的解析正定化形式,从而避免了高代价的特征值分解步骤。注意到四面体网格的边长平方插值结 果具有极低曲率,意味着只需少许修改即可将其压平从而嵌入三维空间。因此提出先将曲面三角网格四面体化, 再从四面体网格的插值结果提取表面。然后将这表面作为初始化用于边长误差能量的牛顿迭代,从而使得收敛 结果更加接近全局最优。在一系列三角网格上进行了实验,结果说明了本文方法比之前方法的边长误差更小, 且得到的结果还是有界扭曲的。     

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.     

Interpolating Polyhedral Models Using Intrinsic Shape Parameters

Metamorphosis, or morphing, is the gradual transformation of one shape into another. It generally consists of two subproblems: the correspondence problem and the interpolation problem. This paper presents a solution to the interpolation problem of transforming one polyhedral model into another. It is an extension of the intrinsic shape interpolation scheme (T. W. Sederberg, P. Gao, G. Wang and H. Mu, ‘2-D shape blending: an intrinsic solution to the vertex path problem, SIGGRAPH '93, pp. 15–18.) for 2D polygons. Rather than considering a polyhedron as a set of independent points or faces, our solution treats a polyhedron as a graph representing the interrelations between faces. Intrinsic shape parameters, such as dihedral angles and edge lengths that interrelate the vertices and faces in the two graphs, are used for interpolation. This approach produces more satisfactory results than the linear or cubic curve paths would, and is translation and rotation invariant. © 1997 by John Wiley & Sons, Ltd.     

网格模型中直纹面的提取

提出一种基于直母线族提取与拟合的网格模型直纹面提取方法.首先通过集合误差权排序方法从模型中选择一个可信直母线种子,然后通过局部标架引导搜索邻接直母线,移动标架重复上述搜索过程,直到跨出网格边界或者开始循环搜索.利用"投影"光顺法对齐直母线段族首末端点,再通过定义欧氏6空间下的距离函数,将欧氏3空间下的直线族逼近直纹面问题转换成欧氏6空间下B样条曲线最小二乘拟合问题.为了使逼近的曲面光顺,在曲线拟合过程中引入了能量函数.与其他算法相比,文中方法获得了较强的直母线族的鲁棒性和精确性,并能有效、合理地拟合出光顺直纹面.     

基于测地距离的多边形网格模型约束变形

提出了一种基于测地线的多边形网格模型的约束变形方法.首先给定一系列的变形约束源(可以是点、线或者面)以及约束源的有效半径及变形目标(偏移量、缩放比例、旋转轴和旋转角度),然后通过计算三角形网格的各顶点到约束源的测地距离来确定各顶点的场值,这个场值将作为变形的权值.在基于欧氏距离的传统约束变形中,对某一约束区域的变形往往导致对约束源附近区域不需要的变形结果,而利用测地距离来计算各点的变形权值,可以很好地避免这种现象的出现.实验结果表明,这种变形方法是直观而且有效的.     

Material-aware differential mesh deformation using sketching interface

In this paper, we present a material-aware mesh deformation method using a sketching interface. Guided by user-specified material properties, our method can deform the surface mesh in a non-uniform way, while previous deformation techniques are mainly designed for uniform materials. The non-uniform deformation is achieved by material-dependent gradient field manipulation and Poisson-based reconstruction. Compared with previous material-oblivious deformation techniques, our method supplies better control of the deformation process and can generate more realistic results. We propose a novel detail representation that transforms geometric details between successive surface levels as a combination of dihedral angles and barycentric coordinates. This detail representation is similarity-invariant and fully compatible with material properties. Based on these two methods, we implement a multi-resolution deformation tool, allowing the user to edit a mesh inside a hierarchy in a material-aware manner. We demonstrate the effectiveness and robustness of our methods by several examples with real-world data.     

Intrinsic Parameterizations of Surface Meshes

Parameterization of discrete surfaces is a fundamental and widely‐used operation in graphics, required, for instance, for texture mapping or remeshing. As 3D data becomes more and more detailed, there is an increased need for fast and robust techniques to automatically compute least‐distorted parameterizations of large meshes. In this paper, we present new theoretical and practical results on the parameterization of triangulated surface patches. Given a few desirable properties such as rotation and translation invariance, we show that the only admissible parameterizations form a two‐dimensional set and each parameterization in this set can be computed using a simple, sparse, linear system. Since these parameterizations minimize the distortion of different intrinsic measures of the original mesh, we call them Intrinsic Parameterizations. In addition to this partial theoretical analysis, we propose robust, efficient and tunable tools to obtain least‐distorted parameterizations automatically. In particular, we give details on a novel, fast technique to provide an optimal mapping without fixing the boundary positions, thus providing a unique Natural Intrinsic Parameterization. Other techniques based on this parameterization family, designed to ease the rapid design of parameterizations, are also proposed.     

Two-dimensional Delaunay-based anisotropic mesh adaptation

Science and engineering applications often have anisotropic physics and therefore require anisotropic mesh adaptation. In common with previous researchers on this topic, we use metrics to specify the desired mesh. Where previous approaches are typically heuristic and sometimes require expensive optimization steps, our approach is an extension of isotropic Delaunay meshing methods and requires only occasional, relatively inexpensive optimization operations. We use a discrete metric formulation, with the metric defined at vertices. To map a local sub-mesh to the metric space, we compute metric lengths for edges, and use those lengths to construct a triangulation in the metric space. Based on the metric edge lengths, we define a quality measure in the metric space similar to the well-known shortest-edge to circumradius ratio for isotropic meshes. We extend the common mesh swapping, Delaunay insertion, and vertex removal primitives for use in the metric space. We give examples demonstrating our scheme’s ability to produce a mesh consistent with a discontinuous, anisotropic mesh metric and the use of our scheme in solution adaptive refinement.     

A Pixel-Based Framework for Data-Driven Clothing

We propose a novel approach to learning cloth deformation as a function of body pose, recasting the graph-like triangle mesh data structure into image-based data in order to leverage popular and well-developed convolutional neural networks (CNNs) in a two-dimensional Euclidean domain. Then, a three-dimensional animation of clothing is equivalent to a sequence of two-dimensional RGB images driven/choreographed by time dependent joint angles. In order to reduce nonlinearity demands on the neural network, we utilize procedural skinning of the body surface to capture much of the rotation/deformation so that the RGB images only contain textures of displacement offsets from skin to clothing. Notably, we illustrate that our approach does not require accurate unclothed body shapes or robust skinning techniques. Additionally, we discuss how standard image based techniques such as image partitioning for higher resolution can readily be incorporated into our framework.     

Articulated‐Motion‐Aware Sparse Localized Decomposition

Compactly representing time‐varying geometries is an important issue in dynamic geometry processing. This paper proposes a framework of sparse localized decomposition for given animated meshes by analyzing the variation of edge lengths and dihedral angles (LAs) of the meshes. It first computes the length and dihedral angle of each edge for poses and then evaluates the difference (residuals) between the LAs of an arbitrary pose and their counterparts in a reference one. Performing sparse localized decomposition on the residuals yields a set of components which can perfectly capture local motion of articulations. It supports intuitive articulation motion editing through manipulating the blending coefficients of these components. To robustly reconstruct poses from altered LAs, we devise a connection‐map‐based algorithm which consists of two steps of linear optimization. A variety of experiments show that our decomposition is truly localized with respect to rotational motions and outperforms state‐of‐the‐art approaches in precisely capturing local articulated motion.     

A new relative chain code in 3D

A new chain code to represent 3D discrete curves is proposed. The method is based on a search for relative changes in the 3D Euclidean space, composed of three main vectors: a reference vector, a support vector, and a change direction vector, utilized to obtain a directed simple path in a grid of 26 connected components. A set of rotation transformations is defined in the 3D Euclidean space, and an alphabet of only 25 symbols is required to represent any face, edge or vertex-connected discrete curve. Important properties of this code are found: independence under translation, rotation and mirror transformations, as well as high compression levels. A set of 3D curve-skeletons and digital elevation model data to study the terrain were utilized to prove the proposed code. Compared with the state-of-the-art, our method has more advantages: at first, it represents voxelized paths independently of vicinity, also it gives better representation for the tested objects and detects better the redundant parts. This fact is shown in the entropy calculated for 3D curve-skeletons: our method gives 3.03 bits/symbol, whereas the state-of-the-art method gives 4.35 bits/symbol. On the other hand, our proposed chain code uses 23% less memory than the well known Freeman code of 26 directions. In case of digital elevation models, our method improves memory for 36.1% regarding Freeman code and 10.7% regarding the well known relative code called orthogonal direction change chain code. Finally, average length of the chain code proposed is 14% shorter than the relative code of the state-of-the-art.     

Triangulation of <Emphasis Type="Italic">p</Emphasis>-Order Parametric Surfaces

The generation of triangulations on p-order parametric surfaces is a fundamental first step to numerical solutions for multidomain problems involving complex geometries such as those encountered in biological fluid dynamics and other applications. In this study we develop a novel, computationally efficient method for generating triangulations in computational space, which, under parametric mapping, are of high geometric quality. Computational efficiency is maintained over parametric orders (p) through approximating the parametric surface by a grid of simplified vector functions. Unlike other length metric approximations, a maximum bound on the error introduced to the calculation of lengths by this approximation is defined to ensure the fidelity of the transformation. This technique is applied to three parametric functions which demonstrate its robustness in handling high mesh distortions, singularities, and high order surfaces. Further, three complex high-order biological finite element meshes are triangulated. High mesh quality and a linear relationship between triangle generation and CPU time is observed for each of these meshes.     

Computing upper and lower bounds of rotation angles from digital images

Rotations in the discrete plane are important for many applications such as image matching or construction of mosaic images. We suppose that a digital image A is transformed to another digital image B by a rotation. In the discrete plane, there are many angles giving the rotation from A to B, which we call admissible rotation angles from A to B. For such a set of admissible rotation angles, there exist two angles that achieve the lower and the upper bounds. To find those lower and upper bounds, we use hinge angles as used in Nouvel and Rémila [Incremental and transitive discrete rotations, in: R. Reulke, U. Eckardt, B. Flash, U. Knauer, K. Polthier (Eds.), Combinatorial Image Analysis, Lecture Notes in Computer Science, vol. 4040, Springer, Berlin, 2006, pp. 199-213]. A sequence of hinge angles is a set of particular angles determined by a digital image in the sense that any angle between two consecutive hinge angles gives the identical rotation of the digital image. We propose a method for obtaining the lower and the upper bounds of admissible rotation angles using hinge angles from a given Euclidean angle or from a pair of corresponding digital images.     

一种3维动画中间帧非线性插值算法

关键帧动画是3维动画制作的常用模式，中间帧插值又是关键帧动画中最为繁琐的环节。提出了一种针对无骨架3维网格模型的非线性插值算法，用于对网格模型的关键帧姿态进行插补，自动生成中间帧动画序列。该算法首先计算动画角色的网格模型各三角片在相邻关键帧中的仿射变换，并据此生成变形梯度向量，作为3维网格模型的形变信息，这种表示形式体现了变形过程中网格顶点之间的局部互相关关系。随后将各仿射变换分解为旋转成分与拉伸缩放成分，对拉伸缩放成分进行线性插值，而对旋转成分采用四元数插值算法进行非线性插值，合成中间帧姿态的变形梯度向量，并据此计算出中间帧网格模型。当相邻关键帧姿态存在较大差异时，该算法也能快速生成平稳而生动的中间帧动画，可有效减少关键帧的数量，提高动画制作效率。     

空间三角网格曲面的边界提取方法

边界是曲面的重要特征之一,在形状匹配、曲面拼接等方面有着重要作用.由于空间网格数据分布不规则,不能从点的坐标直接得到曲面的边界,因此提出了一种空间三角网格曲面的边界提取方法,通过判断一个点的邻接点是否都能通过三角网格的边组成闭合曲线来获取边界点.该方法易于实现、适应性强,并应用于计算机辅助文物复原系统,实验证明,此算法能正确处理空间三角网格数据,且效率很高.