logo标签列表

给定一组三角形顶点和面，分离物体并形成单独的网格。

pythonnetworkxmeshmplot3dmarching-cubes
3

编辑：我已经在这里写了一个更简明的问题版本，但我仍然保留这篇文章，因为它是一个完整的解释。

给定一个3D NumPy数组，marching cubes可以在某个阈值周围形成一个3D 对象。

import numpy as np
from skimage import measure

A = np.zeros((12,12,12))
#A[A<1] = -1
for i in np.arange(1,2):
    for j in np.arange(1,2):
        for k in np.arange(1,2):
            A[i,j,k] = 10

for i in np.arange(8,9):
    for j in np.arange(8,9):
        for k in np.arange(8,9):
            A[i,j,k] = 10

verts, faces, normals, values = measure.marching_cubes_lewiner(A,1)

# which returns 

verts = [[0.1, 1.,  1. ]  [1.,  1.,  0.1]  [1.,  0.1, 1. ]  [1.,  1.,  1.9]  [1.,  1.9, 1. ]
 [1.9, 1.,  1. ]  [7.1, 8.,  8. ]  [8.,  8.,  7.1]  [8.,  7.1, 8. ]  [8.,  8.,  8.9]
 [8.,  8.9, 8. ]  [8.9, 8.,  8. ]]

faces = [[ 2,  1,  0]  [ 0,  3,  2]  [ 1,  4,  0]  [ 0,  4,  3]  [ 5,  1,  2]  [ 3,  5,  2]
 [ 5,  4,  1]  [ 4,  5,  3]  [ 8,  7,  6]  [ 6,  9,  8]  [ 7, 10,  6]  [ 6, 10,  9]
 [11,  7,  8]  [ 9, 11,  8]  [11, 10,  7]  [10, 11,  9]]

这可以被绘制出来：

import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d.art3d import Poly3DCollection
from mpl_toolkits.mplot3d import Axes3D

mesh = Poly3DCollection(verts[faces])

mesh.set_edgecolor('k')
mesh.set_facecolor('b')
ax.set_xlim(0,10)
ax.set_ylim(0,10)
ax.set_zlim(0,12)

返回这个漂亮的 3D 图像：

四面体

我使用自己的代码（见下文）来分离这些物体，得到：

graph1 = {(1.0, 1.0, 0.10000000149011612), (1.899999976158142, 1.0, 1.0), (0.10000000149011612, 1.0, 1.0), (1.0, 1.899999976158142, 1.0), (1.0, 0.10000000149011612, 1.0), (1.0, 1.0, 1.899999976158142)}

graph2 = {(8.899999618530273, 8.0, 8.0), (8.0, 8.899999618530273, 8.0), (7.099999904632568, 8.0, 8.0), (8.0, 8.0, 7.099999904632568), (8.0, 7.099999904632568, 8.0), (8.0, 8.0, 8.899999618530273)}

现在的问题是，虽然我已经找到了组成每个图形的顶点，但我不再有一种简单的方法来为每个对象创建单独的三维网格。之前，使用 verts[faces] 来创建网格，但如何将每个 graph 与 faces 相关联以创建三角形网格并不明显。我已经尝试解决这个问题，但没有成功。例如：

verts1 = verts[0:6]
faces1 = faces[0:6] 
mesh = Poly3DCollection(verts1[faces1])

这不起作用。我认为关键是找到与每个对象对应的面。如果这样做，它可能会起作用。例如，我们的第一个图仅包括顶点1至6。因此，我们只需要引用那些顶点的faces。作为演示，可以使用以下代码重新创建第一个图graph1（而不使用graph2）：

faces1 = faces[0:8]
mesh = Poly3DCollection(verts[faces1])
# and plot like above

如果我可以记录不仅顶点本身，还包括它们的索引，那么我就可以对引用该对象的那些faces进行排序。我来解释一下。首先遇到的问题是，我没有这些索引。这是我的对象排序方式。我们首先创建一个线列表（或边列表），然后将它们变成元组，并使用networkx查找连接部件。

# create linelist
linelist = []
for idx, vert in enumerate(faces):  
    for i,x in enumerate(vert):
        l = [np.ndarray.tolist(verts[faces[idx][i]]), np.ndarray.tolist(verts[faces[idx][(i+1)%len(vert)]])] # connect the verts of the triangle
        linelist.append(l)  # add to the line list

