网格分区和快速查找

Question

我正在编写一个光线追踪器，我正在尝试对一些网格数据（点和面）进行分区，以便计算交集。

目前，对于每个相交

计算，我都必须查找每个面，看看光线是否与它相交。我正在尝试找到一种更快的方法来做到这一点，即只查找相关的面孔。

存储图形数据的良好数据结构是什么（kd树？等分空间？）如何在给定光线的情况下查找相关空间/面？

PS：我正在使用C++

Answer 1

空间分区数据结构（BSP 树、k-D 树或八叉树），甚至更一般的边界卷层次结构（AABB 树）应该可以完成这项工作。请参阅有关从网格构建BSP树及其遍历的相关问题的答案。C++库 CGAL 提供具有所需构造和查询的 AABB 树数据结构。