网格的渐进几何压缩

提出一种渐进几何压缩算法.通过对简化算法的改进,网格模型由基网格及多组顶点分裂操作序列表达.当从一层网格向下一层精网格细化时,该组顶点分裂操作序列中的分裂操作顺序是任意的.因此,改进的渐进网格表示可改变每组顶点分裂操作的排序,实现高效率编码.设计了Laplacian几何预测器,通过相邻顶点来预测新增顶点位置,并对位置校正值进行量化及Huffman编码.实验结果表明,该算法可获得高压缩比,适合几何模型的网络渐进传输.     

任意拓扑三角形网格的全局参数化

提出了一种零亏格的任意拓扑流形三角形网格自动全局参数化方法 .算法首先采用顶点对合并的网格简化方法构造一个网格的累进表示 ,在进行网格简化的同时 ,对被删除的顶点相对于顶点合并操作所得到的新顶点的邻域进行局部参数化 ,由此得到一个带局部参数化信息的累进网格 ;然后将网格简化所得到的基网格进行中心投影到一个单位球面上 ,并采用累进恢复的方法将删除的顶点按与删除时相反的顺序逐次添加回网格上来 ,所添加顶点的坐标不再是其删除前的坐标值 ,而是由局部参数化信息计算得到 ,并且保证是位于单位球面上的 .由此得到原始网格的单位球面参数化网格     

基于2维流形的STL曲面网格重建算法

STL（stereo lithography）作为3D扫描数据和快速原型制造事实上的标准,其广泛应用于娱乐、制造业和Internet等领域.但随着3D模型越来越复杂,数据量越来越庞大,从STL文件难以快速获得完整拓扑关系以及其存在大量冗余信息的缺点,制约着STL网格模型的进一步优化处理与应用.为此,需要针对STL网格模型进行网格重建.本文针对2维流形的STL三角形曲面网格模型,提出了一种快速的网格重建方法.主要利用删除在重建过程中达到饱和的顶点,以便减少需要比对的顶点数,并结合STL文件数据的相关性来提高顶点搜索与比较的效率.对于非封闭的曲面网格,本文算法在提高曲面网格重建效率的同时,还能有效地提取曲面网格模型的边界信息.另外,重建的曲面网格数据文件大大地减少了存储空间,有效地去除了冗余数据.实验结果表明本文算法的高效性及鲁棒性.     

基于顶点重要度的保形网格简化方法研究

为解决许多网格简化方法不能很好地保持模型的重要几何特征问题,提出基于顶点重要度和三角剖分的边折叠简化算法.算法通过特征因子加权顶点重要度作为边的折叠代价,定义法向量夹角因子,控制边的折叠顺序;在折叠过程中对边界特征区域进行冻结处理,以保持模型总体轮廓特征;采用边中点折叠和边邻域网格重建方法完成折叠操作.实验结果表明,模型在大规模简化后,该方法能较好地保持模型的几何特征.     

带属性的三角网格模型简化算法研究

在计算机视觉，计算机仿真，网络传输中，经常遇到带有颜色，纹理等属性的三角网格模型的简化问题，文中提出一种带属性的三角网格模型简化的算法，该算法将表征网格顶点信息的向量由简单的三维几何信息扩展到包含颜色，纹理等附加信息的多维向量，在R^n空间中用对称Hausdorff距离控制网络简化顺序和精度，既保证了简化网格模型在几何上与补始网格模型尽可能地相似，又较好地保存了初始网格模型的颜色，纹理等信息。     

基于最小二乘网格的模型变形算法

针对自由变形技术难以保持模型细节的问题,提出一种基于最小二乘网格的模型变形算法.通过顶点位置约束的全局拉普拉斯光顺分解出表示模型低频信号的最小二乘网格,并求出高频信号在该网格上的编码;通过用户交互,基于均值坐标对最小二乘网格进行自由变形;根据最小二乘网格各顶点处局部标架在变形时的几何变换求出变形后的高频编码,通过解码求出变形后的网格模型.实验结果表明,该算法简单、高效且便于用户交互,有效地保持了模型的几何细节.     

基于边收缩的渐进网格模型生成算法

为了实现3D模型的渐进式网格模型表示,改进基于边收缩方式模型简化的收缩代价计算方法。本算法首先从SMF数据文件中读取模型数据信息,然后在内存中快速建立起3D模型,重新设计Garland算法中QEM的权值计算方法。以顶点相邻三角平面法向量最大偏差的平方作为顶点的重要程度并将其加入到误差测度公式中,通过简化最终生成渐进式网格模型。实验结果表明,本算法简练,网格模型生成速度快,模型轮廓信息保持完整。     

