问题

你可以使用 Trimesh Python 库来获取构成网格边界的顶点的索引。例如，对于平面网格，你可以期望只有位于外边缘的顶点。如果平面网格有一个孔，你还可以期望标记孔边缘的顶点。对于开放的圆柱网格，你可以期望只有位于两个开口处的顶点。

对于给定的网格实例，edges 和 edges_unique 属性可能不会返回你期望的结果。对于平面网格，facets_boundary 可能有效，但对于圆柱网格则可能失败。你是否需要自己查找边缘，例如使用 vertex_counts = np.bincount(faces.flatten())？

对于你的网格，这会产生以下结果：

平面网格 (4x5)
vertex_counts: [2 3 3 3 3 1 3 6 6 6 6 3 3 6 6 6 6 3 3 6 6 6 6 3 1 3 3 3 3 2]

带孔的平面网格 (8x8，中间有一个3x3孔)
vertex_counts: [2 3 3 3 3 3 3 3 1 3 6 6 6 6 6 6 6 3 3 6 4 3 3 3 5 6 3 3 6 3 0 0 0 3 6 3 3 6 3 0 0 0 3 6 3 3 6 3 0 0 0 3 6 3 3 6 5 3 3 3 4 6 3 3 6 6 6 6 6 6 6 3 1 3 3 3 3 3 3 3 2]

圆柱网格 (8 个圆周分割，6 个纵向分割)
vertex_counts: [3 3 3 3 3 3 3 3 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 3 3 3 3 3 3 3 3]

Planar mesh (4x5)
vertex_counts:  [2 3 3 3 3 1 3 6 6 6 6 3 3 6 6 6 6 3 3 6 6 6 6 3 1 3 3 3 3 2]

Planar mesh with hole (8x8 with a 3x3 hole in the middle)
vertex_counts:  [2 3 3 3 3 3 3 3 1 3 6 6 6 6 6 6 6 3 3 6 4 3 3 3 5 6 3 3 6 3 0 0 0 3 6 3 3
 6 3 0 0 0 3 6 3 3 6 3 0 0 0 3 6 3 3 6 5 3 3 3 4 6 3 3 6 6 6 6 6 6 6 3 1 3
 3 3 3 3 3 3 2]

Cylindrical mesh (8 circular divisions, 6 longitudinal divisions)
vertex_counts:  [3 3 3 3 3 3 3 3 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
 6 6 6 6 6 6 6 6 6 6 6 3 3 3 3 3 3 3 3]

答案1

得分: 2

对于给定的网格实例，edges（返回的条目比我拥有的顶点多！）和edges_unique属性都没有返回我期望的结果。

让我们从头开始。一个（三角形的）网格是3D坐标（顶点）的列表，加上顶点的三元组列表（三角形）。让我们考虑一个表示正方形的超简单网格：

0 --- 1
| \   |
|   \ |
2 --- 3

顶点 0、1、2 和 3 通过两个三角形连接在一起：[0, 2, 3] 和 [0, 3, 1]。在这个上下文中，网格的edges是所有三角形中的单独段，也就是 (0, 2)、(2, 3)、(3,0)、(0, 3)、(3, 1) 和 (1, 0) 的对列表。正如你所看到的，对角线边被重复，因为它出现在两个三角形中。edges_unique属性确保不包括这种重复。一般来说，对于具有 $V$ 个顶点的三角形网格，你可以预期有大约 $2V$ 个面和 $3V$ 条边（参见这里）。

facets_boundary对于平面网格有效，但对于圆柱形网格失败得相当惨。在阅读项目API文档时，我发现很难理解我应该从这些属性中期望什么。

根据文档："返回相邻共面面的面索引列表"。我同意这并不是非常清楚，但它所做的是将相邻且共面的面（三角形）分组。以圆柱体为例。顶部和底部圆都由一组相互接触且位于同一平面上的三角形组成。这两组三角形被分组为facets。类似地，一个盒子有六个facets（尽管每个facet可能可以分为多个三角形！）。另一种思考方式是：facet是一组可以被一个平面多边形替代的三角形。

