首页 计算机图形学 C++ 渲染引擎开发

[toc]

# BVH

简单 BVH 图示

# BVH 性质

  • 图元是叶子节点
  • 每个图元只在一个层次中出现过
  • 一个图元可能存在于多个空间划分中
  • 节点数量有界

# BVH 构建

SplitMethod : 构建 BVH 的方法

1
enum class SplitMethod { SAH,HLBVH,Middle,EquialCounts }

# 三个阶段

  1. 计算每个图元的边界信息，并保存到将用于构建 BVH 树的数组中
  2. 用选择的 SplitMethod 编码方法进行树的构建
  3. 将 BVH 树转换为无指针且紧凑的表示以供渲染使用
  4. 划分时需要保证图元边界的交叉尽可能的小

# 构建算法

# BVHPrimitiveInfo

初始化 BVH 中的每个图元信息

1
2
3
4
5
6
7
8
9
10
11
// BVHAccel Local Declarations
struct BVHPrimitiveInfo {
    BVHPrimitiveInfo() {}
    BVHPrimitiveInfo(size_t primitiveNumber, const Bounds3f &bounds)
        : primitiveNumber(primitiveNumber),
          bounds(bounds),
          centroid(.5f * bounds.pMin + .5f * bounds.pMax) {}
    size_t primitiveNumber;
    Bounds3f bounds;
    Point3f centroid;
};

该结构记录了图元的包围盒信息 / 中心 / 以及图元在列表中的 Id 等信息 所有的图元按照图圆的输入顺序在 BVHAccel 中进行初始化

1
2
3
4
5
// Initialize _primitiveInfo_ array for primitives
std::vector<BVHPrimitiveInfo> primitiveInfo(primitives.size());
for (size_t i = 0; i < primitives.size(); ++i)
    primitiveInfo[i] = {i, primitives[i]->WorldBound()};

其中 WorldBound() 函数是用来获取图元的 AABB 包围盒

选择对应的 Bvh 初始化算法进行构建

1
2
3
4
5
6
7
std::vector<std::shared_ptr<Primitive>> orderedPrims;
orderedPrims.reserve(primitives.size());
BVHBuildNode *root;
if (splitMethod == SplitMethod::HLBVH)
    root = HLBVHBuild(arena, primitiveInfo, &totalNodes, orderedPrims);
