إلغاء صحة التقييم المنطقي الذي يسبب تباطؤ 5x؟

Question

أحاول تنفيذ Octree ، ولهذا ، أحتاج إلى خوارزمية تقاطع 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 بيان وعكس جميع المقارنات (> إلى < والعكس بالعكس).

إنها تثلج:

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

هذا يجب أن يعطي نفس النتيجة ، أليس كذلك؟ بدا الأمر كذلك ، لأنه يعيد نفس النتائج مثل الإصدار المنفي مع بضع حالات اختبار. ومع ذلك ، في المعيار ، كان 5x أسرع (50ms للقيام 10 ملايين تقاطعات)! أنا متأكد من أنه لم يتم تحسينه ، يبدو أن معياري مثل هذا:

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

ماذا يمكن أن يشرح هذا الاختلاف الكبير؟ أنا أقوم بتشغيل .NET 4.0 على x86.

Answer 1

الرمز الثاني الخاص بك لا يفعل نفس الشيء مثل أولك.

بالإضافة إلى التغييرات التي أجريتها بالفعل ، تحتاج إلى تحويل جميع ORS إلى و. (نرى قوانين دي مورغان.)

أراهن أنه بعد إجراء الإصلاح ، سيتم تشغيل نسختك بنفس السرعة.

Answer 2

فيما يتعلق بالتحديد بالأداء ، أراهن أن بيان الإرجاع هو دائرة قصيرة في الحالة الثانية من الحالة الأولى. قد يكون من المفيد محاولة تغيير ترتيب المقارنات إذا كان بعضها أكثر عرضة من الآخرين. إذا قمت بتغيير العمليات الحسابية لتكون مكافئة باستخدام && بدلاً من || في الحالة الثانية ، فأنت تريد أن تكون تلك التي من المرجح أن تكون خاطئة أولاً.