现在，回到你最初的问题：如何找到边界？答案是保留仅属于一个三角形的所有边。如果你只需要一个无序的边列表，你可以简单地使用以下方法：

unique_edges = mesh.edges[trimesh.grouping.group_rows(mesh.edges_sorted, require_count=1)]

（参见这个GitHub问题）。如果你需要3D坐标，考虑使用Trimesh.outline()。

如果你需要一个有序的顶点列表，那么就会复杂一些。首先，这只有在你的网格是流形的情况下才有意义（没有边可以属于超过两个三角形）。然后，如这个答案所解释的，在获取边界边的列表后，你需要按顺序遍历它们。下面是一个可以做到这一点的函数：

def boundary(mesh, close_paths=True):
    # 所有边和边界边的集合（那些只出现一次的边）。
    edge_set = set()
    boundary_edges = set()

    # 遍历所有边，以元组的形式表示（i, j）（按 i < j 排序以消除歧义）。
    # 对于每个边，有三种情况可能发生：
    # 1. 边以前从未被访问过。在这种情况下，我们可以将其添加到边集合中，同时也将其添加为边界候选项。
    # 2. 边以前已被访问一次。我们希望将其保留在所有边的集合中，但从边界集合中删除它。
    # 3. 边以前至少已被访问两次。这通常是网格存在问题的迹象。更准确地说，它不是流形的，边界不是封闭的环。
    for e in map(tuple, mesh.edges_sorted):
        if e not in edge_set:
            edge_set.add(e)
            boundary_edges.add(e)
        elif e in boundary_edges:
            boundary_edges.remove(e)
        else:
            raise RuntimeError(f"网格不是流形：边 {e} 出现超过两次。")

    # 给定所有边界顶点，我们创建一个简单的字典，告诉它们谁是它们的邻居。
    neighbours = defaultdict(lambda: [])
    for v1, v2 in boundary_edges:
        neighbours[v1].append(v2)
        neighbours[v2].append(v1)

    # 现在，我们通过“提取”一个循环来查找所有边界路径。在获取路径后，我们从“boundary_edges”集合中删除其边。当所有边都已被使用时，算法终止。
    boundary_paths = []

    while len(boundary_edges) > 0:
        # 给定剩余边界边的集合，获取其中一个并用它来启动当前边界路径。
        # 在下文中，v_previous 和 v_current 表示我们当前正在处理的边。
        v_previous, v_current = next(iter(boundary_edges))
        boundary_vertices = [v_previous]

        # 保持迭代

<details>
<summary>英文:</summary>

&gt; For a given mesh instance, neither the `edges` (which returns more entries than I have vertices!), nor the `edges_unique` properties return what I expect.

Let&#39;s start from scratch. A (triangular) mesh is a list of 3D coordinates (the vertices) plus a list of triplets of vertices (the triangles). Let&#39;s consider a super-simple mesh, representing a square:

0 --- 1
| \ |
| \ |
2 --- 3

