否定布尔评估的真实性导致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.(参见De Morgan的定律.)

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