trimesh.graph module

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, scipy.sparse.csgraph, or graph_tool backends.

Functions

connected_component_labels(edges[, node_count])

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

connected_components(edges[, min_len, …])

Find groups of connected nodes from an edge list.

edges_to_coo(edges[, count, data])

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

face_adjacency([faces, mesh, return_edges])

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

face_adjacency_radius(mesh)

Compute an approximate radius between adjacent faces.

face_adjacency_unshared(mesh)

Return the vertex index of the two vertices not in the shared

facets(mesh[, engine])

Find the list of parallel adjacent faces.

fill_traversals(traversals, edges[, edges_hash])

Convert a traversal of a list of edges into a sequence of

graph_to_svg(graph)

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

is_watertight(edges[, edges_sorted])

param edges

List of vertex indices

multigraph_collect(G, traversal[, attrib])

Given a MultiDiGraph traversal, collect attributes along it.

multigraph_paths(G, source[, cutoff])

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

shared_edges(faces_a, faces_b)

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

smoothed(mesh, angle[, facet_minlen])

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(mesh[, only_watertight, adjacency, engine])

Split a mesh into multiple meshes from face connectivity.

split_traversal(traversal, edges[, edges_hash])

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

traversals(edges[, mode])

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

vertex_adjacency_graph(mesh)

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

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’, ‘graphtool’)

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

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.facets(mesh, engine=None)

Find the list of parallel adjacent faces.

Parameters
  • mesh (trimesh.Trimesh) –

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

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.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.smoothed(mesh, angle, facet_minlen=4)

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) – Angle in radians: adjacent faces below this angle will be smoothed

  • facet_minlen (None or int) – If specified will specially group facets with more faces

Returns

smooth – Geometry with disconnected face patches

Return type

trimesh.Trimesh

trimesh.graph.split(mesh, only_watertight=True, adjacency=None, engine=None)

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, '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]