NURBS体造型与布尔运算
NURBS体造型与布尔运算
高新瑞 张树生 侯增选
(西北工业大学 现代设计与集成制造技术教育部重点实验室，西安，710072)
摘 要：该论文主要讨论NURBS体造型技术与并、交、差布尔运算。NURBS体造型技术主要有蒙皮法、拉伸法与旋转法等。影响NURBS体形状的因素有：控制顶点、结点与结点的重度、权因子与基函数次数。为计算方便，将一次、二次、三次NURBS曲线系数矩阵用统一矩阵形式表示。用基于NURBS体三参数u、v、w的体素模型实现NURBS体的并、交、差布尔运算。
关 键 词：NURBS体；NURBS体造型；体素模型；布尔运算
中图分类号：TP391
Construction of NURBS Volumes and Boolean Operations
Gao Xinrui，Zhang Shusheng， Hou Zengxuan
(Northwestern Polytechnical University The key Laboratory of Contemporary Design and Integrated Manufacturing Technology , Ministry of Education, China, Xi’an,710072)
Abstract: this paper mainly discusses construction of NURBS volumes and the Boolean operations of union, intersection and difference. The methods of construction of NURBS volumes include skinning, sweeping and swinging etc.. The factors which affect the shape of a NURBS volumes include control points, nodes and the multiplicity of nodes, weights, and orders of base functions. For the convenience of calculation, it gives similar expressions of coefficient matrixes of NURBS base functions of cubic and square curves and line. Based on Voxel-based NURBS volumes, the Boolean operations are accomplished.
Key words: NURBS volume. construction of NURBS volumes. Voxel-based volume. boolean operations
1．引言
现代几何造型技术更强调体的造型而不是基于面的造型，在通用几何体元的基础上更强调带有物理属性能够自由变形的体造型，并且强调能够进行交互式操作[1]。首先区分体（Volume）与实体（Solid）概念。实体内部的属性是均匀，而体在其内部可以通过体素表示不同部分的多种物理属性[2]。例如，可使体内部包含有实体、液体、多空物质、不同颜色与材质等成分。
体的表示形式分为两种：连续的表示与离散表示。由基函数（例如B样条、NURBS等）、数学表达式（例如隐含数）、小波类多分辨率等方式所形成的体都属于连续表示形式的体，该类型体函数值在参数范围内是连续变化的。基于体素（Voxel）的体，则是离散形式的体模型。基于体素的体是将一个体离散成一系列的体素，体素的大小根据应用需要可调控。每个体素内部具有相同的属性（边界体素除外，因为该体素是部分占有的）。体素与体素之间靠拓扑关系组织在一起。连续表示形式体的特点是体的表示式简单，但要表示体内物体的不同属性也只能用相应的属性函数，比较麻烦。同时并、交、差布尔运算也比较难实现。基于体素的体仅仅包含一系列相关的体素，没有一个统一的体的表达式，正因为这种离散的特点使得针对每个体素的操作很容易，所有的体素都具有统一的数据结构，对每个体素属性的设置很容易，并且使并、交、差等布尔运算也很容易实现。在这种情况下，通过结合以上两种体表示形式的特点，又产生了第三种体的表示形式：将连续型的体离散成Voxel体的表示形式[2]。既先生成连续型体，再将其离散成一系列Voxel形式（Voxelization）。对一个体这两种表示形式并存，可以兼具两方面的优点。该方法是一种新的体的表示方法。
NURBS技术是目前CAGD领域最常用的一种设计手段。目前对NURBS的研究与应用主要集中在NURBS曲面上，全世界有大量的文章都是这一方面的。相比之下，对NURBS体研究的论文相对较少。分析原因：在NURBS体的造型过程中需要大量的控制顶点，一般情况下，形成NURBS体内部分的控制顶点在只对NURBS体表面有严格要求的情况下没有多大意义，但又必须给出。对于特别复杂形体，这是一项比较艰巨的任务。可能正是这一方面限制了NURBS体的实际应用。而在基于NURBS体的自由变形方面，NURBS体与其控制顶点之间的关系被推广到对任意体的自由变形计算方面，相关内容可以参照[3][4][5][6][7][8][9][10]论文。在这种变形中，首先强调被变形的物体与控制顶点之间没有内在的关系，这个体可以是由NURBS控制顶点形成的体，也可以是用其它方法（如隐含数方法）产生的体，而包围该体的控制顶点也是根据物体形状任意给定。只是在对体表面点进行变形计算的时候，才用到NURBS面上点或NURBS体上点变化量与相应控制顶点变化量之间关系。这一方面的计算效果等都有待进一步研究。
NURBS体的形状由控制顶点、结点、基函数次数、顶点与结点的重复度、控制顶点权因子决定。NURBS体的造型方法与面的造型方法相似（Ruling，Sweeping，Skinning，Shrinking等）。下面对NURBS体的造型技术进行讨论。
2．影响NURBS体的因素
对NURBS体产生影响的因素：结点及其分布（均匀、非均匀）、端结点是否为重结点、控制顶点、权因子、NURBS基函数次数。结点的分布与重度直接影响给定NURBS次数的基函数。图2、图3显示了在同样的64个控制顶点情况下端结点是否重复所产生的三三次NURBS体图形。图1是给定控制多边形，共含有4*4*4=64个控制顶点，图中显示的只是外围的控制顶点。图2是各端结点重复度为4时所产生的图形。图3是端结点没有重复而采用均匀结点时所产生的NURBS体。所产生NURBS体的形状截然不同。
在产生不同次的NURBS 体时，经常存在基函数表达式不统一的问题。这给体的生成带来困难。下面将对应区间中分别由一次、二次、三次基函数所形成的NURBS曲线的系数矩阵表达式加以统一。这一点对NURBS线、面、体的统一计算很重要。
对于三次NURBS基函数Ni，3（u）的表示式为：
对于区间，其间曲线系数矩阵表达式为：
二次NURBS基函数的表达式：
二次NURBS曲线系数矩阵表达式。将其改为三次系数矩阵表示形式为：并将u、v、w矩阵作相应变化，如。
对于由一次NURBS基函数所形成直线的系数矩阵作同样变化：并将u矩阵变为。一次NURBS基函数对柱体、拉伸体等生成比较重要。
通过采用统一的系数矩阵表达式可使使生成各种类型NURBS体时具有统一编程与处理。
3.NURBS体造型
NURBS体的表达式为： [11]。该表达式对NURBS体的生成方式难于理解，这可能是影响NURBS体应用的一个原因；另一个影响NURBS体使用的原因是分母的存在，由于分母的存在使各种计算很复杂。对NURBS体的表示，Young-Ho Chai 在论文[1]提出了一种用一维数组表示NURBS体的方式。该方法在计算与处理方面很麻烦。为了表示和计算方便，采用齐次坐标表示形式：[2]，这个表达式在计算过程中可以去掉分母，可大大简化计算。但对所产生齐次坐标表示的体一定要向w=1的超平面中心投影[11]。将其表示为矩阵块形式：。U、V、W表示在u、v、w三个方向的局部坐标变量的一维矩阵。如果采用双三次NURBS体，则，。为对应u、v、w三参数方向的系数矩阵块，也是控制顶点坐标的矩阵块表示形式。矩阵块表示的最大优点便于用循环编程实现，并且与NURBS的面与线具有相同的表示形式。
NURBS体造型主要包括:蒙皮技术(Skinning)、拉伸技术（Sweeping）、旋转技术（Swing）、直面体技术（Ruling）和伸缩技术（Shrinking）。其中，拉伸技术（Sweeping）、直面体技术（Ruling）和伸缩体技术（Shrinking）可归为一类。所有这些方法都主要是对控制顶点的进行相应操作。
蒙皮技术首先由C D Woodward在1988年提出[12]，并在论文[2]中有详细介绍。其基本思想让B样条曲面通过给定的一系列B样条截线。将这一方法推广到NURBS体的生成，让NURBS体通过一系列的给定的NURBS截面。拉伸体是由对某一NURBS面（包括平面与曲面）沿某一方向移动一段距离所形成，例如，各种类型柱体等。如果拉伸体的方向不固定，而是沿着脊线（Spine line）在变化，这样形成的体称为Sweeping体,图4为由固定截面形成的Sweeping体。旋转体是某一NURBS面绕着某一轴线旋转一周或未满一周而形成的体。直面体是直纹面技术在体成型方面的推广。伸缩体是将某一封闭的柱面向其中心轴线收缩所形成的体，和通过拉伸所生成的体相同。任意NURBS六面体是在u、v、w三参数所形成立方体域内，由所有控制顶点与相应权因子，通过各方向给定次数的基函数所生成的NURBS体。任意NURBS六面体通过相应的处理可以变为其它各种体，也就是说，其它各种NURBS体都是由任意NURBS六面体的经某种特殊变形而产生的。具体造型过程可参考[2]、[11]，在此不再重述。
另一个很值得研究的NURBS体造型技术是将复杂NURBS曲面的造型技术与NURBS体的造型技术相结合，并在NURBS体并、交、差布尔运算基础上，生成能够满足各种工程需要的复杂NURBS体。目前在这一方面这方面的研究较少，是一个需进一步研究方向，在此不作进一步讨论。
4．NURBS体的并、交、差布尔运算
NURBS体的并、交、差布尔运算是基于NURBS体的体素模型。本文所采用的体素模型就是基于Voxel的NURBS体。该体素模型的数据结构为：
其结合了NURBS体与Voxel体素模型的特点。该体素模型是基于NURBS体的u、v、w三参数的体素模型，是对NURBS三维形体的一种特殊离散。体素模型越小，表示的NURBS体的精度越高。在该体素模型的基础上，实现对NURBS体素模型显示，并提取体表面四边形网格与三角网格，进而可以用体表曲面四边网格与三角网格显示该NURBS体。用Marching-Cubes方法根据体与体之间体素的关系决定哪些体素应该在留下，并在最后的图形中显示，哪些体素应该去掉。
在图8、9中，虽然参加布尔运算的形体是简单的立方体，但这两个立方体是两个三三次NURBS体，端结点重复度为4。布尔运算是基于NURBS体的Voxel模型进行的。
5．NURBS体造型与布尔运算图例
本文在Java2.0环境下编程并验证算法[13]，在Java3D环境下显示图形[14]。图1、图2、图3显示端结点的重复度对三三次NURBS体的影响。图1是给定控制顶点所形成的多边形，共含有4*4*4=64个控制顶点，图中显示的只是外围的控制顶点。图2是各端结点重复度为4时所产生的体。图3是端结点没有重复而采用均匀结点时所产生的NURBS体。图4是特殊截面的Sweeping体。图5、6、7是在调整NURBS控制顶点时产生的三种复杂形体。图8、9、10、11、12与布尔运算相关的体。所有NURBS体的显示都采用Voxel模型，而未用表面四边域或三角域显示，这样作使NURBS体更具立体感。
6．结论
通过使用各种NURBS体造型技术可以生成各种复杂形体；当将NURBS体造型技术与复杂NURBS曲面造型技术相结合，便会产生表面形状复杂的NURBS体，一般这种复杂NURBS体很难直接通过NURBS体造型技术产生；再通过NURBS体之间布尔运算，可以生成满足各种工程需要的NURBS组合体。由此可见，NURBS体造型技术在CAD、CAGD与逆向工程方面有着很广阔的应用前景。
参考文献
[1] Young-Ho Chai, Greg R. Lucecke , James C. Edwards. Virtual Clay Modeling Using the ISU Exoskeleton[J]. In Proc .IEEE VRAIS '98. 1998. 76-80.
[2]D. Ma, F. Lin, C. K. Chun. Rapid Prototyping Applications in Medicine.Part 1: NURBS-Based Volume Modeling [J].Advanced Manufacture echnology.2001.18:103-117
[3] S. -M. Hu , Y. -F. Li , T. Ju , X. Zhu..Modifying the shape of NURBS surfaces with geometric constraints [J]. Computer Aided Design.2001.903-912.
[4]Sabin Coquillart.Extended Free-Form Deformation:A Sculpturing Tool 3D Geometric Modeling[J].Computer Graphics,Volume 24,Number 4,August 1990.pp.187-196
[5]William M Hsu,John F. Hughes, Henry Kaufman.Direct Manipulation of Free –Form Defromation[J].Computer Graphics,26,2,July 1992.pp.177-184
[6]Henry J. Lamousin,Warren N. Waggenspack. NURBS-Based Free-Form Deformation[J].Computer Graphics and Applications.1994.59-65
[7]Ron MacCracken,Kenneth I. Joy.Free-Form Deformation With Lattices of Arbitrary Topology[J].In Computer Graphics(SIGGRAPH 96).1996.181-188
[8]Young-Ho Chai,Greg R.Lucecke,James C. Edwards. Virtual Clay Modeling Using the ISU Exoskeleton[J]. In Proc. IEEE VRAIS '98. 1998. 76-80.
[9]Shi-Min Hu,Hui Zhang,Chiew-Lan Tai,Jia-Guang Sun.Direc manipulation of FFD:efficient explicit solutions and decomposiblel multiple point constraints[J].Visual computer.2001.17:370-370.
[10]Yutaka，Bing-Yu Chen，Tomoyuki Nishita，Jieqing Feng.Free-Form Deformation with Automatically Generated Multiresolution Lattices[J].2002.
[11]施法中.计算机辅助几何设计与非均匀有理B样条[M].北京航空航天大学出版社.1993.10
[12]C D Woodward. Skinning techniques for interactive B-spline Surfaces Interpolation [J]. CAD. 1988. 441-451.
[13]印旻.Java语言与面向对象的程序设计[M].清华大学出版社.2000.9.
[14]顾雷.刘鹏.房冰.都志辉.Java3D编程实践[M].清华大学出版社.2002年11月.
NURBS体造型与布尔运算.doc
