By
@Duck
Funky Physics Engineee! A 2D/3D verlet physics engine that supports distance constraints, springs, ball-ball collision, and ball-triangle collision, all in C for superb speed and interoperability.
A bit before shipping, I heard about another physics method called XPBD (extended position based dynamics) that’s a lot more powerful and flexible, and I decided, after I would ship, I would try to convert my engine to that. I kinda have to remake almost all of the physics stuff I already made, but I can recycle a lot of the older code, just making it fit the new framework, and being a lot more educated about physics simulation stuff than when I started this project, it wasn’t too hard to rewrite some new stuff. Right now I have ported over my ball pit thingy, not a lot to show that’s different from old devlogs, but hey, it’s the inside that counts, right?
This is a position-based physics engine made all in C for portability and versatility.
It had many challenging moments when making it, such as triangle collisions, spatial partitioning, performance optimization, and more, but I had a lot of fun building it, showing it off to my friends and family, and learning more about physics.
I added edge detection for 3D triangles and other miscellaneous stuff, like improving the website, adding VSync to the demos, but that stuff’s boring so I’m just going to show off the new demo!
It might be the coolest one so far, but it was one of the easiest to make.
I’m planning on shipping real soon though, just wanna add a few things to the website and readme!
I added triangle-walls which vertices are 3 dynamic spheres, which can collide with other particles and have all 4 particles update with their own velocities!
This makes the engine a lot more flexible, so you don’t have to make big grids of spheres if you want to be able to have walls that can move, instead of being static. And it makes rigidbodies (probably) possible!
(Press enter to spawn balls)
Demo!
2D is, of course, simpler than 3D, and the length of the function for these walls definitely show that (~40 lines). I used the same algorithm to find the closest position on a line to another position as I used for detecting collisions on the edges of the static 3D walls a while ago. It gives you a lerpable value from from the first point to the second point of the line, and you can use that to find the point you are looking for. Comparing it to the circle you’re checking against, will give the distance and the normal of the collision. You can use that information to move the circle out of the wall, and push the wall away, using the value to lerp between as the ratio to push each of the points that the wall is made of away.
This function is a bit more complicated, being about 80 lines long, but a lot of the information in the 2D version is applicable here too.
Here, instead of trying to find the closest point, we are trying to find the barycentric coordinates of the point, which is similar to the value to lerp between the two points in 2D, but for 3D (It’s basically just 3 numbers which tell you how close you are to each vertex of a triangle, and can describe any point on the triangle). This involves find the triangle’s area that you are checking against using the cross product, getting the distance of the point inward to the triangle for each edge, and calculating some inverse areas, which magically (not really) give you the barycentric coordinates. We then use these coordinates, as long as the distance to the triangle face using the dot product, to figure out whether the ball is colliding with the face, and if so, moving the ball outside of the triangle and moving the 3 vertices away as well, of course using each barycentric coordinate as a weight for how much to move each individual vertex.
I haven’t implemented detections with the edges of the triangles exactly yet though, only the faces, but I will try to implement it soon!
I improved the website to include multiple demos, and I made a couple improvements to the performance of the spatial partitioning detection, but I’ve mostly just been doing tinkering and testing with the engine some more.
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
