保内部相似性的平面形状混合算法

为了在计算机动画中可以得到较好的图形过渡效果,提出了一保持平面多边形内部相似性的形状混合算法,从而有效地避免了中间多边形发生局部萎缩或者膨胀的现象.此方法从源和目标多边形的同构三角剖分出发,对同构三角网格每一个夹角处表示边角关系的几何量线性插值得到相对应的中间几何量,通过这些中间几何量以及它们与顶点坐标之间的关系来建立线性方程组,给定初始条件后用现成的程序库快速求解来得到中间三角网格(其边界即为中间多边形).还通过引入特征多边形来保持混合多边形的全局视觉特征.该算法计算量小、运行效率高,对形状复杂的多边形仍然可以得到满意的结果,适合于实际应用中实时的要求.     

利用几何求交实现三角网格模型快速体素化

为解决现有的三角网格模型体素化算法存在的体素寻找不全或者体素化效率不高的问题,提出一种快速的三角网格模型体素化算法.该算法分为表面体素化和内部体素化2个步骤:表面体素化使用几何求交方法快速寻找三角形与全部体素的相交多边形顶点,并将这些顶点和与三角形相交的体素一一对应,得到每一个三角形的相交体素,从而得到与三角网表面相交的全部体素;内部体素化使用同时填充内部和外部体素的扫描线种子填充算法,填充过程中使用变长队列,在保持算法的正确性和效率的同时大幅减小算法的空间复杂度.使用三角形数量较多的模型进行高分辨率体素化的实验结果表明,文中算法耗时短,在三角形数量较多时体素化效率显著提高.     

三角网格模型的补洞算法研究

提出了一种三角网格模型的空间孔洞修补算法.首先根据网格中的点、边和三角形之间的关系提取孔洞边界,然后根据孔洞区域的夹角的顺序在空间中依次填补三角形直至修补完全,接着对新增加的高度弯曲的三角形进行细分,最后对修补后的孔洞网格进行几何形态调整,光顺化整个孔洞曲面.实验结果证明,该算法简单、有效,孔洞修补效果好.     

基于流线的重新网格化及多分辨率表示

