否定布尔求值的真实性会导致速度减慢 5 倍？

Question

我正在尝试实现一个八叉树，为此，我需要一个快速 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。

Answer 1

您的第二个代码与您的第一个代码执行的操作不同。

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

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

Answer 2

具体与性能相关，我敢打赌，在第二种情况下，返回语句比第一种情况更快短路。如果有些比其他更可能是真实的，那么可能值得尝试改变比较的顺序。如果您使用 && 将计算更改为等效；而不是||在第二种情况下，那么您会希望最有可能是错误的那些首先出现。