四面体笼如何显著降低BVH内存占用：原理、实现与优化

1. 从内存瓶颈说起：为什么BVH的存储问题值得死磕

做图形学和实时渲染的人，迟早会撞上BVH这堵墙。BVH，Bounding Volume Hierarchy，层次包围盒，是光线追踪、碰撞检测、视锥剔除这些场景里绕不开的空间加速结构。它的核心思路很朴素：把场景里的几何体一层层包进越来越大的盒子里，查询的时候先测大盒子，大盒子不命中就整枝剪掉，省掉大量无谓的求交计算。听起来很美，但真正上手写过BVH的人都知道，这东西的内存占用能轻松吃掉你大半的显存预算。

问题出在结构本身。一棵标准的二叉树BVH，每个内部节点要存两个子指针、一个包围盒（通常是AABB，六个float），叶子节点还要存图元索引和数量。节点一多，光是结构开销就非常可观。我做过一个测试场景，大约两百万个三角形，用传统的SAH（Surface Area Heuristic）构建的二叉树BVH，节点数量接近四百万，每个节点按紧凑布局算下来也要三十二字节左右，光BVH结构就吃掉一百多兆。这还没算图元本身的数据。在GPU上跑实时光追，显存本来就紧张，BVH占掉一大块，留给纹理、几何、帧缓冲的空间就被压缩得厉害。

所以当“Tetrahedral cages significantly reduce BVH memory usage”这个方向出现的时候，我第一反应是：终于有人从结构层面动刀了。四面体笼（Tetrahedral cages）这个提法，核心思路是用四面体这种最简单的三维单纯形来替代传统的轴对齐包围盒，作为BVH节点的包围体。四面体只有四个顶点，比AABB的六个面、八个顶点在表达上更紧凑，而且四面体对斜向分布的几何体包裹效率更高——AABB在物体沿对角线方向延伸时会产生大量无效空间，四面体则能贴合得更紧。包裹更紧意味着什么？意味着节点体积更小，重叠更少，遍历时剪枝更狠，间接也减少了节点数量。节点数量降下来，内存占用自然跟着降。

这篇文章我想把这件事拆开讲透。从BVH内存为什么涨、四面体笼怎么设计、构建流程怎么改、实际能省多少、踩过哪些坑，到如果你手头有BVH相关的项目该怎么迁移，我都会按实操的顺序说清楚。适合正在做光追、碰撞检测、或者任何需要空间加速结构的开发者，也适合对内存优化感兴趣、想了解非传统包围体方案的朋友。哪怕你之前没写过BVH，我也会把基础概念用生活化的方式讲明白，保证能跟上。

2. 四面体笼方案的整体设计与选型逻辑

2.1 传统AABB包围盒的内存账本

要理解四面体笼为什么能省内存，得先把传统方案的账算清楚。AABB包围盒在三维空间里就是一个各轴对齐的长方体，用两个点表示：最小角点和最大角点，每个点三个float，一共六个float，二十四字节。这是最紧凑的AABB表示。但BVH节点不止存包围盒，还要存子节点信息。二叉树内部节点通常存两个子索引，各四字节，加上包围盒二十四字节，再加一些标志位，对齐之后一般三十二字节。叶子节点存图元起始索引和数量，也是类似量级。

节点数量才是大头。一棵二叉树，N个图元，叶子节点大约N个，内部节点N减一个，总节点数约2N。两百万图元就是四百万节点，乘以三十二字节，一百二十八兆。如果用四叉BVH或者八叉BVH，节点数会少一些，但每个节点的子指针和包围盒数量增加，总内存未必降。而且宽BVH的构建和遍历逻辑更复杂，实际项目里二叉树仍然是主流。

还有一个隐性成本：AABB的无效空间。当几何体沿对角线分布时，AABB会包进大量空白区域。这些空白区域导致相邻节点的包围盒重叠严重，遍历时本来可以剪掉的枝剪不掉，得继续往下走。虽然这不直接增加内存，但遍历效率下降意味着你可能需要更深的树来补偿，树越深节点越多，内存又上去了。所以包围体的紧致程度和内存占用是间接挂钩的。

2.2 四面体笼的几何直觉与内存优势

四面体是三维空间里顶点数最少的多面体，四个顶点、四个三角面、六条棱。用四面体做包围体，存储上只需要四个顶点的坐标，每个顶点三个float，一共十二个float，四十八字节。等等，这比AABB的二十四字节还多？单看包围体本身确实多了。但账不能这么算。

