基于优化八叉树的场景视锥体裁剪算法

李颖颖，黄文培

（1.西南交通大学计算机与人工智能学院，四川 成都 611756；2.西南交通大学信息科学与技术学院，四川 成都 611756）

0 引 言

随着数字孪生［1-2］、虚拟仿真［3］和增强现实［4］技术的迅速发展，浏览器端3D 模型可视化技术在建筑信息（Building Information Modeling，BIM）、智能制造、生物医学成像等领域均得到了广泛应用［5-6］。由于专业领域的模型通常结构复杂，顶点、法向量等几何数据繁多且无序［7］，这无疑增加了计算机存储消耗和CPU 处理压力，以致于出现显示卡顿、交互帧率过低、内存占用量过大等问题，从而整体上影响了三维模型的实时可视化。因此，采用一种有益于计算机存储的空间数据结构管理模型构件［8］，并在此基础上结合可见性裁剪算法，将有效提升大体量三维模型在浏览器端的可视化效果。

1 相关研究工作

常见的空间数据结构有层次包围盒（BVH）、二叉树（BSP）、八叉树（Octree）［9］，应用模型场景不同，但各有优劣。本文所采用的八叉树是一种多层级树形结构，是四叉树在三维场景的扩展［10］，适用组织大体量的模型数据，缺点是随着模型数据与场景复杂度的增加，树的层级逐渐增多，导致了节点查询遍历效率低、内存占用量大、适应性弱等问题。如何在提高空间压缩效率同时具有较强的自适应性，成为了众多学者的研究课题。现如今研究方向主要分3 种：八叉树存储结构［11-12］、自适应性［13-14］与混合其他空间数据结构［15］。

鲍义东等人［16］采用改进编码二进制的方式实现八叉树存储结构，与传统八叉树相比具有速度快、存储量小的优势；与线性八叉树相比，对节点的分割、删除和查找也很方便。并通过检查三角形包围体是否大于节点的1/3来确定是否细分和具有良好的自适应性。Dricot 等人［17］提出了一种模式决策模块，基于失真最小化为每个8 位字节选择最佳编码模式，这种方式显著提高了八叉树的编码效率，具有良好的压缩性能。Koh等人［18］提出了一种截断八叉树的新型存储结构，通过浅八叉树表示深八叉树提高压缩率，提出了一种可变长度寻址方案，能自适应选择八叉树节点地址的长度，从而进一步压缩。吴宇豪等人［19］基于线性八叉树编码进行了改进，采用Hilbert 码标记节点，相比现有的Morton 码转换算法效率更高。周藤藤［20］采用八叉树和层次包围盒混合的空间划分方式管理模型场景，能够根据场景不同的特点选择最优的划分方式，从而加速了视锥体的剔除，达到很好的优化效果。

综上所述，本文提出一种基于优化八叉树的场景视锥体裁剪算法，在存储结构与自适应性方面进行了优化。采用基于Morton 码的分层存储方式加速节点划分与遍历；依据视域与视点，对节点按需增量划分同时设置视距标准作为划分终止条件，使得八叉树具有良好的自适应性。在优化八叉树基础上，采用双层包围体视锥体裁剪方式和基础相交测试，加速视锥体裁剪。通过与传统的八叉树视锥体裁剪相比，本文的算法在空间压缩率和渲染帧率上都有显著的提高。

2 八叉树数据结构

2.1 传统八叉树结构

八叉树结构是将三维空间划分为越来越小的体积，每个体积具有相同的时间和空间复杂度［21］，八叉树的结构示意图见图1。主体积的边界框对应树的根节点，并包括所有的模型构件。将根节点按照一定的划分规则通过循环递归的方法自顶向下均匀地分成2n×2n×2n节点（n为划分的次数），直到节点所含构件数或达到目标深度后停止划分。

图1 八叉树结构图

2.2 存在的问题

目前传统八叉树存在以下一些问题：

1）在生成八叉树结构和查询节点的过程，需要递归执行查询操作，花费大量的时间。

2）每个节点需存储子节点的指针为0 或8 个，存储空间占用较大。

