c++ - C++ 2D 曲面细分库？

Question

我有一些凸多边形存储为点的 STL 向量（或多或少）。我想非常快速地对它们进行镶嵌，最好是尺寸相当均匀的碎片，并且没有“条子”。

我打算用它把一些物体炸成小块。有谁知道一个很好的库来细分多边形（将它们划分为较小的凸多边形或三角形的网格）？

我已经查看了一些我已经在网上找到的，但我什至无法编译它们。这些学术类型并没有过多考虑易用性。

score 17 · 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;
}

要安装 cgal，如果您在 Windows 上，您可以使用安装程序来获取预编译库，并且此页面上的每个平台都有安装指南。它可能不是最简单的安装，但您可以获得最常用和最强大的计算几何库，并且cgal 邮件列表对于回答问题非常有帮助......

score 9 · Accepted Answer

9

poly2tri看起来像一个非常好的用于 2D Delaunay 三角剖分的轻量级 C++ 库。

于 2012-04-09T17:05:24.910 回答

score 4 · Accepted Answer

正如上面评论中提到的 balint.miklos，Shewchuk 的三角形包非常好。我自己用过很多次；它很好地集成到项目中，并且有triangle++ C++ 接口。如果您想避免长条，则允许三角形添加（内部）施泰纳点，以便生成高质量的网格（通常是受约束的符合 delaunay 三角剖分）。

score 3 · Accepted Answer

如果您不想将整个 GCAL 构建到您的应用程序中 - 这可能更容易实现。

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

score 2 · Accepted Answer

我刚刚开始研究同样的问题，我正在考虑 voronoi 镶嵌。原始多边形将分散半随机点，这些点将成为 voronoi 单元的中心，它们分布得越均匀，单元的大小就越规则，但它们不应该在完美的网格中，否则内部多边形看起来都一样。因此，第一件事是能够生成这些单元中心点——在源多边形的边界框上生成它们，并且内部/外部测试不应该太难。

voronoi 边缘是这张图片中的虚线，是 delaunay 三角剖分的补充。所有尖锐的三角形点都变钝了：

在此处输入图像描述

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

下一步是创建 voronoi 多边形。Voro++ http://math.lbl.gov/voro++/是面向 3D 的，但在其他地方建议使用大约 2d 结构，但比面向 2D voronoi 的软件慢得多。另一个看起来比随机学术主页孤儿项目好得多的软件包是https://github.com/aewallin/openvoronoi。

看起来 OpenCV 曾经支持沿着这些思路做一些事情，但它已被弃用（但 c-api 仍然有效？）。cv::distTransform 仍在维护，但对像素进行操作并生成像素输出，而不是顶点和边多边形数据结构，但如果不是你的，可能足以满足我的需求。

一旦我了解了更多信息，我会更新这个。

score 1 · Accepted Answer

如果您有凸多边形，并且您不太在意质量，那么这真的很简单 - 只需进行剪耳即可。别担心，凸多边形不是 O(n^2)。如果您天真地执行此操作（即，在找到耳朵时将其夹住），那么您将得到一个三角扇，如果您想避免裂片，这会有点拖累。可以改进三角剖分的两个简单的启发式方法是

对耳朵进行分类，或者如果这太慢了
随机选择一只耳朵。

如果您想要一个基于耳夹的更强大的三角测量器，请查看FIST。

score 1 · Accepted Answer

关于所需输入和输出的更多细节可能会有所帮助。

例如，如果您只是想将多边形变成三角形，那么三角形扇形可能会起作用。如果你想把一个多边形切成小块，你可以实现某种行进方块。

好吧，我做了一个错误的假设——我认为行进方块会更类似于行进方块。事实证明这是完全不同的，根本不是我的意思.. :|

无论如何，要直接回答您的问题，我不知道有任何简单的库可以满足您的需求。我同意 CGAL 的可用性。

我想到的算法基本上是用线分割多边形，其中线是网格，所以你大多得到四边形。如果你有一个多边形线相交，那么实现会很简单。提出这个问题的另一种方法是将二维多边形视为一个函数，并覆盖一个点网格。然后你只需做一些类似于行进立方体的事情。如果所有 4 个点都在多边形中，则制作一个四边形，如果 3 个在制作一个三角形，2 个在制作一个矩形，等等。可能有点矫枉过正。如果您想要看起来稍微不规则的多边形，您可以随机化网格点的位置。

另一方面，您可以进行 catmull-clark 风格的细分，但忽略平滑。该算法基本上是在质心和每条边的中点添加一个点。然后，对于原始多边形的每个角，您制作一个新的较小的多边形，连接角之前的边缘中点、角、下一个边缘中点和质心。这会平铺空间，并将具有与您的输入多边形相似的角度。

所以，有很多选择，我喜欢头脑风暴解决方案，但我仍然不知道你打算用它做什么。这是为了创建可破坏的网格吗？您是否在进行某种需要较小元素的网格处理？试图避免 Gouraud 着色伪影？这是作为预处理还是实时运行的东西？准确性有多重要？更多信息将产生更好的建议。

c++ - C++ 2D 曲面细分库？

7 回答 7

Related

Reference