बाउंडिंग वॉल्यूम

असतत रेखाओं में खींचे गए बाउंडिंग बॉक्स के साथ 3D मॉडल।

कंप्यूटर ग्राफिक्स और कम्प्यूटेशनल ज्यामिति में, वस्तुओं के एक समुच्चय के लिए बाउंडिंग वॉल्यूम बंद वॉल्यूम है जिसमें समुच्चय में वस्तुओं का संघ पूरी तरह से सम्मलित होता है। अधिक जटिल वस्तुओं को सम्मलित करने के लिए साधारण वॉल्यूम का उपयोग करके ज्यामितीय संचालन की दक्षता में सुधार करने के लिए बाउंडिंग वॉल्यूम का उपयोग किया जाता है। सामान्यतः सरल वॉल्यूम में परस्पर-व्याप्त होने के परीक्षण की सरल विधियाँ होती हैं।

वस्तुओं के समूह के लिए बाउंडिंग वॉल्यूम भी उनके संघ से युक्त एकल वस्तु के लिए बाउंडिंग वॉल्यूम है जिसमें उनके संघ और दूसरी तरफ सम्मलित है। इसलिए, विवरण को किसी वस्तु के स्थितियों में सीमित करना संभव है, जिसे गैर-खाली और परिमित सीमित माना जाता है।

उपयोग

कुछ प्रकार के परीक्षणों में तेजी लाने के लिए बाउंडिंग वॉल्यूम का सबसे अधिक उपयोग किया जाता है।

किरण अनुरेखण में, बाउंडिंग वॉल्यूम का उपयोग किरण-प्रतिच्छेदन परीक्षणों में किया जाता है और कई प्रतिपादन एल्गोरिदम में, उनका उपयोग छिन्नक परीक्षण देखने के लिए किया जाता है। यदि किरण देखने वाला छिन्नक बाउंडिंग वॉल्यूम को प्रतिच्छेद नहीं है, तो यह क्षुद्र अस्वीकृति की अनुमति देते हुए, भीतर निहित वस्तु को प्रतिच्छेद नहीं कर सकता है। इसी प्रकार अगर छिन्नक में बाउंडिंग वॉल्यूम की संपूर्णता होती है, तो सामग्री को बिना किसी परीक्षण के क्षुद्र रूप से स्वीकार किया जा सकता है। ये प्रतिच्छेदन परीक्षण उन वस्तुओं की सूची उत्पन्न करते हैं जिन्हें 'प्रदर्शित' किया जाना चाहिए (प्रदत्त; रेखापुंज)।

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

बाउंडिंग वॉल्यूम की सरल ज्यामिति के कारण, बाउंडिंग वॉल्यूम के विरुद्ध परीक्षण सामान्यतः वस्तु के विरुद्ध परीक्षण करने की तुलना में बहुत तेज होता है। ऐसा इसलिए है क्योंकि 'वस्तु ' सामान्यतः बहुभुज डेटा संरचनाओं से बना होता है जो बहुभुज सन्निकटन में कम हो जाते हैं। किसी भी स्थिति में यदि वस्तु दिखाई नहीं दे रही है, तो दृश्य मात्रा के विरुद्ध प्रत्येक बहुभुज का परीक्षण करना कम्प्यूटेशनल रूप से व्यर्थ है। ऑनस्क्रीन वस्तुओं को स्क्रीन पर 'क्लिप' किया जाना चाहिए, यदि उनकी सतह वास्तव में दिखाई दे रही हों या नहीं।

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

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

सामान्य प्रकार

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

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

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

कई अनुप्रयोगों में बाउंडिंग बॉक्स को-समन्वय प्रणाली के अक्षों के साथ संरेखित किया जाता है और तब इसे अक्ष-संरेखित बाउंडिंग बॉक्स(एएबीबी) के रूप में जाना जाता है। सामान्य स्थितियों को एएबीबी से अलग करने के लिए, एकपक्षीय बाउंडिंग बॉक्स को कभी-कभी उन्मुख बाउंडिंग बॉक्स(ओबीबी) या ओओबीबी कहा जाता है, जब किसी उपस्थित वस्तु का स्थानीय समन्वय प्रणाली में उपयोग किया जाता है। एएबीबी ओबीबी की तुलना में प्रतिच्छेदन के लिए परीक्षण करने के लिए बहुत सरल हैं, किन्तु इसका अपहानि यह है कि जब मॉडल को घुमाया जाता है तो उन्हें इसके साथ आसानी से नहीं घुमाया जा सकता है, किन्तु फिर से गणना करने की आवश्यकता होती है।

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

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

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

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

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

बाउंडिंग त्रिकोण 2-D में बी-स्पलाइन वक्र की दृश्यता परीक्षण को गति देने के लिए अधिक उपयोगी है।उपयोग के उदाहरण के लिए क्लिपिंग (कंप्यूटर ग्राफिक्स) विषय के अनुसार "चक्र और बी-स्पलाइन क्लिपिंग एल्गोरिदम" देखें।

एक उत्तल संवरण सबसे छोटा उत्तल आयतन होता है जिसमें वस्तु होती है। यदि वस्तु बिंदुओं के परिमित समुच्चय का मिलन है, तो इसका उत्तल पॉलीटॉप है।

