Coverage for trimesh/intersections.py: 93%

260 statements  

« prev     ^ index     » next       coverage.py v7.17.0, created at 2026-11-12 17:18 +0000

1""" 

2intersections.py 

3------------------ 

4 

5Primarily mesh-plane intersections (slicing). 

6""" 

7 

8import numpy as np 

9 

10from . import geometry, grouping, util 

11from . import transformations as tf 

12from . import triangles as tm 

13from .constants import tol 

14from .triangles import points_to_barycentric 

15 

16 

17def mesh_plane( 

18 mesh, 

19 plane_normal, 

20 plane_origin, 

21 return_faces=False, 

22 local_faces=None, 

23 cached_dots=None, 

24): 

25 """ 

26 Find a the intersections between a mesh and a plane, 

27 returning a set of line segments on that plane. 

28 

29 Parameters 

30 --------- 

31 mesh : Trimesh object 

32 Source mesh to slice 

33 plane_normal : (3,) float 

34 Normal vector of plane to intersect with mesh 

35 plane_origin : (3,) float 

36 Point on plane to intersect with mesh 

37 return_faces : bool 

38 If True return face index each line is from 

39 local_faces : None or (m,) int 

40 Limit section to just these faces. 

41 cached_dots : (n, 3) float 

42 If an external function has stored dot 

43 products pass them here to avoid recomputing. 

44 

45 Returns 

46 ---------- 

47 lines : (m, 2, 3) float 

48 List of 3D line segments in space. 

49 face_index : (m,) int 

50 Index of mesh.faces for each line 

51 Only returned if return_faces was True 

52 """ 

53 

54 def triangle_cases(signs): 

55 """ 

56 Figure out which faces correspond to which intersection 

57 case from the signs of the dot product of each vertex. 

58 Does this by bitbang each row of signs into an 8 bit 

59 integer. 

60 

61 code : signs : intersects 

62 0 : [-1 -1 -1] : No 

63 2 : [-1 -1 0] : No 

64 4 : [-1 -1 1] : Yes; 2 on one side, 1 on the other 

65 6 : [-1 0 0] : Yes; one edge fully on plane 

66 8 : [-1 0 1] : Yes; one vertex on plane 2 on different sides 

67 12 : [-1 1 1] : Yes; 2 on one side, 1 on the other 

68 14 : [0 0 0] : No (on plane fully) 

69 16 : [0 0 1] : Yes; one edge fully on plane 

70 20 : [0 1 1] : No 

71 28 : [1 1 1] : No 

72 

73 Parameters 

74 ---------- 

75 signs: (n,3) int, all values are -1,0, or 1 

76 Each row contains the dot product of all three vertices 

77 in a face with respect to the plane 

78 

79 Returns 

80 --------- 

81 basic : (n,) bool 

82 Which faces are in the basic intersection case 

83 one_vertex : (n,) bool 

84 Which faces are in the one vertex case 

85 one_edge : (n,) bool 

86 Which faces are in the one edge case 

87 """ 

88 

89 signs_sorted = np.sort(signs, axis=1) 

90 coded = np.zeros(len(signs_sorted), dtype=np.int8) + 14 

91 for i in range(3): 

92 coded += signs_sorted[:, i] << 3 - i 

93 

94 # one edge fully on the plane 

95 # note that we are only accepting *one* of the on- edge cases, 

96 # where the other vertex has a positive dot product (16) instead 

97 # of both on- edge cases ([6, 16]) 

98 # this is so that for regions that are co-planar with the the section plane 

99 # we don't end up with an invalid boundary 

100 key = np.zeros(29, dtype=bool) 

101 key[16] = True 

102 one_edge = key[coded] 

103 

104 # one vertex on plane, other two on different sides 

105 key[:] = False 

106 key[8] = True 

107 one_vertex = key[coded] 

108 

109 # one vertex on one side of the plane, two on the other 

110 key[:] = False 

111 key[[4, 12]] = True 

112 basic = key[coded] 

113 

114 return basic, one_vertex, one_edge 

115 

116 def handle_on_vertex(signs, faces, vertices): 

