分组渐进迭代逼近算法拟合数据点集

目的 在计算机辅助设计领域里,曲线或曲面的渐进迭代逼近（PIA）性质在插值与拟合问题中有着广泛的应用。如果直接使用PIA方法对所有的数据点集进行拟合,那么在拟合大规模数据点时就缺少一定的灵活性。为了进一步提高渐进迭代逼近方法在拟合大规模点集时的灵活性,提出基于分组的渐进迭代逼近方法。方法 首先对待拟合点集进行分组;其次对分组后的点集采用PIA方法或是基于最小二乘的渐进迭代逼近方法（LSPIA）来得到一组插值或拟合精度不断改善的曲线/曲面;最后运用曲线/曲面拼接算法保证曲线/曲面的连续性,得到1条/张插值或拟合于给定点集的曲线/曲面。结果 给定相同的数据点集,分别采用分组PIA方法,PIA方法和LSPIA方法进行拟合。分组PIA方法与PIA方法相比误差减少的倍数与组数相当;分组PIA方法与LSPIA方法相比误差减少一半。结论 本文将分组思想引入渐进迭代逼近方法之中,提出了基于分组的渐进迭代逼近方法。该分组算法适用于拟合大规模数据点集,在拟合过程中,可以提高渐进迭代逼近方法在拟合大规模点集时的灵活性;经过理论推导证明了曲线/曲面的迭代效率有所提高,且与PIA方法相比误差有较大的改善。     

带平台伸缩函数的参数曲线变形

目的 随着科学技术的快速发展,曲线的几何造型技术开始成为近来的热点研究方向.为了获得更多的变形效果,面向2维、3维参数曲线和自由曲线变形,提出一种带平台伸缩函数的变形方法。方法 有别于现有的大多数自由变形算法,首先构造了一种形式简洁的多项式形式伸缩函数;其次借助于伸缩函数,构造了含有伸缩参数与光滑参数的新型伸缩因子,算法表明,这种新型伸缩因子具有单点峰值性、区间峰值性、对称性等优良性质;最后将伸缩因子所构造变形矩阵作用于待变形的曲线,通过控制变形区间、伸缩参数、光滑参数以及变形方向,可以获得整体的、局部的、周期的、伸缩的等各类丰富的图形效果。结果 此变形操作对造型系统中的主流参数曲线(Bézier和NURBS)具有封闭性;通过大量数值实例表明了该方法计算量小,可控性强,重复使用可以得到形状多样、具有艺术效果的轮廓线等效果。结论 与其他方法相比,本文算法不仅可以用于一般的平面与空间参数曲线,也可以用于自由型曲线,扩大了多数自由变形算法的适用范围;由于伸缩函数具备单点峰值性、区间峰值性、对称性等性质,从而能够产生以前变形方法无法产生各类角点、尖点的特殊曲线,在一定程度上极大丰富了曲线的变形效果。     

关键点选取的最小二乘渐进迭代逼近

目的 最小二乘渐进迭代逼近（LSPIA）方法多以均匀参数化或弦长参数化的形式均匀地确定初始控制点,虽然取得了良好效果,但在处理复杂曲线时,迭代速度相对较慢且误差精度不一定能达到预期设定值。为了进一步提高迭代效率和误差精度,本文提出了基于关键点（局部曲率最大点和极端曲率点）的最小二乘渐进迭代逼近方法。方法 首先计算所有数据点的离散曲率,筛选出局部曲率最大点;接着设定初始的曲率下限,筛选出极端曲率点;然后将关键点与均匀选取的控制点按参数顺序化,并将其作为迭代的初始控制点;最后利用LSPIA方法对数据点进行拟合。结果 对同一组数据点,分别采用LSPIA方法和基于关键点的LSPIA方法,本文方法较好地提高了收敛速度;在相同的控制点数目下,与LSPIA算法相比,本文方法的误差精度较小。结论 本文方法适合于比较复杂的曲线,基于曲率分布的关键点的选取,可以更好地反映曲线的几何信息。数值实例表明,结合关键点筛选策略的LSPIA算法提高了计算效率,取得了更好的拟合效果。     

