Not a huge devlog, I’ve mostly been having fun with this little parachute demo I made!
I definitely spent too much time just playing with it.
I’ve also been experimenting a bit with multithreading, but it’s not in a stable or performant enough state right now to showcase.
mp4 compression will hate this
I ported the spatial partitioning to 3D! It’s definitely a lot laggier in the 3D environment, because it needs to check 3x the partitions per ball, but it’s still a lot better than having no spatial partitioning at all.
One of the problems I encountered when transitioning to 3D was lag, but not in the expected “It’s going to be laggy when you have a lot of balls” way. For some strange reason, the framerate was still below 60 even when there were no balls in the world! It turned out to be an issue with needing to calloc a big region of memory everytime it would sort the balls into their partitions, but I was able to fix it by keeping the allocation throughout the lifetime of the partition grid. I also fixed it in the 2D version, even though it wasn’t really a problem there, it also wasn’t really a problem to fix either.
(In the video you will notice the balls disappearing, the sample I whipped up for the devlog just automatically despawns balls when they leave the partitioning grid. Also some balls fly off when spawning, because sometimes the balls spawn inside one another)
I’m getting a bit burnt out from this project though, I might ship after maybe adding multithreading, creating the README, and maybe making some more demos.
I’ve been watching some videos on real rigidbody physics, and I want to try that out too!
I added spatial partitioning to the engine to speed up collisions when you have a lot of balls in a scene.
Spatial partitioning is an optimization that divides the world into a grid, so balls only check other balls that are in close cells, instead of every ball checking all others, which is O(n^2). It seems pretty simple, but I tried 4 different ways before getting a good result. Judging by the time logged, I struggled.
I first tried a naive implementation, which was making a big grid, with each cell having a list of pointers to balls that are in it. The problem is, each cell needs to have the total amount of balls that could be in it allocated.
For the best performance, each grid cell should be the same size as a ball, and for the size I use here, you need the grid dimensions to be in the 100s. with 1000 balls, and with 64 bit pointers, you could have 1000 * 8 * 300 * 300 bytes allocated total, ~720 MB. You can get away with a lot less pointers, but that still wasn’t satisfying, or flexible.
My second try was a grid, but you only store cells which have balls in them. This doesn’t solve the high number of pointers per cell, but it uses less cells overall. It should’ve been easier, but C doesn’t have any built in hashmaps. The physics code doesn’t use many libraries, and I didn’t want to rely on more, so I had the bright idea to make my own hashmap. It didn’t work and I gave up, and that was the end of the sparse grid.
The third attempt was like the first, but I decided to try allocating the memory on the fly, when balls moved around, but it didn’t work out.
The most successful attempt was a grid, every cell is allocated, and yet, uses the least memory. Instead of storing pointers, each cell only stores two things: An offset and a length. Just indices into the ball array, which sounds easy, but then you realize - the balls are in a random order. To fix this, when updating the grid, you sort the balls into the cell they’re in. You may think that going into the dark cave of sorting is a bad idea, but here, it’s just a counting sort. Then it sets each cell’s fields, and you have your partitions.
Collisions are easier than constructing the grid, you just check every ball, find its cell, check balls in close cells, then you’re done.
There was a lot of friction with memory errors. To fix them, I learned GDB, and learnt about sanitizers, which detect lots of hard to catch memory errors.
One time the program would randomly crash, and it was really hard to fix, but a sanitizer detected an easy out of bounds error when rendering. Not even a physics thing. :(
Sorry for the long post, and the time it took me to post it, The devlog guide says to keep it short and post often, but I fell down a rabbit hole with optimizing, and was putting off writing as I knew it would be unwieldy in length.
I haven’t implemented partitioning in 3d yet, but it should be easy to transfer over.
It’s hard to see the balls in the video, but I want to keep the video smaller.
It gets laggy in the video as well, but there are 7000 balls in the scene at the end, and I check collisions 15 times per frame, I am also recording too.
If you read all the way down here, you might want to try the engine. I have a build on my pages, but it’s kinda slow on web.
(at least until I change the demo). On some screens the simulation doesn’t show up until you click fullscreen.
Sorry for weird wording, max devlog size is 4k characters.
Finally added mass to the engine!
Before now all the particles had the same mass (just implicitly, so basically all of them had a mass of 1), making the small ones super dense.
Took so long because I had to migrate back to 2d in order to make sure the mass was working in 2d (everything was in 3d already so I actually added mass to 3d first), and had to update the 2d rendering for it to be able to render in 3d, but now everything (especially springs), is a lot cooler!
I added the shape generators back for 3d, now we have ✨ 3D cloth ✨!
Trying to move to 3D, finally got triangle-sphere collisions working
the edges were by far the hardest part, the sphere-face collision actually wasn’t too hard
the engine wasn’t built for walls to be able to move, but it can handle it semi fine (I’m just having rotating walls for the cool 3d showcase)
Added some functions that generate shapes for you, for example, cloth!
not that big but i migrated to the sdl callback system, so it works on emscripten now (can run in browser)
ignore my screen recorder quality
got circle-circle collision working and with a lot of balls its a bit like a fluid
cleaned up main.c as well too
includes double pendulum for clout
not actually accurate but looks fine
it uses verlet integration and supports springs as well
