项目代码仓库：
GitHub：https://github.com/AKGWSB/EzRT
gitee：https://gitee.com/AKGWSB/EzRT
在 GPU 上实现光线追踪！
在差不多半年之前，我在 光线追踪渲染实战 中讨论并实现了简单的光线追踪，用 c++ 和多线程在 cpu 上最简单的计算，不过仅支持简单的三角形和球作为图元
时过境迁，摆弄这些精致的球体已不再新颖，为了高效遍历大量三角形，这篇 光线追踪加速遍历结构 学习并且讨论了 BVH 这种加速遍历数据结构，同时给出了 c++ 的简单实现和可视化的代码
如果说前两篇博客是 mc 中的木镐，石镐的话，今天我们就敲把铁镐，顺便把 GPU 放在火上烤一烤：
唔，大概说一下思路把：用的是 OpenGL 的 fragment shader 逐像素计算光追，然后三角形和 BVH 结构还有材质等信息，编码一下塞到纹理里面传给 shader，然后嗯算就完事了
hhh 核心部分很简单，就是把原来的 c++ 代码移植一下，搞到 GLSL 里面运行。emmm 这不是经典的大象塞进冰箱嘛。事实上为此我花费很多时间来解决各种百家争鸣的 bug
好在困难的时期已经过去了，翻过这座山… 好了。。。不扯闲话了，做好准备，我们要再一次进入波与粒的世界！
注：
该部分不涉及任何原理，代码讲解
涉猎该部分列出的前置知识，才能比较顺利的阅读本篇博客，以至于看到代码的时候不至于一头雾水 hhh
环境
visual studio 2019，数学库用 glm，然后 OpenGL 用 glew，窗口管理用 freeglut，图像读取用 SOIL2，关于怎么在 vs 上安装第三方库，可以使用 vcpkg 进行包管理，具体用法参考 我之前的博客
OpenGL
因为是基于 GLSL 的实现，那么首先对 OpenGL 得有一定的了解。常见的概念，比如绘制流程，着色器，坐标变换等。常见的操作，比如缓冲区对象，传送纹理，传递 uniform 一致变量等等。关于 OpenGL 的教程，最经典的莫过于 Learn OpenGL 了。当然也顺便推销下我自己的 专栏，尽管它费拉不堪…
GLSL
然后，片段着色器不是简单的输出重心插值后的顶点颜色。我们要在 fragment shader 中洋洋洒洒编写将近 114514e1919 行的代码来进行一个光的追，所以需要了解 GLSL 的语法规范，函数接口，uniform 变量，纹理，采样等操作
简单的几何学
和三角形求交，和轴对齐包围盒 AABB 长方体盒子求交，三角形重心插值等数学几何原理。和三角形求交的原理，和 AABB 求交…
路径追踪
一个点的颜色并不是由魔法确定的，而是通过渲染方程进行积分求解。每次积分逐像素递归求解光路直到碰到光源为止。原理和代码参考：光线追踪渲染实战
片段着色器会对每个像素进行一次计算，并且是在 GPU 上并行的，这正好满足我们的要求：并行与逐像素计算！我们用它来计算光线追踪的颜色！
利用片元着色器计算每个像素，首先我们绘制一个正方形铺满整个屏幕，作为我们的画布：
不需要任何的变换矩阵，直接将 6 个顶点固定到 NDC space，即 [-1, 1] 的范围，c++ 的代码很简单：
std::vector<vec3> square = {
vec3(-1, -1, 0), vec3(1, -1, 0), vec3(-1, 1, 0),
vec3(1, 1, 0), vec3(-1, 1, 0), vec3(1, -1, 0)
};
// 生成 vao vbo , 传送数据，绘制
...
顶点着色器直接传递顶点的 NDC 坐标作为像素的片元坐标，pix 变量的范围 [-1, 1]，在片段着色器中尝试输出像素的坐标 pix 作为颜色。当看到如下的图像，说明画布有在正常工作：
注：
这部分的代码相当无聊，我们是在为 shader 准备数据
如果您比较关心路径追踪的 GLSL 实现，那么大可跳过该部分
和以往的光线追踪程序不同，计算发生在 GPU 端。向 shader 中传递数据有很多种方式，uniform 数组，uniform buffer 等等，但是这些方式都存在数目限制，无法传送大量的数据
回想我们是怎么将图片传送到 GPU 上的，没错，纹理！我们通过 c++ 将模型数据读取到内存，然后以纹理的形式将数据传送到显存，然后在 shader 中对纹理进行采样就可以读出原来的数据！
我们的数据通常是以 数组 形式进行传送，比如三角形数组，BVH 二叉树数组，材质数组等等。这些数组都是一维的，以方便我们用 下标 指针进行访问和采样
可是众所周知一般的图片纹理是二维的，通过一个 0 ~ 1 范围的 uv 坐标进行采样而不是下标。暂且不谈把一维数组折叠到二维纹理这种奇技淫巧，显卡电路中焊死的硬件双线性插值过滤器也会破坏数据的准确性
出于这些原因，OpenGL 提供了一种较为原始的传递方式，叫做 Buffer Texture，即使用纹理作为通用数据缓冲区。它允许我们直接将内存中的二进制数据搬运到显存中，然后通过一种特殊的采样器，也就是 samplerBuffer 来访问。
和一般的 sampler2D 不同，samplerBuffer 将纹理的内容（即显存中的原始数据）视为一维数组，可以通过 下标直接索引 数据，并且不会使用任何过滤器这刚好满足我们的需要！
关于 Buffer Texture 的用法，可以参照 OpenGL Wiki ，或者下面的简单例子。假设我们有一个数组要传送：
int n; // 数组大小
float triangles[];
我们首先需要创建一个缓冲区对象，叫做 texture buffer object，简称 tbo，这可以类比为显存中开辟了一块空间：
GLuint tbo;
glGenBuffers(1, &tbo);
glBindBuffer(GL_TEXTURE_BUFFER, tbo);
然后将数据塞进缓冲区中：
glBufferData(GL_TEXTURE_BUFFER, n * sizeof(float), &your_data[0], GL_STATIC_DRAW);
随后创建一块纹理，注意这时的纹理类型应该为 GL_TEXTURE_BUFFER 这表示我们开辟的不是图像纹理而是数据缓冲区纹理：
GLuint tex;
glGenTextures(1, &tex);
glBindTexture(GL_TEXTURE_BUFFER, tex);
然后用 glTexBuffer 将 tbo 中的数据关联到 texture buffer，这里我们使用 GL_RGB32F 的格式，这样一次访问可以取出一个 vec3 向量的数据。采样器的返回值有 RGB 三个通道，每个通道都是 32 位的浮点数：
glTexBuffer(GL_TEXTURE_BUFFER, GL_RGB32F, tbo);
最后传送 0 号纹理到着色器：
glActiveTexture(GL_TEXTURE0);
glUniform1i(glGetUniformLocation(program, "triangles"), 0);
然后在着色器端使用 texelFetch 和一个整数下标 index 进行 samplerBuffer 类型的纹理的查询：
uniform samplerBuffer triangles;
...
int index = xxx
vec3 data = texelFetch(triangles, index).xyz;
注意这里的数据格式 GL_RGB32F 指的是一个下标（一次采样）能读取到多少数据，即一格数据的单位。一个下标将会索引三个 32 位的浮点数，并且返回一个 vec4，但是仅有 rgb 分量有效。他们和内存数据的映射关系如下：
至此，我们已经掌握了在 GPU 上一次存取 12 字节（RGB32）内存数据的方法，但是我们的结构体不一定都是 12 字节对齐的
注：
也可以使用 GL_R32F 来每次读取一个 32 位浮点数，这样能够更加灵活的组织数据
但是显然一次读取一个 vec3 效率更高
以三角形和其材质为例，在 CPU 上 c++ 代码中他们的定义是这样的：
// 物体表面材质定义
struct Material {
vec3 emissive = vec3(0, 0, 0); // 作为光源时的发光颜色
vec3 baseColor = vec3(1, 1, 1);
float subsurface = 0.0;
float metallic = 0.0;
float specular = 0.0;
float specularTint = 0.0;
float roughness = 0.0;
float anisotropic = 0.0;
float sheen = 0.0;
float sheenTint = 0.0;
float clearcoat = 0.0;
float clearcoatGloss = 0.0;
float IOR = 1.0;
float transmission = 0.0;
};
// 三角形定义
struct Triangle {
vec3 p1, p2, p3; // 顶点坐标
vec3 n1, n2, n3; // 顶点法线
Material material; // 材质
};
注：
这里卖个关子…
算了，这里材质用的是 Disney 定义的 PBR 材质参数，下一章节中我们将实现 Disney principel’s BRDF，简单的说就是规范化的基于物理的渲染
编码三角形数据，我们创建结构体 Triangle_encoded，他们的数据类型都是 vec3 组成的，满足 12 字节对齐：
struct Triangle_encoded {
vec3 p1, p2, p3; // 顶点坐标
vec3 n1, n2, n3; // 顶点法线
vec3 emissive; // 自发光参数
vec3 baseColor; // 颜色
vec3 param1; // (subsurface, metallic, specular)
vec3 param2; // (specularTint, roughness, anisotropic)
vec3 param3; // (sheen, sheenTint, clearcoat)
vec3 param4; // (clearcoatGloss, IOR, transmission)
};
然后准备编码数据，这部分的 c++ 代码相当无聊，就是把数据倒腾来倒腾去：
// 读取三角形
std::vector<Triangle> triangles;
readObj()
int nTriangles = triangles.size();
...
// 编码 三角形, 材质
std::vector<Triangle_encoded> triangles_encoded(nTriangles);
for (int i = 0; i < nTriangles; i++) {
Triangle& t = triangles[i];
Material& m = t.material;
// 顶点位置
triangles_encoded[i].p1 = t.p1;
triangles_encoded[i].p2 = t.p2;
triangles_encoded[i].p3 = t.p3;
// 顶点法线
triangles_encoded[i].n1 = t.n1;
triangles_encoded[i].n2 = t.n2;
triangles_encoded[i].n3 = t.n3;
// 材质
triangles_encoded[i].emissive = m.emissive;
triangles_encoded[i].baseColor = m.baseColor;
triangles_encoded[i].param1 = vec3(m.subsurface, m.metallic, m.specular);
triangles_encoded[i].param2 = vec3(m.specularTint, m.roughness, m.anisotropic);
triangles_encoded[i].param3 = vec3(m.sheen, m.sheenTint, m.clearcoat);
triangles_encoded[i].param4 = vec3(m.clearcoatGloss, m.IOR, m.transmission);
}
然后利用 texture buffer 传送到 shader 中，这里创建 texture buffer object，然后将数据导入 tbo，然后创建纹理，将 tbo 和纹理绑定：
GLuint trianglesTextureBuffer;
GLuint tbo0;
glGenBuffers(1, &tbo0);
glBindBuffer(GL_TEXTURE_BUFFER, tbo0);
glBufferData(GL_TEXTURE_BUFFER, triangles_encoded.size() * sizeof(Triangle_encoded), &triangles_encoded[0], GL_STATIC_DRAW);
glGenTextures(1, &trianglesTextureBuffer);
glBindTexture(GL_TEXTURE_BUFFER, trianglesTextureBuffer);
glTexBuffer(GL_TEXTURE_BUFFER, GL_RGB32F, tbo0);
然后在 shader 中通过 texelFetch 解码数据，并且还原为原本的结构体，这部分的代码也相当无聊，同样是倒腾数据。只是注意访问纹理是以 vec3 为单位，编码后的三角形包含 12 个 vec3 向量，所以要通过下标计算每个下标对应的偏移，GLSL 代码如下：
#define SIZE_TRIANGLE 12
uniform samplerBuffer triangles;
...
// 获取第 i 下标的三角形
Triangle getTriangle(int i) {
int offset = i * SIZE_TRIANGLE;
Triangle t;
// 顶点坐标
t.p1 = texelFetch(triangles, offset + 0).xyz;
t.p2 = texelFetch(triangles, offset + 1).xyz;
t.p3 = texelFetch(triangles, offset + 2).xyz;
// 法线
t.n1 = texelFetch(triangles, offset + 3).xyz;
t.n2 = texelFetch(triangles, offset + 4).xyz;
t.n3 = texelFetch(triangles, offset + 5).xyz;
return t;
}
// 获取第 i 下标的三角形的材质
Material getMaterial(int i) {
Material m;
int offset = i * SIZE_TRIANGLE;
vec3 param1 = texelFetch(triangles, offset + 8).xyz;
vec3 param2 = texelFetch(triangles, offset + 9).xyz;
vec3 param3 = texelFetch(triangles, offset + 10).xyz;
vec3 param4 = texelFetch(triangles, offset + 11).xyz;
m.emissive = texelFetch(triangles, offset + 6).xyz;
m.baseColor = texelFetch(triangles, offset + 7).xyz;
m.subsurface = param1.x;
m.metallic = param1.y;
m.specular = param1.z;
m.specularTint = param2.x;
m.roughness = param2.y;
m.anisotropic = param2.z;
m.sheen = param3.x;
m.sheenTint = param3.y;
m.clearcoat = param3.z;
m.clearcoatGloss = param4.x;
m.IOR = param4.y;
m.transmission = param4.z;
return m;
}
然后尝试传输一个三角形和它的材质，在 shader 中输出它的颜色，顶点信息，或者任何属性以验证。如果成功读取颜色（或者其他数据，比如坐标）说明数据传输无误
首先是光线的定义：
// 光线
struct Ray {
vec3 startPoint;
vec3 direction;
};
然后我们还需要一个求交结果，它包含一些必要的信息，比如交点位置，距离和表面材质：
// 光线求交结果
struct HitResult {
bool isHit; // 是否命中
bool isInside; // 是否从内部命中
float distance; // 与交点的距离
vec3 hitPoint; // 光线命中点
vec3 normal; // 命中点法线
vec3 viewDir; // 击中该点的光线的方向
Material material; // 命中点的表面材质
};
三角形求交的部分也不难，首先是求解光线和三角形所在平面的距离 t，有了距离顺势求出交点 P，思路如下：
求出交点之后，判断交点是否在三角形内。这里通过叉乘的方向和法相是否同向来判断。如果三次叉乘都和 N 同向，说明 P 在三角形中：
代码也很简单，唯一值得注意的是如果视线方向 d 和三角形的法向 N 的方向相同，要翻转一下 N 以保证不管从正面还是背面击中三角形，我们都能获得正确的法向量。代码如下：
#define INF 114514.0
// 光线和三角形求交
HitResult hitTriangle(Triangle triangle, Ray ray) {
HitResult res;
res.distance = INF;
res.isHit = false;
res.isInside = false;
vec3 p1 = triangle.p1;
vec3 p2 = triangle.p2;
vec3 p3 = triangle.p3;
vec3 S = ray.startPoint; // 射线起点
vec3 d = ray.direction; // 射线方向
vec3 N = normalize(cross(p2-p1, p3-p1)); // 法向量
// 从三角形背后（模型内部）击中
if (dot(N, d) > 0.0f) {
N = -N;
res.isInside = true;
}
// 如果视线和三角形平行
if (abs(dot(N, d)) < 0.00001f) return res;
// 距离
float t = (dot(N, p1) - dot(S, N)) / dot(d, N);
if (t < 0.0005f) return res; // 如果三角形在光线背面
// 交点计算
vec3 P = S + d * t;
// 判断交点是否在三角形中
vec3 c1 = cross(p2 - p1, P - p1);
vec3 c2 = cross(p3 - p2, P - p2);
vec3 c3 = cross(p1 - p3, P - p3);
bool r1 = (dot(c1, N) > 0 && dot(c2, N) > 0 && dot(c3, N) > 0);
bool r2 = (dot(c1, N) < 0 && dot(c2, N) < 0 && dot(c3, N) < 0);
// 命中，封装返回结果
if (r1 || r2) {
res.isHit = true;
res.hitPoint = P;
res.distance = t;
res.normal = N;
res.viewDir = d;
// 根据交点位置插值顶点法线
float alpha = (-(P.x-p2.x)*(p3.y-p2.y) + (P.y-p2.y)*(p3.x-p2.x)) / (-(p1.x-p2.x-0.00005)*(p3.y-p2.y+0.00005) + (p1.y-p2.y+0.00005)*(p3.x-p2.x+0.00005));
float beta = (-(P.x-p3.x)*(p1.y-p3.y) + (P.y-p3.y)*(p1.x-p3.x)) / (-(p2.x-p3.x-0.00005)*(p1.y-p3.y+0.00005) + (p2.y-p3.y+0.00005)*(p1.x-p3.x+0.00005));
float gama = 1.0 - alpha - beta;
vec3 Nsmooth = alpha * triangle.n1 + beta * triangle.n2 + gama * triangle.n3;
Nsmooth = normalize(Nsmooth);
res.normal = (res.isInside) ? (-Nsmooth) : (Nsmooth);
}
return res;
}
然后我们编写一个函数，暴力遍历三角形数组进行求交，返回最近的交点：
#define INF 114514.0
// 暴力遍历数组下标范围 [l, r] 求最近交点
HitResult hitArray(Ray ray, int l, int r) {
HitResult res;
res.isHit = false;
res.distance = INF;
for(int i=l; i<=r; i++) {
Triangle triangle = getTriangle(i);
HitResult r = hitTriangle(triangle, ray);
if(r.isHit && r.distance<res.distance) {
res = r;
res.material = getMaterial(i);
}
}
return res;
}
然后我们配置一下相机，相机位于 vec3(0, 0, 4)，看向 z 轴负方向，根据画布像素的 NDC 坐标来投射射线。这里投影平面长宽均为 2.0，而 zNear 为 2.0，这保证了 50° 左右的视场角：
代码如下：
Ray ray;
ray.startPoint = vec3(0, 0, 4);
vec3 dir = vec3(pix.xy, 2) - ray.startPoint;
ray.direction = normalize(dir);
然后用刚刚写的 hitArray 遍历数组，求交点的同时返回表面的颜色：
uniform int nTriangles;
...
HitResult res = hitArray(ray, 0, nTriangles-1);
if(res.isHit) fragColor = vec4(res.material.color, 1);
三角形… 已经看的足够多次了…
读取一个 Stanford Bunny 的 obj 模型再试一下：
ohhhh 虽然是暴力遍历 4000 多个三角形，但是因为 GPU 强大的并行能力，我们能够维持 4 ~ 5 的 FPS
我们成功遍历三角形，但是我们需要更加高效的遍历，BVH 树是一个不错的选择。但是在 GLSL 中 没有指针 这一概念，我们需要将使用 指针 的树形结构改为使用 数组下标 作为指针的线性化二叉树。相信学过数据结构的童鞋都对此不陌生…
这是原来的 BVH 节点结构体，内容分为三部分，分别是左右孩子，AABB 碰撞盒，叶子节点信息，其中 AA 为极小点，BB 为极大点。因为不能用指针，只能用数组下标，我们将结构体改为：
// BVH 树节点
struct BVHNode {
int left, right; // 左右子树索引
int n, index; // 叶子节点信息
vec3 AA, BB; // 碰撞盒
};
这里还引入了一个小变化：一个叶子节点可以保存多个三角形，n 表示该叶子节点的三角形数目，index 表示该节点第一个三角形，在 triangles 数组中的索引：
线性化二叉树也很简单，只需要每次创建节点的时候，将 new Node() 改为 push_back() 即插入数组，而下标的索引方式是照常的。
这里我们允许一个叶子包含 n 个三角形，每次创建节点直接 push_back，然后通过下标进行索引。使用最简单的二分法创建，每次将三角形数组对半分！创建 BVH 的代码如下：
注：
这里仅给出普通的二分建树代码
SAH 优化版本的代码在下文 “完整代码” 部分可以找到
// 构建 BVH
int buildBVH(std::vector<Triangle>& triangles, std::vector<BVHNode>& nodes, int l, int r, int n) {
if (l > r) return 0;
// 注：
// 此处不可通过指针，引用等方式操作，必须用 nodes[id] 来操作
// 因为 std::vector<> 扩容时会拷贝到更大的内存，那么地址就改变了
// 而指针，引用均指向原来的内存，所以会发生错误
nodes.push_back(BVHNode());
int id = nodes.size() - 1; // 注意： 先保存索引
nodes[id] 的属性初始化 ...
// 计算 AABB
for (int i = l; i <= r; i++) {
... // 遍历三角形 计算 AABB
}
// 不多于 n 个三角形 返回叶子节点
if ((r - l + 1) <= n) {
nodes[id].n = r - l + 1;
nodes[id].index = l;
return id;
}
// 否则递归建树
// 按 x,y,z 划分数组
std::sort(...)
// 递归
int mid = (l + r) / 2;
int left = buildBVH(triangles, nodes, l, mid, n);
int right = buildBVH(triangles, nodes, mid + 1, r, n);
nodes[id].left = left;
nodes[id].right = right;
return id;
}
至此我们拥有一个线性化的二叉树，接下来准备将它送入 GPU
注：
该部分的代码也相当无聊，尽情跳过
和三角形数据类似，编码，然后传送：
struct BVHNode_encoded {
vec3 childs; // (left, right, 保留)
vec3 leafInfo; // (n, index, 保留)
vec3 AA, BB;
};
编码的过程太无聊了，不复制代码了。这里贴一下在 shader 中解码 BVHNode 的代码：
#define SIZE_BVHNODE 4
uniform samplerBuffer nodes;
// 获取第 i 下标的 BVHNode 对象
BVHNode getBVHNode(int i) {
BVHNode node;
// 左右子树
int offset = i * SIZE_BVHNODE;
ivec3 childs = ivec3(texelFetch(nodes, offset + 0).xyz);
ivec3 leafInfo = ivec3(texelFetch(nodes, offset + 1).xyz);
node.left = int(childs.x);
node.right = int(childs.y);
node.n = int(leafInfo.x);
node.index = int(leafInfo.y);
// 包围盒
node.AA = texelFetch(nodes, offset + 2).xyz;
node.BB = texelFetch(nodes, offset + 3).xyz;
return node;
}
读取一个兔子，然后遍历所有节点，对于每个叶子节点，遍历它包含的所有三角形，看看兔子是否完整，以验证 BVH 是否传输正确：
注：
这一步还是暴力遍历，没有二分遍历 bvh，只是为了验证数据是否正确
投射光线
...
for(int i=0; i<nNodes; i++) {
BVHNode node = getBVHNode(i);
if(node.n>0) {
int L = node.index;
int R = node.index + node.n - 1;
HitResult res = hitArray(ray, L, R);
if(res.isHit) fragColor = vec4(res.material.color, 1);
}
}
如果返回和 hitArray 一样的结果，说明我们 BVH 数据传输的没问题：
此外，在遍历之前，建议输出一下 1 号节点的左指针，不出意外应该是 2，将 node.left / 3 作为像素颜色输出，如果出现灰色说明正确，务必确保 整数下标 的传输无误！
对于轴对齐包围盒，光线穿入穿出 xoy，xoz，yoz 平面，会有三组穿入点穿出点。如果找到一组穿入点穿出点，使得光线起点距离穿入点的距离 小于 光线起点距离穿出点的距离，即 t0 < t1 则说明命中
我们取 out 中最小的距离记作 t1，和 in 中最大的距离记作 t0，然后看是否 t1 > t0 如果满足等式，则说明命中：
对应的 GLSL 代码如下：
// 和 aabb 盒子求交，没有交点则返回 -1
float hitAABB(Ray r, vec3 AA, vec3 BB) {
vec3 invdir = 1.0 / r.direction;
vec3 f = (BB - r.startPoint) * invdir;
vec3 n = (AA - r.startPoint) * invdir;
vec3 tmax = max(f, n);
vec3 tmin = min(f, n);
float t1 = min(tmax.x, min(tmax.y, tmax.z));
float t0 = max(tmin.x, max(tmin.y, tmin.z));
return (t1 >= t0) ? ((t0 > 0.0) ? (t0) : (t1)) : (-1);
}
注：
n 即近交点 near，也就是 in
f 即远交点 far，也就是 out
因为 in 和 out 在 GLSL 中是关键字不能用作变量名
接下来测试一下。对于 BVH 的根节点（1 号节点）我们分别和其左右子树求交，如果左子树命中则返回红色，右子树命中则返回绿色，两个都命中则返回黄色：
...
BVHNode node = getBVHNode(1);
BVHNode left = getBVHNode(node.left);
BVHNode right = getBVHNode(node.right);
float r1 = hitAABB(ray, left.AA, left.BB);
float r2 = hitAABB(ray, right.AA, right.BB);
vec3 color;
if(r1>0) color = vec3(1, 0, 0);
if(r2>0) color = vec3(0, 1, 0);
if(r1>0 && r2>0) color = vec3(1, 1, 0);
...
结果如下：
出现上述结果说明 BVH 的构建，传送和求交都没有问题
在 GPU 上面没有栈的概念，也不能执行递归程序，我们需要人为编写二叉树遍历的代码。对于 BVH 树，在和 根 节点求交 之后 ，我们总是查找它的左右子树，这相当于二叉树的 先序遍历 ，实现起来相对容易
维护一个栈来保存节点。首先将树根入栈，然后 while(!stack.empty()) 进行循环：
很简单，不过注意 先访问的节点后入栈 ，因为栈的存取顺序是相反的，这样保证下一次取栈顶元素，一定是先被访问的节点。这里摆烂了五毛特效糊一张非递归遍历时栈状态图：
如果不知道代码有没有 bug，可以上 leetcode 的第 144 题检验一下，这里是 传送门
至此我们掌握了非递归遍历二叉树的方法，在 GLSL 中没有 STL 的 stack，所以我们用数组和一个 sp 指针模拟栈。下面是遍历 BVH 查询 最近的 三角形的 GLSL 代码：
// 遍历 BVH 求交
HitResult hitBVH(Ray ray) {
HitResult res;
res.isHit = false;
res.distance = INF;
// 栈
int stack[256];
int sp = 0;
stack[sp++] = 1;
while(sp>0) {
int top = stack[--sp];
BVHNode node = getBVHNode(top);
// 是叶子节点，遍历三角形，求最近交点
if(node.n>0) {
int L = node.index;
int R = node.index + node.n - 1;
HitResult r = hitArray(ray, L, R);
if(r.isHit && r.distance<res.distance) res = r;
continue;
}
// 和左右盒子 AABB 求交
float d1 = INF; // 左盒子距离
float d2 = INF; // 右盒子距离
if(node.left>0) {
BVHNode leftNode = getBVHNode(node.left);
d1 = hitAABB(ray, leftNode.AA, leftNode.BB