提出基于场的重新三角网格化和多分辨率表示生成算法.首先,在原三角网格模型上建立拉普拉斯标量场,据此生成两组夹角为60(的流线.然后,从这两组流线构造以菱形面为主的网格并三角化得到三角基网格.最后,在基网格的基础上,再次使用流线技术对原始数据进行向上重采样,得到模型的多分辨率表示.一般地,基网格的三角形接近等边三角形,实验也表明该方法能够得到较高质量的结果.     

鲁棒的多层次平面参数化

为了提高平面参数化的鲁棒性,提出一种基于多层次结构的平面参数化算法,主要包含简化和细分加点2步.对于一个拓扑同胚于圆盘的三角形网格,首先对网格进行简化并存储所简化点的拓扑信息;然后将简化后的网格映射到圆盘上;再根据所存储的拓扑信息分批次加点直至恢复出三角网格的全部顶点,并在此过程中不断地优化网格,防止三角形翻转同时使网格顶点均匀分布;最后对恢复出全部顶点的圆盘网格进行优化,得到最终的参数化网格.实验结果表明,与当前的算法相比,该算法的鲁棒性有很大的提升.     

三角网格模型的各向异性孔洞修补算法

提出一种用于三角网格模型的各向异性孔洞修补算法.该算法避免了高代价的孔洞多边形最优三角化求解过程,只需对其进行一般三角化;而后通过很少次数的迭代过程对孔洞三角化后的网格进行细化和几何形态的调整,使其和周边网格自然过渡.实验结果证明,该算法高效、稳定,能够处理各种类型的孔洞.     

一种基于带噪声的三角网格模型的光顺算法

为了去除三角网格模型中的噪声,提出了一种基于均值漂移的特征保持的网格光顺算法。该方法在对模型中的三角形的法向量进行滤波的基础上鲁棒地计算了顶点的法向量,利用均值漂移方法自适应地聚类出顶点的邻域。结合顶点间几何特征的相似性,将改进后的双边滤波算子应用于顶点的位置更新,从而完成模型的光顺。实验结果证明了网格光顺算法的有效性。利用这种网格算法,可以达到光顺带噪声的三角网格模型的目的,并在光顺的同时,有效地保持了模型中原有的特征。     

基于局部—全局方法的三角网格优化算法

在基于网格形变的图像缩放算法中,表示图像的网格质量对于这类算法的结果有着很大的影响。为了改善图像网格质量,提出一种基于局部—全局方法的平面三角网格优化算法。在局部阶段利用自定义的最相似规则,为网格中的每一个三角形单元求取与之最相似的正三角形,得到一组目标仿射变换函数;全局阶段采用尽可能刚性方法,利用最小二乘法求取一组满足最小变形能量函数的最优解,使得最终生成的网格由尽可能相似于正三角形的三角形构成。同时,在优化过程中加入约束控制,保护网格中的重要区域不发生改变。实验结果表明,优化后的网格质量得到了明显的改善,有助于图像缩放算法后续工作的进行。     

利用贪心算法进行三角剖分的指纹匹配方法

针对指纹识别过程中的指纹匹配算法的准确性以及识别效果等问题,结合计算几何中平面点集的三角剖分方法-贪心算法的特点,将其引入指纹匹配处理,提出了一种基于三角网格(用贪心算法进行平面点集的三角剖分)的指纹匹配方法。该方法通过对细节点的拓扑结构进行三角划分,把空间上位置相近的细节点按照一定的规则相连,得到三角形网格,并基于该网格寻找若干参考点对,最后通过将两幅指纹图像进行姿势调整构成待识别指纹图像,使用获得的参考点对实现基于点模式的指纹匹配。经分析该方法是一种行之有效的指纹匹配方法,确保了指纹旋转、指纹平移参数计算结果的准确性,有效地提高了最终的识别效果。     

基于近平面合并的三角网格简化算法

提出一种基于近平面合并的三角网格简化算法,针对三维重建MarchingCubes算法中产生的大量三角片进行简化。首先依据近平面判断条件将近似共面的三角形合并成一个大的多边形,然后按相应的准则将其重新进行三角化得到更少的三角形面片,以达到简化的目的。该算法在最大化的保留图像细节的前提下,精简了三角片的数目,提高了重建后图像绘制和传输的速率,节省了存储空间和处理时间。     

三角网格曲面的球面参数化

提出了一种球面参数化三角网格曲面的方法。结合平面凸参数化和球面参数化,计算出封闭网格的切割线边界,网格边界映射到球面的凸区域边界上。然后分别参数化各子网格,最后将三角网格内部点映射到球面上。并用实例验证了此方法的可行性和有效性。     

凸组合球面参数化

针对具有单边界的三角网格或与球面同胚的零亏格封闭网格，提出一种基于球面向量线性凸组合的三维网格球面参数化方法．把参数域从平面凸区域扩展到球面凸区域，并把具有凸性的重心坐标纳入到参数化框架中，使得参数化具有保形性质且变形小，同时证明了该参数化方法的存在性和惟一性．整个算法简单可靠．     

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.     

均匀准保角球面参数化

针对闭的或者单边界亏格为0的三角网格,提出一种球面参数化方法．通过立体投影将现有的平面参数化方法推广到球面上,得到一个初始的球面参数化;为了减小变形,引入质心坐标进行全局优化;最后用Moebius变换均匀化最终的球面网格．该方法能够避免立体投影出现三角形折叠的情况,保证最后的映射是双射．通过大量典型的三维模型实验和比较可以看出：文中的参数化方法变形小,在复杂网格的纹理映射中的均匀化效果较现有的保角、保面积变换有明显的改善．     

On Triangulating Planar Graphs under the Four-Connectivity Constraint

Triangulation of planar graphs under constraints is a fundamental problem in the representation of objects. Related keywords are graph augmentation from the field of graph algorithms and mesh generation from the field of computational geometry. We consider the triangulation problem for planar graphs under the constraint to satisfy 4-connectivity. A 4-connected planar graph has no separating triangles, i.e., cycles of length 3 which are not a face. We show that triangulating embedded planar graphs without introducing new separating triangles can be solved in linear time and space. If the initial graph had no separating triangle, the resulting triangulation is 4-connected. If the planar graph is not embedded, then deciding whether there exists an embedding with at most k separating triangles is NP-complete. For biconnected graphs a linear-time approximation which produces an embedding with at most twice the optimal number is presented. With this algorithm we can check in linear time whether a biconnected planar graph can be made 4-connected while maintaining planarity. Several related remarks and results are included. Received August 1, 1995; revised July 8, 1996, and August 23, 1996.     

Mesh Topological Optimization for Improving Piecewise-Linear Image Registration

This paper presents a mutual-information based optimization algorithm for improving piecewise-linear (PWL) image registration. PWL-registration techniques, which are well-suited for registering images of the same scene with relative local distortions, divide the images in conjugate triangular patches that are individually mapped through affine transformations. For this process to be accurate, each pair of corresponding image triangles must be the projections of a planar surface in space; otherwise, the registration incurs in errors that appear in the resultant registered image as local distortions (distorted shapes, broken lines, etc.). Given an initial triangular mesh onto the images, we propose an optimization algorithm that, by swapping edges, modifies the mesh topology looking for an improvement in the registration. For detecting the edges to be swapped we employ a cost function based on the mutual information (MI), a metric for registration consistency more robust to image radiometric differences than other well-known metrics such as normalized cross correlation (NCC). The proposed method has been successfully tested with different sets of test images, both synthetic and real, acquired from different angles and lighting conditions.     

A two-dimensional paving mesh generator for triangles with controllable aspect ratio and quadrilaterals with high quality

Certain classes of problems result in solution fields of which the characteristic length scales vary with the orientation. Often the orientation of these length scales is related to the orientation of the boundaries. Such solution fields can be captured by the finite element method, using a mesh that is refined in the direction of the short length scales and coarse in the other directions. These meshes contain elements with high aspect ratios in a predefined pattern.The mesh generator presented here can render triangles with high aspect ratios through a paving algorithm. The paving algorithm that is employed applies both triangles and quadrilaterals, combining the advantages of both to render a qualitatively good, oriented triangular mesh, with a concentration of elements in the direction where the internal length scales of the solution field are the shortest.The mesh generator produces triangles with one (almost) orthogonal corner. When low aspect ratio triangles are generated, these are well suited for conversion to quadrilateral elements. Test results indicate that quadrilateral meshes converted from the mesh generator introduced here have a considerably better quality than those converted from several other triangular mesh generators.     

Grinding of a triangular mesh in the problem of biharmonic optimization of complex surfaces

In this paper, the method of grinding a triangular mesh for the biharmonic optimization of surfaces is proposed. The method provides an approximate equality of the lengths of the edges of the mesh. The splitting of triangles relies on the properties of an inscribed circle. Issues of the triangles’ quality and the fulfillment of the Delaunay condition are considered.     

用户控制的纹理合成

提出一种基于用户控制的纹理合成算法．该算法适用于任意二维平面和任意拓扑的三维网格．可方便地控制纹理合成时方向和尺度的连续变化．对于任意平面区域需剖分成较均匀的三角网格，以剖分得到的二角形作为基本的合成单元来进行合成．根据用户在此三角网格上指定表示纹理方向和大小的矢量来插值生成矢量场，用以控制合成纹理的变化．该算法可以自然扩展到三维三角网格，以三角面片作为合成单元，合成后直接输出每个顶点的纹理坐标．该算法对二维和三维纹理合成给出了统一实现的框架．实验结果表明，该算法可以在任意目标区域根据用户的交互生成令人满意的纹理合成效果．     

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

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