Coverage for trimesh/graph.py: 90%
296 statements
« prev ^ index » next coverage.py v7.14.1, created at 2026-06-24 04:40 +0000
1"""
2graph.py
3-------------
5Deal with graph operations. Primarily deal with graphs in (n, 2)
6edge list form, and abstract the backend graph library being used.
8Currently uses networkx or scipy.sparse.csgraph backend.
9"""
11import collections
13import numpy as np
15from . import exceptions, grouping, util
16from .constants import log, tol
17from .geometry import faces_to_edges
18from .typed import (
19 ArrayLike,
20 GraphEngineType,
21 Integer,
22 NDArray,
23 Number,
24 Sequence,
25 int64,
26)
28try:
29 from scipy.sparse import coo_matrix, csgraph
30 from scipy.spatial import cKDTree
31except BaseException as E:
32 # re-raise exception when used
33 cKDTree = exceptions.ExceptionWrapper(E)
34 csgraph = exceptions.ExceptionWrapper(E)
35 coo_matrix = exceptions.ExceptionWrapper(E)
37try:
38 import networkx as nx
39except BaseException as E:
40 # create a dummy module which will raise the ImportError
41 # or other exception only when someone tries to use networkx
42 nx = exceptions.ExceptionWrapper(E)
45def face_adjacency(faces=None, mesh=None, return_edges=False):
46 """
47 Returns an (n, 2) list of face indices.
48 Each pair of faces in the list shares an edge, making them adjacent.
51 Parameters
52 -----------
53 faces : (n, 3) int, or None
54 Vertex indices representing triangles
55 mesh : Trimesh object
56 If passed will used cached edges
57 instead of generating from faces
58 return_edges : bool
59 Return the edges shared by adjacent faces
61 Returns
62 ----------
63 adjacency : (m, 2) int
64 Indexes of faces that are adjacent
65 edges: (m, 2) int
66 Only returned if return_edges is True
67 Indexes of vertices which make up the
68 edges shared by the adjacent faces
70 Examples
71 ----------
72 This is useful for lots of things such as finding
73 face- connected components:
74 ```python
75 >>> graph = nx.Graph()
76 >>> graph.add_edges_from(mesh.face_adjacency)
77 >>> groups = nx.connected_components(graph_connected)
78 ```
79 """
81 if mesh is None:
82 # first generate the list of edges for the current faces
83 # also return the index for which face the edge is from
84 edges, edges_face = faces_to_edges(faces, return_index=True)
85 # make sure edge rows are sorted
86 edges.sort(axis=1)
87 else:
88 # if passed a mesh, used the cached values
89 edges = mesh.edges_sorted
90 edges_face = mesh.edges_face
92 # this will return the indices for duplicate edges
93 # every edge appears twice in a well constructed mesh
94 # so for every row in edge_idx:
95 # edges[edge_idx[*][0]] == edges[edge_idx[*][1]]
96 # in this call to group rows we discard edges which
97 # don't occur twice
98 edge_groups = grouping.group_rows(edges, require_count=2)
100 if len(edge_groups) == 0:
101 log.debug("No adjacent faces detected! Did you merge vertices?")
103 # the pairs of all adjacent faces
104 # so for every row in face_idx, self.faces[face_idx[*][0]] and
105 # self.faces[face_idx[*][1]] will share an edge
106 adjacency = edges_face[edge_groups]
108 # degenerate faces may appear in adjacency as the same value
109 nondegenerate = adjacency[:, 0] != adjacency[:, 1]
110 adjacency = adjacency[nondegenerate]
112 # sort pairs in-place so we can search for indexes with ordered pairs
113 adjacency.sort(axis=1)
115 if return_edges:
116 adjacency_edges = edges[edge_groups[:, 0][nondegenerate]]
117 assert len(adjacency_edges) == len(adjacency)
118 return adjacency, adjacency_edges
120 return adjacency
123def face_neighborhood(mesh) -> NDArray[int64]:
124 """
125 Find faces that share a vertex i.e. 'neighbors' faces.
126 Relies on the fact that an adjacency matrix at a power p
127 contains the number of paths of length p connecting two nodes.
128 Here we take the bipartite graph from mesh.faces_sparse to the power 2.
129 The non-zeros are the faces connected by one vertex.
131 Returns
132 ----------
133 neighborhood : (n, 2) int
134 Pairs of faces which share a vertex
135 """
137 VT = mesh.faces_sparse
138 TT = VT.T * VT
139 TT.setdiag(0)
140 TT.eliminate_zeros()
141 TT = TT.tocoo()
142 neighborhood = np.concatenate(
143 (TT.row[:, None], TT.col[:, None]), axis=-1, dtype=np.int64
144 )
145 return neighborhood
148def face_adjacency_unshared(mesh):
149 """
150 Return the vertex index of the two vertices not in the shared
151 edge between two adjacent faces
153 Parameters
154 ----------
155 mesh : Trimesh object
156 Input mesh
158 Returns
159 -----------
160 vid_unshared : (len(mesh.face_adjacency), 2) int
161 Indexes of mesh.vertices
162 for degenerate faces without exactly
163 one unshared vertex per face it will be -1
164 """
166 # the non- shared vertex index is the same shape
167 # as face_adjacency holding vertex indices vs face indices
168 vid_unshared = np.zeros_like(mesh.face_adjacency, dtype=np.int64) - 1
169 # get the shared edges between adjacent faces
170 edges = mesh.face_adjacency_edges
172 # loop through the two columns of face adjacency
173 for i, fid in enumerate(mesh.face_adjacency.T):
174 # faces from the current column of face adjacency
175 faces = mesh.faces[fid]
176 # should have one True per row of (3,)
177 # index of vertex not included in shared edge
178 unshared = np.logical_not(
179 np.logical_or(
180 faces == edges[:, 0].reshape((-1, 1)),
181 faces == edges[:, 1].reshape((-1, 1)),
182 )
183 )
184 # each row should have exactly one uncontained verted
185 row_ok = unshared.sum(axis=1) == 1
186 # any degenerate row should be ignored
187 unshared[~row_ok, :] = False
188 # set the
189 vid_unshared[row_ok, i] = faces[unshared]
191 return vid_unshared
194def face_adjacency_radius(mesh):
195 """
196 Compute an approximate radius between adjacent faces.
198 Parameters
199 --------------
200 mesh : trimesh.Trimesh
202 Returns
203 -------------
204 radii : (len(self.face_adjacency),) float
205 Approximate radius between faces
206 Parallel faces will have a value of np.inf
207 span : (len(self.face_adjacency),) float
208 Perpendicular projection distance of two
209 unshared vertices onto the shared edge
210 """
212 # solve for the radius of the adjacent faces
213 # distance
214 # R = ---------------
215 # 2 * sin(theta)
216 nonzero = mesh.face_adjacency_angles > np.radians(0.01)
217 denominator = np.abs(2.0 * np.sin(mesh.face_adjacency_angles[nonzero]))
219 # consider the distance between the non- shared vertices of the
220 # face adjacency pair as the key distance
221 point_pairs = mesh.vertices[mesh.face_adjacency_unshared]
222 vectors = np.diff(point_pairs, axis=1).reshape((-1, 3))
224 # the vertex indices of the shared edge for the adjacency pairx
225 edges = mesh.face_adjacency_edges
226 # unit vector along shared the edge
227 edges_vec = util.unitize(np.diff(mesh.vertices[edges], axis=1).reshape((-1, 3)))
229 # the vector of the perpendicular projection to the shared edge
230 perp = np.subtract(
231 vectors, (util.diagonal_dot(vectors, edges_vec).reshape((-1, 1)) * edges_vec)
232 )
233 # the length of the perpendicular projection
234 span = util.row_norm(perp)
236 # complete the values for non- infinite radii
237 radii = np.ones(len(mesh.face_adjacency)) * np.inf
238 radii[nonzero] = span[nonzero] / denominator
240 return radii, span
243def vertex_adjacency_graph(mesh):
244 """
245 Returns a networkx graph representing the vertices and
246 their connections in the mesh.
248 Parameters
249 ----------
250 mesh : Trimesh object
252 Returns
253 ---------
254 graph : networkx.Graph
255 Graph representing vertices and edges between
256 them where vertices are nodes and edges are edges
258 Examples
259 ----------
260 This is useful for getting nearby vertices for a given vertex,
261 potentially for some simple smoothing techniques.
262 >>> graph = mesh.vertex_adjacency_graph
263 >>> graph.neighbors(0)
264 > [1, 3, 4]
265 """
266 g = nx.Graph()
267 g.add_edges_from(mesh.edges_unique)
268 return g
271def shared_edges(faces_a, faces_b):
272 """
273 Given two sets of faces, find the edges which are in both sets.
275 Parameters
276 ---------
277 faces_a : (n, 3) int
278 Array of faces
279 faces_b : (m, 3) int
280 Array of faces
282 Returns
283 ---------
284 shared : (p, 2) int
285 Edges shared between faces
286 """
287 e_a = np.sort(faces_to_edges(faces_a), axis=1)
288 e_b = np.sort(faces_to_edges(faces_b), axis=1)
289 shared = grouping.boolean_rows(e_a, e_b, operation=np.intersect1d)
290 return shared
293def facets(mesh, engine: GraphEngineType = None, facet_threshold: Number | None = None):
294 """
295 Find the list of parallel adjacent faces.
297 Parameters
298 -----------
299 mesh : trimesh.Trimesh
300 engine
301 Which graph engine to use
302 facet_threshold : float
303 Threshold for two facets to be considered coplanar
305 Returns
306 ---------
307 facets : sequence of (n,) int
308 Groups of face indexes of
309 parallel adjacent faces.
310 """
311 if facet_threshold is None:
312 facet_threshold = tol.facet_threshold
313 # what is the radius of a circle that passes through the perpendicular
314 # projection of the vector between the two non- shared vertices
315 # onto the shared edge, with the face normal from the two adjacent faces
316 radii = mesh.face_adjacency_radius
317 # what is the span perpendicular to the shared edge
318 span = mesh.face_adjacency_span
319 # a very arbitrary formula for declaring two adjacent faces
320 # parallel in a way that is hopefully (and anecdotally) robust
321 # to numeric error
322 # a common failure mode is two faces that are very narrow with a slight
323 # angle between them, so here we divide by the perpendicular span
324 # to penalize very narrow faces, and then square it just for fun
325 parallel = np.ones(len(radii), dtype=bool)
326 # if span is zero we know faces are small/parallel
327 nonzero = np.abs(span) > tol.zero
328 # faces with a radii/span ratio larger than a threshold pass
329 parallel[nonzero] = (radii[nonzero] / span[nonzero]) ** 2 > facet_threshold
331 # run connected components on the parallel faces to group them
332 components = connected_components(
333 mesh.face_adjacency[parallel],
334 nodes=np.arange(len(mesh.faces)),
335 min_len=2,
336 engine=engine,
337 )
339 return components
342def split(
343 mesh,
344 only_watertight: bool = True,
345 repair: bool = True,
346 adjacency: ArrayLike | None = None,
347 engine: GraphEngineType = None,
348 **kwargs,
349) -> list:
350 """
351 Split a mesh into multiple meshes from face
352 connectivity.
354 If only_watertight is true it will only return
355 watertight meshes and will attempt to repair
356 single triangle or quad holes.
358 Parameters
359 ----------
360 mesh : trimesh.Trimesh
361 The source multibody mesh to split
362 only_watertight
363 Only return watertight components and discard
364 any connected component that isn't fully watertight.
365 repair
366 If set try to fill small holes in a mesh, before the
367 discard step in `only_watertight.
368 adjacency : (n, 2) int
369 If passed will be used instead of `mesh.face_adjacency`
370 engine
371 Which graph engine to use for the connected components.
373 Returns
374 ----------
375 meshes : (m,) trimesh.Trimesh
376 Results of splitting based on parameters.
377 """
378 if adjacency is None:
379 adjacency = mesh.face_adjacency
381 if only_watertight:
382 # the smallest watertight mesh has 4 faces
383 min_len = 4
384 else:
385 # allow any size of connected component
386 min_len = 1
388 components = connected_components(
389 edges=adjacency, nodes=np.arange(len(mesh.faces)), min_len=min_len, engine=engine
390 )
391 return mesh.submesh(
392 components, only_watertight=only_watertight, repair=repair, **kwargs
393 )
396def connected_components(
397 edges, min_len: Integer = 1, nodes=None, engine: GraphEngineType = None
398):
399 """
400 Find groups of connected nodes from an edge list.
402 Parameters
403 -----------
404 edges : (n, 2) int
405 Edges between nodes
406 nodes : (m, ) int or None
407 List of nodes that exist
408 min_len : int
409 Minimum length of a component group to return
410 engine : str or None
411 Which graph engine to use (None for automatic):
412 (None, 'networkx', 'scipy')
415 Returns
416 -----------
417 components : (n,) sequence of (*,) int
418 Nodes which are connected
419 """
421 def components_networkx():
422 """
423 Find connected components using networkx
424 """
425 graph = nx.from_edgelist(edges)
426 # make sure every face has a node, so single triangles
427 # aren't discarded (as they aren't adjacent to anything)
428 if min_len <= 1:
429 graph.add_nodes_from(nodes)
430 return [list(i) for i in nx.connected_components(graph)]
432 def components_csgraph():
433 """
434 Find connected components using scipy.sparse.csgraph
435 """
436 # label each node
437 labels = connected_component_labels(edges, node_count=node_count)
439 # we have to remove results that contain nodes outside
440 # of the specified node set and reindex
441 contained = np.zeros(node_count, dtype=bool)
442 contained[nodes] = True
443 index = np.arange(node_count, dtype=np.int64)[contained]
444 components = grouping.group(labels[contained], min_len=min_len)
445 return [index[c] for c in components]
447 return components
449 # check input edges
450 edges = np.asanyarray(edges, dtype=np.int64)
451 # if no nodes were specified just use unique
452 if nodes is None:
453 nodes = np.unique(edges)
455 # exit early if we have no nodes
456 if len(nodes) == 0:
457 return []
458 elif len(edges) == 0:
459 if min_len <= 1:
460 return np.reshape(nodes, (-1, 1)).tolist()
461 else:
462 return []
464 if not util.is_shape(edges, (-1, 2)):
465 raise ValueError("edges must be (n, 2)!")
467 # find the maximum index referenced in either nodes or edges
468 counts = [0]
469 if len(edges) > 0:
470 counts.append(edges.max())
471 if len(nodes) > 0:
472 counts.append(nodes.max())
473 node_count = np.max(counts) + 1
475 # remove edges that don't have both nodes in the node set
476 mask = np.zeros(node_count, dtype=bool)
477 mask[nodes] = True
478 edges_ok = mask[edges].all(axis=1)
479 edges = edges[edges_ok]
481 # networkx is pure python and is usually 5-10x slower than scipy
482 engines = collections.OrderedDict(
483 (("scipy", components_csgraph), ("networkx", components_networkx))
484 )
486 # if a graph engine has explicitly been requested use it
487 if engine in engines:
488 return engines[engine]()
490 # otherwise, go through our ordered list of graph engines
491 # until we get to one that has actually been installed
492 for function in engines.values():
493 try:
494 return function()
495 # will be raised if the library didn't import correctly above
496 except BaseException:
497 continue
498 raise ImportError("no graph engines available!")
501def connected_component_labels(edges, node_count=None):
502 """
503 Label graph nodes from an edge list, using scipy.sparse.csgraph
505 Parameters
506 -----------
507 edges : (n, 2) int
508 Edges of a graph
509 node_count : int, or None
510 The largest node in the graph.
512 Returns
513 ----------
514 labels : (node_count,) int
515 Component labels for each node
516 """
517 matrix = edges_to_coo(edges, node_count)
518 _body_count, labels = csgraph.connected_components(matrix, directed=False)
520 if node_count is not None:
521 assert len(labels) == node_count
523 return labels
526def _split_traversal(traversal: NDArray, edges_tree) -> list[NDArray]:
527 """
528 Given a traversal as a list of nodes split the traversal
529 if a sequential index pair is not in the given edges.
530 Useful since the implementation of DFS we're using will
531 happily return disconnected values in a flat traversal.
533 Parameters
534 --------------
535 traversal : (m,) int
536 Traversal through edges
537 edges_tree : cKDTree
538 A way to reconstruct original edge indices from
539 sorted (n, 2) edge values. This is a slight misuse of a
540 kdtree since one could just hash the tuples of the integer
541 edges, but that isn't possible with numpy arrays easily
542 and this allows a vectorized reconstruction.
544 Returns
545 ---------------
546 split : sequence of (p,) int
547 Traversals split into only connected paths.
548 """
549 # turn the (n,) traversal into (n-1, 2) edges
550 # save the original order of the edges for reconstruction
551 trav_edge = np.column_stack((traversal[:-1], traversal[1:]))
553 # check to see if the traversal edges exists in the original edges
554 # the tree is holding the sorted edges so query after sorting
555 exists = edges_tree.query(np.sort(trav_edge, axis=1))[0] < 1e-10
557 if exists.all():
558 split = [traversal]
559 else:
560 # contiguous groups of edges
561 blocks = grouping.blocks(exists, min_len=1, only_nonzero=True)
562 split = [
563 np.concatenate([trav_edge[:, 0][b], trav_edge[b[-1]][1:]]) for b in blocks
564 ]
566 # a traversal may be effectively closed so check
567 # to see if we need to add on the first index to the end
568 needs_close = np.array(
569 [
570 len(s) > 2
571 and s[0] != s[-1]
572 and edges_tree.query(sorted([s[0], s[-1]]))[0] < 1e-10
573 for s in split
574 ]
575 )
577 if needs_close.any():
578 for i in np.nonzero(needs_close)[0]:
579 split[i] = np.concatenate([split[i], split[i][:1]])
581 if tol.strict:
582 for s in split:
583 check_edge = np.sort(np.column_stack((s[:-1], s[1:])), axis=1)
584 assert (edges_tree.query(check_edge)[0] < 1e-10).all()
586 return split
589def fill_traversals(traversals: Sequence, edges: ArrayLike) -> Sequence | NDArray:
590 """
591 Convert a traversal of a list of edges into a sequence of
592 traversals where every pair of consecutive node indexes
593 is an edge in a passed edge list
595 Parameters
596 -------------
597 traversals : sequence of (m,) int
598 Node indexes of traversals of a graph
599 edges : (n, 2) int
600 Pairs of connected node indexes
602 Returns
603 --------------
604 splits : sequence of (p,) int
605 Node indexes of connected traversals
606 """
607 # make sure edges are correct type
608 edges = np.sort(edges, axis=1)
609 edges_tree = cKDTree(edges)
611 # if there are no traversals just return edges
612 if len(traversals) == 0:
613 return edges.copy()
615 splits = []
616 for nodes in traversals:
617 # split traversals to remove edges that don't actually exist
618 splits.extend(_split_traversal(traversal=nodes, edges_tree=edges_tree))
620 # turn the split traversals back into (n, 2) edges
621 included = util.vstack_empty([np.column_stack((i[:-1], i[1:])) for i in splits])
622 if len(included) > 0:
623 # sort included edges in place
624 included.sort(axis=1)
625 # make sure any edges not included in split traversals
626 # are just added as a length 2 traversal
627 splits.extend(grouping.boolean_rows(edges, included, operation=np.setdiff1d))
628 else:
629 # no edges were included, so our filled traversal
630 # is just the original edges copied over
631 splits = edges.copy()
633 return splits
636def traversals(edges, mode="bfs"):
637 """
638 Given an edge list generate a sequence of ordered depth
639 first search traversals using scipy.csgraph routines.
641 Parameters
642 ------------
643 edges : (n, 2) int
644 Undirected edges of a graph
645 mode : str
646 Traversal type, 'bfs' or 'dfs'
648 Returns
649 -----------
650 traversals : (m,) sequence of (p,) int
651 Ordered DFS or BFS traversals of the graph.
652 """
653 edges = np.array(edges, dtype=np.int64)
654 if len(edges) == 0:
655 return []
656 elif not util.is_shape(edges, (-1, 2)):
657 raise ValueError("edges are not (n, 2)!")
659 # pick the traversal method
660 mode = str(mode).lower().strip()
661 if mode == "bfs":
662 func = csgraph.breadth_first_order
663 elif mode == "dfs":
664 func = csgraph.depth_first_order
665 else:
666 raise ValueError("traversal mode must be either dfs or bfs")
668 # make sure edges are sorted so we can query
669 # an ordered pair later
670 edges.sort(axis=1)
671 # coo_matrix for csgraph routines
672 graph = edges_to_coo(edges)
674 # get unique nodes AND leaf node info from bincount
675 bincount = np.bincount(edges.ravel())
677 # a leaf node occurs exactly once
678 nodes_leaf = np.nonzero(bincount == 1)[0]
679 # a non-leaf node occurs more than once
680 nodes = np.nonzero(bincount > 1)[0]
682 # collect traversals
683 traversals = []
684 # keep track of which nodes have been visited
685 visited = np.zeros(len(bincount) + 1, dtype=np.bool_)
687 # process leaf nodes first to avoid DFS backtracking
688 # starting DFS from an interior node of an open path causes
689 # backtracking, which produces non-edge consecutive pairs that
690 # fill_traversals then splits a single path into pieces
691 for start in np.concatenate((nodes_leaf, nodes)):
692 if visited[start]:
693 continue
695 # get an (n,) ordered traversal from this start
696 ordered = func(
697 graph, i_start=start, return_predecessors=False, directed=False
698 ).astype(np.int64)
700 # store the traversal and mark all nodes as visited
701 traversals.append(ordered)
702 visited[ordered] = True
704 return traversals
707def edges_to_coo(edges, count=None, data=None):
708 """
709 Given an edge list, return a boolean scipy.sparse.coo_matrix
710 representing the edges in matrix form.
712 Parameters
713 ------------
714 edges : (n, 2) int
715 Edges of a graph
716 count : int
717 The total number of nodes in the graph
718 if None: count = edges.max() + 1
719 data : (n,) any
720 Assign data to each edge, if None will
721 be bool True for each specified edge
723 Returns
724 ------------
725 matrix: (count, count) scipy.sparse.coo_matrix
726 Sparse COO
727 """
728 edges = np.asanyarray(edges, dtype=np.int64)
729 if not (len(edges) == 0 or util.is_shape(edges, (-1, 2))):
730 raise ValueError("edges must be (n, 2)!")
732 # if count isn't specified just set it to largest
733 # value referenced in edges
734 if count is None:
735 count = edges.max() + 1
736 count = int(count)
738 # if no data is specified set every specified edge
739 # to True
740 if data is None:
741 data = np.ones(len(edges), dtype=bool)
743 return coo_matrix((data, edges.T), dtype=data.dtype, shape=(count, count))
746def neighbors(edges, max_index=None, directed=False):
747 """
748 Find the neighbors for each node in an edgelist graph.
750 TODO : re-write this with sparse matrix operations
752 Parameters
753 ------------
754 edges : (n, 2) int
755 Connected nodes
756 directed : bool
757 If True, only connect edges in one direction
759 Returns
760 ---------
761 neighbors : sequence
762 Vertex index corresponds to set of other vertex indices
763 """
764 neighbors = collections.defaultdict(set)
765 if directed:
766 [neighbors[edge[0]].add(edge[1]) for edge in edges]
767 else:
768 [
769 (neighbors[edge[0]].add(edge[1]), neighbors[edge[1]].add(edge[0]))
770 for edge in edges
771 ]
773 if max_index is None:
774 max_index = edges.max() + 1
775 array = [list(neighbors[i]) for i in range(max_index)]
777 return array
780def smooth_shade(mesh, angle: Number | None = None, facet_minarea: Number | None = 10.0):
781 """
782 Return a non-watertight version of the mesh which
783 will render nicely with smooth shading by
784 disconnecting faces at sharp angles to each other.
786 Parameters
787 -----------
788 mesh : trimesh.Trimesh
789 Source geometry
790 angle : float or None
791 Angle in radians face pairs with angles
792 smaller than this will appear smoothed
793 facet_minarea : float or None
794 Minimum area fraction to consider
795 IE for `facets_minarea=25` only facets larger
796 than `mesh.area / 25` will be considered.
798 Returns
799 ---------
800 smooth : trimesh.Trimesh
801 Geometry with disconnected face patches
802 """
803 if angle is None:
804 angle = np.radians(20)
806 # if the mesh has no adjacent faces return a copy
807 if len(mesh.face_adjacency) == 0:
808 return mesh.copy()
810 # face pairs below angle threshold
811 angle_ok = mesh.face_adjacency_angles < angle
812 # subset of face adjacency
813 adjacency = mesh.face_adjacency[angle_ok]
815 # coplanar groups of faces
816 facets = []
817 nodes = None
818 # collect coplanar regions for smoothing
819 if facet_minarea is not None:
820 areas = mesh.area_faces
821 min_area = mesh.area / facet_minarea
822 try:
823 # we can survive not knowing facets
824 # exclude facets with few faces
825 facets = [f for f in mesh.facets if areas[f].sum() > min_area]
826 if len(facets) > 0:
827 # mask for removing adjacency pairs where
828 # one of the faces is contained in a facet
829 mask = np.ones(len(mesh.faces), dtype=bool)
830 mask[np.hstack(facets)] = False
831 # apply the mask to adjacency
832 adjacency = adjacency[mask[adjacency].all(axis=1)]
833 # nodes are no longer every faces
834 nodes = np.unique(adjacency)
835 except BaseException:
836 log.warning("failed to calculate facets", exc_info=True)
837 # run connected components on facet adjacency
838 components = connected_components(adjacency, min_len=2, nodes=nodes)
840 # add back coplanar groups if any exist
841 if len(facets) > 0:
842 components.extend(facets)
844 if len(components) == 0:
845 # if no components for some reason
846 # just return a copy of the original mesh
847 return mesh.copy()
849 # add back any faces that were missed
850 unique = np.unique(np.hstack(components))
851 if len(unique) != len(mesh.faces):
852 # things like single loose faces
853 # or groups below facet_minlen
854 broke = np.setdiff1d(np.arange(len(mesh.faces)), unique)
855 components.extend(broke.reshape((-1, 1)))
857 # get a submesh as a single appended Trimesh
858 smooth = mesh.submesh(components, only_watertight=False, append=True)
859 # store face indices from original mesh
860 smooth.metadata["original_components"] = components
861 # smoothed should have exactly the same number of faces
862 if len(smooth.faces) != len(mesh.faces):
863 log.warning("face count in smooth wrong!")
864 return smooth
867def is_watertight(
868 edges: ArrayLike, edges_sorted: ArrayLike | None = None
869) -> tuple[bool, bool]:
870 """
871 Parameters
872 -----------
873 edges : (n, 2) int
874 List of vertex indices
875 edges_sorted : (n, 2) int
876 Pass vertex indices sorted on axis 1 as a speedup
878 Returns
879 ---------
880 watertight : boolean
881 Whether every edge is shared by an even
882 number of faces
883 winding : boolean
884 Whether every shared edge is reversed
885 """
886 # passing edges_sorted is a speedup only
887 if edges_sorted is None:
888 edges_sorted = np.sort(edges, axis=1)
890 # group sorted edges throwing away any edge
891 # that doesn't appear exactly twice
892 groups = grouping.group_rows(edges_sorted, require_count=2)
893 # if we didn't throw away any edges that means
894 # every edge shows up exactly twice
895 watertight = bool((len(groups) * 2) == len(edges))
897 # check that the un-sorted duplicate edges are reversed
898 opposing = edges[groups].reshape((-1, 4))[:, 1:3].T
899 winding = bool(np.equal(*opposing).all())
901 return watertight, winding
904def graph_to_svg(graph):
905 """
906 Turn a networkx graph into an SVG string
907 using graphviz `dot`.
909 Parameters
910 ----------
911 graph: networkx graph
913 Returns
914 ---------
915 svg: string, pictoral layout in SVG format
916 """
918 import subprocess
919 import tempfile
921 with tempfile.NamedTemporaryFile() as dot_file:
922 nx.drawing.nx_agraph.write_dot(graph, dot_file.name)
923 svg = subprocess.check_output(["dot", dot_file.name, "-Tsvg"])
924 return svg
927def multigraph_paths(G, source, cutoff=None):
928 """
929 For a networkx MultiDiGraph, find all paths from a source node
930 to leaf nodes. This function returns edge instance numbers
931 in addition to nodes, unlike networkx.all_simple_paths.
933 Parameters
934 ---------------
935 G : networkx.MultiDiGraph
936 Graph to evaluate
937 source : hashable
938 Node to start traversal at
939 cutoff : int
940 Number of nodes to visit
941 If None will visit all nodes
943 Returns
944 ----------
945 traversals : (n,) list of [(node, edge instance index), ] paths
946 Traversals of the multigraph
947 """
948 if cutoff is None:
949 cutoff = (len(G.edges()) * len(G.nodes())) + 1
951 # the path starts at the node specified
952 current = [(source, 0)]
953 # traversals we need to go back and do
954 queue = []
955 # completed paths
956 traversals = []
958 for _ in range(cutoff):
959 # paths are stored as (node, instance) so
960 # get the node of the last place visited
961 current_node = current[-1][0]
962 # get all the children of the current node
963 child = G[current_node]
965 if len(child) == 0:
966 # we have no children, so we are at the end of this path
967 # save the path as a completed traversal
968 traversals.append(current)
969 # if there is nothing on the queue, we are done
970 if len(queue) == 0:
971 break
972 # otherwise continue traversing with the next path
973 # on the queue
974 current = queue.pop()
975 else:
976 # oh no, we have multiple edges from current -> child
977 start = True
978 # iterate through child nodes and edge instances
979 for node in child.keys():
980 for instance in child[node].keys():
981 if start:
982 # if this is the first edge, keep it on the
983 # current traversal and save the others for later
984 current.append((node, instance))
985 start = False
986 else:
987 # this child has multiple instances
988 # so we will need to traverse them multiple times
989 # we appended a node to current, so only take the
990 # first n-1 visits
991 queue.append(current[:-1] + [(node, instance)])
992 return traversals
995def multigraph_collect(G, traversal, attrib=None):
996 """
997 Given a MultiDiGraph traversal, collect attributes along it.
999 Parameters
1000 -------------
1001 G: networkx.MultiDiGraph
1002 traversal: (n) list of (node, instance) tuples
1003 attrib: dict key, name to collect. If None, will return all
1005 Returns
1006 -------------
1007 collected: (len(traversal) - 1) list of attributes
1008 """
1010 collected = []
1011 for u, v in util.pairwise(traversal):
1012 attribs = G[u[0]][v[0]][v[1]]
1013 if attrib is None:
1014 collected.append(attribs)
1015 else:
1016 collected.append(attribs[attrib])
1017 return collected