summaryrefslogtreecommitdiffstatshomepage
path: root/src/osd/modules/render/binpacker.h
blob: 55bd03116e5171a6ec6750006927cdaa232c7018 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
// license:BSD-3-Clause
// copyright-holders:Ryan Holtz
#pragma once

#ifndef __RECTPACKER_H__
#define __RECTPACKER_H__


#include <vector>

class rectangle_packer
{
public:
	// The input and output are in terms of vectors of ints to avoid
	// dependencies (although I suppose a public member struct could have been
	// used). The parameters are:

	// packs : After packing, the outer array contains the packs (therefore
	// the number of packs is packs.size()). Each inner array contains a
	// sequence of sets of 3 ints. Each set represents a rectangle in the
	// pack. The elements in the set are 1) the rect ID, 2) the x position
	// of the rect with respect to the pack, and 3) the y position of the rect
	// with respect to the pack. The widths and heights of the rects are not
	// included, as it's assumed they are stored on the caller's side (they
	// were after all the input to the function).

	class packable_rectangle
	{
	public:
		packable_rectangle() : m_hash(0), m_width(-1), m_height(-1) { }
		packable_rectangle(uint32_t hash, uint32_t format, int width, int height, int rowpixels, const rgb_t *palette, void *base)
			: m_hash(hash)
			, m_format(format)
			, m_width(width)
			, m_height(height)
			, m_rowpixels(rowpixels)
			, m_palette(palette)
			, m_base(base)
		{
		}

		uint32_t hash() const { return m_hash; }
		uint32_t format() const { return m_format; }
		int width() const { return m_width; }
		int height() const { return m_height; }
		int rowpixels() const { return m_rowpixels; }
		const rgb_t* palette() const { return m_palette; }
		void* base() const { return m_base; }

	private:
		uint32_t m_hash;
		uint32_t m_format;
		int m_width;
		int m_height;
		int m_rowpixels;
		const rgb_t* m_palette;
		void* m_base;
	};

	class packed_rectangle
	{
	public:
		packed_rectangle() : m_hash(0), m_format(0), m_width(-1), m_height(-1), m_x(-1), m_y(-1), m_rowpixels(0), m_palette(nullptr), m_base(nullptr) { }
		packed_rectangle(const packed_rectangle& rect)
			: m_hash(rect.m_hash)
			, m_format(rect.m_format)
			, m_width(rect.m_width)
			, m_height(rect.m_height)
			, m_x(rect.m_x)
			, m_y(rect.m_y)
			, m_rowpixels(rect.m_rowpixels)
			, m_palette(rect.m_palette)
			, m_base(rect.m_base)
		{
		}
		packed_rectangle(uint32_t hash, uint32_t format, int width, int height, int x, int y, int rowpixels, const rgb_t *palette, void *base)
			: m_hash(hash)
			, m_format(format)
			, m_width(width)
			, m_height(height)
			, m_x(x)
			, m_y(y)
			, m_rowpixels(rowpixels)
			, m_palette(palette)
			, m_base(base)
		{
		}

		uint32_t hash() const { return m_hash; }
		uint32_t format() const { return m_format; }
		int width() const { return m_width; }
		int height() const { return m_height; }
		int x() const { return m_x; }
		int y() const { return m_y; }
		int rowpixels() const { return m_rowpixels; }
		const rgb_t* palette() const { return m_palette; }
		void* base() const { return m_base; }

	private:
		uint32_t m_hash;
		uint32_t m_format;
		int m_width;
		int m_height;
		int m_x;
		int m_y;
		int m_rowpixels;
		const rgb_t* m_palette;
		void* m_base;
	};

	bool pack(const std::vector<packable_rectangle>& rects, std::vector<std::vector<packed_rectangle>>& packs, int pack_size);

private:
	struct rectangle
	{
		rectangle(int size)
			: x(0)
			, y(0)
			, w(size)
			, h(size)
			, hash(-1)
			, format(0)
			, rowpixels(0)
			, palette(nullptr)
			, base(nullptr)
			, packed(false)
		{
			children[0] = -1;
			children[1] = -1;
		}

		rectangle(int x, int y, int w, int h, int hash, uint32_t format, int rowpixels, const rgb_t *palette, void *base)
			: x(x)
			, y(y)
			, w(w)
			, h(h)
			, hash(hash)
			, format(format)
			, rowpixels(rowpixels)
			, palette(palette)
			, base(base)
			, packed(false)
		{
			children[0] = -1;
			children[1] = -1;
		}

		int get_area() const
		{
			return w * h;
		}

		bool operator<(const rectangle& rect) const
		{
			return get_area() < rect.get_area();
		}

		int             x;
		int             y;
		int             w;
		int             h;
		int             hash;
		uint32_t          format;
		int             rowpixels;
		const rgb_t*    palette;
		void*           base;
		int             children[2];
		bool            packed;
	};

	void clear();
	bool fill(int pack);
	void split(int pack, int rect);
	bool fits(rectangle& rect1, const rectangle& rect2);
	void add_pack_to_array(int pack, std::vector<packed_rectangle>& array) const;

	int                     m_pack_size;
	int                     m_num_packed;
	std::vector<rectangle>  m_rects;
	std::vector<rectangle>  m_packs;
	std::vector<int>        m_roots;
};

#endif // __RECTPACKER_H__