Coverage for trimesh/path/packing.py: 93%
242 statements
« prev ^ index » next coverage.py v7.14.1, created at 2026-06-24 04:40 +0000
1"""
2packing.py
3------------
5Pack rectangular regions onto larger rectangular regions.
6"""
8import numpy as np
10from ..constants import log, tol
11from ..typed import ArrayLike, Integer, NDArray, Number, float64
12from ..util import allclose, bounds_tree
14# floating point zero
15_TOL_ZERO = 1e-12
18class RectangleBin:
19 """
20 An N-dimensional binary space partition tree for packing
21 hyper-rectangles. Split logic is pure `numpy` but behaves
22 similarly to `scipy.spatial.Rectangle`.
24 Mostly useful for packing 2D textures and 3D boxes and
25 has not been tested outside of 2 and 3 dimensions.
27 Original article about using this for packing textures:
28 http://www.blackpawn.com/texts/lightmaps/
29 """
31 def __init__(self, bounds):
32 """
33 Create a rectangular bin.
35 Parameters
36 ------------
37 bounds : (2, dimension *) float
38 Bounds array are `[mins, maxes]`
39 """
40 # this is a *binary* tree so regardless of the dimensionality
41 # of the rectangles each node has exactly two children
42 self.child = []
43 # is this node occupied.
44 self.occupied = False
45 # assume bounds are a list
46 self.bounds = np.array(bounds, dtype=np.float64)
48 @property
49 def extents(self):
50 """
51 Bounding box size.
53 Returns
54 ----------
55 extents : (dimension,) float
56 Edge lengths of bounding box
57 """
58 bounds = self.bounds
59 return bounds[1] - bounds[0]
61 def insert(self, size, rotate=True):
62 """
63 Insert a rectangle into the bin.
65 Parameters
66 -------------
67 size : (dimension,) float
68 Size of rectangle to insert/
70 Returns
71 ----------
72 inserted : (2,) float or None
73 Position of insertion in the tree or None
74 if the insertion was unsuccessful.
75 """
76 for child in self.child:
77 # try inserting into child cells
78 attempt = child.insert(size=size, rotate=rotate)
79 if attempt is not None:
80 return attempt
82 # can't insert into occupied cells
83 if self.occupied:
84 return None
86 # shortcut for our bounds
87 bounds = self.bounds.copy()
88 extents = bounds[1] - bounds[0]
90 if rotate:
91 # we are allowed to rotate the rectangle
92 for roll in range(len(size)):
93 size_test = extents - _roll(size, roll)
94 fits = (size_test > -_TOL_ZERO).all()
95 if fits:
96 size = _roll(size, roll)
97 break
98 # we tried rotating and none of the directions fit
99 if not fits:
100 return None
101 else:
102 # compare the bin size to the insertion candidate size
103 # manually compute extents here to avoid function call
104 size_test = extents - size
105 if (size_test < -_TOL_ZERO).any():
106 return None
108 # since the cell is big enough for the current rectangle, either it
109 # is going to be inserted here, or the cell is going to be split
110 # either way the cell is now occupied.
111 self.occupied = True
113 # this means the inserted rectangle fits perfectly
114 # since we already checked to see if it was negative
115 # no abs is needed
116 if (size_test < _TOL_ZERO).all():
117 return bounds
119 # pick the axis to split along
120 axis = size_test.argmax()
121 # split hyper-rectangle along axis
122 # note that split is *absolute* distance not offset
123 # so we have to add the current min to the size
124 splits = np.vstack((bounds, bounds))
125 splits[1:3, axis] = bounds[0][axis] + size[axis]
127 # assign two children
128 self.child[:] = RectangleBin(splits[:2]), RectangleBin(splits[2:])
130 # insert the requested item into the first child
131 return self.child[0].insert(size, rotate=rotate)
134def _roll(a, count):
135 """
136 A speedup for `numpy.roll` that only works
137 on flat arrays and is fast on 2D and 3D and
138 reverts to `numpy.roll` for other cases.
140 Parameters
141 -----------
142 a : (n,) any
143 Array to roll
144 count : int
145 Number of places to shift array
147 Returns
148 ---------
149 rolled : (n,) any
150 Input array shifted by requested amount
152 """
153 # a lookup table for roll in 2 and 3 dimensions
154 lookup = [[[0, 1], [1, 0]], [[0, 1, 2], [2, 0, 1], [1, 2, 0]]]
155 try:
156 # roll the array using advanced indexing and a lookup table
157 return a[lookup[len(a) - 2][count]]
158 except IndexError:
159 # failing that return the results using concat
160 return np.concatenate([a[-count:], a[:-count]])
163def rectangles_single(extents, size=None, shuffle=False, rotate=True, random=None):
164 """
165 Execute a single insertion order of smaller rectangles onto
166 a larger rectangle using a binary space partition tree.
168 Parameters
169 ----------
170 extents : (n, dimension) float
171 The size of the hyper-rectangles to pack.
172 size : None or (dim,) float
173 Maximum size of container to pack onto.
174 If not passed it will re-root the tree when items
175 larger than any available node are inserted.
176 shuffle : bool
177 Whether or not to shuffle the insert order of the
178 smaller rectangles, as the final packing density depends
179 on insertion order.
180 rotate : bool
181 If True, allow integer-roll rotation.
183 Returns
184 ---------
185 bounds : (m, 2, dim) float
186 Axis aligned resulting bounds in space
187 transforms : (m, dim + 1, dim + 1) float
188 Homogeneous transformation including rotation.
189 consume : (n,) bool
190 Which of the original rectangles were packed,
191 i.e. `consume.sum() == m`
192 """
194 extents = np.asanyarray(extents, dtype=np.float64)
195 dimension = extents.shape[1]
196 # the return arrays
197 offset = np.zeros((len(extents), 2, dimension))
198 consume = np.zeros(len(extents), dtype=bool)
199 # start by ordering them by maximum length
200 order = np.argsort(extents.max(axis=1))[::-1]
202 if shuffle:
203 if random is not None:
204 order = random.permutation(order)
205 else:
206 # reorder with permutations
207 order = np.random.permutation(order)
209 if size is None:
210 # if no bounds are passed start it with the size of a large
211 # rectangle exactly which will require re-rooting for
212 # subsequent insertions
213 root_bounds = [[0.0] * dimension, extents[np.ptp(extents, axis=1).argmax()]]
214 else:
215 # restrict the bounds to passed size and disallow re-rooting
216 root_bounds = [[0.0] * dimension, size]
218 # the current root node to insert each rectangle
219 root = RectangleBin(bounds=root_bounds)
221 for index in order:
222 # the current rectangle to be inserted
223 rectangle = extents[index]
224 # try to insert the hyper-rectangle into children
225 inserted = root.insert(rectangle, rotate=rotate)
227 if inserted is None and size is None:
228 # we failed to insert into children
229 # so we need to create a new parent
230 # get the size of the current root node
231 bounds = root.bounds
232 # current extents
233 current = np.ptp(bounds, axis=0)
235 # pick the direction which has the least hyper-volume.
236 best = np.inf
237 for roll in range(len(current)):
238 stack = np.array([current, _roll(rectangle, roll)])
239 # we are going to combine two hyper-rect
240 # so we have `dim` choices on ways to split
241 # choose the split that minimizes the new hyper-volume
242 # the new AABB is going to be the `max` of the lengths
243 # on every dim except one which will be the `sum`
244 ch = np.tile(stack.max(axis=0), (len(current), 1))
245 np.fill_diagonal(ch, stack.sum(axis=0))
247 # choose the new AABB by which one minimizes hyper-volume
248 choice_prod = np.prod(ch, axis=1)
249 if choice_prod.min() < best:
250 choices = ch
251 choices_idx = choice_prod.argmin()
252 best = choice_prod[choices_idx]
253 if not rotate:
254 break
256 # we now know the full extent of the AABB
257 new_max = bounds[0] + choices[choices_idx]
259 # offset the new bounding box corner
260 new_min = bounds[0].copy()
261 new_min[choices_idx] += current[choices_idx]
263 # original bounds may be stretched
264 new_ori_max = np.vstack((bounds[1], new_max)).max(axis=0)
265 new_ori_max[choices_idx] = bounds[1][choices_idx]
267 assert (new_ori_max >= bounds[1]).all()
269 # the bounds containing the original sheet
270 bounds_ori = np.array([bounds[0], new_ori_max])
271 # the bounds containing the location to insert
272 # the new rectangle
273 bounds_ins = np.array([new_min, new_max])
275 # generate the new root node
276 new_root = RectangleBin([bounds[0], new_max])
277 # this node has children so it is occupied
278 new_root.occupied = True
279 # create a bin for both bounds
280 new_root.child = [RectangleBin(bounds_ori), RectangleBin(bounds_ins)]
282 # insert the original sheet into the new tree
283 root_offset = new_root.child[0].insert(np.ptp(bounds, axis=0), rotate=rotate)
284 # we sized the cells so original tree would fit
285 assert root_offset is not None
287 # existing inserts need to be moved
288 if not allclose(root_offset[0][0], 0.0):
289 offset[consume] += root_offset[0][0]
291 # insert the child that didn't fit before into the other child
292 child = new_root.child[1].insert(rectangle, rotate=rotate)
293 # since we re-sized the cells to fit insertion should always work
294 assert child is not None
296 offset[index] = child
297 consume[index] = True
298 # subsume the existing tree into a new root
299 root = new_root
301 elif inserted is not None:
302 # we successfully inserted
303 offset[index] = inserted
304 consume[index] = True
306 if tol.strict:
307 # in tests make sure we've never returned overlapping bounds
308 assert not bounds_overlap(offset[consume])
310 return offset[consume], consume
313def paths(paths, **kwargs):
314 """
315 Pack a list of Path2D objects into a rectangle.
317 Parameters
318 ------------
319 paths: (n,) Path2D
320 Geometry to be packed
322 Returns
323 ------------
324 packed : trimesh.path.Path2D
325 All paths packed into a single path object.
326 transforms : (m, 3, 3) float
327 Homogeneous transforms to move paths from their
328 original position to the new one.
329 consume : (n,) bool
330 Which of the original paths were inserted,
331 i.e. `consume.sum() == m`
332 """
333 from .util import concatenate
335 # pack using exterior polygon which will have the
336 # oriented bounding box calculated before packing
337 packable = []
338 original = []
339 for index, path in enumerate(paths):
340 quantity = path.metadata.get("quantity", 1)
341 original.extend([index] * quantity)
342 packable.extend([path.polygons_closed[path.root[0]]] * quantity)
344 # pack the polygons using rectangular bin packing
345 transforms, consume = polygons(polygons=packable, **kwargs)
347 positioned = []
348 for index, matrix in zip(np.nonzero(consume)[0], transforms):
349 current = paths[original[index]].copy()
350 current.apply_transform(matrix)
351 positioned.append(current)
353 # append all packed paths into a single Path object
354 packed = concatenate(positioned)
356 return packed, transforms, consume
359def polygons(polygons, **kwargs):
360 """
361 Pack polygons into a rectangle by taking each Polygon's OBB
362 and then packing that as a rectangle.
364 Parameters
365 ------------
366 polygons : (n,) shapely.geometry.Polygon
367 Source geometry
368 **kwargs : dict
369 Passed through to `packing.rectangles`.
371 Returns
372 -------------
373 transforms : (m, 3, 3) float
374 Homogeonous transforms from original frame to
375 packed frame.
376 consume : (n,) bool
377 Which of the original polygons was packed,
378 i.e. `consume.sum() == m`
379 """
381 from .polygons import polygon_bounds, polygons_obb
383 # find the oriented bounding box of the polygons
384 obb, extents = polygons_obb(polygons)
386 # run packing for a number of iterations
387 bounds, consume = rectangles(extents=extents, **kwargs)
389 log.debug("%i/%i parts were packed successfully", consume.sum(), len(polygons))
391 # transformations to packed positions
392 roll = roll_transform(bounds=bounds, extents=extents[consume])
394 transforms = np.array([np.dot(b, a) for a, b in zip(obb[consume], roll)])
396 if tol.strict:
397 # original bounds should not overlap
398 assert not bounds_overlap(bounds)
399 # confirm transfor
400 check_bound = np.array(
401 [
402 polygon_bounds(polygons[index], matrix=m)
403 for index, m in zip(np.nonzero(consume)[0], transforms)
404 ]
405 )
406 assert not bounds_overlap(check_bound)
408 return transforms, consume
411def rectangles(
412 extents,
413 size=None,
414 density_escape=0.99,
415 spacing=None,
416 iterations=50,
417 rotate=True,
418 quanta=None,
419 seed=None,
420):
421 """
422 Run multiple iterations of rectangle packing, this is the
423 core function for all rectangular packing.
425 Parameters
426 ------------
427 extents : (n, dimension) float
428 Size of hyper-rectangle to be packed
429 size : None or (dimension,) float
430 Size of sheet to pack onto. If not passed tree will be allowed
431 to create new volume-minimizing parent nodes.
432 density_escape : float
433 Exit early if rectangular density is above this threshold.
434 spacing : float
435 Distance to allow between rectangles
436 iterations : int
437 Number of iterations to run
438 rotate : bool
439 Allow right angle rotations or not.
440 quanta : None or float
441 Discrete "snap" interval.
442 seed
443 If deterministic results are needed seed the RNG here.
445 Returns
446 ---------
447 bounds : (m, 2, dimension) float
448 Axis aligned bounding boxes of inserted hyper-rectangle.
449 inserted : (n,) bool
450 Which of the original rect were packed.
451 """
452 # copy extents and make sure they are floats
453 extents = np.array(extents, dtype=np.float64)
454 dim = extents.shape[1]
456 if spacing is not None:
457 # add on any requested spacing
458 extents += spacing * 2.0
460 # hyper-volume: area in 2D, volume in 3D, party in 4D
461 area = np.prod(extents, axis=1)
462 # best density percentage in 0.0 - 1.0
463 best_density = 0.0
464 # how many rect were inserted
465 best_count = 0
467 if seed is None:
468 random = None
469 else:
470 random = np.random.default_rng(seed=seed)
472 for i in range(iterations):
473 # run a single insertion order
474 # don't shuffle the first run, shuffle subsequent runs
475 bounds, insert = rectangles_single(
476 extents=extents, size=size, shuffle=(i != 0), rotate=rotate, random=random
477 )
479 count = insert.sum()
480 extents_all = np.ptp(bounds.reshape((-1, dim)), axis=0)
482 if quanta is not None:
483 # compute the density using an upsized quanta
484 extents = np.ceil(extents_all / quanta) * quanta
486 # calculate the packing density
487 density = area[insert].sum() / np.prod(extents_all)
489 # compare this packing density against our best
490 if density > best_density or count > best_count:
491 best_density = density
492 best_count = count
493 # save the result
494 result = [bounds, insert]
495 # exit early if everything is inserted and
496 # we have exceeded our target density
497 if density > density_escape and insert.all():
498 break
500 if spacing is not None:
501 # shrink the bounds by spacing
502 result[0] += [[[spacing], [-spacing]]]
504 log.debug(f"{iterations} iterations packed with density {best_density:0.3f}")
506 return result
509def images(
510 images,
511 power_resize: bool = False,
512 deduplicate: bool = False,
513 iterations: Integer | None = 50,
514 seed: Integer | None = None,
515 spacing: Number | None = None,
516 mode: str | None = None,
517):
518 """
519 Pack a list of images and return result and offsets.
521 Parameters
522 ------------
523 images : (n,) PIL.Image
524 Images to be packed
525 power_resize : bool
526 Should the result image be upsized to the nearest
527 power of two? Not every GPU supports materials that
528 aren't a power of two size.
529 deduplicate
530 Should images that have identical hashes be inserted
531 more than once?
532 mode
533 If passed return an output image with the
534 requested mode, otherwise will be picked
535 from the input images.
537 Returns
538 -----------
539 packed : PIL.Image
540 Multiple images packed into result
541 offsets : (n, 2) int
542 Offsets for original image to pack
543 """
544 from PIL import Image
546 if deduplicate:
547 # only pack duplicate images once
548 _, index, inverse = np.unique(
549 [hash(i.tobytes()) for i in images], return_index=True, return_inverse=True
550 )
551 # use the number of pixels as the rectangle size
552 bounds, insert = rectangles(
553 extents=[images[i].size for i in index],
554 rotate=False,
555 iterations=iterations,
556 seed=seed,
557 spacing=spacing,
558 )
559 # really should have inserted all the rect
560 assert insert.all()
561 # re-index bounds back to original indexes
562 bounds = bounds[inverse]
563 assert np.allclose(np.ptp(bounds, axis=1), [i.size for i in images])
564 else:
565 # use the number of pixels as the rectangle size
566 bounds, insert = rectangles(
567 extents=[i.size for i in images],
568 rotate=False,
569 iterations=iterations,
570 seed=seed,
571 spacing=spacing,
572 )
573 # really should have inserted all the rect
574 assert insert.all()
576 if spacing is None:
577 spacing = 0
578 else:
579 spacing = int(spacing)
581 # offsets should be integer multiple of pizels
582 offset = bounds[:, 0].round().astype(int)
583 extents = np.ptp(bounds.reshape((-1, 2)), axis=0) + (spacing * 2)
584 size = extents.round().astype(int)
585 if power_resize:
586 # round up all dimensions to powers of 2
587 size = (2 ** np.ceil(np.log2(size))).astype(np.int64)
589 if mode is None:
590 # get the mode of every input image
591 modes = list({i.mode for i in images})
592 # pick the longest mode as a simple heuristic
593 # which prefers "RGBA" over "RGB"
594 mode = modes[np.argmax([len(m) for m in modes])]
596 # create the image in the mode of the first image
597 result = Image.new(mode, tuple(size))
599 done = set()
600 # paste each image into the result
601 for img, off in zip(images, offset):
602 if tuple(off) not in done:
603 # box is upper left corner
604 corner = (off[0], size[1] - img.size[1] - off[1])
605 result.paste(img, box=corner)
606 else:
607 done.add(tuple(off))
609 return result, offset
612def meshes(meshes, **kwargs):
613 """
614 Pack 3D meshes into a rectangular volume using box packing.
616 Parameters
617 ------------
618 meshes : (n,) trimesh.Trimesh
619 Input geometry to pack
620 **kwargs : dict
621 Passed to `packing.rectangles`
623 Returns
624 ------------
625 placed : (m,) trimesh.Trimesh
626 Meshes moved into the rectangular volume.
627 transforms : (m, 4, 4) float
628 Homogeneous transform moving mesh from original
629 position to being packed in a rectangular volume.
630 consume : (n,) bool
631 Which of the original meshes were inserted,
632 i.e. `consume.sum() == m`
633 """
634 # pack meshes relative to their oriented bounding boxes
635 obbs = [i.bounding_box_oriented for i in meshes]
636 obb_extent = np.array([i.primitive.extents for i in obbs])
637 obb_transform = np.array([o.primitive.transform for o in obbs])
639 # run packing
640 bounds, consume = rectangles(obb_extent, **kwargs)
642 # generate the transforms from an origin centered AABB
643 # to the final placed and rotated AABB
644 transforms = np.array(
645 [
646 np.dot(r, np.linalg.inv(o))
647 for o, r in zip(
648 obb_transform[consume],
649 roll_transform(bounds=bounds, extents=obb_extent[consume]),
650 )
651 ],
652 dtype=np.float64,
653 )
655 # copy the meshes and move into position
656 placed = [
657 meshes[index].copy().apply_transform(T)
658 for index, T in zip(np.nonzero(consume)[0], transforms)
659 ]
661 return placed, transforms, consume
664def visualize(extents, bounds):
665 """
666 Visualize a 3D box packing.
668 Parameters
669 ------------
670 extents : (n, 3) float
671 AABB size before packing.
672 bounds : (n, 2, 3) float
673 AABB location after packing.
675 Returns
676 ------------
677 scene : trimesh.Scene
678 Scene with boxes at requested locations.
679 """
680 from ..creation import box
681 from ..scene import Scene
682 from ..visual import random_color
684 # use a roll transform to verify extents
685 transforms = roll_transform(bounds=bounds, extents=extents)
686 meshes = [box(extents=e) for e in extents]
688 for m, matrix, check in zip(meshes, transforms, bounds):
689 m.apply_transform(matrix)
690 assert np.allclose(m.bounds, check)
691 m.visual.face_colors = random_color()
692 return Scene(meshes)
695def roll_transform(bounds: ArrayLike, extents: ArrayLike) -> NDArray[float64]:
696 """
697 Packing returns rotations with integer "roll" which
698 needs to be converted into a homogeneous rotation matrix.
700 Currently supports `dimension=2` and `dimension=3`.
702 Parameters
703 --------------
704 bounds : (n, 2, dimension) float
705 Axis aligned bounding boxes of packed position
706 extents : (n, dimension) float
707 Original pre-rolled extents will be used
708 to determine rotation to move to `bounds`.
710 Returns
711 ----------
712 transforms : (n, dimension + 1, dimension + 1) float
713 Homogeneous transformation to move cuboid at the origin
714 into the position determined by `bounds`.
715 """
716 if len(bounds) != len(extents):
717 raise ValueError("`bounds` must match `extents`")
718 if len(extents) == 0:
719 return []
721 # find the size of the AABB of the passed bounds
722 passed = np.ptp(bounds, axis=1)
723 # zeroth index is 2D, `1` is 3D
724 dimension = passed.shape[1]
726 # store the resulting transformation matrices
727 result = np.tile(np.eye(dimension + 1), (len(bounds), 1, 1))
729 # a lookup table for rotations for rolling cuboiods
730 # as `lookup[dimension - 2][roll]`
731 # implemented for 2D and 3D
732 lookup = [
733 np.array(
734 [np.eye(3), np.array([[0.0, -1.0, 0.0], [1.0, 0.0, 0.0], [0.0, 0.0, 1.0]])]
735 ),
736 np.array(
737 [
738 np.eye(4),
739 [
740 [-0.0, -0.0, -1.0, -0.0],
741 [-1.0, -0.0, -0.0, -0.0],
742 [0.0, 1.0, 0.0, 0.0],
743 [0.0, 0.0, 0.0, 1.0],
744 ],
745 [
746 [-0.0, -1.0, -0.0, -0.0],
747 [0.0, 0.0, 1.0, 0.0],
748 [-1.0, -0.0, -0.0, -0.0],
749 [0.0, 0.0, 0.0, 1.0],
750 ],
751 ]
752 ),
753 ]
755 # rectangular rotation involves rolling
756 for roll in range(extents.shape[1]):
757 # find all the passed bounding boxes represented by
758 # rolling the original extents by this amount
759 rolled = np.roll(extents, roll, axis=1)
760 # check to see if the rolled original extents
761 # match the requested bounding box
762 ok = np.ptp((passed - rolled), axis=1) < _TOL_ZERO
763 if not ok.any():
764 continue
766 # the base rotation for this
767 mat = lookup[dimension - 2][roll]
768 # the lower corner of the AABB plus the rolled extent
769 offset = np.tile(np.eye(dimension + 1), (ok.sum(), 1, 1))
770 offset[:, :dimension, dimension] = bounds[:, 0][ok] + rolled[ok] / 2.0
771 result[ok] = [np.dot(o, mat) for o in offset]
773 if tol.strict:
774 if dimension == 3:
775 # make sure bounds match inputs
776 from ..creation import box
778 assert all(
779 allclose(box(extents=e).apply_transform(m).bounds, b)
780 for b, e, m in zip(bounds, extents, result)
781 )
782 elif dimension == 2:
783 # in 2D check with a rectangle
784 from .creation import rectangle
786 assert all(
787 allclose(rectangle(bounds=[-e / 2, e / 2]).apply_transform(m).bounds, b)
788 for b, e, m in zip(bounds, extents, result)
789 )
790 else:
791 raise ValueError("unsupported dimension")
793 return result
796def bounds_overlap(bounds, epsilon=1e-8):
797 """
798 Check to see if multiple axis-aligned bounding boxes
799 contains overlaps using `rtree`.
801 Parameters
802 ------------
803 bounds : (n, 2, dimension) float
804 Axis aligned bounding boxes
805 epsilon : float
806 Amount to shrink AABB to avoid spurious floating
807 point hits.
809 Returns
810 --------------
811 overlap : bool
812 True if any bound intersects any other bound.
813 """
814 # pad AABB by epsilon for deterministic intersections
815 padded = np.array(bounds) + np.reshape([epsilon, -epsilon], (1, 2, 1))
816 tree = bounds_tree(padded)
817 # every returned AABB should not overlap with any other AABB
818 return any(
819 set(tree.intersection(current.ravel())) != {i} for i, current in enumerate(bounds)
820 )