基于B样条曲面生成算法的研究与改进

1B样条曲面生成算法的研究与改进摘要本文首先介绍了B样条曲面生成的已有算法：基于B样条曲线生成的德布尔算法的B样条曲面的生成算法、基于样条曲面反算方法的B样条曲面生成算法。接着介绍了两种双三次B样条曲面生成的改进算法：1.基于deBoor和CoxB递推公式构造B样条曲面基的曲面生成算法，2.提高双三次B样条曲面的生成效率的改进算法。第2种算法能显著提高效率，提出B样条曲面正等测投影的建立方法，讨论用高性能的动态数组和Excel软件存储任意数量控制点的实现方法等关键技术。采用VisualC++6.0为编程工具开发软件系统，实现了任意数量控制点的双三次B样条曲面生成。通过将改进的算法和已有的算法进行比较我们得出改进算法的优点。关键词：B样条曲面生成算法deBoor、CoxB递推公式1引言B样条曲线曲面是实体造型，虚拟现实等CAD／CAM领域中广泛使用的几何造型工具。B样条曲面具有与B样条曲线相同的局部支柱性、凸包性、连续性和几何不变性等性质。与Bezier曲面相比，B样条曲面极为自然地解决了曲面片之间的连接问题。它不仅继承了Bézier曲线曲面的所有优点，而且具有局部修改的性质，因此得到工业界的广泛认可。B样条曲面的生成算法一直都是学者们的研究热点。在施法中提出的B样条曲线生成的德布尔算法[1]的基础上，谭浩强将此算法推广到B样条曲面的生成[2]；吕科，耿国华，周明全等人提出了基于样条曲面反算方法的B样条曲面生成算法[3]；而近几年又有很多人提出了许多改进的算法，其中本文主要介绍了基于deBoor和CoxB递推公式构造B样条曲面基的曲面生成算法[4]和提高双三次B样条曲面的生成效率的改进算法[9]。22.已有算法介绍2.1基于样条曲面反算方法的B样条曲面生成算法定义n,m分别为u向、v向上待插值数据点个数，k=3,l=3,分别为生成曲面在u向、v向上的次数。述的B样条曲面为P(u,w)=WBTTUBV。按网格V中的行构造w向的曲线,则可得到四条B样条曲线:2;4,3,2,1,,413,iwwVBQjijji其中:Bj,3(w)为与顶点Vij对应的B样条基函数;Vij为控制顶点。当参数w在[0,1]内取值w1时,则可分别在曲线Q1(w)、Q2(w)、Q3(w)、Q4(w)上得到四个点q1、q2、q3和q4。若以该四点作为新的特征多边形顶点再构造u向的B样条曲线:3,,1413,wQBwjjjluuP则P(u,wl)为曲面片上的一条曲线。当u和w在[0,1]之间遍历时,就可以得到一张双三次B样条曲面片,如图1所示。可通过正算,用追赶法解方程组获得控制网格,然后反算获得曲面,再进行插值。如图2为给定点云数据通过反求后,滤掉不合格的点,再生成的控制网格和曲面。32.2基于B样条曲线生成的德布尔算法的B样条曲面的生成2.2.1B样条曲线控制顶点及控制多边形的生成[5](1)B样条曲线采用顶点定义，控制顶点的生成有下面几个过程来完成：程序先对控制顶点的坐标赋值：Contr-x=0;Contr-y=0；然后将鼠标所在点的坐标赋给控制顶点：.;ymouseyContrxmousexContr；调入画直线函数，以坐标点(x,y)为中心，画小十字线：line(x-2,y,x+2,y);line(x,y-2,x,y+2).此时，一个点的输入结束，重复这个过程便会在屏幕上得到一系列的控制定点。点的输入结束后，调入直线命令，依次连接控制定点，即在屏幕上生成控制多边形。(2)求B样条曲线上的点控制多边形确定以后，B样条曲线的形状取决于B样条曲线的次数，求B样条曲线上的点可采用德布尔算法的递推公式。1,,iikilkjilkijljdNduuP这里P(u)为所求曲线上的点。对于求出的B样条曲线上的一系列点，依次000,,,;,2,1,10,11111jlkjjljljljljljjljilkijklldddd4用小直线段连接。由于程序中选取的步长非常小，所以在屏幕上显示出所定义的一条眼观光滑的B样条曲线。2.1.2B样条曲面控制网格的生成[1]生成过程如下：程序中用文件输入曲面的控制顶点。这里lnmnjmidji,0;,1,0;,,1,0,,;选取两个参数方向的次数分别用k与l表示，其取值范围：.0,0nlmk;选取两个参数方向的合适步长，将德布尔算法推广到曲面，计算并显示曲面上每个参数方向的对应于定义域内的眼观光滑的等参数线。其生成B样条曲面的算法如下：设给定曲面定义域一对参数值(u,v)，欲求该B样条曲面上对应的点P(u,v)可以先沿任一参数方向譬如先沿v参数方向，按如下步骤进行：首先以参数值对沿v参数方向的m+1个控制多边形执行用于计算B样条曲线上点的德布尔算法，求得m+1个点作为中间顶点，构成中间多边形。然后，以u参数值对这中间多边形执行B样条曲线的德布尔算法，所得一点即所求B样条曲面上一点P(u,v)。给出一系列u,v值，就得到曲面上的一系列点。光滑连接生成曲面：对于求出的B样条曲面上的一系列的点，依次用小直线段连接，即在屏幕上显示出所定义的一张眼观滑的等参数线，即B样条曲面片。下图即为屏幕输出的控制网格及曲面片。52.2.1反算u向控制顶点对于截面层中的存储数据，采用统一的u向节点矢量U：knkniknkikiuPPuuimjijijkii2,,11,,1,,,0,00,1,在节点矢量U上，应用B样条曲线反算，构造出一族统一节点矢量的截面曲线，求出它们的样条控制点：。mjknidji,,1,0,1,,1,0,,2.2.2反算V向控制顶点曲面的v向节点矢量V定义为：knkniknkikivPPvvimjijijkii2,,11,,1,,,0,00,1,在节点矢量V上，以上一步所求得的u向控制点阵为新的待插值数据点，视首末截面对应数据点处v向切矢为给定的边界条件，沿v向方向重复曲线插值算法，即以dji,第i列为数据点，及给定ddmii,0,,处v向切矢量为给定的边界条件反算出条插值曲线，其控制点阵m+k插值曲线，其控制点阵：;1,,1,0,1,,1,0,',lmjknidji即为所求双3次样条插值曲面的控制定点。由控制顶点即可生成曲面。3.改进算法3.1基于deBoor和CoxB递推公式构造B样条曲面基的曲面生成根据deBoor和CoxB递推公式，在区间[a,b]上,取分割baxxxn10为节点(knot),构造B样条基函数为以下递推公式：1,,0,11,11111,,i10,xxxxxxNxxxNxxxNxxNkiikikikiikiikiii其他令k=3则得到工程所用的三次B样条曲面基函数。设已知型值点网格为Pi,j(i=1,2,,m;j=1,2,,n)。其中m和n分别为u向和w向的型值点数。所求的多边形顶点网格为,2,,2,1;2,,2,1,njmiVji则所描63.2提高双三次B样条曲面的生成效率的改进算法3.2.1双三次B样条曲面的数学模型在空间给定（n+1）*（m+1）个点Pij（i=0，1n；j=0，1m），则可以逼近生成一个n*m次的B样条曲面片，其定义为[2]:以逼近生成一个nm次的B样条曲面片，其定义为:1,0,,,,,00vuvuvuPFFPmininimjij式中：PijB样条曲面P（u，v）的控制顶点；为、vuFFmni,i,B样条基函数。由16个控制顶点构成的控制网格可绘制一个双三次（3*3）次B样条曲面片，它的矩阵表示为：VMMTTBBGUvuP,(1)其中，U=［u3u2u1］V=［v3v2v1].0,1,4,10,3,0,30,3,6,31,3,3,161MBPPPPPPPPPPPPPPPPG33323130232221201312111003020100,,,,,,,,,,,,双三次B样条曲面是由三次B样条曲线交织而成。曲面生成时可以通过固定u，变化v得到一簇三次B样条曲线；固定v，变化u得到另一簇三次B样条曲线[3](3孔令德.计算机图形学基础教程（VisualC++版）［M］.北京：清华大学出版社，2008)。当参数u,v在[0，1]之间遍历时，即可生成相应的双三次B样条曲面片。对（1）式作如下改进：令MMTBBGA，根据矩阵运算的结合律，则有VTUAvuP,其中，A与u、v均无关，只与控制点有关，也就是当u、v以一定的步长从0逐步变到1的过程中，A的值不发生变化，因此可以在计算P（u，v）前先计算出A的值（不参与循环），这样可以减少运算时间，提高运算效率。3.2.2连续曲面的生成双三次B样条曲面极为自然地解决了曲面片之间的C2连续性问题双三次B样条曲面的顶点矩阵是PPPPPPPPPPmnnmmij3101111000100~,,,,,,,,,。因为双三次B样条曲面的控制顶点是4*4的所以需要将控制顶点矩阵进行分块。可以采用文献[3]介绍的方7法~Pij进行分块，生成连续曲面。3.2.3正等侧投影的建立三维的真实世界和它的计算机表示是有根本区别的。要将三维的B样条曲面表示在二维平面上，必须经过投影变换。正等测投影能给人一种直观的立体形状，是获得具有立体感的三维图形的一种最常用的方法。设投影对象为三维点P（x,y,z），它的正等测投影变换矩阵为[7](4林大钧.计算机工程图形算法及应用［M］.上海：华东理工大学出版社，2006)：1,0,0,00,8165.0,0,00,4082.0,0,7071.00,4082.0,0,7071.0T正等测投影的坐标是,1,,,1,,,'''zyxzyxT有zyxyxzx8265.04082.04082.0707.07071.0''由于计算机屏幕坐标是二维坐标系，原点位于屏幕左上角，x轴水平向右，y轴垂直向下，点的二维坐标为yx'''',,因此三维坐标系向二维屏幕坐标系的变换公式可修改为zyxyxzyxx8165.04082.04082.07071.07071.0''''''4改进算法的实现4.1动态数组的应用在程序实现的过程中，若采用固定数组描述控制点的坐标，则数组的长度应定义为该组数据可能出现的最大个数由于事先无法预知这个最大个数，那么为了程序的通用性，就必须定义足够大的数组，以适应不同用户对数据量大小不同的需要但这样做往往会导致内存空间大量浪费，而且可能会导致系统崩溃使程8序无法运行动态数组可根据需要动态地使用和释放内存，有效提高内存的使用率它可以根据程序运行时状态的不同而随时改变容量，因此动态数组在程序设计中的应用十分广泛。VC++6.0开发工具中的MFC提供了一套模板库，来实现一些比较常见的数据结构CArray即为其中的一个，它是一个可以存放任何数据类型的复杂的数组结构，并可以实现数组的动态管理，在内存中的地址分配是连续的，可以提高程序的效率。4.2Excel的应用将控制点的坐标以一定的格式输入到Excel2003电子表格中，7*7=49个控制点（数据来源为文献[3]），如图1所示。用VisualC++编程访问该电子表格获取坐标数据，并赋值给动态数组，这样可以实现任意数量控制点的存贮可直接对Excel中的数据进行增加删除编辑，因此具有可扩充性，方便用户使用，并可以实现程序与数据的分离，提高了软件的适用性。4.3程序运行结果程序的运行结果，