Отрицание правдивости булевой оценки, вызывающей 5-кратное замедление?

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мс сделать 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. (См. De Morgan's Laws.)

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

Answer 2

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