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