BVH树的构建与遍历

在计算机图形学中，BVH树是一种空间划分的数据结构，广泛运用于光线追踪。今天来讲述一下它的建立和遍历方法。

BVH树的建立

BVH树的建立分为以下几步：
1.遍历当前场景中的所有物体，存储下它们的每一个图元（primitive，例如三角形、圆形等）；对每一个图元，计算它们的包围盒。
2.递归构建BVH树。
BVH树是一种二叉树，每一个节点记录了它自己的包围盒。对于叶子节点，它存储了它所包含的所有图元；对于非叶子节点，记录了它所包含的孩子节点。节点的定义如下：

struct BVHBuildNode {
    BVHBuildNode* children[2];
    BoundingBox boundingbox;
    int splitAxis, firstPrimeOffset, nPrimitives;
    void initLeaf(int first, int n, const BoundingBox&b);
    void initInterior(int axis, BVHBuildNode*c0, BVHBuildNode*c1);
};

接下来展示递归建立BVH树的代码：

BVHBuildNode* BVHManager::recursiveBuild(int start, int end, int* totalnodes, std::vector<Primitive*>& ordered_prims)
{
    BVHBuildNode* node = nullptr;
    (*totalnodes)++;
    int nPrimitives = end - start;
    BoundingBox bounds;
    for (int i = start; i < end; i++)
        bounds = BoundingBox::Union(bounds, primitives[i]->getBoundingBox());
    if (nPrimitives == 1)
        node = createLeafNode(start, end, totalnodes, ordered_prims, bounds);
    else if(nPrimitives > 1)
    {
        int dim = bounds.maximumExtent();
        if(bounds.getTopFromDim(dim)==bounds.getBottomFromDim(dim))
            node = createLeafNode(start, end, totalnodes, ordered_prims, bounds);
        else
        {
            int mid = partitionPrimitivesWithSAH(start, end, dim, bounds);
            if(mid < 0)
                node = createLeafNode(start, end, totalnodes, ordered_prims, bounds);
            else {
                node = new BVHBuildNode;
                node->initInterior(dim,
                    recursiveBuild(start, mid, totalnodes, ordered_prims),
                    recursiveBuild(mid, end, totalnodes, ordered_prims));
            }
        }
    }
    return node;
}

这里最重要的步骤就是给定一个节点及其包围盒，如何对它进行空间划分。在这里我们采用SAH（Surface Area Heuristic）算法。该算法首先寻找boundingbox中跨度最长的一个轴作为用来分割的轴，然后沿着该轴N等分为一个个块，最后根据代价公式遍历每一个块，如图所示：

我们要做的是寻找出从哪一个块开始分割，使得代价最小。代价公式如下所示：

A和B是由当前的包围盒分割出的两个子模块，t^(trav)和t^(isect)我们可以当做是常数，pA和pB代表光线打到两个子块的概率，我们用两个子块相对于父亲的面积来计算。
这样一来，就可以写出计算SAH的代码：

int BVHManager::partitionPrimitivesWithSAH(int start, int end, int dim, BoundingBox& bounds)
{
    int nPrimitives = end - start;
    int nBuckets = BVHManager::nBuckets;
    if (nPrimitives <= 4)
        return partitionPrimitivesWithEquallySizedSubsets(start, end, dim);
    else
    {
        for (int i = start; i < end; i++)
        {
            BoundingBox prim_bounds = primitives[i]->getBoundingBox();
            int b = nBuckets * 
                (prim_bounds.getCenterValFromDim(dim) - bounds.getBottomFromDim(dim)) /
                (bounds.getTopFromDim(dim) - bounds.getBottomFromDim(dim));
            if (b == nBuckets)
                b--;
            buckets[b].count++;
            buckets[b].bounds = BoundingBox::Union(buckets[b].bounds, prim_bounds);
        }
        float cost[BVHManager::nBuckets - 1];
        for (int i = 0; i < nBuckets - 1; i++)
        {
            BoundingBox b0, b1;
            int count0 = 0, count1 = 0;
            for (int j = 0; j <= i; j++)
            {
                b0 = BoundingBox::Union(b0, buckets[j].bounds);
                count0 += buckets[j].count;
            }

            for (int j = i+1; j < BVHManager::nBuckets; j++)
            {
                b1 = BoundingBox::Union(b1, buckets[j].bounds);
                count1 += buckets[j].count;
            }
            float val0 = count0 ? count0 * b0.surfaceArea() : 0.0f;
            float val1 = count1 ? count1 * b1.surfaceArea() : 0.0f;

            cost[i] = 0.125f + (val0 + val1) / bounds.surfaceArea();
        }

        float min_cost = cost[0];
        int min_ind = 0;
        for (int i = 0; i < BVHManager::nBuckets -1; i++)
        {
            if (cost[i] < min_cost)
            {
                min_cost = cost[i];
                min_ind = i;
            }
        }
        if (nPrimitives > maxPrimsInNode || min_cost < nPrimitives)
        {
            Primitive** p = std::partition(&primitives[start], &primitives[end - 1] + 1,
                [=](const Primitive* pi) {
                int b = nBuckets *
                    (pi->getBoundingBox().getCenterValFromDim(dim) - bounds.getBottomFromDim(dim)) /
                    (bounds.getTopFromDim(dim) - bounds.getBottomFromDim(dim));
                if (b == nBuckets)
                    b--;
                return b <= min_ind;
            });
            return p - &primitives[0];
        }
        else
            return -1;
    }
}

BVH树的构建与遍历

原文：https://www.cnblogs.com/wickedpriest/p/12269564.html