在任意拓扑网格上递归生成B样条曲面.doc

在任意拓扑网格上递归生成B样条曲面 Edwin. Catmull and J. Clark 摘要： 本文介绍了一种通过递归生成曲面来逼近任意拓扑网格上的点的方法．此方法是一种递归双三次B样条细分算法的推广．对矩形网格，这种方法生成一张标准B样条曲面；对非矩形网格，除了在少数称为特别点（extraordinary points）外，它生成标准Ｂ样条曲面．从而，除了这些特别点以外，生成的曲面是的（continuous in tangent and curvature）．在特别点处，曲面的图象显示曲面至少是的，但是没有关于连续性的证明．本文还给出了双二次Ｂ样条的类似的算法． 正文： 　　自从Catmull首先设计将递归曲面细分算法应用于演示曲面片的阴影（shaded渐变）图象以后，这种算法在计算机图形方面得到了广泛的应用．他设计的这种算法递归细分一个曲面片为四个子片，直到生成的片的大小大致相当于用于显示图形的显示器的一个图形元素（pixel象素）．这时，图形的清晰度的试验和它的阴影（渐变）性质的表现都非常简单． 当Catmull的工作接近完成的时候，George Chaikin在一次讨论会上提出了一种从一个控制多边形出发，通过递归“割角”来生成光滑曲线的方法．在此基础上，Catmull得到了一种任意拓扑多面体网格上生成三次曲面的方法．但是，由于他不能证明曲面在每一点处的都是充分光滑（顺）的，他没有完成并贯彻这种方法．近期，Clark完成了这种方法来经验地确定曲面是否光滑，并确定了生成曲面上新点的规则．根据本文给出的一套细分方法所生成的曲面是的．Doo和Sabin分析了曲面在特别点的邻域内的性质，这里给出的图形是证明他们的预测的一部分． 这里给出的算法对构造三维物体的光滑图形有很大用处．如果确定物体的控制点不是位于拓扑矩形网格上的话，确定其光滑逼近是很容易的． 这种方法的基础是考察一个矩形控制点网格上的标准双三次Ｂ样条曲面片．这个曲面片的形状由１６个控制点决定，见图１，初始控制点用圆圈表示．当细分此曲面片为四个子面片时，生成了２５个子控制点，用x表示．注意到某些x位于初始网格的矩形的中间，这些点称为新面点（new face points）．类似的，一些新点位于连接初始控制点的边上，这些点称为新边点（new edge points）；对应于旧控制点的点称为新顶点（new vertex points）．在分裂初始曲面片时，上述的每一种控制点都可以利用与其相邻的点采用相同的代数表达式来计算．例如，每个新面点是通过其所在的面元的四个旧顶点取平均值得到的． 本文介绍了一种方法将这种细分规则推广到任意的控制网格．此方法采用与四边形情况相同的表达形式，即新面点是面元的所有旧顶点的平均值等等，新顶点依赖于和原顶点相连接的边的数目，在矩形情况，正确的表达式是边的数目等于４的情况． 矩形Ｂ样条片分裂： 双三次Ｂ样条片可以表为下列矩阵形式： 　　　　　　　　　　　　　（１） 这里（此处见朱心雄：《自由曲线曲面造型技术》，pp１３１） 是三次Ｂ样条基矩阵，且 是控制顶点集合，按照下标排列在一个拓扑矩形网格上，而 和 是原始基向量． 　　我们将只考虑曲面片相应于的子片．根据Ｂ样条基的对称性，不用考虑其它子片．记此子片为，这里，．代入表达式（１）得 　　　　　　　　　　　　（２） 这里 且 这一必须仍然是双三次Ｂ样条，且具有满足满足如下条件的控制点网格： 这个表达式应该等价于（２）式，而这对任意的和都成立当且仅当 因基矩阵是可逆的，得到 这里 称为分裂矩阵．经过计算得 从而子片的控制顶点网格通过如下表达式与原来的控制顶点联系 　　　　　　　　　　　　　　　（３） 在图１中，新的面点是的（１，１）元素，通过（３）式计算得 　　　　　　　　　　　　（４） 类似的，新边点由下式给出 　　　　　　　　　　　　（５） 这里 且 　　新顶点由下式给出 　　　　　　　　　　　　　　（６） 这里 且 　　易证的每个元素满足某个类似于（４），（５），（６）的表达式．由于这些表达式是从标准Ｂ样条基推出的，所以它们生成一个双三次Ｂ样条曲面． 任意拓扑结构 为将（４），（５），（６）式推广到任意拓扑结构，方便的方法是将它们表达成一套规则，这套规则依赖于一个面元周围的顶点个数和与一个顶点相连接的边的条数．显然当顶点个数和边的条数都是４的时候，这套规则要等价于（４），（５），（６）式．规则如下： （Ａ）新面点――确定面元的所有旧顶点的平均值． （Ｂ）新边点――旧边的中点的平均值和此边两侧的两个新面点的平均值． （Ｃ）新顶点――下述平均值 这里 Ｑ＝旧顶点所在的所有面元上的新面点的平均值． Ｒ＝旧顶点相