Sign in to follow this  
Lolmen

Efficient ConveXcization of point soup.

Recommended Posts

Hello All! I had somehow represent concave polygon in 2R space, and after minute of guessing I just pick conception like split con-cave polygon to group of convexes to provide collision routine tests. I have a soup of 2D points that should be preprocessed somehow, also there should be some verification for those con-caves that is self-intersecting to prevent it from collisions. But after few-time in google, I found nothing interesting, and even don't know where to start... So maybe you guys help me find out liks to papers or point me to some code-sample to implement this thing? Thanks in advance!

Share this post


Link to post
Share on other sites
I've never done it, its a complex issue truely. I have seen it done, at least the general method and the result, I can't find it but if I do I'll post it here.

The general method was

- Pick a random point, then two points closest to that one. This is a virtual triangle
- Pick a random point that is outside this triangle, now you have 2 triangles.
- Keep doing this until you can no longer pick any points that would be outside the polygon formed from your triangles. This should create a convex polygon.

Edit:

Still haven't found exactly it, but this guy seems to have read the same stuff
http://stackoverflow.com/questions/359673/random-but-regular-polygon-generator

Share this post


Link to post
Share on other sites
Yeah, maybe it's about some triangulation, I dunno yet, but here is picture,
it's mean that algorithm should build all possible pattern and only then pick
such one that is more efficient (has few triangles)



And I don't think that is the same as pick any random 3 points and continue build further... beause we can build inside our ARCH :D

Share this post


Link to post
Share on other sites
I think you are going to have to come up with some rules about the types of polygons you want (maybe the "minimum triangle count" rule will be enough) because as you point out, the other method could make triangles inside the arch and you don't want that.

I'm curious, what are you trying to do with these points?

Also, where are these points coming from and what do you intend to do with the resulting shape? Do the points have an "order" they came in (ie drawn with a mouse) or is it really just a bunch of points without order?

These answers might give away some of your secret plans, but they might also let someone be able to help you more specificially (;

Share this post


Link to post
Share on other sites
Ok, I draw collision shape in editor for platformer geometry, so I guess, save draw ordering is possible.

Added: I think maybe 'convex-cization' method will have as enter parameter array of points ordered from first to last point to build concave polygon by traveling from beginning to the ending of array, the problem now is howto triangulate
that polygon.

[Edited by - Lolmen on May 28, 2009 9:52:33 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Lolmen
Ok, I draw collision shape in editor for platformer geometry, so I guess, save draw ordering is possible.

Added: I think maybe 'convex-cization' method will have as enter parameter array of points ordered from first to last point to build concave polygon by traveling from beginning to the ending of array, the problem now is howto triangulate
that polygon.


Here's a good method for breaking a polygon into triangles, I used it to make a fill tool for a game that is now on the shelves in the stores and it worked great (;

http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

Share this post


Link to post
Share on other sites
Quote:
Original post by Lolmen
2 Alvaro
found noting except some formules to check is it skinny triangle...

Well, you mentioned something about the "most efficient pattern", so I figure you want to avoid skinny triangles too. What else would "most efficient" mean?

Quote:
And some very scientific samples of polysoup triangulation...

My first response in that thread is a link to an actual implementation of constrained Delaunay triangulation, which is how I suggest you find the "most efficient" triangulation. Farther down the thread I give another alternative, which is to start with any triangulation (ear clipping would do) and then do a bunch of Delaunay flips to get rid of skinny triangles, if possible. Nothing too scientific, IMHO.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
My first response in that thread is a link to an actual implementation of constrained Delaunay triangulation, which is how I suggest you find the "most efficient" triangulation. Farther down the thread I give another alternative, which is to start with any triangulation (ear clipping would do) and then do a bunch of Delaunay flips to get rid of skinny triangles, if possible. Nothing too scientific, IMHO.


The standard greedy algorithm for ear clipping (grab first available ear from an ordered list of ears) can produce skinny triangles. Doing the "Delaunay flips" after the fact certainly works, but Graham Rhodes' suggestion (in another thread) of using the empty circumcircle condition to be smarter about ear selection is a good one. That idea is the heart of the operation to remove a point from a Delaunay triangulation, although the sorting of ears is based on a ratio of the determinant from the circumcircle test and the determinant whose sign tells you whether a vertex is convex or reflex. If you want to see an illustration of this, and then adapt the idea to triangulation of any triangle, see my Geometric Tools web site, files Wm4IncrementalDelaunay2.{h,cpp}. The ears are stored in a priority queue (as compared to my TriangulateEC ear clipper that stores them in an ordered list).

As you noted ("if possible"), skinny triangles can occur even in a Delaunay triangulation. Recall that the union of the Delaunay triangles is a convex polygon. Imagine such a polygon that has one very long edge, the remaining edges short. Now imagine the closest input point to the long edge is nearly on that edge. This point and the long edge will form a skinny triangle, and no amount of "Delaunizing" will change that :)

Constrained Delaunay triangulations have similar issues, where skinny triangles can occur (a triangle contains a required edge).

Share this post


Link to post
Share on other sites
I could be mistaken but i dont think the OP really cares about skinny triangles.

I think he is just trying to take an outline of a polygon and break that into triangles so it can be a "filled shape".

It seems that was what he was after from the start but didnt realize he had all the data he needed for the outline (ie an editor was making these points so he could store the order that they were drawn in)

Share this post


Link to post
Share on other sites
Atrix256
Yeah, but editor just connect these points in shape outline, and as you say, I need filled shape, and this shape must be presented as list of convex polygons, to pass that data for collision routines...

Thanks for paper, that's seems exactly what I need.

Dave Eberly
Thanks for spot, I'll see your triangulation method.

Share this post


Link to post
Share on other sites
Quote:
Original post by Lolmen
Atrix256
Yeah, but editor just connect these points in shape outline, and as you say, I need filled shape, and this shape must be presented as list of convex polygons, to pass that data for collision routines...

CGAL has what you are asking for now as well: convex partitioning of polygons.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this