बाइनरी स्पेस विभाजन, क्वाड्री, ऑक्ट्री का उपयोग कब करें?

Question

मैंने हाल ही में बाइनरी स्पेस विभाजन पेड़ और उनके आवेदन को 3 डी ग्राफिक्स और टकराव का पता लगाने के बारे में सीखा है। मैंने क्वाड्रिस और ऑक्टेट से संबंधित सामग्री को संक्षेप में भी देखा है। आप बीएसपी पेड़ों पर क्वाड्रिस का उपयोग कब करेंगे, या इसके विपरीत? क्या वे अदलाबदल योग्य हैं? अगर मैं इस तरह की टेबल भरने के लिए पर्याप्त जानकारी प्राप्त करता हूं तो मुझे संतुष्ट होगा:

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

ए, बी, और सी क्या हैं?

Answer 1

आपके प्रश्न का कोई स्पष्ट जवाब नहीं है। यह पूरी तरह निर्भर करता है कि आपका डेटा कैसे व्यवस्थित किया जाता है।

को ध्यान में रखना कुछ:

Quadtrees डेटा लिए सबसे अच्छा काम करता है नेविगेशन सिस्टम में ज्यादातर दो आयामी तरह नक्शे-प्रतिपादन। इस मामले में यह octrees से तेज़ है क्योंकि यह ज्यामिति के लिए बेहतर अनुकूल है और नोड-संरचनाओं को छोटा रखता है।

ऑक्टिक और बीवीएच (बाउंडिंग वॉल्यूम पदानुक्रम) लाभ अगर डेटा तीन आयामी है। यदि आपकी ज्यामितीय इकाइयां 3 डी स्पेस में क्लस्टर हैं तो यह भी बहुत अच्छी तरह से काम करता है। (Octree vs BVH देखें)

ओसी- और क्वाड्रिस का लाभ यह है कि आप कभी भी पेड़ पैदा करना बंद कर सकते हैं। यदि आप ग्राफ़िक त्वरक का उपयोग करके ग्राफिक्स प्रस्तुत करना चाहते हैं तो यह आपको ऑब्जेक्ट स्तर पर पेड़ उत्पन्न करने की अनुमति देता है और प्रत्येक ऑब्जेक्ट को ग्राफिक्स एपीआई में एकल ड्रॉ-कॉल में भेजता है। यह व्यक्तिगत त्रिकोण भेजने से अधिक बेहतर करता है (यदि आप बीएसपी-पेड़ का पूर्ण सीमा तक उपयोग करते हैं तो आपको कुछ करना होगा)।

बीएसपी-पेड़ वास्तव में एक विशेष मामला है। वे 2 डी और 3 डी में बहुत अच्छी तरह से काम करते हैं, लेकिन अच्छे बीएसपी-पेड़ पैदा करना स्वयं पर एक कला रूप है। बीएसपी-पेड़ में कमी है कि आपको अपनी ज्यामिति को छोटे टुकड़ों में विभाजित करना पड़ सकता है। यह आपके डेटा-सेट की समग्र बहुभुज-गिनती को बढ़ा सकता है। वे प्रतिपादन के लिए अच्छे हैं, लेकिन वे टकराव का पता लगाने और रे-ट्रेसिंग के लिए बहुत बेहतर हैं।

बीएसपी-पेड़ों की एक अच्छी संपत्ति यह है कि वे एक बहुभुज-सूप को एक संरचना में विघटित करते हैं जिसे वास्तविक रूप से बिना किसी कैमरे की स्थिति से सामने (और इसके विपरीत) पूरी तरह से प्रस्तुत किया जा सकता है। प्रत्येक दृष्टिकोण से ऑर्डर डेटा-स्ट्रक्चर का हिस्सा है और बीएसपी-ट्री संकलन के दौरान किया जाता है।

कि, वैसे, यही कारण है कि वे 10 साल पहले इतने लोकप्रिय थे। क्वैक ने उन्हें इस्तेमाल किया क्योंकि यह ग्राफिक इंजन/सॉफ्टवेयर रास्टराइज़र को महंगा ज़ेड-बफर का उपयोग करने की अनुमति नहीं देता था।

वर्णित सभी पेड़ पेड़ों के परिवार हैं। ढीले ऑक्टेट्री, केडी-पेड़ हाइब्रिड-पेड़ और अन्य कई संबंधित संरचनाएं भी हैं।

Answer 2

मुझे बीएसपी के साथ बहुत अधिक अनुभव नहीं है, लेकिन मैं कह सकता हूं कि जब आप जिस दृश्य को प्रतिपादित कर रहे हैं वह आपको लंबा है तो आपको क्वाड्री पर ऑक्टेट के साथ जाना चाहिए। यही है, ऊंचाई चौड़ाई और गहराई से अधिक है - अंगूठे का थोड़ा नियम। आम तौर पर, octrees quadtrees पर एक बड़ी लागत नहीं लाएगा और उनके पास चीजों को गतिशील बिट करने की क्षमता है। YMMV।

Answer 3

आमतौर पर इन चीजों का स्पष्ट-स्पष्ट उत्तर नहीं होता है। मैं सुझाव दूंगा कि ए, बी, और सी आपकी जगह के आकार और आपके द्वारा अलग-अलग सामानों की मात्रा के एक फ़ंक्शन का परिणाम हैं।

Answer 4

एक बीएसपी एक छोटी, सरल जगह के लिए बेहतर है जिसे आप केवल भ्रम करना चाहते हैं। यदि आप किसी दिए गए किरण के लिए सभी चौराहे चाहते हैं, तो आपको एक ट्रैक्टर/ऑक्टेटरी में अपग्रेड करना होगा।