117 # case where one vertex is on plane 

118 # and two are on different sides 

119 vertex_plane = faces[signs == 0] 

120 edge_thru = faces[signs != 0].reshape((-1, 2)) 

121 point_intersect, valid = plane_lines( 

122 plane_origin, plane_normal, vertices[edge_thru.T], line_segments=False 

123 ) 

124 lines = np.column_stack((vertices[vertex_plane[valid]], point_intersect)).reshape( 

125 (-1, 2, 3) 

126 ) 

127 return lines 

128 

129 def handle_on_edge(signs, faces, vertices): 

130 # case where two vertices are on the plane and one is off 

131 edges = faces[signs == 0].reshape((-1, 2)) 

132 points = vertices[edges] 

133 return points 

134 

135 def handle_basic(signs, faces, vertices): 

136 # case where one vertex is on one side and two are on the other 

137 unique_element = grouping.unique_value_in_row(signs, unique=[-1, 1]) 

138 edges = np.column_stack( 

139 ( 

140 faces[unique_element], 

141 faces[np.roll(unique_element, 1, axis=1)], 

142 faces[unique_element], 

143 faces[np.roll(unique_element, 2, axis=1)], 

144 ) 

145 ).reshape((-1, 2)) 

146 intersections, valid = plane_lines( 

147 plane_origin, plane_normal, vertices[edges.T], line_segments=False 

148 ) 

149 # since the data has been pre- culled, any invalid intersections at all 

150 # means the culling was done incorrectly and thus things are broken 

151 assert valid.all() 

152 return intersections.reshape((-1, 2, 3)) 

153 

154 # check input plane 

155 plane_normal = np.asanyarray(plane_normal, dtype=np.float64) 

156 plane_origin = np.asanyarray(plane_origin, dtype=np.float64) 

157 if plane_origin.shape != (3,) or plane_normal.shape != (3,): 

158 raise ValueError("Plane origin and normal must be (3,)!") 

159 

160 if local_faces is None: 

161 # do a cross section against all faces 

162 faces = mesh.faces 

163 else: 

164 local_faces = np.asanyarray(local_faces, dtype=np.int64) 

165 # only take the subset of faces if passed 

166 faces = mesh.faces[local_faces] 

167 

168 if cached_dots is not None: 

169 dots = cached_dots 

170 else: 

171 # dot product of each vertex with the plane normal indexed by face 

172 # so for each face the dot product of each vertex is a row 

173 # shape is the same as mesh.faces (n,3) 

174 dots = np.dot(mesh.vertices - plane_origin, plane_normal) 

175 

176 # sign of the dot product is -1, 0, or 1 

177 # shape is the same as mesh.faces (n,3) 

178 signs = np.zeros(len(mesh.vertices), dtype=np.int8) 

179 signs[dots < -tol.merge] = -1 

180 signs[dots > tol.merge] = 1 

181 signs = signs[faces] 

182 

183 # figure out which triangles are in the cross section, 

184 # and which of the three intersection cases they are in 

185 cases = triangle_cases(signs) 

186 # handlers for each case 

187 handlers = (handle_basic, handle_on_vertex, handle_on_edge) 

188 

189 # the (m, 2, 3) line segments 

190 lines = np.vstack( 

191 [h(signs[c], faces[c], mesh.vertices) for c, h in zip(cases, handlers)] 

192 ) 

193 

194 if return_faces: 

195 # everything that hit something 

196 index = np.hstack([np.nonzero(c)[0] for c in cases]) 

197 assert index.dtype.kind == "i" 

198 if local_faces is None: 

199 return lines, index 

200 # we are considering a subset of faces 

201 # so we need to take the indexes from original 

202 return lines, local_faces[index] 

203 return lines 

204 

205 

206def mesh_multiplane(mesh, plane_origin, plane_normal, heights): 

