尧图网站建设 
1. 从内存瓶颈说起为什么BVH的存储问题值得死磕做图形学和实时渲染的人迟早会撞上BVH这堵墙。BVHBounding Volume Hierarchy层次包围盒是光线追踪、碰撞检测、视锥剔除这些场景里绕不开的空间加速结构。它的核心思路很朴素把场景里的几何体一层层包进越来越大的盒子里查询的时候先测大盒子大盒子不命中就整枝剪掉省掉大量无谓的求交计算。听起来很美但真正上手写过BVH的人都知道这东西的内存占用能轻松吃掉你大半的显存预算。问题出在结构本身。一棵标准的二叉树BVH每个内部节点要存两个子指针、一个包围盒通常是AABB六个float叶子节点还要存图元索引和数量。节点一多光是结构开销就非常可观。我做过一个测试场景大约两百万个三角形用传统的SAHSurface 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分开存成SoAStructure of Arrays布局这样一次可以处理四个顶点的同一个分量。虽然总字节数没变但遍历时的向量化效率高很多。具体布局是数组vx[4]、vy[4]、vz[4]每个数组四个float总共十二个float。这样加载一个四面体笼就是三次SIMD加载每次加载四个float非常规整。注意四面体笼的顶点顺序会影响相交测试的符号判断。建议在构建时统一按右手定则排列保证四个面的法线朝外。否则遍历时会出现内外判断反转的bug而且这种bug很难查因为渲染结果可能只是局部漏光或者阴影错误。3.2 构建流程的改造从SAH到四面体拟合传统BVH构建用SAHSurface 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和CUDACPU端做构建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。结果如下表。方案节点数每节点字节总内存构建时间遍历时间纯AABB290万3293MB1.2s8.0ms纯四面体198万56111MB1.7s7.2ms混合215万4495MB1.4s7.5ms纯四面体方案节点数降了百分之三十二但每节点字节从三十二涨到五十六总内存反而涨了。这说明单纯换包围体不一定省内存关键在于节点数的下降幅度能否抵消每节点字节的增加。混合方案在浅层用四面体笼因为浅层节点少但覆盖范围大四面体的紧致性收益高深层用AABB因为深层节点多但每个节点覆盖的图元少AABB的存储优势明显。混合方案的总内存和纯AABB持平但遍历时间降了百分之六。后来我优化了四面体笼的存储把四个顶点的坐标从float换成半精度floatfp16每节点字节从五十六降到四十。再测纯四面体方案总内存降到七十九兆比纯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 常见问题速查表问题现象可能原因排查方法解决方案渲染出现黑色像素四面体退化漏判检查四面体体积体积过小回退AABB构建时间过长凸包计算慢统计各阶段耗时预聚类并行构建遍历出现亮线数值不稳定检查除法epsilon加epsilon和范围检查内存反而增加节点字节增加过多对比节点数和字节数混合方案或半精度存储遍历速度下降分支发散严重分析warp执行效率屏幕空间分块排序射线5.5 独家避坑技巧第一个技巧在构建四面体笼之前先对图元做一次方向分析。如果图元的主方向集中在三个轴附近直接用AABB不要用四面体笼。方向分析可以用PCA算图元法线的协方差矩阵如果特征值差异很大说明方向集中AABB更合适。这个预判能避免在不适用的场景上浪费时间。第二个技巧四面体笼的四个顶点顺序在构建时确定后遍历时不要重新排序。我试过在遍历时根据射线方向动态调整顶点顺序来加速测试结果因为分支发散和额外的排序开销反而慢了。固定顺序让编译器优化效果更好。第三个技巧如果项目里同时有CPU和GPU的遍历四面体笼的存储布局要统一。CPU端用AoSGPU端用SoA构建时生成两份数据。虽然内存多占一份但避免了遍历时的转换开销。转换开销在实时渲染里很致命宁可多占内存也不要每次遍历都转换。6. 迁移建议与扩展思路如果你手头有现成的BVH项目想迁移到四面体笼方案我的建议是分步走。第一步先实现四面体笼的拟合和相交测试在离线渲染器里验证正确性对比AABB的结果确保没有漏判和误判。第二步在构建流程里加入四面体笼但保留AABB作为回退用混合方案跑起来测内存和性能。第三步根据实测数据决定是否全面切换到四面体笼或者继续用混合方案。不要一上来就全换风险太大。扩展思路上四面体笼可以和其他的BVH优化技术结合。比如和压缩节点结合把四面体顶点用增量编码压缩进一步降低每节点字节。或者和宽BVH结合每个节点放多个四面体笼减少树深度。还可以和动态BVH结合用四面体笼的拟合速度优势做实时更新。这些方向我都试过一些效果不一但都值得探索。最后分享一个小技巧四面体笼的拟合代码可以单独抽出来做成一个工具库输入一组点输出最小体积四面体。这个工具库不仅能用在BVH上还能用在碰撞检测的包围体生成、点云的分区、甚至三维重建的网格简化上。我把它用在了一个点云配准的项目里用四面体笼做粗配准的包围体配准速度提升了百分之二十。所以别把四面体笼只看成BVH的优化它本质上是一种紧致包围体的生成方法应用面比你想的广。 四面体笼如何显著降低BVH内存占用：原理、实现与优化
1. 从内存瓶颈说起为什么BVH的存储问题值得死磕做图形学和实时渲染的人迟早会撞上BVH这堵墙。BVHBounding Volume Hierarchy层次包围盒是光线追踪、碰撞检测、视锥剔除这些场景里绕不开的空间加速结构。它的核心思路很朴素把场景里的几何体一层层包进越来越大的盒子里查询的时候先测大盒子大盒子不命中就整枝剪掉省掉大量无谓的求交计算。听起来很美但真正上手写过BVH的人都知道这东西的内存占用能轻松吃掉你大半的显存预算。问题出在结构本身。一棵标准的二叉树BVH每个内部节点要存两个子指针、一个包围盒通常是AABB六个float叶子节点还要存图元索引和数量。节点一多光是结构开销就非常可观。我做过一个测试场景大约两百万个三角形用传统的SAHSurface 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分开存成SoAStructure of Arrays布局这样一次可以处理四个顶点的同一个分量。虽然总字节数没变但遍历时的向量化效率高很多。具体布局是数组vx[4]、vy[4]、vz[4]每个数组四个float总共十二个float。这样加载一个四面体笼就是三次SIMD加载每次加载四个float非常规整。注意四面体笼的顶点顺序会影响相交测试的符号判断。建议在构建时统一按右手定则排列保证四个面的法线朝外。否则遍历时会出现内外判断反转的bug而且这种bug很难查因为渲染结果可能只是局部漏光或者阴影错误。3.2 构建流程的改造从SAH到四面体拟合传统BVH构建用SAHSurface 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和CUDACPU端做构建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。结果如下表。方案节点数每节点字节总内存构建时间遍历时间纯AABB290万3293MB1.2s8.0ms纯四面体198万56111MB1.7s7.2ms混合215万4495MB1.4s7.5ms纯四面体方案节点数降了百分之三十二但每节点字节从三十二涨到五十六总内存反而涨了。这说明单纯换包围体不一定省内存关键在于节点数的下降幅度能否抵消每节点字节的增加。混合方案在浅层用四面体笼因为浅层节点少但覆盖范围大四面体的紧致性收益高深层用AABB因为深层节点多但每个节点覆盖的图元少AABB的存储优势明显。混合方案的总内存和纯AABB持平但遍历时间降了百分之六。后来我优化了四面体笼的存储把四个顶点的坐标从float换成半精度floatfp16每节点字节从五十六降到四十。再测纯四面体方案总内存降到七十九兆比纯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 常见问题速查表问题现象可能原因排查方法解决方案渲染出现黑色像素四面体退化漏判检查四面体体积体积过小回退AABB构建时间过长凸包计算慢统计各阶段耗时预聚类并行构建遍历出现亮线数值不稳定检查除法epsilon加epsilon和范围检查内存反而增加节点字节增加过多对比节点数和字节数混合方案或半精度存储遍历速度下降分支发散严重分析warp执行效率屏幕空间分块排序射线5.5 独家避坑技巧第一个技巧在构建四面体笼之前先对图元做一次方向分析。如果图元的主方向集中在三个轴附近直接用AABB不要用四面体笼。方向分析可以用PCA算图元法线的协方差矩阵如果特征值差异很大说明方向集中AABB更合适。这个预判能避免在不适用的场景上浪费时间。第二个技巧四面体笼的四个顶点顺序在构建时确定后遍历时不要重新排序。我试过在遍历时根据射线方向动态调整顶点顺序来加速测试结果因为分支发散和额外的排序开销反而慢了。固定顺序让编译器优化效果更好。第三个技巧如果项目里同时有CPU和GPU的遍历四面体笼的存储布局要统一。CPU端用AoSGPU端用SoA构建时生成两份数据。虽然内存多占一份但避免了遍历时的转换开销。转换开销在实时渲染里很致命宁可多占内存也不要每次遍历都转换。6. 迁移建议与扩展思路如果你手头有现成的BVH项目想迁移到四面体笼方案我的建议是分步走。第一步先实现四面体笼的拟合和相交测试在离线渲染器里验证正确性对比AABB的结果确保没有漏判和误判。第二步在构建流程里加入四面体笼但保留AABB作为回退用混合方案跑起来测内存和性能。第三步根据实测数据决定是否全面切换到四面体笼或者继续用混合方案。不要一上来就全换风险太大。扩展思路上四面体笼可以和其他的BVH优化技术结合。比如和压缩节点结合把四面体顶点用增量编码压缩进一步降低每节点字节。或者和宽BVH结合每个节点放多个四面体笼减少树深度。还可以和动态BVH结合用四面体笼的拟合速度优势做实时更新。这些方向我都试过一些效果不一但都值得探索。最后分享一个小技巧四面体笼的拟合代码可以单独抽出来做成一个工具库输入一组点输出最小体积四面体。这个工具库不仅能用在BVH上还能用在碰撞检测的包围体生成、点云的分区、甚至三维重建的网格简化上。我把它用在了一个点云配准的项目里用四面体笼做粗配准的包围体配准速度提升了百分之二十。所以别把四面体笼只看成BVH的优化它本质上是一种紧致包围体的生成方法应用面比你想的广。