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.
Functions:

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

Find groups of connected nodes from an edge list. 

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

Returns an (n, 2) list of face indices. 

Compute an approximate radius between adjacent faces. 

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

Given a list of faces (n,3), return a list of edges (n*3,2) 

Find the list of parallel adjacent faces. 

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 

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



Given a MultiDiGraph traversal, collect attributes along it. 

For a networkx MultiDiGraph, find all paths from a source node to leaf nodes. 

Find the neighbors for each node in an edgelist graph. 

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

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

Split a mesh into multiple meshes from face connectivity. 

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

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

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

A sparse matrix in COOrdinate format. 

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: >>> 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
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.
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 : rewrite 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
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.
smoothed
(mesh, angle=None, facet_minarea=15)¶ 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.graph.
split
(mesh, only_watertight=True, adjacency=None, engine=None, **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

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]