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

1在任意拓扑网格上递归生成B样条曲面Edwin.CatmullandJ.Clark摘要：本文介绍了一种通过递归生成曲面来逼近任意拓扑网格上的点的方法．此方法是一种递归双三次B样条细分算法的推广．对矩形网格，这种方法生成一张标准B样条曲面；对非矩形网格，除了在少数称为特别点（extraordinarypoints）外，它生成标准Ｂ样条曲面．从而，除了这些特别点以外，生成的曲面是2C的（continuousintangentandcurvature）．在特别点处，曲面的图象显示曲面至少是1C的，但是没有关于连续性的证明．本文还给出了双二次Ｂ样条的类似的算法．正文：自从Catmull首先设计将递归曲面细分算法应用于演示曲面片的阴影（shaded渐变）图象1以后，这种算法在计算机图形方面得到了广泛的应用．他设计的这种算法递归细分一个曲面片为四个子片，直到生成的片的大小大致相当于用于显示图形的显示器的一个图形元素（pixel象素）．这时，图形的清晰度的试验和它的阴影（渐变）性质的表现都非常简单．当Catmull的工作接近完成的时候，GeorgeChaikin在一次讨论会上提出了一种从一个控制多边形出发，通过递归“割角”来生成光滑曲线的方法2．在此基础上，Catmull得到了一种任意拓扑多面体网格上生成三次曲面的方法．但是，由于他不能证明曲面在每一点处的都是充分光滑（顺）的，他没有完成并贯彻这种方法．近期，Clark完成了这种方法来经验地确定曲面是否光滑，并确定了生成曲面上新点的规则．根据本文给出的一套细分方法所生成的曲面是2C的．Doo和Sabin分析了曲面在特别点的邻域内的性质5，这里给出的图形是证明他们的预测的一部分．这里给出的算法对构造三维物体的光滑图形有很大用处．如果确定物体的控制点不是位于拓扑矩形网格上的话，确定其光滑逼近是很容易的．这种方法的基础是考察一个矩形控制点网格上的标准双三次Ｂ样条曲面片．这个曲面片的形状由１６个控制点决定，见图１，初始控制点用圆圈表示．当细分此曲面片为四个子面片时，生成了２５个子控制点，用x表示．注意到某些x位于初始网格的矩形的中间，这些点称为新面点（newfacepoints）．类似的，一些新点位于连接初始控制点的边上，这些点称为新边点（newedgepoints）；对应于旧控制点的点称为新顶点（newvertexpoints）．在分裂初始曲面片时，上述的每一种控制点都可以利用与其相邻的点采用相同的代数表达式来计算．例如，每个新面点是通过其所在的面元的四个旧顶点取平均值得到的．本文介绍了一种方法将这种细分规则推广到任意的控制网格．此方法采用与四边形情况相同的表达形式，即新面点是面元的所有旧顶点的平均值等等，新顶点依赖于和原顶点相连接的边的数目，在矩形情况，正确的表达式是边的数目等于４的情况．矩形Ｂ样条片分裂：双三次Ｂ样条片可以表为下列矩阵形式：ttVUMGMvuS),(（１）这里（此处见朱心雄：《自由曲线曲面造型技术》，pp１３１）014103030363133161M是三次Ｂ样条基矩阵，且244434241343332312423222114131211PPPPPPPPPPPPPPPPG是控制顶点集合，按照下标排列在一个拓扑矩形网格上，而]1[23uuuU和]1[23vvvV是原始基向量．我们将只考虑曲面片相应于21,0vu的子片．根据Ｂ样条基的对称性，不用考虑其它子片．记此子片为),(11vuS，这里21uu，21vv．代入表达式（１）得tttVSUSMGMvuS),(11（２）这里1000021000041000081S]1[23uuuU且]1[23vvvV这一必须仍然是双三次Ｂ样条，且具有满足满足如下条件的控制点网格1G：ttVMUMGvuS111),(这个表达式应该等价于（２）式，而这对任意的u和v都成立当且仅当tttSSMGMMMG1因基矩阵M是可逆的，得到tttGHHSMMGSMMG1111][][这里SMMH11称为分裂矩阵．经过计算得1610044001610044811H从而子片的控制顶点网格通过如下表达式与原来的控制顶点联系tGHHG111（３）在图１中，新的面点q是1G的（１，１）元素，通过（３）式计算得42221121111ppppq（４）3类似的，新边点12q由下式给出222221212ppDCq（５）这里42221121111ppppCq且42322131213ppppDq新顶点22q由下式给出4242222pRQq（６）这里433311311qqqqQ且2222412322322221221222ppppppppR易证1G的每个元素满足某个类似于（４），（５），（６）的表达式．由于这些表达式是从标准Ｂ样条基推出的，所以它们生成一个双三次Ｂ样条曲面．任意拓扑结构为将（４），（５），（６）式推广到任意拓扑结构，方便的方法是将它们表达成一套规则，这套规则依赖于一个面元周围的顶点个数和与一个顶点相连接的边的条数．显然当顶点个数和边的条数都是４的时候，这套规则要等价于（４），（５），（６）式．规则如下：（Ａ）新面点――确定面元的所有旧顶点的平均值．（Ｂ）新边点――旧边的中点的平均值和此边两侧的两个新面点的平均值．（Ｃ）新顶点――下述平均值nnSnRnQ)3(2这里Ｑ＝旧顶点所在的所有面元上的新面点的平均值．Ｒ＝旧顶点相连接的所有旧的边的中点的平均值．Ｓ＝旧顶点．计算出这些点以后，新的边通过以下方法形成：１．连接每一个新面点到确定旧面元的边上的新边点．２．连接每一个新顶点到与旧顶点相连的所有旧边上的新边点．由这些新边形成新的面元．在图２中给出了应用这些规则到一个简单的非矩形拓扑结构的结果．图２（a）中原始的三角形区域记为Ａ，它要被一个三角形曲面片逼近．象矩形拓扑结构一样，区域Ａ周围的另外四个区域用于定义片的边界上的斜率和曲率．图２（b）给出应用规则一次的结果．需要注意的是所有新面元都有四条边．但是，现在有四个顶点的度是３，这些点分别是相对于区域Ａ的原来的旧顶点所产生的三个新顶点和区域的一个新面点．按照Coons的提议，我们称这些点为特别点（extraordinarypoints），因为最后生成的曲面只在与这些点关联的最终顶点处不是标准Ｂ样条曲面．4再一次应用规则得到图２（c）．此图中，１６个点排列在矩形拓扑结构上，相关联的产生６个面，生成标准Ｂ样条．为清楚记，这些面元用阴影表示（？）．既然所采用的规则对具有这种拓扑结构的点生成一个标准双三次Ｂ样条片，这些区域生成Ｂ样条片．如此，最终的三角形曲面的一部分已经确定，并且因为具有这种顶点的双三次Ｂ样条是2C的，曲面的这一部分当然是连续的．应用规则三次所确定的Ｂ样条曲面片更靠近那些特别点，见图２（d）．用交叉的平行线画出阴影的区域显示了应用规则所产生的新的曲面片．每个新片图２（c）中的适当的片，并具有标准Ｂ样条的连续性．这是显然的，如果我们继续细分这样成的曲面片，曲面片间共有的点规定和继承了连续性．但是，因为用另一算法绘制（render）标准曲面片计算效率更高，所以每次生成一个标准Ｂ样条片就转到一个标准绘制算法（renderingalgorithm透视算法）．显然进一步对特别点周围的区域应用规则会生成更多的更靠近这些点的标准曲面片．在极限情形，整个三角形区域除了特别点以外，被一个Ｂ样条曲面所覆盖．从而，除了可能在特别点以外，这个三角形区域被一个连续曲面所逼近．因为规则对任意拓扑结构都成立，所以区域的形状不必是简单三角形．除了在特别点以外，任意边数结构都生成一个Ｂ样条曲面．需要注意的是，应用规则一次后，所有的面元都是四边形，从而后边产生的所有新点的度都是４．这样，每次应用规则以后，曲面上特别点的个数是一个不变的常数．读者会对曲面在特别点处的性态感兴趣．近期对这些点处的连续性做出分析的（解析的）证明．但是，利用这些规则生成的曲面显示曲面在任意点处至少是1C的．图３给出了由一个四面体（不具有矩形网格控制顶点的最小体积元素）的初始形状所生成的曲面．由于应用规则一次后，每个面产生一个度为３的顶点，所以曲面是封闭的，并且具有８个特别点，对应于四面体的每一个原始的度为３的顶点（共４个），每个面一个（共４个）．图４给出了用于生成图３的原始的四面体以及生成的曲面的线框图．从图３显然看出曲面在相应于四面体的原始顶点的最终顶点处是1C的．另外一种网格见图５，这种网格生成的封闭元见图６．上面给出的规则稍微有些任意，实际上原来实验了另一个规则（Ｃ）．新顶点是（Ｃ）（预备的）424SRQ利用此规则不能得到满意的结果，对于四面体生成的曲面过于尖锐．利用此规则生成的图形导致我们去寻找一套更好的规则，其中最好的就是上面给出的．一套更好的规则，实际上，一个对于规则的更好的评判标准（而不是通过图象的质量表现）仍需要设计．根据M.Sabin的建议，做出了一个取点自马鞍面xyz的网格．中心多边形有８条边．图７给出了沿z轴的垂直投影．应用一次后，在中心有一个点连接了８条边（见图８，９）．从马鞍面的明暗图形（图１０）可以看出，如果一个马鞍面周围的边数很多时，中心的性态不好．马鞍面的例子说明作者没有找到最好的一套规则．双二次曲面这个方法还可以应用到双二次Ｂ样条．生成细分网格的办法是对原始网格的每个面、边和点都产生一个新面元．在图１１中，粗线是原始网格，细线是新网格．得到每个新点的规则是依赖于它所靠近的角点．通过与上述类似的方法对双二次细分进行分析可以得到，在图１１中163392221121111ppppq这可以改写成一个规则用于在一个旧顶点p附近生成一个新顶点qnnpnEnFq)3(2其中n＝面元的顶点数．5Ｆ＝面元的顶点的平均值．Ｅ＝连接点p的两条边的平均值．此规则可以同样地应用于任意的拓扑结构．这种情况下，经过一次细分，非四边形面元的个数保持常数且所有的顶点的度为４．结论本文给出的在任意网格上生成Ｂ样条曲面的方法除了在少数特别点以外是连续的．所生成的图形显示曲面在这些点处也是连续的，但没有给出关于连续性的分析证明．还有一些用于逼近非矩形控制顶点网格的方法．例如，Lane和Riesenfeld3给出了双参数变量的一个公式．还有，Barnhill4给出了一个三角形片逼近方案．这些方法都不同于本文给出的方法．要证明曲面在特别点处的连续性，需要一个对在任意拓扑结构网格上的逼近计划的一致（coherent连贯，凝聚）的数学处理．这种处理应该包含所有这些细分方法．希望本文能激励这些研究．参考文献1.Catmull,Edwin,Asubdivisionalgorithmforcomputerdisplayofcurvedsurfaces.TechnicalReportUTECCSc-74-133,UniversityofUtah,USA(1974).2.Riesenfeld,R.F,OnChaikin’sAlgorithm,Comput.Graph.ImageProc.Vol4(1975)pp304-310.3.Lane,J.M,Riesenfeld,R.F,Theapplicationoftotalpositivitytocomputeraidedcurveandsurfacedesign.TechnicalReport,Dept.ofComputerScience,UniversityofUtah,USA(1977).4.Barnhill,R.E,Smoothinterpolationovertriangles.CAGDAcademicPress(1974)pp45-70.5.Doo,DandSabinM,Behaviourofrecursivedivisionsurfacesnearextraordinar