如何从四面体网格中提取表面三角形？

Question

我想使用一些3D软件来渲染四面体网格。然而，由于我拥有的四面体网格文件格式不受支持，因此无法直接在所选软件中（例如Blender）加载。所以我应该自己提取相应顶点索引的面。

对于一个立方体，我的四面体文件包含每个四面体的顶点ID，其中包括4个面，如下所示：

v 0.41 0.41 0.41
v 0.41 0.41 -0.41
v 0.41 -0.41 0.41
v 0.41 -0.41 -0.41
v -0.41 0.41 0.41
v -0.41 0.41 -0.41
v -0.41 -0.41 0.41
v -0.41 -0.41 -0.41
t 0 1 2 4
t 5 1 4 7
t 1 2 4 7
t 3 1 7 2
t 6 4 2 7

但是，我不确定如何在给定这些数据的情况下提取表面网格。有人知道我应该如何做或该使用什么算法吗？

- Amir

---

每个v行都是某个顶点的x y z坐标。每个t行是三角形或四边形的顶点的第一、第二、第三和可选的第四个索引。这里 是一个很好的教程，在Unity中创建网格时，您可以了解顶点位置以及如何将顶点连接成三角形。 - Ruzihm

@Ruzihm 我知道每个 v 行的含义，但不确定如何从每个 t 行中获取 4 个面。 - Amir

为什么不分享生成该文件的代码或应用程序呢？ - Ruzihm

@Ruzihm 我没有权限访问那个。我只有这些四面体网格文件。 - Amir

我不理解的是，为什么你说这个有4个面，但我看到了5个..还有，为什么每个面明显由4个而不是3个顶点构成？如果它是一个四面体，难道不应该只有4个顶点和4个面吗？ - derHugo

我想我已经弄清楚如何从“t”行中获取面。基本上只需要获取4个选择3个顶点集。表面网格由在四面体中不共享公共顶点的面表示。稍后我会发布答案。 - Amir

Answer 1

这里有一种简单的暴力方法。对于每个四面体，例如看第三个，t: 1 2 4 7，通过移除每个顶点，生成所有四个四面体顶点中的三个顶点的四种组合，即

face[t][0]: 1 2 4,  face[t][1]: 1 2 7,  face[t][2]: 1 4 7, face[t][3]: 2 4 7

并按升序对每个三角形的整数标签进行排序（以确保唯一性）。这样，您就可以生成所有四面体网格中所有面的列表（或某种数组）。 现在，在刚刚生成的所有三角形面的列表上运行一个循环，查找重复项。每当一个三角形在所有三角形面的列表中出现两次时，将其删除，因为它是内部三角形，即相邻的两个四面体共享此三角形面，因此它是内部面而不是边界面。 经过此过程后，剩下的只有四面体网格的边界（即表面）三角形面。 以下是使用Python编写此算法的示例。

import numpy as np

def list_faces(t):
  t.sort(axis=1)
  n_t, m_t= t.shape 
  f = np.empty((4*n_t, 3) , dtype=int)
  i = 0
  for j in range(4):
    f[i:i+n_t,0:j] = t[:,0:j]
    f[i:i+n_t,j:3] = t[:,j+1:4]
    i=i+n_t
  return f

def extract_unique_triangles(t):
  _, indxs, count  = np.unique(t, axis=0, return_index=True, return_counts=True)
  return t[indxs[count==1]]

def extract_surface(t):
  f=list_faces(t)
  f=extract_unique_triangles(f)
  return f

V = np.array([
[ 0.41,  0.41,  0.41],
[ 0.41,  0.41, -0.41],
[ 0.41, -0.41,  0.41],
[ 0.41, -0.41, -0.41],
[-0.41,  0.41,  0.41],
[-0.41,  0.41, -0.41],
[-0.41, -0.41,  0.41],
[-0.41, -0.41, -0.41]])

T = np.array([
              [0, 1, 2, 4],
              [5, 1, 4, 7],
              [1, 2, 4, 7],
              [3, 1, 7, 2],
              [6, 4, 2, 7]])


F_all = list_faces(T)
print(F_all)
print(F_all.shape)

F_surf = extract_surface(T)
print(F_surf)
print(F_surf.shape)

- Futurologist

Answer 2

一种非常有效的方法是使用哈希集合（在Python中称为set，在C++中称为std::unordered_set，在Rust中称为HashSet）

从四面体的体积中检索信封的原理与检索三角形表面的轮廓相同（您可以在此处找到）

这在Python中给出了以下代码，在任何具有哈希集合的语言中都很容易翻译（在此处简单地使用Python）：

envelope = set()
for tet in tetraedrons:
    for face in (  (tet[0], tet[1], tet[2]), 
                   (tet[0], tet[2], tet[3]), 
                   (tet[0], tet[3], tet[2]),
                   (tet[1], tet[3], tet[2]) ):
        # if face has already been encountered, then it's not on the envelope
        # the magic of hashsets makes that check O(1) (eg. extremely fast)
        if face in envelope:    envelope.remove(face)
        # if not encoutered yet, add it flipped
        else:                   envelope.add((face[2], face[1], face[0]))

# there is now only faces encountered once (or an odd number of times for paradoxical meshes)
return envelope

- jimy byerley