1// LAF Gfx Library
2// Copyright (C) 2019 Igara Studio S.A.
3// Copyright (C) 2001-2014 David Capello
4//
5// This file is released under the terms of the MIT license.
6// Read LICENSE.txt for more information.
7
8#ifdef HAVE_CONFIG_H
9#include "config.h"
10#endif
11
12#include "gfx/packing_rects.h"
13
14#include "gfx/region.h"
15#include "gfx/size.h"
16
17namespace gfx {
18
19void PackingRects::add(const Size& sz)
20{
21 m_rects.push_back(Rect(sz));
22}
23
24void PackingRects::add(const Rect& rc)
25{
26 m_rects.push_back(rc);
27}
28
29Size PackingRects::bestFit(base::task_token& token,
30 const int fixedWidth,
31 const int fixedHeight)
32{
33 Size size(fixedWidth, fixedHeight);
34
35 // Nothing to do, the size is already specified
36 if (fixedWidth > 0 && fixedHeight > 0)
37 return size;
38
39 // Calculate the amount of pixels that we need, the texture cannot
40 // be smaller than that.
41 int neededArea = 0;
42 for (const auto& rc : m_rects) {
43 neededArea += rc.w * rc.h;
44 size |= rc.size();
45 }
46
47 const int w0 = std::max(size.w, 1);
48 const int h0 = std::max(size.h, 1);
49 int w = w0;
50 int h = h0;
51 int z = 0;
52 bool fit = false;
53 while (!token.canceled()) {
54 if (w*h >= neededArea) {
55 fit = pack(Size(w, h), token);
56 if (fit) {
57 size = Size(w, h);
58 break;
59 }
60 }
61
62 if (fixedWidth == 0 && fixedHeight == 0) {
63 if ((++z) & 1)
64 w += w0;
65 else
66 h += h0;
67 }
68 else if (fixedWidth == 0) {
69 w += w0;
70 }
71 else {
72 h += h0;
73 }
74 }
75
76 return size;
77}
78
79static bool by_area(const Rect* a, const Rect* b) {
80 return a->w*a->h > b->w*b->h;
81}
82
83bool PackingRects::pack(const Size& size,
84 base::task_token& token)
85{
86 m_bounds = Rect(size).shrink(m_borderPadding);
87
88 // We cannot sort m_rects because we want to
89 std::vector<Rect*> rectPtrs(m_rects.size());
90 int i = 0;
91 for (auto& rc : m_rects)
92 rectPtrs[i++] = &rc;
93 std::sort(rectPtrs.begin(), rectPtrs.end(), by_area);
94
95 gfx::Region rgn(m_bounds);
96 i = 0;
97 for (auto rcPtr : rectPtrs) {
98 if (token.canceled())
99 return false;
100 token.set_progress(float(i) / int(rectPtrs.size()));
101
102 gfx::Rect& rc = *rcPtr;
103
104 // The rectangles are treated as its original size during placement,
105 // but occupies an extra border of <shapePadding> pixels once its
106 // position has been determined.
107 // This ensures that all rectangles are padded by <sp> pixels,
108 // and are still placed correctly near edges, e.g. when remaining
109 // horizontal space is between <width> and <width>+<shapePadding>.
110 for (int v=0; v<=m_bounds.h-rc.h; ++v) {
111 for (int u=0; u<=m_bounds.w-rc.w; ++u) {
112 if (token.canceled())
113 return false;
114
115 gfx::Rect possible(m_bounds.x + u, m_bounds.y + v, rc.w, rc.h);
116 Region::Overlap overlap = rgn.contains(possible);
117 if (overlap == Region::In) {
118 rc = possible;
119 rgn.createSubtraction(
120 rgn,
121 gfx::Region(Rect(rc).inflate(m_shapePadding))
122 );
123 goto next_rc;
124 }
125 }
126 }
127 return false; // There is not enough room for "rc"
128 next_rc:;
129 ++i;
130 }
131
132 return true;
133}
134
135} // namespace gfx
136