Collisions
I consider this project to be more or less done now. The last thing I implemented was a way to reduce the amount of collision checks. If one does a naive solution, then all particles gets checked against all particles resulting in a O(n^2) solution. This quickly escalates already for only 3 objects in my expiremts such that it becomes infeasible. So what I did was to read online and most recommended using a 3D uniform grid for the particles. Such that each particle inside a grid voxel was checked only against particles within the voxel itself and adjacent voxels.
One powerpoint I found online suggested using a hashmap and only store voxel IDs that are used, otherwise one would have to allocate a huge chunk of memory of a finite amount of space. I could not find that powerpoint again but I'm glad that I remembered this idea. In my solution I ended up using std::map instead which internally has a red-black tree. I used this as it is more reliable, a hash solution can in worst case yield O(n) lookups. Furthermore, when hashing one has to create a good hash and that is not always trivial, there is very little concrete research about how to hash values properly.
Something I had to google to realize was that std::map and std::unordered_map can have very slow lookup times when you run the program in DEBUG-mode, which I do in order to detect bugs obviously. So when I ran my O(n) collision detection solution, it was extremely choppy and slow for only 3 rigid objects. However, when setting the compiler to RELEASE-mode everything went super-smooth.
My collision reducer method stores at most 4 particles per voxels. It is assumed that particles cannot intersect, and thus it is expected that voxels eventually only will have about 1-2 particles at all times.
Here are some more videos showing multiple objects with collision detection. One extra cool feature I added was transparent particles, however I would need to re-structure the code in order to account for the order of all particles. As the code is now it only sorts particles locally and not in a global rendering manner.
One powerpoint I found online suggested using a hashmap and only store voxel IDs that are used, otherwise one would have to allocate a huge chunk of memory of a finite amount of space. I could not find that powerpoint again but I'm glad that I remembered this idea. In my solution I ended up using std::map instead which internally has a red-black tree. I used this as it is more reliable, a hash solution can in worst case yield O(n) lookups. Furthermore, when hashing one has to create a good hash and that is not always trivial, there is very little concrete research about how to hash values properly.
Something I had to google to realize was that std::map and std::unordered_map can have very slow lookup times when you run the program in DEBUG-mode, which I do in order to detect bugs obviously. So when I ran my O(n) collision detection solution, it was extremely choppy and slow for only 3 rigid objects. However, when setting the compiler to RELEASE-mode everything went super-smooth.
My collision reducer method stores at most 4 particles per voxels. It is assumed that particles cannot intersect, and thus it is expected that voxels eventually only will have about 1-2 particles at all times.
Here are some more videos showing multiple objects with collision detection. One extra cool feature I added was transparent particles, however I would need to re-structure the code in order to account for the order of all particles. As the code is now it only sorts particles locally and not in a global rendering manner.
Kommentarer
Skicka en kommentar