By
@Duck
Funky Physics Engineee! A 2D/3D XPBD physics engine that supports distance constraints, boundary constraints, penetration constraints, and a constraint solver all in C for superb speed and interoperability.
I’ve been rewriting a lot of the physics engine for XPBD (eXtended Position Based Dynamics) since the last ship, but on a separate branch so that if I broke anything too bad it wouldn’t show up on the website, but today I finally merged the xpbd branch into main. Sadly, it is a fair bit slower than the previous verlet integration (at least for my simple demos), but it’s a far more flexible integration and constraint scheme and I think the tradeoff is worth it.
(I am a bit disappointed with the performance on the website though, I swear it was faster before I merged it! It’s a lot faster natively!)
I added a constraint that I named a “boundary constraint”, that confines a particle to being on the specific side of a line e.g. making four lines around the edges of the screen and making sure the particle is on the side which is visible on screen. This is different from a wall because walls have two sides (and also zero thickness) which can cause a particle that’s going super fast to completely pass through to the other side of the wall in a single physics step, whereas with a boundary it will always snap it back to the correct side of the line. (If this was a bad explanation, I’m sorry).
I suppose the word ‘failed’ is a bit harsh in this scenario, I was just dipping my toes into integrating a little lua shell into the demos that would let you spawn particles and stuff programatically, but I decided it wasn’t worth it for small demos that aren’t meant to be super duper flexible anyway because they’re just meant to show off cool features the engine can do.
throwing balls very quickly at the wall, which don’t clip through VVV
I’ve optimized the triangle collision code to use the spatial partitioning I implemented before for collisions. It goes through each triangle and checks what balls are in its bounding box with the collision grid, and completely skips any balls that aren’t close. This allows for about a thousand balls in a scene (at least on my computer), which is a lot better than the hundred or so you’d get with just bounding box checks and the tens or so you would get with a naive approach. Sadly, this change is only on the XPBD branch for now, meaning it won’t reflect on the website, but you’d still probably have to be spawning balls for a while for that to slow down, depending on the computer.
I’ve also added far better interaction to the cloth, using some matrix multiplication and some raycast tests, you can now drag the cloth around with your mouse! This change was on the main branch too, so this is right on the website, right now!
I did try to implement a system for having the cloth tear when it was under stress, but it would have required me to rework a lot of stuff and it didn’t quite work out. :(
For a couple days I’ve been researching and trying to implement a PBF (position based fluid) fluid simulation, but there are barely any resources on the topic that I’ve been able to find, and the ones I have found are very math oriented with evil cryptic symbols that take a while to wrap my head around.
The fluid simulation does work, but it’s much laggier, a lot finickier, and not a lot better (if at all better) than just chucking a couple thousand balls together and having them collide normally.
I spend the last couple days integrating OpenGL rendering into a couple of the projects, meaning the graphics will be a lot better and rendered on the GPU instead of being rendered on the CPU, as well as speeding up the demos because even with the added visual complexity, the GPU is just so much faster at rendering!
I made these changes of the main branch so that they would reflect on the website sooner, but git’s merge system is actually super good and it took no more than 15 minutes to merge the OpenGL rendering to the XPBD branch.
I’ve only migrated over the cloth and fluid demos, but they’re the ones that needed it the most, and it’s not too hard to add it to more demos after I’ve had most of the OpenGL boilerplate implemented.
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
