基于CSG体的投影包围盒加速算法研究

陆济湘，唐双平，严晓凤

(武汉理工大学理学院，湖北 武汉 430070)

在基本的光线跟踪算法中，每一条射线都要和场景中的所有物体求交，然后再对所给的求交数据进行分析排序，这是一个重复迭代的过程，需要对大量的光线进行一遍又一遍同样的操作[1]。而对于复杂环境的场景，这种简单的处理渲染效率很低。为了提高渲染效率，需要对光线跟踪算法进行加速，加速技术主要包括以下几个方面:提高求交速度、减少求交次数、减少光线跟踪条数和采用并行计算等。提高求交速度的算法在计算机图形学中已经发展得较为成熟;而减少光线跟踪条数会降低图形的渲染质量;采用并行计算则需要硬件的支持。因此，现在的研究重点在减少求交次数。为减少求交次数，在光线跟踪中可采用包围盒技术[2－5]。包围盒技术是加速光线跟踪的基本方法之一，其基本思想是用一些简单的包围盒(如球面、长方体)将复杂景物包围起来，求交的光线首先与包围盒进行求交测试，若相交，则光线再与景物求交，否则光线与景物必无交[6]。简单的包围盒技术效率并不高，因为被跟踪的光线必须与场景中每一个景物的包围盒进行求交测试。

由于包围盒形状简单(一般是长方体)，在三维空间中不能紧密的包围景物;景物之间也有空隙，且包围盒是将整个场景都包裹，这就造成了大量的无效求交测试。为了进一步提高求交效率，笔者提出了一种新的包围盒，即投影包围盒技术。

投影包围盒是指场景中的物体投影在屏幕上一块包裹物体的矩形区域，即将三维的数据转化为二维数据。这样，在减少数据分析量的同时，光线跟踪也不用对整个屏幕进行迭代，只需要对投影在屏幕的区域进行迭代，从而缩短渲染的时间。构造实体几何(CSG)的布尔操作(交，并，差)是CSG的核心内容。对于基于CSG的投影包围盒，需要在预处理阶段扫描CSG物体对应的树，在每个节点处对物体进行布尔操作，构建CSG体的投影包围盒。

1 CSG体数据结构设计

构造实体几何(CSG)是由基本的几何形体通过布尔操作构造的，这些基本的形体包括正方体、圆柱体、球和圆锥体等。这些形体之间可以进行几何变换和布尔操作。利用二叉树将这些形体保存起来，构造一棵CSG树，可以显著减少对场景中物体进行排序的时间[7]。通过二叉树来表示CSG体的信息，如图1所示。

构造CSG树时，叶节点对应于基本的几何形体，非叶节点则对应于布尔操作。叶节点的数据结果描述如下:

由于布尔体没有自己的仿射变换，而在SDL文件中，没有经过仿射变换的是默认方式的形体，如正方体，默认边长为1，图1中的A是正方体经过了几何变换后得到的，因此要将几何变换保存在节点中，对于图1的CSG树，可将几何变换写入节点中，即叶节点对应的是几何变换后的形体，如图2所示(T表示几何变换)。

图1 CSG树

图2 几何变换后的形体示意图

保持节点中的显式变换，可以在CSG体被构建后，通过单独使用树中的一个变换来调整形状，而这也为寻找布尔体的更紧致的包围盒提供了可能。

2 投影包围盒算法设计

2.1 点束的采集

CSG体的投影包围盒要求在预处理阶段为每个物体求投影包围盒，并且把它与对应的物体存储起来，因此必须在预处理阶段为场景中的所有物体构建点束[8－10]。由于CSG体是由基本的形体通过布尔操作完成的，因此在预处理阶段为基本的形体建立点束。长方体和平面的点束可以直接采用顶点，而对于球体和其他的形体则用一个紧紧包裹这些形体的多面体，点束就是多面体的顶点[11]。如球体采用一个20面体来包裹它，顶点则在离球心大约1.26倍半径的地方。

2.2 投影包围盒的建立

通过上述方法建立的点束，可以快速地建立投影包围盒。当然，这种情况下所求的投影包围盒的坐标是在OpenGL下的坐标，因此要将点束转化为屏幕坐标系下的坐标。投影包围盒主要记录4个坐标信息，即屏幕上矩形区域的{left，right，top，bottom}，点束中的每个点都投影到所对应的屏幕上，如图3所示。

