基于八叉树邻域分析的光线跟踪加速算法

张文胜， 解 骞， 钟 瑾， 刘俊平， 郝 青， 郭广利

（1. 石家庄铁道大学交通运输学院，河北 石家庄 050043；2. 河北省交通安全与控制重点实验室，河北 石家庄 050043；3. 石家庄市中医院放射科，河北 石家庄 050011；4. 河北医科大学第四医院，河北 石家庄 050011）

基于八叉树邻域分析的光线跟踪加速算法

张文胜1,3， 解 骞1,2， 钟 瑾3， 刘俊平3， 郝 青4， 郭广利3

（1. 石家庄铁道大学交通运输学院，河北 石家庄 050043；2. 河北省交通安全与控制重点实验室，河北 石家庄 050043；3. 石家庄市中医院放射科，河北 石家庄 050011；4. 河北医科大学第四医院，河北 石家庄 050011）

八叉树是加速光线跟踪常用的层次划分结构，为加快八叉树跟踪光线的过程，论文研究了运用八叉树邻域分析提高光线与八叉树节点之间的碰撞检测速度的方法，提出了一种结构简单、计算效率更高的八叉树节点的邻域分析算法。运用该算法可由现碰撞节点快速计算出下一碰撞节点，避免了采用大量递归搜索计算，从而提高了图像的渲染速度。实验结果表明，使用论文提出的邻域分析进行碰撞检测，效率比传统算法提高了3倍以上，大大提高了光线跟踪的速度。

光线跟踪；八叉树；邻域分析；加速算法

将三维空间中复杂的三维场景投影到二维空间的视平面一直是计算机图形学的研究热点，其目的是为更加真实的渲染出受到光照、阴影和物体之间的反射光等因素影响的三维环境[1]。视平面上每个像素点的颜色都是由光线在三维空间中经过若干次反射计算得出，跟踪每条光线的路径涉及到大量光线与物体之间的碰撞检测[2]。为加速光线跟踪的计算过程，人们提出了如空间网格法、层次包围法等多种方法[3-4]。八叉树结构是层次包围法主要采用的一种层次划分结构，它将三维空间分成具有一定层次性的空间单元。光线与空间单元进行初步碰撞检测，若空间单元与光线不发生碰撞，则空间单元内的物体不再与光线做进一步碰撞检测，可提高光线跟踪的速度。

在初步检测光线与八叉树的碰撞时，需对八叉树子节点进行遍历，逐一判断子节点是否与光线碰撞。由于图形处理器(graphic processing unit, GPU)无法直接实现递归，限制了图像显示速度[5]。为此，Samet[6-7]提出了基于八叉树邻域分析的光线追踪算法。该算法不再遍历整个树，而是搜索最小公共祖节点找到与光线相交的一系列相邻节点来跟踪光线。虽然该算法避免了搜索整个树，但仍在小范围内自下而上地搜索最小公共祖节点，没能避免递归计算。Schrack[8]和肖乐斌[9]提出八叉树邻域节点的直接算法，通过研究八叉树的位置编码，发现八叉树编码规律与特性，对位置编码加、减常数得出邻域节点的编码。但算法中加减的常数决定于节点的位置和计算方向等因素，涉及到另外一套复杂的计算方法，不能有效地加速光线追踪。Voros[10]研究出了一种矩阵算法，将八叉树的位置编码转化为矩阵，通过矩阵的计算得出邻域节点，但矩阵的计算量会随着矩阵阶数的增加急剧增大，增加了光线跟踪的空间复杂度。Sarah和Ronald[11]采用规则八叉树的记录方式，记下每个节点的父节点、子节点、坐标以及大小，以此计算出八叉树邻域节点。采用坐标计算邻域节点的方法简便直观，但是规则八叉树的储存方式会大大增加节点的存储空间，不利于发挥出八叉树在节省栅格空间上的优势。Yoder和Bloniarz[12]发明了一张八叉树邻域分析表，根据表上的迭代方法，可计算不同方向的邻域节点。这种方法非常实用，但同时受邻域分析表的限制，无法在其基础上改进利用，因此该方法也不适合应用于光线追踪。近几年，关于八叉树邻域分析未有突破性的研究成果，进而在加速光线跟踪方面也没有较大的发展。