The vertices `0`, `1`, `2` and `3` are connected thanks to two triangles: `[0, 2, 3]` and `[0, 3, 1]`. In this context, the `edges` of a mesh are the individual segments in all triangles, that is, the list of couples `(0, 2)`, `(2, 3)`, `(3,0)`, `(0, 3)`, `(3, 1)` and `(1, 0)`. As you can see, the diagonal edge is repeated since it appears in both triangles. The `edges_unique` property makes sure that this repetition is not included. In general, for a triangular mesh with $V$ vertices you can expect to have roughly $2V$ faces and $3V$ edges (see [here](https://math.stackexchange.com/questions/425968/eulers-formula-for-triangle-mesh)).

> The `facets_boundary` works for planar meshes, but fails spectacularly for the cylindrical mesh. In reading the project API documentation, I find it difficult to understand what I should expect from these properties.

From the [documentation](https://trimsh.org/trimesh.base.html#trimesh.base.Trimesh.facets): "Return a list of face indices for coplanar adjacent faces". I agree that it is not super clear, but what it does is to group faces (triangles) that are both adjacent and co-planar. Take as an example a cylinder. The top and bottom circles are both made of a set of triangles that touch each other and lie on the same planes. The two sets of triangles are grouped as facets. Similarly, a box has six facets (though each facet could be divided into many triangles!). Another way of thinking about it: a facet is a group of triangles that could be replaced by a planar polygon.

Now, back to your original question: how to find the boundary? The answer is to keep all edges that belong to only one triangle. If an unordered list of edges is enough for you, you can do it simply with:

unique_edges = mesh.edges[trimesh.grouping.group_rows(mesh.edges_sorted, require_count=1)]

(see [this GitHub issue](https://github.com/mikedh/trimesh/issues/1060#issuecomment-731441168)). If you want 3D coordinates, consider using [`Trimesh.outline()`](https://trimsh.org/trimesh.base.html#trimesh.base.Trimesh.outline) instead.

If you need an ordered list of vertices, then it's a bit more involved. First of all, this makes sense only if your mesh is a manifold (no edge can belong to more than two triangles). Then, as explained in [this answer](https://stackoverflow.com/questions/14108553/get-border-edges-of-mesh-in-winding-order), after getting the list of boundary edges you need to traverse them in order. Here is a function that can do so:

```python
def boundary(mesh, close_paths=True):
    # Set of all edges and of boundary edges (those that appear only once).
    edge_set = set()
    boundary_edges = set()

    # Iterate over all edges, as tuples in the form (i, j) (sorted with i < j to remove ambiguities).
    # For each edge, three cases are possible:
    # 1. The edge has never been visited before. In this case, we can add it to the edge set and as a boundary
    #    candidate as well.
    # 2. The edge had already been visited once. We want to keep it into the set of all edges but remove it from the
    #    boundary set.
    # 3. The edge had already been visited at least twice. This is generally an indication that there is an issue with
    #    the mesh. More precisely, it is not a manifold, and boundaries are not closed-loops.
    for e in map(tuple, mesh.edges_sorted):
        if e not in edge_set:
            edge_set.add(e)
            boundary_edges.add(e)
        elif e in boundary_edges:
            boundary_edges.remove(e)
        else:
            raise RuntimeError(f"The mesh is not a manifold: edge {e} appears more than twice.")

    # Given all boundary vertices, we create a simple dictionary that tells who are their neighbours.
    neighbours = defaultdict(lambda: [])
    for v1, v2 in boundary_edges:
        neighbours[v1].append(v2)
        neighbours[v2].append(v1)

    # We now look for all boundary paths by "extracting" one loop at a time. After obtaining a path, we remove its edges
    # from the "boundary_edges" set. The algorithm terminates when all edges have been used.
    boundary_paths = []

    while len(boundary_edges) > 0:
        # Given the set of remaining boundary edges, get one of them and use it to start the current boundary path.
        # In the sequel, v_previous and v_current represent the edge that we are currently processing.
        v_previous, v_current = next(iter(boundary_edges))
        boundary_vertices = [v_previous]

        # Keep iterating until we close the current boundary curve (the "next" vertex is the same as the first one).
        while v_current != boundary_vertices[0]:
            # We grow the path by adding the vertex "v_current".
            boundary_vertices.append(v_current)

            # We now check which is the next vertex to visit.
            v1, v2 = neighbours[v_current]
            if v1 != v_previous:
                v_current, v_previous = v1, v_current
            elif v2 != v_previous:
                v_current, v_previous = v2, v_current
            else:
                # This line should be un-reachable. I am keeping it only to detect bugs in case I made a mistake when
                # designing the algorithm.
                raise RuntimeError(f"Next vertices to visit ({v1=}, {v2=}) are both equal to {v_previous=}.")

        # Close the path (by repeating the first vertex) if needed.
        if close_paths:
            boundary_vertices.append(boundary_vertices[0])

        # "Convert" the vertices from indices to actual Cartesian coordinates.
        boundary_paths.append(mesh.vertices[boundary_vertices])

        # Remove all boundary edges that were added to the last path.
        boundary_edges = set(e for e in boundary_edges if e[0] not in boundary_vertices)

    # Return the list of boundary paths.
    return boundary_paths

Note that it returns a list of 3D paths. If you want list of vertices, just change the line boundary_paths.append(mesh.vertices[boundary_vertices]) to boundary_paths.append(boundary_vertices). Also note that if the parameter close_paths is True, the first element of a path is repeated at the end as well to "make it" a closed path.

Finally, there may be ways to do the same that are much more efficient than what I just wrote!

答案2

得分: 0

以下是您要翻译的代码部分：

unique_edges = mesh.edges[trimesh.grouping.group_rows(mesh.edges_sorted, require_count=1)]

def boundary_indices(self):
    """
    获取位于网格边界上的顶点的索引。

    对于每个边界，返回边界索引。

    返回：
        boundaries (ndarray)：边界面索引的（边界数）x（变量）数组。
    """
    # 来自StackExchange的建议解决方案：
    # https://stackoverflow.com/questions/76435070/how-do-i-use-python-trimesh-to-get-boundary-vertex-indices/76907565#76907565
    connections = self.trimesh_obj.edges[trimesh.grouping.group_rows(
        self.trimesh_obj.edges_sorted, require_count=1)]

    # 从第一个顶点开始，然后遍历连接的图
    if (len(connections) == 0):
        # 没有边界！
        log.error("网格没有边界边缘！")
        raise ValueError("网格没有边界边缘！")

    # 调整：重新排序第一个条目，最低的在前
    connections[0] = sorted(connections[0])

    # 使用ChatGPT将连接减少为连接顶点的列表
    adj_dict = {}
    for conn in connections:
        for vertex in conn:
            adj_dict.setdefault(vertex, []).extend(c for c in conn if c != vertex)

    groups = []
    visited = set()

    def dfs(vertex, group):
        group.append(vertex)
        visited.add(vertex)
        for conn_vertex in adj_dict[vertex]:
            if conn_vertex not in visited:
                dfs(conn_vertex, group)

    for vertex in adj_dict:
        if vertex in visited:
            continue
        group = []
        dfs(vertex, group)
        groups.append(group)

    # 转换为numpy数组
    boundaries = np.empty((len(groups)), dtype=object)
    for index, boundary in enumerate(groups):
        # 通过将第一个元素添加到末尾来关闭边界
        boundary.append(boundary[0])
        new_array = np.asarray(boundary, dtype=int)
        boundaries[index] = new_array

    return boundaries

如果您需要进一步的翻译或有其他问题，请告诉我。

unique_edges = mesh.edges[trimesh.grouping.group_rows(mesh.edges_sorted, require_count=1)]

def boundary_indices(self):
"""
Get the indices of vertices that are on the boundaries of the mesh.
For each of n boundaries, return the boundary indices.
Returns:
boundaries (ndarray): An (number of boundaries) x (variable) array of boundary face indices.
"""
# Proposed solution from StackExchange:
# https://stackoverflow.com/questions/76435070/how-do-i-use-python-trimesh-to-get-boundary-vertex-indices/76907565#76907565
connections = self.trimesh_obj.edges[trimesh.grouping.group_rows(
self.trimesh_obj.edges_sorted, require_count=1)]
# Start with the first vertex and then walk the graph of connections
if (len(connections) == 0):
# No boundaries!
log.error("Mesh has no boundary edges!")
raise ValueError("Mesh has no boundary edges!")
# Tweak: Re-order the first entry, lowest first
connections[0] = sorted(connections[0])
# Use ChatGPT to reduce connections to lists of connected vertices
adj_dict = {}
for conn in connections:
for vertex in conn:
adj_dict.setdefault(vertex, []).extend(c for c in conn if c != vertex)
groups = []
visited = set()
def dfs(vertex, group):
group.append(vertex)
visited.add(vertex)
for conn_vertex in adj_dict[vertex]:
if conn_vertex not in visited:
dfs(conn_vertex, group)
for vertex in adj_dict:
if vertex in visited:
continue
group = []
dfs(vertex, group)
groups.append(group)
# Convert to numpy arrays
boundaries = np.empty((len(groups)), dtype=object)
for index, boundary in enumerate(groups):
# Close the boundary by add the first element to the end
boundary.append(boundary[0])
new_array = np.asarray(boundary, dtype=int)
boundaries[index] = new_array
return boundaries