论文部分内容阅读
近年来,在CAGD和CAD中,三角Bézier曲面受到越来越广泛关注.它在表示拓扑结构复杂的几何模型时比张量积型Bézier曲面更灵活.因此,它更适合作为复杂几何体的拟合、插值离散数据点的工具.本文我们以三角Bézier曲面为研究对象,针对三角Bézier曲面在求交问题及其有理形式在低阶导矢界的改进两大方面的应用进行了研究. 主要成果如下: 1.提出了implicit Bézier linear clipping(IBLC)算法来解决两平面Bézier曲线的交.在研究射线与三角Bézier曲面的求交方法之前,我们先研究了两Bézier曲线的求交,希望得到一些启发.IBLC算法利用了Bézier曲线的凸包性,降阶性以及曲线隐式化,将Bézier切割算法与隐式化算法结合起来,从而达到快速有效地求解两曲线的交.该算法继承了隐式化方法的高速性和Bézier切割算法的稳定性.我们从理论上证明了:横截相交情况下,IBLC算法具有2次收敛速度,数值实验表明该算法优于现存的求交算法. 2.提出了两种稳定且有效的几何算法来解决光线追踪问题中射线与三角Bézier曲面的求交问题(RPI).我们首先把RPI问题转化为求方程组的根的问题,这里方程组包含两个方程两个未知量.然后求解该方程组,所得的解即为射线与三角Bézier曲面的交. Bilinear clipping(BLC)算法:对每个方程我们用一组线性带状区域(fat line)去包围,这样方程组的根一定位于两组线性带状区域所围成的四边形中,即新得到的参数域小于原来的参数域.结合细分等方法进行迭代直到最后的参数域的直径小于给定的阈值.该算法利用三角Bézier曲面的凸包性,降阶算法,Descartes符号法则等技术,保证了算法运算的高效性,并且我们从理论上证明了该算法对于单根情况具有二阶收敛速度.另外,该算法克服了牛顿法的缺陷,即不需要提供初始值就能使整个迭代收敛于我们要求的交点. 基于BLC几何切割算法,提出了一种收敛速度更快,对重根更有效的算法来解决射线与三角Bézier曲面的求交问题(RPI),我们把它称作hybrid clipping(HC)算法.基本原理是:利用低次逼近(降阶方法实现)的思想,将方程组所表示的两条曲线用低次形式逼近,并分别选用一次和二次的带状区域来包围,这样交点将位于两带状区域所围成的参数域内(该参数域不大于原来的三角域),再结合细分方法,重复上述迭代过程直到参数域的直径小于某个给定的阈值. HC算法与BLC算法的区别在于:HC算法不直接对转化后的方程组进行操作,而是将转化后的方程组做一个预处理工作,使其变成等价的新的方程组,该步骤能有效提高算法的收敛阶.另外,HC算法是分别用一次和二次带状区域包围曲线,而BLC算法是用两组一次带状区域来包围曲线.理论和数值试验证明了HC算法在单根的情况有三阶收敛速度.顸处理虽然能有效提高收敛速度,但比较耗时.对于单根系统,BLC算法速度更快.对于重根系统,HC算法更有效. 3.估计了有理三角Bézier曲面导矢界.在曲面的绘制,曲线(线与线的交,面与面的交)奇异点的检测,曲面的平坦度检测等问题都需要估计曲线曲面的导数界.我们得到的界越紧越有助于提高算法的效率.因此,我们估计了有理三角Bézier曲面导矢界.通过利用三角Bézier曲面的升阶性、凸包性和一些基本的代数不等式技巧推导出了有理三角Bézier曲面一阶以及二阶导矢界,并且我们从理论和数值实验两方面说明我们估计出的界优于现存在的界.