基于八叉树邻域分析光线跟踪的云三维模拟

郑 义，谢永华,2，姬 瑜，朱超凡

(1.南京信息工程大学 计算机与软件学院，江苏 南京 210044；2.南京信息工程大学 江苏省网络监控中心，江苏 南京 210044)

0 引 言

由于云[1]具有不规则的模糊边界、整体不光滑性以及运动的多变性，这些特征使得云很难被计算机模拟，尤其是在云的光照模拟中，光线进入云后具有十分复杂的传播方式，很难用精确的模型去描述。

在计算机上模拟三维云，最重要的是模拟云的真实感，主要过程包括建模和渲染两个方面。在渲染方面，研究者们针对光线的传播过程，提出了多种加速光线与节点求交的方法。Wong等[2]结合八叉树和分层网格结构，提出了八叉树网格，通过减少相位测试的数量来加快碰撞检测，一定程度上提高了运行速度，但是该方法在计算节点的过程中需要进行大量的递归运算，效率依然不高。王皛等[3]通过KD-Tree设计出一种完全流水化的方法，并结合硬件处理的方式提升了光线遍历性的能力，有效地提高了绘制速度，但该方法仍然需要遍历所有的节点，计算量非常的庞大，不适用于大规模三维云场景的模拟。周海英等[4]提出了一种八叉树空间编码邻域搜索方法，该方法通过存储初始节点的空间编码以及层次差来解决不同层次间节点的计算，加快了光线与节点的求交速度，但是该方法在构建八叉树时需要额外一部分存储空间来存储节点与其邻域节点的层次差，降低了存储空间的利用率。袁昱纬等[5]采用八叉树自适应技术，将空白节点自适应的聚集为包围体，减少光线与空白节点的求交次数来提高光线跟踪算法的计算效率，但是该方法只能够处理大规模动态场景中局部更新的问题，并不适用于云三维模拟场景。

针对以上方法的不足，本文提出了基于八叉树邻域分析的光线跟踪算法，并用于天气预报模式(weather research and forecasting，WRF)数值的三维模拟。该方法首先使用八叉树结构优化光线跟踪的数据存储结构，然后通过存储节点编码和划分层次改进邻域分析算法对不同划分层次节点的计算方式，加快光线的求交速度，并对光线折射公式做出改进，简化了光照模型。实验结果表明，该方法能有效提高云图绘制速度和渲染效果，更好展现真实三数据的物理特性。

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

1.1 数据存储结构优化

光线跟踪是一个比光线投射[6]或者扫描线渲染[7]更加逼真的实现方法，其通过反向跟踪所有光线的方式，求出光线与物体的交点，并在交点处累积光线直接照射光强、反射光强以及折射光强，经过叠加色度和不透明度来确定屏幕上所有像素点的颜色，最终达到渲染的目的。但是云粒子的数据量十分庞大，当视点发生改变时，需要重新计算每一条光线，因此无论对于云数据的存储，还是光线的计算，消耗的资源是巨大的。

针对以上不足，本文采用了八叉树结构优化传统光线跟踪算法的数据存储结构，以提高数据存储效率。

首先确定整个云场景的包围盒，公式如下

(1)

然后将包围盒按照八叉树层次结构划分为0、1、2、3、4、5、6、7这8个子节点，如图1所示，再根据需要对子节点递归划分，但逐层划分过程中对应的节点的编码位数会不断的增加。在实验中，当八叉树结构达到最大深度或者达到某个阈值时停止划分。在此基础上，本文算法将光线与云的求交问题转化为光线与八叉树节点求交，如果一条光线与某一个节点没有相交，那么可以直接舍去该节点[8]。这样一来，可以节省大量的数据存储空间，优化光线跟踪算法的数据存储结构。

图1 八叉树划分

1.2 改进的邻域分析算法

八叉树结构划分完成后，光线如何从当前八叉树节点计算出下一个节点是提高光线跟踪算法效率的关键。传统八叉树光线跟踪算法为了存取某一个节点，必须先遍历其余7个节点后才能进行，造成了大量的递归运算，导致了光线跟踪算法效率的降低。张文胜等[9]提出了一种新的邻域分析算法，通过简单的0-1互换，可以从当前节点快速的求出下一节点，加快了光线跟踪的计算速度，但是该方法需要额外的判断节点的层次关系，造成了大量的判断和重新计算。针对以上不足，本文提出了一种改进的邻域分析算法[10]来加快不同划分层次节点间的计算速度，该算法在0-1互换算法的基础上，通过存储节点的编码和划分层次来改变不同层次节点间的计算方式，可从当前节点的编码和射出方向直接计算出下一个节点，避免了大部分的递归运算，极大地提高了计算效率。

