Generating collision boxes based on images with transparency?

[haatveit88]

Hi! I'm considering migrating my project to Love2D, and as part of evaluating it, I'm trying to find out if there's any built-in (doesn't look like it) or community library that supports generating collision meshes based on an image using its transparency. This could be used to auto-gen a collision mesh from just a normal image, or the way I intended to use it, using specific collision outline images (just a transparent image with a shape defined using any colored pixels).

CoronaSDK has this built-in (API reference), which was very convenient to use, and it's also using Box2D physics, so I thought it might have been a built in feature. But it doesn't seem like it.

If there's no convenient way to do this out of the box, does anyone have experience with implementing their own solution to do something like this?

I only need to do it once, when the game launches - and I'll probably cache the results as well for subsequent runs. But, I'm somewhat of a novice programmer so I'm not super clear on what a good way to approach this would be.

I think I can probably figure out how to outline an image based on transparency, using marching squares for example - but an outline created by that method would be waaaay too complex to use with Box2D as-is, right? So I need a way to simplify the "mesh" (polygon). I don't intend to use very complex outlines, on the order of a dozen vertices or so, usually.

I got this working well in Corona, but then ran into a ton of other problems since CoronaSDK is so focused on mobile devices, that I ran out of patience and wanted to try out Love2D instead. I'm super impressed with the amount of features I've seen, reading through the documentation - the only thing left of the list of things I need to support before I can confidently switch to Love2D for this project is this whole image-transparency-collision-thing.

It has to be done at run-time because the collision meshes are user-supplied via a file and images, as part of a custom user level system. Part of the specification for the custom user level format is that the user supplies their own collision mask image for the object in question, or if it's omitted, the game should try to auto-generate a collision mesh based on the graphical sprite used. Really, those two scenarios are basically the same, just that the collision mask is the preferred method (since it allows an object to specify a simplified collision mesh for a complex sprite graphic with lots of semi-transparent pixels etc).


I'm not really looking for suggestions saying "not" do this, it's a requirement for what I'm trying to do, and seeing as it's a feature in a slew of other frameworks and engines, I can't be the only one! Any help or pointers to good source material would be much appreciated!

[ivan]

Welcome to the Love2D forums.

Once you ship your game, the images and textures are not expected to change, right?
Generating hitmasks should NOT be handled in real-time. This is the sort of thing that should be pre-generated ONCE by a level editor or another external tool. Can players edit/generate transparent images in-game? If not then your game should NOT be concerned with things like this.

First of all, you input needs to be very clearly defined. 24-bit PNGs can have an alpha channel - your input needs to be 8-bit indexed color PNGs. You would run marching squares on the image first then simplify the resulting polygon. You have two options here - you could use something like a convex hull algorithm, OR you have to triangulate the resulting polygon. The latter is much more difficult as Box2D has several geometry constraints. And what about transparent holes in your image? As you can see, this is not a trivial problem.

The most sensible solution is to use rotated rectangles and circles for your collisions masks. It doesn't matter if your collision masks overlap, Box2D can handle multiple fixtures per body. Having super-complicated collision masks is a waste of time anyways, especially for fast moving objects.

Another thing you could try is to use "chain shapes" which would work quite well for outlines and static environments. Good luck!

[haatveit88]

Cheers for the response,

After reading about triangulation and the limits of the Box2D engine, it seems like Constrained Delaunay triangulation is what I'm looking for. Basically I need to create a set of points based on the alpha channel of the input image, triangulate the result, and then perhaps simplify it to some extent. Finally take all the resulting triangles and add them as separate shape fixtures to the same Box2D body, creating a compound body that closely resembles the input shape, no matter if it has holes, is convex or concave, it doesn't matter at all, it should work since none of the individual fixtures violate the Box2D restrictions.

I found some impressive demonstrations of this technique here, proving it works: https://www.iforce2d.net/rube/loaders/javascript/
(The demos are interactive, try clicking on stuff!)

