كيف يمكنني اختبار إذا أعطيت BSP الشجرة هو الأمثل ؟

Question

لدي المضلع حساء من المثلثات التي أود أن بناء BSP شجرة.بلدي الحالي البرنامج ببساطة يبني BSP شجرة عن طريق إدخال عشوائي مثلث من نموذج واحد في وقت واحد حتى مثلثات المستهلكة ، ثم التحقق من عمق واتساع الشجرة يتذكر أفضل درجة أنها حققت (أدنى عمق أدنى اتساع).

من خلال تعريف أفضل العمق سيكون log2(ن) (أو أقل إذا كان المشارك مستو مثلثات يتم تجميع?) حيث n هو عدد المثلثات في نموذج أفضل اتساع سيكون n (بمعنى لا تقسيم حدث).ولكن هناك بعض تكوينات من مثلثات هذه قمة لن يتم التوصل إلى اتفاق.

هل هناك فعال اختبار للتحقق من جودة BSP الشجرة ؟ على وجه التحديد, أنا أحاول العثور على طريقة للحصول على البرنامج أن تعرف أنها يجب أن تتوقف عن البحث أكثر الأمثل البناء.

Answer 1

وبناء شجرة الأمثل هو مشكلة NP-كاملة. تحديد ما إذا كانت شجرة معينة هي الأمثل هو في الأساس نفس المشكلة.

BSP التعليمات :

<اقتباس فقرة>   

والمشكلة هي واحدة من تقسيم مقابل   موازنة شجرة. هذه هي متبادل   متطلبات خاصة. يجب   اختيار لديك استراتيجية لبناء   شجرة جيدة على أساس مدى استعدادك ل   استخدام الشجرة.

Answer 2

وعشوائيا بناء أشجار BSP حتى لك فرصة بناء على واحدة جيدة وسوف يكون حقا، حقا غير فعالة.

وبدلا من اختيار ثلاثي عشوائيا لاستخدامه كقاعدة تقسيم الطائرة، وتريد أن تجرب عدة (ربما كل منهم، أو ربما أخذ العينات العشوائية) واختيار واحد وفقا لبعض مجريات الأمور. وعادة ما يستند الكشف عن مجريات الأمور على (أ) كيف متوازن العقد التابعة الناتجة سيكون، و (ب) كم تريس سيكون تقسيم.

ويمكنك مقايضة الأداء والجودة من خلال النظر في عينة أصغر أو أكبر من تريس مرشحا انقسام الطائرات.

ولكن في النهاية، لا يمكن أن نأمل في الحصول على شجرة مثلى تماما عن أي بيانات في العالم الحقيقي لذلك قد تضطر إلى تسوية ل"جيدة بما فيه الكفاية".

Answer 3

• في محاولة لاختيار الطائرات التي (قد) على تقسيم معظم الطائرات تقسيم الطائرات.تقسيم الطائرات لا يمكن أن يكون تقسيم.
• حاول اختيار الطائرة التي لديها ما يقرب من نفس العدد من الطائرات في الجبهة كما في الظهر.
• حاول اختيار الطائرة التي لا تسبب الكثير من الانقسامات.
• حاول اختيار الطائرة التي متحد المستوى مع الكثير من الأسطح الأخرى

عليك أن تذوق هذه المعايير تأتي مع نظام التهديف أن تقرر أي واحد هو الأكثر احتمالا أن يكون خيارا جيدا بالنسبة تقسيم الطائرة.على سبيل المثال ، زيادة توازنه ، والمزيد من النقاط فإنه يفقد.إذا كان يسبب 20 انشقاقات ، ثم عقوبة -5 * 20 (على سبيل المثال).اختيار واحد أن درجات أفضل.لم يكن لديك إلى عينة من كل مضلع, البحث فقط عن جيد.