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. The pieces don't have to be perfectly evenly sized, but they should still be bits and pieces... and preferably no slivers -- I'm just 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.

Answer 1

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.

Answer 2

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%5FPolygon%5FTriangulation.shtml

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

Answer 4

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.