क्वाड्री बनाम ऑक्टेट्री के लिए - आप कितने आयामों की परवाह करते हैं? दो आयामों का अर्थ है क्वाड्री, चार एक ऑक्टेट्री। जैसा कि कहा गया है, चूंकि क्वाड्री तीन-स्थान पर काम कर सकता है, लेकिन यदि आप चाहते हैं कि प्रत्येक आयाम उचित उपचार दे, तो एक ऑक्टेट जाने का रास्ता है।

Answer 5

शहरी वातावरण के लिए एक बीएसपी सर्वोत्तम है।

एक Quadtree जब आप इलाके के ऊंचाई मानचित्र का उपयोग करने के लिए सबसे अच्छा है, आदि

एक Octree आप इस तरह के एक सौर प्रणाली के रूप में 3 डी अंतरिक्ष, में ज्यामिति के गुच्छों है जब के लिए सबसे अच्छा है।

Answer 6

बीएसपी टकराव का पता लगाने के लिए एक अच्छा विकल्प है, जिसके आधार पर आप किस स्वाद का उपयोग करते हैं। वे बिंदु और रेखा या रे परीक्षणों पर विशेष रूप से तेज़ होते हैं, कुछ हद तक कम तेज़ और मात्रा के साथ चीजों के लिए थोड़ा अधिक जटिल होते हैं।

ग्राफिक्स में उनके उपयोग के लिए, बीएसपी बहुत अप्रचलित हैं। एएबीबी पेड़ के रूप में, सकल दृश्यता को कम करने जैसी चीजों के लिए ऑक्टिस अच्छी तरह से काम करते हैं।

Answer 7

बीएसपी-पेड़ और 3 डी पेड़ों के अन्य प्रकार के बीच सबसे बड़ा व्यावहारिक अंतर यह है कि बीएसपी-पेड़ अधिक इष्टतम हो सकते हैं लेकिन केवल स्थिर ज्यामिति पर काम करते हैं। ऐसा इसलिए है क्योंकि बीएसपी-पेड़ आमतौर पर निर्माण करने में बहुत धीमे होते हैं, अक्सर एक ठेठ स्थिर शहरी गेम स्तर के लिए घंटों या दिन लगते हैं।

बीएसपी-पेड़ बनाने के लिए लंबे समय तक ले जाने के दो मुख्य कारण हैं (ए) वे गैर-अक्ष-संरेखित विभाजन विमानों का उपयोग करते हैं, जो अधिक समय तक बेहतर रूप से ढूंढते हैं, और (बी) वे धुरी सीमाओं पर ज्यामिति को उप-विभाजित करते हैं, कोई ऑब्जेक्ट नहीं देते हैं पार विभाजित विमानों।

अन्य प्रकार के 3 डी-पेड़ (ऑक्ट्री, क्वाड्रिस, केडी-पेड़, बाउंडिंग-वॉल्यूम-पदानुक्रम) धुरी-गठबंधन बाध्यकारी वॉल्यूम का उपयोग करते हैं, और वॉल्यूम (वैकल्पिक रूप से) ओवरलैप करने की अनुमति देते हैं, इसलिए निहित वस्तुओं की आवश्यकता नहीं होती है मात्रा सीमाओं पर कटौती। ये दोनों पेड़ को बीएसपी-पेड़ों की तुलना में कम इष्टतम बनाते हैं, लेकिन गतिशील वस्तुओं के लिए बदलने के लिए तेज़ी से और आसान बनाना।

स्थितियों में इन कारकों Extrapolating ...

आउटडोर क्षेत्रों में आम तौर ऊंचाई मैदान आधारित जमीन अभ्यावेदन, या तो साधारण heightmaps या ROAM की तरह अधिक जटिल भू-MIP-मानचित्रण तकनीक का उपयोग करें। जमीन खुद ही 3 डी अंतरिक्ष विभाजन में भाग नहीं लेती है, केवल जमीन पर रखी वस्तुओं।

सरल और समान ज्यामिति के उदाहरण (घरों, पेड़, क्षुद्रग्रहों, आदि) अक्सर एक गैर बसपा-वृक्ष (जैसे एक BVH के रूप में) का उपयोग करेगा की बहुत सारी के साथ दुनिया, क्योंकि एक बसपा-पेड़ में ज्यामिति डालने का मतलब होगा प्रत्येक उदाहरण के लिए विवरण ज्यामिति को डुप्लिकेट करना और विभाजित करना।

इसके विपरीत, कोई शहरी दृश्य, या एक जटिल इनडोर वातावरण जैसे किसी भी इंस्टेंटिंग के साथ एक बड़ा कस्टम स्थैतिक जाल, आमतौर पर बेहतर रनटाइम प्रदर्शन के लिए बसपा-पेड़ का उपयोग करेगा। तथ्य यह है कि बीएसपी-पेड़ नोड-सीमाओं पर ज्यामिति को विभाजित करता है, प्रदर्शन को प्रस्तुत करने में सहायक होता है, क्योंकि बीएसपी नोड्स को पूर्व-संगठित त्रिभुज प्रतिपादन बैचों के रूप में उपयोग किया जा सकता है। बीएसपी-ट्री को भी बीएसपी-ट्री के हिस्सों को आकर्षित करने की आवश्यकता से परहेज करते हुए, अन्य ज्यामिति के पीछे जाने के लिए प्रक्षेपण के लिए अनुकूलित किया जा सकता है।

यह भी देखें: Octree vs BVH, Bounding Volume Hierarchy Tutorial, BSP Tutorial।