三角网格的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轴)包含这些的原始数组三个三角形由平面划分,平行于x = 2.5(中位数)平行于yz平面.生成的左基元数组包含三个三角形,生成的右基元数组包含三个三角形.

具有左和右基元的两个结果阵列用于构造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-tree构建期间的终止条件:

1)在构建kd-tree的每一步,在子树分裂之前 - 你必须计算当前子树的SAH

SAH_initial = number_of_polygons * area_of_subtree

2)Aftre你必须找到当前子树的最佳分割的SAH

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

3)Aftre你必须比较:

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
}

这是Stackoverflow的另一个答案,它包含有关SAH的文章的参考.