Simulate each pixel with a rigid body?

[PandaDecSt]

How is the collision between pixel particles and rigid bodies achieved?

[PieKing1215]

My implementation is based off of the ideas that Petri Purho (one of the Noita devs) explained in their talk "Exploring the Tech and Design of Noita" (5:42 to 9:17). If you don't get something I explain here, there's a chance that their talk will clear it up for you.

Basically there's three different simulations: - The pixel-based sand/liquid/solid simulation ("falling sand") - The particle simulation (not covered deeply here) - The RigidBody simulation

RigidBody simulation

Let's say you have a bunch of pixels you want to be a rigidbody:

The game has to generate a mesh for the rigidbody, which takes a few steps:

First, the image is run through an algorithm called "Marching Squares"- This algorithm basically takes in an image and spits out one or more outlines depending on if there are holes in the shape.

In the end, the physics engine (in this case Box2D) wants the mesh to be a bunch of triangles, so you need to use a triangulation algorithm to turn the outline into triangles. In this case, I'm using the PolyPartition library.

Consider the result you get by directly plugging the result of Marching Squares into PolyPartition:

Notice how the result has a very unnecessarily large amount of triangles (284!). This is because the output of Marching Squares is generally pixel-perfect, so you get a lot of 90 degree angles.

Having this many tris is bad for performance, so before converting the mesh into triangles, we need to simplify the mesh. I am using something called the Douglas-Peucker algorithm, which takes a mesh and "smooths it out".

Here's the result of doing Marching Squares -> Douglas-Peucker -> PolyPartition:

Notice that there's way fewer triangles (only 85)! The final mesh doesn't perfectly match the input image, but it's not super important as long as it's very close.

These triangles can now be used to create a RigidBody in Box2D.

Interaction with pixel simulation

Obviously, having one RigidBody is useless unless it can collide and interact with the world. In order to combine the Box2D simulation with the falling sand simulation, there's a few steps:

For solid pixels, a mesh is generated in the same way as for a RigidBody (Marching Squares -> Douglas-Peucker -> PolyPartition). These "world meshes" are added to the Box2D simulation (result shown in red here): Whenever something in the world changes, the world meshes need to be regenerated. In my case the world meshes are generated and stored per-chunk (black grid in the picture above) so that it only has to regenerate the chunk that changed. Another trick is that you only need to generate & regenerate world meshes when they're within a range of a rigidbody, since the world mesh is not used for player collision (in Noita and in my game player collision is pixel-perfect and is a completely separate system).

Up to here, the RigidBody will collide with solid pixels, but will completely ignore sand/liquid.

In order for sand/liquid to land on the RigidBody, at the beginning of each tick, every pixel of each RigidBody gets put into the "falling sand" simulation as a solid pixel. The "falling sand" simulation is then ticked, and each RigidBody gets their pixels taken out of the "falling sand" simulation.

In order for a RigidBody to displace sand/liquid, at the end of each tick, each RigidBody calculates the position of every one of its pixels in the world. If the pixel at that position is sand or liquid, it takes it out of the "falling sand" simulation and moves it into the "particle" simulation, and in my case, it dampens the RigidBody's velocity so it slows down.

So that's more or less everything. The only (major) thing I left out was how to get the individual RigidBody pixels to interact with/act like the "falling sand" pixels (eg. have a RigidBody that catches fire), since I'm still only like halfway done implementing this myself. Hopefully the rest was somewhat coherent. Feel free to ask any more questions.

This repo/project should become open source soon so you'll be able to look at my (not very clean) code and maybe get more out of it.

Once it goes open source, I also want to make a bunch of GitHub Pages to document the algorithms I'm using more completely so it might be useful for people.

[PandaDecSt]

Thank you for giving such a detailed answer.Some issues have been resolved.

[EDToaster]

How did you get PolyPartition to work fine with geometry that has holes? My results are quite unfortunate :(

[EDToaster]

Oh nevermind. I was using ear clipping and that had horrible results :) For anyone else wondering, Triangulate_MONO is quite good at handling holes, even though it creates a bunch of unnecessary triangles.

[PieKing1215]

You can use Triangulate_EC with holes, you just need to call RemoveHoles first. Something like this:

std::list<TPPLPoly> src;
// fill out src with polys

TPPLPartition part;
std::list<TPPLPoly> dst1;
std::list<TPPLPoly> dst2;

part.RemoveHoles(&src, &dst1);
part.Triangulate_EC(&dst1, &dst2);

[EDToaster]

The issue is that rigid bodies can also reside within a hole, so the only option for me is to use Triangulate_MONO. The issue now is that I seem to have found a bug within the PolyPartition library ...

[EDToaster]

EDIT: I've found the issue and it seems to stem from my lack of understanding with how PolyPartition works. I had thought that polypartition would automatically detect that a polygon is CW and treat it as a hole. However, that doesn't seem to be the case. Thanks for your help, your code was very helpful :)

Original: Sorry I seem to have misunderstood your answer. Are you able to get the result you posted above (the star with the holes), by using Remove holes then ear clipping?

When I try that, this is the result that I get. The outer contour is constructed CCW and the inner hole is CW.

Thanks for taking your time to help me 👍

[PieKing1215]

I'll just add for reference in case anyone else find this, polypartition doesn't automatically detect holes (except for Triangulate_MONO). When you're making the TPPLPolys you have to call SetHole to mark them as such in order for RemoveHoles to work.

I should have included this in my example from before, but to continue it, when you're filling out src you could do something like this:

for(int i = 0; i < myNumberOfPolys; i++){
  TPPLPoly poly;

  // make the poly

  if(poly.GetOrientation() == TPPL_CW) {
      poly.SetHole(true);
  }

  src.push_back(poly);
}

Thanks for your help

np, glad I could help!