[FP3.0] Bugs in texture to polygon feature

Topics: Developer Forum, User Forum
May 10, 2010 at 5:41 PM

In our game we planned on using the texture to polygon feature for a lot of our objects, we found that the routine consistently left out triangles. When switching to debug build, it fails the following assert:

 

// Your polygon is non-convex (it has an indentation) or
// has collinear edges.
float s = MathUtils.Cross(edge, r);
Debug.Assert(s > 0.0f);

 

I know why this is an error, but aren't these the simplifier (collinearity) and decomposer's (convexity) sole tasks to prevent this from happening? We used this in our test code:

 

private void CreatePolygonsForBody(string asset, FarseerPhysics.Dynamics.Body body, float density)
{
    var texture = this.GameInstance.Content.Load<Microsoft.Xna.Framework.Graphics.Texture2D>(asset);
    var data = new uint[texture.Width * texture.Height];
    texture.GetData(data);
    var verticesList = FarseerPhysics.Common.PolygonTools.CreatePolygon(data, texture.Width, texture.Height, 1f, 0xff, true, true);
    var scale = new Microsoft.Xna.Framework.Vector2(0.05f, 0.05f);
    verticesList.ForEach(v => v.Scale(ref scale));

    foreach (var vertices in verticesList)
    {
        var triangles = FarseerPhysics.Common.Decomposition.EarclipDecomposer.ConvexPartition(FarseerPhysics.Common.PolygonManipulation.BooleanTools.Simplify(vertices));
        
        foreach (var triangle in triangles)
        {
            var shape = new FarseerPhysics.Collision.Shapes.PolygonShape(triangle, density);
            body.CreateFixture(shape);
        }
    }
}

 

Are we doing something wrong? Thanks in advance!

May 11, 2010 at 2:37 PM

We narrowed it down to being the simplifier in BooleanTools.Simplify. Though, both with and without it fails the aforementioned assert consistently in debug builds. Are we doing something wrong?

Coordinator
May 12, 2010 at 6:59 PM
Can you simplify the error case down to the bare bones and post it here? Might be something wrong with the order in which the vertices are returned.
May 12, 2010 at 8:23 PM
Edited May 12, 2010 at 8:59 PM

Thank you for your quick reply, I certainly can.

When using the attached image in a debug build, the assertion mentioned in the opening post fails with the following backtrace:

