कंप्यूटर साइंस में, बाइनरी स्पेस पार्टीशनिंग (BSP) नामक एक विधि को हाइपरप्लेन्स (Hyperplanes) को पार्टीशन के रूप में लागू करके एक स्पेस को दो कन्वेक्स सेट्स (Convex Sets) में पुनरावर्ती रूप से उप-विभाजित (Recursively Subdividing) करने के लिए लागू किया जाता है। उप-विभाजन की यह प्रक्रिया क्षेत्र में वस्तुओं के प्रतिनिधित्व को BSP ट्री के रूप में ज्ञात एक ट्री डेटा स्ट्रक्चर के रूप में जन्म देती है।
बाइनरी स्पेस पार्टीशनिंग का आविष्कार 1969 में 3D कंप्यूटर ग्राफिक्स के संदर्भ में किया गया था, जहां BSP ट्री की संरचना एक दृश्य में वस्तुओं के बारे में स्थानिक जानकारी तक त्वरित पहुंच की अनुमति देती है जो रेंडरिंग में उपयोगी है, जैसे दिए गए स्थान पर एक दर्शक के संबंध में वस्तुओं को फ्रंट-टू-बैक (Front-to-Back) क्रम में व्यवस्थित करना। BSP के अन्य अनुप्रयोगों में शामिल हैं: CAD में आकृतियों (Constructive Solid Geometry) के साथ ज्यामितीय ऑपरेशन करना, 3D वीडियो गेम और रोबोटिक्स में टकराव पहचान (Collision Detection), रे ट्रेसिंग (Ray Tracing), और अन्य अनुप्रयोग जिनमें जटिल स्थानिक दृश्यों को संभालना शामिल है।
अवलोकन (Overview)
बाइनरी स्पेस पार्टीशनिंग को एक सामान्य प्रक्रिया के रूप में माना जाता है जिसमें एक दृश्य को दो में पुनरावर्ती रूप से विभाजित किया जाता है जब तक कि पार्टीशनिंग एक या अधिक आवश्यकताओं को पूरा न कर ले। इसे k-d ट्रीज़ और क्वाडट्रीज़ (Quadtrees) जैसे अन्य स्थानिक ट्री संरचनाओं के सामान्यीकरण के रूप में देखा जा सकता है, जहां पार्टीशनिंग स्पेस के हाइपरप्लेन्स किसी भी ओरिएंटेशन के हो सकते हैं, बजाय इसके कि वे k-d ट्रीज़ या क्वाडट्रीज़ में जैसे कोऑर्डिनेट एक्सिस के साथ संरेखित हों। जब प्लेनर पॉलीगॉन्स (Planar Polygons) से बने दृश्यों को रेंडर करने के लिए कंप्यूटर ग्राफिक्स में लागू किया जाता है, तो पार्टीशनिंग प्लेन को अक्सर दृश्य में पॉलीगॉन्स द्वारा परिभाषित प्लेन के साथ मेल खाने के लिए चुना जाता है। पार्टीशनिंग प्लेन की विशिष्ट पसंद और पार्टीशनिंग प्रक्रिया को पूरा करने का मानदंड BSP ट्री के उद्देश्य के आधार पर भिन्न होता है। उदाहरण के लिए, कंप्यूटर ग्राफिक्स रेंडरिंग में, दृश्य को तब तक विभाजित किया जाता है जब तक कि BSP ट्री का प्रत्येक नोड केवल उन पॉलीगॉन्स से न बना हो जिन्हें मनमाने क्रम में रेंडर किया जा सके। जब बैक-फेस कलिंग (Back-face Culling) लागू किया जाता है, तो प्रत्येक नोड इसलिए पॉलीगॉन्स के एक कन्वेक्स सेट से बना होता है, जबकि डबल-साइडेड पॉलीगॉन्स रेंडर करते समय, BSP ट्री का प्रत्येक नोड केवल एक ही प्लेन में पॉलीगॉन्स से बना होता है। टकराव पहचान या रे ट्रेसिंग में, एक दृश्य को कुछ प्रिमिटिव्स (Primitives) में विभाजित किया जा सकता है जिन पर टकराव या रे इंटरसेक्शन टेस्ट सीधे होते हैं।
उत्पत्ति (Generation)
पेंटर एल्गोरिदम (Painter's Algorithm) की मदद से पॉलीगॉन्स रेंडर करने के लिए BSP ट्री का विहित कार्यान्वयन (Canonical Implementation) (जो डबल-साइडेड हैं, यानी बैक-फेस कलिंग के बिना) है। प्रत्येक पॉलीगॉन को एक फ्रंट साइड और एक बैक साइड के साथ नामित किया जाता है जिसे मनमाने ढंग से चुना जा सकता है और केवल ट्री की संरचना को प्रभावित करता है लेकिन आवश्यक परिणाम को नहीं। ऐसा ट्री दृश्य में सभी पॉलीगॉन्स की अनसॉर्टेड सूची से बनाया जाता है। उस पॉलीगॉन्स की सूची से BSP ट्री बनाने के लिए पुनरावर्ती एल्गोरिदम है:
- सूची से एक पॉलीगॉन A चुनें।
- BSP ट्री में एक नोड N बनाएं, और उस नोड पर पॉलीगॉन्स की सूची में A जोड़ें।
- सूची के प्रत्येक अन्य पॉलीगॉन के लिए
- यदि वह पॉलीगॉन A को समाहित करने वाले प्लेन के पूरी तरह सामने स्थित है, तो उस पॉलीगॉन को A के सामने के नोड्स की सूची में ले जाएं।
- यदि वह पॉलीगॉन A को समाहित करने वाले प्लेन के पूरी तरह पीछे स्थित है, तो उस पॉलीगॉन को P के पीछे के नोड्स की सूची में ले जाएं।
- यदि वह पॉलीगॉन A से बने प्लेन द्वारा प्रतिच्छेदित होता है, तो उसे दो पॉलीगॉन्स में विभाजित करें और उन्हें P के पीछे और सामने स्थित पॉलीगॉन्स की संबंधित सूचियों में ले जाएं।
- यदि वह पॉलीगॉन A को समाहित करने वाले प्लेन के भीतर स्थित है, तो इसे नोड N पर पॉलीगॉन्स की सूची में जोड़ें।
- इस एल्गोरिदम को A के सामने स्थित पॉलीगॉन्स की सूची पर लागू करें।
- इस एल्गोरिदम को A के पीछे स्थित पॉलीगॉन्स की सूची पर लागू करें।
