减少光线追踪时的计算量
Reduce calculations while Raytracing
我已经编写了自己的 3D 游戏引擎（我花了一年时间），我想创建一个 运行 在我的 CPU（不是 GPU！！）上的 Raytracer =10=]
目前，光线追踪过程简化如下：
- 为每个输出像素投射一条光线。
- 如果当前光线射中物体，将输出像素颜色设置为"white"
- 否则设置为黑色
为了提高光线追踪器的速度，我为每个实体添加了一个球形边界框。如果当前光线与边界框相交，它将运行与实体的每个三角形相交测试。
我在光线三角形相交和光线点距离上使用了最快的方法，但每条光线仍然必须测试每个实体的每个可能相交的三角形。
因此，渲染一个包含大约 10000 个多边形的对象 (1920x1080) 需要 5 多分钟，我认为这不是我想要的。
有什么方法可以减少我需要检查的三角形数量吗？
你好，芬恩
Is there any way of reducing the amount of triangles that I need to check?
是的。
听起来你的场景由一个三角形列表组成，你在列表中线性迭代并检查每个三角形以找到最接近的三角形。这是线性搜索，具有 O(n) 运行时间，n = 三角形数。
您可以使用 volumetric kd-trees or bounding volume hierarchies 来存储您的三角形，从而将此时间减少到平均 O(log(n)) 时间。就个人而言，我更喜欢 kd-trees，但是这两种方法都有效。请注意，BVH 通常在动画场景中表现更好。
请注意，加速结构在它们的构造或遍历方式中可能包含细微的错误，因此您可能想要开发一些方法来使用朴素列表方法（对于参考图像）和结构化方法。在我的爱好追踪器中，我是这样组织的：
AbstractScene - 所有场景类型的基础 class。大多数代码仅与 AbstractScene 字段和方法交互。
KDScene - 派生 class 将场景实现为 kd 树。
BVHScene - 派生 class 将场景实现为 BVH。
NaiveScene - 派生 class 将场景实现为三角形列表。
还有其他加速结构，如grids (aka voxels)。
我已经编写了自己的 3D 游戏引擎（我花了一年时间），我想创建一个 运行 在我的 CPU（不是 GPU！！）上的 Raytracer =10=]
目前，光线追踪过程简化如下：
- 为每个输出像素投射一条光线。
- 如果当前光线射中物体，将输出像素颜色设置为"white"
- 否则设置为黑色
为了提高光线追踪器的速度，我为每个实体添加了一个球形边界框。如果当前光线与边界框相交，它将运行与实体的每个三角形相交测试。
我在光线三角形相交和光线点距离上使用了最快的方法，但每条光线仍然必须测试每个实体的每个可能相交的三角形。
因此，渲染一个包含大约 10000 个多边形的对象 (1920x1080) 需要 5 多分钟，我认为这不是我想要的。
有什么方法可以减少我需要检查的三角形数量吗？
你好，芬恩
Is there any way of reducing the amount of triangles that I need to check?
是的。
听起来你的场景由一个三角形列表组成，你在列表中线性迭代并检查每个三角形以找到最接近的三角形。这是线性搜索，具有 O(n) 运行时间，n = 三角形数。
您可以使用 volumetric kd-trees or bounding volume hierarchies 来存储您的三角形，从而将此时间减少到平均 O(log(n)) 时间。就个人而言，我更喜欢 kd-trees，但是这两种方法都有效。请注意，BVH 通常在动画场景中表现更好。
请注意，加速结构在它们的构造或遍历方式中可能包含细微的错误，因此您可能想要开发一些方法来使用朴素列表方法（对于参考图像）和结构化方法。在我的爱好追踪器中，我是这样组织的：
AbstractScene - 所有场景类型的基础 class。大多数代码仅与 AbstractScene 字段和方法交互。
KDScene - 派生 class 将场景实现为 kd 树。
BVHScene - 派生 class 将场景实现为 BVH。
NaiveScene - 派生 class 将场景实现为三角形列表。
还有其他加速结构，如grids (aka voxels)。