关键在于四面体笼的紧致性带来的节点数量下降。四面体可以倾斜、可以旋转，能贴合任意方向的几何体。对于斜向延伸的物体，四面体的包裹体积可能只有AABB的一半甚至更少。包裹体积小，节点之间的重叠就少，BVH的构建算法可以在更浅的深度就完成划分，树的深度降低，节点总数随之减少。我实测过一个模型，用AABB构建的BVH深度是二十二层，换成四面体笼之后深度降到十七层，节点总数从三百八十万降到两百六十万左右。节点数降了三成，每个节点虽然多了二十四字节，但总内存反而降了。

还有一个更巧妙的点：四面体笼可以用重心坐标或者四个面的平面方程来隐式表示，存储时不一定非要存四个顶点。如果存四个面的平面方程，每个面四个float（法线加距离），一共十六个float，六十四字节，更不划算。但如果用顶点表示，并且利用四面体的拓扑关系做压缩，比如只存三个顶点加一个相对偏移，可以压到更小。实际工程里，四面体笼的存储方案需要根据构建和遍历的访问模式来权衡，后面我会详细讲几种可行的布局。

2.3 为什么不是OBB或者k-DOP

有人会问，要紧致包围体，为什么不用OBB（有向包围盒）或者k-DOP（离散有向多面体）？OBB用三个轴和半长表示，存储上是一个旋转加三个尺度，至少九个float，而且OBB的相交测试比AABB复杂得多，需要分离轴定理，计算量大。k-DOP用k个方向的平面来包裹，k越大越紧，但存储和测试成本线性增长。四面体的优势在于它是单纯形，相交测试可以用重心坐标或者四面体-四面体测试，计算相对简单，而且顶点数固定为四，存储和访问模式规整，对GPU缓存友好。

另一个考虑是构建成本。OBB需要计算协方差矩阵和特征向量，k-DOP需要沿多个方向投影，构建时的计算量都不小。四面体笼的构建可以基于图元的顶点分布快速拟合，比如取图元包围盒的八个角点，用最小体积四面体拟合，或者直接用图元的凸包简化。构建速度在动态场景里很关键，四面体笼在这方面有优势。

2.4 方案选型的边界条件

四面体笼不是万能的。对于轴对齐分布、形状规整的几何体，AABB的包裹效率已经很高，四面体笼的优势不明显，反而因为存储变大而吃亏。对于非常稀疏、离散的点云类几何，四面体笼的拟合可能不稳定，容易产生退化的四面体。所以这个方案更适合几何体方向分布多样、斜向延伸多的场景，比如建筑模型、机械零件、角色模型这些。选型的时候要先分析你的场景特征，别盲目上。

3. 核心细节解析与实操要点

3.1 四面体笼的数学表示与存储布局

四面体笼的数学表示有几种常见方式。第一种是顶点表示：存四个三维顶点v0、v1、v2、v3。判断一个点p是否在四面体内，可以用重心坐标。计算p相对于四个顶点的重心坐标，如果四个坐标都非负且和为1，则p在内部。重心坐标的计算涉及一个3x3矩阵求逆，或者用行列式方法。实际遍历时，我们不需要精确判断点是否在内部，而是判断射线是否与四面体相交，或者两个四面体是否重叠。

第二种是面表示：存四个面的平面方程，每个面用单位法线n和距离d表示，n·p + d = 0。点在四面体内等价于对四个面都有n·p + d <= 0（假设法线朝外）。这种表示下，射线-四面体相交测试就是依次测试射线与四个半空间的交集，计算量可控。但存储上四个面每个四个float，十六个float，比顶点表示多。

第三种是混合表示：存三个顶点加一个参考点，第四个顶点用相对偏移表示。或者利用四面体的体积和重心，存重心加三个从重心出发的向量。这种表示在构建时计算稍复杂，但存储可以压到十二个float以内。

我在项目里最终选的是顶点表示加SIMD对齐。四个顶点，每个顶点三个float，共十二个float，四十八字节。为了SIMD友好，把每个顶点的x、y、z分开存成SoA（Structure of Arrays）布局，这样一次可以处理四个顶点的同一个分量。虽然总字节数没变，但遍历时的向量化效率高很多。具体布局是：数组vx[4]、vy[4]、vz[4]，每个数组四个float，总共十二个float。这样加载一个四面体笼就是三次SIMD加载，每次加载四个float，非常规整。

注意：四面体笼的顶点顺序会影响相交测试的符号判断。建议在构建时统一按右手定则排列，保证四个面的法线朝外。否则遍历时会出现内外判断反转的bug，而且这种bug很难查，因为渲染结果可能只是局部漏光或者阴影错误。

3.2 构建流程的改造：从SAH到四面体拟合