207 """ 

208 A utility function for slicing a mesh by multiple 

209 parallel planes which caches the dot product operation. 

210 

211 Parameters 

212 ------------- 

213 mesh : trimesh.Trimesh 

214 Geometry to be sliced by planes 

215 plane_origin : (3,) float 

216 Point on a plane 

217 plane_normal : (3,) float 

218 Normal vector of plane 

219 heights : (m,) float 

220 Offset distances from plane to slice at: 

221 at `height=0` it will be exactly on the passed plane. 

222 

223 Returns 

224 -------------- 

225 lines : (m,) sequence of (n, 2, 2) float 

226 Lines in space for m planes 

227 to_3D : (m, 4, 4) float 

228 Transform to move each section back to 3D 

229 face_index : (m,) sequence of (n,) int 

230 Indexes of mesh.faces for each segment 

231 """ 

232 # check input plane 

233 plane_normal = util.unitize(plane_normal) 

234 plane_origin = np.asanyarray(plane_origin, dtype=np.float64) 

235 heights = np.asanyarray(heights, dtype=np.float64) 

236 

237 # dot product of every vertex with plane 

238 vertex_dots = np.dot(plane_normal, (mesh.vertices - plane_origin).T) 

239 

240 # reconstruct transforms for each 2D section 

241 base_transform = geometry.plane_transform(origin=plane_origin, normal=plane_normal) 

242 base_transform = np.linalg.inv(base_transform) 

243 

244 # alter translation Z inside loop 

245 translation = np.eye(4) 

246 

247 # store results 

248 transforms = [] 

249 face_index = [] 

250 segments = [] 

251 

252 # loop through user specified heights 

253 for height in heights: 

254 # offset the origin by the height 

255 new_origin = plane_origin + (plane_normal * height) 

256 # offset the dot products by height and index by faces 

257 new_dots = vertex_dots - height 

258 # run the intersection with the cached dot products 

259 lines, index = mesh_plane( 

260 mesh=mesh, 

261 plane_origin=new_origin, 

262 plane_normal=plane_normal, 

263 return_faces=True, 

264 cached_dots=new_dots, 

265 ) 

266 

267 # get the transforms to 3D space and back 

268 translation[2, 3] = height 

269 to_3D = np.dot(base_transform, translation) 

270 to_2D = np.linalg.inv(to_3D) 

271 transforms.append(to_3D) 

272 

273 # transform points to 2D frame 

274 lines_2D = tf.transform_points(lines.reshape((-1, 3)), to_2D) 

275 

276 # if we didn't screw up the transform all 

277 # of the Z values should be zero 

278 # assert np.allclose(lines_2D[:, 2], 0.0) 

279 

280 # reshape back in to lines and discard Z 

281 lines_2D = lines_2D[:, :2].reshape((-1, 2, 2)) 

282 # store (n, 2, 2) float lines 

283 segments.append(lines_2D) 

284 # store (n,) int indexes of mesh.faces 

285 face_index.append(index) 

286 

287 # (n, 4, 4) transforms from 2D to 3D 

288 transforms = np.array(transforms, dtype=np.float64) 

289 

290 return segments, transforms, face_index 

291 

292 

293def plane_lines(plane_origin, plane_normal, endpoints, line_segments=True): 

294 """ 

295 Calculate plane-line intersections 

296 

297 Parameters 

298 --------- 

299 plane_origin : (3,) float 

300 Point on plane 

301 plane_normal : (3,) float 

302 Plane normal vector 

303 endpoints : (2, n, 3) float 

304 Points defining lines to be tested 

305 line_segments : bool 

306 If True, only returns intersections as valid if 

307 vertices from endpoints are on different sides 

308 of the plane. 

309 

310 Returns 

311 --------- 

312 intersections : (m, 3) float 

313 Cartesian intersection points 

314 valid : (n, 3) bool 

315 Indicate whether a valid intersection exists 

316 for each input line segment 

317 """ 

318 endpoints = np.asanyarray(endpoints) 

319 plane_origin = np.asanyarray(plane_origin).reshape(3) 

320 line_dir = util.unitize(endpoints[1] - endpoints[0]) 

321 plane_normal = util.unitize(np.asanyarray(plane_normal).reshape(3)) 

322 

323 t = np.dot(plane_normal, (plane_origin - endpoints[0]).T) 