3）划分方式为刚性（即所含构件数或固定深度作为阈值），不具有灵活性，不能与视点等相关因素建立联系。

4）采用静态划分的方式，不具有实时性，易造成在渲染时保持相当高的内存占用量。

3 优化八叉树数据结构

针对传统八叉树存在的问题，本文在存储结构和自适应2 个方面进行优化，构建流程如图2 所示。优化过程如下：

图2 优化八叉树构建流程图

1）存储结构方面。逐层划分时，采用Morton 码的分层存储方式，在每层节点生成时，先利用构件和当前节点的空间坐标，求出目标节点的Morton 码；然后根据Morton 码确定目标节点存储的实际位置。

2）自适应方面。通过按需增量划分和设置视距标准使得八叉树在整体上具有自适应性。首先根据视域因素，按需对八叉树节点进行划分，控制八叉树横向的生长。然后根据视点因素，设置视距标准，作为节点划分终止条件，控制八叉树的纵向生长。从而在整体上实现自适应同时保证较低的空间消耗。

3.1 基于Morton码分层存储

与普通八叉树相比，线性八叉树是提高数据存储压缩率的有效方式，其存储方式是将所有层级的叶节点混合在一起，然后按照Morton码从小到大的顺序依次存储。本文在划分过程中基于线性八叉树Morton码，在其存储结构上采用了分层线性存储的方式。

分层线性存储的每一个层级都对应一维线性数组。在逐层划分时，利用构件与当前节点（父节点）的空间位置信息，生成目标节点（子节点）的Morton码，然后对目标节点按照M-Order（即节点Morton 码对应的一维数组索引顺序）存储至相应层的一维数组中。目标节点的Morton 码均采用6 位二进制表示，取值范围0~26。分层线性存储方式分为节点Morton码的计算和利用Morton码确定目标节点实际存储位置2大步骤。

3.1.1 节点Morton的计算

节点Morton 码是节点在对应实际存储空间的索引，用一维的数值表示，其计算方式主要有2 种：利用查询表计算与迭代交叉计算［22］。本文选择后者，因其算法过程容易理解，并采用二进制移位运算的方式，可减少计算复杂度。计算过程如下：

1）输入构件与父节点的空间位置，计算出目标节点所在正负区间inside；

其中：p为构件的BS 体的中心，r为半径，min、max 为节点最大和最小顶点。

2）根据公式（2）计算目标节点分量的Morton 码；设目标节点分量的Morton码分别为Mx、My、Mz；

3）已知目标节点分量Morton 码，使用公式（3）计算节点的Morton码。

3.1.2 利用Morton码确定目标节点实际存储位置

一维线性数组的长度为8，可用3位二进制表示。每位可取0或1，表示每个轴向划分的左右2个区间。

1）利用三层嵌套循环，对8个区间遍历。

2）每层循环体中，分别使用公式（4）~公式（6）判断，结果为false，跳出本层循环；x、y、z取值0或1。

3）在最内层循环中，通过公式（7）计算出节点在数组的实际存储索引octant，octant 初始值为0，x、y、z取值0或1。

4）在索引位置生成节点对象。

3.1.3 分层线性存储方式优势

分层线性存储方式具有以下优势：

1）利用二进制移位操作，快速计算节点的Morton码，减少计算量。

2）建立节点的Morton码与存储位置的对应关系，加速节点划分与遍历，提高空间压缩效率。

3）不用存储节点的Morton码，节省了存储空间。

3.2 按需增量划分

实时渲染时，模型会以完全处于视域内或部分处于视域内2 种状态存在。前者需渲染所有的模型构件，此种状态下再创建多层级八叉树将带来无用的内存空间消耗；后者则只需要对与视域相交的节点增量划分，对于在视域外和内的节点则不需生成。考虑到以上情况，本文采用按需增量划分的方式。该方式主要分为2个阶段：

1）根节点生成。首先建立体积较小的根节点，然后判断根节点是否包含每一个构件，如果都包含则输出根节点；否则对旧的根节点依次进行上下边界的扩充，生成新的根节点，递归调用判断函数，直至包含该构件。新节点的宽度为旧节点的2 倍，并通过公式（8）得到新节点的位置信息。

