voxelman.geometry.rectbinpacker source code

1 /**
2 Copyright: Copyright (c) 2013-2018 Andrey Penechko.
3 License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0).
4 Authors: Andrey Penechko.
5 */
6 
7 /// Rewrite of Jukka Jylanki's RectangleBinPacker
8 module voxelman.geometry.rectbinpacker;
9 
10 import voxelman.math;
11 
12 struct Node
13 {
14 	irect rect;
15 	Node* left, right;
16 }
17 
18 struct RectBinPacker
19 {
20 	this(in uint width, in uint height, in uint x = 0, in uint y = 0)
21 	{
22 		binWidth = width;
23 		binHeight = height;
24 		root.left = root.right = null;
25 		root.rect.x = x;
26 		root.rect.y = y;
27 		root.rect.width = width;
28 		root.rect.height = height;
29 	}
30 
31 	/**
32 	 * Running time is linear to the number of rectangles already packed. Recursively calls itself.
33 	 * @Returns: null If the insertion didn't succeed.
34 	 */
35 	Node* insert(ivec2 size)
36 	{
37 		return insert(&root, size.x, size.y);
38 	}
39 
40 	/++
41 	 + @Returns: A value [0, 1] denoting the ratio of total surface area that is in use.
42 	 + 0.0f - the bin is totally empty, 1.0f - the bin is full.
43 	 +/
44 	float occupancy()
45 	{
46 		ulong totalSurfaceArea = binWidth * binHeight;
47 		ulong area = usedSurfaceArea(&root);
48 
49 		return cast(float)area/totalSurfaceArea;
50 	}
51 
52 private:
53 
54 	uint binWidth;
55 	uint binHeight;
56 
57 	Node root;
58 
59 	Node* insert(Node* node, in uint width, in uint height)
60 	{
61 		if (node.left !is null || node.right !is null)
62 		{
63 			if (node.left !is null)
64 			{
65 				Node* newNode = insert(node.left, width, height);
66 				if (newNode)
67 					return newNode;
68 			}
69 			if (node.right !is null)
70 			{
71 				Node* newNode = insert(node.right, width, height);
72 				if (newNode !is null)
73 					return newNode;
74 			}
75 			return null; // Didn't fit into either subtree!
76 		}
77 
78 		if (width > node.rect.width || height > node.rect.height)
79 			return null; // no space.
80 
81 		int w = node.rect.width - width;
82 		int h = node.rect.height - height;
83 
84 		node.left = new Node();
85 		node.right = new Node();
86 
87 		if (w <= h) // Split the remaining space in horizontal direction.
88 		{
89 			node.left.rect.x = node.rect.x + width;
90 			node.left.rect.y = node.rect.y;
91 			node.left.rect.width = w;
92 			node.left.rect.height = height;
93 
94 			node.right.rect.x = node.rect.x;
95 			node.right.rect.y = node.rect.y + height;
96 			node.right.rect.width = node.rect.width;
97 			node.right.rect.height = h;
98 		}
99 		else // Split the remaining space in vertical direction.
100 		{
101 			node.left.rect.x = node.rect.x;
102 			node.left.rect.y = node.rect.y + height;
103 			node.left.rect.width = width;
104 			node.left.rect.height = h;
105 
106 			node.right.rect.x = node.rect.x + width;
107 			node.right.rect.y = node.rect.y;
108 			node.right.rect.width = w;
109 			node.right.rect.height = node.rect.height;
110 		}
111 
112 		node.rect.width = width;
113 		node.rect.height = height;
114 		return node;
115 	}
116 
117 	ulong usedSurfaceArea(Node* node) const
118 	{
119 		if (node.left || node.right)
120 		{
121 			ulong result = node.rect.width * node.rect.height;
122 
123 			if (node.left !is null)
124 			{
125 				result += usedSurfaceArea(node.left);
126 			}
127 			if (node.right !is null)
128 			{
129 				result += usedSurfaceArea(node.right);
130 			}
131 
132 			return result;
133 		}
134 
135 		// This is a leaf node, it doesn't constitute to the total surface area.
136 		return 0;
137 	}
138 }