# 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

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) ````

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

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:

trimesh.graph.face_neighborhood(mesh)#

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)#

Find the list of parallel adjacent faces.

Parameters:
• mesh (trimesh.Trimesh) –

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

Returns:

facets – Groups of face indexes of parallel adjacent faces.

Return type:

sequence of (n,) int

trimesh.graph.fill_traversals(traversals, edges, edges_hash=None)#

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

• edges_hash (None, or (n,) int) – Edges sorted along axis 1 then hashed using grouping.hashable_rows

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 | None = None, facet_minarea: float | 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.smoothed(*args, **kwargs)#

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.split_traversal(traversal, edges, edges_hash=None)#

Given a traversal as a list of nodes, split the traversal if a sequential index pair is not in the given edges.

Parameters:
• edges ((n, 2) int) – Graph edge indexes

• traversal ((m,) int) – Traversal through edges

• edge_hash ((n,)) – Edges sorted on axis=1 and passed to grouping.hashable_rows

Returns:

split

Return type:

sequence of (p,) int

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

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]