Quasi-angle-preserving mesh deformation using the least-squares approach

We propose an angle-based mesh representation, which is invariant under translation, rotation, and uniform scaling, to encode the geometric details of a triangular mesh. Angle-based mesh representation consists of angle quantities defined on the mesh, from which the mesh can be reconstructed uniquely up to translation, rotation, and uniform scaling. The reconstruction process requires solving three sparse linear systems： the first system encodes the length of edges between vertices on the mesh, the second system encodes the relationship of local frames between two adjacent vertices on the mesh, and the third system defines the position of the vertices via the edge length and the local frames. From this angle-based mesh representation, we propose a quasi-angle-preserving mesh deformation system with the least-squares approach via detail-preserving mesh editing examples are presented to handle translation, rotation, and uniform scaling. Several demonstrate the effectiveness of the proposed method.     

Interactive mesh deformation using equality-constrained least squares

Mesh deformation techniques that preserve the differential properties have been intensively studied. In this paper, we propose an equality-constrained least squares approach for stably deforming mesh models while approximately preserving mean curvature normals and strictly satisfying other constraints such as positional constraints. We solve the combination of hard and soft constraints by constructing a typical least squares system using QR decomposition. A well-known problem of hard constraints is over-constraints. We show that the equality-constrained least squares approach is useful for resolving such over-constrained situations. In our framework, the rotations of mean curvature normals are treated using the logarithms of unit quaternions in . During deformation, mean curvature normals can be rotated while preserving their magnitudes. In addition, we introduce a new modeling constraints called rigidity constraints and show that rigidity constraints can effectively preserve the shapes of feature regions during deformation. Our framework achieves good performance for interactive deformation of mesh models.     

Non-uniform deformation of an STL model satisfying error criteria

In this research, a method is presented for generating a deformed model satisfying given error criteria from an STL model in a triangular-mesh representation suitable for rapid prototyping (RP) processes. A deformed model is a non-uniformly modified shape from a base STL model. In developing a family product with various sizes such as a shoe, sometimes prototypes for all sizes should be made using an RP machine. Although an STL model is generated from a solid model, it is well known that creating a non-uniformly modified solid model from a base solid model is very difficult. Generally there are some gaps between surfaces after modification, and stitching the gaps is very difficult. To solve this problem, the authors explored the possibility of generating a deformed STL model directly from a base STL model. This research includes a data structure for modifying the STL model, checking the error of a modified edge compared with the exact non-uniformly scaled curve, checking the error of a modified facet compared with the exact non-uniformly scaled surface, and splitting a facet with an error greater than the allowable tolerance. Using the results of this research, the difficult work of creating solid models to build non-uniformly deformed STL models could be avoided.     

Inverse adaptation of a Hex-dominant mesh for large deformation finite element analysis

In the finite element analysis of metal forming processes, many mesh elements are usually deformed severely in the later stage of the analysis because of the corresponding large deformation of the geometry. Such highly distorted elements are undesirable in finite element analysis because they introduce error into the analysis results, and, in the worst case, inverted elements can cause the analysis to terminate prematurely. This paper proposes a new inverse-adaptation method that reduces or eliminates the number of inverted mesh elements created in the later stage of finite element analysis, thereby lessening the chances of early termination and improving the accuracy of the analysis results. By this method, a simple uniform mesh is created initially, and a pre-analysis is run in order to observe the deformation behavior of the elements. Next, an input hex-dominant mesh is generated in which each element is “inversely adapted”, or pre-deformed in such a way that it has approximately the opposite shape of the final shape that normal analysis would deform it into. Thus, when finite element analysis is performed, the analysis starts with an input mesh of inversely adapted elements whose shapes are not ideal. As the analysis continues, the element shape quality improves to almost ideal, and then, toward the final stage of analysis, degrades again, but much less than would be the case without the inverse adaptation. This method permits the analysis to run to the end, or to a further stage, with no inverted elements. Besides its pre-skewing the element shape, the proposed method is also capable of controlling the element size according to the equivalent plastic strain information collected from the pre-analysis. The proposed inverse adaptation can be repeated iteratively until reaching the final stage of deformation.     