2）实时渲染。当视锥体运动时，检测出与之碰撞的节点，对这些节点动态地进行划分，然后对每个子节点继续检测是否与视锥体碰撞，对于碰撞的子节点再次进行划分，对于完全在视锥体内和外的节点会停止划分。停止子结点划分的3 种条件：①当节点满足划分终止条件时；②节点完全被视锥体包含时；③节点完全在视锥体外时。

此方式虽然在增量划分时会产生一定的时间消耗，但也仅仅在面向相交节点时才会产生额外的计算。而且在大规模静态场景中，可见构件的数据量远小于场景中所有的构件数量，视点的移动范围和速度也不会很大，因此不会造成与之相交的静态八叉树节点的频繁变化。故采用这种方式，能够在保证时间效率的前提下，减少无用的节点生成，从而控制八叉树横向的生长，具有很好的适应性。

3.3 设置划分终止条件

采用自顶向下的八叉树划分方式，若不设置划分终止条件，容易造成八叉树纵向的不断生长，从而导致栈溢出的问题。目前通过刚性的方式难以满足复杂场景的需要。本文通过建立视距标准作为划分终止条件，能使得模型场景满足距离视点较近且密度较大的部分，使用较多的树节点组织；距离较近且密度小的部分，使用较少的树节点组织。

传统的视距标准［23］，仅仅依赖视点与节点的距离对节点进行划分，该方式过于片面。本文认为节点尺寸也是一个重要的因素，因为尺寸过大，在屏幕中也会占据较大的区域，如果不对当前节点进行划分，会导致渲染中出现失真的现象，所以在对节点进行划分时，应同时考虑视距和节点尺寸2 个因素。视距标准的示意图如图3所示。

图3 视距标准图

图3 中L表示视点到节点中心的距离，S表示节点的尺寸，定义视距标准变量V，用以下公式判断节点是否划分：

当V＜1 时，对节点进行划分，V≥1 时终止划分；C为视距的控制变量，通过调整C的大小来改变视距对节点划分的影响程度。经过实验推导出，C与V的取值成反比，当C取值越大时，V越小，视点距离对节点划分影响就越大，相反，视点距离对节点划分影响越小。

关于视点距离L的计算，三维距离的计算方式常用有2 种，分别是欧几里得公式、曼哈顿公式［24］。设视点坐标（x1，y1，z1），节点中心坐标（x2，y2，z2），2 种计算公式如下：

欧几里得公式：

曼哈顿公式：

欧几里得公式能精确反映2 点的距离，但涉及开方复杂运算；曼哈顿公式虽然求值结果会存在结果偏大的误差，但是可以通过增大C来减小误差，同时可以减少计算量。基于每次节点划分都要计算视点距离，故采用曼哈顿公式作为求2 点距离的表达公式，节省运算量。关于节点尺寸S的计算，八叉树的节点是由AABB 包围盒描述的，故取出包围盒的最大顶点和最小顶点，并通过曼哈顿公式求2 点的距离，作为节点的尺寸S。实验结果表明：本文设置的视距标准，创建的八叉树具有合适的细分程度，可以保证不同距离的模型构件表现效果基本相同，使得八叉树在纵向上与视点建立良好的适应性。

4 基于优化八叉树的视锥体裁剪

4.1 视锥体裁剪原理

视锥体裁剪是对模型里的每一个构件判断和视锥体的相交关系，如果构件在视锥体内或者相交，就将构件加入渲染列表，否则将其剔除。研究表明：随着模型构件增加，每帧的视锥裁剪运行时间与构件的数量成线性关系，反而导致渲染帧数降低［25］。通过对场景中的模型建立空间数据结构，利用其空间相关性进行视锥体裁剪，能够大幅度提高裁剪效率。