# Creates graph
tmp = [tuple(tuple(j) for j in i) for i in linelist]
graph = nx.Graph(tmp)
graphs = []
i=0
for idx, graph in enumerate(sorted(nx.connected_components(graph),key = len, reverse = True)):
    graphs.append((graph))
    print("Graph ",idx," corresponds to vertices: ",graph,'\n\n',file=open("output.txt","a"))         
    i+=1

我不知道networkx如何记录每个顶点的索引。

其次，可能会出现每个对象引用的faces是不相交的情况，即它可能是faces[0:4] + faces[66] + faces[100:110]。然而，这可能是可以克服的。

假设我们可以为每个图形生成一个索引列表，主要问题是发现一种有效的方法来发现哪些面引用了那些顶点。我的解决方案适用于这组对象，但对于更复杂的排列（我可以提供），它也非常缓慢。尽管如此，这里是：

objects  = []
obj = []
i = 0
for idx, face in enumerate(M):
    if i == 0:
        obj.append(face)
        i = i + 1
    else:
        if np.isin(face,obj).any():
            obj.append(face)
        else: 
            objects.append(obj.copy())
            obj = []
            obj.append(face)
            i = 0
        if idx == len(M)-1:
            objects.append(obj.copy())

如果你读到这里，我对社区的印象深刻。我认为也许有一种有效的方法可以用 networkx 实现，但我还没有找到它。

期望输出: 我想将面孔按连接组件排序，就像我对顶点排序一样。 graph1 = faces[x1] + faces[x2] + ... + faces[xn]。

编辑：如果有人能帮我编码，我有一个想法（部分感谢 @Ehsan）。在分成连接组件并找到图形后，每个组件的顶点可以被哈希以查找原始索引。然后，您可能能够搜索包括至少一个这些索引的faces（因为如果它包含一个顶点，那么它必须是graph的面）。我不确定这样做是否高效。如果有一个快速的 networkx 解决方法，那就太好了。

你能否以正确的格式（即所有逗号设置正确）添加“faces”和“verts”？这样我们就可以直接在我们的代码中使用你的数据。此外，我不确定我是否理解了你的回答。你想将面和顶点拆分成相同风格的列表，这些列表属于连接的对象吗？也许添加所需输出形式会有助于澄清这一点。 - Sparky05
当然，已经更新了faces和verts。是的，我基本上想以与verts相同的方式将面排序为对象，其中每组verts都连接在一起。由于verts可以放在边缘列表的形式中，因此这更容易。我不知道如何使用faces做到这一点。我会更新帖子并添加我忘记放入的更多代码。 - McM
@Sparky05我已经创建了一个更简洁的问题，并且有一个更明确的期望：https://stackoverflow.com/questions/61584283/find-connected-components-in-list-of-triangle-vertices - McM
1个回答
0

@Paul Broderson回答了这个问题https://stackoverflow.com/a/61590348/12919727

我只是为了美观而将其放在这里：

#!/usr/bin/env python
"""
Given a list of triangles, find the connected components.

https://stackoverflow.com/q/61584283/2912349
"""
import itertools
import networkx as nx

faces = [[ 2,  1,  0],  [ 0,  3,  2],  [ 1,  4,  0],  [ 0,  4,  3],  [ 5,  1,  2],  [ 3,  5,  2],
         [ 5,  4,  1],  [ 4,  5,  3],  [ 8,  7,  6],  [ 6,  9,  8],  [ 7, 10,  6],  [ 6, 10,  9],
         [11,  7,  8],  [ 9, 11,  8],  [11, 10,  7],  [10, 11,  9]]

#create graph
edges = []
for face in faces:
    edges.extend(list(itertools.combinations(face, 2)))
g = nx.from_edgelist(edges)

# compute connected components and print results
components = list(nx.algorithms.components.connected_components(g))

for component in components:
    print(component)

# {0, 1, 2, 3, 4, 5}
# {6, 7, 8, 9, 10, 11}

# separate faces by component
component_to_faces = dict()
for component in components:
    component_to_faces[tuple(component)] = [face for face in faces if set(face) <= component] # <= operator tests for subset relation

for component, component_faces in component_to_faces.items():
    print(component, component_faces)
# (0, 1, 2, 3, 4, 5) [[2, 1, 0], [0, 3, 2], [1, 4, 0], [0, 4, 3], [5, 1, 2], [3, 5, 2], [5, 4, 1], [4, 5, 3]]
# (6, 7, 8, 9, 10, 11) [[8, 7, 6], [6, 9, 8], [7, 10, 6], [6, 10, 9], [11, 7, 8], [9, 11, 8], [11, 10, 7], [10, 11, 9]]
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接