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