कंप्यूटर विज्ञान में, बाइनरी स्पेस पार्टीशनिंग (बीएसपी) के रूप में जाना जाने वाला एक तरीका हाइपरप्लेन को विभाजन के रूप में लागू करके एक स्थान को दो उत्तल सेटों में पुनरावर्ती रूप से उप-विभाजित करने के लिए लागू किया जाता है। उप-विभाजन की यह प्रक्रिया एक पेड़ डेटा संरचना के रूप में क्षेत्र के भीतर वस्तुओं के प्रतिनिधित्व को जन्म देती है जिसे बीएसपी पेड़ के रूप में जाना जाता है।
बाइनरी स्पेस पार्टिशनिंग का आविष्कार 1969 में 3डी कंप्यूटर ग्राफिक्स के संदर्भ में किया गया था, जहां एक बसपा पेड़ की संरचना एक दृश्य में वस्तुओं के बारे में स्थानिक जानकारी के लिए अनुमति देती है जो कि प्रतिपादन में उपयोगी होती है, जैसे वस्तुओं को आगे से पीछे से ऑर्डर किया जा रहा है किसी दिए गए स्थान पर एक दर्शक के संबंध में, जल्दी से पहुँचा जा सकता है। बीएसपी के अन्य अनुप्रयोगों में शामिल हैं:सीएडी में आकृतियों (रचनात्मक ठोस ज्यामिति) के साथ ज्यामितीय संचालन को पूरा करना, 3 डी वीडियो गेम और रोबोटिक्स में टकराव का पता लगाना, रे ट्रेसिंग, और अन्य अनुप्रयोग जिनमें जटिल स्थानिक दृश्यों को संभालना शामिल है।
अवलोकन
बाइनरी स्पेस पार्टिशनिंग को एक दृश्य को दो भागों में पुनरावर्ती रूप से विभाजित करने की एक सामान्य प्रक्रिया के रूप में माना जाता है जब तक कि विभाजन एक या अधिक आवश्यकताओं को पूरा नहीं करता है। इसे अन्य स्थानिक वृक्ष संरचनाओं के सामान्यीकरण के रूप में देखा जा सकता है जैसे कि के-डी पेड़ और क्वाडट्री, एक जहां हाइपरप्लेन जो अंतरिक्ष को विभाजित करते हैं, समन्वय अक्षों के साथ गठबंधन होने के बजाय किसी भी अभिविन्यास हो सकते हैं क्योंकि वे के-डी पेड़ या क्वाडट्री में हैं। जब प्लेनर पॉलीगॉन से बने दृश्यों को प्रस्तुत करने के लिए कंप्यूटर ग्राफिक्स में लागू किया जाता है, तो विभाजन वाले विमानों को अक्सर दृश्य में पॉलीगॉन द्वारा परिभाषित विमानों के साथ मेल खाने के लिए चुना जाता है। विभाजन विमान की विशिष्ट पसंद और विभाजन प्रक्रिया को पूरा करने के लिए मानदंड बसपा वृक्ष के उद्देश्य के आधार पर भिन्न होता है। उदाहरण के लिए, कंप्यूटर ग्राफिक्स रेंडरिंग में, दृश्य को तब तक विभाजित किया जाता है जब तक कि बीएसपी पेड़ के प्रत्येक नोड में केवल बहुभुज होते हैं जो मनमाने ढंग से प्रस्तुत कर सकते हैं। जब बैक-फेस कलिंग को लागू किया जाता है, तो प्रत्येक नोड में बहुभुजों का एक उत्तल सेट होता है, जबकि दो तरफा बहुभुज प्रदान करते समय, बसपा पेड़ के प्रत्येक नोड में एक ही विमान में केवल बहुभुज होते हैं। टक्कर का पता लगाने या किरण अनुरेखण में, एक दृश्य को कुछ आदिम में विभाजित किया जा सकता है, जिस पर टकराव या किरण प्रतिच्छेदन परीक्षण सीधे होते हैं।
पीढ़ी
एक बसपा पेड़ का विहित कार्यान्वयन चित्रकार के एल्गोरिथ्म की मदद से बहुभुज (जो दो तरफा हैं, यानी बिना बैक-फेस कलिंग के) को प्रस्तुत करने के लिए है। प्रत्येक बहुभुज को सामने की ओर और पीछे की ओर से नामित किया जाता है जिसे मनमाने ढंग से चुना जा सकता है और केवल पेड़ की संरचना को प्रभावित करता है लेकिन आवश्यक परिणाम नहीं। ऐसा पेड़ एक दृश्य में सभी बहुभुजों की एक अनसुलझी सूची से बनाया गया है। पॉलीगॉन की उस सूची से बसपा ट्री बनाने के लिए पुनरावर्ती एल्गोरिथम है
- सूची से बहुभुज A चुनें।
- बीएसपी ट्री में एक नोड एन बनाएं, और उस नोड पर पॉलीगॉन की सूची में ए जोड़ें।
- एक दूसरे के बहुभुज की सूची के लिए
- यदि वह बहुभुज A वाले तल के बिल्कुल सामने स्थित है, तो उस बहुभुज को A के सामने नोड्स की सूची में ले जाएं।
- यदि वह बहुभुज A वाले तल के बिल्कुल पीछे स्थित है, तो उस बहुभुज को P के पीछे स्थित नोड्स की सूची में ले जाएं।
- यदि उस बहुभुज को A के समतल द्वारा प्रतिच्छेद किया जाता है, तो उसे दो बहुभुजों में विभाजित करें और उन्हें P के पीछे और सामने स्थित बहुभुजों की संबंधित सूचियों में ले जाएँ।
- यदि वह बहुभुज A वाले तल के भीतर स्थित है, तो उसे नोड N पर बहुभुजों की सूची में जोड़ें।
- ए के सामने स्थित बहुभुजों की सूची में इस एल्गोरिथम को लागू करें।
- इस एल्गोरिथम को A के पीछे स्थित बहुभुजों की सूची में लागू करें।