视锥体是由透视投影矩阵变换得到的结果，因此每个面的法线平面方程均可由透视投影矩阵推导出。在推导中可得出以下结论：平面方程的法向量指向视锥体内侧，且若点到平面的距离为正，表示为与法向量同向，则判断点在平面内侧；若距离为负，则判断点在平面外侧［26］。通过此结论可以计算出包围体与视锥体的碰撞结果。

使用包围体对构件近似描述，可以解决复杂构件与视锥体碰撞检测困难的问题。在本文中共定义了3 种包围体（Bonuding Volume）：AABB 盒（AB）、OBB盒和BSphere 体（BS）。AB 盒用来描述树节点，构建简单，适用于粗略的碰撞检测；OBB 包围盒用来描述构件，构建复杂，但紧密性比AB 盒、BS 体表现都要好，适用于精确的碰撞检测；BS 体构造简单且碰撞检测最为容易，但紧密性也是最差的，因此利用BS体对2种包围盒进行包裹，可以加快碰撞检测的速度。

本文裁剪算法在优化八叉树基础上，前期对八叉树节点采用BS-AB 双层包围体方式逐层进行粗略筛选，后期对碰撞的潜在构件采用BS-OBB 双层包围体方式逐层进行精细筛选，最终得到渲染构件对象列表。

4.2 裁剪算法描述

1）粗略筛选。首先判断节点BS体与视锥体的相交关系。测试结果为“包含”，则表示该节点以及子节点中的构件都是可见的，把节点及子节点所含的构件添加到渲染列表中，测试结束。测试结果为“不相交”，则表示该节点以及子节点内的构件都不可见，测试结束。测试结果为“相交”，则开始判断节点AB 盒与视锥体的关系，包含，则将节点以及子节点所含构件添加至渲染列表，测试结束；不相交，测试结束；相交，则继续遍历子节点，对子节点同样进行BS 体和AB盒的判断，直至叶子节点。

2）精细筛选。取出叶子节点的所有构件，对构件的BS 体和OBB 盒逐层裁剪。先判断构件BS 体与视锥体的关系，不相交时，测试结束；包含时，将构件放入渲染列表中，测试结束；相交时，则开始判断构件OBB 盒，若OBB 盒与视锥体不相交，测试结束，相交或者包含时，把该构件放入渲染列表中。所有构件遍历结束，则裁剪算法终止。整体裁剪算法流程如图4 所示。

图4 视锥体裁剪流程图

4.3 双层包围体与视锥体的碰撞检测

BS 体与视锥体的相交测试是直接根据BS 体中心到6 个平面的有向距离distance 与BS 体半径radius判断。若|distance|≤radius，则判断相交；在相交不成立的情况下，若distance＞radius，那么BS 体在平面的内侧，所有的平面都满足时，则判断包含；若distance＜-radius，那么BS 体在视锥体外侧，任一平面满足该条件时，则判断为不相交，直接退出循环。

包围盒与视锥体的精确相交测试，即包围盒的8个顶点与视锥平面进行测试［27］。该方法实现过程简单，但计算量非常大。本文采用Assarsson和Tomas在1999 年提出的视锥体剔除优化中的基础相交测试方法［25］。该方法只需测试对角线与平面法线夹角最小的2 个顶点，分别记为顶点p和顶点n。测试流程为：找到一条穿过包围盒中心且与平面法向量方向较为接近的包围盒对角线向量V=，如果n顶点位于平面的外侧，则整个包围盒都在外面，停止测试，判断结果为不相交；然后对p顶点进行测试，若p顶点在平面内侧，判断结果为包含，否则包围盒和视锥体相交。p和n顶点的确定：设平面法向量为N，当N的第i个分量为正值，选择pi=box.min［i］、ni=box.max［i］，保证了对角线向量Vi与平面法向量Ni相同符号；当平面法向量N第i个分量为负值，选择pi=box.max［i］、ni=box.min［i］，同样也保证了对角线向量Vi与平面法向量Ni相同符号。示意图如图5所示。

图5 包围盒与视锥体相交测试图

5 实验结果及分析

