2 डी टकराव एन-बॉडी सिमुलेशन (गेंदों की बड़ी संख्या के लिए तेज़ टकराव का पता लगाने)

Question

मैं 2 डी पर उच्च संख्या (एन = 1000 - 10^5 और अधिक) निकायों (मंडल) की गति को अनुकरण करने के लिए एक प्रोग्राम लिखना चाहता हूं विमान। सभी निकायों के बराबर आकार होता है और उनके बीच एकमात्र बातचीत लोचदार टक्कर होती है।

मैं जैसे कुछ प्राप्त करना चाहता हूं लेकिन बड़े पैमाने पर, अधिक गेंदों और विमान के अधिक घने भरने के साथ (यहां एक गैस मॉडल नहीं है, लेकिन उबलते पानी के मॉडल की तरह smth)।

तो मुझे पता लगाने की एक तेज विधि चाहिए कि गेंद संख्या i में 2 * त्रिज्या + वी * डेल्टा_टी दूरी के भीतर अपने पथ पर कोई अन्य गेंद है। मैं i गेंद के प्रत्येक के लिए एन गेंदों के साथ टकराव की पूरी खोज नहीं करना चाहता हूं। (यह खोज एन^2 होगी।)

पीएस लूप-एनिमेटेड जीआईएफ के लिए खेद है। इसे रोकने के लिए बस Esc दबाएं। (क्रोम में काम नहीं करेगा)।

Answer 1

भौतिकी सिमुलेशन में यह पहला कदम व्यापक चरण टकराव का पता लगाने है। http://http.developer.nvidia.com/GPUGems3/gpugems3_ch32.html पर उल्लिखित कई दृष्टिकोण हैं, लेकिन दो मूलभूत स्थान स्थानिक विभाजन हैं, वस्तुओं को ग्रिड में विभाजित करते हैं, या सॉर्ट-एंड-स्वीप, जिसमें दो अक्षों के साथ सभी ऑब्जेक्ट्स को सॉर्ट करना होता है।

Answer 2

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

मुझे यकीन है कि अधिक परिष्कृत दृष्टिकोण हैं, लेकिन यह एक अच्छी शुरुआत हो सकती है।

Answer 3

ग्रिड चौड़ाई/लंबाई उनके त्रिज्या से अधिक या बराबर होनी चाहिए और खोज पहले पड़ोसियों (8 + केंद्र = 9 ग्रिड) पर होनी चाहिए। न्यूनतम ग्रिड आकार के साथ, यह कणों की गणना की संख्या से दस से पंद्रह गुना है।