कोलिजन डिटेक्शन

This article is about गणनात्मक ज्यामिति में टकराव का पता लगाना. For कंप्यूटर नेटवर्क में टकराव का पता लगाना, see टकराव की जांच के साथ कैरियर सेंस मल्टीपल एक्सेस.

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

अवलोकन

टकराव का पता लगाने के विज्ञान के भीतर बिलियर्ड्स गेंदों को एक-दूसरे से टकराना एक उत्कृष्ट उदाहरण है।

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

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

कंप्यूटर अनुकरण में टक्कर (भिड़ंत) का पता लगाना

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

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

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

दूसरे शब्दों में, भौतिक सिमुलेटर आमतौर पर दो तरीकों में से एक कार्य करते हैं, जहां टक्कर का पता एक पश्चवर्ती (टक्कर होने के बाद) या एक प्राथमिकता (टक्कर होने से पहले) लगता है। पश्चवर्ती और प्राथमिक भेद के अलावा, लगभग सभी आधुनिक टकराव का पता लगाने वाले एल्गोरिदम को एल्गोरिदम के पदानुक्रम में विभाजित किया गया है। अक्सर "असतत" और "निरंतर" शब्दों का उपयोग पश्चवर्ती और प्राथमिकता के बजाय किया जाता है।

एक पोस्टीरियरी (असतत) बनाम एक प्राथमिकता (निरंतर)

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

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

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

दूसरी ओर, एक पश्चवर्ती एल्गोरिदम फिक्सिंग चरण में समस्याएँ पैदा करता है, जहाँ चौराहों (जो शारीरिक रूप से सही नहीं हैं) को ठीक करने की आवश्यकता होती है। इसके अलावा, यदि असतत कदम बहुत बड़ा है, तो टकराव का पता नहीं चल सकता है, जिसके परिणामस्वरूप एक वस्तु जो दूसरे के माध्यम से गुजरती है, अगर यह पर्याप्त रूप से तेज या छोटी है।

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

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

अनुकूलन

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

लौकिक सुसंगतता का शोषण

कई अनुप्रयोगों में, एक चरण से अगले चरण तक भौतिक निकायों का विन्यास बहुत कम बदलता है। हो सकता है कि बहुत सी वस्तुएं बिल्कुल भी न हिलें। एल्गोरिदम को डिज़ाइन किया गया है ताकि पूर्ववर्ती समय चरण में की गई गणनाओं को वर्तमान समय चरण में पुन: उपयोग किया जा सके, जिसके परिणामस्वरूप गणना तेजी से पूरी हो सके।

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

प्रत्येक बॉक्स को तीन अंतरालों के उत्पाद द्वारा दर्शाया जाता है (यानी, एक बॉक्स होगा $I_{1}\times I_{2}\times I_{3}=[a_{1},b_{1}]\times [a_{2},b_{2}]\times [a_{3},b_{3}]$). बाउंडिंग बॉक्स की टक्कर का पता लगाने के लिए एक सामान्य एल्गोरिथ्म झाड़ू और छँटाई है। ध्यान दीजिए कि ऐसे दो डिब्बे, $I_{1}\times I_{2}\times I_{3}$ और $J_{1}\times J_{2}\times J_{3}$ यदि और केवल यदि | यदि, और केवल यदि, प्रतिच्छेद करें $I_{1}$ काटती है $J_{1}$, $I_{2}$ काटती है $J_{2}$ और $I_{3}$ काटती है $J_{3}$. ऐसा माना जाता है कि, एक चरण से दूसरे चरण तक, $I_{k}$ और $J_{k}$ प्रतिच्छेद करते हैं, तो यह बहुत संभावना है कि अगली बार चरण में वे अभी भी प्रतिच्छेद करेंगे। इसी तरह, यदि वे पिछले समय के चरण में प्रतिच्छेद नहीं करते हैं, तो उनके न जारी रहने की बहुत संभावना है।

इसलिए हम फ्रेम से फ्रेम तक ट्रैकिंग की समस्या को कम कर देते हैं, जो अंतराल प्रतिच्छेद करते हैं। हमारे पास अंतराल की तीन सूचियाँ हैं (प्रत्येक अक्ष के लिए एक) और सभी सूचियाँ समान लंबाई की हैं (क्योंकि प्रत्येक सूची की लंबाई है $n$, बाउंडिंग बॉक्स की संख्या।) प्रत्येक सूची में, प्रत्येक अंतराल को सूची में अन्य सभी अंतरालों को प्रतिच्छेद करने की अनुमति है। तो प्रत्येक सूची के लिए, हमारे पास एक होगा $n\times n$ मैट्रिक्स (गणित) $M=(m_{ij})$ शून्य और वाले का: $m_{ij}$ 1 है अगर अंतराल $i$ और $j$ प्रतिच्छेद करें, और 0 यदि वे प्रतिच्छेद नहीं करते हैं।

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

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

