2

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)。

4

2 回答 2

9

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

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

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

因此，SAH 的主要思想是最小化这两者：子树的表面积和它们内部的多边形数量。

在此处输入图像描述

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

在此处输入图像描述

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

1）在构建kd-tree的每一步，在子树分裂之前——你必须计算当前子树的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
}

这是 Stackoverflow 上的另一个答案，其中包含对有关 SAH 的文章的引用。

于 2013-11-17T10:59:14.593 回答
1

中间点的计算看起来不正确。对于 x 坐标为 2,3,8 的三角形，中点应为 2 + (8-2)/2 = 5。 x 坐标为 1,2,3 的三角形应有中点 1 + (3-1)/2 = 2。这可以解释不平衡的叶子。

于 2016-12-13T11:54:46.373 回答