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

Question

我想使用一些 3D 软件渲染四面体网格。但是，我无法在我选择的软件（例如 Blender）中直接加载四面体网格，因为不支持我的四面体网格文件格式。所以我应该以某种方式自己提取具有相应顶点索引的面。

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

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

但是，我不确定如何根据这些数据提取表面网格。有人知道我该怎么做或算法是什么吗？

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)

Answer 2

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

从四面体体积中提取包络的原理与提取三角形表面轮廓的原理相同(as you can find here)

这在 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

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

How to extract surface triangles from a tetrahedral mesh?

c++

3d

rendering

unity3d

game-physics