مثل Flatland
في عمل ادوين أبتوت Flatland (1884): سكان مستوى ثنائي الأبعاد. يدركون الطول والعرض. العمق: البعد الثالث فوقهم، غير مرئي. لا يمكنهم رؤيته، لا يمكنهم استخدامه، لا يمكنهم بناؤه به. يحتوي جغرافية عالمهم على بعد لا يستطيعون استخدامه. يتعاملون معه على أنه مستوى مستو. يقوم الفحص الخطي بتعاملهم معه على أنه قائمة مستوية.
MOAD-0007 يعمل بنفس الطريقة. الجسم في الفضاء ثلاثي الأبعاد يحمل موقعه ووضعه الدوري ومجال الحدود: بنية جيومتيرية غنية. فحص خطي يتعامل معها كقائمة مستوية. توجد بنية الجيومتيري: موجودة، غير مستخدمة، تم التخلص منها. كل اختبار للتقاطع يفحص القائمة بأكملها، كما لو كان الجسم ليس لديه جغرافية وليس لديه موقف.
مثال Three.js
Three.js Raycaster.intersectObjects(): مع راي (موضع وطريقة في الفضاء ثلاثي الأبعاد)، ابحث عن جميع الأشياء التي يتقاطع بها الراي. التنفيذي: يتفاعل مع جميع N جسم المشهد، ويقارن كل منها مع الراي. O(N) لكل استدعاء.
تعامل مع حدث التبديل يدعو intersectObjects() مرة واحدة لكل إطار بسرعة 60 إطارًا في الثانية. مع N = 100 جسم: 6,000 اختبار التقاطع في الثانية. مع N = 10,000 جسم: 600,000 اختبار التقاطع في الثانية. التكلفة: متناسبة مع N وليس عدد الأشياء التي يتقاطع بها الراي الفعلية.
في N = 100: غير مرئي. الميزانية المحددة للطول البالغ (16.7 مللي ثانية عند 60 إطارًا في الثانية) تتحمل تكلفة بدون شكوى.
في N = 10,000: المهيمنة. 600,000 اختبار التقاطع في الثانية يملأ المحور الرئيسي. معدل الإطار ينخفض. المشهد الذي عمل في N = 100 ينهار ساكنًا عندما يمر الحد.
البنية التي يتم التخلص منها بواسطة الفحص الخطي
الجسم يحتوي على مواقع في الفضاء. لا يمكن أن يتقاطع جسم في موضع (1000، 0، 0) مع راي يوجه في الاتجاه (-1، 0، 0) من موضع (0، 0، 0): الجسم يقع في الاتجاه المعاكس. يقوم الفحص الخطي بفحصه على أي حال.
لديها مجالات الحدود: كرة أو صندوق يحتوي على الجسم بأكمله. راي لا يلتقي مع مجال الحدود لن يتم التقاطع مع الجسم. يقوم الفحص الخطي بتحويل اختبار التقاطع الكامل على أي حال.
البنية الجيومتيرية تحدد أي جسم يجب تجنبه. يقوم الفحص الخطي ب игنور الجيومتيري. هذا هو التخلص.
ماذا يعني "التخلص من البنية"
مثال بلاد المخطّطات: سكان بلاد المخططات لم يكن لديهم إدراك للحجم. عيوب بلاد المخططات ترفض الهيكل الجيومتري الذي يوجد في البيانات ولكن لا يدخل في الخوارزمية.
لماذا لا يمكن لحزمة قيم ثابتة حل MOAD-0007
تصحيح MOAD-0001: استبدل اختبار الأعضاء التسلسلي بالحزمة القيم الثابتة. list.contains(x): O(N). set.has(x): O(1). السؤال المتعلق بالعضوية: 'هل x في هذه المجموعة؟' لا يوجد فيه جيو متري.
تصحيح MOAD-0007: استبدل فحص المسافة الخطية بمؤشر المساحة (BVH، شجرة الأوكت، شجرة k-d، شجرة R). السؤال الجغرافي: 'أي أشياء في هذه المجموعة تتفاعل مع هذا السهم/كرة/مصفوفة؟' مطلوب المسافة الجغرافية.
تجيب حزمة قيم ثابتة على عضوية: 'هل هذا الجسم الدقيق موجود؟' O(1). لا يمكنها الإجابة على المسافة: 'أي أشياء قريبة من هذا السهم؟' لا يوجد لديها مفهوم المسافة أو الحجم الجغرافي. التغليف باستخدام الهاش يرفض الجيو كما فعل فحص الخطي.
تجيب BVH على المسافة: 'أي أشياء داخل هذا استفسار جوي؟' O(log N + k). تُنظم الأشياء حسب الوضع حتى يتم تجاوز الأشياء الجغرافية البعيدة.
| السؤال | الهيكل الصحيح | الهيكل الخاطئ |
|-------|---------------|--------------|
| هل يوجد شيء X في هذا المجموعة؟ | HashSet (O(1)) | قائمة خطية (O(N)) |
| أي أشياء تفاعل مع هذا السهم؟ | BVH / شجرة الأوكت / شجرة k-d (O(log N)) | فحص خطي أو حزمة قيم ثابتة (O(N) أو O(N)) |
MOAD-0001 & MOAD-0007: كلا العمليات الخطية تستبدل بـ شيء أسرع. يتطلب ذلك تراكيبياً مختلفاً لأن الأسئلة مختلفة.
متى تُنشأ، ومتى يتم تجاهله
إنشاء BVH يكلف O(N log N). استفسار يكلف O(log N + k). التوازن الاقتصادي: عندما يفوق عدد الاستفسارات عدد الإنشاءات بما يكفي حيث تقل الفوائد من الاستفسار عن تكلفة الإنشاء.
عند N = 100: الفحص الخطي يتطلب ميكرو ثانية. إنشاء BVH يضيف تكاليف إضافية. تجنب إنشاء BVH.
عند N = 10,000 عند 60 هرتز: الفحص الخطي يسيطر على ميزانية الإطار. استفسار BVH يكلف 1/1000 من تكلفة الفحص الخطي. انشأ BVH مرة واحدة؛ استفسر 60 مرة في الثانية. وصل التوازن الاقتصادي قبل الإطار الأول.
القاعدة: انشأ عندما N * Q > N log N، حيث Q = عدد الاستفسارات لكل دور إعادة الإنشاء. في مشاهدات ثلاثية الأبعاد التفاعلية: Q = 60 في الثانية، الحد الفاصل = عدد قليل من الأشياء.
تشخيص وتصحيح مشهد ثلاثي الأبعاد
تطبيق ترسيم ثلاثي الأبعاد يرسم 5,000 جسم هندسي. يطلق معالج التبدير 60 مرة في الثانية. في كل حدث من تبدير، يُدعَم المعالج scene.intersectObjects(ray, objects) الذي يتفقد جميع الجسمات الخمسة thousand ويتحقق منها كل منها ضد الشعاع. انخفض معدل الإطار من 60 إطار في الثانية إلى 8 إطارات في الثانية.
صديق يوصي: 'أضف جميع الجسمات إلى مجموعة لاسترجاع O(1).'