《基于B样条曲面生成算法的研究与改进》由会员分享，可在线阅读，更多相关《基于B样条曲面生成算法的研究与改进（10页珍藏版）》请在金锄头文库上搜索。
1、1B 样条曲面生成算法的研究与改进摘要本文首先介绍了 B 样条曲面生成的已有算法：基于 B 样条曲线生成的德布尔算法的 B 样条曲面的生成算法、基于样条曲面反算方法的 B 样条曲面生成算法。接着介绍了两种双三次 B 样条曲面生成的改进算法：1.基于 deBoor 和CoxB 递推公式构造 B 样条曲面基的曲面生成算法，2.提高双三次 B 样条曲面的生成效率的改进算法。第 2 种算法能显著提高效率，提出 B 样条曲面正等测投影的建立方法，讨论用高性能的动态数组和 Excel 软件存储任意数量控制点的实现方法等关键技术。采用 Visual C+6.0 为编程工具开发软件系统，实现了任意数量控制点的
2、双三次 B 样条曲面生成。通过将改进的算法和已有的算法进行比较我们得出改进算法的优点。关键词：B 样条曲面 生成算法 deBoor、CoxB 递推公式1 引言B 样条曲线曲面是实体造型，虚拟现实等 CADCAM 领域中广泛使用的几何造型工具。B 样条曲面具有与 B 样条曲线相同的局部支柱性、凸包性、连续性和几何不变性等性质。与 Bezier 曲面相比，B 样条曲面极为自然地解决了曲面片之间的连接问题。它不仅继承了 Bzier 曲线曲面的所有优点，而且具有局部修改的性质，因此得到工业界的广泛认可。B 样条曲面的生成算法一直都是学者们的研究热点。在施法中提出的 B 样条曲线生成的德布尔算法1的基础
3、上，谭浩强将此算法推广到 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 ) = 。按网格 V 中的行构造 wWTUBV向的曲线, 则可
4、得到四条 B 样条曲线:2;4,31,413,iwQjjji其中: B j , 3 (w )为与顶点 Vi j 对应的 B 样条基函数; Vi j为控制顶点。当参数 w 在 0 , 1内取值 w1 时, 则可分别在曲线 Q1 (w )、Q2 (w )、Q3 (w )、 Q4 (w )上得到四个点 q1、 q2、q3 和 q4。若以该四点作为新的特征多边形顶点再构造 u 向的 B 样条曲线:3, 1413,jjjluP则 P ( u , w l)为曲面片上的一条曲线。当 u 和 w 在 0 , 1之间遍历时, 就可以得到一张双三次 B 样条曲面片, 如图 1 所示。可通过正算, 用追赶法解方程组
5、获得控制网格, 然后反算获得曲面, 再进行插值。如图 2 为给定点云数据通过反求后, 滤掉不合格的点, 再生成的控制网格和曲面。32.2 基于 B 样条曲线生成的德布尔算法的 B 样条曲面的生成2.2.1 B 样条曲线控制顶点及控制多边形的生成5(1) B 样条曲线采用顶点定义，控制顶点的生成有下面几个过程来完成：程序先对控制顶点的坐标赋值：Contr-x=0; Contr-y=0；然后将鼠标所在点的坐标赋给控制顶点： ；.; ymouseyContrxmusexContr 调入画直线函数，以坐标点(x,y)为中心，画小十字线：line(x-2,y,x+2,y);line(x,y-2,x,y+
6、2).此时，一个点的输入结束，重复这个过程便会在屏幕上得到一系列的控制定点。点的输入结束后，调入直线命令，依次连接控制定点，即在屏幕上生成控制多边形。(2) 求 B 样条曲线上的点控制多边形确定以后，B 样条曲线的形状取决于 B 样条曲线的次数，求 B样条曲线上的点可采用德布尔算法的递推公式。 1, , iikilkjilkij dNduuP这里 P(u)为所求曲线上的点。对于求出的 B 样条曲线上的一系列点，依次0, ,;,21,10,11jlkjjlj ljljjlj ilkijdd4用小直线段连接。由于程序中选取的步长非常小，所以在屏幕上显示出所定义的一条眼观光滑的 B 样条曲线。2.1
7、.2 B 样条曲面控制网格的生成1生成过程如下：程序中用文件输入曲面的控制顶点;选取两个参数方向的次数分别用 k。这 里 lnmjidji ,0;,1;,0, 与 l 表示，其取值范围： ;选取两个参数方向的合适步长，将.k德布尔算法推广到曲面，计算并显示曲面上每个参数方向的对应于定义域内的眼观光滑的等参数线。其生成 B 样条曲面的算法如下：设给定曲面定义域一对参数值(u,v)，欲求该 B 样条曲面上对应的点 P(u,v)可以先沿任一参数方向譬如先沿 v 参数方向，按如下步骤进行：首先以参数值对沿 v 参数方向的 m+1 个控制多边形执行用于计算 B 样条曲线上点的德布尔算法，求得 m+1 个
8、点作为中间顶点，构成中间多边形。然后，以 u 参数值对这中间多边形执行 B 样条曲线的德布尔算法，所得一点即所求 B 样条曲面上一点 P(u,v)。给出一系列 u,v 值，就得到曲面上的一系列点。光滑连接生成曲面：对于求出的 B 样条曲面上的一系列的点，依次用小直线段连接，即在屏幕上显示出所定义的一张眼观滑的等参数线，即 B 样条曲面片。下图即为屏幕输出的控制网格及曲面片。52.2.1 反算 u 向控制顶点对于截面层中的存储数据，采用统一的 u 向节点矢量 U：kni knikiuPimj jijkii 2,11,0,01, 在节点矢量 U 上，应用 B 样条曲线反算，构造出一族统一节点矢量的
9、截面曲线，求出它们的样条控制点： 。mjknidj ,10,10, 2.2.2 反算 V 向控制顶点曲面的 v 向节点矢量 V 定义为：kni knikiPimj jijkii 2,11,0,01, 在节点矢量 V 上，以上一步所求得的 u 向控制点阵为新的待插值数据点，视首末截面对应数据点处 v 向切矢为给定的边界条件，沿 v 向方向重复曲线插值算法，即以 第 i 列为数据点，及给定 处 v 向切矢量为给定的边dji, dmii,0,界条件反算出条插值曲线，其控制点阵 m+k 插值曲线，其控制点阵：;1,0,1,0, ljknij 即为所求双 3 次样条插值曲面的控制定点。由控制顶点即可生成
10、曲面。3.改进算法3.1 基于 deBoor 和 CoxB 递推公式构造 B 样条曲面基的曲面生成根据 de Boo r 和 CoxB 递推公式，在区间 a , b上, 取分割为节点 ( knot) ,构造 B 样条基函数为以下递推公式：baxn101, ,11,i 1, xxxNNkiikikiikikiii 其 他令 k=3 则得到工程所用的三次 B 样条曲面基函数。设已知型值点网格为 Pi , j( i= 1 , 2 , , m; j= 1 , 2 , , n )。其中 m 和 n 分别为 u 向和 w 向的型值点数。所求的多边形顶点网格为 则所,2,;2, jVji 6描3.2 提高双
11、三次 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 样条曲面片，其定义为:,0, ,0 vuvuPFiiijj式中： Pij B 样条曲面 P （u， v）的控制顶点； B 样条为、 vuFmni,i,基函数。由 16 个控制顶点构成的控制网格可绘制一个双三次（3 *3）次 B 样条曲面片，它的矩阵表示为： (1)VMTBGUv,其中， U= u3 u2 u 1 V= v3 v2
12、v 1.0,43,6MB P323102132100,双三次 B 样条曲面是由三次 B 样条曲线交织而成。曲面生成时可以通过固定 u，变化 v 得到一簇三次 B 样条曲线；固定 v，变化 u 得到另一簇三次 B样条曲线3(3 孔令德.计算机图形学基础教程（Visual C+版） M .北京：清华大学出版社，2008)。当参数 u,v 在0， 1之间遍历时，即可生成相应的双三次 B 样条曲面片。对（1）式作如下改进：令 ，根据矩阵TBGA运算的结合律，则有 VTUAvuP,其中，A 与 u、v 均无关，只与控制点有关，也就是当 u、v 以一定的步长从 0 逐步变到 1 的过程中， A 的值不发生
13、变化，因此可以在计算 P（ u，v ）前先计算出 A 的值（不参与循环） ，这样可以减少运算时间，提高运算效率。3.2.2 连续曲面的生成双三次 B 样条曲面极为自然地解决了曲面片之间的 连续性问题 双三次 C2B 样条曲面的顶点矩阵是 。因为双三次 B 样条曲面的控Pmnmij 3101100, 7制顶点是 4*4 的所以需要将控制顶点矩阵进行分块。可以采用文献3介绍的方法 进行分块，生成连续曲面。Pij3.2.3 正等侧投影的建立三维的真实世界和它的计算机表示是有根本区别的。要将三维的 B 样条曲面表示在二维平面上，必须经过投影变换。正等测投影能给人一种直观的立体形状，是获得具有立体感的三
14、维图形的一种最常用的方法。设投影对象为三维点 P（x ,y,z） ，它的正等测投影变换矩阵为7(4 林大钧.计算机工程图形算法及应用M .上海：华东理工大学出版社，2006)： 1,0865.0,42.,7.T正等测投影的坐标是 有,1, zyxTyxz8265.04.082.7由于计算机屏幕坐标是二维坐标系，原点位于屏幕左上角，x 轴水平向右，y 轴垂直向下，点的二维坐标为 ,因此三维坐标系向二维屏幕坐标系的变换公式可修改为 zyxz8165.042.08.714 改进算法的实现4.1 动态数组的应用在程序实现的过程中，若采用固定数组描述控制点的坐标，则数组的长度应定义为该组数据可能出现的最
15、大个数 由于事先无法预知这个最大个数，那么为了程序的通用性，就必须定义足够大的数组，以适应不同用户对数据量大小8不同的需要 但这样做往往会导致内存空间大量浪费，而且可能会导致系统崩溃使程序无法运行 动态数组可根据需要动态地使用和释放内存，有效提高内存的使用率 它可以根据程序运行时状态的不同而随时改变容量，因此动态数组在程序设计中的应用十分广泛。VC+6.0 开发工具中的 MFC 提供了一套模板库，来实现一些比较常见的数据结构 CArray 即为其中的一个，它是一个可以存放任何数据类型的复杂的数组结构，并可以实现数组的动态管理，在内存中的地址分配是连续的，可以提高程序的效率。4.2 Excel 的应用将控制点的坐标以一定的格式输入到 Excel 2003 电子表格中， 7*7=49 个控制点（数据来源为文献3） ，如图 1 所示。用 VisualC+编程访问该电子表格获取坐标数据，并赋值给动态数组，这样可以实现任意数量控制点的存贮 可直接对 Excel 中的数据进行增加
