Quasi-Developable Mesh Surface Interpolation via Mesh Deformation

We present a new algorithm for finding a most "developable" smooth mesh surface to interpolate a given set of arbitrary points or space curves. Inspired by the recent progress in mesh editing that employs the concepts of preserving the Laplacian coordinates and handle-based shape editing, we formulate the interpolation problem as a mesh deformation process that transforms an initial developable mesh surface, such as a planar figure, to a final mesh surface that interpolates the given points and/or curves. During the deformation, the developability of the intermediate mesh is maintained by means of preserving the zero-valued Gaussian curvature on the mesh. To treat the high nonlinearity of the geometric constrains owing to the preservation of Gaussian curvature, we linearize those nonlinear constraints using Taylor expansion and eventually construct a sparse and over-determined linear system which is subsequently solved by a robust least-squares solution. By iteratively performing this procedure, the initial mesh is gradually and smoothly "dragged" to the given points and/or curves. The initial experimental data has shown some promising aspects of the proposed algorithm as a general quasi-developable surface interpolation tool.     

织物模拟中的自适应网格剖分研究

本文提出一种在织物模拟中的动态网格剖分方法，针对传统模拟算法中因网格剖分固定和曲面整体网格均匀剖分造成模拟误差与计算耗费，分别从织物物理和几何角度出发，提出在动态模拟过程中的自适应的网格剖分方法。利用模拟过程中曲面片局部形变信息，对网格进行动态剖分与合并，有效提高了模拟效率。经实际应用表明：该算法具有模拟效率高、易于计算机实现等优点，特别在对非均匀形变物体模拟中，该算法从模拟效率和精度均得到满意结果。     

拓扑最优的可展网格曲面放样建模

在服装、制鞋、钣金等行业的产品外形设计中,经常需要插值多条特征空间曲线,构建可展曲面 (可无伸缩地展开成平面)。针对这一问题,基于Dijkstra算法提出了一种新的放样建模算法：给定多条参数曲线,经过自适应离散后,寻找一个全局拓扑最优的可展网格放样曲面（针对不同的目标曲面能量,同样可以产生目标能量定义的拓扑最优的放样网格曲面）。该问题最终可转化为有向无环图(DAG)的单源最短路径的求解,算法的时间复杂度为O(N log N),其中N为搜寻空间。测试结果表明该算法在相关行业的放样外形设计方面具有实际工程应用价值。     

基于能量最小化的网格优化算法

对网格优化的方法进行研究,提出一种基于能量最小化的网格优化算法.给定一定数量的三维散乱点数据和一个初始三角网格,使用能量最小化算法对网格顶点位置进行优化,使网格顶点更好地逼近三维散乱点数据;网格也更加逼近实际曲面.实验结果表明,使用该算法能够获得形状良好的网格.     

三维网格曲面的可展性优化算法

可展曲面是每点高斯曲率均为0的曲面,具有许多良好的性质,因此在工业中具有很多应用.将一般的曲面用可展曲面来逼近表示具有现实意义.以此为目的,文中设计了一个有效的算法来处理一般的曲面,使得处理后的曲面尽可能满足可展的性质,同时与初始的曲面尽量地接近.首先利用最小范数方法来对网格曲面进行处理,得到初始预测的网格曲面.初始预测曲面具有良好的可展性,但是不能较好地保持网格的局部结构.然后利用尽可能刚性(As-rigid-as-possible)的方法,在初始预测曲面的基础上进行修正得到新的网格曲面.为了保持局部结构,作者的方法可以是基于顶点邻域的,也可以是基于三角形的.这两个过程可以迭代进行,直至得到满足要求的结果.与以往的算法相比,文中算法能保证结果收敛,迭代次数更少,且能得到更好的结果.     

基于力学模型的曲面展开通用算法

为了解决曲面展开算法实现复杂、累积误差和通用性不佳的缺点,提出一种在三维空间内基于能量模型的曲面展开算法,待展开的曲面以三角网格形式表示,将曲面简化为三角网格的顶点组成的质点系统,通过在每个质点上加上适当的力使得三角网格产生相应的变形,达到将曲面展开的效果.与现有算法相比,该曲面展开算法适用于任意形状曲面,不需要使用投影平面,整个变形完全由网格顶点受力来驱动,便于实现、适用面广、对于不可展曲面也能得到较好的展开效果,而不会出现裂纹现象.     

