优化变形能的平面多边形同构剖分

平面多边形间的同构三角剖分是平面形状渐进过渡与插值的基础,降低对应三角形的变形程度是获得高质量应用的关键.文中提出一种基于变形能优化的2个平面多边形的同构剖分算法,其中包含同构剖分生成和变形能最小化2个模块.首先根据用户指定的对应特征点对多边形进行顶点重采样,得到顶点一一对应的2个多边形;然后利用带约束的Delaunay剖分对其中的一个多边形进行三角化,得到源网格;再用重心坐标将源网格的内部顶点嵌入到另一个多边形得到同构剖分(目标网格);最后逐一检查三角形的变形能,对源网格中变形能超过阈值的三角形进行细分,用同构剖分模块生成新的目标网格.实验及数据统计分析表明,该算法可以得到较好的同构三角剖分,提升网格质量,并能很好地避免纹理细节失真.     

基于形状特征的可避免自交的平面多边形变形

给出了平面简单多边形的一种基于形状特征的可避免自交的变形方法。该方法将初始和目标多边形分别嵌入到以其放大的凸包边界为边界的同构平面三角网格中,通过采用对所嵌入的同构网格进行变形的方法,实现了平面多边形的变形。与已有的Surazhsky和Gotsman的方法相比,该方法考虑了初始和目标多边形的几何轮廓及其差异性,故变形过程更加自然,而且在网格剖分时使用了更少的额外顶点,因而提高了算法速度。     

改进的基于mean value重心坐标的多边形变形

对平面多边形的变形,为了避免变形过程中边界的退化和自交现象,目前主要采用将初始多边形与目标多边形分别嵌入到具有凸边界的同构三角网格中去,转化成三角网格的变形问题。但该方法在进行同构三角剖分时,增加的额外点数目较多,复杂度高,且不能实现刚性变形。论文提出一种基于多边形星形分解的同构三角网格剖分算法,使用较少的额外点,降低了算法复杂度。此外,文中选择正多边形作为三角网格的边界,并采用刚体变形技术以保持初始多边形和目标多边形尽可能刚性地变形,取得了较好的变形效果。     

可控制形状的多边形变形算法

提出了一种可控制形状的多边形变形算法。该方法在源和目标多边形上指定对应的特征点,通过特征点的位置变化来带动整个多边形变化。得到的中间多边形在特征点约束下保持原内在量相对关系的最小变化,有效去除了多余的形变。通过试验表明,该算法产生的变形序列能很好地避免萎缩、自交等不自然现象,取得了良好的变形效果。     

多分辨率三维建筑群建模与实时绘制技术

将纹理特征分析技术引入到多边形网格建模中,提出一种基于高程特征值进行曲面细分的算法以构建多分辨率虚拟建筑群模型。该算法给出一种三角边与纹理特征曲线相交的三角面分裂方法构造自适应细分三角网格。通过设计细分三角网格的二叉树数据结构和开发测试程序进行测试,表明该算法具有自适应网格速度快和保持几何特征较好的特点,可以满足在PC机上实现三维建筑群的大范围建模和实时交互显示要求。     

基于局部单射的平面形状插值形变

在只给出用简单多边形表示的两输入形状的情况下,实现一种简单易用、自然高效的形状插值方法.首先利用基于形状感知的特征匹配算法生成源形状和目标形状之间的匹配;之后在源形状上构造三角剖分,并通过求解映射到目标形状上的尽量刚体的局部单射得到同构三角剖分;最后利用扭曲有界的插值方法得到中间序列.实验结果表明,该方法构造的形变结果能较好地体现源形状和目标形状的特征对应信息,形变过程自然,扭曲较小.     

一种基于小波的多边形变形算法

文章提出了一种基于小波分解算法和相应的重构算法的变形方法。先用小波分解算法作用于平面多边形,得到平面多边形的轮廓和细节。然后分别对多边形的轮廓和细节进行变形,得到从初始图形变换到目标图形的中间图形的轮廓和细节。最后用重构算法重构出中间图形。该文算法可以处理任意顶点数的多边形,减少同构三角剖分的计算量,并且能够得到很好的变形结果。     

