0

我正在尝试学习使用 CGAL。我对使用哪种数据结构和三角测量方案来解决我的问题有疑问。

问题描述：

我有少量（<1000）粒子在球体上移动。我需要用这个点云制作一个三角形的Delaunay网格。在每个时间步骤，我需要：

  1. 仅在需要时重新网格化点云，以使 Delaunay 准则仍然成立。独立于点坐标存储网格连通性。
  2. 保持拓扑固定，使用迭代求解器进行一些优化以计算新的粒子位置。具有相同连通性的求解器迭代次数可以是 100 次或更多。在每次迭代中，计算需要每个三角形的面积和一些由边连接的顶点的计算（即每个顶点与最近邻的第一环相互作用）。

问题：

  1. 如何在不使三角剖分的迭代器或循环器失效的情况下更改与网格（三角剖分数据结构、曲面网格、多面体等）顶点关联的点的坐标？
  2. 如何检查何时需要重新划分网格？
  3. 哪种数据结构可以在整个网格上一次通过最快的速度访问所有边和面？每条边都在两个三角形之间共享。边缘的计算是最昂贵的。因此，我只想为每个边计算一次。对所有面进行一次迭代并分别对所有边进行迭代可能效率较低。

如果需要更多信息，请告诉我。

4

1 回答 1

1

部分回答您的问题：

3/ 您可以使用 openmesh 库来网格化您的点。它允许一个人非常快地到达第一个邻居环，如此处所述，以及所有边缘和面。我不能确定是不是数据结构可以最快地访问这些信息。为了让您了解预期的速度，在我的工作中，我使用 openmesh：运行 30 个“for”循环，每个循环遍历我的网格的 500 000 个顶点的第一个环邻居并计算一些算术（通常是重心)，总共需要不到 100 毫秒。

1/ 使用 openmesh，您可以随时重置点位置而不更改其连接性（它不会删除已定义的边和面）。

2/ 要检查是否需要重新划分网格，您必须检查网格的每个点是否仍满足 Delaunay 条件。如果不是，重新网格化整个或交换合适的边缘。

希望这可以帮助！

于 2018-07-06T12:50:22.813 回答