Bézier曲线降阶的迭代算法

为提高Bézier曲线降阶的稳定性,提出以基于L_2范数的逼近误差为指导的一种迭代算法. 该算法从一条初始Bézier曲线开始逐渐地对其控制顶点进行偏移,得到具有误差最小的逼近曲线; 同时,应用线性搜索方法来优化控制顶点的偏移,使得在每次迭代后逼近误差可以达到局部最小. 实例结果表明了该算法的快速收敛性.     

NURBS曲线拟合的最小二乘渐进迭代逼近优化算法

为了使NURBS曲线更精确地拟合散乱数据点,提出了一种基于最小二乘渐进迭代逼近(least square progressive and iterative approximation,LSPIA)的NURBS曲线拟合优化算法.首先,确定一条初始NURBS曲线,利用LSPIA算法优化控制顶点;然后,分别优化数据点参数,拟合曲线的节点和权因子,每优化好一个变量,重新优化控制顶点;最后,经多次优化迭代得到高精度的NURBS拟合曲线.在优化每类变量时,为了避免被其他变量影响,保持其他变量不变.基于LSPIA的NURBS曲线拟合优化算法充分利用了LSPIA算法的优点,在迭代过程中,可以重复使用前一迭代步骤得到的控制顶点等数据,从而节省了运算时间.算法实例表明,该算法能获得一定保形效果.     

非均匀三次B样条曲线插值的Jacobi-PIA算法

为了求解非均匀三次B样条曲线插值问题,基于解线性方程组的Jacobi迭代方法提出一种渐进迭代插值算法——Jacobi-PIA算法.该算法以待插值点为初始控制多边形得到第0层的三次B样条曲线,递归地求得插值给定点集的三次B样条曲线;在每个迭代过程中,定义待插值点与第k层的三次B样条曲线上对应点的差向量乘以该点对应的B样条系数的倒数为偏移向量,第k层的控制顶点加上对应的偏移向量得到第k+1层的三次B样条曲线的控制顶点.由于Jacobi-PIA算法在更新控制顶点时减少了一个减法运算,因而运算量更少.理论分析表明该算法是收敛的.数值算例结果表明,Jacobi-PIA算法的收敛速度优于经典的渐进迭代插值算法,与最优权因子对应的带权渐进迭代插值算法基本相同.     

基于正则渐进迭代逼近的自适应B 样条曲线拟合

基于渐进迭代逼近(PIA)的数据拟合方法以其简单和灵活的特性获得了广泛的关 注。为了获得高保真度的拟合曲线,提出了一种基于主导点选取和正则渐进迭代逼近(RPIA)的 自适应B 样条曲线拟合算法。首先根据数据点的曲率估计选取初始主导点并生成初始PIA 曲线。 然后,借助于拟合误差和数据点集的曲率分布选取加细的主导点及实现PIA 曲线的更新。得益 于基于曲率分布的主导点选取,使得拟合曲线在复杂区域分布较多的控制顶点,而在平坦区域 则较少。通过正则参数的引入构造了一种RPIA 格式,提升了渐进迭代控制的灵活性。最后, 数值算例表明相比于传统最小二乘曲线拟合该算法在使用较少数量的控制顶点时可实现较高的 拟合精度。     

渐进迭代逼近方法在等距曲线逼近中的应用

渐进迭代逼近(PIA)方法在CAD领域有很好的自适应性和收敛稳定性,在曲线或曲面的逼近和拟合问题上具有很好的应用前景.文中将该方法应用于二维自由曲线的等距曲线(也称offset曲线)的逼近,提出基于PIA的等距曲线逼近算法.首先在等距曲线上采样数据点,采用Floater的方法对数据点进行参数化,并以这些采样点作为初始控制顶点,由这些初始控制顶点产生初始逼近曲线;然后考察相同参数值处采样点和逼近点的误差,并运用PIA方法逐步逼近等距曲线.该算法分别考虑了等距曲线的多项式逼近和有理逼近.数值实例结果表明,综合控制顶点数和算法误差这2项因素,文中算法具备较好的优势.     