本文实验的环境为64 位Windows 10 系统，CPU为Intel（R）Core（TM）i7-10510U CPU@1.80 GHz，内存为16 GB，显卡为NVIDIA GeForce MX350，实验的运行和调试平台为Chrome 浏览器，开发软件为vsCode，选择Three.js 框架作为三维模型渲染平台。本文所采用的列车转向架三维模型来源于“面向产品全生命周期及闭环反馈的信息物理融合理论”国家重点研发项目，其模型格式为.glb，构件数量为9454个。

表1 为不同划分方式在节点数和平均渲染时间上的比较，均为刚性划分（同一目标深度）。从表1 数据中可以得出以下结论：

表1 按需划分与静态划分对比

1）节点数的比较。视点位置相同的情况下，静态划分方式在运行过程中始终保持较高的节点数，但按需划分方式则是随着视角的变换，节点数稳定增加，且在同一个视角和多个视角的情况下节点数都是远少于静态划分的。

2）平均渲染时间比较。虽然按需划分方式所消耗时间多于静态划分，但差距不大，在可控范围内。

根据以上结论，选择按需划分的方式可以较好地控制八叉树横向的生长，使其具有横向的自适应性和较好的空间压缩效率。

表2 为视距控制变量C来确定的实验结果，划分过程中，采用按需划分的方式并以Morton码的分层存储方式管理子节点。表中构件剔除占比=（总构件数-渲染构件数）/总构件数，从表2 数据中可以得出以下结论：

表2 视距控制变量C的确定

1）当C取相同值时，随着视点与节点的距离的不断变小，八叉树细分的程度越高，节点数越多，剔除的构件也逐渐变多。

2）当视点位置相同时，随着C值不断增大，剔除效果逐渐变好，节点数也是较稳定的增加，当C取40时，剔除效果和C取35 时几乎相同，但节点数的增加幅度明显变大。

根据以上结论，本文选择C取35 计算视距标准，既保证剔除的良好性，又在纵向上具有自适应性。

表3 为传统八叉树与优化八叉树在内存空间压缩效率方面的比较，表中传统八叉树采用静态划分的方式和传统的存储结构，总内存占用量=（现在内存量-原内存量）/原内存量。通过表3数据可以看出：

表3 优化八叉树与传统八叉树在内存空间压缩效率对比

1）同一深度，优化八叉树要比传统八叉树节点数少，且随着深度的增加，优化八叉树节点增加幅度要明显小于传统八叉树。

2）在总内存占用量少，相对于传统八叉树，优化八叉树减少了约38个百分点，具有较好的空间压缩效率。

表4 为基于优化八叉树的视锥体裁剪算法与传统八叉树裁剪算法在渲染帧率上面的比较。通过表4 结果可以看出：在传统渲染的情况下最低帧数约为7帧，要比基于优化八叉树的视锥体裁剪少5帧左右。原因是：初始加载时，整个模型处于场景内，需渲染所有的构件，剔除效果不明显，这种情况下帧数都偏低，而本文算法通过按需增量划分的方式，在初始时并未生成多层级的八叉树结构，因此帧数要比传统的略多。最多帧数这一栏，因视点距离模型较近时，可以剔除掉很多的构件，所以帧率可以达到60 帧（满帧），传统的未达到满帧，是使用简单的存储结构，节点数较多引起的。平均渲染帧率是决定浏览是否卡顿的关键，传统的仅仅只有17 帧，难以满足流畅显示与交互。在本文算法优化的情况下可以达到31 帧，已经可以满足流畅的模型浏览。

表4 本文算法与传统算法对比

6 结束语

本文针对于大体量模型在浏览器端渲染效果不佳的问题，提出了一种基于优化八叉树的场景视锥体裁剪算法。针对传统八叉树存在的问题，在存储结构和自适应性2 个方面进行了优化，达到了既具有高效的空间压缩效率，又能根据视点位置和模型场景特点构建出自适应的八叉树。在视锥体裁剪上，采用了双层包围体的方式同时对碰撞检测进行了优化，既降低了裁剪的时间复杂度，又提高了裁剪的准确率。最后以高速列车实例模型作为应用场景，通过多次实验证明了算法的可行性、合理性和有效性。