That particular page is a demo for a commercial tool that generates the fixtures, but ultimately it runs inside a normal Box2D world. Judging by the live demo, the performance is orders of magnitude better than I'll ever need in my game, so it seems a valid way to do it. I just need to implement the technique it myself in Lua, since it needs to be applied to user created content at runtime.


Anyway, before finding the stuff above, I was halfway through explaining a little bit about why I'm trying to do this, so I might as well include it below in case anyone else ever stumbles upon this same problem.


--------------------------------
--------------------------------

If not then your game should NOT be concerned with things like this.

I don't really understand this. The game loads user created levels from disk - and I don't want a separate level editor or tool. I want the custom levels to be able to supply an image to be used as the collision mesh. It's not just a wish, it's a part of the game design. With those requirements, of course it's the game's concern. Like I said at the bottom of my post, I'm not interested in being told not to do this, I predicted as much I'm interested in finding a way to do it.

The custom level support is very simplistic in nature, so there is no tool, and no level editor - it's just a config file (containing json object definitions), and a folder structure of images (sprites) to be used by this config file. These custom maps are loaded when the game launches, since users can add or remove custom maps from their install whenever they want. So the game objects are constructed at runtime, including their collision geometry. It's not being done real-time, it's being done once.

Of course, there are rules for what can and cannot be done as far as the custom levels themselves are concerned, and if the level maker voids these rules then the result is undefined, and that's fine - it's up to them to test things before sharing them, that's not my responsibility. All I'm offering is a reasonable collision mesh in return for a reasonable outline image, or, in the case the custom level doesn't explicitly offer an outline for a sprite, the fall-back is to create one based on the actual graphical sprite, with the creator accepting the risk that the result might not be great.

Anyway, this was all actually quite simple to do in Corona, it generated simplified outlines that could be used for collision, and they could be convex, concave, anything worked. So clearly the problem can be solved. It is also very fast, I did a quick benchmark, and using a set of fairly random images similar to the one shown below as the "hitmask" file, I could generate simplified collision meshes at a rate of ~500 meshes per second, so clearly performance is a non-issue. Even if it was much slower, it's not a problem, since it only happens on application launch, never during gameplay.


Example of a random hitmask image, it's very "noisy" and complex / bad source material:


Resulting output from Corona graphics.newOutline() is perfectly useable:



If there are holes in the hitmask source, it simply covers them up, creating solid objects. Regardless of the complexity or properties of the final mesh, it works great with Box2D in their implementation - it seems to have no restrictions to convex vs concave, the only restriction I know of is that the mesh can't be self-intersecting, and their mesh generation seems to guarantee this, given reasonable inputs - I have seen it fail on inputs that are basically swiss cheese though, but then that's really not my problem, the users creating the levels have a set of rules to follow, and trying to create simple and solid collision outlines is one of them. If it fails, I'll just refuse to load that level, and show a message saying it failed to load an invalid outline, no problem.

So I guess I'm trying to figure out how they're doing it, as clearly it's possible - the system works, it's extremely fast (basically instant, with a reasonable number of custom levels), the performance is perfectly unaffected in-game versus using rect colliders or whatever, so there seems to be no downside to what they're doing. I'm just trying to find a way to achieve the same behavior in Love2D. Which is hard since the CoronaSDK source is closed, and I have no way of guessing what they're doning to generate the meshes.

Marching squares and simplifying the polygon is what I've been trying to find source material on, but they all seem to only end up with convex hulls, which is not what I want. Essentially I want to generate an outline, simplify it, and make sure it's flood-filled at the end.

[ivan]

it seems like Constrained Delaunay triangulation is what I'm looking for... none of the individual fixtures violate the Box2D restrictions.

