2 boyutlu çarpışma n-gövdesi simülasyonu (çok sayıda top için hızlı Çarpışma Algılama)

Question

2D üzerinde yüksek sayıdaki (N = 1000 - 10^5 ve daha fazla) cismin (daire) hareketini simüle etmek için bir program yazmak istiyorum uçak. Tüm bedenler eşit büyüklükte ve aralarındaki tek etkileşim elastik çarpışmadır.

gibi bir şey elde etmek istiyorum ama daha büyük ölçekte, daha fazla top ve daha yoğun bir düzlem dolgusuyla (burada olduğu gibi gaz modeli değil, kaynar su modeli gibi).

Bu nedenle, i numaralı topun 2 * yarıçap + V * delta_t mesafesi içindeki yolunda başka bir topun bulunmadığı hızlı bir algılama yöntemi istiyorum. i topunun her biri için N topları ile tam bir çarpışma yapmak istemiyorum. (Bu arama N^2 olacaktır.)

PS Döngüsel animasyonlu GIF için özür dilerim. Durdurmak için Esc tuşuna bas. (Chrome'da çalışmayacak).

Answer 1

Bu fizik simülasyonunda ilk adım, geniş-faz çarpışma algılamasıdır. http://http.developer.nvidia.com/GPUGems3/gpugems3_ch32.html numaralı belgede özetlenen birkaç yaklaşım var, ama iki temel nesne, nesneleri ikiye doğru sıralamaktan ibaret olan, bir ızgaraya veya nesneleri sıraya ayırmaya ya da ayırmaya dayalı mekansal bölümleme.

Answer 2

Açıkçası, her yinelemeyle çarpışmaları önlemek için (N1 -) * N denetler. Basit bir yaklaşım, alanı bir 2B grid hücresine bölmek ve daha sonra her topun mevcut yinelemede hangi hücrelerden geçtiğini belirlemek için tek bir geçiş yapmak olacaktır. Her top sadece geçtiği hücrelerden geçen toplarla çarpışmayı kontrol eder.

Daha sofistike yaklaşımlar olduğundan eminim, ancak bu iyi bir başlangıç ​​olabilir.

Answer 3

Şebeke genişliği/uzunluğu, bunların yarıçapına eşit veya ondan büyük olmalı ve arama, 1. komşularda (8 + merkez = 9 ızgara) olmalıdır. Minimum ızgara boyutuyla, parçacık sayısının on ila on beş katıdır.