使用 kd-tree 进行交集测试
Intersection test with kd-tree
我目前对kd树的理解是；在每个节点上，我们将点分成一个轴的两个同样大的组。
我们遍历各个轴，直到树饱和。
这种数据结构对于光线追踪应用程序来说当然很有趣，因为我们不必搜索每个三角形面来测试我们与光线的交点，我们只需要知道它可能在哪里三角形会与我们的射线相交。
我对这是如何完成的有一些疑问。
我们如何处理无法轻松拆分的奇怪三角形（三角形与其他三角形相交或跨越整个三角形？
我们是在三角形上分割还是在顶点上分割？
我们究竟如何测试从相机发出的光线的交点？
我看到了几种方法。首先，我们可以从我们的场景和分割平面构建边界框并测试与这些框的交集，或者我们可以测试与分割平面的交集并查看交集相对于相机的位置
简短的回答是：这完全取决于您的应用程序。 kd-trees.
有多种变体
我们如何处理无法轻松拆分的奇怪三角形？
我相信您指的是为一组给定的三角形选择分割平面。这是一个非常困难的优化问题，通常使用启发式方法来解决。例如，您可以沿一个轴对三角形的质心进行排序，然后选择中位数作为分割平面。没有什么能阻止您实施更智能的标准。
如果您发现您的分割平面穿过图元，您有两种选择。拆分图元或将其添加到两个子树。你应该做什么取决于你的应用程序。
我们是在三角形上分割还是在顶点上分割？
这取决于您要添加到树中的基元。如果您想使用树进行光线投射，那么在树中放置三角形是有意义的。 kd-trees 是一个非常通用的概念，适用于任何类型的基元。例如，它们也广泛用于点云。
我们究竟如何测试从相机发出的光线的交点？
你通过遍历树来做到这一点。因此，您从根节点开始检查射线是否与关联的边界框（即整个 space）相交。然后你检查这两个子树中的哪一个首先被射线相交并继续这个。然后你重复：你测试与节点的 AABB 的交集（你从分裂平面增量构建）。如果射线不与AABB相交，则立即return回到parent节点。如果是，请继续第一个 child。当你从第一个 child 回来时，去第二个 child （除非你已经找到路口）。
有关更多详细信息，我建议查看 kd-trees 的 application-specific 个实例。
我目前对kd树的理解是；在每个节点上，我们将点分成一个轴的两个同样大的组。
我们遍历各个轴，直到树饱和。
这种数据结构对于光线追踪应用程序来说当然很有趣，因为我们不必搜索每个三角形面来测试我们与光线的交点，我们只需要知道它可能在哪里三角形会与我们的射线相交。
我对这是如何完成的有一些疑问。
我们如何处理无法轻松拆分的奇怪三角形（三角形与其他三角形相交或跨越整个三角形？
我们是在三角形上分割还是在顶点上分割？
我们究竟如何测试从相机发出的光线的交点？
我看到了几种方法。首先，我们可以从我们的场景和分割平面构建边界框并测试与这些框的交集，或者我们可以测试与分割平面的交集并查看交集相对于相机的位置
简短的回答是：这完全取决于您的应用程序。 kd-trees.
有多种变体我们如何处理无法轻松拆分的奇怪三角形？
我相信您指的是为一组给定的三角形选择分割平面。这是一个非常困难的优化问题，通常使用启发式方法来解决。例如，您可以沿一个轴对三角形的质心进行排序，然后选择中位数作为分割平面。没有什么能阻止您实施更智能的标准。
如果您发现您的分割平面穿过图元，您有两种选择。拆分图元或将其添加到两个子树。你应该做什么取决于你的应用程序。
我们是在三角形上分割还是在顶点上分割？
这取决于您要添加到树中的基元。如果您想使用树进行光线投射，那么在树中放置三角形是有意义的。 kd-trees 是一个非常通用的概念，适用于任何类型的基元。例如，它们也广泛用于点云。
我们究竟如何测试从相机发出的光线的交点？
你通过遍历树来做到这一点。因此，您从根节点开始检查射线是否与关联的边界框（即整个 space）相交。然后你检查这两个子树中的哪一个首先被射线相交并继续这个。然后你重复：你测试与节点的 AABB 的交集（你从分裂平面增量构建）。如果射线不与AABB相交，则立即return回到parent节点。如果是，请继续第一个 child。当你从第一个 child 回来时，去第二个 child （除非你已经找到路口）。
有关更多详细信息，我建议查看 kd-trees 的 application-specific 个实例。