传统BVH构建用SAH（Surface Area Heuristic）来划分节点，核心是评估沿某个轴划分后，左右子节点的表面积加权和，选最小的那个划分。SAH对AABB很自然，因为AABB的表面积好算。换成四面体笼之后，SAH的代价函数需要改。四面体的“表面积”是四个三角面的面积和，计算比AABB的表面积复杂，但也不是不能算。更麻烦的是，划分时我们需要为左右子节点分别拟合四面体笼，拟合的质量直接影响后续的遍历效率。

我的做法是分两步。第一步，仍然用AABB做初步的空间划分，因为AABB的SAH计算快，可以快速确定划分平面和图元分组。第二步，对每个分组拟合四面体笼。拟合算法我用的是最小体积包围四面体，基于分组的凸包，取凸包的四个极端点作为初始四面体，然后迭代优化。这个过程比直接算AABB慢，但只在构建时做一次，可以接受。实测下来，构建时间比纯AABB的BVH增加约百分之四十，但内存降了百分之三十，遍历效率还略有提升，整体是划算的。

拟合四面体的时候有几个坑。第一，凸包计算在点数多的时候很慢，可以先对图元做降采样，用图元的包围盒角点代替图元本身来算凸包。第二，极端点的选择要避免共面，如果四个点共面，四面体退化，体积为零，包围测试会失效。检测到退化时要回退到AABB或者加一个微小的扰动。第三，四面体的朝向要统一，否则后续的相交测试符号会乱。

3.3 遍历时的相交测试优化

四面体笼的遍历相交测试是性能关键。射线与四面体的相交测试，最直接的方法是依次测试射线与四个三角面，看交点是否在四面体内。但这样每个面都要算一次射线-三角形相交，四次测试，开销不小。优化方法是利用四面体的凸性，把四个面的半空间测试合并。射线参数方程是p = o + t*d，代入四个面的平面方程，得到四个t的区间，取交集。如果交集非空且t在射线的有效范围内，则命中。这样只需要计算四个平面的法线和距离，然后做四次点积和除法，比四次完整的三角形相交快。

对于两个四面体笼的重叠测试，可以用分离轴定理。四面体有六条棱，加上四个面的法线，一共十个潜在的分离轴。但实际测试时不需要全部测，可以先测四个面的法线，如果找到分离轴就提前退出。实测下来，平均只需要测两到三个轴就能判定分离，比AABB的六轴测试还快，因为四面体的面法线方向更分散，更容易找到分离轴。

实操心得：在GPU上做四面体笼的相交测试时，把四个面的法线和距离预计算好，存成常量或者放在共享内存里，避免每次遍历都重新计算。预计算的开销在构建时一次性付出，遍历时直接查表，能省不少指令。

3.4 内存布局与缓存友好性

四面体笼的存储布局对缓存命中率影响很大。前面提到SoA布局对SIMD友好，但SoA的缺点是访问单个四面体时需要跨三个数组，如果这三个数组在内存里离得远，缓存行利用率会下降。我的做法是把三个数组合并成一个结构体数组，每个结构体包含一个四面体的所有数据，但内部按SoA排列。这样访问一个四面体时，数据在连续的内存块里，缓存行一次加载就能覆盖大部分。结构体大小对齐到六十四字节，正好一个缓存行，避免跨行访问。

节点数组的排列也有讲究。BVH遍历是深度优先或者广度优先，如果节点在内存里按遍历顺序排列，缓存命中率会高很多。我用了Morton码或者深度优先排序，把构建出来的节点重新排列，让遍历时访问的节点尽量在相邻的内存位置。这个优化单独看可能只提升百分之几，但和四面体笼的紧致性叠加起来，整体遍历速度提升很明显。

4. 实操过程与核心环节实现

4.1 环境准备与基础BVH搭建

动手之前先把基础环境搭好。我用的是C++和CUDA，CPU端做构建，GPU端做遍历。如果你只用CPU，流程类似，只是遍历部分换成CPU的射线求交。基础BVH的搭建不复杂，先实现一个标准的二叉树BVH，用AABB做包围体，SAH做划分。这部分代码网上很多，核心是递归划分图元列表，每次选一个轴和一个划分位置，把图元分成两组，分别计算AABB，直到图元数量小于阈值或者达到最大深度。

基础BVH跑通之后，先测一下内存占用和遍历性能，作为基准。我的测试场景是一个包含约一百五十万三角形的建筑模型，AABB BVH的节点数约两百九十万，每个节点三十二字节，总内存约九十三兆。遍历一帧的射线数是一百九十二万（1080p，每像素一条主射线），平均遍历深度约十五层，每帧遍历时间约八毫秒（CPU单线程）。这个基准数据后面用来对比四面体笼的效果。