首先将0到7这8个子节点划分到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}。假设一条光线入射到节点N，该节点的Morton码为n，n1为节点第一层所处的位置，nk为节点第k层所处的位置，则n=n1n2n3…nk，r为该节点所在的划分层次数，然后将该节点以如下形式存储：(n，r)，则如图2划分后可将节点表示为 {(0，1)，(1，1)，(251，3)，(255，3)，(34，2)，(35，2)，(4，1)，(5，1)，(7，1)}。 最后根据节点N的Morton码和所处的划分层次进行不同的方式计算，由已知的节点和光线的方向可以快速的求出下一节点。

具体步骤为：

(1)提取光线射出节点编码n及所在层次rout，光线射入节点所在层次rin；

(2)当rout≥rin时，从左向右保留n的rin位编码，其余舍去；

1)提取保留后编码的最后一位nk，将其转换成二进制码，即nk=4ax+2ay+az，其中ax、ay、az=0或1；

2)进行0-1互换，假设求X+、X-方向的邻域节点，若ax=1，则ax=0；若ax=0，则ax=1，同理可求出Y和Z方向上的邻域节点；

3)将互换后的二进制码再转回八进制码mk，并替换nk，判断mk是否与nk属于同一个方向集合，若不是，则提取nk的前一位nk-1，转入步骤1)；若是，则计算结束；

(3)当rout

1)求出光线与该射出节点包围盒的交点，判断该交点在所处平面上的位置来添加相应的编码，增加编码的位数为Δr，Δr=rin-rout；

2)进行0-1互换，具体步骤同上。

如图2所示，假设光线从节点“255”的X+方向射出，所求邻域节点与节点“255”处于同一划分层次，即rout=rin，那么提取该节点末位编码“5”转为二进制码“101”，则ax=1，ay=0，az=1，因为求X+方向，所以将ax进行0-1互换，即ax=0，得到二进制码“001”，再转成八进制码得“1”，判断“1”属于X+方向集合，计算结束，得出邻域节点“251”。假设光线从节点“251”的Z-方向射出，由于节点“251”的划分层次rout=3，所求节点的划分层次rin=2，先根据rin=2从左向右保留2位编码得出节点“25”，再根据0-1互换算法求出节点“34”。假设光线从节点“34”的Z+方向射出，rout=2，所求节点划分层次rin=3，那么先根据求出光线与节点“34”包围盒的交点，判断该交点处于该平面的右下方，根据划分规则，在节点“34”末位增加1位编码“0”，得出节点“340”，在根据0-1互换算法计算出下一节点“251”。

图2 光线求交

张文胜等[9]提出的0-1互换算法计算得出的是大小相同的节点，也就是划分层次相同的节点，对于不同层次的节点，就需要经过一系列节点层次关系的判断，其算法步骤如图3(a)所示，而且在提取部分叶子节点的时候需要满足一个条件，在节点编码后加上的标号所属的基准向必须与射出节点的基准向相反，再将所有满足条件的叶子节点提取出来，并逐一判断光线射出的交点是否在叶子节点包围盒的范围内,在这个过程中需要进行大量的判断和递归计算，降低了算法的计算效率。而本文算法通过存储节点编码和划分层次的方式，可直接通过当前节点计算出光线进入的下一节点，解决了不同层次节点间的计算问题，避免了大量由于判断节点不同层次带来的递归运算，其算法步骤如图3(b)所示，最大限度提高了邻域分析算法的计算效率，大大加快了光线与不同层次节点间的求交速度，对大规模三维云渲染速度起到了非常关键的作用。

图3 算法对比

2 云三维模拟

光照模型是生成真实感图形的基础，它根据光学物理定律，计算物体表面任意一点投向观察者眼中的光照强度，通过将光线上采样点的颜色和透明度叠加，形成像素点，最终合成图像。渲染技术的不同，采用的光照模型也不一样，而全局光照模型是最适用光线跟踪算法的光照模型。

2.1 光照模型优化

Whitted[11]光照模型是典型的全局光照模型，该模型在简单光照模型的基础上增加了环境光在镜面反射方向和规则折射方向对被照射点产生的光强，更符合三维云的真实效果，该模型可表示为

I=Ilocal+KsIs+KtIt

(2)

