C++ 2D tessellation library?

Question

I've got some convex polygons stored as an STL vector of points (more or less). I want to tessellate them really quickly, preferably into fairly evenly sized pieces, and with no "slivers".

I'm going to use it to explode some objects into little pieces. Does anyone know of a nice library to tessellate polygons (partition them into a mesh of smaller convex polygons or triangles)?

I've looked at a few I've found online already, but I can't even get them to compile. These academic type don't give much regard for ease of use.

Marry

Answer 1

CGAL has packages to solve this problem. The best would be probably to use the 2D Polygon Partitioning package. For example you could generate y-monotone partition of a polygon (works for non-convex polygons, as well) and you would get something like this:

The runnning time is O(n log n).

In terms of ease of use this is a small example code generating a random polygon and partitioning it (based on this manual example):

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Partition_traits_2<K>                         Traits;
typedef Traits::Point_2                                     Point_2;
typedef Traits::Polygon_2                                   Polygon_2;
typedef std::list<Polygon_2>                                Polygon_list;
typedef CGAL::Creator_uniform_2<int, Point_2>               Creator;
typedef CGAL::Random_points_in_square_2<Point_2, Creator>   Point_generator;   


int main( )
{
   Polygon_2    polygon;
   Polygon_list partition_polys;

   CGAL::random_polygon_2(50, std::back_inserter(polygon),
                      Point_generator(100));

   CGAL::y_monotone_partition_2(polygon.vertices_begin(),
                                polygon.vertices_end(),
                                std::back_inserter(partition_polys));

   // at this point partition_polys contains the partition of the input polygons
   return 0;
}

To install cgal, if you are on windows you can use the installer to get the precompiled library, and there are installations guides for every platform on this page. It might not be the simplest to install but you get the most used and robust computational geometry library there is out there, and the cgal mailing list is very helpful to answer questions...

Heraclitean

I was actually trying cgal before.... it's ugly as hell. Just look at those typedefs! Perhaps I'll give it another go though. Partitioning I've already got though. Tessellation is a little bit different, unless I've got my terminology mixed up. I want a fine mesh, not just convex randomly sized polies; of which those 2 actually look pretty terrible. Too many slivers. – Marry

You have written "you are not worried about the quality of the mesh", so I thought this partitioning would be what you are looking for. Do you want to triangulate a polygon such that you have control over the quality and size of the triangles? If this is your question you could look into this cgal package: cgal.org/Manual/3.3/doc_html/cgal_manual/Mesh_2/… – Heraclitean

Err...sorry, by quality I meant that I'm not too picky about them all angles being at least a certain degree or having completely consistent sizes across all the subdivisions... it does however, need to produce some sort of mesh. I should have made that more clear. That last link looks a lot more like what I want. Thanks! – Marry

If you would like to avoid slivers (as you have written in your first comment) that means implicitly that you would prefer a bound on minimum angle. Would you like something like this? www-sop.inria.fr/members/Jane.Tournois/images/seattle_big.png This picture and the CGAL 2d meshing package is based on a method called Delaunay refinement. And there is another opensource Delaunay mesh generator here: cs.cmu.edu/~quake/triangle.html , as well. – Heraclitean

Answer 2

poly2tri looks like a really nice lightweight C++ library for 2D Delaunay triangulation.

Sabina

Just wanna add that poly2tri doesn't support self intersecting polygons – Poling

Answer 3

As balint.miklos mentioned in a comment above, the Shewchuk's triangle package is quite good. I have used it myself many times; it integrates nicely into projects and there is the triangle++ C++ interface. If you want to avoid slivers, then allow triangle to add (interior) Steiner points, so that you generate a quality mesh (usually a constrained conforming delaunay triangulation).

Teshatesla

Answer 4

If you don't want to build the whole of GCAL into your app - this is probably simpler to implement.

http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

Cosignatory

FWIW, this Flipcode tessellate code is excellent. Fast and correct for arbitrarily complex polygons. – Spadix

Answer 5

