Отрицание правдимости логической оценки, вызывая замедление 5x?

Question

Я пытаюсь осуществить октери, и для этого мне нужен быстрый алгоритм пересечения AABB-Ray. После некоторых поисков я наткнулся это бумага, которая, казалось, предложила это. Из исходного кода доступно здесь, Я перевел 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 Заявление и изменено все сравнения (> к < и Visa Versa).

Это снег:

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

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

В дополнение к изменениям, которые вы уже сделали, вам нужно повернуть все свои или в и. (Видеть Законы де Моргана.)

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

Answer 2

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