本文从光线跟踪出发，提出一种八叉树邻域分析新算法——0-1互换邻域分析算法，只需对0、1编码进行简单的互换，即可得出6个方向的邻域节点。因此，在加速光线跟踪中，只根据光线在当前节点的穿出平面，就可直接计算出下个碰撞节点，最终无需采用搜索算法并能依次找出与光线碰撞的节点。同时在计算过程中高效地利用了三维空间中的坐标系，将0-1互换同三维坐标结合起来，提高了光线跟踪的计算效率。

1 光线跟踪与八叉树

1.1 光线跟踪

如图 1所示，三维渲染中视点接收的每条光线，都是在场景中进行若干次反射，穿过视平面，射入视点。光线跟踪则是沿着光线逆向检测与之发生碰撞的物体，根据光线在物体表面的反射和折射光线确定视平面上像素点的颜色。用这种方法确定出视平面上每一个像素点的颜色，以生成三维场景的渲染图像。

图1 光线跟踪示意图

1.2 八叉树

八叉树是一种三维空间层次结构的划分方案。构造一个能包含全部场景的最小轴对齐立方体，定义为最初根节点。将最初根节点沿轴向等分成8个子节点，将子节点递归等分，当八叉树结构达到最大深度或子节点中包含的物体面片数少于某个预定值时，八叉树层次空间构造结束。一般采用八进制的 Morton码记录划分结束后每个节点的位置，如图2所示，用0、1、2、3、4、5、6、7共8个数字来表示每次分裂后产生8个节点的标号，在逐级分割中，节点编码的位数不断增加[13]。

图2 八叉树划分

1.3 八叉树加速光线跟踪

八叉树结构广泛应用于光线跟踪的加速计算。如图3所示，当光线在场景中行进时，也同时穿过八叉树节点，根据八叉树节点与场景中物体间的组织关系，将光线与物体的碰撞检测简化为先与八叉树节点进行碰撞检测，找到与光线发生碰撞的节点，再与节点内包含的物体进行碰撞检测，能减少与不必要的物体进行碰撞检测。因此，八叉树结构对加快光线与物体之间的碰撞检测具有重要意义。

图3 光线碰撞检测

2 基于邻域分析的光线跟踪算法

2.1 光线跟踪与八叉树邻域分析

虽然使用八叉树能够加速光线跟踪的计算，但在与八叉树节点进行碰撞检测中还是需要遍历整个八叉树，而递归计算是限制图像显示的一个主要因素。为此本文研究了采用八叉树邻域分析进行光线与八叉树节点的碰撞检测。如图3所示，光线穿过的八叉树节点是一系列相邻节点（由节点1到2或由节点3到4再到5），因此采用八叉树邻域分析算法，由初始碰撞节点逐步计算光线所穿过的节点，能避免采用递归计算，进而加速光线追踪的计算。

如图4(a)所示，光线可看做从源点O发出、方向为单位向量d的射线，则光线上任一点P的参数化方程可表示为：P=O+td

图4 光线与八叉树节点碰撞求交

将光线与八叉树的最初根节点求交，光线与最初根节点有两个交点，根据交点的参数值t的大小，可明显看出t值小的为光线与场景的初始碰撞点P0。根据P0点坐标计算出P0所在的叶子节点，即为初始碰撞节点N1。

将光线方程写成函数形式：

其中，(x0, y0, z0)为源点O坐标，(i, j, k)表示光线方向d。

