Ok, thanks again to everyone for testing out this stuff and pointing out bugs. Here's a new upload with a few changes:
 Fixed a few memory leaks and fixed copy constructor in b2Polygon
 Fixed clockwise/counterclockwise bugs, hopefully these are gone for good now!
 Added _extremely_ experimental b2Polygon TraceEdge(b2Polygon* p) function to try and handle nonconvex polygons, see the ConvexDecomposition.h file for an example.
There is at least one known bug in this stuff, which is that if you have "pinch points," where a polygon comes back and touches itself, the triangulator will usually give up, in which case the results will be empty. This happens quite often using the TraceEdge function, because any sort of figureeight type creation will have pinch points. I'm working on this, I'll let you know when I have a fix. I wouldn't rely on TraceEdge for anything too important yet.
Let me know about any other bugs, though, I'd like to know all the cases where this stuff fails so I can take care of them.
Convex shape decomposition
Re: Convex shape decomposition
 Attachments

 convexdecomp011608.zip.zip
 (13.79 KiB) Downloaded 546 times
Re: Convex shape decomposition
Ist there any form of external (meaning: not code comments) documentation to this?
Re: Convex shape decomposition
Hm, not yet, though that's a good point, I should do that. In the meantime, here's a real quick rundown of how to use the functions.
Start with two arrays storing vertex positions:
I'm assuming your b2World variable is called m_world, btw. Create a prototype polygon definition that will be used for the characteristics of all shapes we make  this prevents you from having to create a separate b2PolyDef for each decomposed piece.
To use convex decomposition, do the following:
To take the convex hull, do the following (the results of the convex hull are passed through the convex decomposition merely to split it up into multiple polygons if there are too many vertices):
Note that convexHull doesn't take a polygon as input (though I may add the ability in the future).
To trace the edge of a possibly nonsimple (self intersecting) path:
Those three functions (ConvexHull, DecomposeConvexAndAddTo, and TraceEdge) are the only ones you should need to use if you just want to sanitize shapes to use with Box2d. The other ones do important things and could be useful, but they're finnicky and not very user friendly.
One other thing you should know is that the ConvexDecomposition.h test should go in the TestBed>Tests directory, and you'll need to #include it and add an entry for it in TestEntries.cpp in that same directory for it to show up on the list when you run the testbed.
At some point I'll put together some real documentation, but honestly, I'm still debugging and I'm likely to change the organization/naming/use of these things soon, so I want to wait until it's settled a bit and mostly bug free (I know that 2.0 is going to change the way the shape creation is handled, so I'll definitely be reworking after that).
Start with two arrays storing vertex positions:
Code: Select all
float32[] x = {...};
float32[] y = {...};
int32 length = [length of x and y arrays]
I'm assuming your b2World variable is called m_world, btw. Create a prototype polygon definition that will be used for the characteristics of all shapes we make  this prevents you from having to create a separate b2PolyDef for each decomposed piece.
Code: Select all
b2PolyDef polyprot;
polyprot.density = 1.0f; //insert your values here and/or do whatever else you'd usually do with a b2PolyDef
polyprot.friction = 0.3f;
polyprot.restitution = 0.2f;
To use convex decomposition, do the following:
Code: Select all
b2Polygon pgon(x,y,length); //if you have an array of b2Vec2s, you can also do pgon(vecs, length)
b2BodyDef bd;
//The next line decomposes pgon, and adds it to bd body using polyprot as the b2PolyDef for each piece
b2PolyDef* deleteMe = DecomposeConvexAndAddTo(&pgon, &bd, &polyprot);
m_world>CreateBody(&bd);
delete[] deleteMe;
To take the convex hull, do the following (the results of the convex hull are passed through the convex decomposition merely to split it up into multiple polygons if there are too many vertices):
Code: Select all
b2BodyDef bd;
b2Polygon convexHull = ConvexHull(x,y,length);
b2PolyDef* deleteMe = DecomposeConvexAndAddTo(&convexHull, &bd, &polyprot);
m_world>CreateBody(&bd);
delete[] deleteMe;
Note that convexHull doesn't take a polygon as input (though I may add the ability in the future).
To trace the edge of a possibly nonsimple (self intersecting) path:
Code: Select all
b2Polygon poly(x,y,length);
b2BodyDef bd;
b2Polygon tracedPgon = TraceEdge(&poly);
b2PolyDef* deleteMe = DecomposeConvexAndAddto(&tracedPgon, &bd, &polyprot);
m_world>CreateBody(&bd);
delete[] deleteMe;
Those three functions (ConvexHull, DecomposeConvexAndAddTo, and TraceEdge) are the only ones you should need to use if you just want to sanitize shapes to use with Box2d. The other ones do important things and could be useful, but they're finnicky and not very user friendly.
One other thing you should know is that the ConvexDecomposition.h test should go in the TestBed>Tests directory, and you'll need to #include it and add an entry for it in TestEntries.cpp in that same directory for it to show up on the list when you run the testbed.
At some point I'll put together some real documentation, but honestly, I'm still debugging and I'm likely to change the organization/naming/use of these things soon, so I want to wait until it's settled a bit and mostly bug free (I know that 2.0 is going to change the way the shape creation is handled, so I'll definitely be reworking after that).
Re: Convex shape decomposition
Thanks a lot for your work ewjordan! I'm using your convex decomposition code in my Nintendo DS game Pocket Physics, which would be very restrictive wrt the kinds of shapes that can be drawn without convex decomposition. I'm looking forward to a more stable TraceEdge!
Re: Convex shape decomposition
Hey, ewjordan I don't have any other way to get this to you so I figured I'd just post it here.
This is a list of verticies, that makes up one polygon, that is causing me a bunch of grief with version 2.0 and the decomposition algorithm.
Oh and ps, I don't know how proxies worked in version 1.4.3 but in 2.0 each shape is a proxy and therefore having a minimal decomposition would be the most desirable.
This is a list of verticies, that makes up one polygon, that is causing me a bunch of grief with version 2.0 and the decomposition algorithm.
Oh and ps, I don't know how proxies worked in version 1.4.3 but in 2.0 each shape is a proxy and therefore having a minimal decomposition would be the most desirable.
 Attachments

 vertex_list.txt
 (525 Bytes) Downloaded 280 times
Re: Convex shape decomposition
@allanon  Thanks for the test file, that's turning out to be incredibly useful. I've already tracked down and fixed a couple of bugs that I wouldn't have caught without it. It turns out that long objects with many near parallel diagonals are generally going to cause a lot of trouble with this thing.
Due to the requirement of a minimum angle between edges, it's becoming clear to me that a generic valid triangulation is the real problem here  sometimes they are nasty, even if they are right. This is inconvenient because greedy ear clipping is the most straightforward triangulation, but there's no way to restrict the type of triangles it provides without introducing the possibility of the algorithm failing altogether. I've gotten things working so that the resulting geometry is usable in Box2d, but right now some pieces of geometry get deformed or missed. This is a fundamental problem with merging edges  the results don't completely cover the original area.
I'm tossing around a few options, ranging from rewriting the triangulator so it gives more regular triangulations to altering the merge algorithm so that it preserves every edge by splitting polygons instead of eliminating vertices (that's what I'm leaning towards right now since it's easier, but we'll see how it works).
@Erin  I know that polygons with near parallel edges are a big problem, so a very thin triangle with the "bad" vertex in the middle (say (1,0)>(1,0)>(0,.001) ) will mess things up. But is it "safe" to merely split this down the middle, or will the extreme thinness of the resulting pair of triangles also cause simulation problems (or worse, cause assertions at some point down the line)? If so, then I'll probably have no choice but to insist on altering the input geometry in some cases.
Due to the requirement of a minimum angle between edges, it's becoming clear to me that a generic valid triangulation is the real problem here  sometimes they are nasty, even if they are right. This is inconvenient because greedy ear clipping is the most straightforward triangulation, but there's no way to restrict the type of triangles it provides without introducing the possibility of the algorithm failing altogether. I've gotten things working so that the resulting geometry is usable in Box2d, but right now some pieces of geometry get deformed or missed. This is a fundamental problem with merging edges  the results don't completely cover the original area.
I'm tossing around a few options, ranging from rewriting the triangulator so it gives more regular triangulations to altering the merge algorithm so that it preserves every edge by splitting polygons instead of eliminating vertices (that's what I'm leaning towards right now since it's easier, but we'll see how it works).
@Erin  I know that polygons with near parallel edges are a big problem, so a very thin triangle with the "bad" vertex in the middle (say (1,0)>(1,0)>(0,.001) ) will mess things up. But is it "safe" to merely split this down the middle, or will the extreme thinness of the resulting pair of triangles also cause simulation problems (or worse, cause assertions at some point down the line)? If so, then I'll probably have no choice but to insist on altering the input geometry in some cases.
Re: Convex shape decomposition
I'm not sure I follow what you mean by 'split down the middle', but I am pretty sure that it will cause an assertion because of its thinness.

 Site Admin
 Posts: 2948
 Joined: Thu Sep 06, 2007 12:34 am
Re: Convex shape decomposition
The minimum shape radius must be bigger than b2_toiSlop or you will get an assertion when the core shape is computed.
For a polygon, the minimum radius is the distance between the centroid and the closest edge.
For the case you mentioned, you should just eliminate the middle vertex. Can't you just detect the shallow angle and eliminate the vertex?
For a polygon, the minimum radius is the distance between the centroid and the closest edge.
For the case you mentioned, you should just eliminate the middle vertex. Can't you just detect the shallow angle and eliminate the vertex?
Re: Convex shape decomposition
But wait...its a triangle, if he eleminates the vertex it won't be a 'poly' any more...I don't think I understand what you're saying.

 Site Admin
 Posts: 2948
 Joined: Thu Sep 06, 2007 12:34 am
Re: Convex shape decomposition
I'm talking about a polygon with two connected edges that are nearly parallel. The middle vertex should be eliminated.
Return to “Bugs, Requests, and Feedback”
Who is online
Users browsing this forum: No registered users and 2 guests