We're back with another Wizard-Pixels-flavored update, again on duct-taping together two physics worlds!

Last time we ended up with moving (rigid body) colliders being created from physics-pixels, and physics-pixels were stopped by fixed rigid body colliders - so you could stack boxes on top of a sand pile, and sand would be stopped by fixed platforms.

This week, well, you can still mainly do those things. But! Wait! Don't leave! This week it performs at least 10x better, which makes it actually playable! And you can draw custom moving bodies, and actually walk on the sand as a player too - both of which are sort of neat.

How is this black magic possible? Let me tell you!

What we had

If you recall last time, I had implemented the physics bridge in two steps:

1. Find the space that (fixed or movable) rigid body colliders take up, and mark that as occupied in the pixel-physics simulation.
2. Find the space that's occupied by pixels in the pixel-physics simulation, run marching squares on that to get line segments, connect line segments together to get polygons, and beg the physics engine to make some colliders from them.

And as you may remember if you played last week's demo, this approach performed much like the original Ford Model T: it went forward, but it sure as heck didn't go fast. (Though we did support colors other than black - take that Henry.)

On our tiny tiny 512x256 world, the simulation was managing to compute about 4-10 frames a second, rather than the (at least) 60 frames per second target needed for smooth gameplay. And that 512x256 world needs to be at least 4-8 times bigger too (or about 16-32 times bigger if I am not multithreading). So yeah, room for improvement.

Speeding things up

When code is slow, you run a profiler on it, and in this case it was really obvious what my profiler was telling me:

Collider generation was taking 173 milliseconds to run. For reference, we have 16.6ms (1/60) to complete all the calculations for a whole frame.

Simplifying lines

When I broke down the time spent further, the step of "beg the physics engine to make colliders from closed polygons" was the slowest, so it was time to optimize.

The first thing I tried was to implement the Ramen-Douglas-Pecker line simplification algorithm. It finds vertices of the polygon which are "not contributing that much" (and "that much" is tunable) to the overall shape of the polygon, and removes them.

My theory was that this would make the rigid body physics engine collider construction step have less work to do, because there would be fewer line segments it would have to deal with.

But it didn't help! It turns out that the collider construction algorithm (VHACD) doesn't scale relative to the number of vertices in the polygon, but instead scales relative to bounds of the polygon (so larger polygons are slower).

Line simplification did make the generated colliders shapes a little less jagged, which should at least result in slightly less work simulating each rigid body, and fewer physics glitches.

Faster collider construction

So, time to swap out the collider generation approach; the old one worked by sampling pixels and seeing if they were inside the polygon or not, which explains why having the polygon composed of simpler lines didn't really help.

I knew my physics library could support colliders generated from a "trimesh" (arbitrary triangles stuck together), so I use an approach called Ear Clipping to convert my polygon into a trimesh - which I discovered was also provided by my physics library, so I don't know why that isn't promoted more.

This was about 10x faster! My sand falling benchmark was now running at around 60 frames per second on the tiny 512x256 world, which was great.

But when I bumped the world size to 1024x1024, it only ran at 30 frames per second, and we had a new culprit:

Collider generation for a much bigger world is now running in only 7ms, but we can see that 'Scrape contained points' is our biggest problem now.

Smarter marking of space occupied by rigid bodies

Scrape contained points corresponded directly to step 1 that I mentioned way back at the start of this update:

Find the space that (fixed or movable) rigid body colliders take up, and mark that as occupied in the pixel-physics simulation.

This was working by looking at every pixel in the world, and asking the rigid body physics engine if that pixel overlaps with any rigid body - so of course it got slower linearly as the amount of pixels increased.

But rigid bodies don't change shape! So really, we only need to do this once per rigid body, and we can record which pixels are occupied. (Full disclosure: I totally stole that insight from a remark by a Noita developer.)

Time for some cleverness:

1. What we want: moving body polygons that can say which pixels they occupy.
2. What we just spent X hours optimizing: generating polygons from the pixels they occupy.
3. What if: moving body polygons were also just generated from an image?

This approach allows reusing* most of the work that we just did. And by treating rigid bodies as if they internally consist of pixel-physics pixels, (in future) moving bodies will be able to be partially destroyed, set on fire, etc. And it also enables taking normal sprites (images) and turning them into moving bodies.

With that done, we completely eliminated having to scrape the pixel-physics world for contained points; instead the moving body does some calculations when it's created to generate its collider, and then each frame we just ask the rigid body which pixels it is occupying based on its current position and rotation.

Faster marching squares

The other thing that increases linearly with size of the world is the marching squares algorithm (see last week), so I did a bunch of micro-optimizations and managed to shave 70% off its run time.

With that done, we can set our world size to 1024x1024 again and see how we're doing:

All our game logic fits in 9ms now. Rendering (not shown) takes about 2ms, so we could even make the world 50% bigger and still hit 60 frames per second!

Not bad! We're starting to see the "moteworld" (my internal name for the pixel physics engine) take up significant chunks of time relative to other pieces.

Playable web build‎

Be sure to try out the Body tool to draw a moving body, and the Grab tool to fling moving bodies around:

Controls:

• Move the player with A and D (and jump with W or Space)
• The rest of the controls are in the UI tooltips now, but here's a special callout: you can use C to clear all the things you've created and start over.

Things aren't perfect yet!

• Dropping sand on a moving body still crushes the moving body into the floor, and you can't walk through any falling sand! This is super not fun so probably this will be next week's thing to fix.
• Holes in shapes are not handled well: I've worked out to detect them, but at the moment I'm just discarding the holes. This is mostly only noticeable if you manage to trap yourself; you can turn on the debug option (press F2) to "Show discarded inner polygons" to see this in action.

(* In theory, reusing the polygon generation approach should have been free. In practice, it required a significant code rework to remove all kinds of hardcoded assumptions. This is the way.)