由N1的编码计算出初始碰撞节点所构成的包围盒，用xmin，ymin，zmin，xmax，ymax，zmax表示。令光线方程中x=xmin，x=xmax，y=ymin，y=ymax，z=zmin，z=zmax，求出光线与构造出N1包围盒的6个平面的交点，再采用下面的不等式限制交点坐标在包围盒内：

xmin≤x≤xmax

ymin≤y≤ymax

zmin≤z≤zmax

求出光线与包围盒的两个交点，其中一点与初始碰撞交点P0相同，定义为进盒交点P1，另一点定义为出盒交点 P2，如图 4(b)所示。当光线从 P2穿出后，将进入下一节点，可看出P2是光线跟踪从现节点到下一节点的桥梁。因此，如何不采用遍历搜索方法，由P2直接求出下一碰撞节点是提高光线跟踪效率的关键。P2是 N1所构成的包围盒上的一点，根据P2的坐标和包围盒的参数比较，容易看出P2从包围盒6个方向（X+、X-、Y+、Y-、Z+、Z-）中哪个方向穿出，则下一节点就是 N1在穿出方向上的相邻节点。

本文研究出一种求八叉树相邻节点的新算法——0-1互换算法，将八叉树编码中的八进制数转换成只有0、1的二进制数，只对0、1进行变换即能求出光线穿出方向的下一碰撞节点，规避了递归求交，加速了光线跟踪过程。

2.2 0-1互换邻域分析光线跟踪加速算法

为加速光线跟踪的计算，本文放弃采用传统的遍历方式进行碰撞检测，而是采用八叉树邻域分析，根据光线从现碰撞节点的穿出方向，求出下一碰撞节点。

如图5所示，本文将图2中八叉树的编码分为6个方向，X+={0,1,2,3}，X-={4,5,6,7}，Y+={2,3,6,7}，Y-={0,1,4,5}，Z+={0,2,4,6}，Z-={1,3,5,7}。可以看出，每个方向包含4个编码，每个编码属于3个方向。基准向的划分是0-1互换算法用于光线跟踪，分析各方向相邻节点的基础。

图5 八叉树基准向划分

设跟踪光线到节点N1，其八叉树Morton码为：

u1u2…uk

根据P2在N1包围盒面的方位决定光线的穿出方向，光线跟踪则是要求求出 N1在该方向的邻域节点。N1有6个方向的邻域节点：X+、X-、Y+、Y-、Z+、Z-，为求出不同方向的邻域节点，本文将Morton码中的八进制数转化为二进制编码(bx, by, bz)，二进制码中的bx, by, bz分别赋予图2中所规定的X, Y, Z轴向，对bx, by或bz做0-1互换则求出相应轴向上的邻域节点。

算法具体如下：

(1) 提取出N1节点Morton码的最后一位uk。

(2) 将提取出的八进制标号转化为二进制编码(bx, by, bz)，uk=4bx+2by+bz, bx、by、bz=0或1。

(3) 假设求 X+、X-向的邻域节点，则对 bx做0-1互换：

假若bx=1，则bx=0

如果bx=0，则bx=1

若求Y、Z向的邻域节点，同理对by，bz做0-1互换。

(4) 将互换后的二进制编码再转回八进制数vk，用vk替换掉Morton码中的uk。

(5) 判断vk在X轴上的基准向与邻域分析方向是否相同。若不同，则提取出uk前一位标号uk-1，转入步骤(2)；若相同，则计算结束。

以图6中节点“255”为例：光线从“255”的Z+方向穿出，则要求出 Z+向邻域节点。提取末位编码“5”转化为二进制编码，得出(1,0,1)，将二进制编码中代表 Z轴向的末位数“1”换成“0”，得出(1,0,0)，转回八进制数得“4”，“4”属于Z+向，与分析方向相同，计算结束，得出邻域节点“254”。

图6 光线与八叉树碰撞示意图

使用上述算法，发现计算出的邻域节点与现碰撞节点大小相同，不能完全满足跟踪到下一节点的要求（如图6中“254”节点到“61”节点），需对通过0-1互换计算出的邻域节点进一步处理。

