c# - 否定导致 5 倍减速的 bool 值评估的真实性？

Question

我正在尝试实现一个八叉树，为此，我需要一个快速的 AABB 射线相交算法。经过一番搜索，我遇到了 this似乎提供了这一点的论文。来自源代码，可用here , 我翻译了 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。 (参见 De Morgan's Laws。)

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