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

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

DEPRECATED: use trimesh.graph.smooth_shade(mesh, …)

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]