使用0-1互换计算出的邻域节点存在不是光线跟踪的下一节点的可能性，为此采用了如下的处理方法。首先判断计算出的邻域节点是否为八叉树的叶子节点，若是，则说明计算出的邻域节点即为下一碰撞节点。若不是，则再次判断计算出的邻域节点是否为八叉树的枝节点，若不是枝节点，说明八叉树在这一枝上没有分割到计算出的邻域节点的层次，下一节点是计算出的邻域节点的父节点，需逐个减少邻域节点编码的末位标号，判断减少标号后的节点是否为八叉树的叶子节点，直到得出的是叶子节点，即为下一碰撞节点为止。若计算出的邻域节点是八叉树的枝节点，则下一节点是计算出的邻域节点的子节点，提取出邻域节点这一枝下的部分叶子节点，提取的条件是：在邻域节点编码后加上的标号所属的基准向必须与计算邻域节点的方向相反，比如计算的是Z+向的邻域节点，则其编码后所加的标号都属于Z-向{1, 3, 5, 7}，其目的是确保提取出的叶子节点与上一碰撞节点相邻。计算提取出的每个叶子节点所构成包围盒的范围，依次判断穿出交点P2的坐标是否在包围盒内，满足条件的叶子节点即是下一碰撞节点。如图6，假设光线从“61”节点X+向穿出，通过0-1互换计算出的邻域节点是“25”，经过判断“25”是八叉树的枝节点，提取在“25”编码后只加X-向标号{4, 5, 6, 7}的叶子节点：“254”、“255”。判断穿出交点 P2是否在“254”和“255”的范围，确定出下一碰撞节点“254”。

光线跟踪加速算法通过一种简单的邻域分析找出了光线跟踪的下一碰撞节点，该邻域分析算法只对 0、1编码进行互换，即能找出各方向的邻域节点，即避免了递归算法遍历所有节点，又没有采用复杂的邻域分析算法增加碰撞检测的复杂度，最大限度地提高了光线跟踪的速度。

3 实验结果

运用OPENGL对上述算法进行了实现，跟踪了场景中的某条光线，并采用0-1互换算法提取出与碰撞的八叉树叶子节点。图7(a)是导入初始三维场景，根据场景的大小构造出初始包围盒，作为八叉树根节点；图 7(b)是将导入的三维场景采用层次分割成了八叉树结构，图中每个包围盒是一个八叉树叶子节点；图7(c)导入光线，穿过三维场景；图7(d)采用0-1互换算法提取出与光线碰撞的八叉树节点。

图8为测试算法跟踪光线的效率，本文采用了Samet算法、Schrack算法和0-1互换3种不同算法，在不同场景中进行了光线与八叉树叶子节点的碰撞检测实验。从表1中测试统计数据可以看出0-1互换算法比 Samet算法的效率高出十多倍，并且Samet算法由于是一种类搜索算法，其碰撞检测的耗时会随着八叉树节点的增加而增加，而0-1互换算法没有；由于0-1互换算法不涉及复杂的计算过程，在实验场景中的耗时与Schrack算法相比，效率最小，提高了3.97倍，最大提高了6.12倍，多数场景中效率提高了4～5倍。

图7 使用0-1互换邻域分析的碰撞检测图

图8 效率比较的实验场景

表1 不同算法效率比较

4 结 论

八叉树作为加速光线跟踪主要采用的一种层次划分结构，是光线跟踪加速算法的重要研究方向。本文采用邻域分析直接计算碰撞节点，避免了使用递归方法遍历整个八叉树，加快了碰撞检测的速度。提出了八叉树邻域分析的新算法：0-1互换邻域分析算法，简化了邻域分析的计算步骤，极大增强了八叉树邻域分析在加速光线跟踪中的效率与作用。