A quantitative assessment of approaches to mesh generation for surgical simulation

In surgical simulation, it is common practice to use tetrahedral meshes as models for anatomy. These meshes are versatile, and can be used with a number of different physically based modelling schemes. A variety of mesh generators are available that can automatically create tetrahedral meshes from segmented anatomical volumes. Each mesh generation scheme offers its own set of unique attributes. However, few are readily available. When choosing a mesh generator for simulation, it is critical for it to output good-quality, patient-specific meshes that provide a good approximation of the shape or volume to be modelled. To keep computation time within the bounds required for real-time interaction, there is also a limit imposed on the number of elements in the mesh generated. To the authors knowledge, there has been little work directly assessing the suitability of mesh generators for surgical simulation. This paper seeks to address this issue by assessing the use of six mesh generators in a surgical simulation scenario, and examining how they affect simulation precision. This paper aims to perform these comparisons against high-resolution reference meshes, where we examine the precision of meshes from the same mesh generator at different levels of complexity.

3D sketching for aesthetic design using fully free-form deformation features

This paper addresses the designers’ activity and in particular the way designers express an object shape in 2D sketches through character lines and how these lines form a basis for sketching shapes in 3D. The tools currently available in commercial CAS/CAD systems to manipulate the digital models are still not sufficiently suited to support design. In this paper, the so-called fully free-form deformation features (δ-F⁴) are introduced as a modelling method to take into account the curve-oriented stylists’ way of working. Both the advantages of a free-form surface deformation method and a feature-based approach are merged to define these high-level modelling entities allowing for a direct manipulation of surfaces through a limited number of intuitive parameters. Such features incorporate several characteristics designed to handle the uncertainties and/or inconsistencies of the designer's input during a sketching activity. In addition, a δ-F⁴ classification is proposed to enable a fast access to the desired shape according to its semantics and characteristics.     

适用于SBS网格变形的权重分配方法

提出一种适用于球面混合蒙皮（SBS）网格变形的权重分配算法,使用顶点在骨骼上的投影作为初始权重求解热平衡方程,将每一条骨骼控制的顶点进行聚类,对位于类边界上顶点相对于这条骨骼的权重衰减,对每个骨骼类的非边界顶点的权重基于邻域进行插值。该算法能够抑制肢体交接处权重过度分配的问题,并且使权重符合网格拓扑结构以及过渡平缓。实验结果表明,该算法计算的权重可以使SBS变形达到自然、平滑的效果。     

Preserving form features in interactive mesh deformation

Interactive mesh deformation that preserves differential properties is a promising technique for the design of mechanical parts such as automobile sheet-metal panels. However, existing methods lack the ability to manipulate the form features and hard constraints that are commonly used in engineering applications. In this paper, we propose a new deformation framework that precisely preserves the shapes of form features during deformation. Geometrical shapes are interactively deformed so that mean curvature normals are approximately preserved in a least-squares sense and positional constraints and form-feature constraints are precisely satisfied. In our system, the combination of soft and hard constraints is solved using the Lagrange multiplier method. We also show how to constrain the motion of a form feature on a plane or a straight line using linear constraints. The implemented system achieves a real-time response for constrained deformation.     

Hexahedral mesh generation constraints

For finite element analyses within highly elastic and plastic structural domains, hexahedral meshes have historically offered some benefits over tetrahedral finite element meshes in terms of reduced error, smaller element counts, and improved reliability. However, hexahedral finite element mesh generation continues to be difficult to perform and automate, with hexahedral mesh generation taking several orders of magnitude longer than current tetrahedral mesh generators to complete. Thus, developing a better understanding of the underlying constraints that make hexahedral meshing difficult could result in dramatic reductions in the amount of time necessary to prepare a hexahedral finite element model for analysis. In this paper, we present a survey of constraints associated with hexahedral meshes (i.e., the conditions that must be satisfied to produce a hexahedral mesh). In presenting our formulation of these constraints, we will utilize the dual of a hexahedral mesh. We also discuss how incorporation of these constraints into existing hexahedral mesh generation algorithms could be utilized to extend the class of geometries to which these algorithms apply. We also describe a list of open problems in hexahedral mesh generation and give some context for future efforts in addressing these problems.     