三维网格模型的球面分割几何压缩算法

首先对单位球面进行均匀分割,构造出规则球面网格,然后依次对球面网格点进行编号,用半径和球面网格点编号近似表示每个顶点的三维坐标.对这些编号排序后,用相邻编号的差值来表示球面网格点编号,实现了只用一个浮点数和一个网格点编号差值来表示一个顶点的3个坐标值.浮点数表示的半径可以量化为整数,进一步压缩存储空间.该算法的最大优点是与模型的拓扑性质无关,只需要利用模型的顶点坐标.实验结果显示,文中算法有较好的压缩效果,虽然该算法是针对三角面片网格来说明的,但是其基本思想也可以应用到其他形式的网格模型中.     

基于数据相关性的STL曲面网格快速重建算法

通过分析大量STL文件中的三角形单元数据,发现文件中顺序相邻的2个独立的三角形网格单元至少共一个顶点的概率大约是0.84～0.99,共2个顶点的概率大约是0.67～0.75,表明相邻网格单元数据存在强相关性以及大量的冗余信息.利用这种数据相关性,从概率的角度给出了一条检查冗余点的有效途径,进而得到一种快速的STL三角形曲面网格重建算法.新的曲面网格数据文件存储容量为原来的25%左右,有效地去除了冗余数据.实验结果表明了该算法的高效性及鲁棒性.     

基于顶点范数三维网格模型抗简化盲水印算法

为提高三维网格模型的数字水印对网格简化攻击的鲁棒性，提出一种基于顶点范数的三维网格模型抗简化盲水印算法。结合网格模型点与面的权重关系计算模型中心，利用中心计算顶点范数，根据水印长度建立顶点范数分组，在嵌入水印时，通过映射函数调整分组内顶点范数均值嵌入水印信息；在检测水印时，计算各集合内均值进行水印信息的盲检测。实验结果表明，该水印算法具有较好的透明性、鲁棒性以及简化攻击抵抗的能力，为三维网格模型的版权保护提供了有效技术支持。     

Task migration in n-dimensional wormhole-routed mesh multicomputers

In a mesh multicomputer, performing jobs needs to schedule submeshes according to some processor allocation scheme. In order to assign the incoming jobs to a free submesh, a task compaction scheme is needed to generate a larger contiguous free region. The overhead of compaction depends on the efficiency of the task migration scheme. In this paper, two simple task migration schemes are first proposed in n-dimensional mesh multicomputers with supporting dimension-ordered wormhole routing in one-port communication model. Then, a hybrid scheme which combines advantages of the two schemes is discussed. Finally, we evaluate the performance of all of these proposed approaches.     

Unconditionally stable high-order time integration for moving mesh finite difference solution of linear convection–diffusion equations

This paper is concerned with moving mesh finite difference solution of partial differential equations. It is known that mesh movement introduces an extra convection term and its numerical treatment has a significant impact on the stability of numerical schemes. Moreover, many implicit second and higher order schemes, such as the Crank–Nicolson scheme, will lose their unconditional stability. A strategy is presented for developing temporally high-order, unconditionally stable finite difference schemes for solving linear convection–diffusion equations using moving meshes. Numerical results are given to demonstrate the theoretical findings.     

Finite difference solutions of the Navier-Stokes equations on staggered and non-staggered grids

Finite difference schemes for the Navier-Stokes equations are considered, with particular attention to the discretization of the pressure gradient and divergence terms. It is demonstrated that the relation between these terms is the principal reason for the use of the conventional staggered mesh with SIMPLE and other schemes. The important factors in the differencing are that it should lead to an elliptic scheme that satisfies the integrability constraint. The SIMPLE scheme automatically satisfies these two constraints.A non-staggered mesh scheme that also satisfies these constraints has been developed. Comparisons between it and a SIMPLE scheme for natural convection in a cavity indicate that the schemes have equivalent accuracy. For the non-uniform mesh used in this problem the non-staggered scheme is more efficient. It is expected that this increase in efficiency would be greater for adaptive and multi-grid algorithms.     

Second-order-accurate explicit fluctuation splitting schemes for unsteady problems

This paper is concerned with the issue of obtaining explicit fluctuation splitting schemes which achieve second-order accuracy in both space and time on an arbitrary unstructured triangular mesh. A theoretical analysis demonstrates that, for a linear reconstruction of the solution, mass lumping does not diminish the accuracy of the scheme provided that a Galerkin space discretization is employed. Thus, two explicit fluctuation splitting schemes are devised which are second-order accurate in both space and time, namely, the well known Lax-Wendroff scheme and a Lax-Wendroff-type scheme using a three-point-backward discretization of the time derivative. A thorough mesh-refinement study verifies the theoretical order of accuracy of the two schemes on meshes with increasing levels of nonuniformity.     

