Convex shape decomposition

General Box2D issues or C++ specific issues
ewjordan
Posts: 803
Joined: Sun Sep 23, 2007 2:35 pm

Re: Convex shape decomposition

Postby ewjordan » Wed Jan 16, 2008 2:07 pm

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 non-convex 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 figure-eight 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.
Attachments
convexdecomp011608.zip.zip
(13.79 KiB) Downloaded 544 times

galaktor
Posts: 11
Joined: Wed Jan 16, 2008 12:30 pm

Re: Convex shape decomposition

Postby galaktor » Wed Jan 16, 2008 3:20 pm

Ist there any form of external (meaning: not code comments) documentation to this?

ewjordan
Posts: 803
Joined: Sun Sep 23, 2007 2:35 pm

Re: Convex shape decomposition

Postby ewjordan » Wed Jan 16, 2008 4:38 pm

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:

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 non-simple (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).

0xtob
Posts: 13
Joined: Thu Dec 06, 2007 7:36 am

Re: Convex shape decomposition

Postby 0xtob » Wed Jan 16, 2008 5:50 pm

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!

allanon
Posts: 35
Joined: Fri Dec 07, 2007 12:32 pm

Re: Convex shape decomposition

Postby allanon » Fri Jan 18, 2008 12:46 pm

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.
Attachments
vertex_list.txt
(525 Bytes) Downloaded 278 times

ewjordan
Posts: 803
Joined: Sun Sep 23, 2007 2:35 pm

Re: Convex shape decomposition

Postby ewjordan » Tue Jan 22, 2008 2:51 am

@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.

allanon
Posts: 35
Joined: Fri Dec 07, 2007 12:32 pm

Re: Convex shape decomposition

Postby allanon » Tue Jan 22, 2008 10:43 am

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.

Erin Catto
Site Admin
Posts: 2948
Joined: Thu Sep 06, 2007 12:34 am

Re: Convex shape decomposition

Postby Erin Catto » Tue Jan 22, 2008 10:50 am

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?

allanon
Posts: 35
Joined: Fri Dec 07, 2007 12:32 pm

Re: Convex shape decomposition

Postby allanon » Tue Jan 22, 2008 10:54 am

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.

Erin Catto
Site Admin
Posts: 2948
Joined: Thu Sep 06, 2007 12:34 am

Re: Convex shape decomposition

Postby Erin Catto » Tue Jan 22, 2008 12:53 pm

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 1 guest