摘要
作为天气系统的主要组成部分,三维云仿真在军事、航空等领域都起着重要作用．目前主流的边界体积层次结构(Bounding Volume Hierarchy,BVH)在处理形状不均匀且体积较大的云时存在渲染效率低下的问题,为此提出一种基于优化BVH算法的云产品渲染方法．将WRF(Weather Research and Forecasting,天气研究与预报)模型网格点中的数据作为云基元,利用Z-order Hilbert曲线对其进行空间排序,结合云基元密度优化BVH算法,提高计算效率．提出ONS (Overlapping Node Sets,重叠节点结构)降低数据存取耗时．优化BVH算法能够减少不必要的光线和三角形面之间的相交测试次数,并解决边界体无效重叠问题．仿真实验显示,SAH(Surface Area Heuristic,表面积启发式)成本较同类最优算法可提升15.6%,EPO(Effective Partial Overlap,有效重叠部分)可提升10%,构建时间减少100%以上,在任意云场景中优化BVH算法的计算效率较同类算法都有显著提高,表明其能实现WRF云产品的快速渲染．
Abstract
As a crucial component of weather systems,3D cloud simulation plays a significant role in various fields such as military and aviation.However,the current mainstream Bounding Volume Hierarchy (BVH) algorithm exhibits inefficient rendering performance when dealing with non-uniform and large-volume clouds.Here,a cloud rendering approach based on optimized BVH algorithm is proposed.The data points from the WRF（Weather Research and Forecasting） grids are used as cloud primitives,and a Z-order Hilbert curve is employed for spatial sorting.The BVH algorithm based on the Surface Area Heuristic (SAH) is optimized by locally optimizing the cloud primitive density,aiming to enhance computational efficiency.To tackle the data access overhead of overlapping BVH nodes,a novel storage structure called Overlapping Node Sets (ONS) is introduced,which reduces the time complexity.The optimized BVH algorithm reduces unnecessary intersection tests between rays and triangle surfaces,and resolves issues related to invalid boundary volume overlaps.Simulation experiments demonstrate that the proposed method achieves a 15.6% improvement in SAH cost compared to similar state-of-the-art algorithms,a 10% improvement in EPO(Effective Partial Overlap),and a reduction of over 100% in construction time.The computational efficiency of the optimized BVH algorithm outperforms similar algorithms in any WRF cloud scenario,indicating its capability for rapid rendering of WRF cloud products.
0 引言
随着计算机硬件的迅猛发展，复杂多变的自然天气的真实高效视景仿真得以实现．云在地球气候系统中扮演着重要角色[1-2]，而云仿真则为人们深入理解云的影响及提升对气候系统的认识水平提供了重要帮助．此外，云仿真还能研究气候变化对云的影响，对评估和预测全球气候变化至关重要[3]．在航空安全方面，准确模拟云的形态和运动可为航空活动提供合理规划和决策的依据，确保飞行的安全和效率．
云仿真是计算机图形学中的重要研究领域之一，主要涵盖建模和渲染两个步骤，目前主流的建模方法包括粒子系统、数字模拟和体绘制等．Xie等[4]提出优化粒子系统完成云建模，从而减少计算量; Tong等[5]提出一种元胞自动机方法实现云建模，提高云真实感; 刘保权等[6]提出一种基于多分辨率的体绘制方法进行云的建模仿真，大大地减少了计算量．当前建模技术得到了长足的发展，基本满足仿真需求，但渲染方面还面临着渲染效果和渲染性能无法兼顾的问题．
光线追踪具有真实感强、适应复杂场景等优点[7-8]，近年来被广泛使用在云渲染领域．传统光线追踪算法使用表面交点估计法计算光线与物体表面的交点，并根据交点信息计算光线与场景中物体的相交关系．然而，对于复杂的云场景，传统光线追踪算法存在渲染时间长和效果不佳等问题[9]，因此需要优化光线追踪性能．空间分割算法在光线追踪领域是一种常用的优化方法，主要原理是将场景划分为多个子空间，仅在光线相交的子空间中进行相交计算，减少计算量．统一网格、八叉树和KD树都是基于空间划分的加速结构，NVIDIA（英伟达）提供的统一网格加速结构将整个空间划分为大小相同的子空间，这种做法会使得在处理体积大且不均匀的云场景时会出现某些子空间中包含大量对象而另外一些子空间没有对象的情况，导致性能下降．虽然一些研究者对八叉树进行了优化[10-11]，但在处理体积大且不均匀分布的云场景时，仍会出现分割不完全的无效重叠问题，导致建树的时间和内存占用高，影响总体性能．王皛等[12]提出一种全流水线化光线追踪KD树遍历单元硬件架构，该架构利用硬件提升性能，但当云形状发生变化时计算量依然庞大．当云的形状发生变化时，以上基于空间划分的加速结构每帧都需要重新构建，带来巨大开销．
BVH（Bounding Volume Hierarchy，边界体积层次结构）由于其基于对象划分的特点，当云形状开始变化时只需要更新包围盒信息而无需重新构建，可以弥补上述算法的缺陷．然而在处理云基元分布不均匀的情况时，目前主流的BVH算法效率低下，主要原因是相同的云基元可能被划分到不同的子空间，导致交叉测试过程中多次引用不同子空间中的相同云基元，降低计算效率．为此，Goldsmith等[13]提出一种广泛使用的表面启发式算法，并基于该算法对BVH构造进行优化，但优化后的算法在SAH（Surface Area Heuristic，表面积启发式）成本方面表现不理想．Ernst等[14]提出一种BVH的分割裁剪算法，该算法放宽了每个BVH叶节点中只能存储一个原语的限制，成功减少了树的深度但加重了节点的重叠，依然存在性能浪费．Dammertz等[15]提出一种边缘体积启发式算法来减少节点之间的重叠，但在处理分布不均匀的云场景时并没有明显提升．Wu等[16]提出一种基于BVH划分的分治射线追踪算法，该算法解决了空间划分方案中包围盒不能紧紧包围基元的问题，减少了子空间中的不必要射线，但该方法不适合应用在大体积场景中．Kulkarni等[17]提出将BVH融合到细节网格中，提高被渲染物体的真实感，但在性能方面表现一般．
本文算法将云基元密度与SAH结合，优化BVH树的构建策略，以最大限度地减少空间重叠，提高渲染效率．首先对WRF数据进行预处理，获得云渲染所需数据．采用基于Z-order Hilbert曲线的空间排序方法对云基元进行排序并在该曲线上计算云基元局部密度．在Z-order Hilbert曲线上快速搜索每个簇的最近簇和子最近簇，实现并行合并和删除操作．根据局部密度最小化SAH成本，调整BVH构建策略，提高整体性能．本文针对BVH空间重叠节点存取性能低效问题，提出ONS（Overlapping Node Sets）节点存储结构．该结构解决了BVH左右节点的空间重叠而引起的遍历资源浪费问题，提高了遍历速率．本文提出的基于优化BVH算法的云产品渲染方法，能有效地解决目前BVH算法处理形状不均匀且体积较大的云场景时性能低下的问题．
1 数据和方法
1.1 WRF云产品
WRF是一种气象模型，通过数学公式对大气物理过程建模，能够准确模拟和预测天气现象．云通常由冰晶和水滴等组成，本文在进行云三维渲染时，选择云冰混合比和云水混合比作为WRF初始数据，用以描述冰晶和水滴在云中的相对含量．由于冰晶和水滴对光的散射和吸收特性不同，需对数据进行预处理．预处理后添加适当的着色和光照效果，得到真实感和立体感都极强的三维渲染效果．
本文通过分析云冰混合比和云水混合比确定云基元密度，得出三维云模型中体数据间的接近程度．由于冰晶和水滴对光线的折射率不同，需要综合考虑它们的影响．采用式（1）对初始数据进行混合处理:
(1)
其中:Qice表示云冰混合比; Qwater表示云水混合比; a，b分别表示云冰混合比、云水混合比的折射率．对于云水混合比或者云冰混合比小于阈值的体数据进行去除处理，从而减少需要处理的数据量．
1.2 BVH结构
BVH结构是一种在计算机图形学和碰撞检测领域广泛应用的高效数据结构，其主要目的是加速光线追踪和空间查询等关键计算任务．它通过将场景中的对象或几何体分割成分层树状结构，实现对数据的有效访问和查询．在BVH结构中，每个节点代表一个边界体积，通常由简单的形状（如轴对齐边界框或球体）组成，以包围所代表的对象或几何体．初始状态下，所有对象都被包含在表示层次结构根节点的单个边界体积中．通过递归地分割根节点中包含的对象或几何体，BVH结构将其细分为更小的边界体积．该细分过程一直进行，直到满足终止条件，例如达到每个节点的最大深度或最小对象数．使用BVH结构能将光线追踪算法的时间复杂度从o（n）降为o（log n）.BVH结构的设计和构建过程可以根据具体的应用场景进行调整，以平衡空间占用和查询效率，BVH实现过程如图1所示，其中，A1~A8表示基元，N1~N8表示包围盒．
图1BVH实现过程示意图
Fig.1Schematic diagram of the implementation process of BVH
1.3 总体架构
目前主流的BVH算法在渲染体积庞大且不均匀的云场景时存在限制．主要原因是过度的空间重叠导致边界框间的重叠区域增多，需要对两个树节点进行交叉测试，增加了遍历和交叉测试成本．为此，本文提出一种基于优化BVH算法的云产品渲染方法，该方法通过分析云基元密度与构建速度之间的关系，最小化SAH成本，确保BVH的构建效率．
本文总体架构主要由空间排序模块、密度计算模块、簇结合模块、ONS存储模块组成．将经过预处理后的WRF数据输入到空间排序模块中，采用基于Z-order Hilbert 曲线的方法对其进行空间排序，将三维空间中的云基元排列成有序的二维集合，提高空间数据的存取效率．在密度计算模块中，为减少密度计算成本，引入搜索半径的概念，在Z-order Hilbert曲线上进行局部搜索，得到云基元的局部密度并近似替代全局密度，根据云密度最小化SAH成本．簇结合模块使用聚类的方式构建BVH，选取k个密度最大的基元作为簇群中心，在Z-order Hilbert曲线上计算每个簇的最近簇和次最近簇，并按照簇最近结合原则进行结合，得到高效的BVH树．ONS存储模块提出一种新的重叠节点存储结构，通过光线求交得到空间重叠节点，并将其存入ONS存储结构中，解决当BVH树的左右节点出现空间重叠时的资源浪费问题．完成上述步骤后，递归的对子空间进行左右子树的分割，直至子树的叶节点数量达到阈值后将左右子树连接起来作为父节点的两个子节点，并更新父节点的包围盒，直到所有的叶节点都被分割为止，则BVH构建完成．算法总流程如图2所示．
1.4 空间排序模块
传统的基元密度计算方法的时间复杂度（o（n2），n 代表基元数量）较高，在基元数量较大时，会出现渲染效率低下问题．为此，本文提出一种基于Z-order Hilbert 曲线的空间排序方法．该方法通过计算每个基元的Morton编码将三维空间中的基元排序成二维的有序基元集合，该集合按照Hilbert曲线连接，保证其局部连续性．在此基础上进行的密度计算可以极大地减少基元密度计算成本．
Z-order Hilbert曲线通过重新排序Morton编码的二进制位生成，结合了Morton编码和Hilbert曲线的特点．该曲线特征是利用Morton曲线生成多维网格，并使用Hilbert曲线遍历网格以实现紧凑性和局部连续性．对三维空间中的基元进行排序，能确保曲线上的基元在局部按照三维空间的顺序存储．这种基元排序方式为后续的局部密度计算提供便利．
Morton编码的基本思想是交替排列多维坐标的二进制位，形成一维整数．例如，对于二维坐标（2，5），其二进制为 010和101，将它们交替排列得到011001．Morton编码还具有优异的空间局部性，即相邻坐标的Morton编码在二进制中也是相邻的，CPU缓存机制利用该特点来加速空间数据的访问和处理．
本节提出的基元Z-order Hilbert 曲线的空间排序方法能够实现对空间数据的快速查找和排序，更高效地对三维场景中的基元进行空间排序、存储和处理，降低数据的存取成本．
图3展示了二维Hilbert曲线的生成方式，将二维空间划分为一系列的正方形，在Hilbert 曲线上对这些正方形进行遍历．使用Hilbert 曲线时，从一个正方形到相邻的正方形只需要在曲线上移动几个位置，保持了局部连续性．图4展示了云基元在Z-order Hilbert 曲线上的分布，所有基元按照曲线特性形成有序的二维基元集合．
图2算法总流程
Fig.2Overall flow chart of the proposed algorithm
图3二维空间中的Hilbert曲线
Fig.3Hilbert curve in two-dimensional space
图4基元的空间排序
Fig.4Spatial sorting map of primitives
1.5 密度计算模块
为了降低密度计算的时间成本，本模块运用局部搜索策略对Z-order Hilbert 曲线上的二维有序基元集合进行高效的密度计算，以代替运算量庞大的全局密度计算．基元集合经过空间排序后表示为L={L1，L2，L3，···，Ln}，在三维空间中创建一个球体，以某一基元为球体中心，选定合适的搜索半径r，则密度的定义为:对于任何原始Li，i∈n，以Li为球体中心且半径为r 的球体中包含的其他基元的数量．密度pi定义如式（2）、式（3）所示:
(2)
(3)
其中:dist（Li，Lj）代表Li，Lj间的欧式距离; pi代表原始Li的密度，其定义如图5所示．
图5密度定义
Fig.5Density definition map
图5中:蓝色三角形表示基元，三角形大小表示基元大小，位置与WRF网格格点对应; 白色球体表示半径为r 的搜索范围; 橙色三角形表示中心基元．为避免密度计算量过大，本文采用局部搜索策略，在二维空间中进行局部搜索，并将得到的局部密度近似替代全局密度，如图6所示．图6中:橙色三角形代表中心基元，以橙色三角形为中心搜索半径为r 的搜索范围内包含的基元标记为绿色三角形，而未被搜索到的基元则标记为灰色三角形．
图6基元密度搜索
Fig.6Primitive density search graph
例如，对于索引为i的基元Li，其局部搜索范围为（i-r，i+r），近似代表图5中的白色球体的搜索范围．通过局部密度计算公式计算原始Li的局部密度，如式（4）、式（5）所示:
(4)
(5)
其中:pi代表原始Li的局部密度; dist（Li，Lj）是Li，Lj间的欧式距离．式（4）用来判断在（i-r，i+r）范围内的其他基元与Li的距离是否大于搜索半径．由于基元都分布在WRF网格格点上，基元之间的欧式距离可用格点位置计算，这样计算出的距离能反映三维空间中基元的真实位置关系．通过上述的基元局部密度计算方法能极大地减少计算量，降低时间成本．
由于Z-order Hilbert 曲线的构造方式和细分规则的特性，基于该曲线的基元排序并不是完全有序和相邻的．因此，局部密度无法完全代表基元的全局密度，从而出现资源浪费和云渲染效果失真的问题．为了保证局部密度的使用质量，本文在实验中计算了不同搜索半径下全局密度与局部密度之间的相对误差．相对误差的计算可评估局部密度的准确性，并确保其稳定性和可靠性，保证云场景渲染工作的效果．
相对误差ER 的计算公式:
(6)
其中:n 是基元的总数．当搜索半径r=ρ时，r表示基元Li的局部密度; 当r=n时，计算的值是遍历所有基元得到的密度．
本文对5种云场景进行相对误差实验，其中:Cloud1表示海雾天气下的积云、Cloud2表示热带气旋天气下的积云、Cloud3表示海雾天气下的积雨云、Cloud4表示热带气旋天气下的积雨云、Cloud5表示雷暴天气下的积雨云．实验结果如表1所示.
从表1中可以观察到，当搜索半径r 增大时，误差减小．但当搜索半径达到一定阈值时，误差变化较小，且会显著增加计算量．经过分析，在本文实验中选择搜索半径值r=50，即可在保证算法效率的同时，也保证局部密度的准确性．
表1局部密度和密度之间的相对误差
Table1Relative error between local density and density
1.6 簇结合模块
本文使用基于聚类的方法构建BVH，但传统方法中计算簇与其他簇之间的距离存在巨大时间成本．为此，本文提出一种基于Z-order Hilbert 曲线的优化方法．在Z-order Hilbert曲线上将场景空间划分为多个子空间并进行搜索，仅计算簇i 和范围（i-r，i+r）中的其他簇的距离，作为最近簇和次最近簇的候选．如果簇A的最近簇是簇B，且簇B的最近簇也是簇A，则互为最近簇; 如果簇A的次最近簇是簇B，且簇B的最近簇是簇A，则B是A的次最近簇．由于Z-order Hilbert 曲线上的基元是局部有序的，可以极大地减少簇之间距离的计算时间，确定每个簇的最近簇和次最近簇后根据簇最近结合算法，以初始簇群中心为中心对其他簇进行合并，这种方法能够有效降低时间成本．簇结合算法如图7所示．
图7簇结合算法
Fig.7Cluster combination algorithm
在图7中，簇a和簇b是对方的最近簇，故簇a和簇b互为最近簇．此外，图中簇f和簇g的距离小于簇g和簇h的距离，而簇h的最近簇为g，故簇h为簇g的次最近簇．
簇结合算法的基本思想是在每次迭代中，如果两个节点互为最近簇群，它们将被合并．如果一个簇群没有最近的簇群，则继续搜索次最近的簇群，并将其与下一级簇群合并．在簇群合并操作后，执行扫描操作以消除簇群在Morton曲线上产生的间隙，保持曲线的紧凑性，并快速删除无效的簇群．
SAH算法通过估计光线与边界体积的表面积来判断光线是否与边界相交．由于光线的范围和强度是有限的，一旦光线与边界相交并从另一边的边界射出，就需要在BVH中执行光线的求交、折射等操作，而这些操作与基元密度密切相关．因此，本文在保证BVH紧凑的前提下，将计算得到的云基元密度与SAH相结合，最小化SAH成本并为基元密度更高的BVH分配更多的资源，以实现更合理的资源分配．结合后的SAH成本公式如式（7）所示:
(7)
其中:m 为基元密度; α是边界体积表面积与基元密度间的权重系数，值范围为[0，1]; S（A）和S（B）分别表示左侧和右侧节点边界体积A 和B 的表面积; S（C）表示父节点边界体积C 的表面积; CBVH表示BVH树构建成本; ti表示相交成本; kA和kB分别表示边界体积A 和B 中三角形面的数量，两个簇之间的距离被视为包含它们的边界框的表面积．将簇结合算法和SAH算法相结合，能对密度大的基元分配更多的资源，并总体上降低总SAH成本，提高效率.
1.7 ONS存储结构模块
在构造BVH时，基元密度越大，与周围基元的重叠部分就越多，遍历时间的开销将相应增加，因此，基元密度与射线穿过原始体的速度密切相关，在云场景渲染实验中也佐证了这一结论．实验结果表明，基元密度大的基元与其他基元相比，其边界框与周围基元的边界框重叠程度更高，且在构造的BVH中，密度大的基元不仅会影响同一级别的边界框的遍历结果，还影响从根节点到该原始节点的所有节点，这极大地增加了遍历步骤和基元交集的计算开销．为此，本文提出一种ONS节点存储结构，每次迭代时BVH重叠的左右节点被存入该节点存储结构的链表中，以便在遍历过程中能够快速识别和访问这些节点，从而提高重叠节点的存取效率，并减少由于节点重叠而引起的资源浪费．ONS存储结构如图8所示．
图8中:Q1~Qn为存储光源样本，它们均有两个指针节点P1、P2，P1指向list1存储节点的光路，P2指向list2存储节点的光路交点．当光路发生变化时，list1与list2同时更新，确保它们始终保持同步．将与光线有交点的BVH左右边界节点分别存入L1，···，Ln、R1，···，Rn链表中，并最终存至L1R1，···，LnRn链表形成一一对应关系，通过ONS节点存储结构可将查找重叠节点时的时间复杂度从o（n3）降低为o（n2log n），使得重叠节点的查找和访问变得高效，减少不必要的计算和资源浪费．同时，保证光路信息与光路交点在链表中的一致性，确保了正确的渲染结果．
2 实验
2.1 实验设置与实验方案
本文使用的实验设备的处理器为Intel（R）Core（TM）i9-10900X，内存为32 GB，GPU为NVIDIA GeForce GTX 3090Ti，操作系统为Ubuntu18.04．本实验选取热带气旋、雷暴、海雾等天气下的不同三维云数据作为初始WRF数据，它们分别代表不同的云类型．在WRF数据集中，本文选取云冰混合比和云水混合比作为初始数值．通过对这两个参数的模拟和分析，能更好地帮助我们理解热带气旋、暴雨、雷暴等气象事件中云的形成和演化过程．
图8ONS存储结构
Fig.8ONS storage structure
以不同天气条件下的5组WRF三维云数据为本实验初始数据集，其中:Cloud1代表海雾天气下的积云、Cloud2代表热带气旋天气下的积云、Cloud3代表海雾天气下的积雨云、Cloud4代表热带气旋天气下的积雨云、Cloud5代表雷暴天气下的积雨云．分别进行以下3种实验:消融实验、云仿真效率对比实验、云仿真视觉效果对比实验．通过比较SAH成本、EPO、构建时间、每秒射线数和视觉效果等评估标准，对实验结果进行综合评估．
2.2 评估指标
本文针对不同天气下的5组不同云三维数据模型进行实验．由于SAH成本函数只能近似预测整个加速结构中射线遍历的成本，而无法精确预测单个射线的遍历成本，所以，为了更加准确地评估构建结果的质量，本文使用多种度量标准，包括BVH构建时间、SAH成本、EPO、每秒射线数、视觉效果等，以更好地分析和比较实验数据．
1）SAH成本
SAH成本是一个用于衡量射线遍历整个加速结构的近似预期成本的指标，如式（7）所示，当SAH成本越小时代表该BVH的性能越好．
2) EPO
EPO是BVH的重叠度量[18]，如式（8）所示:
(8)
其中:n 是BVH中的某一节点; Q（n）是该节点的兄弟节点;（n\Q（n））∩n表示不属于n 但与之重叠的集合; A（）是相应的体积．EPO指标越小，BVH性能越好．
3）BVH构建时间
BVH构建时间是测量BVH性能的最直观指标，能直接反映BVH的性能．BVH构建时间越短，性能越好．
4）每秒射线数
每秒射线数是每秒BVH构建的兆射线数，是计算机图形学中衡量性能的一种指标．每秒射线数越高，计算速度越快．
5）视觉效果
视觉效果作为判断渲染质量的关键指标，在计算机图形学领域中扮演着重要的角色，根据渲染出的视觉效果可以直观地反映出各种方法的优缺点．
2.3 实验结果
2.3.1 消融实验
为验证密度计算模块和ONS模块对云仿真性能和效果的提升作用，本消融实验在5个不同三维云场景中将本文算法与去除密度计算模块后结合ONS的BVH构建算法（ONS-BVH）及去除ONS模块后结合空间排序的BVH构建算法（空间排序-BVH）分别进行消融实验．以SAH成本、EPO、BVH构建时间、每秒射线数、视觉效果等评估指标对比，本文算法与消融算法的具体区别如表2所示．
表2本文算法与两种消融算法对比
Table2Comparison between the proposed algorithm and two ablation algorithms
ONS-BVH算法相比本文算法缺少密度计算模块，其主要流程为对基元进行空间排序后根据排序结果进行簇结合，完成BVH树构建工作并将重叠节点存储入ONS模块，跳过密度计算模块．将本文算法与其进行视觉效果对比，结果如图9所示．
图9本文算法与ONS-BVH算法视觉效果对比
Fig.9Visual effect comparison between the proposed algorithm and ONS-BVH algorithm
本文实验中将初始数值大的区域着色为黑色，数值越大黑色越深，体现积雨云的特征．从图9中可以观察到，在5个云场景中，ONS-BVH算法在云朵间的连接区域的细节处理上表现不如本文算法．尤其在Cloud4和Cloud5这2个复杂云场景中，云之间的连接部分缺乏部分细节．这是由于其未进行密度计算，导致在簇结合过程中未以密度最大的基元作为簇群中心，且对处于簇群边缘的次最近簇无法进行结合，使得云连接部分的一些数据无法在渲染结果中准确体现，影响整体的真实感和细节感．
将本文算法与ONS-BVH算法进行云渲染效率对比，实验结果如表3所示．
表3中可以观察到，本文算法相较于ONS-BVH算法，在多个评估指标上均表现出了优势．1）SAH成本．本文算法相比ONS-BVH算法，在简单的云场景如Cloud1、Cloud2中，SAH成本的减少量在分别为16、33，而在复杂的云场景如Cloud3、Cloud4、Cloud5中，SAH成本减少量进一步增加，分别为45、57、60．随着场景复杂性的增加，本文算法对SAH成本的提升越明显．2）EPO．本文算法相较于ONS-BVH算法，Cloud1~Cloud5场景下EPO的提升幅度分别为38.3%、38.0%、38.8%、42.1%和55.4%．随着场景复杂程度的增加，本文算法对EPO的提升幅度呈现上升趋势．3）构建时间．在Cloud1~Cloud5场景中，本文算法相比ONS-BVH算法，减少的构建时间为1.78~12.74 ms．4）每秒射线数．本文算法相比ONS-BVH算法在5个云场景中都略有提升．
综合以上实验结果可知:随着云场景复杂程度的增加，本文算法相较于消融了密度计算模块算法的优势愈发明显，性能提升更为显著，表明本文算法在处理任何云场景时都更加灵活高效．
为验证本文算法中ONS模块对仿真性能的提升效果，将缺失ONS模块的结合空间排序的BVH构建算法（空间排序-BVH）与本文算法进行对比实验．由于ONS模块主要功能为存储BVH构建时重叠的左右空间节点，影响的指标为BVH构建时间，所以本消融实验只对该指标进行仿真效率的实验对比，表4展示了本文算法和空间排序-BVH算法的对比情况．
表3本文算法与ONS-BVH算法的指标对比
Table3Indicator comparison between the proposed algorithm and ONS-BVH algorithm
表4本文算法与空间排序-BVH算法的构建时间对比情况
Table4Construction time comparison between the proposed algorithm and BVH algorithm combined with spatial sorting
从表4中可以观察到，在BVH构建时间指标上，本文算法相比于空间排序-BVH算法在5个云场景中均有大幅提升，且随着场景的复杂程度增加，本文算法的提升幅度整体呈现上升趋势．在越复杂的场景中，BVH树的节点重叠情况更为复杂，查询重叠节点所需的级别也会更高．缺失了ONS模块的消融算法处理复杂情况时效率低下，导致在查询和处理重叠节点时浪费了大量的计算资源，从而造成构建时间的显著增加．
2.3.2 云仿真效率对比实验
本实验旨在对5个不同的三维云场景进行仿真效率对比，以验证本文提出的算法在渲染不均匀且体积庞大的云场景时的性能优势．为此，将本文算法与经过优化后的LBVH[19]、HLBVH[20]和K-means[21]三种BVH构建算法进行实验对比，以SAH成本、EPO、BVH构建时间和每秒射线数为评估指标．表5展示了以上4种算法在5个云场景中的指标对比情况．
表5评估指标对比
Table5Evaluation index comparison
从表5中可以观察到:1）本文算法的SAH成本在所有场景中表现都是最好的，这表明，在考虑云基元模型的情况下，将云基元密度与SAH结合，实现了SAH成本的最小化，并给予了基元密度大的基元更多的资源，使得本文算法在SAH成本上表现好于其他算法; 2）本文算法的EPO相比HLBVH算法在5个云场景中均有小幅提升，而相比其他2种经典算法均有大幅提升，这表明根据云基元模型进行BVH构建可以极大地减少空间重叠和重叠节点，提高运算效率; 3）本文算法的构建时间均远远小于其他经典算法，且随着场景复杂度的增加，构建时间的提升效果也越大，这表明，本文算法可以极大地减少光线与物体的求交次数，减少空间重叠部分，从而完成对BVH的性能优化; 4）本文算法在每秒射线数评估指标上表现最好，HLBVH表现次之，LBVH表现最差，表明本文算法的光线追踪算法性能表现最好．
2.3.3 云仿真视觉效果对比实验
通过对比本文算法与优化后的LBVH、HLBVH、K-means算法在5组不同三维云场景中的视觉效果，来验证本文算法在实现性能大幅提升的同时，也能保证云的视觉效果．视觉效果对比结果如图10所示．
从图10中可以观察到:K-means算法渲染出的云场景与本文算法相比，整体视觉效果相仿但云边缘显得更绵长，边界感略差; LBVH算法所渲染的云场景与本文算法相比，云之间的层次感展现得不够明显; HLBVH算法所渲染的云场景与本文最为相似，都很好地展现出云的形状和特征．因此，本文以聚类的方式进行BVH构建并以基元密度大的基元为中心，可以很好地呈现出云的层次感，边缘的不同基元也会被不同簇群结合，边缘细节感表现得更强，能真实地呈现出云在不同天气下的视觉效果．
3 结论
本文提出一种基于优化后BVH算法的云渲染加速方法，建立云基元密度模型，以此为基础优化SAH，达到提高BVH性能的目的．对5组天气不同的三维云模型进行实验分析，得到以下结论:
1）基于优化后BVH算法的云渲染加速方法如果去除密度计算模块，会导致渲染性能下降，视觉效果也会受到影响．如果去除ONS存储结构模块，重叠节点的资源浪费问题不能得到解决，BVH构建时间会大大提高．
图10本文算法与K-means、LBVH、HLBVH算法视觉对比
Fig.10Visual comparison between the proposed algorithm and K-means, LBVH and HLBVH algorithms
2）基于优化后BVH算法的云渲染加速方法相比于优化后的LBVH、HLBVH、K-means算法，在SAH成本、EPO、构建时间等性能指标上都有大幅提升．
3）基于优化后BVH算法的云渲染加速方法在提升渲染性能的同时，可以保证云场景的视觉效果．
4）基于优化后BVH算法的云渲染加速方法应用到越复杂的场景中时提升效果越大．
本文利用Z-order Hilbert 曲线对基元进行空间排序，提高了数据读取和存储的效率．通过密度计算优化BVH算法从而有效去除子空间中不必要的光线并减少射线和三角形面之间不必要的相交测试次数，减少了BVH的建树时间．在Z-order Hilbert 曲线上计算最近簇和次最近簇，且基元密度与SAH相结合，在最小化SAH成本的同时提高BVH的资源利用率．ONS节点存储结构解决了BVH左右节点空间重叠引起的遍历资源浪费问题，提高了遍历速率．实验结果表明，本算法在实际应用中具有很好的可行性和实用性．然而，本文方法在处理小型云场景时性能与传统方法相比并没有明显优势，并且渲染效果的改进幅度也有限．因此，未来将进一步提升算法在小型云场景中的性能，并探索更多可能的渲染效果改进方案．