基于法矢控制的B样条曲面逼近的PIA方法

提出了一种基于法矢控制的 B 样条曲面逼近的渐进迭代逼近(PIA)算法。一方面该方法将离散数据点的切失、曲率、法矢等几何特征充分应用到离散数据点的逼近问题上,利用数据点两个方向的切矢构造出数据点的法矢约束来控制逼近曲面形状,相比于无法矢控制的 B 样条曲面逼近的渐进迭代逼近(PIA)方法,逼近曲面更光顺,可获得更好的逼近效果。另一方面由于该算法选取主特征点作为控制顶点,所以允许在曲面拟合中控制顶点的数目小于数据点的数目。而且PIA算法的每次迭代过程中的各个步骤都是独立的,很容易被应用到并行计算上,可提高计算效率。本文还给出了一些实例来验证该算法的有效性。     

细分曲面拟合的局部渐进插值方法

逼近型细分方法生成的细分曲面其品质要优于插值型细分方法生成的细分曲面.然而,逼近型细分方法生成的细分曲面不能插值于初始控制网格顶点.为使逼近型细分曲面具有插值能力,一般通过求解全局线性方程组,使其插值于网格顶点.当网格顶点较多时,求解线性方程组的计算量很大,因此,难以处理稠密网格.与此不同,在不直接求解线性方程组的情况下,渐进插值方法通过迭代调整控制网格顶点,最终达到插值的效果.渐进插值方法可以处理稠密的任意拓扑网格,生成插值于初始网格顶点的光滑细分曲面.并且经证明,逼近型细分曲面渐进插值具有局部性质,也就是迭代调整初始网格的若干控制顶点,且保持剩余顶点不变,最终生成的极限细分曲面仍插值于初始网格中被调整的那些顶点.这种局部渐进插值性质给形状控制带来了更多的灵活性,并且使得自适应拟合成为可能.实验结果验证了局部渐进插值的形状控制以及自适应拟合能力.     

基于渐进迭代逼近的矢量地图曲线化简方法

矢量地图化简在地形仿真、制图综合等研究中具有重要应用。针对已有算法难以兼顾化简曲线 的整体形态和局部特征点精度的问题,提出一种基于 B 样条曲线渐进迭代逼近(PIA)的矢量地图曲线化简方法。 首先筛选出能保持曲线轮廓、具有最大信息量的特征点列,将其作为初始控制点列,得到相应的非均匀 3 次 B 样条拟合曲线;然后根据拟合曲线与特征点的误差进行迭代调整控制点,逐步得到一系列逼近曲线,直至最终 满足精度要求。实验表明,PIA 方法不仅保持了化简曲线的整体几何形态,而且能在满足全局误差要求的情况 下,实现特征点处的高精度逼近。     

三角域上Said-Ball基的推广渐近迭代逼近

目的：如果一组基函数是规范全正（Normalized Totally Positive, abbr. NTP）的,并且对应的配置矩阵是非奇异的,那么由它所生成的参数曲线或张量积曲面具有渐近迭代逼近（progressive iteration approximation, abbr. PIA）性质。为了进一步推广渐近迭代逼近性质的适用范围,本文提出对于一组基函数,如果其对应的配置矩阵不是全正的,那么该基函数也可能具有渐近迭代逼近性质。方法：提出的定理是以基函数具有渐近迭代逼近性质时其对应的配置矩阵所需满足的条件作为理论基础,建立了配置矩阵为严格对角占优或者广义严格对角占优矩阵与基函数具有渐近迭代逼近性质之间的联系。结果：配置矩阵为严格对角占优或者广义严格对角占优矩阵,则相应的三角曲面具有PIA性质或带权PIA性质,即广义PIA性质。数值试验验证了上述理论,并细致地分析了三角域上的低次Said-Ball基,指出了它们具有相应的广义PIA性质。结论：本文将渐近迭代逼近的适用范围推广到三角域上的一般混合基函数。类似三角域上Said-Ball基,本文算法亦可用于研究三角域上的其他各类广义Ball基的PIA性质。     

