Mô phỏng n-mô phỏng va chạm 2D (phát hiện va chạm nhanh cho số lượng lớn quả bóng)

Question

Tôi muốn viết chương trình mô phỏng chuyển động có số lượng lớn (N = 1000 - 10^5 và hơn) của cơ quan (hình tròn) trên 2D máy bay. Tất cả các cơ quan có kích thước bằng nhau và tương tác duy nhất giữa chúng là va chạm đàn hồi.

Tôi muốn có thứ gì đó như nhưng ở quy mô lớn hơn, với nhiều quả bóng hơn và dày đặc hơn của mặt phẳng (không phải là mô hình khí như ở đây, nhưng hơi giống như mô hình nước sôi).

Vì vậy, tôi muốn có một phương pháp phát hiện nhanh rằng số bóng i không có bất kỳ quả bóng nào khác trên đường đi của nó trong phạm vi 2 * bán kính + V * delta_t. Tôi không muốn thực hiện tìm kiếm đầy đủ va chạm với N quả bóng cho mỗi quả bóng i. (Tìm kiếm này sẽ là N^2.)

PS Rất tiếc cho GIF động vòng lặp. Chỉ cần nhấn Esc để dừng nó. (Sẽ không hoạt động trong Chrome).

Answer 1

Bước đầu tiên trong mô phỏng vật lý là phát hiện va chạm pha rộng. Có một số cách tiếp cận được nêu ở đây http://http.developer.nvidia.com/GPUGems3/gpugems3_ch32.html nhưng hai phương thức cơ bản là phân vùng không gian, chia các đối tượng thành lưới, hoặc sắp xếp và quét, bao gồm phân loại tất cả các đối tượng dọc theo hai trục.

Answer 2

Rõ ràng là bạn muốn tránh (N1 -) * N kiểm tra các xung đột với mỗi lần lặp. Một cách tiếp cận đơn giản là chia khu vực thành một ô lưới 2D và sau đó tạo một đường chuyền để tìm ra các ô mà mỗi quả bóng đi qua trong lần lặp hiện tại. Mỗi quả bóng sau đó chỉ kiểm tra va chạm với quả bóng đi qua các tế bào nó đi qua.

Tôi chắc chắn có nhiều cách tiếp cận tinh vi hơn, nhưng đây có thể là một khởi đầu tốt.

Answer 3

Chiều rộng/chiều dài của lưới phải lớn hơn hoặc bằng bán kính của chúng và tìm kiếm phải ở trên hàng xóm thứ nhất (8 + center = 9 lưới). Với kích thước lưới tối thiểu, đó là mười đến mười lăm lần số lượng các phép tính hạt.