二元B样条基函数的金字塔算法研究及应用

发布时间：2018-06-04 15:14

本文选题：基函数 + 金字塔算法　；参考：《华北理工大学》2017年硕士论文

【摘要】：金字塔算法(Pyramid Algorithms)是由美国数学家Ron Goldman首先提出来的,是一种动态编程算法,因其形似金字塔,结构清晰简单,表现算法全局能力强,因此在多项式插值和逼近理论中得到广泛应用。在复杂的自由曲线曲面造型中,不可避免地要对曲线曲面的切向、曲率及包络等变量进行求解运算,而该类问题一般都可转化为基函数和导函数的求解。所以,研究样条基函数快速且通用的构造方法具有重要意义。基于传统样条插值逼近理论,系统地研究了金字塔算法在基函数构建过程中的运用。首先针对Lagrange,Newton及Hermite三类插值基函数,通过线性插值来构建算法金字塔,综合Neville和Aitken算法,分析了路径路标仿射组合系数的性质,得到了节点下标的可交换性,有效减少了计算复杂度。通过数值算例,分析插值曲线拼接处的光滑性,验证了算法的优越性。其次结合开花(Blossom)理论,通过利用对称性及多仿射性将旧的开花值递推得到新的开花值,来推导一元B样条基函数的算法金字塔。基于路径路标的对称平行性质,通过倒转金字塔来减少计算复杂度,得到基函数的向下递推算法。并且对相邻路径进行交叉重叠,实现了拼接节点处光滑性的简单证明。进一步将算法在x,y两个方向上进行双线性插值,得到矩形张量积基函数的金字塔算法,并分析了计算复杂度。针对矩形张量积节点处计算复杂度较高的问题,将节点定义在三角形网格上,利用重心坐标的仿射不变性,推广到局部三角形B样条曲面。通过对基函数构造理论的分析和研究,设计了基于动态编程的一般插值多项式及样条曲线曲面生成的金字塔算法,为复杂曲线曲面和实体造型问题提供了新的思路与方法,特别是对CAGD中需要对几何变量进行编程求解的问题具有重要的应用价值。
[Abstract]:Pyramid algorithm was first put forward by American mathematician Ron Goldman. It is a kind of dynamic programming algorithm. So it is widely used in polynomial interpolation and approximation theory. In the complex modeling of free curve and surface, it is inevitable to solve the tangential, curvature and envelope variables of curve and surface, but this kind of problem can be transformed into the solution of basis function and derivative function. Therefore, it is of great significance to study the fast and general construction method of spline basis function. Based on the traditional spline interpolation approximation theory, the application of pyramid algorithm in the construction of basis functions is systematically studied. Firstly, the algorithm pyramid is constructed by linear interpolation for Lagrange Newton and Hermite interpolation basis functions. The properties of affine combination coefficients of path signs are analyzed by synthesizing Neville and Aitken algorithms, and the commutativity of node subscript is obtained. The computational complexity is reduced effectively. By numerical example, the smoothness of interpolation curve splicing is analyzed, and the superiority of the algorithm is verified. Secondly, based on the Blossom-blooming theory, the new flowering value is obtained by using symmetry and multi-affine to derive the algorithm pyramid of B-spline basis function. Based on the symmetry and parallelism of path signs, the computational complexity is reduced by turning the pyramids upside down, and the downward recursive algorithm of the basis function is obtained. And the adjacent paths are crossed and overlapped, and a simple proof of smoothness of the spliced nodes is realized. The algorithm is further interpolated bilinear in XY direction to obtain the pyramid algorithm of rectangular tensor product basis function, and the computational complexity is analyzed. In order to solve the problem of high computational complexity at rectangular tensor product nodes, the nodes are defined on triangular meshes and generalized to local triangular B-spline surfaces by using affine invariance of barycentric coordinates. Based on the analysis and research of basis function construction theory, a pyramid algorithm for generating general interpolation polynomial and spline curve and surface based on dynamic programming is designed, which provides a new way of thinking and method for complex curve and surface and solid modeling problem. Especially, it has important application value to solve the problem of geometric variables in CAGD.
【学位授予单位】：华北理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O241.3

【参考文献】