324 b = np.dot(plane_normal, line_dir.T) 

325 

326 # If the plane normal and line direction are perpendicular, it means 

327 # the vector is 'on plane', and there isn't a valid intersection. 

328 # We discard on-plane vectors by checking that the dot product is nonzero 

329 valid = np.abs(b) > tol.zero 

330 if line_segments: 

331 test = np.dot(plane_normal, np.transpose(plane_origin - endpoints[1])) 

332 different_sides = np.sign(t) != np.sign(test) 

333 nonzero = np.logical_or(np.abs(t) > tol.zero, np.abs(test) > tol.zero) 

334 valid = np.logical_and(valid, different_sides) 

335 valid = np.logical_and(valid, nonzero) 

336 

337 d = np.divide(t[valid], b[valid]) 

338 intersection = endpoints[0][valid] 

339 intersection = intersection + np.reshape(d, (-1, 1)) * line_dir[valid] 

340 

341 return intersection, valid 

342 

343 

344def planes_lines( 

345 plane_origins, 

346 plane_normals, 

347 line_origins, 

348 line_directions, 

349 return_distance=False, 

350 return_denom=False, 

351): 

352 """ 

353 Given one line per plane find the intersection points. 

354 

355 Parameters 

356 ----------- 

357 plane_origins : (n,3) float 

358 Point on each plane 

359 plane_normals : (n,3) float 

360 Normal vector of each plane 

361 line_origins : (n,3) float 

362 Point at origin of each line 

363 line_directions : (n,3) float 

364 Direction vector of each line 

365 return_distance : bool 

366 Return distance from origin to point also 

367 return_denom : bool 

368 Return denominator, so you can check for small values 

369 

370 Returns 

371 ---------- 

372 on_plane : (n,3) float 

373 Points on specified planes 

374 valid : (n,) bool 

375 Did plane intersect line or not 

376 distance : (n,) float 

377 [OPTIONAL] Distance from point 

378 denom : (n,) float 

379 [OPTIONAL] Denominator 

380 """ 

381 

382 # check input types 

383 plane_origins = np.asanyarray(plane_origins, dtype=np.float64) 

384 plane_normals = np.asanyarray(plane_normals, dtype=np.float64) 

385 line_origins = np.asanyarray(line_origins, dtype=np.float64) 

386 line_directions = np.asanyarray(line_directions, dtype=np.float64) 

387 

388 # vector from line to plane 

389 origin_vectors = plane_origins - line_origins 

390 

391 projection_ori = util.diagonal_dot(origin_vectors, plane_normals) 

392 projection_dir = util.diagonal_dot(line_directions, plane_normals) 

393 

394 valid = np.abs(projection_dir) > 1e-5 

395 

396 distance = np.divide(projection_ori[valid], projection_dir[valid]) 

397 

398 on_plane = line_directions[valid] * distance.reshape((-1, 1)) 

399 on_plane += line_origins[valid] 

400 

401 result = [on_plane, valid] 

402 

403 if return_distance: 

404 result.append(distance) 

405 if return_denom: 

406 result.append(projection_dir) 

407 

408 return result 

409 

410 

411def slice_faces_plane( 

412 vertices, 

413 faces, 

414 plane_normal, 

415 plane_origin, 

416 uv=None, 

417 face_index=None, 

418 cached_dots=None, 

419): 

420 """ 

421 Slice a mesh (given as a set of faces and vertices) with a plane, returning a 

422 new mesh (again as a set of faces and vertices) that is the 

423 portion of the original mesh to the positive normal side of the plane. 

424 

425 Parameters 

426 --------- 

427 vertices : (n, 3) float 

428 Vertices of source mesh to slice 

429 faces : (n, 3) int 

430 Faces of source mesh to slice 

431 plane_normal : (3,) float 

432 Normal vector of plane to intersect with mesh 

433 plane_origin : (3,) float 

434 Point on plane to intersect with mesh 

435 uv : (n, 2) float, optional 

436 UV coordinates of source mesh to slice 

437 face_index : ((m,) int) 

438 Indexes of faces to slice. When no mask is provided, the 

439 default is to slice all faces. 

440 cached_dots : (n, 3) float 

441 If an external function has stored dot 

442 products pass them here to avoid recomputing 

443 

444 Returns 

445 ---------- 

446 new_vertices : (n, 3) float 

447 Vertices of sliced mesh 

448 new_faces : (n, 3) int 

449 Faces of sliced mesh 

450 new_uv : (n, 2) int or None 

451 UV coordinates of sliced mesh 

452 """ 