I'm afraid it's not that simple. Like I said, Box2D has polygon limitations - for example:
- the vertex angle cannot be below a certain threshold
- the side length cannot be below a certain threshold
- polygons have "skins" so they will not sit neatly next to each other
In short, you can't just throw a bunch of triangles at Box2D and hope for the best.
You are certainly welcome to try (that's half the fun).

That particular page is a demo for a commercial tool that generates the fixtures,

Yes, iForce (aka irresistibleForce or Chris) is very clever and knowledgeable. He has personally helped me out a few times.
Unfortunately his Rube editor is not very popular among devs so I wouldn't judge him by that alone.
In my experience, Box2D requires a lot of manual tweaking and fiddling to get the behavior you want.

The game loads user created levels from disk - and I don't want a separate level editor or tool.

I think you are going to be in trouble if you expect an algorithm to produce exactly the behavior and physics that you want based on an image. It could work for very simple shapes but I wouldn't expect anything too sophisticated.

Good luck!

[haatveit88]

I think you are going to be in trouble if you expect an algorithm to produce exactly the behavior and physics that you want based on an image. It could work for very simple shapes but I wouldn't expect anything too sophisticated.

I guess the big frustration trying to research this is that it works great in one framework that uses the same physics engine. Like I said in the previous post, Corona2D does this, and it just works. I already have the system working, I've tested it, I've played with it, used it in my game... But I ran into other problems with their framework completely unrelated to this physics stuff, so I wanted to switch (it's too geared towards mobile games for my taste). And I thought that there'd be a known method of achieving the result seeing as they offer it as a standard solution, it's just a function call that takes an image (any image!) and make very usable hitboxes from them.

Right now it's the only item on the list that I need to tick before I can swap to Love2D. And the feature is a core feature of the game, so if not, my options are to keep working with a problematic framework, or shelve a core feature of the game...

[pgimeno]

This is a description of an algorithm to do what you want: https://potrace.sourceforge.net/potrace.pdf

I haven't looked into it in any detail, but it seems complex at first sight. There's also the problem of concave shapes, that needs to be dealt with separately.

Potrace comes as a library, but if you want to use it, you need to purchase a license or distribute your game as GPL2+. https://potrace.sourceforge.net/#dual

It's likely that Corona has done just that.

[pauls313]

Is it really necessary to generate a collision box? In my game I just do this:

Code: Select all

 r, g, b, a = image:getPixel(xx, yy)
    if a > 0 then
      return true, xx, yy
    else
      return false, xx, yy
    end

[haatveit88]

Is it really necessary to generate a collision box? In my game I just do this:

Code: Select all

 r, g, b, a = image:getPixel(xx, yy)
    if a > 0 then
      return true, xx, yy
    else
      return false, xx, yy
    end

I guess I could set up points along the player shape perimeter, and test those points to see if they are overlapping with any of the non-transparent points of the obstacle sprites, but I would have to convert the coordinates between the global "world space" coordinates to the local obstacle sprite pixel coordinates to do the test. I feel like that would be prone to objects intersecting unless I have a fairly dense set of detection points... Also, have to apply rotation transformations to the test points since both the player and the obstacles can rotate.

Then again, if I just use rectangular collision boxes as sensors only, and when a "collision" begins, I push it onto a stack. And every frame, if (and only if) there are any items on the stack, I do pixel by pixel searches between objects in the stack and the player object sensor points. When a collision ends I pop the object off the stack...

Interesting! Also sounds completely horrible to maintain, but, if it's performant enough, I may just be desperate enough to try it. Will have to do some tests later today.


Edit: On a closer look, getPixel is only available for ImageData, not actual image drawables, so I have to create a map of non-transparent pixels at level load for the sprites I want to detect on I guess...

[pgimeno]

Edit: On a closer look, getPixel is only available for ImageData, not actual image drawables, so I have to create a map of non-transparent pixels at level load for the sprites I want to detect on I guess...

I'm not sure how accurate this is, but my take on it is that ImageData is a CPU-side image, while Image is on the GPU-side. Transferring from the GPU to the CPU is expensive, that's why you can't easily sample from an Image object.

You can always load the image to an ImageData object and convert that ImageData to an Image, and keep both around. You can modify the ImageData if you wish, that won't affect the Image (unless you use (Image):replacePixels to force it, that is).