其中，Ilocal为光源的直接反射光，Is和It为环境镜面反射光强和规则折射光强Ks和Kt为反射系数和折射系数，取值均在0～1之间。

在计算折射光强的过程中，折射光线的计算公式为

T=(cosθ2-(η1/η2)cosθ1)N-(η1/η2)d

(3)

其中，θ1和θ2分别表示光线入射角和折射角，η1和η2分别表示入射光线和折射光线所在空间介质的折射率，N和d分别表示单位法向量和入射光线的单位方向向量。

但该折射光线的计算公式过于繁琐，不利于云三维的实时绘制，因此本文在该公式的基础上做出改进，具体步骤如下：

如图4所示，d、R、T分别为入射、反射、折射光线的方向向量，N为单位法向量，那么

T=-N+T1

(4)

R1=d+N

(5)

因为N为单位向量，则

R1/T1=sinθ1/sinθ2=η2/η1

(6)

由式(6)得出

T1=(η1/η2)R1

(7)

将式(5)带入式(7)，可得

T1=(η1/η2)(d+N)

(8)

再将式(8)带入式(4)，得出

T=(η1/η2)(d+N)-N

(9)

运用改进后的光线折射公式，降低了计算复杂度，在大规模三维云实时渲染的过程中有效地提高了绘制速度。

图4 折射光线求解

2.2 渲染流程

三维云的渲染包括预处理和实时处理两个部分，在预处理阶段，利用光线跟踪算法对云粒子进行采样以及插值计算，计算出粒子的光强。在实时处理阶段，通过式(10)计算得出粒子的不透明度和颜色值

(10)

其中，Cnow和αnow表示为当前体素的颜色值和不透明度，Cin和αin表示光线进入当前体素时的颜色值和不透明度，Cout和αout表示光线穿过体素后的颜色值和不透明度，本文实验中设定当α=1时，停止计算。最终将粒子的不透明度和颜色值赋予屏幕像素，合成图像。

3 实验结果

本实验所用的硬件配置是Intel i5-6500，3.20 GHz CPU，8.00 G内存，Nvidia GTX 1060显卡，操作系统为Windows 7。使用的语言为C++，可视化部分使用OpenGL和Vapor辅助完成。实验数据为中尺度天气预报模式WRF v3.3.1模拟数据。模拟区域为：400km×400km范围；水平格距1 km；中心纬度：23°；中心经度：129°；经度范围：127°至131°；纬度范围：21°至25°；垂直层数：50层三维气象数据。

图5为传统八叉树光线跟踪算法和本文算法渲染效果对比图，表1为两种方法绘制所用时间。分析图5和表1可以得出，本文方法有效地改善了锯齿化现象，对光线的明暗效果和云缕的展现都具有明显提升，更好展现了真实数据云的物理特性，同时极大地提高了渲染速度，比传统方法提高了60.4%。

图5 传统八叉树光线跟踪和本文方法渲染效果对比

表1 绘制时间对比

图6为八叉树空间分割技术[12]、KD-Tree方法[3]以及空间均匀网格技术[13]与本文算法的渲染效果对比图，表2为以上方法渲染帧率对比。实验数据为中尺度模式WRF v3.3.2模拟数据，经度范围：106°至110°；纬度范围：30°至34°。分析图6可以看出，八叉树空间剖分整体绘制效果较差，在云的细节上效果不明显。KD-Tree方法对于云整体效果有所改进，但是在云周边出现了锯齿化现象。空间均匀网格锯齿化现象明显，光线的明暗效果较差，而且没有很好展现云缕效果，和本文方法比较起来整体效果不够清晰。分析表2可以得出，本文方法在提高了绘制效果的基础上，有效地减少了绘制时间，平均渲染帧率提高了7.1帧。

4 结束语

本文提出一种八叉树邻域分析的光线跟踪算法并用于三维气象云数据可视化，该方法首先利用八叉树结构优化了光线跟踪算法的数据存储结构，然后改进邻域分析算法，通过存储节点编码和划分层次，改善了不同节点间的计算方式，加快了光线与三维云的求交速度，最终改进了折射光线的计算公式，简化了Whitted光照模型，在算法的实现过程中利用OpenGL和Vapor辅助完成。该方法有效降低了渲染时间，提高了绘制效果和渲染帧率。在以后的研究

图6 各类方法渲染效果对比

表2 渲染帧率对比

工作中，还要考虑以下几个问题，在云边界处，云粒子较少的情况下会产生锯齿化现象，后期将采用球形粒子来改善这种情况。