Johan HelsingFeb 7, 2024
Erin Catto
Recently I started a side project called Solver2D https://github.com/erincatto/solver2d. The idea is to create a platform for prototyping and comparing many different 2D rigid body solvers. So far there are 8 solvers including PGS, TGS, NGS, and XPBD. I've created many tests that push these solvers to their limits. Read about it here https://box2d.org/posts/2024/02/solver2d/ and see the solvers compared here https://www.youtube.com/watch?v=sKHf_o_UCzI
GitHub - erincatto/solver2d: A project for testing rigid body solver algorithms

A project for testing rigid body solver algorithms - GitHub - erincatto/solver2d: A project for testing rigid body solver algorithms

GitHub
Feb 7, 2024 at 4:18pmWeb
Show threadJohan HelsingFeb 7, 2024

@erin_catto really interesting watch, and great reference for comparing solvers. I'm a bit surprised xpbd did so poorly. I've been dabbling a bit with it, and i was also struggling a lot with friction...

I'm also wondering how the performance with the different solvers are? If one is cheaper maybe you could afford to do additional substeps or iterations?

Show threadErin CattoFeb 7, 2024
@johanhelsing someone else also mentioned this as well, so I added a simple performance analysis to my post and a short video showing balanced iterations
Show threadOscar Civit FloresFeb 8, 2024
@erin_catto this is very useful for learning and prototyping, thanks for doing the hard work and publishing it.
I also ran into friction issues with XPBD, initially, and I think I found a reasonable workaround that achieved static friction, but not sure how accurate is it. Will try to remember the details and report back.
Show threadslembckeFeb 8, 2024

@erin_catto Hmm. I had dismissed soft constraints as being a coat of paint on penalty forces. I suppose they are in a way, but they seem to have a number of nice properties anyway.

On the topic of XPBD, isn't one of the main reasons it exists to only operate on positions, removing the possibility of getting the position and velocity out of sync? I don't disagree that XPBD has it's issues, but if you are storing velocities or delta positions directly it makes it a bit unremarkable?

Show threadErin CattoFeb 8, 2024

@slembcke soft constraints can act as a low-pass filter for sub-stepping noise/energy. Direct solvers use regularization, which is similar to constraint softness, to deal with over-constrained problems. So they seem like a generally good thing.

On XPBD, the paper I'm following keeps the velocity and position separate. When there is collision overlap, delta positions can imply huge velocities that are not meaningful.

Show threadSpicy Lobster StudioMar 21, 2024
@erin_catto looks like the Bevy team (not lead by the core devs, but they’re involved) is evaluating your solver2D work as a way to transition away from the patented XPBD: https://github.com/Jondolf/bevy_xpbd/issues/346
Rebrand Bevy XPBD and Switch Solvers · Issue #346 · Jondolf/bevy_xpbd

I am making this as an early notice of major upcoming changes and to explain their rationale. There are important issues that need to be addressed, and I want to be as transparent as possible. With...

GitHub
Show thread🌈 Andrew ☄️Jan 27, 2025

@erin_catto I was thinking recently about your video where you have a concave table, and adjust the overlaps to prevent thin seams (sorry, couldn’t find a post of yours about it to reply to, and sorry for the brain dump).

It’d be interesting to try automatically constructing a BVH/CSG style hierarchy instead, where you form a concave object from the intersection or subtraction of multiple convex ones. For example, gift wrap, and find the concave border polygons to subtract. It’d also make finding the “overlap” (as per your video) much easier and unambiguous, as you just pad the subtracted border segment shared between convex and concave polygons along its normal. It can’t go too far, so there’s no risk of intersecting other geometry with the overlap.

You can keep each CSG layer’s geometry simple for performance. The intersection for collisions should be trivial to represent as a similar CSG too. The hierarchy allows you to avoid unecessary work in that test. In a swept scenario it might also allow you to prioritise earlier collisions more cheaply.

Have you thought about similar?

In my initial experiments I tried doing it with a pill shaped bvh volume (rather than the traditional aabb), and using a Minkowski subtraction (a rounded parallelogram) to test for intersection. It was a little complex, but interesting. Although I haven’t had time to pursue it, and thought I should just talk to someone :)

Thanks for reading! Also, thanks for your dynamic bvh slides, they’re a great read, I’ll have to find the video.

Show threadErin CattoJan 27, 2025

@bnut Automatic convex decomposition would be really nice for something like this. People try this in 3D with mixed success, but maybe 2D is easier.

A convex decomposition doesn't necessarily need a separate BVH. It becomes worthwhile once the number of child shapes becomes large. In 3D it is common to have a separate BVH for a triangle mesh.

Show thread🌈 Andrew ☄️Jan 27, 2025

@erin_catto Yeah that’s a good point, and I looked into automatic convex decomposition too, but I think bvh+csg can avoid most of the complexity and optimisation tradeoffs of decomposition by building it with bvh style costs. For example, whether you insert Steiner points, which diagonals you insert to break up a concave point etc. With a hierarchy you can fairly directly identify the concave parts. I think they will also be guaranteed to have fewer edges than the original polygon, unlike decomposition (which can be 4n iirc).

It’d be interesting to see how many convex regions you end up with a bvh, vs how many with decomposition though.

To clarify in case it got lost in my all words, I’m not meaning a traditional bvh purely for acceleration, but also as a simplification of representing the concave regions.