ऑब्जेक्ट्स

Question

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

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

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

(1) Octree (2) ढीला Octree (3) रैखिक Octree (+ ढीला) (4) केडी ट्री (5) बसपा:

तो, मेरे अनुसंधान के क्षेत्र में मैं किसी एक का उपयोग कर सकते हैं वृक्ष (6) हैशिंग

अब तक (6) एकमात्र ऐसा है जिसे मैंने आजमाया है। यह वास्तव में गति के मामले में पूरी तरह से शानदार है (8192 आइटम टक्कर मेरे सिस्टम पर 1 एमएमएस के तहत चेक किया गया है) यदि दृश्य में ऑब्जेक्ट औसतन समान रूप से फैल गए हैं। यह इतना अच्छा एल्गोरिदम नहीं है यदि सभी वस्तुओं को एक छोटे से क्षेत्र में जोड़ दिया जाता है, जो मुझे लगता है कि संभव है।

क्या किसी के पास कुछ अंतर्दृष्टि है कि किस चीज का उपयोग करना है, या किसी भी चाल को मैं चीजों को गति देने के लिए नियोजित कर सकता हूं? मैं सोच रहा हूं कि जो कुछ भी होता है मैं स्थिर ज्यामिति के लिए एक अलग बीएसपी पेड़ का उपयोग कर सकता हूं। मुझे लगता है कि गतिशील "गोलाकार" मुझे सबसे ज्यादा चिंता करते हैं। नोट: कोई CUDA नहीं, यह केवल सीपीयू है: पी।

धन्यवाद

संपादित करें: ठीक है, फ्लोरिस करने के लिए धन्यवाद, मैं AABB पेड़ के बारे में अधिक जानकारी नहीं मिली। GameDev पर यहां एक पुरानी चर्चा है: http://www.gamedev.net/topic/308665-aabb-tree---wheres-the-poly-o_o/। एक अच्छा समझौता की तरह लग रहा है।

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

Answer 1

शानदार सवाल।

आप मूल रूप से एक जटिल व्यापार बंद के बीच है: एक पूरा टक्कर पता लगाने चरण

अद्यतन करने के ओवरहेड/डेटा संरचना को बनाए रखने के

1. स्पीड के रूप में वस्तुओं के आसपास

बुरा के लिए कदम खबर यह है कि इस वजह से कोई "सही" उत्तर नहीं है - यह वास्तव में आपकी स्थिति के लिए अद्वितीय विभिन्न कारकों पर निर्भर करेगा। उदाहरण के लिए बीएसपी 1 के लिए तेजी से तेज हैं। जब वे बहुत से स्थिर योजनाकार ज्यामिति के साथ पूर्व-गणना की जाती हैं, जो बताती है कि वे शुरुआती एफपीएस खेलों में इतने प्रचलित क्यों थे।

मेरा व्यक्तिगत अनुमान यह है कि प्रत्येक निचले स्तर के बाउंडिंग बॉक्स में उचित मात्रा में ऑब्जेक्ट्स (5-10?) के साथ एक ढीला एएबीबी (एक्सिस संरेखित बाउंडिंग बॉक्स) पेड़ शायद आपके मामले में सबसे अच्छा काम करेगा। कारण:

• आपके पास ऑब्जेक्ट्स के क्लस्टर के साथ काफी बड़ी/स्पैस स्पेस है। एएबीबी पेड़ इसके लिए अच्छा होता है, क्योंकि आप कई स्तरों को काट सकते हैं जिन्हें आपको अन्यथा चाहिए।
• आप सही क्षेत्र मान रहे हैं। क्षेत्र टकराव परीक्षण के क्षेत्रफल बहुत सस्ते हैं ताकि आप आसानी से प्रत्येक निचले स्तर-नोड के लिए 10-45 परीक्षण कर सकें। मूल रूप से एन^2 एन के छोटे मानों के लिए ठीक है :-)
• एक्सिस संरेखण पेड़ को अद्यतन करना आसान बनाता है और चौराहे परीक्षण सबसे अधिक विकल्पों की तुलना में बहुत सस्ता है। चूंकि आप मोटे तौर पर गोलाकार वस्तुओं को मान रहे हैं, मुझे नहीं लगता कि आपको उन्मुख बाध्यकारी बक्से से अधिक लाभ मिलेगा (जो वास्तव में आपको एक लाभ देता है यदि आपके पास अजीब कोणों पर बहुत लंबे/पतले आकार होते हैं)।
• बाध्यकारी बक्से ढीले होने और वस्तुओं की उचित संख्या रखने की अनुमति देकर, आप मौका कम करते हैं कि किसी भी व्यक्तिगत वस्तु की गति इसे एएबीबी सीमाओं के बाहर ले जाएगी। जब तक ऐसा न हो, आपको पेड़ को अपडेट करने की आवश्यकता नहीं है। यह आपको बहुत सारे पेड़-अद्यतन समय बचाएगा। जब ऐसा होता है, तो थोड़ी सी मार्जिन के साथ बाध्यता बढ़ाएं ताकि आपको तुरंत अगले फ्रेम को फिर से विस्तारित न करना पड़े - याद रखें कि अधिकतर गति कुछ फ्रेम के लिए उसी दिशा में जारी रहती है!

थोड़ा ऊन जवाब के लिए खेद है, लेकिन मुझे उम्मीद है कि यह आपको कुछ उपयोगी विचार/विचारों पर विचार करेगी!

Answer 2

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

एक ओओबीबीटी (ओरिएंटेड बाउंडिंग बॉक्स) यह बेहतर काउंटर हिस्सा होगा।