عند استخدام ثنائي مساحة التقسيم ، Quadtree, Octree?

Question

وقد علمت مؤخرا حول ثنائي تقسيم مساحة الأشجار و تطبيقها على 3d الرسومات الكشف عن التصادم.لدي أيضا لفترة وجيزة طالع المواد المتعلقة quadtrees و octrees.عندما يمكنك استخدام quadtrees على bsp الأشجار أو العكس ؟ هم للتبادل?سأكون راضيا لو كان لدي معلومات كافية لملء الجدول مثل هذا:

            | BSP | Quadtree | Octree
------------+----------------+-------
Situation A |  X  |          |
Situation B |     |     X    |
Situation C |     |          |   X

ما هي A و B و C ؟

Answer 1

لا توجد إجابة واضحة على السؤال الخاص بك.ذلك يعتمد كليا كيفية تنظيم البيانات.

شيء أن نأخذ في الاعتبار:

Quadtrees تعمل بشكل أفضل مع البيانات التي في الغالب ثنائية الأبعاد مثل خريطة-التقديم في أنظمة الملاحة.في هذه الحالة انها أسرع من octrees لأنها تتكيف بشكل أفضل هندسة وتبقى العقدة-هياكل صغيرة.

Octrees و BVHs (إحاطة حجم الهرمية) فائدة إذا كانت البيانات ثلاثية الأبعاد.كما أنها تعمل بشكل جيد جدا إذا هندسية الكيانات تتجمع في الفضاء 3D.(انظر Octree مقابل BVH)

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

BSP-الأشجار هي حالة خاصة حقا.أنها تعمل جيدا جدا في 2D و 3D ، ولكن توليد جيدة BSP أشجار هو شكل من اشكال الفن من تلقاء نفسها.BSP-الأشجار العيب أن قد تضطر إلى تقسيم الهندسة إلى قطع أصغر.هذا يمكن أن تزيد من العام المضلع-عد من مجموعة البيانات.فهي لطيفة على التقديم ، لكنها أفضل بكثير من أجل الكشف عن التصادم و ray-tracing.

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

هذا بالمناسبة هو السبب في أنها كانت شعبية جدا قبل 10 سنوات.الزلزال استخدمها لأنه يسمح محرك الرسومات / برنامج rasterizer عدم استخدام مكلفة z-buffer.

كل الأشجار المذكورة هي مجرد الأسر من الأشجار.هناك فضفاضة octrees دينار كويتي-أشجار الهجين-الأشجار والكثير من الهياكل ذات الصلة أيضا.

Answer 2

أكبر فرق عملي بين BSP-الأشجار وغيرها من أنواع 3d-الأشجار التي BSP-الأشجار يمكن أن يكون أكثر الأمثل ولكن تعمل فقط على ثابت الهندسه.وهذا لأن BSP-الأشجار عموما بطيئة جدا لبناء وغالبا ما يأخذ ساعات أو أيام نموذجية الساكنة الحضرية مستوى اللعبة.

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

أنواع أخرى من 3d-الأشجار (Octrees, Quadtrees دينار كويتي-شجرة وثاب-حجم-الهرمي) استخدام محور الانحياز إحاطة مجلدات و مجلدات (اختياريا) يسمح التداخل ، لذا الواردة الأشياء لا تحتاج إلى قطع في حجم الحدود.كل هذه تجعل الأشجار أقل مثالية من BSP-الأشجار ، ولكن أسرع في بناء و أسهل إلى تغيير ديناميكية الأجسام.

استقراء هذه العوامل في حالات...

المناطق في الهواء الطلق عادة استخدام الارتفاع الميدانية القائمة على الأرض تعهدات سواء بسيطة heightmaps أو أكثر تعقيدا geo-mip-تقنيات رسم الخرائط مثل التجول.الأرض نفسها لا تشارك في الفضاء 3d التقسيم فقط الأشياء الموضوعة على الأرض.

العالمين مع الكثير من الحالات من أبسط مماثلة الهندسة (المنازل, الأشجار, الكويكبات, الخ) وغالبا ما تستخدم غير BSP-شجرة (مثل BVH) ، لأن وضع الهندسة في BSP-شجرة يعني تكرار وتقسيم التفاصيل الهندسة لكل مثيل.

على العكس كبيرة ثابتة مخصصة مش مع أي المثيلات مثل المشهد الحضري ، أو معقدة البيئة الداخلية ، عادة ما تستخدم BSP-شجرة تحسين وقت الأداء.حقيقة أن BSP-شجرة انشقاقات الهندسة على عقدة الحدود مفيد تقديم الأداء ، لأن BSP العقد يمكن أن تستخدم من قبل تنظيم مثلث تقديم دفعات.BSP-شجرة يمكن أيضا أن تكون الأمثل انسداد تجنب الحاجة إلى رسم أجزاء من BSP-الشجرة التي هي معروفة لتكون خلف هندسة أخرى.

انظر أيضا: Octree مقابل BVH, إحاطة حجم الهرمي التعليمي, BSP التعليمي.

Answer 3

BSP هو أفضل البيئات الحضرية.

أ Quadtree هو أفضل عند استخدام ارتفاع خريطة التضاريس ، إلخ.

وهو Octree هو أفضل عندما يكون لديك كتل الهندسة في الفضاء 3d ، مثل نظام الطاقة الشمسية.

Answer 4

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

أما بالنسبة استخدامها في الرسومات ، BSPs حد كبير عفا عليها الزمن.Octrees عمل أشياء مثل الإجمالي الرؤية اعدام ، كما تفعل AABB الأشجار.

Answer 5

ليس لدي الكثير من الخبرة مع BSPs ، ولكن أستطيع أن أقول أن عليك أن تذهب مع octrees على quadtrees عند المشهد أنت التقديم هو طويل القامة.أي أن ارتفاع أكثر من نصف العرض و العمق-القليل من الإبهام.عموما, octrees لن تجلب تكلفة ضخمة على quadtrees و لديهم القدرة على تسريع الامور لائقة بعض الشيء.YMMV.

Answer 6

عادة ما تكون هذه الأشياء ليس لدي جواب واضح.أود أن أقترح أن A و B و C هي نتيجة وظيفة من حجم المساحة الخاصة بك وكمية من الاشياء كنت التفريق.

Answer 7

BSP أفضل أصغر وأبسط المساحة التي تريد فقط أن تفعل مع انسداد.إذا كنت تريد جميع التقاطعات معين راي, سوف تحتاج إلى الترقية إلى رباعية/octree.

أما بالنسبة quadtree مقابلoctree - كيف العديد من الأبعاد تهتم الكثير عنه ؟ بعدين يعني quadtree أربعة وهي octree.كما جاء ، quadtree يمكن أن تعمل في الفضاء ، ولكن إذا كنت تريد كل البعد إعطاء العلاج المناسب ، octree هو الطريق للذهاب.