A Robust Reconstruction for Unstructured WENO Schemes

The weighted essentially non-oscillatory (WENO) schemes are a popular class of high order numerical methods for hyperbolic partial differential equations (PDEs). While WENO schemes on structured meshes are quite mature, the development of finite volume WENO schemes on unstructured meshes is more difficult. A major difficulty is how to design a robust WENO reconstruction procedure to deal with distorted local mesh geometries or degenerate cases when the mesh quality varies for complex domain geometry. In this paper, we combine two different WENO reconstruction approaches to achieve a robust unstructured finite volume WENO reconstruction on complex mesh geometries. Numerical examples including both scalar and system cases are given to demonstrate stability and accuracy of the scheme.     

Transitive mesh space of a progressive mesh

The paper investigates the set of all selectively refined meshes that can be obtained from a progressive mesh. We call the set the transitive mesh space of a progressive mesh and present a theoretical analysis of the space. We define selective edge collapse and vertex split transformations, which we use to traverse all selectively refined meshes in the transitive mesh space. We propose a complete selective refinement scheme for a progressive mesh based on the transformations and compare the scheme with previous selective refinement schemes in both theoretical and experimental ways. In our comparison, we show that the complete scheme always generates selectively refined meshes with smaller numbers of vertices and faces than previous schemes for a given refinement criterion. The concept of dual pieces of the vertices in the vertex hierarchy plays a central role in the analysis of the transitive mesh space and the design of selective edge collapse and vertex split transformations.     

Structured mesh generation by kriging with local refinement with a new elliptic scheme

Accurate results in finite element analysis are strongly related to mesh quality. In this paper, an automatic quadrilateral mesh generation methodology using kriging interpolation is described, a quality mesh study is conducted, and the development of a new local refinement scheme, called the elliptic scheme, is presented. The new elliptic refinement scheme is evaluated using four standard structural cases, and it is shown that it compares very well with octree-based refinement schemes and other local refinement methods.     

Efficient mesh optimization schemes based on Optimal Delaunay Triangulations

In this paper, several mesh optimization schemes based on Optimal Delaunay Triangulations are developed. High-quality meshes are obtained by minimizing the interpolation error in the weighted L¹ norm. Our schemes are divided into classes of local and global schemes. For local schemes, several old and new schemes, known as mesh smoothing, are derived from our approach. For global schemes, a graph Laplacian is used in a modified Newton iteration to speed up the local approach. Our work provides a mathematical foundation for a number of mesh smoothing schemes often used in practice, and leads to a new global mesh optimization scheme. Numerical experiments indicate that our methods can produce well-shaped triangulations in a robust and efficient way.     

Bilateral normal filtering for mesh denoising

Decoupling local geometric features from the spatial location of a mesh is crucial for feature-preserving mesh denoising. This paper focuses on first order features, i.e., facet normals, and presents a simple yet effective anisotropic mesh denoising framework via normal field denoising. Unlike previous denoising methods based on normal filtering, which process normals defined on the Gauss sphere, our method considers normals as a surface signal defined over the original mesh. This allows the design of a novel bilateral normal filter that depends on both spatial distance and signal distance. Our bilateral filter is a more natural extension of the elegant bilateral filter for image denoising than those used in previous bilateral mesh denoising methods. Besides applying this bilateral normal filter in a local, iterative scheme, as common in most of previous works, we present for the first time a global, noniterative scheme for an isotropic denoising. We show that the former scheme is faster and more effective for denoising extremely noisy meshes while the latter scheme is more robust to irregular surface sampling. We demonstrate that both our feature-preserving schemes generally produce visually and numerically better denoising results than previous methods, especially at challenging regions with sharp features or irregular sampling.     

Task migration in all-port wormhole-routed 2D mesh multicomputers

In a mesh multicomputer, submeshes are allocated to perform jobs according to processor allocation schemes, with each task assigned to occupy processors of one submesh with an appropriate size. To assign regions for incoming tasks, task compaction is needed to produce a large contiguous free region. The overhead of task compaction relies mainly on designing an efficient task migration scheme. This paper investigates task migration schemes in 2D wormhole-routed mesh multicomputers with an all-port communication model. Two constraints are given between two submeshes for task migration. Two task migration schemes that follow one of the constraints in 2D mesh multicomputers are then developed. In addition, the proposed schemes are proven to be deadlock-free and congestion-free. Finally, performance analysis is adopted to compare the proposed task migration schemes.