453 

454 if len(vertices) == 0: 

455 return vertices, faces, uv 

456 

457 have_uv = uv is not None 

458 

459 # Construct a mask for the faces to slice. 

460 if face_index is None: 

461 mask = np.ones(len(faces), dtype=bool) 

462 else: 

463 mask = np.zeros(len(faces), dtype=bool) 

464 mask[face_index] = True 

465 

466 if cached_dots is not None: 

467 dots = cached_dots 

468 else: 

469 # dot product of each vertex with the plane normal indexed by face 

470 # so for each face the dot product of each vertex is a row 

471 # shape is the same as faces (n,3) 

472 dots = np.dot(vertices - plane_origin, plane_normal) 

473 

474 # Find vertex orientations w.r.t. faces for all triangles: 

475 # -1 -> vertex "inside" plane (positive normal direction) 

476 # 0 -> vertex on plane 

477 # 1 -> vertex "outside" plane (negative normal direction) 

478 signs = np.zeros(len(vertices), dtype=np.int8) 

479 signs[dots < -tol.merge] = 1 

480 signs[dots > tol.merge] = -1 

481 signs = signs[faces] 

482 

483 # Find all triangles that intersect this plane 

484 # onedge <- indices of all triangles intersecting the plane 

485 # inside <- indices of all triangles "inside" the plane (positive normal) 

486 signs_sum = signs.sum(axis=1, dtype=np.int8) 

487 signs_asum = np.abs(signs).sum(axis=1, dtype=np.int8) 

488 

489 # Cases: 

490 # (0,0,0), (-1,0,0), (-1,-1,0), (-1,-1,-1) <- inside 

491 # (1,0,0), (1,1,0), (1,1,1) <- outside 

492 # (1,0,-1), (1,-1,-1), (1,1,-1) <- onedge 

493 onedge = np.logical_and(signs_asum >= 2, np.abs(signs_sum) <= 1) & mask 

494 

495 # faces not in the mask are kept unchanged 

496 inside = (signs_sum == -signs_asum) | ~mask 

497 

498 # for any faces that lie exactly on-the-plane 

499 # we want to only include them if their normal 

500 # is backwards from the slicing normal 

501 on_plane = (signs_asum == 0) & mask 

502 if on_plane.any(): 

503 # compute the normals and whether 

504 # face is degenerate here 

505 check, valid = tm.normals(vertices[faces[on_plane]]) 

506 # only include faces back from normal 

507 dot_check = np.dot(check, plane_normal) 

508 # exclude any degenerate faces from the result 

509 inside[on_plane] = valid 

510 # exclude the degenerate face from our mask 

511 on_plane[on_plane] = valid 

512 # apply results for this subset 

513 inside[on_plane] = dot_check < 0.0 

514 

515 # Automatically include all faces that are "inside" 

516 new_faces = faces[inside] 

517 

518 # Separate faces on the edge into two cases: those which will become 

519 # quads (two vertices inside plane) and those which will become triangles 

520 # (one vertex inside plane) 

521 triangles = vertices[faces] 

522 cut_triangles = triangles[onedge] 

523 cut_faces_quad = faces[np.logical_and(onedge, signs_sum < 0)] 

524 cut_faces_tri = faces[np.logical_and(onedge, signs_sum >= 0)] 

525 cut_signs_quad = signs[np.logical_and(onedge, signs_sum < 0)] 

526 cut_signs_tri = signs[np.logical_and(onedge, signs_sum >= 0)] 

527 

528 # If no faces to cut, the surface is not in contact with this plane. 