图3 点束投影示意图

伪代码如下:

2.3 创建CSG体的投影包围盒

利用上述方法可以实现物体投影包围盒的创建，同时一个CSG体的每个节点的投影包围盒的构建与其长方体包围盒的构建相同。每个节点的投影包围盒由其左右子树的投影包围盒组成。用P(object)来表示object的投影包围盒，则有如下表示:

并集:P(L∪R)=P(P(L)∪P(R))

差集:P(L∩R)=P(L)∩P(R)

交集:P(L－R)=P(L)

以CSG体交集为例，则CSG差集的投影包围盒的 4 个坐标信息{left，top，right，bottom}如下:

3 实验与分析

为验证笔者提出算法的有效性，利用VC++6.0和OpenGL对图形库进行了交、并、差3种布尔操作。比较基于光线跟踪下，CSG体在未使用投影包围盒和使用投影包围盒的时间，所得到的结果是:投影包围盒可以快速提高CSG体的渲染时间。

(1)CSG体并集运算在两种情况下的时间比较如图4所示。场景中的物体是由两个圆柱的并操作而来的。通过实验数据可以观察到:使用投影包围盒，渲染的时间从原来的2 891 μs减少到359 μs，时间缩短至原来的大约1/8，渲染效率有了很大的提高。

图4 CSG体并集运算在两种情况下的时间比较

(2)CSG体差集运算在两种情况下的时间比较如图5所示。场景中的物体是通过两个半径不相等的半球做差运算而来的。通过实验数据可以发现:CGS体原来的渲染时间是现在的大约8.4倍，渲染效率同样也有很大的提高。

图5 CSG体差集运算在两种情况下的时间比较

(3)CSG体交集运算在两种情况下的时间比较如图6所示。场景中的物体是通过3个圆柱体做布尔操作的交集运算而得到的。对比两个时间数据渲染效率提高了10倍。

图6 CSG体交集运算在两种情况下的时间比较

对CSG体的3种布尔操作，通过实验分析数据可以发现，在运用光线跟踪的投影包围盒算法时，场景的渲染效率可提高8～10倍。结合以上的分析，笔者设计并实现了基于CSG体的投影包围盒加速算法。获取实验数据的计算机配置为酷睿双核，2.21 GHz，512 DDR内存，屏幕分辨率为1 024×768，光源为点光源与环境光。

4 结论

光线跟踪是建立CSG体的重要技术，提高光线跟踪算法效率是研究的重点之一。笔者采用投影包围盒算法，并结合CSG体中的布尔操作来实现和提高光线跟踪的渲染效率。实验表明，该算法能够将CSG体的渲染效率提高8～10倍。

[1] FRANCIS S H，STPHEN J M K.计算机图形学(OpenGL版)[M].胡事民，译.北京:清华大学出版社，2009:32－89.

[2] 吴慧欣，薛惠锋，刑书宝.限定TN与CSG集成仿真模型生成算法研究[J].计算机应用，2007(2):475－478.

[3] KOZO O，DAISUKE N，MITSURU B.3 － D shape measurement by inverse raytracing approach[C]//SICE Annual Conference.[S.l.]:[s.n.]，2008:1531 －1535.

[4] 郭小凯.光线跟踪及其加速算法的研究[D].西安:西安电子科技大学图书馆，2008.

[5] 杨勋年，汪国昭.三维凸包的快速算法[J].浙江大学学报:自然科学版，1999(2):3－6.

[6] 占春生，蔡勇.一种基于光线相关性的快速光线跟踪算法[J].计算机与现代化，2003(6):4－6.

[7] 刘广忠，黄琳娜.基于二叉树的散乱点集快速凸包算法[J].测绘科学，2008(4):86－88.

[8] FABIANO R，LUIZ V.Hardware－ assisted rending of CSG models[J].Computer Graphics and Image Processing，2006，19(6):139 －146.

[9] WIEGAND T F.Interactive readering of CSG models[J].Computer Graphics Forum，1996，15(4):249 －261.

[10] FLORIAN K，JURGEN D.Rendering techniques for hardware－accelerated image－ based CSG[J].Journal of WSCG，2004，12(2):221 －228.

[11] 崔新友，李东亮.三维模型的布尔运算研究[J].科技信息，2010(15):444－445.