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

Question

我已经根据Wald和Havran的论文On building fast kd-Trees for Ray Tracing, and on doing that in O(N log N)实现了基于SAH的kd-tree。请注意，我没有按照他们在最后提出的建议进行剪接和合并，只是使用了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），即使正确的成本表明需要进一步细分，它也可能停止细分。特别地，局部逼近可能导致对需要从侧面拆分平面单元格的体素过早终止：许多场景（特别是建筑场景）包含以轴对齐框盒的形式呈现的几何体（例如灯具、桌子的腿或桌面等），在这种情况下，必须将侧面“削平”，直到暴露出空的内部。对于选择错误的参数或使用不同于我们使用的成本函数（特别是将恒定成本添加到叶估计中的函数），递归可能会过早地终止。虽然这种过早退出也可以以硬编码的方式避免，例如仅对非平面单元格执行自动终止测试，但我们建议遵循我们的公式，这样就不会发生过早退出。

我有做错什么吗？我该如何纠正这个问题？

- PeteUK

Answer 1

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

修复方法：仅在一侧计数==0且宽度非零时应用偏差。

- Ingo Wald