一种有效的隐式约束动力学布料动画方法

布料动画中,通常采用施加约束的方式限制布料的过度拉伸.已有的研究工作没有充分考虑拉伸约束与弯曲形变之间的关系,构造的动画模型并不完善,无法模拟布料无拉伸而多褶皱的"刚柔"相混的复杂变形效果.针对此问题,提出一种基于隐式约束力的布料动画方法.首先,建立有效的布料弯曲受力模型,并提出一种动态适应性约束方法,能够同时处理布料运动过程中结构和剪切2种不同类型的拉伸,避免单一结构拉伸约束导致的"过剪切"变形或者过约束导致的"刚性"失真效果;建立碰撞约束,避免局部调整穿透质点引起的过度拉伸问题.其次,将各种约束以隐式约束力的形式增加到动力学系统中,采用约束型迭代精化的方法进行求解.实验结果表明,该方法稳定有效,能够在保持布料弯曲形变的前提下,将拉伸控制在合理范围内,真实地刻画布料"易弯抗拉"的变形特征,实现逼真的布料变形动画模拟.     

Boundary Handling at Cloth–Fluid Contact

We present a robust and efficient method for the two‐way coupling between particle‐based fluid simulations and infinitesimally thin solids represented by triangular meshes. Our approach is based on a hybrid method that combines a repulsion force approach with a continuous intersection handling to guarantee that no penetration occurs. Moreover, boundary conditions for the tangential component of the fluid's velocity are implemented to model the different slip conditions. The proposed method is particularly useful for dynamic surfaces, like cloth and thin shells. In addition, we demonstrate how standard fluid surface reconstruction algorithms can be modified to prevent the calculated surface from intersecting close objects. For both the two‐way coupling and the surface reconstruction, we take into account that the fluid can wet the cloth. We have implemented our approach for the bidirectional interaction between liquid simulations based on Smoothed Particle Hydrodynamics (SPH) and standard mesh‐based cloth simulation systems.     

Continuum-based Strain Limiting

We present Continuum-based Strain Limiting (CSL) – a new method for limiting deformations in physically-based cloth simulations. Despite recent developments for nearly inextensible materials, the efficient simulation of general biphasic textiles and their anisotropic behavior remains challenging. Many approaches use soft materials and enforce limits on edge elongations, leading to discretization-dependent behavior. Moreover, they offer no explicit control over shearing and stretching unless specifically aligned meshes are used. Based on a continuum deformation measure, our method allows accurate control over all strain components using individual thresholds. We impose deformation limits element-wise and cast the problem as a 6×6 system of linear equations. CSL can be combined with any cloth simulator and, as a velocity filter, integrates seamlessly into standard collision handling.     

Drawing on air: input techniques for controlled 3D line illustration

Stretch-free surface flattening has been requested by a variety of applications. At present, the most difficult problem is how to segment a given model into nearly developable atlases so that a nearly stretch-free flattening can be computed. The criterion for segmentation is needed to evaluate the possibility of flattening a given surface patch, which should be fast computed. In this paper, we present a method to compute the length-preserved free boundary (LPFB) of a mesh patch, which speeds up the mesh parameterization. The distortion on parameterization can then be employed as the criterion in a trial-and-error algorithm for segmenting a given model into nearly developable atlases. The computation of LPFB is formulated as a numerical optimization problem in the angle space, where we are trying to optimize the angle excesses on the boundary while preserving the constraints derived from the closed-path theorem and the length preservation.     

Computing length-preserved free boundary for quasi-developable mesh segmentation