Bézier曲线的同次扩展及其参数选择

目的 本文旨在构造一种含形状参数的Bézier曲线,要求该曲线定义在代数多项式空间上,其基函数的次数与相同数量控制顶点所需Bernstein基函数的次数相同,对基函数以及相应曲线的计算要尽可能简单,并且要给出常见设计要求下曲线中形状参数的选取方案。方法 以三次Bézier曲线为初始研究对象,依据由可调控制顶点定义可调曲线的思想,在两个内控制顶点中引入参数,与Bernstein基函数作线性组合生成形状可调曲线,再将曲线表达式改写成固定控制顶点与含参数的调配函数的线性组合,从而得出三次Bernstein基函数的含参数扩展基,借助递推公式得出更高次的含参数扩展基,然后观察基函数表达式的规律,给出所有含参数扩展基统一的显示表达式,分析了扩展基的性质,并由之定义含参数的曲线,分析了曲线的性质,给出了曲线的几何作图法以及光滑拼接条件,以曲线拉伸能量、弯曲能量、扭曲能量近似最小为目标,推导了曲线中形状参数的计算公式,再通过曲线图和曲率图对比分析了不同能量目标所得曲线的差异。结果 由于所给含参数的扩展基并未提升Bernstein基函数的次数,且具有统一的显示表达式,因此本文方法在赋予Bézier曲线形状调整能力的同时并未增加计算量,由于提供了可以直接使用的形状参数的计算公式,因此在使用该方法时,符合设计要求的形状参数的确定变得简单,数值实例直观显示了所给曲线造型方法以及曲线中形状参数选取方案的正确性与有效性,体现了本文方法较文献中类似方法的优越之处。结论 所给含参数扩展基的构造方法以及形状参数的选取方法具有一般性,该方法可以推广至构造含形状参数的三角域Bézier曲面。     

对可调控Bézier曲线的改进

目的 在用Bézier曲线表示复杂形状时,相邻曲线的控制顶点间必须满足一定的光滑性条件。一般情况下,对光滑度的要求越高,条件越复杂。通过改进文献中的“可调控Bézier曲线”,以构造具有多种优点的自动光滑分段组合曲线。方法 首先给出了两条位置连续的曲线G^l连续的一个充分条件,进而证明了“可调控Bézier曲线”在普通Bézier曲线的G^l光滑拼接条件下可达G^l(l为曲线中的参数)光滑拼接。然后对“可调控Bézier基”进行改进得到了一组新的基函数,利用该基函数按照Bézier曲线的定义方式构造了一种新曲线。分析了该曲线的光滑拼接条件,并根据该条件定义了一种分段组合曲线。结果 对于新曲线而言,只要前一条曲线的最后一条控制边与后一条曲线的第1条控制边重合,两条曲线便自动光滑连接,并且在连接点处的光滑度可以简单地通过改变参数的值来自由调整。由新曲线按照特殊方式构成的分段组合曲线具有类似于B样条曲线的自动光滑性和局部控制性。不同的是,组合曲线的各条曲线段可以由不同数量的控制顶点定义,选择合适的参数,可以使曲线在各个连接点处达到任何期望的光滑度。另外,改变一个控制顶点,至多只会影响两条曲线段的形状,改变一条曲线段中的参数,只会影响当前曲线段的形状,以及至多两个连接点处的光滑度。结论 本文给出了构造易于拼接的曲线的通用方法,极大简化了曲线的拼接条件。此基础上,提出的一种新的分段组合曲线定义方法,无需对控制顶点附加任何条件,所得曲线自动光滑,且其形状、光滑度可以或整体或局部地进行调整。本文方法具有一般性,为复杂曲线的设计创造了条件。     

An extended iterative format for the progressive-iteration approximation

