Отрицание правдивости логической оценки, вызывающей 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 мс, чтобы сделать 10 миллионов пересечений), поэтому я попытался провести несколько микробанчмаркингов с различными вариантами. В одном я удалил отрицание, которое находится сразу после утверждения 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 мс, чтобы сделать 10 миллионов пересечений)! Я уверен, что это не было оптимизировано, мой тест выглядит так:

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

Чем можно объяснить эту огромную разницу? Я использую .NET 4.0 на x86.

Answer 1

Ваш второй код не делает то же самое, что и ваш первый.

В дополнение к уже внесенным изменениям вам необходимо превратить все ваши OR в AND.(См. Законы Де Моргана .)

Держу пари, что после того, как вы исправите, две версии будут работать с одинаковой скоростью.

Answer 2

Бьюсь об заклад, что оператор возврата закорачивается быстрее во втором случае, чем в первом. Возможно, стоит попытаться изменить порядок сравнений, если некоторые из них более правдивы, чем другие, чтобы быть правдой. Если вы измените расчеты на эквивалентные, используя && вместо || во втором случае вы бы хотели, чтобы те, которые с наибольшей вероятностью были ложными, пришли первыми.