问三角形网格的Kd树太慢了

EN

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个三角形的兔子时，有大量的一个三角形的叶节点，最后一个叶节点仍然包含762个三角形。

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

更新:我搜索了一种算法或启发式方法，可以根据切点将间隔t0、t1的数组划分为两个间隔数组。左数组包含切割点左侧的间隔和包含切割点的间隔。正确数组的类比。两个数组必须具有大致相同的间隔数，重复间隔的数目必须尽可能最少。该算法不具有O(n^2)的复杂度。