17

I am a developer of the open-source game, Bitfighter. As per the following SO post, we have used the excellent 'Triangle' library for mesh-zone generation for use with our in-game AI (robots):

Polygon Triangulation with Holes

However, we ran into a small snag when wanting to package our game for Debian - the use of the 'Triangle' library will make our game be considered as 'non-free'.

We have been extremely pleased with the performance of the 'Triangle' library, and don't really want to give it up; however, we don't like dealing with license issues either. Therefore we have embarked upon a quest to find a suitable, permissively-licensed replacement that can match 'Triangle' in its robustness and speed.

We're looking for a C or C++ library for dividing large, complex, areas into triangles, that can handle any type of irregular polygons placed together in any manner, as well as holes. Robustness is our primary need, with speed almost as important.

I have found poly2tri, but it suffers from a bug in which it cannot handle polygons with coincident edges.

We have found several libraries, but all seem to suffer from one thing or another: either too slow, or don't handle holes, or suffer from some bug. Currently we are testing out polypartition and we have high hopes.

What are the best alternatives to the great 'Triangle' library, but have a permissive license?

Community
  • 1
  • 1
raptor
  • 799
  • 1
  • 5
  • 16
  • Can you elaborate on what you exactly need from a library like Triangle please? Perhaps you can write some of the algorithms yourself and publish your code like you need it. – Mare Infinitus Apr 16 '13 at 17:10
  • What exactly is the Triangle license? Have you tried emailing Jonathan Shewchuk to ask whether he would relicense it for you? – rob mayoff Apr 16 '13 at 17:18
  • 1
    @MareInfinitus We have levels with walls in them. The entire playable area of a level needs to be triangulated for mesh-zone navigation so our robots can move. – raptor Apr 16 '13 at 18:31
  • @raptor really hard to tell, perhaps best is, like rob mayoff already recommend, to write to the author of Triangle – Mare Infinitus Apr 16 '13 at 18:31
  • 1
    Funny that this has been closed as off-topic with the instructions to "describe the problem and what has been done so far to solve it" – raptor Apr 05 '15 at 03:54

3 Answers3

19

I found a solution. It was poly2tri after all, with the use of the excellent Clipper library, and some minor algorithmic additions to the inputs.

Our process is as follows:

  1. Run all our holes through Clipper using a union with NonZero winding (this means that inner holes are wound the opposite direction as outer ones). Clipper also guarantees nice clean input points with no repeats within epsilon.
  2. Filter our holes into ones that are wound counter-clockwise and clockwise. Clockwise holes meant the hole was circuitous and that there was another concentric area inside that needed to be triangulated
  3. Using poly2tri, triangulate the outer bounds and each clockwise polygon found, using the rest of the holes as inputs to poly2tri if they were found within one of the bounds.

Result: poly2tri seems to triangulate just about as fast as Triangle and has so far been very robust with everything we've thrown at it.

For those interested, here are our code changes.

Update

I have attempted to pull out our clipper-to-poly2tri code, with our robustness additions, into a separate library which I started here: clip2tri

raptor
  • 799
  • 1
  • 5
  • 16
  • I'd just like to follow up and say that poly2tri, while quick, does indeed suffer from robustness problems sometimes, usually involving points that are really close together in epsilon – raptor Oct 22 '13 at 22:49
  • 1
    I used the techniques you described and also found some instances in which poly2tri crashes. I was able to solve all the cases with this combination: set Clipper::StrictlySimple(true) before Execute(); after, I use CleanPolygon(), then your edgeShrink() to both the resulting polygons and holes; and finally, check for adjacent vertices with equal coordinates and delete one of them (discarding the entire polygon/hole when it gets to fewer than 3 vertices). – Fabio Ceconello Feb 25 '15 at 18:04
1

You can have a look at the 2D Triangulations package of CGAL. An example to triangulate a polygon with holes is given here. The license of the package is GPLv3+.

Note that it should not be too hard to extract only this package if needed.

sloriot
  • 6,070
  • 18
  • 27
1

As a small side-note:

I recently had to implement a complex polygon clipper & triangulator for cutting window frames into house walls.

While I was happy with the Vatti clipper results, the Delaunay triangulation used in poly2tri was too heavy to allow smooth dragging of the window frame along the barycentric coordinates of the wall face. After scratching my head a little bit, I ended up tricking this much simpler triangular to work with holes:

http://wiki.unity3d.com/index.php?title=Triangulator

What I did was horizontally subdivide the wall face by the height of the shortest clipping poly. In my case they are always rectangles, but they needn't be. Anyway, it forces the clipper to only work with regular or concave polys, and hence enables you to get away with a cheaper triangulation method.

Here are some screenshots showing it working:

https://www.dropbox.com/sh/zbzpvlkwj8b9gl3/sIBYCqa8ak

Hope this helps.

Rob Bantin
  • 11
  • 1