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
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)
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
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=10)
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]