529 # Thus, return a mesh with only the inside faces 

530 if len(cut_faces_quad) + len(cut_faces_tri) == 0: 

531 if len(new_faces) == 0: 

532 # if no new faces at all return empty arrays 

533 empty = ( 

534 np.zeros((0, 3), dtype=np.float64), 

535 np.zeros((0, 3), dtype=np.int64), 

536 np.zeros((0, 2), dtype=np.float64) if have_uv else None, 

537 ) 

538 return empty 

539 

540 # find the unique indices in the new faces 

541 # using an integer-only unique function 

542 unique, inverse = grouping.unique_bincount( 

543 new_faces.reshape(-1), minlength=len(vertices), return_inverse=True 

544 ) 

545 

546 # use the unique indices for our final vertices and faces 

547 final_vert = vertices[unique] 

548 final_face = inverse.reshape((-1, 3)) 

549 final_uv = uv[unique] if have_uv else None 

550 

551 return final_vert, final_face, final_uv 

552 

553 # Extract the intersections of each triangle's edges with the plane 

554 o = cut_triangles # origins 

555 d = np.roll(o, -1, axis=1) - o # directions 

556 num = (plane_origin - o).dot(plane_normal) # compute num/denom 

557 denom = np.dot(d, plane_normal) 

558 denom[denom == 0.0] = 1e-12 # prevent division by zero 

559 dist = np.divide(num, denom) 

560 # intersection points for each segment 

561 int_points = dist[:, :, None] * d + o 

562 

563 # Initialize the array of new vertices with the current vertices 

564 new_vertices = vertices 

565 new_quad_vertices = np.zeros((0, 3)) 

566 new_tri_vertices = np.zeros((0, 3)) 

567 

568 # Handle the case where a new quad is formed by the intersection 

569 # First, extract the intersection points belonging to a new quad 

570 quad_int_points = int_points[(signs_sum < 0)[onedge], :, :] 

571 num_quads = len(quad_int_points) 

572 if num_quads > 0: 

573 # Extract the vertex on the outside of the plane, then get the vertices 

574 # (in CCW order of the inside vertices) 

575 quad_int_inds = np.where(cut_signs_quad == 1)[1] 

576 quad_int_verts = cut_faces_quad[ 

577 np.stack((range(num_quads), range(num_quads)), axis=1), 

578 np.stack(((quad_int_inds + 1) % 3, (quad_int_inds + 2) % 3), axis=1), 

579 ] 

580 

581 # Fill out new quad faces with the intersection points as vertices 

582 new_quad_faces = np.append( 

583 quad_int_verts, 

584 np.arange(len(new_vertices), len(new_vertices) + 2 * num_quads).reshape( 

585 num_quads, 2 

586 ), 

587 axis=1, 

588 ) 

589 

590 # Extract correct intersection points from int_points and order them in 

591 # the same way as they were added to faces 

592 new_quad_vertices = quad_int_points[ 

593 np.stack((range(num_quads), range(num_quads)), axis=1), 

594 np.stack((((quad_int_inds + 2) % 3).T, quad_int_inds.T), axis=1), 

595 :, 

596 ].reshape(2 * num_quads, 3) 

597 

598 # Add new vertices to existing vertices, triangulate quads, and add the 

599 # resulting triangles to the new faces 

600 new_vertices = np.append(new_vertices, new_quad_vertices, axis=0) 

601 new_tri_faces_from_quads = geometry.triangulate_quads(new_quad_faces) 

602 new_faces = np.append(new_faces, new_tri_faces_from_quads, axis=0) 

603 

604 # Handle the case where a new triangle is formed by the intersection 

605 # First, extract the intersection points belonging to a new triangle 

606 tri_int_points = int_points[(signs_sum >= 0)[onedge], :, :] 

607 num_tris = len(tri_int_points) 

608 if num_tris > 0: 

609 # Extract the single vertex for each triangle inside the plane and get the 

610 # inside vertices (CCW order) 

611 tri_int_inds = np.where(cut_signs_tri == -1)[1] 

612 tri_int_verts = cut_faces_tri[range(num_tris), tri_int_inds].reshape(num_tris, 1) 

