Coverage for trimesh/path/packing.py: 94%
238 statements
« prev ^ index » next coverage.py v7.14.1, created at 2026-07-31 23:55 +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, Seed, float64
12from ..util import allclose, bounds_tree, random_generator
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(
164 extents, size=None, shuffle=False, rotate=True, random: Seed = None
165):
166 """
167 Execute a single insertion order of smaller rectangles onto
168 a larger rectangle using a binary space partition tree.
170 Parameters
171 ----------
172 extents : (n, dimension) float
173 The size of the hyper-rectangles to pack.
174 size : None or (dim,) float
175 Maximum size of container to pack onto.
176 If not passed it will re-root the tree when items
177 larger than any available node are inserted.
178 shuffle : bool
179 Whether or not to shuffle the insert order of the
180 smaller rectangles, as the final packing density depends
181 on insertion order.
182 rotate : bool
183 If True, allow integer-roll rotation.
184 random : None or int or numpy.random.Generator
185 Source for the shuffle, pass a `Generator` to draw from
186 one stream across repeated calls.
188 Returns
189 ---------
190 bounds : (m, 2, dim) float
191 Axis aligned resulting bounds in space
192 transforms : (m, dim + 1, dim + 1) float
193 Homogeneous transformation including rotation.
194 consume : (n,) bool
195 Which of the original rectangles were packed,
196 i.e. `consume.sum() == m`
197 """
199 extents = np.asanyarray(extents, dtype=np.float64)
200 dimension = extents.shape[1]
201 # the return arrays
202 offset = np.zeros((len(extents), 2, dimension))
203 consume = np.zeros(len(extents), dtype=bool)
204 # start by ordering them by maximum length
205 order = np.argsort(extents.max(axis=1))[::-1]
207 if shuffle:
208 # reorder with permutations
209 order = random_generator(random).permutation(order)
211 if size is None:
212 # if no bounds are passed start it with the size of a large
213 # rectangle exactly which will require re-rooting for
214 # subsequent insertions
215 root_bounds = [[0.0] * dimension, extents[np.ptp(extents, axis=1).argmax()]]
216 else:
217 # restrict the bounds to passed size and disallow re-rooting
218 root_bounds = [[0.0] * dimension, size]
220 # the current root node to insert each rectangle
221 root = RectangleBin(bounds=root_bounds)
223 for index in order:
224 # the current rectangle to be inserted
225 rectangle = extents[index]
226 # try to insert the hyper-rectangle into children
227 inserted = root.insert(rectangle, rotate=rotate)
229 if inserted is None and size is None:
230 # we failed to insert into children
231 # so we need to create a new parent
232 # get the size of the current root node
233 bounds = root.bounds
234 # current extents
235 current = np.ptp(bounds, axis=0)
237 # pick the direction which has the least hyper-volume.
238 best = np.inf
239 for roll in range(len(current)):
240 stack = np.array([current, _roll(rectangle, roll)])
241 # we are going to combine two hyper-rect
242 # so we have `dim` choices on ways to split
243 # choose the split that minimizes the new hyper-volume
244 # the new AABB is going to be the `max` of the lengths
245 # on every dim except one which will be the `sum`
246 ch = np.tile(stack.max(axis=0), (len(current), 1))
247 np.fill_diagonal(ch, stack.sum(axis=0))
249 # choose the new AABB by which one minimizes hyper-volume
250 choice_prod = np.prod(ch, axis=1)
251 if choice_prod.min() < best:
252 choices = ch
253 choices_idx = choice_prod.argmin()
254 best = choice_prod[choices_idx]
255 if not rotate:
256 break
258 # we now know the full extent of the AABB
259 new_max = bounds[0] + choices[choices_idx]
261 # offset the new bounding box corner
262 new_min = bounds[0].copy()
263 new_min[choices_idx] += current[choices_idx]
265 # original bounds may be stretched
266 new_ori_max = np.vstack((bounds[1], new_max)).max(axis=0)
267 new_ori_max[choices_idx] = bounds[1][choices_idx]
269 assert (new_ori_max >= bounds[1]).all()
271 # the bounds containing the original sheet
272 bounds_ori = np.array([bounds[0], new_ori_max])
273 # the bounds containing the location to insert
274 # the new rectangle
275 bounds_ins = np.array([new_min, new_max])
277 # generate the new root node
278 new_root = RectangleBin([bounds[0], new_max])
279 # this node has children so it is occupied
280 new_root.occupied = True
281 # create a bin for both bounds
282 new_root.child = [RectangleBin(bounds_ori), RectangleBin(bounds_ins)]
284 # insert the original sheet into the new tree
285 root_offset = new_root.child[0].insert(np.ptp(bounds, axis=0), rotate=rotate)
286 # we sized the cells so original tree would fit
287 assert root_offset is not None
289 # existing inserts need to be moved
290 if not allclose(root_offset[0][0], 0.0):
291 offset[consume] += root_offset[0][0]
293 # insert the child that didn't fit before into the other child
294 child = new_root.child[1].insert(rectangle, rotate=rotate)
295 # since we re-sized the cells to fit insertion should always work
296 assert child is not None
298 offset[index] = child
299 consume[index] = True
300 # subsume the existing tree into a new root
301 root = new_root
303 elif inserted is not None:
304 # we successfully inserted
305 offset[index] = inserted
306 consume[index] = True
308 if tol.strict:
309 # in tests make sure we've never returned overlapping bounds
310 assert not bounds_overlap(offset[consume])
312 return offset[consume], consume
315def paths(paths, **kwargs):
316 """
317 Pack a list of Path2D objects into a rectangle.
319 Parameters
320 ------------
321 paths: (n,) Path2D
322 Geometry to be packed
324 Returns
325 ------------
326 packed : trimesh.path.Path2D
327 All paths packed into a single path object.
328 transforms : (m, 3, 3) float
329 Homogeneous transforms to move paths from their
330 original position to the new one.
331 consume : (n,) bool
332 Which of the original paths were inserted,
333 i.e. `consume.sum() == m`
334 """
335 from .util import concatenate
337 # pack using exterior polygon which will have the
338 # oriented bounding box calculated before packing
339 packable = []
340 original = []
341 for index, path in enumerate(paths):
342 quantity = path.metadata.get("quantity", 1)
343 original.extend([index] * quantity)
344 packable.extend([path.polygons_closed[path.root[0]]] * quantity)
346 # pack the polygons using rectangular bin packing
347 transforms, consume = polygons(polygons=packable, **kwargs)
349 positioned = []
350 for index, matrix in zip(np.nonzero(consume)[0], transforms):
351 current = paths[original[index]].copy()
352 current.apply_transform(matrix)
353 positioned.append(current)
355 # append all packed paths into a single Path object
356 packed = concatenate(positioned)
358 return packed, transforms, consume
361def polygons(polygons, **kwargs):
362 """
363 Pack polygons into a rectangle by taking each Polygon's OBB
364 and then packing that as a rectangle.
366 Parameters
367 ------------
368 polygons : (n,) shapely.geometry.Polygon
369 Source geometry
370 **kwargs : dict
371 Passed through to `packing.rectangles`.
373 Returns
374 -------------
375 transforms : (m, 3, 3) float
376 Homogeonous transforms from original frame to
377 packed frame.
378 consume : (n,) bool
379 Which of the original polygons was packed,
380 i.e. `consume.sum() == m`
381 """
383 from .polygons import polygon_bounds, polygons_obb
385 # find the oriented bounding box of the polygons
386 obb, extents = polygons_obb(polygons)
388 # run packing for a number of iterations
389 bounds, consume = rectangles(extents=extents, **kwargs)
391 log.debug("%i/%i parts were packed successfully", consume.sum(), len(polygons))
393 # transformations to packed positions
394 roll = roll_transform(bounds=bounds, extents=extents[consume])
396 transforms = np.array([np.dot(b, a) for a, b in zip(obb[consume], roll)])
398 if tol.strict:
399 # original bounds should not overlap
400 assert not bounds_overlap(bounds)
401 # confirm transfor
402 check_bound = np.array(
403 [
404 polygon_bounds(polygons[index], matrix=m)
405 for index, m in zip(np.nonzero(consume)[0], transforms)
406 ]
407 )
408 assert not bounds_overlap(check_bound)
410 return transforms, consume
413def rectangles(
414 extents,
415 size=None,
416 density_escape=0.99,
417 spacing=None,
418 iterations=50,
419 rotate=True,
420 quanta=None,
421 seed: Seed = None,
422):
423 """
424 Run multiple iterations of rectangle packing, this is the
425 core function for all rectangular packing.
427 Parameters
428 ------------
429 extents : (n, dimension) float
430 Size of hyper-rectangle to be packed
431 size : None or (dimension,) float
432 Size of sheet to pack onto. If not passed tree will be allowed
433 to create new volume-minimizing parent nodes.
434 density_escape : float
435 Exit early if rectangular density is above this threshold.
436 spacing : float
437 Distance to allow between rectangles
438 iterations : int
439 Number of iterations to run
440 rotate : bool
441 Allow right angle rotations or not.
442 quanta : None or float
443 Discrete "snap" interval.
444 seed
445 If deterministic results are needed seed the RNG here.
447 Returns
448 ---------
449 bounds : (m, 2, dimension) float
450 Axis aligned bounding boxes of inserted hyper-rectangle.
451 inserted : (n,) bool
452 Which of the original rect were packed.
453 """
454 # copy extents and make sure they are floats
455 extents = np.array(extents, dtype=np.float64)
456 dim = extents.shape[1]
458 if spacing is not None:
459 # add on any requested spacing
460 extents += spacing * 2.0
462 # hyper-volume: area in 2D, volume in 3D, party in 4D
463 area = np.prod(extents, axis=1)
464 # best density percentage in 0.0 - 1.0
465 best_density = 0.0
466 # how many rect were inserted
467 best_count = 0
469 # hoist the generator so the loop below draws from one stream
470 # rather than re-collecting OS entropy on every iteration
471 random = random_generator(seed)
473 for i in range(iterations):
474 # run a single insertion order
475 # don't shuffle the first run, shuffle subsequent runs
476 bounds, insert = rectangles_single(
477 extents=extents, size=size, shuffle=(i != 0), rotate=rotate, random=random
478 )
480 count = insert.sum()
481 extents_all = np.ptp(bounds.reshape((-1, dim)), axis=0)
483 if quanta is not None:
484 # compute the density using an upsized quanta
485 extents = np.ceil(extents_all / quanta) * quanta
487 # calculate the packing density
488 density = area[insert].sum() / np.prod(extents_all)
490 # compare this packing density against our best
491 if density > best_density or count > best_count:
492 best_density = density
493 best_count = count
494 # save the result
495 result = [bounds, insert]
496 # exit early if everything is inserted and
497 # we have exceeded our target density
498 if density > density_escape and insert.all():
499 break
501 if spacing is not None:
502 # shrink the bounds by spacing
503 result[0] += [[[spacing], [-spacing]]]
505 log.debug(f"{iterations} iterations packed with density {best_density:0.3f}")
507 return result
510def images(
511 images,
512 power_resize: bool = False,
513 deduplicate: bool = False,
514 iterations: Integer | None = 50,
515 seed: Seed = None,
516 spacing: Number | None = None,
517 mode: str | None = None,
518):
519 """
520 Pack a list of images and return result and offsets.
522 Parameters
523 ------------
524 images : (n,) PIL.Image
525 Images to be packed
526 power_resize : bool
527 Should the result image be upsized to the nearest
528 power of two? Not every GPU supports materials that
529 aren't a power of two size.
530 deduplicate
531 Should images that have identical hashes be inserted
532 more than once?
533 mode
534 If passed return an output image with the
535 requested mode, otherwise will be picked
536 from the input images.
538 Returns
539 -----------
540 packed : PIL.Image
541 Multiple images packed into result
542 offsets : (n, 2) int
543 Offsets for original image to pack
544 """
545 from PIL import Image
547 if deduplicate:
548 # only pack duplicate images once
549 _, index, inverse = np.unique(
550 [hash(i.tobytes()) for i in images], return_index=True, return_inverse=True
551 )
552 # use the number of pixels as the rectangle size
553 bounds, insert = rectangles(
554 extents=[images[i].size for i in index],
555 rotate=False,
556 iterations=iterations,
557 seed=seed,
558 spacing=spacing,
559 )
560 # really should have inserted all the rect
561 assert insert.all()
562 # re-index bounds back to original indexes
563 bounds = bounds[inverse]
564 assert np.allclose(np.ptp(bounds, axis=1), [i.size for i in images])
565 else:
566 # use the number of pixels as the rectangle size
567 bounds, insert = rectangles(
568 extents=[i.size for i in images],
569 rotate=False,
570 iterations=iterations,
571 seed=seed,
572 spacing=spacing,
573 )
574 # really should have inserted all the rect
575 assert insert.all()
577 if spacing is None:
578 spacing = 0
579 else:
580 spacing = int(spacing)
582 # offsets should be integer multiple of pizels
583 offset = bounds[:, 0].round().astype(int)
584 extents = np.ptp(bounds.reshape((-1, 2)), axis=0) + (spacing * 2)
585 size = extents.round().astype(int)
586 if power_resize:
587 # round up all dimensions to powers of 2
588 size = (2 ** np.ceil(np.log2(size))).astype(np.int64)
590 if mode is None:
591 # get the mode of every input image
592 modes = list({i.mode for i in images})
593 # pick the longest mode as a simple heuristic
594 # which prefers "RGBA" over "RGB"
595 mode = modes[np.argmax([len(m) for m in modes])]
597 # create the image in the mode of the first image
598 result = Image.new(mode, tuple(size))
600 done = set()
601 # paste each image into the result
602 for img, off in zip(images, offset):
603 if tuple(off) not in done:
604 # box is upper left corner
605 corner = (off[0], size[1] - img.size[1] - off[1])
606 result.paste(img, box=corner)
607 else:
608 done.add(tuple(off))
610 return result, offset
613def meshes(meshes, **kwargs):
614 """
615 Pack 3D meshes into a rectangular volume using box packing.
617 Parameters
618 ------------
619 meshes : (n,) trimesh.Trimesh
620 Input geometry to pack
621 **kwargs : dict
622 Passed to `packing.rectangles`
624 Returns
625 ------------
626 placed : (m,) trimesh.Trimesh
627 Meshes moved into the rectangular volume.
628 transforms : (m, 4, 4) float
629 Homogeneous transform moving mesh from original
630 position to being packed in a rectangular volume.
631 consume : (n,) bool
632 Which of the original meshes were inserted,
633 i.e. `consume.sum() == m`
634 """
635 # pack meshes relative to their oriented bounding boxes
636 obbs = [i.bounding_box_oriented for i in meshes]
637 obb_extent = np.array([i.primitive.extents for i in obbs])
638 obb_transform = np.array([o.primitive.transform for o in obbs])
640 # run packing
641 bounds, consume = rectangles(obb_extent, **kwargs)
643 # generate the transforms from an origin centered AABB
644 # to the final placed and rotated AABB
645 transforms = np.array(
646 [
647 np.dot(r, np.linalg.inv(o))
648 for o, r in zip(
649 obb_transform[consume],
650 roll_transform(bounds=bounds, extents=obb_extent[consume]),
651 )
652 ],
653 dtype=np.float64,
654 )
656 # copy the meshes and move into position
657 placed = [
658 meshes[index].copy().apply_transform(T)
659 for index, T in zip(np.nonzero(consume)[0], transforms)
660 ]
662 return placed, transforms, consume
665def visualize(extents, bounds):
666 """
667 Visualize a 3D box packing.
669 Parameters
670 ------------
671 extents : (n, 3) float
672 AABB size before packing.
673 bounds : (n, 2, 3) float
674 AABB location after packing.
676 Returns
677 ------------
678 scene : trimesh.Scene
679 Scene with boxes at requested locations.
680 """
681 from ..creation import box
682 from ..scene import Scene
683 from ..visual import random_color
685 # use a roll transform to verify extents
686 transforms = roll_transform(bounds=bounds, extents=extents)
687 meshes = [box(extents=e) for e in extents]
689 for m, matrix, check in zip(meshes, transforms, bounds):
690 m.apply_transform(matrix)
691 assert np.allclose(m.bounds, check)
692 m.visual.face_colors = random_color()
693 return Scene(meshes)
696def roll_transform(bounds: ArrayLike, extents: ArrayLike) -> NDArray[float64]:
697 """
698 Packing returns rotations with integer "roll" which
699 needs to be converted into a homogeneous rotation matrix.
701 Currently supports `dimension=2` and `dimension=3`.
703 Parameters
704 --------------
705 bounds : (n, 2, dimension) float
706 Axis aligned bounding boxes of packed position
707 extents : (n, dimension) float
708 Original pre-rolled extents will be used
709 to determine rotation to move to `bounds`.
711 Returns
712 ----------
713 transforms : (n, dimension + 1, dimension + 1) float
714 Homogeneous transformation to move cuboid at the origin
715 into the position determined by `bounds`.
716 """
717 if len(bounds) != len(extents):
718 raise ValueError("`bounds` must match `extents`")
719 if len(extents) == 0:
720 return []
722 # find the size of the AABB of the passed bounds
723 passed = np.ptp(bounds, axis=1)
724 # zeroth index is 2D, `1` is 3D
725 dimension = passed.shape[1]
727 # store the resulting transformation matrices
728 result = np.tile(np.eye(dimension + 1), (len(bounds), 1, 1))
730 # a lookup table for rotations for rolling cuboiods
731 # as `lookup[dimension - 2][roll]`
732 # implemented for 2D and 3D
733 lookup = [
734 np.array(
735 [np.eye(3), np.array([[0.0, -1.0, 0.0], [1.0, 0.0, 0.0], [0.0, 0.0, 1.0]])]
736 ),
737 np.array(
738 [
739 np.eye(4),
740 [
741 [-0.0, -0.0, -1.0, -0.0],
742 [-1.0, -0.0, -0.0, -0.0],
743 [0.0, 1.0, 0.0, 0.0],
744 [0.0, 0.0, 0.0, 1.0],
745 ],
746 [
747 [-0.0, -1.0, -0.0, -0.0],
748 [0.0, 0.0, 1.0, 0.0],
749 [-1.0, -0.0, -0.0, -0.0],
750 [0.0, 0.0, 0.0, 1.0],
751 ],
752 ]
753 ),
754 ]
756 # rectangular rotation involves rolling
757 for roll in range(extents.shape[1]):
758 # find all the passed bounding boxes represented by
759 # rolling the original extents by this amount
760 rolled = np.roll(extents, roll, axis=1)
761 # check to see if the rolled original extents
762 # match the requested bounding box
763 ok = np.ptp((passed - rolled), axis=1) < _TOL_ZERO
764 if not ok.any():
765 continue
767 # the base rotation for this
768 mat = lookup[dimension - 2][roll]
769 # the lower corner of the AABB plus the rolled extent
770 offset = np.tile(np.eye(dimension + 1), (ok.sum(), 1, 1))
771 offset[:, :dimension, dimension] = bounds[:, 0][ok] + rolled[ok] / 2.0
772 result[ok] = [np.dot(o, mat) for o in offset]
774 if tol.strict:
775 if dimension == 3:
776 # make sure bounds match inputs
777 from ..creation import box
779 assert all(
780 allclose(box(extents=e).apply_transform(m).bounds, b)
781 for b, e, m in zip(bounds, extents, result)
782 )
783 elif dimension == 2:
784 # in 2D check with a rectangle
785 from .creation import rectangle
787 assert all(
788 allclose(rectangle(bounds=[-e / 2, e / 2]).apply_transform(m).bounds, b)
789 for b, e, m in zip(bounds, extents, result)
790 )
791 else:
792 raise ValueError("unsupported dimension")
794 return result
797def bounds_overlap(bounds, epsilon=1e-8):
798 """
799 Check to see if multiple axis-aligned bounding boxes
800 contains overlaps using `rtree`.
802 Parameters
803 ------------
804 bounds : (n, 2, dimension) float
805 Axis aligned bounding boxes
806 epsilon : float
807 Amount to shrink AABB to avoid spurious floating
808 point hits.
810 Returns
811 --------------
812 overlap : bool
813 True if any bound intersects any other bound.
814 """
815 # pad AABB by epsilon for deterministic intersections
816 padded = np.array(bounds) + np.reshape([epsilon, -epsilon], (1, 2, 1))
817 tree = bounds_tree(padded)
818 # every returned AABB should not overlap with any other AABB
819 return any(
820 set(tree.intersection(current.ravel())) != {i} for i, current in enumerate(bounds)
821 )