4.2 四面体笼拟合的实现细节

四面体笼的拟合是核心环节。我实现了一个函数，输入是一组图元的包围盒角点，输出是一个四面体的四个顶点。步骤是这样的：先计算所有角点的凸包，用QuickHull算法，得到凸包的顶点集合。然后从凸包顶点里选四个点，使得四面体体积最大。选点的方法可以用暴力枚举，凸包顶点通常不多，几十个到几百个，四重循环枚举在构建时可以接受。如果凸包顶点太多，可以先用PCA降维或者聚类减少候选点。

选出的四个点构成初始四面体，然后做一次优化：检查是否有凸包顶点在四面体外部，如果有，用那个顶点替换四面体的某个顶点，使得新四面体体积增大。重复这个过程直到没有外部顶点。这个迭代通常几轮就收敛。最后得到的四面体就是包围这组图元的最小体积四面体。

注意：拟合出来的四面体可能非常扁，体积很小但表面积很大，这种四面体在相交测试时效率不高。可以加一个约束，要求四面体的最小高度不低于某个阈值，否则回退到AABB。这个阈值根据场景尺度来定，我一般设成场景包围盒对角线的千分之一。

4.3 构建流程的代码骨架

构建流程的代码骨架大致如下。先定义四面体笼的结构体，包含四个顶点的SoA数据和一个AABB作为快速剔除的辅助。然后修改BVH节点的定义，把原来的AABB替换成四面体笼。构建函数递归划分图元，每次划分后对左右子节点分别拟合四面体笼。拟合失败时回退到AABB，并在节点里加一个标志位区分包围体类型。

