C++ 2D曲面细分库？

Question

C++ 2D曲面细分库？

c++geometrycomputational-geometrytesselation

10

我有一些以STL点向量形式存储的凸多边形（或者类似的）。我想要快速地镶嵌它们，最好是均匀划分，没有“薄片”。

我将用它来将一些物体炸成小块。有人知道一个好的库来镶嵌多边形（将它们划分为较小的凸多边形或三角形网格）吗？

我已经查看了一些我在网上找到的，但我甚至无法编译它们。这些学术类型不太关心易用性。

- mpen

7个回答

9

Poly2tri 看起来是一个非常好用的、轻量级的C++库，可以用于实现二维Delaunay三角网格化。

- prideout

2

只想补充一下，poly2tri不支持自相交的多边形。 - Coolant

4

如上评论中balint.miklos提到的，Shewchuk的triangle包非常不错。我自己也用过很多次；它可以很好地集成到项目中，并且有triangle++ C ++接口。如果你想避免出现slivers，则允许triangle添加（内部）Steiner点，以便生成高质量的网格（通常是约束一致的Delaunay三角剖分）。

- Victor Liu

3

如果您不想将整个GCAL构建到您的应用程序中-这可能更容易实现。 http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

- Martin Beckett

就我个人而言，这个Flipcode镶嵌代码非常出色。对于任意复杂的多边形都能快速且正确地进行处理。 - Blake Senftner

2

我刚开始研究这个问题，考虑使用泰森多边形。原始多边形将获得一些半随机点的散布，这些点将是泰森单元的中心，它们分布得越均匀，单元的大小就越规则，但它们不应该在完美的网格上，否则内部多边形看起来都是相同的。所以第一步是能够生成这些单元中心点-在源多边形的边界框和内/外部测试上生成它们应该不难。

泰森图中的虚线是泰森边缘，是德劳内三角剖分的补集。所有尖锐的三角形点都被钝化了。

Boost有一些泰森功能：http://www.boost.org/doc/libs/1_55_0/libs/polygon/doc/voronoi_basic_tutorial.htm。

下一步是创建泰森多边形。Voro++ http://math.lbl.gov/voro++/ 面向3D，但建议在大约2D结构上工作，但比面向2D泰森的软件要慢得多。另一个包看起来比随机的学术主页项目好得多，就是https://github.com/aewallin/openvoronoi。

看起来OpenCV曾经支持这样做，但已弃用（但C-API仍然可以工作？）。cv::distTransform仍在维护，但操作的是像素并生成像素输出，而不是顶点和边缘多边形数据结构，但如果不是你的话，可能足够满足我的需求。

我会在学到更多之后更新这个问题。

- Lucas Walter

1

如果您拥有凸多边形，并且不太在意质量问题，那么这非常简单-只需使用 ear clipping。别担心，对于凸多边形来说，它不是O(n²)的。如果您以天真的方式执行此操作（即在找到耳朵时剪切它们），则会得到一个三角形扇面，如果您试图避免片状物，则可能会有点困难。可以改善三角测量的两个微不足道的启发式方法是：

按耳朵排序，或者如果太慢
随机选择一只耳朵。

如果您想要基于耳朵剪切的更健壮的三角形剖分器，请查看FIST。

- IV.

我知道耳剪裁剪法，但正如你所指出的那样，它并不能产生非常好的结果。不过还是谢谢 :) - mpen

1

更详细的输入和输出信息可能会有所帮助。

例如，如果您只是想将多边形转换为三角形，那么三角形扇形可能会起作用。如果您想将多边形切成小块，则可以实现某种行进方格算法。

好的，我做了一个错误的假设——我认为 marching squares 会更像 marching cubes。结果它是非常不同的，完全不是我想要的.. :|

无论如何，直接回答你的问题，我不知道有任何简单的库可以做到你想要的功能。我同意 CGAL 的易用性。

我想的算法基本上是用线条切割多边形，其中线条是网格，所以你大部分都得到四边形。如果你有一个多边形-线条相交，实现就很简单。另一种表述这个问题的方式是将二维多边形视为函数，并覆盖一个点网格。然后你只需要做类似于 marching cubes 的事情...如果所有4个点都在多边形中，则制作四边形；如果3个在多边形内则制作三角形，2个则制作矩形等等。可能过度设计了。如果你想要略微不规则的多边形，可以随机化网格点的位置。

另一方面，您可以使用Catmull-Clark风格的细分，但省略平滑处理。算法基本上是在重心和每个边的中点处添加一个点。然后对于原多边形的每个角落，您都可以创建一个新的较小多边形，连接到该角落之前的边中点，该角落，下一个边中点和重心。这样铺砌空间，并且其角度类似于您的输入多边形。

因此，有很多选择，我喜欢集思广益解决问题，但我仍然不知道您打算用它做什么。这是为了创建可摧毁的网格？您是否正在执行某种需要较小元素的网格处理？是否尝试避免Gouraud着色伪影？这是作为预处理或实时运行的东西吗？准确性有多重要？提供更多信息将产生更好的建议。

- tfinniga

好的，就像我说的一样，我正在将形状分解成小块。我不关心这些块是否完全均匀，但它们应该仍然是块，而不是拉长的三角形。我不明白为什么使用 marching squares 有任何相关性...难道不是用于将位图转换为多边形吗？ - mpen

可被摧毁的网格，没错。我想我提到过了。将在实时中完成，但希望不是每一帧 :) 这是为了游戏...只有当两个物体猛烈碰撞时，我希望它们爆炸。我会考虑你的建议，谢谢！ - mpen

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- balint.miklos · Accepted Answer

CGAL提供了解决这个问题的包。最好使用2D Polygon Partitioning包，例如，您可以生成多边形的y-单调分割（也适用于非凸多边形），然后会得到下面这样的结果：

运行时间为O(n log n)。

在易用性方面，以下是一个生成随机多边形并进行分割的小例子代码（基于这个手册示例）:

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;
}

如果你使用Windows系统，可以使用安装程序获取预编译库来安装CGAL，每个平台都有安装指南在此页面上。虽然安装可能不是最简单的，但你将获得当前最广泛和稳健的计算几何库，并且cgal邮件列表非常有帮助，可以回答你的问题...