空间求交加速-BVH（Unity CPU/GPU）

起

    需要求解射线与Mesh交点。但三角面太多，算法效率低下,Log(n)。

承

    通过网上大致了解BVH。我以自己的方法实现最简单BVH，将被求交的空间对象——三角面array，通过不断二分（二分策略为沿着最长轴切半），获得AABB包围盒（以下简称BBox），到一定深度后，记录每个叶子节点下对应的三角面的leafArray。于是求交变成了先与Log2(n)的BBox求交，最后遍历leafArray三角面求交。

由于与BBox求交远比三角面求交简单，所以省不少。

例如Mesh有1024个三角面，如果我们构建10层的BVH树，那么最优情况下我们只需要沿着BVH树，求交10次BBox，就能确定交到哪个三角形；如果我们构建9层，那么最优只需求交9次BBox，遍历求交1个或2个三角形...

PS:左右子节点的BBox不一定包含同数量三角面，也可能相交。

转

即使与这个节点的BBox相交，也不一定会交在这个bbox内。

具体都在图里了。如果一下看不懂也不用在意，因为实现的时候会很自然地碰到，并知道怎么做。

如果没有考虑这个情况地话，实际会是这样：

合

最后我将算法在Unity中用CPU和GPU端都实现了一遍(c#脚本和ComputeShader)。CPU端用来离线构建BVH，生成树信息后，用来实时进行BVHTrace，使得渲染速度大符上升。

我还将BVH用于加速其他射线检测，以实现加速离线烘培Mesh SDF,AO,软阴影等...

其他

我的BVH划分策略比较简单，并且带leafArray。这是为了移植算法到ComputeShader不得以的。如果不考虑快速兼容GPU，这种算法划分不足以应付一些特殊情况。即使是GPU，我也没有确定一个比较合理的BVH树深度设置策略，导致深度不同，效率vary巨大。

BVH划分算法是一个还没有研究透的领域，各种算法层出不穷，大家自己选择最适合的就行。

最后给上我的代码地址：https://gitee.com/ouerkakachango/UnityRayTrace