NURBS裁剪曲面绘制方法

摘要：根据NURBS曲面在u,v参数域的偏导数动态地把NURBS曲面细分成一些四边形区域，然后用双三次Bézier曲面实现这些四边形的C1连续的逼近。完成裁剪曲面绘制这个过程需要由GPU(Graphic Processing Unit)执行两遍。第一遍先由几何着色器实现裁剪曲面的三角化，再由像素着色器生成裁剪纹理。在此基础上执行第二遍，由几何着色器实现双三次Bézier面片的镶嵌，然后由像素着色器根据裁剪纹理绘制出裁剪后的NURBS曲面。采用GPU实现NURBS裁剪曲面的绘制，把大部分的计算从CPU迁移到了GPU。

关键词：动态细分；几何着色器；像素着色器；NRUBS裁剪曲面；GPU

中图分类号：TP391文献标识码：A文章编号：1009-3044(2012)09-2077-04

Rending Method of Trimming NURBS Surface

LIU Bin, ZHANG Ren-jing

(School of Mathematics and Computer Science, Guizhou Normal University, Guiyang 550001, China)

Abstract: NURBS surface is subdivided dynamically into some quadrilaterals according to the partial differential with respect to parameter field of w or v, then approximate these quadrilaterals with bi-cubic C1-continuous Bézier surfaces. GPU(Graphic Processing Unit) renders the trimmed NURBS surface in two passes. First, it uses geometry shader to triangulate the trimmed surface, then uses fragment shader to generate trimmed texture. In the second pass, the tessellation of the bi-cubic Bézier patch is realized by geometry shader, later on, the fragment shader renders the trimmed surface according to the trimmed texture. GPU is introduced to render the trimmed NURBS surface, as it can do a great part of computing works that processed in CPU before.

Key words: dynamic subdivision; geometry shader; fragment shader; NURBS trimmed surface; GPU

1概述

由于非均匀有理B样条(non-uniform rational B-Spline,NURBS)曲面能够表示几乎所有的曲面，特别是它能精确地表示二次曲线和曲面，越来越多的CAD/CAM系统、虚拟现实系统都以NURBS曲面为其标准表示形式。但由于目前计算机显卡还不直接支持NURBS曲面的绘制，所以需要在CPU里将NURBS曲面转换成一些GPU支持的多边形，通常NURBS曲面转换为四边形或三角形（镶嵌）。为了能逼真的反映NURBS曲面的原貌，这些四边形或三角形都会要求比较小，因此会产生大量的四边形或三角形及其相关的数据。而且由于NURBS曲面表达式复杂（见公式1，2），计算量会比较大，因此会耗费CPU许多时间，很难应用到实时场景。随着可编程显卡的发展，含有几十个至几百个流处理器的显卡越来越普及，它们具有非常好的并行计算能力，所以将许多以前由CPU实现的工作交由GPU处理变成了可能。郭建华,鞠鲁粤利用Open GL提供的方法，把裁剪面看成是被裁剪曲面参数域的一个子域[1]。方顾,李际军等人首先在NURBS曲面的参数域中定义曲面的裁剪曲线，然后自上而下地分析曲面参数域中的每一条U(或V)向线段，通过这些线段与裁剪曲线的相交关系来判定曲面的裁剪域，从而实现NURBS曲面的裁剪[2]。Dongsoo Han利用GPU中几何着器实现NURBS曲面的镶嵌和绘制，但在他的报告中只涉及到了基本曲面的绘制[3]。Michael Guthe等人把NURBS曲面先用一系列Bézier面片逼近，但这些Bézier面片的次数有差异，需要将这些Bézier面片都用双三次Bézier曲面逼近，再由GPU的顶点着色器递归细分到合适的精度，然后由像素点着色器根据纹理实现裁剪[4-5]，他们这种由不同次数的Bézier面片用固定次数的Bézier曲面逼近的方法，当次数相差比较大时，逼近带来的误差也会比较大。该文采用一种新的方法，根据NURBS曲面在u和v参数域方向上的偏导数把曲面划分成一些小的区域，然后把这些区域用双三次Bézier曲面逼近，再将这些双三次Bézier曲面传送到GPU，由GPU几何着色器并行完成面片镶嵌，像素着色器实现裁剪纹理，生成被裁剪后的NURBS曲面。

2由CPU和GPU协调工作的NURBS裁剪曲面绘制过程