基于特征分解的2-D多边形渐变

二维多边形渐变在二维角色动画、模式匹配、几何造型等领域有着重要的应用.已有的方法大多根据多边形的边长、角度、面积、骨架等几何属性来完成多边形之间的最佳对应和渐变,而忽略了多边形的内在视觉特征.提出了一种基于视觉特征对应的2-D多边形渐变方法,该方法把源多边形和目标多边形按照视觉特征进行同构特征分解,得到若干对对应的特征子多边形.在渐变过程中,每个源特征子多边形光滑地过渡到目标特征子多边形.通过引入特征分解点,用户可以灵活和直观地改变特征子多边形,按照预想的效果控制多边形的渐变.实验效果表明,基于特征分解的顶点对应和插值算法不仅可以得到光滑的多边形渐变序列,而且可以实现多边形的特征对应和特征保留.     

基于四面体控制网格的模型变形算法

提出一种鲁棒的保体积保表面细节的模型变形算法.首先将输入模型嵌入到一个稀疏的四面体控制网格中,并且通过一种改进的重心坐标来建立两者的对应关系;然后通过用户的交互,对控制网格建立一个二次非线性能量函数对其进行变形,而输入模型的变形结果则可以通过插值来直接获得.由于能量函数的优化是在控制网格上进行的,从而大大提高了算法的效率.与此同时,提出一种新的能量--Laplacian能量,可以使四面体控制网格进行尽量刚性的变形,从而有效地防止了大尺度编辑过程中模型形状的退化现象.文中算法还具有通用性,可支持多种模型的表示方式,如三角网格模型、点模型等.实验结果表明,该算法可以有效地保持输入模型的几何细节、防止明显的体积变化,得到了令人满意的结果.     

计算机二维动画中一种快速动画变形方法的研究*

提出了一种针对于同构三角网格图形的快速插值方法。在三角网格中,每个三角形均用三角形的质心和三个顶点连线表示的向量来代替这个三角形,在插值每个三角形时均对这三个向量进行插值;然后将所有插值产生的三角形按照预先定义好的规则组合成中间的插值图形。该算法简单、计算速度快,能够达到实时的要求。实验结果表明,该算法能够得到令人满意的变形效果,可以避免中间图形的扭曲和变形,适用于计算机动画、几何造型、CAD等领域。     

同构平面三角网格的保凸变形方法

对于具有不同凸边界的同构平面三角网格的变形,提出了一种简单、有效的方法．该方法结合了两种已有的算法．能够保证网格边界在变形过程中始终保持凸性,且任意时刻的中间网格与初末网格同构,即不产生自交现象;同时文中方法实现了两个凸多边形的保凸变形。     

可控制的同构平面三角网格的保凸变形

对于具有不同凸边界的同构平面三角网格的变形,提出了一种简单易行且允许人工参与的算法。算法在保证网格边界在变形过程中始终保持凸性,且中间网格与初末网格同构的基础上,提供了可调参数,从而在一定程度上实现了用户对变形过程的人为控制。     

平面散乱点集约束Delaunay三角形剖分切割算法

文章提出了一种基于切割的平面散乱点集约束Delaunay三角剖分算法。该算法的基本思路是首先对平面散乱点集作约束最大空圆凸多边形剖分,然后对多边形的内部再作约束Delaunay三角形剖分。文章还证明了平面散乱点集的约束最大空圆凸多边形剖分是唯一的以及约束Delaunay三角剖分的不唯一性仅仅体现在约束最大空圆凸多边形的内部。使用约束最大空圆凸多边形的概念消除了由于“退化”现象（三个以上的点共圆）带来的算法上的潜在错误。     

Recognizing polygons,or how to spy