[1] Suffer K. 光线跟踪算法技术[M]. 刘天慧, 译. 北京:清华大学出版社, 2011: 1-3.

[2] Cosson B, Schmidt F, Maoult Y L, et al. Infrared heating stage simulation of semi-transparent media (PET) using ray tracing method [J]. International Journal of Material Forming, 2011, 4(1): 1-10.

[3] 李 静, 王文成, 吴恩华. 基于空盒自适应生成的动态场景光线跟踪计算[J]. 计算机学报, 2009, 32(6): 1172-1182.

[4] 蔡 鹏, 尹宝才, 孔德慧. 基于最近离散点的光线跟踪[J]. 图学学报, 2013, 34(3): 1-6.

[5] Gunther J, Friedrich H, Seidel H. Interactive ray tracing of skinned animations [J]. Visual Computer, 2006, 22(9-11): 785-792.

[6] Samet H. Neighbor finding in image represented by octrees [J]. Computer Graphics and Image Processing, 1989, 46(3): 367-386.

[7] Samet H. Implementing ray tracing with octrees and neighbor finding [J]. Computers & Graphics, 1989, 13(4): 445-460.

[8] Schrack G. Finding neighbors of equal size in linear quadtrees and octrees in constant time [J]. CVGIP: Image Understanding, 1992, 55(3): 221-230.

[9] 肖乐斌. 基于栅格框架的三维GIS集成数据模型与空间分析研究[D]. 北京: 中国科学院地理研究所, 1999.

[10] Voros J. A strategy for repetitive neighbor finding in octree representations [J]. Image and Vision Computing, 2000, 18(14): 1085-1091.

[11] Sarah F F, Ronald N P. Simple and efficient traversal methods for quadtrees and octrees [J]. Journal of Graphics Tools, 2002, 7(3): 1-11.

[12] Yoder R, Bloniarz P A. A practical algorithm for computing neighbors in quadtrees, octrees, and hyperoctrees [C]//Proceedings of the 2006 International Conference on, Lasvegas, Nevada, USA, 2006: 249-255.

[13] Armin H, Kal M W, Maren B, et al. OctoMap: an efficient probabilistic 3D mapping framework based on octrees [J]. Auton Robot, 2013, 34(3): 189-206.

Acceleration Algorithm in Ray Tracing by the Octree Neighbor Finding

Zhang Wensheng1,3, Xie Qian1,2, Zhong Jin3, Liu Junping3, Hao Qing4, Guo Guangli3

(1.Shijiazhuang Tiedao University Transportation Institute, Shijiazhuang Hebei 050043, China; 2. Traffic Safety and Control Key Laboratory of Hebei Province, Shijiazhuang Hebei 050043, China; 3. Radiology Department of Shijiazhuang Hospital of TCM, Shijiazhuang Hebei 050011, China; 4. The Fourth Hospital of Hebei Medical University, Shijiazhuang Hebei 050011, China)

Octree is a kind of hierarchy structure, and is often used to accelerate ray tracing. In order to speed up the process of ray tracing, a method which used octree neighbor finding to improve the speed of collision detection between ray and octree nodes is provided. This method proposes a octree neighbor finding algorithm which has simple structure and high computational efficiency. Using this algorithm, the next collision node can be calculated by current collision node quickly, which improves the image rendering speed. The experimental results show that the efficiency increased at least 3 times if the collision detection using the neighbor finding rather than the traditional algorithm, and the proposed algorithm can greatly accelerate the ray tracing.

ray tracing; octree; neighbor finding; acceleration algorithm

TP 391

A

2095-302X(2015)03-0339-06

2014-08-14；定稿日期：2014-11-14

国家自然科学基金资助项目(51308358)；河北省交通厅科研计划资助项目(J-20130438)；石家庄市科技支撑计划资助项目(141462353, 133130074A，157130036A)

张文胜(1971-)，男，宁夏隆德人，教授，博士。主要研究方向为信息技术研究。E-mail：zws163@163.com