Post a Comment On: C0DE517E

Locoroco is a GREAT game. In an attemp to do something similar to it, I made with a friend of mine a 2d softbody simulation. Nothing too sophisticated, particles, verlet integration, springs and dampers, very simple collision detection and an internal pressure force used instead of the more common internal "structural" springs (but no non-folding contraints so it can go bad, especialy as the volume computation used for the pressure force assumes a no self-intersections). Surely way more than what it's going on the original locoroco game. And way less stable as well...

Next step was placing on the softbody surface some markers for eyes, mouth etc. Again, probably locoroco is doing something simple, but as this is mostly a toy experiment, I wanted to find an interesting solution. What I wanted was to express the position of the anchor as a function of every point on the softbody (particles). This turned out to be a problem.

Basically what I wanted is, given N 2d points (particles), express another given one (anchor point) as a linear combination of the those ones. To do so you have to solve a very underdetermined system (only two equations and N unknowns, the weights of the linear combination). Now probably the mistake I made was thinking in terms of numerical analysis that is not the field I'm most expert of, but after a few internet searches, it seemed to me that most solvers of such systems were interested in finding the most sparse solutions, so I would have a lot of zeroes in the weight vector, basically unlinking the anchor from many particles, that's not what I wanted to do. Also I was uncomfortable with the idea of writing a QR factorization algorithm. It may seem odd, but if you do some "random" maths, then you're more free of doing in incorrectly, but if you have to implement an algorithm that is well known in the NA field, then to me you should really be an expert or rely on well tested libraries instead... but I didn't want to link my pet project with Lapack or similar libraries, it seemed to be really overkill to me...

After much thinking, I ended up with a simple solution. For each particle in the softbody shell (point), I selected the particle that was most orthogonal to it respect to the centroid, expressed the anchor point in the base formed by those three points (centroid and the two particles), and accumulate those weights in the array representing the solution (the weights for each particle). Then I divided the weights by the number of particles. I constructed N very sparse solutions, and then did a linear combination of them to obtain a single, complete one.

It worked. But I don't know how ignorant this solution is...

P.S. Have you ever come up with a solution to a problem, by looking at an obviously wrong solution someone came up with? I was thinking about that, it didn't happen this time, but many times I can find interesting solutions while trying to explain why someone else proposed solution is SO basically wrong. Naive attempts at solving an hard problem, can miss some key facts, but they usually bring a different view, not completelly unrelated to your problem, just wrong, but with an underlying idea. Sometimes you're able to pick that naive idea and translate it in a real solution, and it's very surprising to me when it happens.


Update: the 'right' solution is actually obvious when you look at the problem from the right perspective. If instead of considering it as a linear system or geometrically, you look at it as a constrained minimization, it's quite simple. The function to minimize is the weight variance, and the constraints are linear equations, one for each geometrical dimension. Cast in this way it's a quadratic programming problem, and I think it has actually a simple analytic solution.