减少计算而光线追踪

Question

我写我自己的3D游戏引擎（我花了一年），我想创造我的CPU上运行的光线跟踪（而不是GPU！）

就目前而言，射线追踪过程如下简化：

1. 为每个输出像素投射射线。
2. 如果当前射线碰到物体，设置输出像素的颜色为“白色”
3. 否则设置为黑色

为了提高光线跟踪器的速度，我添加了一个球形边界框每个实体。如果当前射线与边界框相交，它将运行与实体的每个三角形的相交测试。

我在射线三角交点和射线点距离上使用了最快的方法，但每条射线都必须测试每个可能相交的实体的每个三角形。

因此，使用大约10000多个多边形渲染一个对象（1920x1080）需要5分多钟，我想这不是我想要的。

有什么办法减少我需要检查的三角形数量吗？

问候，芬兰人

Answer 1

有没有减少，我需要检查三角形的量的方法吗？

是的。

这听起来像你的场景由三角列表组成，并且你正在线性迭代列表并检查每个三角形以找到最接近的三角形。这是线性搜索并具有运行时间，n =三角形的数量。

您可以通过使用volumetric kd-trees或bounding volume hierarchies存储您的三角形，从而减少该平均O(log(n))时间。就个人而言，我更喜欢kd-trees，但任何一种方法都可行。请注意，BVH通常在动画场景中表现更好。

请注意，加速结构可能包含构造或遍历的细微缺陷，因此您可能需要开发一些方法来使用朴素列表方法（用于参考图像）和结构化方法呈现相同的场景。在我的爱好追踪器中，我这样组织：

AbstractScene - 所有场景类型的基类。大多数代码仅与AbstractScene字段和方法交互。

KDScene - 将场景实现为kd-tree的派生类。

​​- 将场景实现为BVH的派生类。

NaiveScene - 将场景实现为三角形列表的派生类。

还有其他加速结构，如grids (aka voxels)。