具有许可许可证的强大,快速复杂的多边形(带孔)三角剖分c/c ++库

Question

我是开源游戏Bitfighter的开发者.根据以下SO帖子,我们使用优秀的"三角"库进行网格区生成,以便与我们的游戏内AI(机器人)一起使用:

带孔的多边形三角剖分

然而,当我们想要为Debian打包我们的游戏时,我们遇到了一个小问题 - 使用'Triangle'库将使我们的游戏被视为'非自由'.

我们对"三角"图书馆的表现非常满意,并不真的想放弃它; 但是,我们也不喜欢处理许可证问题.因此,我们已着手寻找一种合适的,允许许可的替代品,它可以在稳健性和速度方面与"三角形"相匹配.

我们正在寻找一个C或C++库,用于将大型复杂区域划分为三角形,可以处理以任何方式放置在一起的任何类型的不规则多边形以及孔.稳健性是我们的首要需求,速度几乎同样重要.

我找到了poly2tri,但是它遇到了一个错误,它无法处理具有重合边的多边形.

我们已经找到了几个库,但似乎都有一个或另一个问题:要么太慢,要么不处理漏洞,或者遇到一些bug.目前我们正在测试polypartition,我们寄予厚望.

什么是伟大的'三角'图书馆的最佳替代品,但有许可证？

Answer 1

我找到了解决方案.毕竟是poly2tri,使用了优秀的Clipper库,并对输入添加了一些小的算法.

我们的流程如下:

1. 使用带NonZero绕组的接头通过Clipper运行所有孔(这意味着内孔的缠绕方向与外部孔相反).Clipper还保证了良好的干净输入点,epsilon中没有重复.
2. 将我们的孔过滤成逆时针和顺时针缠绕的孔.顺时针孔意味着孔是迂回的,并且内部还有另一个需要进行三角测量的同心区域
3. 使用poly2tri,对外部边界和每个顺时针多边形进行三角测量,使用其余的孔作为poly2tri的输入,如果在其中一个边界内找到它们的话.

结果: poly2tri似乎与Triangle一样快三角形,并且到目前为止我们已经抛出的所有内容都非常强大.

对于那些感兴趣的人,这是我们的代码更改.

更新

我试图将我们的clipper-to-poly2tri代码和我们的健壮性添加到我从这里开始的一个单独的库中: clip2tri