Coverage for trimesh/repair.py: 87%
132 statements
« prev ^ index » next coverage.py v7.14.1, created at 2026-06-24 04:40 +0000
1"""
2repair.py
3-------------
5Fill holes and fix winding and normals of meshes.
6"""
8import numpy as np
10from . import graph, triangles
11from .constants import log
12from .geometry import faces_to_edges, triangulate_quads
13from .graph import connected_components
14from .grouping import group_rows, hashable_rows
16try:
17 import networkx as nx
18except BaseException as E:
19 # create a dummy module which will raise the ImportError
20 # or other exception only when someone tries to use networkx
21 from .exceptions import ExceptionWrapper
23 nx = ExceptionWrapper(E)
25try:
26 from .path.exchange.misc import faces_to_path
27except BaseException as E:
28 from .exceptions import ExceptionWrapper
30 faces_to_path = ExceptionWrapper(E)
33def fix_winding(mesh):
34 """
35 Traverse and change mesh faces in-place to make sure
36 winding is correct with edges on adjacent faces in
37 opposite directions.
39 Parameters
40 -------------
41 mesh : Trimesh
42 Source geometry to alter in-place.
43 """
44 # anything we would fix is already done
45 if mesh.is_winding_consistent:
46 return
48 graph_all = nx.from_edgelist(mesh.face_adjacency)
49 flipped = 0
51 faces = mesh.faces.view(np.ndarray).copy()
53 # we are going to traverse the graph using BFS
54 # start a traversal for every connected component
55 for components in nx.connected_components(graph_all):
56 # get a subgraph for this component
57 g = graph_all.subgraph(components)
58 # get the first node in the graph in a way that works on nx's
59 # new API and their old API
60 start = next(iter(g.nodes()))
62 # we traverse every pair of faces in the graph
63 # we modify mesh.faces and mesh.face_normals in place
64 for face_pair in nx.bfs_edges(g, start):
65 # for each pair of faces, we convert them into edges,
66 # find the edge that both faces share and then see if edges
67 # are reversed in order as you would expect
68 # (2, ) int
69 face_pair = np.ravel(face_pair)
70 # (2, 3) int
71 pair = faces[face_pair]
72 # (6, 2) int
73 edges = faces_to_edges(pair)
74 overlap = group_rows(np.sort(edges, axis=1), require_count=2)
75 if len(overlap) == 0:
76 # only happens on non-watertight meshes
77 continue
78 edge_pair = edges[overlap[0]]
79 if edge_pair[0][0] == edge_pair[1][0]:
80 # if the edges aren't reversed, invert the order of one face
81 flipped += 1
82 faces[face_pair[1]] = faces[face_pair[1]][::-1]
84 if flipped > 0:
85 mesh.faces = faces
87 log.debug("flipped %d/%d edges", flipped, len(mesh.faces) * 3)
90def fix_inversion(mesh, multibody: bool = False):
91 """
92 Check to see if a mesh has normals pointing "out."
94 Parameters
95 -------------
96 mesh : trimesh.Trimesh
97 Mesh to fix in-place.
98 multibody : bool
99 If True will try to fix normals on every body
100 """
102 # we are not considering multiple bodies so we only need to
103 # do anything if the mesh is watertight and the volume is negative
104 if not multibody:
105 if mesh.is_watertight and mesh.volume < 0.0:
106 # this will make things worse for non-watertight meshes
107 mesh.invert()
108 return
110 # get groups of connected faces
111 groups = connected_components(mesh.face_adjacency)
113 # mask of faces to flip
114 flip = np.zeros(len(mesh.faces), dtype=bool)
116 # save these to avoid thrashing cache in a loop
117 tri = mesh.triangles
118 cross = mesh.triangles_cross
119 # get the edges indexable as faces
120 face_edges = mesh.edges.reshape((-1, 6))
122 # loop through indexes of `mesh.faces`
123 for face_index in groups:
124 # we need watertight bodies to do anything so immediately
125 # skip anything smaller than 4 faces (tetrahedron)
126 if len(face_index) < 4:
127 continue
128 # check the watertightness and winding of this group
129 is_tight, is_wound = graph.is_watertight(face_edges[face_index].reshape((-1, 2)))
131 # if we're not completely correct skip it as flipping faces will make it worse
132 if not (is_tight and is_wound):
133 continue
135 # check the volume for just this body
136 volume = triangles.mass_properties(
137 tri[face_index], crosses=cross[face_index], skip_inertia=True
138 ).volume
139 # if that volume is negative it is either
140 # inverted or just total garbage
141 if volume < 0.0:
142 flip[face_index] = True
144 # one or more faces needs flipping
145 if flip.any():
146 if "face_normals" in mesh._cache:
147 # flip normals of necessary faces
148 normals = mesh.face_normals.copy()
149 normals[flip] *= -1.0
150 else:
151 normals = None
152 # flip faces
153 mesh.faces[flip] = np.fliplr(mesh.faces[flip])
154 # assign corrected normals
155 if normals is not None:
156 mesh.face_normals = normals
159def fix_normals(mesh, multibody=False):
160 """
161 Fix the winding and direction of a mesh face and
162 face normals in-place.
164 Really only meaningful on watertight meshes but will orient all
165 faces and winding in a uniform way for non-watertight face
166 patches as well.
168 Parameters
169 -------------
170 mesh : trimesh.Trimesh
171 Mesh to fix normals on
172 multibody : bool
173 if True try to correct normals direction
174 on every body rather than just one
176 Notes
177 --------------
178 mesh.faces : will flip columns on inverted faces
179 """
180 # traverse face adjacency to correct winding
181 fix_winding(mesh)
182 # check to see if a mesh is inverted
183 fix_inversion(mesh, multibody=multibody)
186def broken_faces(mesh, color=None):
187 """
188 Return the index of faces in the mesh which break the
189 watertight status of the mesh.
191 Parameters
192 --------------
193 mesh : trimesh.Trimesh
194 Mesh to check broken faces on
195 color: (4,) uint8 or None
196 Will set broken faces to this color if not None
198 Returns
199 ---------------
200 broken : (n, ) int
201 Indexes of mesh.faces
202 """
203 adjacency = nx.from_edgelist(mesh.face_adjacency)
204 broken = [k for k, v in dict(adjacency.degree()).items() if v != 3]
205 broken = np.array(broken)
206 if color is not None and broken.size != 0:
207 # if someone passed a broken color
208 color = np.array(color)
209 if not (color.shape == (4,) or color.shape == (3,)):
210 color = [255, 0, 0, 255]
211 mesh.visual.face_colors[broken] = color
212 return broken
215def fill_holes(mesh, use_fan: bool = False):
216 """
217 Fill boundary holes in-place using fans, which may result
218 in bad answers if the holes are non convex!
220 Face colors and attributes will be padded with default values
221 so shapes match.
223 Parameters
224 ----------
225 mesh : trimesh.Trimesh
226 Mesh will be repaired in-place.
227 use_fan
228 If passed, holes larger than quads will be triangulated
229 using fans which are only valid for non-convex holes.
230 """
231 if len(mesh.faces) < 3:
232 return False
233 if mesh.is_watertight:
234 return True
236 # any edge that occurs once is on the boundary
237 boundary_groups = group_rows(mesh.edges_sorted, require_count=1)
238 # either watertight or broken in a weird way
239 if len(boundary_groups) < 3:
240 return False
242 # ordered edges on the boundary
243 boundary = mesh.edges[boundary_groups]
245 # use networkx to find cycles of boundary edges
246 holes = nx.cycle_basis(nx.from_edgelist(boundary))
248 # this handles mixed tris, quads, and arbitrary polygons
249 new_faces = triangulate_quads(holes, use_fan=use_fan)
250 if len(new_faces) == 0:
251 return False
253 # now we need to fix the winding for every new face
254 new_edges = faces_to_edges(new_faces)
256 # the hashable rows for the mesh boundary edges
257 # and the boundary of the original hole in the mesh
258 # a well-constructed mesh has edges that are REVERSED
259 # so we're going to try a cheap indexing operation
260 hashable_new = hashable_rows(new_edges)
261 hashable_old = hashable_rows(boundary)
263 # the magic trick: if any ordered edge of the NEW face is contained
264 # in the OLD boundary edges, it means the new face has edges that
265 # are in the same order as the boundary, and that new face
266 # needs to be reversed and since new_edges has exactly three
267 # edges per triangle we can compact indexes back to triangles
268 needs_reverse = np.isin(hashable_new, hashable_old).reshape((-1, 3)).any(axis=1)
270 # now we have some shiny new faces that might even be wound correctly!
271 new_faces[needs_reverse] = np.fliplr(new_faces[needs_reverse])
273 # do the bookkeeping to preserve face normals and pad attributes
274 mesh.extend_faces(new_faces)
276 return mesh.is_watertight
279def stitch(mesh, faces=None, insert_vertices=False):
280 """
281 Create a fan stitch over the boundary of the specified
282 faces. If the boundary is non-convex a triangle fan
283 is going to be extremely wonky.
285 Parameters
286 -----------
287 mesh : trimesh.Trimesh
288 Mesh to create fan stitch on.
289 faces : (n,) int
290 Face indexes to stitch with triangle fans.
291 insert_vertices : bool
292 Allow stitching to insert new vertices?
294 Returns
295 ----------
296 fan : (m, 3) int
297 New triangles referencing mesh.vertices.
298 vertices : (p, 3) float
299 Inserted vertices (only returned `if insert_vertices`)
300 """
301 if faces is None:
302 faces = np.arange(len(mesh.faces))
304 # get a sequence of vertex indices representing the
305 # boundary of the specified faces
306 # will be referencing the same indexes of `mesh.vertices`
307 points = [
308 e.points
309 for e in faces_to_path(mesh, faces)["entities"]
310 if len(e.points) > 3 and e.points[0] == e.points[-1]
311 ]
313 # get properties to avoid querying in loop
314 vertices = mesh.vertices
315 normals = mesh.face_normals
317 # find which faces are associated with an edge
318 edges_face = mesh.edges_face
319 tree_edge = mesh.edges_sorted_tree
321 if insert_vertices:
322 # create one new vertex per curve at the centroid
323 centroids = np.array([vertices[p].mean(axis=0) for p in points])
324 # save the original length of the vertices
325 count = len(vertices)
326 # for the normal check stack our local vertices
327 vertices = np.vstack((vertices, centroids))
328 # create a triangle between our new centroid vertex
329 # and each one of the boundary curves
330 fan = [
331 np.column_stack((np.ones(len(p) - 1, dtype=int) * (count + i), p[:-1], p[1:]))
332 for i, p in enumerate(points)
333 ]
334 else:
335 # since we're not allowed to insert new vertices
336 # create a triangle fan for each boundary curve
337 fan = [
338 np.column_stack((np.ones(len(p) - 3, dtype=int) * p[0], p[1:-2], p[2:-1]))
339 for p in points
340 ]
342 # now we do a normal check against an adjacent face
343 # to see if each region needs to be flipped
344 for i, t in zip(range(len(fan)), fan):
345 # get the edges from the original mesh
346 # for the first `n` new triangles
347 e = t[:10, 1:].copy()
348 e.sort(axis=1)
350 # find which indexes of `mesh.edges` these
351 # new edges correspond with by finding edges
352 # that exactly correspond with the tree
353 query = tree_edge.query_ball_point(e, r=1e-10)
354 if len(query) == 0:
355 continue
356 # stack all the indices that exist
357 edge_index = np.concatenate(query)
359 # get the normals from the original mesh
360 original = normals[edges_face[edge_index]]
362 # calculate the normals for a few new faces
363 check, valid = triangles.normals(vertices[t[:3]])
364 if not valid.any():
365 continue
366 # take the first valid normal from our new faces
367 check = check[0]
369 # if our new faces are reversed from the original
370 # Adjacent face flip them along their axis
371 sign = np.dot(original, check)
372 if sign.mean() < 0:
373 fan[i] = np.fliplr(t)
375 fan = np.vstack(fan)
377 if insert_vertices:
378 return fan, centroids
379 return fan