三角形的表面积启发式（SAH）kd树-平面单元

Question

我已经基于“ 关于建立用于射线跟踪的快速kd树”的论文，以及 Wald和Havran 在O（N log N）中进行的研究，实现了SAH kd树。请注意，最后我还没有完成他们的拼接和合并建议，只是为了加快树的构建速度，只是SAH部分。

我正在使用轴对齐的多维数据集测试该算法，其中每个面都分成两个三角形，所以我N = 12总共有三角形。左下角的顶点（即最靠近轴的顶点）实际上位于原点。

Face    Triangle
----------------
Front:  0, 1
Left:   6, 7
Right:  2, 3
Top:    4, 5
Bottom: 10, 11
Back:   8, 9

假设节点遍历成本Ct = 1.0和交叉成本Ci = 10.0。我们首先发现不分裂的成本为Cns = N * Ci = 12 * 10.0 = 120.0。

现在，我们依次遍历每个轴，并逐步遍历候选拆分平面，以查看拆分成本是否更便宜。第一个分割平面是p = <x,0>。我们有Nl = 0，Np = 2而且Nr = 10（也就是三角形的上左边的数字，在飞机上，并以平面的右侧）。平面中的两个三角形分别是数字6和7（左侧）。其他所有人都在右边。

SAH(p,V,Nl,Nr,Np)现在执行该功能。这需要分割平面，V要分割的体素以及左/右/平面三角形的数量。它计算出命中左（平坦）体素Pl = SA(Vl)/SA(V) = 50/150 = 1/3的概率为，右命中的概率为Pr = SA(Vr)/SA(V) = 150/150 = 1。现在它运行成本函数两次；首先使用左侧的平面三角形，然后使用右侧的平面三角形分别获得Cl和Cr。

成本函数C(Pl,Pr,Nl,Nr)返回bias * (Ct + Ci(Pl * Nl + Pr * Nr))

Cl：左侧带有平面三角形的成本（Nl = 2，Nr = 10）

bias = 1 我们没有偏见，因为左或右体素都不为空。
Cl = 1 * (1 + 10(1/3 * 2 + 1 * 10)) = 107.666

Cr：右边带有平面三角形的成本（Nl = 0，Nr = 12）

bias = 0.8 空单元偏差开始起作用。
Cr = 0.8 * (1 + 10(1/3 * 0 + 1 * 12)) = 96.8

该算法确定Cr = 96.8比将两个三角形分割成一个平面单元Cl = 107.666更好，也比根本不分割体素更好Cns = 120.0。没有其他候选分割更便宜。因此，我们分裂为一个空的左孩子和一个包含所有三角形的右孩子。当我们递进合适的孩子继续进行树的构建时，我们将执行与上述完全相同的步骤。仅由于最大深度终止条件，才不会导致堆栈溢出。生成的树很深。

该论文声称考虑过这种事情：

在裁剪期间，必须特别注意正确处理“扁平”（即零体积）像元之类的特殊情况，或可能出现数值不正确的情况（例如，与三角形大小相比非常薄的像元） ）。例如，我们必须确保不要“剪掉”位于平面单元中的三角形。请注意，这种情况并非罕见，但SAH确实鼓励这种情况，因为它们通常产生最低的预期成本。

这种局部近似值很容易卡在局部最小值中：由于局部贪婪SAH高估了CV（p），因此即使正确的成本已表明需要进一步细分，它也可能会停止细分。特别是，局部近似会导致需要将侧面的平面单元分开的体素的过早终止：许多场景（尤其是建筑场景）包含呈轴对齐框（灯具，桌腿）形式的几何形状或桌面……），在这种情况下，必须“刮掉”侧面，直到露出空的内部。对于错误选择的参数，或使用与我们使用的参数函数不同的成本函数（尤其是在叶子估计中添加了恒定成本的函数）时，递归可能会提前终止。

我做错什么了吗？我该如何纠正？

Answer 1

现在可能有点晚了:-/，但以防万一：我认为这里“错误”的事情是“空单元格”偏见的概念：你想要“鼓励”的东西（通过给它一个小于-一个偏差）正在切除空白空间，但这意味着被切除的细胞实际上确实有体积。显然，在您的实现中，您只检查一侧是否有零个三角形，因此即使根本没有空间被切掉，也会应用偏差。

修复：仅当一侧的 count==0且宽度非零时才应用偏差。