A new class of so-called pseudo-starshaped polygons is introduced. A polygon is pseudo-star-shaped if there exists a point from which the whole interior of the polygon can be seen, provided it is possible to see through single edges. We show that the class of pseudo-star-shaped polygons unifies and generalizes the well-known classes of convex, monotone and pseudostar-sphaped polygons. We give algorithms for testing whether a polygon is pseudostar-shaped from a given point in linear time, and for constructing all regions from which the polygon is pseudo-star-shaped in quadratic time. We show the latter algorithm to be worst-case optimal. Also, we give efficient algorithms solving standard geometrical problems such as point-location and triangulation for pseudo-starshaped polygons.A preliminary version of this paper has been presented at the 24 th Allerton Conference on Communication, Control and Computing, Monticello, Ill, October 1986Research for this paper was done while the author was at Carleton UniversityResearch for this paper was done in part while the author was visiting Carleton UniversityThis research was supported in part by NSERC and by Carleton University     

Convolution surfaces based on polygons for infinite and compact support kernels

We provide formulae to create 3D smooth shapes fleshing out a skeleton made of line segments and planar polygons. The boundary of the shape is a level set of the convolution function obtained by integration along the skeleton. The convolution function for a complex skeleton is thus the sum of the convolution functions for the basic elements of the skeleton. Providing formulae for the convolution of a polygon is the main contribution of the present paper. We improve on previous results in several ways. First we do not require the prior triangulation of the polygon. Then, we obtain formulae for families of kernels, either with infinite or compact supports. Last, but not least, in the case of compact support kernels, the geometric computations needed are restricted to intersections of spheres with line segments.     

基于三角形分解和重构的平面多边形变形方法

为解决较复杂的不同拓扑结构的二维形状渐变问题,提出一种基于三角形分解和重构的平面多边形变形方法.该方法将图形多层分解为三角形,保留分解过程中的各层边角信息;然后通过线性插值各层边长比例及角度,并结合刚性变换方法重构中间多边形的细节和框架,以达到变形的目的.该方法适用于任意点数的多边形,具有一般性.实验结果表明,文中方法能很好地解决变形序列中的萎缩问题,并且对较复杂的狭长图形也能避免自交现象,变形效果自然.     

High quality compatible triangulations

Compatible meshes are isomorphic meshings of the interiors of two polygons having a correspondence between their vertices. Compatible meshing may be used for constructing sweeps, suitable for finite element analysis, between two base polygons. They may also be used for meshing a given sequence of polygons forming a sweep. We present a method to compute compatible triangulations of planar polygons, sometimes requiring extra (Steiner) vertices. Experimental results show that for typical real-life inputs, the number of Steiner vertices introduced is very small. However, having a small number of Steiner vertices, these compatible triangulations are usually not of high quality, i.e. they do not have well-shaped triangles. We show how to increase the quality of these triangulations by adding Steiner vertices in a compatible manner, using remeshing and mesh smoothing techniques. The total scheme results in high-quality compatible meshes with a small number of triangles. These meshes may then be morphed to obtain the intermediate triangulated sections of a sweep, if needed.     

基于多层次特征结构的二维形状渐变

二维形状渐变在二维角色动画、模式匹配、几何造型中有着重要的应用.已有方法大多根据边长、角度、面积等局部几何属性来完成形状之间的最佳对应和渐变,忽略了形状的内在特征结构.为此,提出一种基于多层次特征结构的二维形状渐变方法,首先将源形状和目标形状分解为若干个视觉显著性特征,并通过一种用户启发式的半自动方法建立2个形状的特征对应关系;然后根据形状的特征信息构建源形状和目标形状的多层次特征结构,分别表示形状特征的整体位置和朝向、形状特征的局部朝向和形状特征的局部细节;最后组合不同特征层次上的插值结果,重构出中间形状.在源形状到目标形状的渐变过程中,针对不同层次上的特征信息分别使用近似保刚性插值、边角插值以及弹性线性插值方法进行过渡.实验结果表明,该方法简单高效,有效地避免了形状的内部扭曲,保持了形状的局部特征,可产生自然、光滑且视觉真实的形状渐变序列.