Progressive-iteration approximation (PIA) is a new data fitting technique developed recently for blending curves and surfaces. Taking the given data points as the initial control points, PIA constructs a series of fitting curves (surfaces) by adjusting the control points iteratively, while the limit curve (surface) interpolates the data points. More importantly, progressive-iteration approximation has the local property, that is, the limit curve (surface) can interpolate a subset of data points by just adjusting a part of corresponding control points, and remaining others unchanged. However, the current PIA format requires that the number of the control points equals that of the data points, thus making the PIA technique inappropriate to fitting large scale data points. To overcome this drawback, in this paper, we develop an extended PIA (EPIA) format, which allows that the number of the control points is less than that of the given data points. Moreover, since the main computations of EPIA are independent, they can be performed in parallel efficiently, with storage requirement O(n), where n is the number of the control points. Therefore, due to its local property and parallel computing capability, the EPIA technique has great potential in large scale data fitting. Specifically, by the EPIA format, we develop an incremental data fitting algorithm in this paper. In addition, some examples are demonstrated in this paper, all implemented by the parallel computing toolbox of Matlab, and run on a PC with a four-core CPU.     

高阶连续的形状可调三角多项式曲线曲面

目的目前使用的B样条曲线曲面存在着高连续阶与高局部调整性两者无法兼而有之的不足,且B样条曲线曲面的形状被控制顶点和节点向量唯一确定,这些因素影响着B样条方法的几何设计效果与方便性。本文旨在克服这种局限,以期构造具有高次B样条方法的高连续阶,低次B样条方法的高局部调整性,以及有理B样条方法权因子决定的形状调整性的曲线曲面。方法在三角函数空间上构造了一组含参数的调配函数,进而定义具有与3次B样条曲线曲面相同结构的新曲线与张量积曲面。结果新曲线曲面继承了B样条方法的凸包性、对称性、几何不变性等诸多性质。不同的是,同样是基于4点分段,3次均匀B样条曲线C2连续,而对于等距节点,在一般情况下,新曲线C5连续,当参数取特殊值时可达C7连续。新曲线在C5连续的情况下存在1个形状参数,能较好地调整曲线的形状同时又无须改变控制顶点。另外,将形状参数设为特定值,新曲线可以自动插值给定点列。新曲面具有与新曲线相应的优点。结论在强局部性下实现高阶连续性的形状可调分段组合曲线曲面,为高阶光滑曲线曲面的设计提供了可能,并且新曲线实现了逼近与插值的统一表示,能较好地应用于工程实际。调配函数的构造方法具有一般性,可用相同方式构造其他具有类似性质的调配函数。     

Free-form deformation of constructive shell models

Free-form deformation (FFD) is known to be a powerful technique for deforming an object independent of its representation. A point on a solid is deformed by specifying the point relative to a coordinate system defined with a lattice of control points. Adjusting the control points of the lattice deforms the object. The deformed object can be visualized by sampling points on the object surfaces, or by approximating the object with a polyhedral model. However, a conversion of the polyhedral model to the underlining solid representation is required if further solid operations (e.g. Boolean operation) is to be applied. This paper presents a technique for applying FFD on constructive shell models (CSR). A CSR object is constructed by subtracting a set of depression (negative) trunctets from the union of a set of outer (positive) trunctets and a polyhedron core. FFD is applied to the polyhedron core and the trunctets of the model. A trunctet is deformed by applying FFD to a set of selected surface points on the trunctet. The deformed trunctet is obtained by interpolating a surface through the deformed surface points. In the deformation of a trunctet, an outer trunctet may become a depression trunctet (or vice versa). By using the concept of mating trunctet, and an approach for classifying the shape of a trunctet, shape changes of a trunctet in a deformation can be determined. Deformation of a trunctet may also result in an invalid trunctet that bulges out of its enclosing tetrahedron. Besides, the degree of the algebraic surface used determines the size of a trunctet relative to the distance between adjacent lattice control points. A subdivision of a trunctet may have to be performed to maintain the validity of a deformation.