यदि किसी दृश्य में भौतिक पिंडों के वेग पर एक ऊपरी सीमा रखी जा सकती है, तो वस्तुओं के जोड़े को उनकी प्रारंभिक दूरी और समय चरण के आकार के आधार पर छंटाई की जा सकती है।

जोड़ो में छंटाई

एक बार जब हम आगे की जांच के लिए भौतिक पिंडों की एक जोड़ी का चयन कर लेते हैं, तो हमें टकरावों की अधिक सावधानी से जांच करने की आवश्यकता होती है। हालाँकि, कई अनुप्रयोगों में, अलग-अलग वस्तुओं (यदि वे बहुत विकृत नहीं हैं) को छोटे आदिमों के एक सेट द्वारा वर्णित किया जाता है, मुख्य रूप से त्रिकोण। तो अब, हमारे पास त्रिभुजों के दो सेट हैं, $S={S_{1},S_{2},\dots ,S_{n}}$ और $T={T_{1},T_{2},\dots ,T_{n}}$ (सादगी के लिए, हम मान लेंगे कि प्रत्येक सेट में त्रिभुजों की संख्या समान है।)

करने के लिए स्पष्ट बात सभी त्रिकोणों की जांच करना है $S_{j}$ सभी त्रिकोणों के खिलाफ $T_{k}$ टक्करों के लिए, लेकिन इसमें शामिल है $n^{2}$ तुलना, जो अत्यधिक अक्षम है। यदि संभव हो, तो हमें जाँचने के लिए आवश्यक त्रिभुजों के जोड़े की संख्या को कम करने के लिए छंटाई एल्गोरिथ्म का उपयोग करना वांछनीय है।

एल्गोरिदम के सबसे व्यापक रूप से उपयोग किए जाने वाले परिवार को श्रेणीबद्ध बाउंडिंग वॉल्यूम विधि के रूप में जाना जाता है। प्रीप्रोसेसिंग कदम के रूप में, प्रत्येक वस्तु के लिए (हमारे उदाहरण में, $S$ और $T$) हम एक बाउंडिंग वॉल्यूम पदानुक्रम की गणना करेंगे। फिर, प्रत्येक समय कदम पर, जब हमें टकराव की जांच करने की आवश्यकता होती है $S$ और $T$, विचाराधीन त्रिकोणों के जोड़े की संख्या को कम करने के लिए पदानुक्रमित बाउंडिंग वॉल्यूम का उपयोग किया जाता है। सरलता के लिए, हम बाउंडिंग स्फेयर का उपयोग करते हुए एक उदाहरण देंगे, हालांकि यह देखा गया है कि कई मामलों में स्फेयर अवांछनीय होते हैं। यदि $E$ त्रिकोणों का एक सेट है, हम एक बाउंडिंग गोले की पूर्व गणना कर सकते हैं $B(E)$. चुनने के कई तरीके हैं $B(E)$, हम केवल यह मानते हैं $B(E)$ एक गोला है जिसमें पूरी तरह शामिल है $E$ और जितना संभव हो उतना छोटा है।

समय से पहले, हम गणना कर सकते हैं $B(S)$ और $B(T)$. स्पष्ट रूप से, यदि ये दो गोले प्रतिच्छेद नहीं करते हैं (और यह परीक्षण करना बहुत आसान है), तो न तो करें $S$ और $T$. हालाँकि, यह एन-बॉडी प्रूनिंग एल्गोरिथम से बहुत बेहतर नहीं है।

यदि $E={E_{1},E_{2},\dots ,E_{m}}$ त्रिकोणों का एक समूह है, तो हम इसे दो हिस्सों में विभाजित कर सकते हैं $L(E):={E_{1},E_{2},\dots ,E_{m/2}}$ और $R(E):={E_{m/2+1},\dots ,E_{m-1},E_{m}}$. हम यह कर सकते हैं $S$ और $T$, और हम (समय से पहले) सीमा क्षेत्रों की गणना कर सकते हैं $B(L(S)),B(R(S))$ और $B(L(T)),B(R(T))$. यहाँ आशा यह है कि ये सीमाबद्ध गोले इससे बहुत छोटे हैं $B(S)$ और $B(T)$. और, यदि, उदाहरण के लिए, $B(S)$ और $B(L(T))$ प्रतिच्छेद न करें, तो किसी त्रिभुज को अंदर जाँचने का कोई मतलब नहीं है $S$ किसी भी त्रिकोण के खिलाफ $L(T)$.

