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

धराशायी लाइनों में खींचे गए आकार निर्धारक बॉक्स के साथ एक 3D मॉडल।

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

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

उपयोग

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

एbounding slab वह आयतन है जो एक अक्ष पर एक हद तक प्रोजेक्ट करता है, और इसे दो विमानों के बीच बंधे हुए स्लैब (ज्यामिति) के रूप में माना जा सकता है। एक बाउंडिंग बॉक्स ऑर्थोगोनली ओरिएंटेड बाउंडिंग स्लैब का प्रतिच्छेदन है। किरण अनुरेखण (ग्राफिक्स) को गति देने के लिए बाउंडिंग स्लैब का उपयोग किया गया है एbounding triangle 2-डी में बी-स्पलाइन वक्र की क्लिपिंग या दृश्यता परीक्षण को गति देने के लिए काफी उपयोगी है। क्लिपिंग (कंप्यूटर ग्राफिक्स)#Algorithms| देखें उपयोग के उदाहरण के लिए विषय क्लिपिंग (कंप्यूटर ग्राफिक्स) के तहत सर्कल और बी-स्पलाइन क्लिपिंग एल्गोरिदम।

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

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

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

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

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

एएबीबी के स्थितियों में, यह परीक्षण इकाई अक्षों के संदर्भ में परस्पर-व्याप्त होना परीक्षणों का एक सरल समूह बन जाता है। एम, एन द्वारा परिभाषित एएबीबी के लिए ओ, पी द्वारा परिभाषित एक के खिलाफ वे छेड़छाड़ नहीं करते हैं (एम_x> पी_x) या (ओ_x> एन_x) या (एम_y> पी_y) या (ओ_y> एन_y) या (एम_z> पी_z) या (ओ_z> एन_z).

एक AABB को एक अक्ष के साथ भी प्रक्षेपित किया जा सकता है, उदाहरण के लिए, यदि इसकी लंबाई 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 इस संबंध में समान है, लेकिन थोड़ा अधिक जटिल है। उपरोक्त के रूप में एल और सी के साथ ओबीबी के लिए, और ओबीबी के आधार अक्ष के रूप में 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₁, मैं₀×J₁, ...) कोई और निश्चित हो सकता है कि चौराहा असंभव है।

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

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

यह भी देखें

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

बाहरी संबंध

• Illustration of several DOPs for the same model, from epicgames.com