2D colliding n-body simulation (fast Collision Detection for large number of balls)
I want to write a program for simulating a motion of high number (N = 1000 - 10^5 and more) of bodies (circles) on 2D plane. All bodies have equal size and the only interaction between them is elastic collision.
I want to get something like 
but in larger scale, with more balls and more dense filling of the plane (not a gas model as here, but smth like boiling water model).
So I want a fast method of detection that ball number i does have any other ball on its path within 2*radius+V*delta_t distance. I don't want to do a full search of collision with N balls for each of i ball. (This search will be N^2.)
PS Sorry for loop-animated GIF. Just press Esc to stop it. (Will not work in Chrome).
This first step in physics simulation is the broad-phase collision detection. There are several approaches outlined here Broad-Phase Collision Detection with CUDA but the two basics ones are:
- spatial partitioning: dividing the objects into a grid
- sort-and-sweep: sorting all the objects along two axes
- Simple frame by frame video decoder library
- GCC no longer implements <varargs.h>
- Contents of IO buffer unknown == unsafe?
- Avoiding strcpy overflow destination warning
- Sort program not working, not sure why
- Fast & accurate atan/arctan approximation algorithm
- What's the difference between strtok_r and strtok_s in C?
- How memory address for pointer to arrays is same as an element in 2D array?
- Which is the best way to suppress "unused variable" warning
- How to use ellipsis in c's case statement?
- How can I exclude non-numeric keys? CS50 Caesar Pset2
- Fast ceiling of an integer division in C / C++
- Is there an invalid pthread_t id?
- How to Implement Universal Setter/Getter Functions for Interrupt-Driven Variables in Embedded C?
- How does SIMD (avx) processing work? for example, if I want 10 32 bit floats how do i fit in a 256 bit avx vector?
- FDCAN problems on STM32G4
- How does the call macro enable mutual recursion between functions f and g in this Hanoi Tower implementation?
- Running test on Rocket core CPU - global variable initialized to 0 is unsuccessful, output wrong value instead
- Interacting with C arrays without knowing the size
- Combination of two strings
- carriage return by fgets
- How to use special characters in C?
- Why does 1.0/100.0 == 0.1/10.0 give True?
- Is it correct to compare pointers in C?
- Force free() to return malloc memory back to OS
- How can I print to standard error in C with 'printf'?
- What is the standard behavior of fread in C on Windows?
- How is strtok removing lines it shouldn't have access to?
- Using array as smart point in C
- Assigning string to malloced 2d char array not working as intended