एक पूर्वगणना के रूप में, हम प्रत्येक भौतिक शरीर (त्रिकोणों के एक सेट द्वारा दर्शाया गया) ले सकते हैं और इसे पुनरावर्ती रूप से एक बाइनरी ट्री में विघटित कर सकते हैं, जहाँ प्रत्येक नोड $N$ त्रिकोणों के एक समूह का प्रतिनिधित्व करता है, और उसके दो बच्चे प्रतिनिधित्व करते हैं $L(N)$ और $R(N)$. पेड़ में प्रत्येक नोड पर, हम बाउंडिंग क्षेत्र की पूर्व-गणना कर सकते हैं $B(N)$.

जब टकराव के लिए वस्तुओं की एक जोड़ी का परीक्षण करने का समय आता है, तो उनके बाउंडिंग स्फेयर ट्री का उपयोग त्रिकोण के कई जोड़े को खत्म करने के लिए किया जा सकता है।

एक क्षेत्र के अलावा कुछ और चुनकर एल्गोरिदम के कई रूपों को प्राप्त किया जाता है $B(T)$. यदि कोई अक्ष-संरेखित बाउंडिंग बॉक्स चुनता है, तो उसे AABBTreees मिलते हैं। ओरिएंटेड बाउंडिंग बॉक्स ट्री को OBBTrees कहा जाता है। अंतर्निहित वस्तु में परिवर्तन होने पर कुछ पेड़ों को अद्यतन करना आसान होता है। कुछ पेड़ सरल त्रिकोणों के बजाय उच्च क्रम के आदिम को समायोजित कर सकते हैं जैसे कि स्पलाइन (गणित)।

सटीक जोड़ीदार टक्कर का पता लगाने

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

एक बुनियादी अवलोकन यह है कि किसी भी दो उत्तल सेट वस्तुओं के लिए जो अलग-अलग हैं, अंतरिक्ष में एक विमान मिल सकता है ताकि एक वस्तु पूरी तरह से उस विमान के एक तरफ स्थित हो, और दूसरी वस्तु उस विमान के विपरीत दिशा में स्थित हो। यह उत्तल वस्तुओं के लिए बहुत तेजी से टकराव का पता लगाने वाले एल्गोरिदम के विकास की अनुमति देता है।

इस क्षेत्र में प्रारंभिक कार्य में पृथक्करण अक्ष प्रमेय विधियों को शामिल किया गया था। दो त्रिभुज अनिवार्य रूप से तभी टकराते हैं जब उन्हें तीन शीर्षों से होकर जाने वाले तल द्वारा अलग नहीं किया जा सकता है। यानी अगर त्रिकोण हैं ${v_{1},v_{2},v_{3}}$ और ${v_{4},v_{5},v_{6}}$ जहां प्रत्येक $v_{j}$ में सदिश है $\mathbb {R} ^{3}$, तो हम तीन शीर्ष ले सकते हैं, $v_{i},v_{j},v_{k}$, तीनों शीर्षों से होकर जाने वाला तल खोजें, और जाँचें कि क्या यह अलग करने वाला तल है। यदि ऐसा कोई तल एक अलग करने वाला तल है, तो त्रिभुजों को असंयुक्त माना जाता है। दूसरी ओर, यदि इनमें से कोई भी तल अलग-अलग तलों को नहीं बना रहा है, तो त्रिभुजों को प्रतिच्छेदित माना जाता है। ऐसे बीस विमान हैं।

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

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

इस सारे एल्गोरिथम कार्य का अंतिम परिणाम यह है कि विशिष्ट व्यक्तिगत कंप्यूटर और गेम कंसोल पर वास्तविक समय में हजारों गतिमान वस्तुओं के लिए टकराव का पता लगाने का कुशलता से किया जा सकता है।

एक प्राथमिक छंटाई

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

एन-बॉडी प्रूनिंग और पेयरवाइज़ प्रूनिंग दोनों में यहाँ भी प्रूनिंग वांछनीय है, लेकिन एल्गोरिदम को समय लेना चाहिए और अंतर्निहित भौतिक प्रणाली में उपयोग की जाने वाली गतियों को ध्यान में रखना चाहिए।

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