else
    root = recursiveBuild(arena, primitiveInfo, 0, primitives.size(),

除了HLBVH算法单独编写外,其他三种BVH的构建都由recursiveBuild负责

BVHBuildNode

BVHBuildNode 表示一个 BVH 节点，每个节点都存有一个 Bounds 来表示包围盒，所有 Node 节点通过 MemoryArena 分配内存

# MemoryArena

构建 BVH 节点有这样一行代码:

1
BVHBuildNode *node = arena.Alloc<BVHBuildNode>();

其中 Alloc 代码是这样

1
2
3
4
5
6
7
template <typename T>
T *Alloc(size_t n = 1, bool runConstructor = true) {
    T *ret = (T *)Alloc(n * sizeof(T));
    if (runConstructor)
        for (size_t i = 0; i < n; ++i) new (&ret[i]) T();
    return ret;
}

内部会根据对齐规则对内存进行分配，分配的方式是直接在 MemoryArena 内部记录所有的内存，通过管理空闲块来进行新内存的分配，即自己编写的 malloc

# BVHBuildNode

  • 每个 BVHBuildNode 都保存有 2 个孩子节点的指针槽
  • 每个 BVHBuildNode 都保存有该节点的 Bounds

其中存储孩子节点的引用后，还会保存孩子节点的起始下标的总共有多少个图元 (以保证内存排布的紧凑)

recursiveBuild

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
BVHBuildNode *BVHAccel::recursiveBuild(
    MemoryArena &arena, std::vector<BVHPrimitiveInfo> &primitiveInfo, int start,
    int end, int *totalNodes,
    std::vector<std::shared_ptr<Primitive>> &orderedPrims) {
    CHECK_NE(start, end);
    BVHBuildNode *node = arena.Alloc<BVHBuildNode>();
    (*totalNodes)++;
    // Compute bounds of all primitives in BVH node
    Bounds3f bounds;
    for (int i = start; i < end; ++i)
        bounds = Union(bounds, primitiveInfo[i].bounds);
    int nPrimitives = end - start;
    if (nPrimitives == 1) {
        // Create leaf _BVHBuildNode_
        int firstPrimOffset = orderedPrims.size();
        for (int i = start; i < end; ++i) {
            int primNum = primitiveInfo[i].primitiveNumber;
            orderedPrims.push_back(primitives[primNum]);
        }
        node->InitLeaf(firstPrimOffset, nPrimitives, bounds);
        return node;
    } else {
        // Compute bound of primitive centroids, choose split dimension _dim_
        Bounds3f centroidBounds;
        for (int i = start; i < end; ++i)
            centroidBounds = Union(centroidBounds, primitiveInfo[i].centroid);
        int dim = centroidBounds.MaximumExtent();

        // Partition primitives into two sets and build children
        int mid = (start + end) / 2;
        if (centroidBounds.pMax[dim] == centroidBounds.pMin[dim]) {
            // Create leaf _BVHBuildNode_
            int firstPrimOffset = orderedPrims.size();
            for (int i = start; i < end; ++i) {
                int primNum = primitiveInfo[i].primitiveNumber;
                orderedPrims.push_back(primitives[primNum]);
            }
            node->InitLeaf(firstPrimOffset, nPrimitives, bounds);
            return node;
        } else {
            // Partition primitives based on _splitMethod_
            switch (splitMethod) {
            case SplitMethod::Middle: {
                // Partition primitives through node's midpoint
                Float pmid =
                    (centroidBounds.pMin[dim] + centroidBounds.pMax[dim]) / 2;
                BVHPrimitiveInfo *midPtr = std::partition(
                    &primitiveInfo[start], &primitiveInfo[end - 1] + 1,
                    [dim, pmid](const BVHPrimitiveInfo &pi) {
                        return pi.centroid[dim] < pmid;
                    });
                mid = midPtr - &primitiveInfo[0];
                // For lots of prims with large overlapping bounding boxes, this
                // may fail to partition; in that case don't break and fall
                // through
                // to EqualCounts.
                if (mid != start && mid != end) break;
            }
            case SplitMethod::EqualCounts: {
                // Partition primitives into equally-sized subsets
                mid = (start + end) / 2;
                std::nth_element(&primitiveInfo[start], &primitiveInfo[mid],
                                 &primitiveInfo[end - 1] + 1,
                                 [dim](const BVHPrimitiveInfo &a,
                                       const BVHPrimitiveInfo &b) {
                                     return a.centroid[dim] < b.centroid[dim];
                                 });
                break;
            }
            case SplitMethod::SAH:
            default: {
                // Partition primitives using approximate SAH
                if (nPrimitives <= 2) {
                    // Partition primitives into equally-sized subsets
                    mid = (start + end) / 2;
                    std::nth_element(&primitiveInfo[start], &primitiveInfo[mid],
                                     &primitiveInfo[end - 1] + 1,
                                     [dim](const BVHPrimitiveInfo &a,
                                           const BVHPrimitiveInfo &b) {
                                         return a.centroid[dim] <
                                                b.centroid[dim];
                                     });
                } else {
                    // Allocate _BucketInfo_ for SAH partition buckets
                    PBRT_CONSTEXPR int nBuckets = 12;
                    BucketInfo buckets[nBuckets];

                    // Initialize _BucketInfo_ for SAH partition buckets
                    for (int i = start; i < end; ++i) {
                        int b = nBuckets *
                                centroidBounds.Offset(
                                    primitiveInfo[i].centroid)[dim];
                        if (b == nBuckets) b = nBuckets - 1;
                        CHECK_GE(b, 0);
                        CHECK_LT(b, nBuckets);
                        buckets[b].count++;
                        buckets[b].bounds =
                            Union(buckets[b].bounds, primitiveInfo[i].bounds);
                    }

                    // Compute costs for splitting after each bucket
                    Float cost[nBuckets - 1];
                    for (int i = 0; i < nBuckets - 1; ++i) {
                        Bounds3f b0, b1;
                        int count0 = 0, count1 = 0;
                        for (int j = 0; j <= i; ++j) {
                            b0 = Union(b0, buckets[j].bounds);
                            count0 += buckets[j].count;
                        }
                        for (int j = i + 1; j < nBuckets; ++j) {
                            b1 = Union(b1, buckets[j].bounds);
                            count1 += buckets[j].count;
                        }
                        cost[i] = 1 +
                                  (count0 * b0.SurfaceArea() +
                                   count1 * b1.SurfaceArea()) /
                                      bounds.SurfaceArea();
                    }

                    // Find bucket to split at that minimizes SAH metric
                    Float minCost = cost[0];
                    int minCostSplitBucket = 0;
                    for (int i = 1; i < nBuckets - 1; ++i) {
                        if (cost[i] < minCost) {
                            minCost = cost[i];
                            minCostSplitBucket = i;
                        }
                    }

                    // Either create leaf or split primitives at selected SAH
                    // bucket
                    Float leafCost = nPrimitives;
                    if (nPrimitives > maxPrimsInNode  minCost < leafCost) {
                        BVHPrimitiveInfo *pmid = std::partition(
                            &primitiveInfo[start], &primitiveInfo[end - 1] + 1,
                            [=](const BVHPrimitiveInfo &pi) {
                                int b = nBuckets *
                                        centroidBounds.Offset(pi.centroid)[dim];
                                if (b == nBuckets) b = nBuckets - 1;
                                CHECK_GE(b, 0);
                                CHECK_LT(b, nBuckets);
                                return b <= minCostSplitBucket;
                            });
                        mid = pmid - &primitiveInfo[0];
                    } else {
                        // Create leaf _BVHBuildNode_
                        int firstPrimOffset = orderedPrims.size();
                        for (int i = start; i < end; ++i) {
                            int primNum = primitiveInfo[i].primitiveNumber;
                            orderedPrims.push_back(primitives[primNum]);
                        }
                        node->InitLeaf(firstPrimOffset, nPrimitives, bounds);
                        return node;
                    }
                }
                break;
            }
            }
            node->InitInterior(dim,
                               recursiveBuild(arena, primitiveInfo, start, mid,
                                              totalNodes, orderedPrims),
                               recursiveBuild(arena, primitiveInfo, mid, end,
                                              totalNodes, orderedPrims));
        }
    }
    return node;
}

如果是最后一个图元，则标记为叶子节点

1
2
3
4
5
6
7
8
9
10
if (nPrimitives == 1) {
    // Create leaf _BVHBuildNode_
    int firstPrimOffset = orderedPrims.size();
    for (int i = start; i < end; ++i) {
        int primNum = primitiveInfo[i].primitiveNumber;
        orderedPrims.push_back(primitives[primNum]);
    }
    node->InitLeaf(firstPrimOffset, nPrimitives, bounds);
    return node;
}

然后再判断是否是叶子节点，是的话，构建叶子节点，否则 第一步，获取长度最长的维度，按最长的维度来进行 BVH 的划分

1
2
3
4
Bounds3f centroidBounds;
for (int i = start; i < end; ++i)
    centroidBounds = Union(centroidBounds, primitiveInfo[i].centroid);
int dim = centroidBounds.MaximumExtent();

第二部，计算中点

1
int mid = (start + end) / 2;

第三步，开始构建 BVH

3.1 如果当前轴 dim 的最大值等于最小值的话，记为叶子节点

1
2
3
4
5
6
7
8
9
10
if (centroidBounds.pMax[dim] == centroidBounds.pMin[dim]) {
    // Create leaf _BVHBuildNode_
    int firstPrimOffset = orderedPrims.size();
    for (int i = start; i < end; ++i) {
        int primNum = primitiveInfo[i].primitiveNumber;
        orderedPrims.push_back(primitives[primNum]);
    }
    node->InitLeaf(firstPrimOffset, nPrimitives, bounds);
    return node;
}

3.2 按照 splitMethod 进行 BVH 的划分 3.2.1 计算图元组的中心 (对应维度)

1
2
Float pmid =
    (centroidBounds.pMin[dim] + centroidBounds.pMax[dim]) / 2;

3.2.2 使用 partition 将图元组划分为两个区间

1
2
template< class BidirIt, class UnaryPredicate >
BidirIt partition( BidirIt first, BidirIt last, UnaryPredicate p );

partition: 从首地址开始到最终地址，使用 p 对该区间进行划分，划分为满足与不满足的两个区间，同时返回第二个区间的手首地址指针

1
2
3
4
5
6
7
8
9
10
11
BVHPrimitiveInfo *midPtr = std::partition(
    &primitiveInfo[start], &primitiveInfo[end - 1] + 1,
    [dim, pmid](const BVHPrimitiveInfo &pi) {
        return pi.centroid[dim] < pmid;
    });
mid = midPtr - &primitiveInfo[0];
// For lots of prims with large overlapping bounding boxes, this
// may fail to partition; in that case don't break and fall
// through
// to EqualCounts.
if (mid != start && mid != end) break;

其中，Middle 划分算法的 Predicate 是如果当前节点在对应维度上的中点到该 Bounds 的中点小于当前 Bounds 维度的一半，则移动到满足区间 注意，最下面的:

1
if (mid != start && mid != end) break;

表示的是，Middle 划分方法如果发现几个 (大于 2) 图元有巨大的重叠包围框，Middle 方法可能无法将图元划分为两组 (即 midstart 或者 end), 这种情况下，就自行 Break, 尝试进行 SplitMethod::EqualCounts 方法再试一次

EqualCounts

1
2
3
4
5
6
7
8
9
// Partition primitives into equally-sized subsets
mid = (start + end) / 2;
std::nth_element(&primitiveInfo[start], &primitiveInfo[mid],
                 &primitiveInfo[end - 1] + 1,
                 [dim](const BVHPrimitiveInfo &a,
                       const BVHPrimitiveInfo &b) {
                     return a.centroid[dim] < b.centroid[dim];
                 });
break;

使用 n_th_element
它对数组排序使得中点指针处元素的位置是，如果数组完全排序，则所有中点之前的元素都比中点元素小且所有后面的元素都比它大。

# SAH 表面积启发式优化

上面的 Middle 划分对某些图元的划分效果不错，但实际应用中它们通常会选择性能较差的划分，导致光线要访问树的更多节点，因此带来渲染时不必要的低效光线 - 图元相交计算。 SAH 主要用来解决 大量图元划分方案中,哪个方案能带来来更好的划分方案/选择哪个划分空间可以带来更好的加速结构?
该模型有以下几个特征:
- 1. 估计执行光线相交测试的开销，包括穿行树的节点花的时间和为特定的图元划分进行光纤 - 图元相交测试花的时间 - 2. 得到每次构建的最小花销 - 3. 贪婪法构建每个层次节点最小化开销