1

我正在尝试实现一个八叉树，为此，我需要一个快速的 AABB 射线相交算法。经过一番搜索，我发现了这篇似乎提供了这一点的论文。从这里提供的源代码中，我将pluecker_cls_cff函数翻译为 C#，如下所示：

public bool Intersect_2(ref RayPluecker r)
{
  switch (r.Classification)
  {

    // 7 same-ish cases snipped

    case Classification.PPP:

      return !((r.Position.X > this.Max.X) || (r.Position.Y > this.Max.Y) || (r.Position.Z > this.Max.Z) ||
        (r.PlueckerCoefficient.X + r.Direction.X * this.Max.Y - r.Direction.Y * this.Min.X < 0) ||
        (r.PlueckerCoefficient.X + r.Direction.X * this.Min.Y - r.Direction.Y * this.Max.X > 0) ||
        (r.PlueckerCoefficient.Y + r.Direction.X * this.Min.Z - r.Direction.Z * this.Max.X > 0) ||
        (r.PlueckerCoefficient.Y + r.Direction.X * this.Max.Z - r.Direction.Z * this.Min.X < 0) ||
        (r.PlueckerCoefficient.Z - r.Direction.Z * this.Min.Y + r.Direction.Y * this.Max.Z < 0) ||
        (r.PlueckerCoefficient.Z - r.Direction.Z * this.Max.Y + r.Direction.Y * this.Min.Z > 0));
  }

  return false;
}

这似乎工作正常，但对我来说似乎相当慢（250 毫秒来做 1000 万次相交）所以我尝试了一些不同品种的微基准测试。一方面，我删除了return声明之后的否定并反转了所有比较（>反之亦然<）。

下雪了：

case Classification.PPP:

      return ((r.Position.X < this.Max.X) || (r.Position.Y < this.Max.Y) || (r.Position.Z < this.Max.Z) ||
        (r.PlueckerCoefficient.X + r.Direction.X * this.Max.Y - r.Direction.Y * this.Min.X > 0) ||
        (r.PlueckerCoefficient.X + r.Direction.X * this.Min.Y - r.Direction.Y * this.Max.X < 0) ||
        (r.PlueckerCoefficient.Y + r.Direction.X * this.Min.Z - r.Direction.Z * this.Max.X < 0) ||
        (r.PlueckerCoefficient.Y + r.Direction.X * this.Max.Z - r.Direction.Z * this.Min.X > 0) ||
        (r.PlueckerCoefficient.Z - r.Direction.Z * this.Min.Y + r.Direction.Y * this.Max.Z > 0) ||
        (r.PlueckerCoefficient.Z - r.Direction.Z * this.Max.Y + r.Direction.Y * this.Min.Z < 0));

这应该给出相同的结果，对吧？看起来是这样，因为它返回与带有几个测试用例的否定版本相同的结果。然而，在基准测试中，它快了 5 倍（50 毫秒完成 1000 万次相交）！我确定它没有被优化，我的基准看起来像这样：

for (int i = 0; i < 10000000; i++)
{
  if (!box.Intersect_3(ref ray))
  {
    throw new Exception();
  }
}

什么可以解释这种巨大的差异？我在 x86 上运行 .NET 4.0。

4

2 回答 2

5

您的第二个代码与您的第一个代码不同。

除了您已经进行的更改之外，您还需要将所有 OR 转换为 AND。（参见德摩根定律。）

我敢打赌，在您进行修复后，您的两个版本将以相同的速度运行。

于 2010-09-16T23:02:04.777 回答
0

Specifically related to performance, I bet the return statement is short-circuiting sooner in the second case than the first. It may be worth trying to change the order of the comparisons if some are more likely than others to be true. If you change the calculations to be equivalent using && instead of || in the second case, then you would want the ones that are most likely to be false to come first.

于 2010-09-16T23:23:26.630 回答