at PolygonShape.Set(Vertices vertices) D:\Storage\MI6MMb\branches\steve.testbed\FarseerPhysics\SourceFiles\FP3.0\Collision\Shapes\PolygonShape.cs(122)
at PolygonShape..ctor(Vertices vertices, Single density) D:\Storage\MI6MMb\branches\steve.testbed\FarseerPhysics\SourceFiles\FP3.0\Collision\Shapes\PolygonShape.cs(44)
at <>c__DisplayClassc.<CreatePolygonsForBody>b__8(Vertices triangle) D:\Storage\MI6MMb\branches\steve.testbed\FarseerPhysics\Samples\FP3.0\Testbed\Tests\ByggsTest.cs(123)
at <>c__DisplayClass12`3.<CombineSelectors>b__11(TSource x)
at WhereSelectListIterator`2.MoveNext()
at Buffer`1..ctor(IEnumerable`1 source)
at Enumerable.ToArray(IEnumerable`1 source)
at ByggsTest.CreatePolygonsForBody(String asset, Body body, Single density) D:\Storage\MI6MMb\branches\steve.testbed\FarseerPhysics\Samples\FP3.0\Testbed\Tests\ByggsTest.cs(123)
at ByggsTest.Initialize() D:\Storage\MI6MMb\branches\steve.testbed\FarseerPhysics\Samples\FP3.0\Testbed\Tests\ByggsTest.cs(28)
at Game1.StartTest(Int32 index) D:\Storage\MI6MMb\branches\steve.testbed\FarseerPhysics\Samples\FP3.0\Testbed\Game1.cs(109)
at Game1.Initialize() D:\Storage\MI6MMb\branches\steve.testbed\FarseerPhysics\Samples\FP3.0\Testbed\Game1.cs(99)
at Game.Run()
at Game1.Main(String[] args) D:\Storage\MI6MMb\branches\steve.testbed\FarseerPhysics\Samples\FP3.0\Testbed\Game1.cs(364)

When using it in a release build (or clicking ignore a whole lot of times in debug), a small set of triangles (we've been finding 2-10 consistently) are missing.

Image we're using in a test environment: http://i43.tinypic.com/15n2kn8.png
The result when not simplified: http://i42.tinypic.com/mm4ysm.png
The result when simplified: http://i44.tinypic.com/6iecnc.png

I'm not sure if this is more than one issue or if they are related: the assertion fails consistently regardless of the simplifier, but the missing triangles is the simplifier at work--obviously not counting triangles with collinear edges. The assertion is the biggest issue I suppose--when in release build it seems to work but when a dynamic body hits a specific fixture of the texture-to-polygoned body, it gets stuck and won't move anymore (game keeps running fine for all the other bodies).  I could mail you the entire project (= a stripped down FP3.0 testbed with some of our testing code) if you wish, it consistently fails and the fixture it gets stuck at is the same every time.

May 26, 2010 at 12:25 PM

Shameless bump! Does anyone have an idea what might be going on and what might be the solution? Thanks!

Coordinator
May 29, 2010 at 9:44 PM

I've looked over the Simplify routine and I think I found the cause of your problem. I don't have the time to test it, so I will let that be up to you.

Download the latest check-in from the source control and see if that works.

May 29, 2010 at 10:24 PM

Thanks for the quick reply to my e-mail!

That solved a large part of the missing triangles, there's one more triangle missing now, which I assume is the last one: http://i49.tinypic.com/2z53n95.png

The image used is this one: http://i43.tinypic.com/15n2kn8.png

I tried adding the last vertex and I tried adding the first vertex, but it seems to be a different one. Any ideas?

Coordinator
May 29, 2010 at 10:41 PM

Yeah, the solution only shifted the problem. Before it could remove corners from a list of vertices, now it can remove sides instead. I guess there needs to be checks in place to ensure nothing important gets removed. That kind of results is what you get from such a simple algorithm. There are algorithms that calculate the longest distance between collinear points instead and remove all points in between. They might be more suited to simplify complex sets of points.

Coordinator
May 30, 2010 at 12:26 PM

By the way, the algorithm you use looks like the EarClip algorithm. Try out the Bayazit algorithm, you might get better results since it decomposes your polygon directly into convex polygons.

May 30, 2010 at 1:39 PM

We tried both, Bayazit does indeed give better results when it works. We found that it erred a lot on BayazitDecomposer.cs:17:

private static Vector2 At(int i, Vertices vertices)
{
    int s = vertices.Count;
    return vertices[i < 0 ? s - (-i % s) : i % s]; // This is line 17.
}
In some cases, s will be 1, i will be -1, and it will try to access vertices[1]: i < 0 is true, 1 - (1 % 1) == 1 (ArgumentOutOfRangeException).

It doesn't happen with all images, but here's an example for testing purposes, if you will: http://i49.tinypic.com/ao2all.png

The original Bayazit algorithm uses i < 0 ? i % s + s : i % s, but that comes down to the same thing (-1 % 1 is 0, 0 + 1 is 1), which leads me to believe the problem is elsewhere. Tracing the stack frame when the ArgumentOutOfRangeException happens shows that there was a 32-polygon and then through "list.AddRange(ConvexPartition(poly1));", the method was recursively called for a 1-polygon, I'm not sure if that can be right.

To us it seems that: 1) The EarClipDecomposer leaves non-convex or collinear edges (the assert in my opening post), 2) The BayazitDecomposer throws aforementioned exceptions, 3) The simplifier in BooleanTools leaves out triangles. I'm not sure if the problem lies in the algorithms or FP3.0's implementation.

May 31, 2010 at 2:41 AM

I created an issue for this a while ago. I tried tracing the error too, but I didn't understand enough of what was happening to figure out where it originated, but it happens often even when using shapes I created manually.

Coordinator
Jun 1, 2010 at 10:53 PM

To my knowledge, the Bayazit algorithm was not designed to handle holes, even though it tries. The algorithms should not be used live in games - I recommend they should be used as a tool to create vertices from a texture, and then saved to a file, for later use.

I'm currently in the process of implementing several different simplifying techniques. I'll also write a little about them on my blog in case you want to know how they work.

Jun 1, 2010 at 11:16 PM
Edited Jun 1, 2010 at 11:17 PM

I just finished rewriting the Bayazit algorithm from scratch with a my own custom simplifier, and it works great.

I used a simplifier that culls collinear points by checking if the area of each consecutive three points is less than some value, say, 1e-8. I also merge points that are closer together than that value. I repeat this process until there is nothing left to cull.

Let me know how your simplifier algorithms work, perhaps we can work together to create a great set of simplifiers to put into Farseer. I can also provide my Bayazit implementation.

Coordinator
Jun 2, 2010 at 12:31 AM

I've already included a simplifier identical to what you describe. I tested it using your test image and it seems that the EarClip algorithm ignores one of the triangles because of the tolerance given to MergeParallelEdges(). The default tolerance is Settings.AngularSlop - I've moved this tolerance out as a parameter to the EarClip implementation.

Another thing is that right now the polygons created by the EarClip algorithm is not guaranteed to be without collinear points. I will add some code to remove collinear points from the polygonized triangles.

Coordinator
Jun 2, 2010 at 12:37 AM

Oh, and of course you can send me your code. You have my email right? you can also upload it as a patch to our patch section.

Coordinator
Jun 2, 2010 at 1:08 AM

I've uploaded the changes to the source control. Feel free to have a look at it. Again, I don't have the time to test it out fully, so you are very welcome to test the new tools.

Jun 3, 2010 at 4:41 PM

I don't have your e-mail, last time I e-mailed you I used the contact button through CodePlex. My Bayazit implementation can be found here: http://csharp.pastebin.com/1jJ58wQ5

I tested your changes on Farseer's Bayazit implementation and they gave me the same problems on my test images. Try out my implementation, I tried a range of images and it seems to work fine. The implementations differ quite a lot too, I'm not sure which source the creator of Farseer's implementation used.

Coordinator
Jun 3, 2010 at 6:16 PM
The Bayazit algorithm still crashes in some cases. No algorithm works in all cases, that is why I decided to provide multiple algorithms and even more in the future. I've not changed the Bayazit algorithm it inself, I just simplified the output by removing collinear points by default. Normally I would let the users do that, but since FPE don't like collinear points, I think it is my job to make sure that the output of the toolset does not generate results with collinear points. What have you changed in the Bayazit algorithm? I created the original implementation for Farseer Physics Engine - I did not port it myself if I remember correctly, Mark (creator of the algorithm) might have pointed me to a C# implementation or something like that. It is a long time ago.
Jun 3, 2010 at 6:24 PM

I didn't mean to imply anything bad, sorry if I did!

I took Mark's own C++ implementation and rewrote it in C#. It differs only in its static structure, its behaviour should be 1:1 with Mark's C++ implementation. See the bottom of the page at http://mnbayazit.com/406/bayazit.

Coordinator
Jun 3, 2010 at 7:29 PM
Not at all. It is all good. I just reread my email correspondence with Mark Bayazit and it seems like I did indeed port over the code to C#. Is your port exactly the same, but it does not crash with your test images? You could install Netbeans and run Mark's own C++ implementation on the same images to see if it crashes, but most importantly of all, if it produce the same results. I would be more than happy to use your port if it better. I'll contact you by codeplex, the reply email should be my personal email.