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

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)$. यदि कोई अक्ष-संरेखित बाउंडिंग बॉक्स चुनता है, तो उसे एएबीबीट्रीज मिलते हैं। ओरिएंटेड बाउंडिंग बॉक्स ट्री को ओबीबीट्रीज़ कहा जाता है। अंतर्निहित वस्तु में परिवर्तन होने पर कुछ पेड़ों को अद्यतन करना आसान होता है। कुछ पेड़ सरल त्रिकोणों के बजाय उच्च क्रम के आदिम को समायोजित कर सकते हैं जैसे कि स्पलाइन (गणित)।

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

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

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

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

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

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

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

प्राथमिक प्रूनिंग

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

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

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

उदाहरण के रूप में, दो त्रिभुजों को समय के साथ गतिमान होने पर विचार करें ${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}}}$ यहां खंड की लंबाई/दूरी खंड का समायोज्य हिट मानदंड आकार है। जैसे-जैसे वस्तुएं पास आती हैं, लंबाई थ्रेशोल्ड मान तक घट जाती है। त्रिकोण क्षेत्र प्रभावी ज्यामिति परीक्षण बन जाता है। केन्द्रक पर केन्द्रित गोले को त्रिभुज के सभी शीर्षों को घेरने के लिए आकार दिया जा सकता है।

वीडियो गेम

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

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

त्रि-आयामी खेलों ने एन एन-बॉडी प्रूनिंग के लिए स्थानिक विभाजन विधियों का उपयोग किया है, और लंबे समय तक जोड़ीदार जांच के लिए वास्तविक 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