Sign in to follow this  
gpulove

Many triangles to few polygons

Recommended Posts

Hi guys. I recently stumbled upon this problem: I have a list of triangles that is: 1. in indexed form 2. given as a list of independent triangles How do I compute(efficiently) a minimal(or near to minimal) set of convex polygons from the initial list(s) of triangles?

Share this post


Link to post
Share on other sites
oh boy. I assume it's 2D.

I think the first step would be to construct the neighbour information (topology) between all triangles. What triangles neighbour a triangle, what edge belong to which triangle(s).

Then, start from point, with an edge that has no neighbour (only belongs to one triangle). This edge is an edge on the 'border' of the map, preferably not a edge that belongs to an internal concave loop (imagine a ring, you should select a point on the outer edge of the ring, not the inner edge, basically, an edge with a 'convex' point).

Then follow the edges, taking the path of the most convex one. At some point, you will loop back to a point of your search, hopefully, it will be the very first one. That loop should then be convex. if it is not, then your map has some overlapping triangles, and that's bad.

Now it's done, you can remove that portion from your map, (sever the edge and triangle links), and start your search again.

That's also assuming there are no weirdness in your map, and it's nice and topologically correct.

You can detect some dodgy cases when you start building your topology. For example, if you find an edge belonging to three triangles, than there is something wrong with your data. Or if vertices overlap, ect...

Share this post


Link to post
Share on other sites
Quote:
Original post by gpulove
Hi guys.
I recently stumbled upon this problem:

I have a list of triangles that is:

1. in indexed form
2. given as a list of independent triangles

How do I compute(efficiently) a minimal(or near to minimal) set of convex polygons from the initial list(s) of triangles?


I assume you have a 2D problem. Otherwise, you will need to define what you mean by "minimal set of convex polygons".

First, you need to identify the connected components of the triangles. Each component consists of triangles that share an edge with some other triangle. This is fairly easy code to write, using STL, and produces a disjoint set of meshes. Second, for each mesh component, locate the boundary edges of the mesh. This gives you a simple polygon. Third, apply a convex decomposition of this polygon. Search on Keil and Snoeyink for a paper on such an algorithm (uses dynamic programming); this is a nontrival problem. If you want nearly optimal, search on Hertel and Melhorn.

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