Stretch-free surface flattening has been requested by a variety of applications. At present, the most difficult problem is how to segment a given model into nearly developable atlases so that a nearly stretch-free flattening can be computed. The criterion for segmentation is needed to evaluate the possibility of flattening a given surface patch, which should be fast computed. In this paper, we present a method to compute the length-preserved free boundary (LPFB) of a mesh patch which speeds up the mesh parameterization. The distortion on parameterization can then be employed as the criterion in a trial-and-error algorithm for segmenting a given model into nearly developable atlases. The computation of LPFB is formulated as a numerical optimization problem in the angle space, where we are trying to optimize the angle excesses on the boundary while preserving the constraints derived from the closed-path theorem and the length preservation.     

Geometry-aware bases for shape approximation

We introduce a new class of shape approximation techniques for irregular triangular meshes. Our method approximates the geometry of the mesh using a linear combination of a small number of basis vectors. The basis vectors are functions of the mesh connectivity and of the mesh indices of a number of anchor vertices. There is a fundamental difference between the bases generated by our method and those generated by geometry-oblivious methods, such as Laplacian-based spectral methods. In the latter methods, the basis vectors are functions of the connectivity alone. The basis vectors of our method, in contrast, are geometry-aware since they depend on both the connectivity and on a binary tagging of vertices that are "geometrically important" in the given mesh (e.g., extrema). We show that, by defining the basis vectors to be the solutions of certain least-squares problems, the reconstruction problem reduces to solving a single sparse linear least-squares problem. We also show that this problem can be solved quickly using a state-of-the-art sparse-matrix factorization algorithm. We show how to select the anchor vertices to define a compact effective basis from which an approximated shape can be reconstructed. Furthermore, we develop an incremental update of the factorization of the least-squares system. This allows a progressive scheme where an initial approximation is incrementally refined by a stream of anchor points. We show that the incremental update and solving the factored system are fast enough to allow an online refinement of the mesh geometry     

A computational model of bounded developable surfaces with application to image‐based three‐dimensional reconstruction

Developable surfaces have been extensively studied in computer graphics because they are involved in a large body of applications. This type of surfaces has also been used in computer vision and document processing in the context of three‐dimensional (3D) reconstruction for book digitization and augmented reality. Indeed, the shape of a smoothly deformed piece of paper can be very well modeled by a developable surface. Most of the existing developable surface parameterizations do not handle boundaries or are driven by overly large parameter sets. These two characteristics become issues in the context of developable surface reconstruction from real observations. Our main contribution is a generative model of bounded developable surfaces that solves these two issues. Our model is governed by intuitive parameters whose number depends on the actual deformation and including the “flat shape boundary”. A vast majority of the existing image‐based paper 3D reconstruction methods either require a tightly controlled environment or restricts the set of possible deformations. We propose an algorithm for reconstructing our model's parameters from a general smooth 3D surface interpolating a sparse cloud of 3D points. The latter is assumed to be reconstructed from images of a static piece of paper or any other developable surface. Our 3D reconstruction method is well adapted to the use of keypoint matches over multiple images. In this context, the initial 3D point cloud is reconstructed by structure‐from‐motion for which mature and reliable algorithms now exist and the thin‐plate spline is used as a general smooth surface model. After initialization, our model's parameters are refined with model‐based bundle adjustment. We experimentally validated our model and 3D reconstruction algorithm for shape capture and augmented reality on seven real datasets. The first six datasets consist of multiple images or videos and a sparse set of 3D points obtained by structure‐from‐motion. The last dataset is a dense 3D point cloud acquired by structured light. Our implementation has been made publicly available on the authors' web home pages. Copyright © 2012 John Wiley & Sons, Ltd.     

数值稳定的可展网格仿真方法(英文)

动态可展曲面是采用哈密尔顿原理的一类新型动态模型。详细论述了这类动态模型的数值计算引擎。大量实验结果表明:(1)光滑和褶皱的可展曲面都可用动态网格模拟;(2)传统的挑战性问题如纸张褶皱仿真和塑性服装建模等都可用动态网格以稳定、快速的方式进行计算。     

Adaptive meshing for cloth animation

Most of the numerical simulation methods regarding cloth draping are based on mechanical models. Graphically, the representation of this model is likely to be a uniform grid. Fabrics being a very flexible material, a number of wrinkles appear on its surface when submitted to free or constrained motion (collision/applied load, supports). The problem regarding the simulation run is to represent realistically the mechanical system surface and its associated motion which are strongly related to mesh discretization. We propose a new method based on adaptive meshing allowing the mechanical system to behave without any constraint related to a uniform mesh. Numerical examples are given to show the efficiency of the method.     