613 

614 # Fill out new triangles with the intersection points as vertices 

615 new_tri_faces = np.append( 

616 tri_int_verts, 

617 np.arange(len(new_vertices), len(new_vertices) + 2 * num_tris).reshape( 

618 num_tris, 2 

619 ), 

620 axis=1, 

621 ) 

622 

623 # Extract correct intersection points and order them in the same way as 

624 # the vertices were added to the faces 

625 new_tri_vertices = tri_int_points[ 

626 np.stack((range(num_tris), range(num_tris)), axis=1), 

627 np.stack((tri_int_inds.T, ((tri_int_inds + 2) % 3).T), axis=1), 

628 :, 

629 ].reshape(2 * num_tris, 3) 

630 

631 # Append new vertices and new faces 

632 new_vertices = np.append(new_vertices, new_tri_vertices, axis=0) 

633 new_faces = np.append(new_faces, new_tri_faces, axis=0) 

634 

635 # find the unique indices in the new faces 

636 # using an integer-only unique function 

637 unique, inverse = grouping.unique_bincount( 

638 new_faces.reshape(-1), minlength=len(new_vertices), return_inverse=True 

639 ) 

640 

641 # use the unique indexes for our final vertex and faces 

642 final_vert = new_vertices[unique] 

643 final_face = inverse.reshape((-1, 3)) 

644 

645 final_uv = None 

646 if have_uv: 

647 # Generate barycentric coordinates for intersection vertices 

648 quad_barycentrics = points_to_barycentric( 

649 np.repeat(vertices[cut_faces_quad], 2, axis=0), new_quad_vertices 

650 ) 

651 tri_barycentrics = points_to_barycentric( 

652 np.repeat(vertices[cut_faces_tri], 2, axis=0), new_tri_vertices 

653 ) 

654 all_barycentrics = np.concatenate([quad_barycentrics, tri_barycentrics]) 

655 

656 # Interpolate UVs 

657 cut_uv = np.concatenate([uv[cut_faces_quad], uv[cut_faces_tri]]) 

658 new_uv = np.einsum("ijk,ij->ik", np.repeat(cut_uv, 2, axis=0), all_barycentrics) 

659 final_uv = np.concatenate([uv, new_uv])[unique] 

660 

661 return final_vert, final_face, final_uv 

662 

663 

664def slice_mesh_plane( 

665 mesh, 

666 plane_normal, 

667 plane_origin, 

668 face_index=None, 

669 cap=False, 

670 engine=None, 

671 **kwargs, 

672): 

673 """ 

674 Slice a mesh with a plane returning a new mesh that is the 

675 portion of the original mesh to the positive normal side 

676 of the plane. 

677 

678 Parameters 

679 --------- 

680 mesh : Trimesh object 

681 Source mesh to slice 

682 plane_normal : (3,) float 

683 Normal vector of plane to intersect with mesh 

684 plane_origin : (3,) float 

685 Point on plane to intersect with mesh 

686 cap : bool 

687 If True, cap the result with a triangulated polygon 

688 face_index : ((m,) int) 

689 Indexes of mesh.faces to slice. When no mask is provided, the 

690 default is to slice all faces. 

691 cached_dots : (n, 3) float 

692 If an external function has stored dot 

693 products pass them here to avoid recomputing 

694 engine : None or str 

695 Triangulation engine passed to `triangulate_polygon` 

696 kwargs : dict 

697 Passed to the newly created sliced mesh 

698 

699 Returns 

700 ---------- 

701 new_mesh : Trimesh object 

702 Sliced mesh 

703 """ 

704 # check input for none 

705 if mesh is None: 

706 return None 

707 

708 # avoid circular import 

709 from scipy.spatial import cKDTree 

710 

711 from .base import Trimesh 

712 from .creation import triangulate_polygon 

713 from .path import polygons 

714 from .visual import TextureVisuals 

715 

716 # check input plane 

717 plane_normal = np.asanyarray(plane_normal, dtype=np.float64) 