एक उदाहरण के रूप में, दो त्रिभुजों को समय के साथ गतिमान होने पर विचार करें ${v_{1}(t),v_{2}(t),v_{3}(t)}$ और ${v_{4}(t),v_{5}(t),v_{6}(t)}$. किसी भी समय, दो त्रिकोणों को पहले उल्लिखित बीस विमानों का उपयोग करके चौराहे के लिए चेक किया जा सकता है। हालाँकि, हम बेहतर कर सकते हैं, क्योंकि इन बीस विमानों को समय पर ट्रैक किया जा सकता है। यदि $P(u,v,w)$ विमान बिंदुओं से गुजर रहा है $u,v,w$ में $\mathbb {R} ^{3}$ फिर बीस विमान हैं $P(v_{i}(t),v_{j}(t),v_{k}(t))$ ट्रैक करने के लिए। प्रत्येक विमान को तीन शीर्षों के विरुद्ध ट्रैक करने की आवश्यकता होती है, यह ट्रैक करने के लिए साठ मान देता है। इन साठ कार्यों पर रूट खोजक का उपयोग दो दिए गए त्रिकोणों और दो दिए गए प्रक्षेपवक्र के लिए सटीक टकराव के समय का उत्पादन करता है। हम यहां ध्यान देते हैं कि यदि कोने के प्रक्षेपवक्र को रैखिक बहुपद माना जाता है $t$ तो अंतिम साठ कार्य वास्तव में घन बहुपद हैं, और इस असाधारण मामले में, घन की जड़ों के सूत्र का उपयोग करके सटीक टक्कर समय का पता लगाना संभव है। कुछ संख्यात्मक विश्लेषकों का सुझाव है कि क्यूबिक की जड़ों के लिए सूत्र का उपयोग करना संख्यात्मक रूप से उतना स्थिर नहीं है जितना कि बहुपदों के लिए रूट फाइंडर का उपयोग करना।

स्थानिक विभाजन

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

आकार निर्धारक बॉक्स

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

त्रिभुज केन्द्रक खंड

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

किसी त्रिभुज के केन्द्रक का स्थिति सदिश उसके शीर्षों के स्थिति सदिशों का औसत होता है। इसलिए यदि इसके शीर्षों में कार्टेशियन निर्देशांक हैं $(x_{1},y_{1},z_{1})$, $(x_{2},y_{2},z_{2})$ और $(x_{3},y_{3},z_{3})$ तो केन्द्रक है $\left({\frac {(x_{1}+x_{2}+x_{3})}{3}},{\frac {(y_{1}+y_{2}+y_{3})}{3}},{\frac {(z_{1}+z_{2}+z_{3})}{3}}\right)$.

यहाँ दो 3D बिंदुओं के बीच एक रेखा खंड की दूरी के लिए कार्य है। $\mathrm {distance} ={\sqrt {(z_{2}-z_{1})^{2}+(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}}$ यहां खंड की लंबाई/दूरी खंड का समायोज्य हिट मानदंड आकार है। जैसे-जैसे वस्तुएं पास आती हैं, लंबाई थ्रेशोल्ड मान तक घट जाती है। एक त्रिकोण क्षेत्र प्रभावी ज्यामिति परीक्षण बन जाता है। केन्द्रक पर केन्द्रित एक गोले को त्रिभुज के सभी शीर्षों को घेरने के लिए आकार दिया जा सकता है।

वीडियो गेम

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

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

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

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

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

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

हिटबॉक्स

File:GearheadsCollisionBoxSize.png

किसी वस्तु के हिटबॉक्स को नियंत्रित करने वाले गियरहेड्स (वीडियो गेम) में एक डिबग मेनू डायलॉग बॉक्स

File:GearheadsCollisionBox.png

उपरोक्त स्क्रीन द्वारा नियंत्रित एक गियरहेड्स (वीडियो गेम) खिलौने का हिटबॉक्स

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

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

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

यह भी देखें

• हिट-परीक्षण
• बाउंडिंग वॉल्यूम
• खेल भौतिकी
• गिल्बर्ट-जॉनसन-कीर्ति दूरी एल्गोरिदम
• मिन्कोस्की पोर्टल शोधन
• भौतिकी इंजन
• लुबाचेव्स्की-स्टिलिंगर एल्गोरिथम
• रैगडॉल भौतिकी

बाहरी कड़ियाँ

• University of North Carolina at Chapel Hill collision detection research web site
• Prof. Steven Cameron (Oxford University) web site on collision detection
• How to Avoid a Collision by George Beck, Wolfram Demonstrations Project.
• Bounding boxes and their usage
• Separating Axis Theorem
• Unity 3d Collison
• Godot Physics Collison