一种提取可展网格曲面的新方法

可展曲面是每一点高斯曲率为零的曲面,由于其具有优良性质,因此在工程实践中得到广泛应用。为便于各种网格处理,从一个整体表面网格模型中获取可展区域具有重要意义。针对目前相关方法中存在的不足,本文提出了一个提取可展网格面片的新方法。首先利用高斯曲率提取可展网格面片,接着对分割得到的层可展区域进行微分几何上的直纹面的拟合,然后根据拟合的直纹面方程来判断是否可展,最后根据每种可展类型的直母线性质来判定可展类型。获得的可展面片中包括连续柱面和连续锥面,而传统方法无法获得;另外,确定获得面片的可展类型便于下一步网格处理。与已有方法相比,此方法更具有可行性和优越性。     

基于几何测量和变形的真实感织物模拟

提出一种有效、直观的基于几何测量和网格变形的织物模拟方法,可以获得具有不同面料属性的织物真实感形态.织物几何测量方法能够度量反映面料几何属性的3个关键特征,包括复原性、拉伸性和弯曲性.对应这3个几何属性度量,建立包括顶点位置、边长和二面角约束能量项的基于微分网格变形的泛函能量优化模型.3个变形能量项各自对应的权重是从每种真实面料测量数据中量化统计得到.该变形能量函数可以统一在最小二乘数值优化中求解,通过过程优化和权重设置,即可模拟到真实织物行为.实验结果表明,该方法可以有效地仿真到不同面料材质的织物真实感效果.     

融合QPSO算法的多精度布料仿真建模方法

在布料建模领域，如何快速模拟布料形变之后的褶皱细节是研究的热点。通过使用多精度布料建模方法，在布料的不同形变区域使用不同精度的网格，可以有效平衡建模的精度和速度，已有的工作主要是在布料形变过程中，动态计算出布料质点邻域的曲率，依据人为设定的阈值，划分出布料的多精度区域，而在大部分场景中，布料的变形模式没有规律，固定不变的阈值可能会影响布料的仿真效果。针对该问题，首先将基于量子行为的粒子群算法引入建模过程，通过粒子群算法对布料表面的搜索，提高了布料弯曲部位的搜索效率，优化了多精度布料的建模速度和精度，其次针对布料仿真运动过程进行研究，参考布料受空气阻力的数学模型，以及粒子动力学中的数值积分方法，优化布料运动的仿真计算方法。实验证明，与现有布料多精度方法相比，该方法能较快检测到布料褶皱区域并判断是否需要细化，且能较好地表现出布料仿真过程中空气阻力对布料造成的形变。     

基于特征的图像网格生成方法

基于网格形变的图像缩放算法是目前的一个研究热点。适当的图像网格表示是这类算法成功的关键之一。提出一种基于图像特征的三角形网格生成算法。提取图像分割形成区域的边缘特征点,与图像四条边界上均匀分布的点一起,作为改进的Dart-throwing算法的初始点集。用距离变换计算每个像素到最近边缘线的距离,作为Dart-throwing算法的控制参量;所生成的网格点集接近边缘线时密集,远离边缘线时稀疏。最后用Delaunay算法形成图像的三角形网格表示。实验结果表明,所生成的三角网格较好地体现了图像的结构特征,并且有效减少了网格点数目,有利于提高后续算法的处理效率。     

Evolutionary computation applied to mesh optimization of a 3-Dfacial image

We apply evolutionary algorithms to the approximation of a three-dimensional image of a human face using a triangular mesh. The problem is how to locate a limited number of node points such that the mesh approximates the facial surface as closely as possible. Two evolutionary algorithms are implemented and compared. The first does selection and reproduction in the population of node points in a single triangulation. The second is a genetic algorithm in which a set of different triangulations is regarded as a population. We expect that such evolutionary computation can be used in other engineering applications which share the same problem of surface approximation