Nier l'truthiness d'une évaluation booléenne provoquant 5x ralentissement?

Question

Je suis en train de mettre en œuvre un octree, et pour cela, je besoin d'un algorithme d'intersection AABB-ray rapide. Après quelques recherches, je suis tombé sur cet article qui semblait offre cette. À partir du code source, href="http://jgt.akpeters.com/papers/MahovskyWyvill04/" disponible , je traduis la fonction pluecker_cls_cff à C # comme ceci:

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;
}

Cela semble fonctionner très bien, mais il semblait assez lent à me (250ms pour 10 millions d'intersecte) alors j'ai essayé quelques micro-analyses comparatives avec des variétés différentes. Dans l'un, j'ai enlevé la négation qui est juste après la déclaration de return toutes les comparaisons et reprises (> à < et vice versa).

Il est maintenant:

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));

Cela devrait donner le même résultat, non? Il semblait ainsi, car il renvoie les mêmes résultats que la version niée avec quelques cas de test. Toutefois, l'indice de référence, il était 5 fois plus rapide (50 ms à 10 millions d'intersecte)! Je suis sûr qu'il n'a pas été optimisé, mon regard de référence comme ceci:

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

Comment expliquer cette énorme différence? Je suis en cours d'exécution .NET 4.0 sur x86.

Answer 1

Votre deuxième code ne fait pas la même chose que votre premier.

En plus des modifications déjà apportées, vous devez transformer tous vos ORs en ANDs. (Voir Lois de De Morgan .)

Je parie que lorsque vous faites le correctif, vos deux versions fonctionnent à la même vitesse.

Answer 2

Plus précisément liée à la performance, je parie que la déclaration de retour est court-circuit plus tôt dans le second cas que le premier. Il peut être intéressant d'essayer de changer l'ordre des comparaisons si certains sont plus susceptibles que les autres d'être vrai. Si vous modifiez les calculs à l'aide d'équivalent && au lieu de || dans le second cas, alors vous voulez que ceux qui sont les plus susceptibles d'être faux à venir en premier.