Resolved Generate Physics Shape from Sprite?

Hi there, I'm looking for an algorithm that can generate a physics shape / an outline of points from a png. Bonus points if the algorithm can handle holes. Doesn't matter how unperformant it is btw, I have asynchronous wiggle room on this one.



If you are interested, here's my issue:
I have something that creates shapes at runtime, and many of them. Currently I'm using Sprite.Create for this, which has an option generateFallbackPhysicsShape which generates an outline of points from a png. But... it's inaccurate.

View attachment 701097
(Sucks butt, especially annoying for stairs )

Now, all I would need is a tolerance value like so:
View attachment 701100

And if I set it to 1 I get this:
View attachment 701109
(Beauty and perfection )

However... this tolerance value is not available at runtime. So I need my own algorithm to do it. Sadly googling "generate png outline" only gives you photoshop tutorials or bitmap stuff, I'm really looking for a raw, shape-searching algorithm for pngs.

I'm not afraid for something unperformant either, I have the wiggle room to split the function across frames or run it asynchronously. Getting thousands of points isn't a problem as I already use an algorithm to reduce those as well.

I've already tried looking in Unity's source code, but even if I dig deep, the GenerateOutline function is hidden in a blackbox. If someone at Unity reads this, I would love if you could sneak a peek for me at your algorithm.

 

The tolerance value should be made available through code and also when editing multiple sprites at once in the editor, with "Apply all". Maybe a physics shape tolerance slider under "generate physics shape" checkbox in the UI? They should add it if possible.

 

Hi, I dont know if this is still relevant for you. But a year back I made a game for global game jam, which featured an edge detection algorithm.

It's obviously not performant as it is gamejam code, but it might give you a starting point for implementing your own solution.

As I was using it to generate more exact physic shapes of user generated images, I didn't mind sloped corners to save on a few verts. (It generates edge vertices only on up/down/left/right instead of 8 way, but I think you could add it if you really needed it.)

 

Thanks! But I figured out a solution using a contour tracing algorithm (that weird pdf name) that I reshaped to generate sloped corners based on the direction of the last traveling pixel and some other stuff so it could still account for corners. It also does holes.

Since f*ck it, here it is!

Use like this:

Code (CSharp):

1. var boundaryTracer = new ContourTracer();
2. boundaryTracer.Trace(texture2D, centerPivot, pixelsPerUnit, outliner.gapLength, outliner.product);

texture2D, centerPivot and pixelsPerUnit should all speak for themselves: they are your everyday ordinary sprite settings.

gapLength: "How much difference in pixels in a straight line is considered a gap. This can help smooth out the outline a bit."
product: "Product for optimizing the outline based on angle. 1 means no optimization. This value should be kept pretty high if you want to maintain round shapes. Note that some points (e.g. outer angles) are never optimized."

gapLength 3 and product 0.99 are pretty good every-situation settings, both able to optimize sharp corners and maintain round edges. However, since you might need some extra accuracy for weird shapes or less of it for simpler lines, I suggest you keep these settings in a ScriptableObject that you can reuse where needed. That's the Outliner.cs.

The Outliner also has a tolerance value. This I use to optimize the shape further after it has been created using the Ramer-Douglas-Peuker algorithm (tried and true method). This sentence makes me 'sound' smart, but actually its just a standard Unity method.

So after that first bit of code, also do this:

Code (CSharp):

1. // Store these lists outside the method for free memory optimization.
2. List<Vector2> path = new List<Vector2>();
3. List<Vector2> points = new List<Vector2>();
4.  
5. polygonCollider2D.pathCount = boundaryTracer.pathCount;
6. for(int i = 0; i < polygonCollider2D.pathCount; i++)
7. {
8.     boundaryTracer.GetPath(i, ref path);
9.     LineUtility.Simplify(path, outliner.tolerance, points);
10.     if(points.Count < 3)
11.     {
12.         polygonCollider2D.pathCount--;
13.         i--;
14.     }
15.     else
16.     {
17.         polygonCollider2D.SetPath(i, points);
18.     }
19. }

 

Cool, thanks for posting. This thread was pretty far up for me in terms of google search results, so it may help people with similar problems.

 

Hm. Somehow I can't figure out how to setup ContourTracer properly. I wanted to try out your solution, but for most sprites it produces just 4point rectangles and if not also doesn't produce expected results.

I experiemented a bit with gap, product and tolerance but to no avail. Any Pointers in what I might be doing wrong?

original sprite:
my solution from up top:

Code (CSharp):

1. public void Trace()
2.     {
3.         ContourTracer tracer = new ContourTracer();
4.         Texture2D targetTex = sprite.texture;
5.         tracer.Trace(targetTex, sprite.pivot, sprite.pixelsPerUnit, gapLength, product);
6.  
7.         List<Vector2> path = new List<Vector2>();
8.         List<Vector2> points = new List<Vector2>();
9.  
10.         var polygonCollider2D = gameObject.GetComponent<PolygonCollider2D>();
11.         if(!polygonCollider2D) polygonCollider2D = gameObject.AddComponent<PolygonCollider2D>();
12.  
13.         polygonCollider2D.pathCount = tracer.pathCount;
14.         for (int i = 0; i < polygonCollider2D.pathCount; i++)
15.         {
16.             tracer.GetPath(i, ref path);
17.             LineUtility.Simplify(path, tolerance, points);
18.             if (points.Count < 3)
19.             {
20.                 polygonCollider2D.pathCount--;
21.                 i--;
22.             }
23.             else
24.             {
25.                 polygonCollider2D.SetPath(i, points);
26.             }
27.         }
28.     }

 

Oh wait that’s right! For optimization purposes I have my code check for black pixels instead of transparent for tracing (I had a specific use case). So sorry .

If you ctrl+f in that script I’m sure you’ll find it pretty quickly, just check for color.a < 0.25 (or add a threshold to the method).

 

Yep, that seemed to be the issue! Good catch.

The tracer produces really good results - just struggles with pixel-art resolution images. As it seems to round pixel positions down instead of propagating from the center.


Thanks for sharing your results nonetheless.

 

You can mitigate that by decreasing the gap length. In your case maybe to 0 even. It 'should' work, but I confess I haven't tested it on 8x8 sprites.

For good measure also set the product to 0 so it absolutely doesn't skip anything.