基于细分的网格模型骨架驱动变形技术

针对传统骨架驱动变形方法中模型细节特征不能得到有效保持的问题,提出一种基于细分的骨架驱动网格模型变形方法。首先,对网格模型待变形区域基于截交线进行局部骨架提取和控制网格构建,分别建立骨架与控制网格以及控制网格所对应细分曲面与待变形模型区域之间的关联关系;然后,将基本函数作用下的自由变形方法应用于骨架变形,通过骨架变形驱动控制网格变形,将变形前后控制网格所对应细分曲面的变化信息转为网格模型泊松梯度场的改变;最后,根据改变后梯度场重建网格模型。实例表明,该变形方法针对不同网格模型均可以得到较好的编辑效果,且细节信息在变形后都得到了有效保持。与传统骨架驱动变形方法相比,该方法除具备交互操作简单直观的优势外,同时能够更好保持变形模型几何细节特征,更为适合具有丰富几何细节的复杂模型的变形编辑。     

Consistent mesh partitioning and skeletonisation using the shape diameter function

Mesh partitioning and skeletonisation are fundamental for many computer graphics and animation techniques. Because of the close link between an object’s skeleton and its boundary, these two problems are in many cases complementary. Any partitioning of the object can assist in the creation of a skeleton and any segmentation of the skeleton can infer a partitioning of the object. In this paper, we consider these two problems on a wide variety of meshes, and strive to construct partitioning and skeletons which remain consistent across a family of objects, not a single one. Such families can consist of either a single object in multiple poses and resolutions, or multiple objects which have a general common shape. To achieve consistency, we base our algorithms on a volume-based shape-function called the shape-diameter-function (SDF), which remains largely oblivious to pose changes of the same object and maintains similar values in analogue parts of different objects. The SDF is a scalar function defined on the mesh surface; however, it expresses a measure of the diameter of the object’s volume in the neighborhood of each point on the surface. Using the SDF we are able to process and manipulate families of objects which contain similarities using a simple and consistent algorithm: consistently partitioning and creating skeletons among multiple meshes.     

Parallel adaptive mesh generation and decomposition

An important class of methodologies for the parallel processing of computational models defined on some discrete geometric data structures (i.e. meshes, grids) is the so calledgeometry decomposition or splitting approach. Compared to the sequential processing of such models, the geometry splitting parallel methodology requires an additional computational phase. It consists of the decomposition of the associated geometric data structure into a number of balancedsubdomains that satisfy a number of conditions that ensure the load balancing and minimum communication requirement of the underlying computations on a parallel hardware platform. It is well known that the implementation of the mesh decomposition phase requires the solution of a computationally intensive problem. For this reason several fast heuristics have been proposed. In this paper we explore a decomposition approach which is part of a parallel adaptive finite element mesh procedure. The proposed integrated approach consists of five steps. It starts with a coarse background mesh that isoptimally decomposed by applying well known heuristics. Then, the initial mesh is refined in each subdomain after linking the new boundaries introduced by its decomposition. Finally, the decomposition of the new refined mesh is improved so that it satisfies the objectives and conditions of the mesh decomposition problem. Extensive experimentation indicates the effectiveness and efficiency of the proposed parallel mesh and decomposition approach.     

A comparison of two optimization methods for mesh quality improvement

We compare inexact Newton and block coordinate descent optimization methods for improving the quality of a mesh by repositioning the vertices, where the overall quality is measured by the harmonic mean of the mean-ratio metric. The effects of problem size, element size heterogeneity, and various vertex displacement schemes on the performance of these algorithms are assessed for a series of tetrahedral meshes.