I've just begun looking into this same problem and I'm considering voronoi tessellation. The original polygon will get a scattering of semi random points that will be the centers of the voronoi cells, the more evenly distributed they are the more regularly sized the cells will be, but they shouldn't be in a perfect grid otherwise the interior polygons will all look the same. So the first thing is to be able to generate those cell center points- generating them over the bounding box of the source polygon and a interior/exterior test shouldn't be too hard.

The voronoi edges are the dotted lines in this picture, and are sort of the complement of the delaunay triangulation. All the sharp triangle points become blunted:

Boost has some voronoi functionality: http://www.boost.org/doc/libs/1_55_0/libs/polygon/doc/voronoi_basic_tutorial.htm

The next step is creating the voronoi polygons. Voro++ http://math.lbl.gov/voro++/ is 3D oriented but it is suggested elsewhere that approximately 2d structure will work, but be much slower than software oriented towards 2D voronoi. The other package that looks to be a lot better than a random academic homepage orphan project is https://github.com/aewallin/openvoronoi.

It looks like OpenCV used to support do something along these lines, but it has been deprecated (but the c-api still works?). cv::distTransform is still maintained but operates on pixels and generates pixel output, not vertices and edge polygon data structures, but may be sufficient for my needs if not yours.

I'll update this once I've learned more.

Louisville

Answer 6

A bit more detail on your desired input and output might be helpful.

For example, if you're just trying to get the polygons into triangles, a triangle fan would probably work. If you're trying to cut a polygon into little pieces, you could implement some kind of marching squares.

---

Okay, I made a bad assumption - I assumed that marching squares would be more similar to marching cubes. Turns out it's quite different, and not what I meant at all.. :|

In any case, to directly answer your question, I don't know of any simple library that does what you're looking for. I agree about the usability of CGAL.

The algorithm I was thinking of was basically splitting polygons with lines, where the lines are a grid, so you mostly get quads. If you had a polygon-line intersection, the implementation would be simple. Another way to pose this problem is treating the 2d polygon like a function, and overlaying a grid of points. Then you just do something similar to marching cubes.. if all 4 points are in the polygon, make a quad, if 3 are in make a triangle, 2 are in make a rectangle, etc. Probably overkill. If you wanted slightly irregular-looking polygons you could randomize the locations of the grid points.

On the other hand, you could do a catmull-clark style subdivision, but omit the smoothing. The algorithm is basically you add a point at the centroid and at the midpoint of each edge. Then for each corner of the original polygon you make a new smaller polygon that connects the edge midpoint previous to the corner, the corner, the next edge midpoint, and the centroid. This tiles the space, and will have angles similar to your input polygon.

So, lots of options, and I like brainstorming solutions, but I still have no idea what you're planning on using this for. Is this to create destructible meshes? Are you doing some kind of mesh processing that requires smaller elements? Trying to avoid Gouraud shading artifacts? Is this something that runs as a pre-process or realtime? How important is exactness? More information would result in better suggestions.

Disarray

Well, like I said, I'm exploding shapes into little bits. I'm not concerned about the bits being perfectly evenly sized, but they should still be bits, not elongated triangles. I don't see how marching squares is at all relevant... is that not for turning bitmaps into polygons essentially? – Marry

Destructible meshes, yes. Thought I mentioned that. Will be done in real-time, but hopefully not every frame :) It's for a game... just when two objects collide hard, I want them to explode. I'll take your suggestions into consideration, thanks! – Marry

Answer 7

If you have convex polygons, and you're not too hung up on quality, then this is really simple - just do ear clipping. Don't worry, it's not O(n^2) for convex polygons. If you do this naively (i.e., you clip the ears as you find them), then you'll get a triangle fan, which is a bit of a drag if you're trying to avoid slivers. Two trivial heuristics that can improve the triangulation are to

1. Sort the ears, or if that's too slow
2. Choose an ear at random.

If you want a more robust triangulator based on ear clipping, check out FIST.

Absorptivity

I'm aware of ear clipping, but it doesn't produce very nice results, as you pointed out. But thanks :) – Marry