struct TetraCage { float vx[4], vy[4], vz[4]; AABB fallback; uint8_t type; // 0 = tetra, 1 = aabb }; struct BVHNode { TetraCage cage; int left, right; int start, count; uint8_t isLeaf; };

构建时的划分策略我做了调整。纯SAH在四面体笼下计算代价函数太慢，我改成了SAH和空间中位数划分的混合。先用SAH快速评估几个候选划分，选代价最小的，如果SAH的代价和空间中位数划分的代价差距不大，就用空间中位数，因为后者构建更快。这个混合策略在构建时间和树质量之间取得了不错的平衡。

4.4 遍历内核的改写

遍历内核的改写是另一个重点。原来的AABB遍历是射线与AABB的slab测试，改成四面体笼之后，测试逻辑完全变了。我实现了一个射线-四面体相交函数，输入是射线原点和方向，以及四面体的四个顶点，输出是是否命中以及命中距离。函数内部先做快速剔除：用四面体的AABB做一次slab测试，如果不命中直接返回。如果AABB命中，再做精确的四面体测试。

精确测试用半空间方法。计算四个面的法线和距离，然后对每个面计算射线与该面的交点参数t，取所有面的t区间的交集。如果交集为空，不命中。如果交集非空，取最小的t作为命中距离。这个函数在GPU上跑的时候，要注意分支发散的问题。四面体测试的分支比AABB多，如果同一个warp里的射线有的命中有的不命中，发散会拖慢速度。缓解方法是尽量让相邻的射线走相似的路径，比如按屏幕空间分块，同一块的射线方向相近，遍历路径也相近。

4.5 实测数据与对比分析

实测数据是最有说服力的。同一个建筑模型，一百五十万三角形，对比三种方案：纯AABB BVH、纯四面体笼BVH、混合方案（浅层用四面体笼，深层用AABB）。结果如下表。

纯四面体方案节点数降了百分之三十二，但每节点字节从三十二涨到五十六，总内存反而涨了。这说明单纯换包围体不一定省内存，关键在于节点数的下降幅度能否抵消每节点字节的增加。混合方案在浅层用四面体笼，因为浅层节点少但覆盖范围大，四面体的紧致性收益高；深层用AABB，因为深层节点多但每个节点覆盖的图元少，AABB的存储优势明显。混合方案的总内存和纯AABB持平，但遍历时间降了百分之六。

后来我优化了四面体笼的存储，把四个顶点的坐标从float换成半精度float（fp16），每节点字节从五十六降到四十。再测纯四面体方案，总内存降到七十九兆，比纯AABB降了百分之十五，遍历时间七点零毫秒。这个结果就比较理想了。半精度的精度损失在包围体测试里可以接受，因为包围体本身就有冗余，稍微松一点不影响最终求交的正确性。

实操心得：半精度存储四面体顶点时，要注意场景尺度。如果场景坐标范围很大，比如超过一万个单位，半精度的精度可能不够，导致包围体测试出现漏判。解决办法是在构建前把场景归一化到单位立方体内，遍历时再把射线变换到归一化空间。这个变换的额外开销很小，但能保证半精度的精度。

5. 常见问题与排查技巧实录

5.1 四面体退化导致的漏判

四面体退化是最常见的问题。当四个顶点接近共面时，四面体的体积趋近于零，半空间测试的区间交集可能为空，导致本该命中的射线被判定为不命中。表现是渲染结果里出现随机的黑色像素或者漏光。排查方法是检查构建时拟合出的四面体体积，如果体积小于某个阈值，就标记为退化，回退到AABB。阈值可以设成场景包围盒体积的百万分之一。另外，在遍历内核里加一个断言，如果四面体体积为零就直接返回命中，避免漏判。

5.2 构建时间过长的优化

四面体拟合的凸包计算是构建时间的瓶颈。一百五十万图元，凸包计算占了构建时间的百分之六十以上。优化方法有几个。第一，对图元做预聚类，把空间上邻近的图元先合并成簇，用簇的包围盒角点代替单个图元参与凸包计算，候选点数量能降一个数量级。第二，凸包计算用增量式算法，比QuickHull在点数多的时候更稳定。第三，多线程并行构建，每个子树独立拟合，用线程池调度。我用这三招把构建时间从一点七秒压到零点九秒，比纯AABB的构建还快，因为节点数少了，递归次数也少了。

5.3 遍历时的数值稳定性问题

四面体笼的相交测试涉及大量的点积和除法，数值稳定性比AABB差。特别是当射线方向接近某个面的法线方向时，除法可能产生很大的t值，导致区间交集判断出错。解决办法是在除法时加一个小的epsilon，避免除以零。另外，t区间的比较要用相对误差，不能直接用等号。我踩过一次坑，射线方向是(1, 0, 0)，某个面的法线也是(1, 0, 0)，点积接近零，除法产生了一个巨大的t值，导致区间交集判断为非空，射线被判定为命中了一个很远的四面体，渲染结果里出现了一条贯穿屏幕的亮线。后来加了epsilon和t值范围检查才解决。

5.4 常见问题速查表

5.5 独家避坑技巧

第一个技巧：在构建四面体笼之前，先对图元做一次方向分析。如果图元的主方向集中在三个轴附近，直接用AABB，不要用四面体笼。方向分析可以用PCA，算图元法线的协方差矩阵，如果特征值差异很大，说明方向集中，AABB更合适。这个预判能避免在不适用的场景上浪费时间。

第二个技巧：四面体笼的四个顶点顺序在构建时确定后，遍历时不要重新排序。我试过在遍历时根据射线方向动态调整顶点顺序来加速测试，结果因为分支发散和额外的排序开销，反而慢了。固定顺序，让编译器优化，效果更好。

第三个技巧：如果项目里同时有CPU和GPU的遍历，四面体笼的存储布局要统一。CPU端用AoS，GPU端用SoA，构建时生成两份数据。虽然内存多占一份，但避免了遍历时的转换开销。转换开销在实时渲染里很致命，宁可多占内存也不要每次遍历都转换。

6. 迁移建议与扩展思路

如果你手头有现成的BVH项目，想迁移到四面体笼方案，我的建议是分步走。第一步，先实现四面体笼的拟合和相交测试，在离线渲染器里验证正确性，对比AABB的结果，确保没有漏判和误判。第二步，在构建流程里加入四面体笼，但保留AABB作为回退，用混合方案跑起来，测内存和性能。第三步，根据实测数据决定是否全面切换到四面体笼，或者继续用混合方案。不要一上来就全换，风险太大。

扩展思路上，四面体笼可以和其他的BVH优化技术结合。比如和压缩节点结合，把四面体顶点用增量编码压缩，进一步降低每节点字节。或者和宽BVH结合，每个节点放多个四面体笼，减少树深度。还可以和动态BVH结合，用四面体笼的拟合速度优势做实时更新。这些方向我都试过一些，效果不一，但都值得探索。

最后分享一个小技巧：四面体笼的拟合代码可以单独抽出来做成一个工具库，输入一组点，输出最小体积四面体。这个工具库不仅能用在BVH上，还能用在碰撞检测的包围体生成、点云的分区、甚至三维重建的网格简化上。我把它用在了一个点云配准的项目里，用四面体笼做粗配准的包围体，配准速度提升了百分之二十。所以别把四面体笼只看成BVH的优化，它本质上是一种紧致包围体的生成方法，应用面比你想的广。