trimesh.graph

graph.py

Deal with graph operations. Primarily deal with graphs in (n, 2) edge list form, and abstract the backend graph library being used.

Currently uses networkx or scipy.sparse.csgraph backend.

trimesh.graph.connected_component_labels(edges, node_count=None)

Label graph nodes from an edge list, using scipy.sparse.csgraph

Parameters:

  • edges ((n, 2) int) – Edges of a graph

  • node_count (int, or None) – The largest node in the graph.

Returns:

labels – Component labels for each node

Return type:

(node_count,) int

trimesh.graph.connected_components(edges, min_len=1, nodes=None, engine=None)

Find groups of connected nodes from an edge list.

Parameters:

  • edges ((n, 2) int) – Edges between nodes

  • nodes ((m, ) int or None) – List of nodes that exist

  • min_len (int) – Minimum length of a component group to return

  • engine (str or None) – Which graph engine to use (None for automatic): (None, ‘networkx’, ‘scipy’)

Returns:

components – Nodes which are connected

Return type:

(n,) sequence of (*,) int

trimesh.graph.edges_to_coo(edges, count=None, data=None)

Given an edge list, return a boolean scipy.sparse.coo_matrix representing the edges in matrix form.

Parameters:

  • edges ((n, 2) int) – Edges of a graph

  • count (int) – The total number of nodes in the graph if None: count = edges.max() + 1

  • data ((n,) any) – Assign data to each edge, if None will be bool True for each specified edge

Returns:

matrix – Sparse COO

Return type:

(count, count) scipy.sparse.coo_matrix

trimesh.graph.face_adjacency(faces=None, mesh=None, return_edges=False)

Returns an (n, 2) list of face indices. Each pair of faces in the list shares an edge, making them adjacent.

Parameters:

  • faces ((n, 3) int, or None) – Vertex indices representing triangles

  • mesh (Trimesh object) – If passed will used cached edges instead of generating from faces

  • return_edges (bool) – Return the edges shared by adjacent faces

Returns:

  • adjacency ((m, 2) int) – Indexes of faces that are adjacent

  • edges ((m, 2) int) – Only returned if return_edges is True Indexes of vertices which make up the edges shared by the adjacent faces

Examples

This is useful for lots of things such as finding face- connected components: `python >>> graph = nx.Graph() >>> graph.add_edges_from(mesh.face_adjacency) >>> groups = nx.connected_components(graph_connected) `

trimesh.graph.face_adjacency_radius(mesh)

Compute an approximate radius between adjacent faces.

Parameters:

mesh (trimesh.Trimesh)

Returns:

  • radii ((len(self.face_adjacency),) float) – Approximate radius between faces Parallel faces will have a value of np.inf

  • span ((len(self.face_adjacency),) float) – Perpendicular projection distance of two unshared vertices onto the shared edge

trimesh.graph.face_adjacency_unshared(mesh)

Return the vertex index of the two vertices not in the shared edge between two adjacent faces

Parameters:

mesh (Trimesh object) – Input mesh

Returns:

vid_unshared – Indexes of mesh.vertices for degenerate faces without exactly one unshared vertex per face it will be -1

Return type:

(len(mesh.face_adjacency), 2) int

trimesh.graph.face_neighborhood(mesh) → ndarray[tuple[int, ...], dtype[int64]]

Find faces that share a vertex i.e. ‘neighbors’ faces. Relies on the fact that an adjacency matrix at a power p contains the number of paths of length p connecting two nodes. Here we take the bipartite graph from mesh.faces_sparse to the power 2. The non-zeros are the faces connected by one vertex.

Returns:

neighborhood – Pairs of faces which share a vertex

Return type:

(n, 2) int

trimesh.graph.facets(mesh, engine=None, facet_threshold: float | floating | int | integer | unsignedinteger | None = None)

Find the list of parallel adjacent faces.

Parameters:

  • mesh (trimesh.Trimesh)

  • engine (str) – Which graph engine to use: (‘scipy’, ‘networkx’)

  • facet_threshold (float) – Threshold for two facets to be considered coplanar

Returns:

facets – Groups of face indexes of parallel adjacent faces.

Return type:

sequence of (n,) int

trimesh.graph.fill_traversals(traversals: Sequence, edges: Buffer | _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes]) → Sequence | ndarray[tuple[int, ...], dtype[_ScalarType_co]]

Convert a traversal of a list of edges into a sequence of traversals where every pair of consecutive node indexes is an edge in a passed edge list

Parameters:

  • traversals (sequence of (m,) int) – Node indexes of traversals of a graph

  • edges ((n, 2) int) – Pairs of connected node indexes

