2 डी टकराव का पता लगाने के लिए क्वाड्री

Question

मैं 2 डी टकराव का पता लगाने के लिए क्वाड्री का उपयोग करने की कोशिश कर रहा हूं, लेकिन मैं इसे कार्यान्वित करने के तरीके पर थोड़ा स्टंप हूं। सबसे पहले, मेरे पास एक क्वाड्री होगी जिसमें चार उपट्री (प्रत्येक चतुर्भुज का प्रतिनिधित्व करने वाला) होता है, साथ ही ऑब्जेक्ट्स का एक संग्रह होता है जो एक एकल उप-भाग में फिट नहीं होता है।

1. वर्तमान नोड में किसी भी वस्तुओं के साथ टकराव के लिए वस्तु की जाँच करें:

   जब पेड़ में टक्कर के लिए एक वस्तु की जाँच, मैं कुछ इस तरह (QuadTree for 2D collision detection करने के लिए धन्यवाद) करना होगा।

2. किसी भी उप-धारा के लिए जिसका स्थान वस्तु को ओवरलैप करता है, रिकर्स करता है।

एक quadtree पेड़ के भीतर सभी टकराव ढूंढने के लिए:

1. चेक वर्तमान नोड में एक दूसरे को वस्तु के खिलाफ वर्तमान नोड में प्रत्येक वस्तु।
2. प्रत्येक उपखंड के खिलाफ वर्तमान नोड में प्रत्येक ऑब्जेक्ट की जांच करें।

एक quadtree में सम्मिलित करने के लिए: वस्तु कई subtrees में फिट बैठता है

1. है, तो वर्तमान नोड में जोड़ने, और लौट आते हैं।
2. अन्यथा, जो भी उपट्री में शामिल है उसे पुन: दर्ज करें।
   प्रत्येक सबट्री में
   1. recurse:

   एक quadtree अद्यतन करने के लिए।

3. यदि वर्तमान नोड में कोई भी तत्व वर्तमान पेड़ में पूरी तरह से फिट नहीं होता है, तो इसे पैरेंट पर ले जाएं।
4. यदि वर्तमान नोड में कोई तत्व उपट्री में फिट बैठता है, तो उसे उपट्री में डालें।

क्या यह ठीक है? क्या यह सुधार किया जा सकता है?

Answer 1

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

के संचालन के कार्यान्वयन पर एक नजर है:

1. quadtree में एक वस्तु सम्मिलित करें:
   चेक वस्तु वर्तमान नोड काटती है यदि। यदि हां, तो रिकर्स करें। यदि आप पत्ती के स्तर तक पहुंच गए हैं, तो ऑब्जेक्ट को संग्रह में डालें।
2. quadtree से एक वस्तु को नष्ट करें:
   के रूप में अगर वस्तु डालने ठीक उसी चरणों निष्पादित, लेकिन जब आप पहुँच गए पत्ती स्तर संग्रह से नहीं हटेगी।
3. टेस्ट एक वस्तु quadtree अंदर किसी भी वस्तु काटती है यदि:
   के रूप में अगर वस्तु डालने ठीक उसी चरणों निष्पादित, लेकिन आप संग्रह में सभी वस्तुओं के साथ टकराव के लिए पत्ती स्तर की जांच पहुँच गए हैं जब। सभी वस्तुओं के बीच सभी टकराव quadtree अंदर के लिए
4. टेस्ट:
   quadtree में हर वस्तु के लिए एक वस्तु टक्कर परीक्षण निष्पादित।
5. क्वाड्री अद्यतन करें:
   क्वाड्री से सभी ऑब्जेक्ट हटाएं जिनकी स्थिति संशोधित की गई है और उन्हें दोबारा डालें।

यह कई लाभ है:

• केवल पत्ते यह quadtree पर कार्रवाई को संभालने के लिए बहुत आसान है (कम विशेष मामलों) में वस्तुओं के भंडारण के द्वारा
• quadtree साथ पत्ते हो सकता है विभिन्न गहराई, इस प्रकार आप इसे क्षेत्रीय क्षेत्र के आधार पर क्वाड्री के घनत्व को अनुकूलित करने की अनुमति देते हैं। यह अनुकूलन रनटाइम पर हो सकता है, इस प्रकार ऑब्जेक्ट/नोड अनुपात इष्टतम रखता है।

केवल disatvantage:

• वस्तुओं quadtree अंदर कई संग्रहों की हो सकती है। डुप्लीकेट के बिना आपको प्रत्येक ऑब्जेक्ट को गिनने के लिए क्वाड्री के बाहर एक अतिरिक्त रैखिक संग्रह की आवश्यकता होगी।

Answer 2

मुझे यकीन है कि कैसे cpu प्रभावी यह अभी तक है, लेकिन यह ग्रहण में मेरी कोर की जोड़ी पर ठीक काम कर रहा है नहीं कर रहा हूँ, अभी भी मूल रूप से पर 2400 से अधिक एफपीएस lol चलाता है ..

, मैं एक सूची जोड़ी quadtree नोड ऑब्जेक्ट्स के संदर्भों को संग्रहीत करने के लिए टिकाऊ वस्तुओं के लिए जो मैंने ऑब्जेक्ट को (क्वाड्री में डालने के माध्यम से) से जोड़ा है। मैंने प्रत्येक क्वाड्री नोड में एक सूची भी जोड़ा, जो उस नोड की सीमाओं के भीतर समझा गया किसी भी ऑब्जेक्ट के संदर्भ संग्रहीत करता है। इसलिए प्रत्येक नोड में केवल प्रत्येक ऑब्जेक्ट की एक घटना होगी। प्रत्येक नोड अपने माता-पिता नोड के संदर्भ में भी नोड्स के लिए नेविगेशन के लिए एक संदर्भ संग्रहीत करता है अगर मैं इन टकराव सटीकता के लिए इनबिटल नोड के बाद उनमें से किसी एक को देखना चाहता हूं।

यह एक सेल में अन्य सभी वस्तुओं के लिए संदर्भ पाने के लिए बहुत आसान है:

list temp_checklist = object.cells[cell_index].objects 
//('objects' being some sort of array or list of object references as described above) 

आशा है कि किसी को मदद मिलती है;)

Answer 3

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

अन्य पूरी तरह से अलग दृष्टिकोण भी हैं जो बेहतर हो सकते हैं।उदाहरण के लिए, आप, Zomorodian और Edelsbrunner एल्गोरिथ्म को लागू करने की कोशिश कर सकते के रूप में मैं निम्नलिखित मॉड्यूल में किया था:

• https://github.com/mikolalysenko/box-intersect

यहाँ भी कुछ लेख जो मुझे लगता है कि और अधिक विस्तार में इन मुद्दों पर चर्चा लिखा हैं:

• http://0fps.net/2015/01/07/collision-detection-part-1/
• http://0fps.net/2015/01/18/collision-detection-part-2/
• http://0fps.net/2015/01/23/collision-detection-part-3-benchmarks/

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