c++ - 在现有的 Delaunay 四面体化中创建并重新填充孔

Question

我正在尝试实现 mesh generation algorithm .我使用 CGAL::Delaunay_triangulation_3 表示 Delaunay 四面体化类(class)。

在算法的一个阶段(第 7 节:小平面恢复)，我有一个 Delaunay 四面体化(比如 DT0)，我需要创建一个空腔(或孔)C在 Delaunay 四面体化内部(从而将其转换为 DT1 )并通过在空腔的顶点上执行 Delaunay 四面体化(例如 DT2 )再次用新的四面体填充它。产生的四面体化不需要纯粹 Delaunay(即，它可能有一些不满足 empty sphere criteria 的单元格)。下面的上下文部分中提到了有关为什么需要再次创建和重新填充此类空腔的更多详细信息。

问题:
是否可以在 CGAL 中在现有 Delaunay 四面体化中创建这样的空腔并用另一个四面体化填充它？

相关详情:

• 空腔 C是一个多面体，其所有面都与 DT0 中的单元格共享.
• DT2不表示 C 的顶点的完全 Delaunay 四面体化.它只包含 C 内的那些四面体, 其余的四面体被丢弃。
• 我找到了 this question成为有点与我的有关，但仍未解决。

上下文:
创建空腔并重新填充它的目的如下:算法(上述)用于计算约束保留 Delaunay 四面体化。该算法的输入是一组顶点、线段(线段连接 2 个顶点)和小平面(在我的例子中是三角形)作为约束，必须在最终四面体化中保留。在这个问题中，我正在讨论算法的 facet preservation 部分的实现。为了恢复最终四面体化中任何缺失的约束面，算法创建一个空腔并用四面体(或单元)重新填充它，这样这些单元中的一些面的组合可以恢复约束面(即, f1+f2+...+fn=f 其中 f1,f2..fn 是空腔中一些新创建的单元的面，f 是约束面，或者换句话说，f1,f2..fn 是输出四面体化中 f ) 的子面。输出四面体化在文献中称为Constrained Delaunay tetrahedralization，它可能是也可能不是Delaunay。

我的尝试:
目前，我没有找到任何相关的 CGAL 类来直接解决这个问题，所以我正在考虑执行以下操作:

1. 表示初始 Delaunay 四面体化 DT0使用 CGAL::Delaunay_triangulation_3 .
2. 计算腔C里面DT0遵循算法并表示 C作为一个单独的 Polyhedron_3目的。其余的四面体集共同表示为 DT1 .
3. 计算 Delaunay 四面体 DT2' C 的顶点.
4. 从 DT2' 中选择单元格(根据算法)计算 DT2 .
5. 最后，合并DT1和 DT2 .由于两者共享 C 的方面(由算法保证)，因此它们原则上可以连接。

现在我想代表DT1和 DT2作为std::list<Tetrahedron_3>对象，但如何合并它们以创建四面体化？

Answer 1

这是CGAL中实现点移除的方式。您可能需要查看删除代码。