Linear BVH

GPGPU

Arch

放一张Turing架构的美图

SIMT vs. SIMD

SIMD全称为“Single Instruction Multiple Data”，即单指令多数据。在这种模型中，同一个指令会被同时应用于多个数据元素上进行处理。通常情况下，这些数据元素需要具有相同的类型和长度，并且可以通过向量寄存器等特殊硬件来实现高效地并行计算。

不同于我们之前介绍的SIMD，SIMT全称为“Single Instruction Multiple Thread”，即单指令多线程。在这种模型中，大量的线程被分配到不同的处理器核心上，并且每个核心都可以同时执行相同的指令，但是操作数据和内存时可以独立进行。这样就能够实现高效地并行计算。

Divergence

看到这里你可能会想SIMD毕竟只是一个指令而已，SIMT可是真正分配了线程，难道不能做到不同的线程干不同的事情？换句话说，一个if语句就给一个wrap干寄了呀！事实上这不会发生，因为我们有Divergence.（aka.线程组分歧）

例如，如果在一个32线程的线程块中，如果有16个线程满足if语句的条件，则CUDA会为这16个线程提供一个分支执行路径，并将另外16个不满足条件的线程放在另一个分支执行路径中。这种方法可以提高线程的并行执行效率。

鱼和熊掌不能兼得，Divergence会产生一些性能问题，在实际生产中，人们会使用一些策略来尽量减少以至于消除Divergence.

BVH

BVH(Bounding Volume Hierarchy)，即包围盒层次结构。它常用于计算机图形学中加速射线追踪的数据结构。BVH以树形结构的形式组织场景中的物体，每个节点表示一组物体的包围盒，根节点表示整个场景的包围盒。通过检测射线与包围盒的交点，BVH可以快速地确定射线与场景中的哪些物体相交，从而加速射线追踪算法的运算速度。

通常来说，每个BVH Node包括两个BVH Node指针/索引和自身的包围盒，哦对，对于子节点而言，会映射到最终的数据，也要存一个数据的指针/索引。总结下来，常见结构如下:

struct Node
{
    Node* lChild, *rChild;
    NodeBox box;
    Data* data = nullptr;
};

Build (SAH，Surface Area Heuristic)

仔细想想上面说的道理，那么如何划分左右孩子是个问题。我们简单介绍一种稍微好点的方法，叫SAH.

SAH基于这样的假设，包围盒表面积越大其被光线打到的几率越高，而且三角形越多计算量越大，我们要找到中间的平衡点，即求

$\min_d\left\{S_lN_l + S_rN_r\right\}$

此外考虑到我们的划分方向有三条 $x, y, z$ ，那么我们的逻辑有了

得到当前范围的包围盒，如果三角形数量小于阈值，就直接当作子节点返回
得到每个三角形的中心，存到数组里
SAH方法划分该包围盒，x,y,z轴分别遍历
1. 按照当前轴方向对三角形中心排序
2. 对上述排好序的数组依次枚举，作为划分点
$$
\left\{0, 1, ..., n\right\}\left\{n + 1, n + 2, ..., max\right\}
$$
1. 计算出包围盒，得到花费，记录
得到最低花费的划分轴和划分位置，递归调用该函数

Retrieve

我们假设已经得到了一棵BVH，我们该如何利用它加速光线相交判断呢？

这个就很简单了，大致思路是这样的

queue<Node*> que;
vector<Data*> testList;
que.push(root);
while(!que.empty())
{
    auto node = que.pop();
    if(node && node->intersectWith(light))
    {
        if(node->isLeaf())
        {
            testList.push_back(node->data);
        }
        else{
            que.push_back(que.lChild);
            que.push_back(que.rChild);
        }
    }
}

至于三角形如何和射线快速判交，有现成的Möller-Trumbore算法可以使用。

OpenMP

可以利用以下技术来简单加速一下构建过程

Task
Parallel Radix Sort
Parallel For

LBVH(1. BVH and GPGPU)