Box2D Forums

It is currently Thu Dec 18, 2014 6:27 pm

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 110 posts ]  Go to page Previous  1, 2, 3, 4, 5 ... 11  Next
Author Message
PostPosted: Mon Nov 19, 2007 1:07 am 
Offline

Joined: Sun Sep 23, 2007 2:35 pm
Posts: 803
No problem, I'm putting together a few simple tests as we speak. Documentation shouldn't be too big a deal, either - there are only a couple of useful public functions, so I can explain them pretty briefly.

One thing that I'm currently noticing is that a set of polygons that cover the same area as a single polygon don't always collide in the same way that the single polygon would; sometimes things can get stuck on each other in weird ways (once they penetrate a lot, they can get stuck along the "seams"), but I guess that's just the price to pay for having very fast moving concave objects. Maybe CCD will make that less of an issue.

Speaking of CCD, that's great that it's working out - when I get a chance, I'm going to update my local copy from SVN and get it running, I've noticed all the changes going on and I'm curious to see what's happening!


Top
 Profile  
 
PostPosted: Mon Nov 19, 2007 12:25 pm 
Offline
Site Admin

Joined: Thu Sep 06, 2007 12:34 am
Posts: 2946
Yeah, I thought about that and CCD is the cure (I hope). Please be aware that the SVN version is unstable right now (look at the log). I'm currently abusing SVN as a method of moving between computers, so I will commit code that may not even compile. It's also my way of doing backups.

After v2.0 I'll try to stop abusing SVN this way.


Top
 Profile  
 
PostPosted: Tue Nov 20, 2007 2:52 am 
Offline

Joined: Sun Sep 23, 2007 2:35 pm
Posts: 803
Don't worry, I'll take anything from SVN with a nugget of salt - in any case I'm certainly not the one to apologize to about being quick on the commit-trigger, we're already all the way up to revision 70+ with the Java port, and we're just translating code that you've already debugged!

Back on topic, I've got the decomposition stuff working right, as far as I can tell, in the Java port now. I put it all into a Polygon class (plus a Triangle class with one method - boolean isInside(Vec2) ) and I have it living in the subpackage util.nonconvex, but the location doesn't matter much and can easily be changed. Here are the important public methods:

public Polygon(float[] x, float[] y)
public Polygon(Vec2[] v)
public Vec2[] getVertexVecs() - Polygon stores list of floats, not Vec2s, this returns a list of Vec2s
public boolean isConvex()
public boolean isSimple()
public Polygon add(Triangle t) - adds a triangle to the polygon if touching
public void addTo(PolyDef pd) - adds the polygon to a PolyDef
public static Triangle[] triangulatePolygon(float[] xv, float[] yv, int nVert) - turn polygon into a triangle
public static Polygon[] polygonizeTriangles(Triangle[] triangulated) - turn connected triangles into list of convex polys
public static Polygon[] decomposeConvex(Polygon p) - triangulates then polygonizes the result
public static void decomposeConvexAndAddTo(Polygon p, BodyDef bd, PolyDef prototype)
public static Polygon convexHull(Vec2[] cloud, int nVert)
public static Polygon convexHull(float[] cloudX, float cloudY[], int nVert)

Any of the methods that return arrays will need to be reworked in C++ - I'm up for suggestions as to the best way to do that, for now I assume the user passes in an allocated array pointer and the return value is the length of the result (only problem - the length is usually unknown in advance, so how much space should be allocated? Would a linked list be more appropriate here?). The only function that probably needs any explanation is decomposeConvexAndAddTo, which takes the non-convex polygon p, decomposes it, and adds all the resulting pieces to bd using prototype to fill in the details like density, friction, restitution, etc. This would be the function you would usually use to create a nonconvex polygon as simply as possible, but the others are available in case people want to store the results.

Any suggestions for name, method signature, or functionality changes would be most happily received while I'm still in Java mode and can refactor with a click... At some point I can put together an aggressive decomposition function that attempts to find a near-minimal decomposition (much slower, though, O(N^3) or worse) if you think it might be useful.


Top
 Profile  
 