2.1算法概述

本NURBS裁剪曲面绘制由GPU执行2遍完成。第1遍由裁剪曲线生成裁剪纹理，第2遍把要被裁剪的NURBS曲面依据纹理绘 制出裁剪后的三角形网络，如图1所示。首先，从CPU将封闭的裁剪曲线参数传递给GPU，在能保证足够精度的情况下由几何着色器把裁剪曲面取样生成一些三角形；然后由像素着色器将这些三角形生成一个适当大小的纹理。CPU把NURBS曲面按参数的偏导数划分为一些四边形面片(详见2.2)，接着再用双三次Bézier曲面逼近这些四边形面片，然后CPU将逼近后双三次Bézier曲面参数值传递给GPU。几何着色器将面片根据细节层次值进行细分镶嵌，组合出一些逼近Bézier面片的三角形图元，并将这些三角形图元传递给像素着色器。最后在执行裁剪时，像素着色器根据相应纹理的值绘制，如果纹理值为1就显示该像素点，如果为0则不显示该像素点（见2.4）。

图1基于GPU的NURBS裁剪曲面绘制过程

2.2 NURBS曲面的动态面片化

NURBS曲面的有理分式表示如公式（1）：

式中，Qi,j为控制顶点，形成NURBS曲面的控制网格。wi,j为权与因子，分别与控制顶点Qi,j对应。基函数Bi,m(u)和Bj,n(v)是B样条基函数，分别由节点矢量U=(u0,u1,…,um+p+1)和V=(v0,v1,…,vn+q+1)按公式2递推定义。

根据NURBS曲面的弯曲程度把NURBS曲面变换成一些四边形。通过求曲线关于u,v参量的导数，就可以求得出令(1)式右端分子为N，分母为D，则s关于u的一阶导数为:

su=?è

(6)

s关于v的一阶导数同理可以求出。

2.2.1面片化方法

如图2所示NURBS曲面的一个子四边形区域(边界线为u1,u2,v1,v2)。求su(u1,v1)和su(u2,v1)的值，它们分别代表曲面在参数(u1,v1)和(u2,v1)处u方向的偏导数，可以求出这两个偏导数矢量之间的夹角，可以这样认为，这个角度越小，曲面就越光滑，如图3所示。再求su(u1,v2)和su(u2,v2)的值，代表参数(u1,v2)和(u2,v2)处u方向的偏导数，再求出这两偏导数矢量的夹角。同样可以求出sv(u1,v1)和sv(u1,v2), sv(u2,v1)和sv(u2,v2)以及这两对矢量之间的夹角。如果这四个夹角中有一个大于某个设定的值(此值越小后面绘制出来结果越准确，但计算量会增大)，就在u和v的中点把此四边形分为四个四边形。再把这四个新得到的小四边形按前面的方法做同样的处理，直到所有四边形顶点偏导数矢量之间的夹角都小于规定的值为止。为了避免曲面中间有尖峰，在求u或v方向的偏导数夹角时不仅仅求端点的偏导数，同也在端点之间另求几个点的值，如果任意两个点的偏导数之间的夹角大于设定的值都要

图2面片化示意图

2.2.2面片的存储结构

因为实行的是一分四，所以采用四叉树来存储面片集合。图3所示的曲面面片化后的层次如图3所示。用方格表示的是还要继续分割的面，这个面被分为四个更小的子面。用圆圈表示的是已经不需要再进一步分割的面片，在每个面片中在记录的内容依次是s(u1,v1)，s(u2,v1), s(u1,v2), s(u2,v2), su(u1,v1)，su(u2,v1), su(u1,v2), su(u2,v2), sv(u1,v1)，sv(u2,v1), sv(u1,v2), sv(u2,v2), s(u1+(u2-u1)/ 3, v1+(v2-v1)/3)，s(u1+(u2-u1)/3, v1+2(v2-v1)/3) , s(u1+2(u2-u1)/3, v1+(v2-v1)/3)，s(u1+2(u2-u1)/3, v1+2(v2-v1)/3)。这些值用来把四边形面片用双三次Bézier曲面逼近时使用，详情参考2.3。图3面片的层次结构

2.3面片双三次Bézier曲面逼近

双三次Bézier曲面参数方程为：

q(u,v)=∑

P0,0P0,1P0,2P0,3

P1,0P1,1P1,2P1,3

P2,0P2,1P2,2P2,3