718 plane_origin = np.asanyarray(plane_origin, dtype=np.float64) 

719 

720 # check to make sure origins and normals have acceptable shape 

721 shape_ok = ( 

722 (plane_origin.shape == (3,) or util.is_shape(plane_origin, (-1, 3))) 

723 and (plane_normal.shape == (3,) or util.is_shape(plane_normal, (-1, 3))) 

724 and plane_origin.shape == plane_normal.shape 

725 ) 

726 if not shape_ok: 

727 raise ValueError("plane origins and normals must be (n, 3)!") 

728 

729 # start with copy of original mesh, faces, and vertices 

730 vertices = mesh.vertices.copy() 

731 faces = mesh.faces.copy() 

732 

733 # We copy the UV coordinates if available 

734 has_uv = ( 

735 hasattr(mesh.visual, "uv") and np.shape(mesh.visual.uv) == (len(mesh.vertices), 2) 

736 ) and not cap 

737 uv = mesh.visual.uv.copy() if has_uv else None 

738 

739 if "process" not in kwargs: 

740 kwargs["process"] = False 

741 

742 # slice away specified planes 

743 for origin, normal in zip( 

744 plane_origin.reshape((-1, 3)), plane_normal.reshape((-1, 3)) 

745 ): 

746 # save the new vertices and faces 

747 vertices, faces, uv = slice_faces_plane( 

748 vertices=vertices, 

749 faces=faces, 

750 uv=uv, 

751 plane_normal=normal, 

752 plane_origin=origin, 

753 face_index=face_index, 

754 ) 

755 # check if cap arg specified 

756 if cap: 

757 if face_index: 

758 # This hasn't been implemented yet. 

759 raise NotImplementedError("face_index and cap can't be used together") 

760 

761 # start by deduplicating vertices again 

762 unique, inverse = grouping.unique_rows(vertices) 

763 vertices = vertices[unique] 

764 # will collect additional faces 

765 f = inverse[faces] 

766 # remove degenerate faces by checking to make sure 

767 # that each face has three unique indices 

768 f = f[(f[:, :1] != f[:, 1:]).all(axis=1)] 

769 # transform to the cap plane 

770 to_2D = geometry.plane_transform(origin=origin, normal=-normal) 

771 to_3D = np.linalg.inv(to_2D) 

772 

773 vertices_2D = tf.transform_points(vertices, to_2D) 

774 edges = geometry.faces_to_edges(f) 

775 edges.sort(axis=1) 

776 

777 on_plane = np.abs(vertices_2D[:, 2]) < 1e-8 

778 edges = edges[on_plane[edges].all(axis=1)] 

779 edges = edges[edges[:, 0] != edges[:, 1]] 

780 

781 unique_edge = grouping.group_rows(edges, require_count=1) 

782 if len(unique) < 3: 

783 continue 

784 

785 tree = cKDTree(vertices) 

786 # collect new faces 

787 faces = [f] 

788 for p in polygons.edges_to_polygons(edges[unique_edge], vertices_2D[:, :2]): 

789 # triangulate cap and raise an error if any new vertices were inserted 

790 vn, fn = triangulate_polygon(p, engine=engine, force_vertices=True) 

791 # collect the original index for the new vertices 

792 vn3 = tf.transform_points(util.stack_3D(vn), to_3D) 

793 distance, vid = tree.query(vn3) 

794 if distance.max() > 1e-8: 

795 util.log.debug("triangulate may have inserted vertex!") 

796 # triangulation should not have inserted vertices 

797 nf = vid[fn] 

798 # hmm but it may have returned faces that are now degenerate 

799 nf_ok = (nf[:, 1:] != nf[:, :1]).all(axis=1) & (nf[:, 1] != nf[:, 2]) 

800 faces.append(nf[nf_ok]) 

801 

802 faces = np.vstack(faces) 

803 

804 visual = ( 

805 TextureVisuals(uv=uv, material=mesh.visual.material.copy()) if has_uv else None 

806 ) 

807 

808 # return the sliced mesh 

809 return Trimesh(vertices=vertices, faces=faces, visual=visual, **kwargs)