如何求出delaunay三角剖分的边界

Question

我正在实现"三维模型中几何感知手柄和隧道环的计算“中的隧道检测算法。

在实际隧道检测之前，需要对输入进行预处理，如论文第5节所述

为了应用持久化算法，我们假定输入面M是用一个简单复形K表示的，它决定了M的凸壳是K的一个子复形，这意味着我们对内外空间O都有显式的单纯表示。

我的输入是一个三角形的封闭曲面网格，根据上面的引语，我的理解是我应该：

1.读取曲面网格，利用曲面网格的点执行delaunay三维算法。这一步的输出是四面体网格。

2.从step1中可以得到边界面(边界与输入面网格相同)、外部三角形和内部三角形。

论文的作者实际上发布了一个Youtube上的视频，说明了上面提到的步骤。

我的问题是:在step2中，如何从四面体网格中获得表面和外部三角形？在delaunay三角剖分3d中，它所需要的只是点云(即。(点的位置)。

我尝试过构造初始曲面网格的SDF，并尝试用SDF从四面体中找到曲面，但这证明不是理想的。

有人能给我点提示吗？还是我走错方向了？

Answer 1

除非生成的tet网格使用原始表面网格三角形，否则不可能(不可能)获得原始边界表面(当然，原始边界表面是凸壳)。如果边界四面体面保留原来的网格结构，则原始的表面网格三角形只能编码到生成的四面体网格中。用于生成单元网格(无约束)的Delaunay方法不这样做。无约束Delaunay方法可能会边缘翻转，从而失去原来的表面镶嵌.

无约束Delaunay方法总是产生一个凸包(原始点集.( 2D和3D)，所以听起来这个例程正常工作(你会得到一个凸包)，但是它是用来生成单元网格的方法，在这种情况下阻止了你想要的东西。

因此不幸的是，在这种情况下，您不能使用Delaunay，而不是限制-Delaunay创建了tet网格。

构造非结构网格的替代方法，如约束-Delaunay法和前沿网格法，以原始曲面网格为边界条件，可以保留或编码原始曲面网格，利用以下方法提取原始曲面网格，得到原始边界曲面网格。

如果使用另一种方法生成保留/编码边界面为tet面的单元网格，则可以通过识别在共享顶点的元网格中一次使用哪一组面来获得该单元网格的边界面。从定义上讲，这些三角形是tet网格边界面的三角形。

所有“内”面最多由两个四面体使用。所有的“外部”(边界面)面将只使用一次。

1. 共享单元网格的顶点。
2. 创建一个包含所有三角形(面)的列表(每个组有4个面，并且由于组网格使用共享顶点，每个组将有4个顶点)。
3. 创建顶点使用wrt到三角形的列表。即每个三角形的顶点列表。
4. 大多数三角形应该有6个顶点使用(3个唯一的顶点，所以3对)。具有3个顶点(无重复顶点索引)的三角形没有相邻的三角形，边界三角形也是如此。
5. 仅使用边界三角形重建三角形曲面。

健壮性是很重要的，在单元网格中的任何空洞都将被识别为边界曲面，但是当共享顶点(检查哪些顶点是相等的)时，你可以相当自由地保持相等的容忍度。