P3,0P3,1P3,2P3,3

所以曲面关于u和v的偏导数分别用公式(10)(11)求出。

qu=[U’][N][P][N]T[V]

(10)

qv=[U][N][P][N]T[V’](11)

为了找到图3所示每个四边形面片的双三次的Bézier逼近曲面，由前面的内容可知，我们每个四边形面片保存的信息包括4个

顶点，4个顶点在u,v方向的偏导数共8个值，另外还保存了四边形中间的4个偏导数，合计在每个四边形面片共有16个数值可供使

用。通过4个顶点可求出P0,0, P0,3, P3,0, P3,34个顶点，保证逼近曲面的C1连续性可以用u方向的偏导列出4个方程，v方向的偏导

也可以列出4个方程。另外保存的4个中间曲面上的值也可以列出4个方程，共12个线性方程求出面中另外12个顶点的值。

2.4裁剪纹理

裁剪曲线的数据从CPU传送到GPU后，根据显示窗口的大小生成一个全部数据都为1的纹理，然后把属于裁剪区内的位置的数据改写为0.每一个裁剪都将根据曲线生成一些三角形片，所有三角形内的纹理数据都改写为0，当所有三角形都处理完后裁剪区域的纹理都变为0了，在第2遍绘制图形时，每个像素点根据纹理的值进行处理，如果为1就显示出来，为0就不显示。裁剪纹理如图3所示，灰色部分为1，白色区域为0。

3实验结果

实验软硬件环境：显卡：NVidia GeForce 8800GT,内存：2G，操作系统：Windows XP,开发工具:Visual Studio 2005 Professional,编程语言:C/C++,Cg 2.0(beta),主要编程库:Win32 API, OpenGL/GLU。如图4所示，(a)是没有被裁剪的NURBS曲面(b)是被一条NURBS曲线裁剪后的曲面(c)是被两条NURBS曲线裁剪后的曲面。

4结束语

该文提供了一种采用CPU和GPU协同绘制NURBS裁剪曲面的方法,CPU根据NURBS曲面的光滑程度动态地划分成一些四边形区域，并把这些四边形的区域用满足C1连续性的Bézier曲面逼近，然后利用几何着色器可以批量处理几何图形的特性及强大的并行计算能力绘制这些Bézier曲面。这种方法可以广泛应用于CAD/CAM、虚拟现实、游戏等领域。这种绘制方法具备以下四个方面的优点：⑴动态面片化算法可以减少CPU的计算量，提高逼近的精度；⑵从CPU传送到GPU的数据大幅度降低，数据总线带宽不会再是系统瓶颈，便于获得高质量的曲线和曲面的显示效果；⑶由于显卡具有许多流处理器，曲面镶嵌和绘制可以进行并行处理；⑷细节层次是由GPU实现，不再影响CPU的负载。不过，几何着色器也存在以下局限性：⑴输出的图元数目受到限制，所以目前还是需要CPU实现小部分几何计算的功能，需要CPU将复杂的曲面进行粗分为一些曲面后再传送到GPU；⑵几何着色器代码长度及循环迭代受限，在超出限制时要想办法精炼代码。

参考文献：

[1]郭建华,鞠鲁粤.用Open GL和MFC实现NURBS曲面的绘制及裁剪[J].上海大学学报:自然科学版,2004,10(4):367-370.

[2]方顾,李际军.用于非均匀有理B样条曲面裁剪的扫描线算法[J].计算机集成制造系统,2007,13(10):2060-2063.

[3] Han Dongsoo. Tessellating and Rendering Bezier/B-Spline/NURBS Curves and Surfaces using Geometry Shader in GPU[EB/OL]. www.seas.upenn.edu/~cis665/projects/CIS%20665%20GPU%20Project%20Final%20Report%20-%20Dongsoo%20Han.pdf

[4] Michael Guthe,ákos Balázs,Reinhard Klein.GPU-based Trimming and Tessellation of NURBS and T-Spline Surfaces[J]. ACM Transactions on Graphics, 2005.24(3):1016-1023.

[5] Michael Guthe,ákos Balázs,Reinhard Klein.GPU-based Appearance Preserving Trimmed NURBS Rendering[J]. Journal of WSCG,2006, 14(1):1-8.

[6] T Lyche, K Morken. Making the Oslo algorithm more efficient[J]. SIAM Journal on Numerical Analysis.1986,23(3): 663-675.