基于局部刚性约束的微分网格变形算法

针对网格角色模型（人体或动物模型）的关节部位在变形中易出现扭曲或不自然体积改变的问题,结合网格刚性变形和微分变形的理论,提出了一种基于局部刚性约束的变形算法。在本算法中,首先采用距离场方法求取模型的骨架关节点,然后在关节点上插入刚性约束架,再用均值坐标将刚性约束架和模型绑定到一起,最后通过求解包含微分约束和局部刚性约束的能量方程得到变形结果。实验表明,本算法很好地解决了大规模角色模型变形过程中,关节部位出现失真的问题。     

Shape optimization of quad mesh elements

We study the problem of optimizing the face elements of a quad mesh surface, that is, re-sampling a given quad mesh to make it possess, as much as possible, face elements of some desired aspect ratio and size. Unlike previous quad mesh optimization/improvement methods based on local operations on a small group of elements, we adopt a global approach that does not introduce extra singularities and therefore preserves the original quad structure of the input mesh. Starting from a collection of quad patches extracted from an input quad mesh, two global operations, i.e. re-sampling and re-distribution, are performed to optimize the number and spacings of grid lines in each patch. Both operations are formulated as simple optimization problems with linear constraints.     

Differential coordinates for local mesh morphing and deformation

Published online: 14 February 2003     

使用定向天线的骨干无线网格网络容量研究

定向天线能够提高无线网格网络（WMN）的空间复用率,因而影响了WMN的容量。虽然目前许多文献已经提出使用定向天线的介质访问控制方案、路由协议和拓扑控制方法去提高MWN的性能,但是在理论上研究配置定向天线的MWN的容量仍然是必要的。用渐进的分析方法对使用定向天线的骨干WMN的容量进行了研究,分析了定向天线对容量的影响,并推导出网格路由器平均吞吐量上限。结果表明在接入点数量达到一定的门限时,定向天线的使用有效地增大了网络的容量。     

基于Kinect与网格几何变形的人脸表情动画

面部表情重建的实时性与重建效果的真实性是人脸表情动画的关键问题,提出一种基于Kinect人脸追踪和几何变形技术的面部表情快速重建新方法。使用微软的Kinect设备识别出表演者面部并记录其特征点数据,并利用捕捉到的特征点建立覆盖人脸的网格模型,从中选取变形使用的控制点数据,由于Kinect可以实时地自动追踪表演者面部,由此实现了利用三种不同变形算法对目标模型实时快速重建。实验结果表明,该方法简单易实施,不用在表演者面部做任何标定,可以自动地将人脸表情动作迁移到目标模型上,实现人脸表情快速重建,并且保证目标模型表情真实自然。     

Adaptive mesh refinement using piecewise-linear shape functions based on the blending function method

Use of quadrilateral elements for finite element mesh refinement can lead either to so-called irregular meshes or the necessity of adjustments between finer and coarser parts of the mesh necessary. In the case of irregular meshes, constraints have to be introduced in order to maintain continuity of the displacements. Introduction of finite elements based on blending function interpolation shape functions using piecewise boundary interpolation avoids these problems. This paper introduces an adaptive refinement procedure for these types of elements. The refinement is anh-method. Error estimation is performed using the Zienkiewicz-Zhu method. The refinement is controlled by a switching function representation. The method is applied to the plane stress problem. Numerical examples are given to show the efficiency of the methodology.     

骨架驱动的三维模型变形方法

为发展三维网格模型的变形技术,研究了多种三维模型变形算法,通过对骨架驱动变形算法的深入研究,针对现行算法多是以单一骨架驱动变形的不足,提出了一种新的基于多骨架点驱动的交互式局部变形方法.有效结合模型的骨架图结构,确定各骨架点对应的局部区域.并将骨架点拟合为二次Bézier曲线,通过交互式拖动任意骨架点计算与之相连的多骨架点的动态变化,实现模型局部区域的自然形变.实验结果表明了该算法的有效性和直观性.