raytracing - 三角形网格的 Kd 树太慢

Question

Kd 算法首先通过划分基元数组(三角形、球体等)来创建根 BSP 节点，以便创建两个新数组(左基元和右基元)，用于创建其两个基元子树。

左基元和右基元是通过将给定基元数组划分为两个数组来计算的。通过取每个三角形的间隔(投影到给定轴(x、y 或 z))的中点的中值来计算分割平面位置。

例如，x 坐标为 1, 2, 3 的三角形的中点为 1=(3-1)/2(沿 x 轴)x 坐标为 2, 3, 8 的三角形的中点 3=(8-2)/2(沿 x 轴)x 坐标为 4, 3, 8 的三角形的中点为 2.5=(8-3)/2(沿 x 轴)包含这三个三角形的基元数组由与 yz 平面平行的 x=2.5(中值)平面划分。生成的左图元数组包含三个三角形，生成的右图元数组包含三个三角形。

带有左基元和右基元的两个结果数组用于构造 Kd 节点的左子树和右子树(基元仅存储在叶节点)。

对于左子树:

If (the left primitives are empty) then the left subtree points to NULL
else if (the number of left primitives is smaller than the minimal number || the depth == 1) then the left subtree is a leaf node
else the left subtree is another tree.

create the left subtree with the left primitives along the axis (++axis % 3) with --depth as depth and the same minimal number.

与右子树类似。

实现的算法有效，但速度非常慢，因为树的分区不是很好。当对 5500 个三角形的兔子进行光线追踪时，有很多 1 个三角形的叶子节点，最后一个叶子节点仍然包含 762 个三角形。

是否有更好的分区算法(因为我的只是将单点转换为曲面的 Kd 树的实现)，可以平衡树？

更新:我搜索了一种算法或启发式算法，可以根据切割点将间隔数组 [t0,t1] 划分为两个间隔数组。左侧数组包含切割点左侧的间隔以及包含切割点的间隔。与右侧数组类似。两个数组必须具有大致相同的间隔数量，并且重复间隔的数量必须尽可能少。该算法的复杂度可能不是 O(n^2)。

Answer 1

我建议您使用表面积启发式 (SAH) 来寻找最佳分割。

光线与子树相交的概率 - 与该子树的边界框的表面积成正比。

但是，如果叶子子树包含很多三角形 - 这意味着我们必须遍历所有三角形。

因此，SAH 的主要思想是最小化:子树的表面积和子树内部多边形的数量。

让我们看一下小型 2D 示例:

此外，使用 SAH - 有助于确定构建 kd 树期间的终止条件:

1)在构建kd树的每个步骤中，在子树 split 之前 - 你必须计算当前子树的SAH

SAH_initial = number_of_polygons * area_of_subtree

2)之后你必须找到当前子树的最优分割的SAH

SAH_optimal = min(S_left * N_left + S_right * N_right)

3)之后你必须比较:

define some split_cost
...

if( SAH_optimal + split_cost < SAH_initial ) { 
   it would be optimal to split that subtree
} else {
   you don't have to split current subtree
}

这是另一个 answer on Stackoverflow ，其中包含有关 SAH 的文章引用。