Packing Behaviour

[lassade]

Hi! while trying to pack a bunch of glyphs inside a rectangle I notice this strange behaviour where my atlas will start be filled in the diagonal, from the top left to the bottom right and then branching to the sides, is that the right behaviour?

I also reach a point where the packing whould give an not enough space error, but visually having quite a bit of space to spare. For instance in the next example I can't pack everything together into a single atlas. What is happening?

Rectangle Pack Results (warning! very white images)

In contrast using a skyline heuristic (from texture_packer) I got mutch better results, using the same settings

Skyline Results

[lassade]

Ok I think I know what is happening.

Since the current implementation doesn't handle rotation it gives the impression of filling along the diagonal first but the packer just doesn't do that.

The packer is working as intended, is just it can't deal with an unsorted input very well in this particular case, the rectpack2D uses a function that tries different input sortings to maximize the packing efficiency.

There is some weird input data out there...

[chinedufn]

Thanks for looking into this!

Since the current implementation doesn't handle rotation it gives the impression of filling along the diagonal first but the packer just doesn't do that.

I'd be happy to review a PR that adds rotation support. If you only need 2D rotation then we would just need Z-axis rotation support.

the rectpack2D uses a function that tries different input sortings to maximize the packing efficiency.

rectangle-pack intentionally gives the user control of the heuristics used when packing.

We take in two functions that allow you to control how things are placed.

If you want to try multiple algorithms, you can just run multiple pack multiple times with different passed in heuristic functions.

rectangle-pack/src/lib.rs

Lines 139 to 140 in de824b1

	box_size_heuristic: &BoxSizeHeuristicFn,
	more_suitable_containers_fn: &ComparePotentialContainersFn,

To match rectpack2d you would run rectangle-pack six times so that you could compare using the 6 different algorithms that rectpack2d uses (the user would need to provide the algorithm themself. I would also be open to a PR that exposes common heuristics)

rectangle-pack/src/box_size_heuristics.rs

Lines 10 to 13 in 99774a4

	/// The volume of the box
	pub fn volume_heuristic(whd: WidthHeightDepth) -> u128 {
	whd.width as u128 * whd.height as u128 * whd.depth as u128
	}

rectangle-pack/src/bin_section.rs

Lines 27 to 42 in de824b1

	/// Select the container that has the smallest box.
	///
	/// If there is a tie on the smallest boxes, select whichever also has the second smallest box.
	pub fn contains_smallest_box(
	mut container1: [WidthHeightDepth; 3],
	mut container2: [WidthHeightDepth; 3],
	heuristic: &BoxSizeHeuristicFn,
	) -> Ordering {
	container1.sort_by(|a, b| heuristic(*a).cmp(&heuristic(*b)));
	container2.sort_by(|a, b| heuristic(*a).cmp(&heuristic(*b)));
	match heuristic(container2[0]).cmp(&heuristic(container1[0])) {
	Ordering::Equal => heuristic(container2[1]).cmp(&heuristic(container1[1])),
	o => o,
	}
	}

---

After you ran it six times you would need to compare the 6 to see which was packed the tightest.

This part isn't possible yet, but I'd be happy to review a PR that implements it.

https://github.com/chinedufn/rectangle-pack#stats-on-how-the-bins-were-packed

---

Thanks for opening this issue! Let me know if you're interested in any of the above and I'd be happy to provide any guidance needed on how to implement it.

Cheers!

[lassade]

hi chinedufn! Thanks for writing this crate, but I'm going in another direction.