Returns:

splits – Node indexes of connected traversals

Return type:

sequence of (p,) int

trimesh.graph.graph_to_svg(graph)

Turn a networkx graph into an SVG string using graphviz dot.

Parameters:

graph (networkx graph)

Returns:

svg

Return type:

string, pictoral layout in SVG format

trimesh.graph.is_watertight(edges, edges_sorted=None)
Parameters:

  • edges ((n, 2) int) – List of vertex indices

  • edges_sorted ((n, 2) int) – Pass vertex indices sorted on axis 1 as a speedup

Returns:

  • watertight (boolean) – Whether every edge is shared by an even number of faces

  • winding (boolean) – Whether every shared edge is reversed

trimesh.graph.multigraph_collect(G, traversal, attrib=None)

Given a MultiDiGraph traversal, collect attributes along it.

Parameters:

  • G (networkx.MultiDiGraph)

  • traversal

  • attrib (dict key, name to collect. If None, will return all)

Returns:

collected

Return type:

(len(traversal) - 1) list of attributes

trimesh.graph.multigraph_paths(G, source, cutoff=None)

For a networkx MultiDiGraph, find all paths from a source node to leaf nodes. This function returns edge instance numbers in addition to nodes, unlike networkx.all_simple_paths.

Parameters:

  • G (networkx.MultiDiGraph) – Graph to evaluate

  • source (hashable) – Node to start traversal at

  • cutoff (int) – Number of nodes to visit If None will visit all nodes

Returns:

traversals – Traversals of the multigraph

Return type:

(n,) list of [(node, edge instance index), ] paths

trimesh.graph.neighbors(edges, max_index=None, directed=False)

Find the neighbors for each node in an edgelist graph.

TODO : re-write this with sparse matrix operations

Parameters:

  • edges ((n, 2) int) – Connected nodes

  • directed (bool) – If True, only connect edges in one direction

Returns:

neighbors – Vertex index corresponds to set of other vertex indices

Return type:

sequence

trimesh.graph.shared_edges(faces_a, faces_b)

Given two sets of faces, find the edges which are in both sets.

Parameters:

  • faces_a ((n, 3) int) – Array of faces

  • faces_b ((m, 3) int) – Array of faces

Returns:

shared – Edges shared between faces

Return type:

(p, 2) int

trimesh.graph.smooth_shade(mesh, angle: float | floating | int | integer | unsignedinteger | None = None, facet_minarea: float | floating | int | integer | unsignedinteger | None = 10.0)

Return a non-watertight version of the mesh which will render nicely with smooth shading by disconnecting faces at sharp angles to each other.

Parameters:

  • mesh (trimesh.Trimesh) – Source geometry

  • angle (float or None) – Angle in radians face pairs with angles smaller than this will appear smoothed

  • facet_minarea (float or None) – Minimum area fraction to consider IE for facets_minarea=25 only facets larger than mesh.area / 25 will be considered.

Returns:

smooth – Geometry with disconnected face patches

Return type:

trimesh.Trimesh

trimesh.graph.split(mesh, only_watertight=True, adjacency=None, engine=None, **kwargs) → list

Split a mesh into multiple meshes from face connectivity.

If only_watertight is true it will only return watertight meshes and will attempt to repair single triangle or quad holes.

Parameters:

  • mesh (trimesh.Trimesh)

  • only_watertight (bool) – Only return watertight components

  • adjacency ((n, 2) int) – Face adjacency to override full mesh

  • engine (str or None) – Which graph engine to use

Returns:

meshes – Results of splitting

Return type:

(m,) trimesh.Trimesh

trimesh.graph.traversals(edges, mode='bfs')

Given an edge list generate a sequence of ordered depth first search traversals using scipy.csgraph routines.

Parameters:

  • edges ((n, 2) int) – Undirected edges of a graph

  • mode (str) – Traversal type, ‘bfs’ or ‘dfs’

Returns:

traversals – Ordered DFS or BFS traversals of the graph.

Return type:

(m,) sequence of (p,) int

trimesh.graph.vertex_adjacency_graph(mesh)

Returns a networkx graph representing the vertices and their connections in the mesh.

Parameters:

mesh (Trimesh object)

Returns:

graph – Graph representing vertices and edges between them where vertices are nodes and edges are edges

Return type:

networkx.Graph

Examples

This is useful for getting nearby vertices for a given vertex, potentially for some simple smoothing techniques. >>> graph = mesh.vertex_adjacency_graph >>> graph.neighbors(0) > [1, 3, 4]