असतत उन्मुख पॉलीटॉप (डीओपी) बाउंडिंग बॉक्स का सामान्यीकरण करता है। k-डीओपी k दिशाओं के साथ विस्तारों का बूलियन प्रतिच्छेदन है। इस प्रकार, k-डीओपी k बाउंडिंग स्लैब का बूलियन प्रतिच्छेदन है और उत्तल पॉलीटॉप है 2-D में बहुभुज; 3-डी में बहुतल जिसमें वस्तु है। 2-D आयत 2-Dओपी का विशेष स्थिति है और 3-डी बॉक्स 3-डीओपी का विशेष स्थिति है। सामान्यतः, डीओपी के अक्षों को ऑर्थोगोनल नहीं होना चाहिए, और अंतरिक्ष के आयामों की तुलना में अधिक अक्ष हो सकते हैं। उदाहरण के लिए, 3-डी बॉक्स जिसे सभी किनारों और कोनों पर झुकाव किया गया है, उसे 13-डीओपी के रूप में बनाया जा सकता है। चेहरों की वास्तविक संख्या 2 गुना से कम हो सकती है यदि कुछ चेहरे पतित हो जाते हैं, किनारे या शीर्ष तक सिकुड़ जाते हैं।

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

बुनियादी प्रतिच्छेदन की जाँच

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

एएबीबी के स्थितियों में, यह परीक्षण इकाई अक्षों के संदर्भ में परस्पर-व्याप्त होना परीक्षणों का सरल समूह बन जाता है। M, N द्वारा परिभाषित एएबीबी के लिए O, P द्वारा परिभाषित के विरुद्ध वे छेड़छाड़ नहीं करते हैं (M_x > P_x) या (O_x > N_x) या (M_y > P_y) या (O_y > N_y) या (M_z > P_z) या (O_z > N_z).

एक एएबीबी को अक्ष के साथ भी प्रक्षेपित किया जा सकता है, उदाहरण के लिए, यदि इसकी लंबाई L के किनारे हैं और C पर केंद्रित है, और अक्ष N:
के साथ प्रक्षेपित किया जा रहा है $r=0.5L_{x}|N_{x}|+0.5L_{y}|N_{y}|+0.5L_{z}|N_{z}|\,$, और $b=C*N\,$ या $b=C_{x}N_{x}+C_{y}N_{y}+C_{z}N_{z}\,$, और $m=b-r,n=b+r\,$, जहाँ m और n न्यूनतम और अधिकतम विस्तार हैं।

एक OBB इस संबंध में समान है, किन्तु थोड़ा अधिक जटिल है। उपरोक्त के रूप में L और C के साथ ओबीबी के लिए, और ओबीबी के आधार अक्ष के रूप में I, J, और K के साथ, फिर

$r=0.5L_{x}|N*I|+0.5L_{y}|N*J|+0.5L_{z}|N*K|\,$

$m=C*N-r{\mbox{ and }}n=C*N+r\,$

श्रेणी m,n और o,p के लिए यह कहा जा सकता है कि यदि m > p या o > n है तो वे प्रतिच्छेद नहीं करते हैं। इस प्रकार, प्रत्येक OBB के I, J और K अक्षों के साथ 2 OBBs की श्रेणियों को परियोजन करके और गैर-प्रतिच्छेदन की जाँच करके पता लगाना संभव है। अतिरिक्त रूप से इन अक्षों के पार उत्पादों की जाँच करके (I₀×I₁, I ₀×J₁, ...) कोई और निश्चित हो सकता है कि प्रतिच्छेदन असंभव है।

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

दो K-डीओपी के प्रतिच्छेदन की गणना एएबीबी के समान ही की जा सकती है। प्रत्येक अभिविन्यास के लिए, आप केवल दो डीओपी के दो संबंधित अंतरालों की जांच करें। तो, जैसे डीओपी एएबीबी का सामान्यीकरण है, प्रतिच्छेदन परीक्षण एएबीबी परस्पर-व्याप्त होना परीक्षण का सामान्यीकरण है। दो डीओपी के परस्पर-व्याप्त होना परीक्षण की जटिलता में है O(k). चूंकि, यह माना जाता है कि दोनों डीओपी उन्मुखताओं के समान समूह के संबंध में दिए गए हैं। यदि उनमें से को घुमाया जाता है, तो यह अब सत्य नहीं है। उस स्थिति में, दो डीओपी की जांच करने का अपेक्षाकृत सरल विधि $D^{1},D^{2}$ प्रतिच्छेदन के लिए घुमाए गए को घेरना है, $D^{2}$, दूसरे द्वारा, सबसे छोटा संलग्न डीओपी ${\tilde {D}}^{2}$ जो पहले डीओपी के उन्मुखीकरण के संबंध में $D^{1}$ उन्मुख है। उसके लिए प्रक्रिया थोड़ी अधिक जटिल है, किन्तु अंततः जटिलता के आव्यूह वेक्टर गुणन की मात्रा O(k) भी है ।

यह भी देखें

• बाउंडिंग वृत्त
• उत्तल पतवार एल्गोरिदम
• न्यूनतम बाउंडिंग बॉक्स
• न्यूनतम बाउंडिंग आयत
• स्थानिक सूचकांक

बाहरी संबंध

• Illustration of several डीओपीs for the same model, from epicgames.com