PostPosted: Wed Nov 21, 2007 1:42 am 
Offline
Site Admin

Joined: Thu Sep 06, 2007 12:34 am
Posts: 2946
This looks great!

It is generally better if the user can provide the memory. But I understand that in this circumstance this is quite difficult.

Did you look at the convex decomposition stuff in Bullet. That might give you some API ideas.

I'm fine with this as is except: Polygon -> b2Polygon and capitalized function names.

Thanks!


Top
 Profile  
 
PostPosted: Fri Dec 07, 2007 3:11 pm 
Offline

Joined: Fri Dec 07, 2007 3:09 pm
Posts: 241
I look forward to this addition to Box2D! Just what I need for the game I've been planning. Thanks for all your great work ewjordan and Erin!


Top
 Profile  
 
PostPosted: Fri Dec 07, 2007 5:32 pm 
Offline

Joined: Sun Sep 23, 2007 2:35 pm
Posts: 803
Thanks for the encouragement, darkzerox - this will be ready soon, it's just taking longer than I expected because it turns out I suck at C++. [I'm only half joking, hence no smiley]

Seriously, though, this is essentially done, I just need to make sure I haven't left any memory leaks open. Probably a couple of days or so and I'll upload what I've got.


Top
 Profile  
 
PostPosted: Sun Dec 09, 2007 2:42 am 
Offline

Joined: Sun Dec 09, 2007 2:40 am
Posts: 3
Sounds good.

One option would be to dump it out somewhere so the community could give you feedback :) I always find the best way to break something is hand it to an end-stage user.


Top
 Profile  
 
PostPosted: Tue Dec 11, 2007 7:24 pm 
Offline

Joined: Sun Sep 23, 2007 2:35 pm
Posts: 803
Okay, well here's what I've got so far. I'm having some issues that I might need help on, I can't seem to get rid of the compiler warnings (a lot of stuff about ignoring visibility attributes) - this is the first C++ I've written in years, so before anyone tears into my code, realize that I don't know what I'm doing, and this is directly ported from Java. It works on my computer, though you may need to fix up the headers to match wherever you put the files (put b2Triangle.h/cpp and b2Polygon.h/cpp in the same directory, I used Source->Contrib, and ConvexDecomposition.h, the example, goes in Examples->TestBed->Tests, you'll need to update TestEntries.cpp, too).

Let me know if you see any problems or suggestions, I'll try to get this fixed up and ready to use, given your input.


Attachments:
convexdecomposition.zip [10.83 KiB]
Downloaded 327 times
Top
 Profile  
 
PostPosted: Thu Dec 13, 2007 12:06 pm 
Offline

Joined: Fri Dec 07, 2007 12:32 pm
Posts: 35
ewjordan wrote:
...At some point I can put together an aggressive decomposition function that attempts to find a near-minimal decomposition (much slower, though, O(N^3) or worse) if you think it might be useful.


I think it might be helpfull to have this as a stand alone application...you could choose the level of decomposition you wanted and provide the non-convex poly as a input and output the new shapes to a file. That way if someone wanted near-minimal decomp it wouldn't affect runtime of the game.


Top
 Profile  
 
PostPosted: Thu Dec 13, 2007 12:56 pm 
Offline

Joined: Sun Sep 23, 2007 2:35 pm
Posts: 803
Yeah, that's not a bad idea - at the moment I'm just trying to get it working so that it gives results that are usable, after that I'm going to look into the optimal algorithm. Turns out there is a way to provably get the minimal decomposition, I'm working through the details now to see if it's plausible to implement.

I'm also planning to improve the triangulation phase a bit - right now I'm pretty sure it runs at worse than O(N^2) time, and I know I can get that down by picking a better (but less simple) method. There does exist an O(N) method, but nobody's ever implemented it because it's so complicated, so I might go with an O(N log N) one.

Anyways, please let me know if anyone finds bugs in the code I uploaded, or if it seems to work as expected.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 110 posts ]  Go to page Previous  1, 2, 3, 4, 5 ... 11  Next

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Powered by phpBB® Forum Software © phpBB Group