《基于B样条曲面生成算法的研究与改进.doc》由会员分享，可在线阅读，更多相关《基于B样条曲面生成算法的研究与改进.doc（10页珍藏版）》请在金锄头文库上搜索。
1、B样条曲面生成算法的研究与改进本文由天空乐园大学生兼职网整理分享摘要本文首先介绍了B样条曲面生成的已有算法：基于B样条曲线生成的德布尔算法的B样条曲面的生成算法、基于样条曲面反算方法的B样条曲面生成算法。接着介绍了两种双三次B样条曲面生成的改进算法：1.基于deBoor和CoxB递推公式构造B样条曲面基的曲面生成算法，2.提高双三次B样条曲面的生成效率的改进算法。第2种算法能显著提高效率，提出B样条曲面正等测投影的建立方法，讨论用高性能的动态数组和Excel软件存储任意数量控制点的实现方法等关键技术。采用Visual C+6.0为编程工具开发软件系统，实现了任意数量控制点的双三次B样条曲面生成
2、。通过将改进的算法和已有的算法进行比较我们得出改进算法的优点。关键词：B样条曲面 生成算法 deBoor、CoxB递推公式1引言B样条曲线曲面是实体造型，虚拟现实等CADCAM领域中广泛使用的几何造型工具。B样条曲面具有与B样条曲线相同的局部支柱性、凸包性、连续性和几何不变性等性质。与Bezier曲面相比，B样条曲面极为自然地解决了曲面片之间的连接问题。它不仅继承了Bzier曲线曲面的所有优点，而且具有局部修改的性质，因此得到工业界的广泛认可。B样条曲面的生成算法一直都是学者们的研究热点。在施法中提出的B样条曲线生成的德布尔算法1的基础上，谭浩强将此算法推广到B样条曲面的生成2；吕 科，耿国华
3、，周明全等人提出了基于样条曲面反算方法的B样条曲面生成算法3；而近几年又有很多人提出了许多改进的算法，其中本文主要介绍了基于deBoor和CoxB递推公式构造B样条曲面基的曲面生成算法4 和提高双三次B样条曲面的生成效率的改进算法9。2.已有算法介绍2.1基于样条曲面反算方法的B样条曲面生成算法定义n,m分别为u向、v向上待插值数据点个数，k=3,l=3,分别为生成曲面在u向、v向上的次数。述的 B样条曲面为 P ( u, w ) = 。按网格 V中的行构造 w向的曲线, 则可得到四条 B样条曲线:其中: B j , 3 (w )为与顶点 Vi j对应的 B样条基函数; Vi j为控制顶点。当
4、参数 w在 0 , 1内取值 w1 时, 则可分别在曲线 Q1 (w )、Q2 (w )、 Q3 (w )、 Q4 (w )上得到四个点 q1、 q2、q3 和 q4。若以该四点作为新的特征多边形顶点再构造 u向的 B样条曲线:则 P ( u , w l)为曲面片上的一条曲线。当 u和 w 在 0 , 1之间遍历时, 就可以得到一张双三次 B样条曲面片, 如图 1所示。可通过正算, 用追赶法解方程组获得控制网格, 然后反算获得曲面, 再进行插值。如图 2为给定点云数据通过反求后, 滤掉不合格的点, 再生成的控制网格和曲面。2.2基于B样条曲线生成的德布尔算法的B样条曲面的生成2.2.1 B样条
5、曲线控制顶点及控制多边形的生成5(1) B样条曲线采用顶点定义，控制顶点的生成有下面几个过程来完成：程序先对控制顶点的坐标赋值：Contr-x=0; Contr-y=0；然后将鼠标所在点的坐标赋给控制顶点：；调入画直线函数，以坐标点(x,y)为中心，画小十字线：line(x-2,y,x+2,y);line(x,y-2,x,y+2).此时，一个点的输入结束，重复这个过程便会在屏幕上得到一系列的控制定点。点的输入结束后，调入直线命令，依次连接控制定点，即在屏幕上生成控制多边形。(2) 求B样条曲线上的点控制多边形确定以后，B样条曲线的形状取决于B样条曲线的次数，求B样条曲线上的点可采用德布尔算法的
6、递推公式。这里P(u)为所求曲线上的点。对于求出的B样条曲线上的一系列点，依次用小直线段连接。由于程序中选取的步长非常小，所以在屏幕上显示出所定义的一条眼观光滑的B样条曲线。2.1.2 B样条曲面控制网格的生成1生成过程如下：程序中用文件输入曲面的控制顶点;选取两个参数方向的次数分别用k与l表示，其取值范围：;选取两个参数方向的合适步长，将德布尔算法推广到曲面，计算并显示曲面上每个参数方向的对应于定义域内的眼观光滑的等参数线。其生成B样条曲面的算法如下：设给定曲面定义域一对参数值(u,v)，欲求该B样条曲面上对应的点P(u,v)可以先沿任一参数方向譬如先沿v参数方向，按如下步骤进行：首先以参数
7、值对沿v参数方向的m+1个控制多边形执行用于计算B样条曲线上点的德布尔算法，求得m+1个点作为中间顶点，构成中间多边形。然后，以u参数值对这中间多边形执行B样条曲线的德布尔算法，所得一点即所求B样条曲面上一点P(u,v)。给出一系列u,v值，就得到曲面上的一系列点。光滑连接生成曲面：对于求出的B样条曲面上的一系列的点，依次用小直线段连接，即在屏幕上显示出所定义的一张眼观滑的等参数线，即B样条曲面片。下图即为屏幕输出的控制网格及曲面片。2.2.1反算u向控制顶点对于截面层中的存储数据，采用统一的u向节点矢量U：在节点矢量U上，应用B样条曲线反算，构造出一族统一节点矢量的截面曲线，求出它们的样条控
8、制点：2.2.2反算V向控制顶点曲面的v向节点矢量V定义为：在节点矢量 V上，以上一步所求得的 u向控制点阵为新的待插值数据点，视首末截面对应数据点处 v向切矢为给定的边界条件，沿 v向方向重复曲线插值算法，即以 第i列为数据点，及给定处v向切矢量为给定的边界条件反算出条插值曲线，其控制点阵 m+k插值曲线，其控制点阵：即为所求双 3次样条插值曲面的控制定点。由控制顶点即可生成曲面。3.改进算法3.1基于deBoor和CoxB递推公式构造B样条曲面基的曲面生成根据 de Boo r和 CoxB递推公式，在区间 a , b上, 取分割为节点 ( knot) ,构造 B样条基函数为以下递推公式：令
9、k=3则得到工程所用的三次B样条曲面基函数。设已知型值点网格为 Pi , j( i= 1 , 2 , , m; j= 1 , 2 , , n )。其中 m和 n分别为 u向和 w 向的型值点数。所求的多边形顶点网格为则所描3.2 提高双三次B样条曲面的生成效率的改进算法3.2.1 双三次B样条曲面的数学模型在空间给定（n+1）*（m+1）个点Pij （i=0， 1 n； j=0， 1 m），则可以逼近生成一个n *m次的B样条曲面片，其定义为2:以逼近生成一个n m次的B样条曲面片，其定义为:式中： Pij B样条曲面P （u， v）的控制顶点；B样条基函数。由16个控制顶点构成的控制网格可绘
10、制一个双三次（3 *3）次B样条曲面片，它的矩阵表示为： (1)其中， U= u3 u2 u 1 V= v3 v2 v 1. 双三次 B样条曲面是由三次 B样条曲线交织而成。曲面生成时可以通过固定 u，变化v 得到一簇三次 B样条曲线；固定 v，变化 u得到另一簇三次 B样条曲线3(3孔令德.计算机图形学基础教程（Visual C+版）M .北京：清华大学出版社，2008)。当参数 u,v在0， 1之间遍历时，即可生成相应的双三次 B样条曲面片。对（1）式作如下改进：令 ，根据矩阵运算的结合律，则有其中，A 与 u、v均无关，只与控制点有关，也就是当 u、v以一定的步长从0逐步变到1的过程中，
11、 A的值不发生变化，因此可以在计算 P（ u，v ）前先计算出 A的值（不参与循环），这样可以减少运算时间，提高运算效率。3.2.2 连续曲面的生成双三次 B样条曲面极为自然地解决了曲面片之间的连续性问题 双三次 B样条曲面的顶点矩阵是。因为双三次B样条曲面的控制顶点是4*4的所以需要将控制顶点矩阵进行分块。可以采用文献3介绍的方法进行分块，生成连续曲面。3.2.3 正等侧投影的建立三维的真实世界和它的计算机表示是有根本区别的。要将三维的B样条曲面表示在二维平面上，必须经过投影变换。正等测投影能给人一种直观的立体形状，是获得具有立体感的三维图形的一种最常用的方法。设投影对象为三维点P（x ,y
12、,z），它的正等测投影变换矩阵为7(4林大钧.计算机工程图形算法及应用M .上海：华东理工大学出版社， 2006)：正等测投影的坐标是有由于计算机屏幕坐标是二维坐标系，原点位于屏幕左上角，x轴水平向右，y轴垂直向下，点的二维坐标为,因此三维坐标系向二维屏幕坐标系的变换公式可修改为4 改进算法的实现4.1 动态数组的应用在程序实现的过程中，若采用固定数组描述控制点的坐标，则数组的长度应定义为该组数据可能出现的最大个数 由于事先无法预知这个最大个数，那么为了程序的通用性，就必须定义足够大的数组，以适应不同用户对数据量大小不同的需要 但这样做往往会导致内存空间大量浪费，而且可能会导致系统崩溃使程序无
13、法运行 动态数组可根据需要动态地使用和释放内存，有效提高内存的使用率 它可以根据程序运行时状态的不同而随时改变容量，因此动态数组在程序设计中的应用十分广泛。VC+6.0开发工具中的MFC提供了一套模板库，来实现一些比较常见的数据结构 CArray即为其中的一个，它是一个可以存放任何数据类型的复杂的数组结构，并可以实现数组的动态管理，在内存中的地址分配是连续的，可以提高程序的效率。4.2 Excel的应用将控制点的坐标以一定的格式输入到Excel 2003电子表格中， 7*7=49个控制点（数据来源为文献3），如图1所示。用VisualC+编程访问该电子表格获取坐标数据，并赋值给动态数组，这样可
14、以实现任意数量控制点的存贮 可直接对Excel中的数据进行增加 删除 编辑，因此具有可扩充性，方便用户使用，并可以实现程序与数据的分离，提高了软件的适用性。4.3 程序运行结果程序的运行结果，如图2所示 图中同时生成了双三次B样条曲面和相应的控制点网格。结论（1）基于基于deBoor和CoxB递推公式构造B样条曲面基的曲面生成的改进算法相对于传统算法更加精确逼近。（1）采用提高曲面生成效率的改进算法可以显著提高B 样条曲面的生成效率（2）采用动态数组可以存贮任意数量的控制点，具有重要的工程意义（3）解决了双三次B样条曲面由理论转化为可视化的问题。（4）设计模块可以单独使用，也可作为一个模块嵌入
15、到其它图形系统中使用。5.参考文献1谭浩强.C程序设计.M 北京：清华大学出版社，19952银红霞.计算机图形学M .北京：中国水利水电出版社， 20053吕 科，耿国华，周明全,医学图象三维表面的快速重构方法J,计算机工程.2002年第28卷第2期。4阎开印, 穆朝永,基于 B样条的曲面生成及加工仿真研究J,计算机应用研究.2007年8月第二十卷第8期。5施法中.计算机辅助几何设计与非均匀有理B 样条.北京:北京航空 航天大学出版社 ,1994. 2283186孔令德.计算机图形学基础教程（Visual C+版）M .北京：清华大学出版社， 20087林大钧.计算机工程图形算法及应用M .上海：华东理工大学出版社， 20068方逵，双三次B样条插值曲面，J,数学理论与应用.2001年9月第21卷第3期。9陈岳坪，李书平，谌炎辉，王虎奇，双三次B样条曲面生成的关键技术研究，J机械设计与制造,2010年4月第4期。10李铁军，自由曲面的计算机辅助几何造型设计与数控加工自动编程系统，D,哈尔滨工业大学硕士论文，1987 由开封市同力基础工程有限公司
