1 /**
2 Internal. Operations on list of 2D boxes.
3
4 Copyright: Guillaume Piolat 2015.
5 License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
6 * Authors: Guillaume Piolat
7 */
8 module dplug.gui.boxlist;
9
10 import dplug.core.vec;
11 import dplug.core.sync;
12 import dplug.math.box;
13
14
15 /// Returns: Bounding boxes of all bounding boxes.
16 box2i boundingBox(box2i[] boxes) pure nothrow @nogc
17 {
18 if (boxes.length == 0)
19 return box2i(0, 0, 0, 0);
20 else
21 {
22 // Computes union of all boxes
23 box2i unionBox = boxes[0];
24 for(int i = 1; i < cast(int)boxes.length; ++i)
25 unionBox = unionBox.expand(boxes[i]);
26 return unionBox;
27 }
28 }
29
30
31 /// Make 4 boxes that are A without C (C is contained in A)
32 /// Some may be empty though since C touch at least one edge of A
33
34 /// General case
35 /// +---------+ +---------+
36 /// | A | | D |
37 /// | +---+ | After split +--+---+--+
38 /// | | C | | => | E| |F | At least one of D, E, F or G is empty
39 /// | +---+ | +--+---+--+
40 /// | | | G |
41 /// +---------+ +---------+
42 void boxSubtraction(in box2i A, in box2i C, out box2i D, out box2i E, out box2i F, out box2i G) pure nothrow @nogc
43 {
44 D = box2i(A.min.x, A.min.y, A.max.x, C.min.y);
45 E = box2i(A.min.x, C.min.y, C.min.x, C.max.y);
46 F = box2i(C.max.x, C.min.y, A.max.x, C.max.y);
47 G = box2i(A.min.x, C.max.y, A.max.x, A.max.y);
48 }
49
50 // Change the list of boxes so that the coverage is the same but none overlaps
51 // Every box pushed in filtered are non-intersecting.
52 // This may modify boxes in input.
53 // FUTURE: something better than O(n^2)
54 void removeOverlappingAreas(ref Vec!box2i boxes, ref Vec!box2i filtered) nothrow @nogc
55 {
56 for(int i = 0; i < cast(int)(boxes.length); ++i)
57 {
58 box2i A = boxes[i];
59
60 assert(A.isSorted());
61
62 // empty boxes aren't kept
63 if (A.volume() <= 0)
64 continue;
65
66 bool foundIntersection = false;
67
68 // test A against all other rectangles, if it pass, it is pushed
69 for(int j = i + 1; j < cast(int)(boxes.length); ++j)
70 {
71 box2i B = boxes[j];
72
73 box2i C = A.intersection(B);
74 bool doesIntersect = C.isSorted() && (!C.empty());
75
76 if (doesIntersect)
77 {
78 // case 1: A contains B, B is removed from the array, and no intersection considered
79 if (A.contains(B))
80 {
81 // Remove that box since it has been dealt with
82 boxes.removeAndReplaceByLastElement(j);
83 j = j - 1;
84 continue;
85 }
86
87 foundIntersection = true; // A will not be pushed as is
88
89 if (B.contains(A))
90 {
91 break; // nothing from A is kept
92 }
93 else
94 {
95 // computes A without C
96 box2i D, E, F, G;
97 boxSubtraction(A, C, D, E, F, G);
98
99 if (!D.empty)
100 boxes.pushBack(D);
101 if (!E.empty)
102 boxes.pushBack(E);
103 if (!F.empty)
104 boxes.pushBack(F);
105 if (!G.empty)
106 boxes.pushBack(G);
107
108 // no need to search for other intersection in A, since its parts have
109 // been pushed
110 break;
111 }
112 }
113 }
114
115 if (!foundIntersection)
116 filtered.pushBack(A);
117 }
118 }
119
120 unittest
121 {
122 auto bl = makeVec!box2i();
123 bl.pushBack( box2i(0, 0, 4, 4) );
124 bl.pushBack( box2i(2, 2, 6, 6) );
125 bl.pushBack( box2i(1, 1, 2, 2) );
126
127 import dplug.core.vec;
128
129 auto ab = makeVec!box2i();
130
131 removeOverlappingAreas(bl, ab);
132 assert(ab[] == [ box2i(2, 2, 6, 6), box2i(0, 0, 4, 2), box2i(0, 2, 2, 4) ] );
133
134 assert(bl[].boundingBox() == box2i(0, 0, 6, 6));
135 }
136
137
138 // Split each boxes in smaller boxes.
139 void tileAreas(in box2i[] areas, int maxWidth, int maxHeight, ref Vec!box2i splitted) nothrow @nogc
140 {
141 foreach(area; areas)
142 {
143 assert(!area.empty);
144 int nWidth = (area.width + maxWidth - 1) / maxWidth;
145 int nHeight = (area.height + maxHeight - 1) / maxHeight;
146
147 foreach (int j; 0..nHeight)
148 {
149 int y0 = maxHeight * j;
150 int y1 = y0 + maxHeight;
151 if (y1 > area.height)
152 y1 = area.height;
153
154 foreach (int i; 0..nWidth)
155 {
156 int x0 = maxWidth * i;
157 int x1 = x0 + maxWidth;
158 if (x1 > area.width)
159 x1 = area.width;
160
161 box2i b = box2i(x0, y0, x1, y1).translate(area.min);
162 assert(area.contains(b));
163 splitted.pushBack(b);
164 }
165 }
166 }
167 }
168
169 /// For debug purpose.
170 /// Returns: true if none of the boxes overlap.
171 bool haveNoOverlap(in box2i[] areas) nothrow @nogc
172 {
173 int N = cast(int)areas.length;
174
175 // check every pair of boxes for overlap, inneficient
176 for (int i = 0; i < N; ++i)
177 {
178 assert(areas[i].isSorted());
179 for (int j = i + 1; j < N; ++j)
180 {
181 if (areas[i].intersects(areas[j]))
182 return false;
183 }
184 }
185 return true;
186 }
187
188 unittest
189 {
190 assert(haveNoOverlap([ box2i( 0, 0, 1, 1), box2i(1, 1, 2, 2) ]));
191 assert(!haveNoOverlap([ box2i( 0, 0, 1, 1), box2i(0, 0, 2, 1) ]));
192 }
193
194
195 DirtyRectList makeDirtyRectList() nothrow @nogc
196 {
197 return DirtyRectList(4);
198 }
199
200 struct DirtyRectList
201 {
202 public:
203 nothrow @nogc:
204
205 this(int dummy)
206 {
207 _dirtyRectMutex = makeMutex();
208 _dirtyRects = makeVec!box2i(0);
209 }
210
211 @disable this(this);
212
213 bool isEmpty() nothrow @nogc
214 {
215 _dirtyRectMutex.lock();
216 bool result = _dirtyRects.length == 0;
217 _dirtyRectMutex.unlock();
218 return result;
219 }
220
221 /// Returns: Array of rectangles in the list, remove them from the list.
222 /// Needed to avoid races in repainting.
223 void pullAllRectangles(ref Vec!box2i result) nothrow @nogc
224 {
225 _dirtyRectMutex.lock();
226
227 foreach(rect; _dirtyRects[])
228 result.pushBack(rect);
229
230 _dirtyRects.clearContents();
231
232 _dirtyRectMutex.unlock();
233 }
234
235 /// Add a rect while keeping the no overlap invariant
236 void addRect(box2i rect) nothrow @nogc
237 {
238 assert(rect.isSorted);
239
240 if (!rect.empty)
241 {
242 _dirtyRectMutex.lock();
243 scope(exit) _dirtyRectMutex.unlock();
244
245 bool processed = false;
246
247 for (int i = 0; i < _dirtyRects.length; ++i)
248 {
249 box2i other = _dirtyRects[i];
250 if (other.contains(rect))
251 {
252 // If the rectangle candidate is inside an element of the list, discard it.
253 processed = true;
254 break;
255 }
256 else if (rect.contains(other)) // remove rect that it contains
257 {
258 // If the rectangle candidate contains an element of the list, this element need to go.
259 _dirtyRects[i] = _dirtyRects.popBack();
260 i--;
261 }
262 else
263 {
264 box2i common = other.intersection(rect);
265 if (!common.empty())
266 {
267 // compute other without common
268 box2i D, E, F, G;
269 boxSubtraction(other, common, D, E, F, G);
270
271 // remove other from list
272 _dirtyRects[i] = _dirtyRects.popBack();
273 i--;
274
275 // push the sub parts at the end of the list
276 // this is guaranteed to be non-overlapping since the list was non-overlapping before
277 if (!D.empty) _dirtyRects.pushBack(D);
278 if (!E.empty) _dirtyRects.pushBack(E);
279 if (!F.empty) _dirtyRects.pushBack(F);
280 if (!G.empty) _dirtyRects.pushBack(G);
281 }
282 // else no intersection problem, the candidate rectangle will be pushed normally in the list
283 }
284
285 }
286
287 if (!processed)
288 _dirtyRects.pushBack(rect);
289
290 // Quadratic test, disabled
291 // assert(haveNoOverlap(_dirtyRects[]));
292 }
293 }
294
295 private:
296 /// The possibly overlapping areas that need updating.
297 Vec!box2i _dirtyRects;
298
299 /// This is protected by a mutex, because it is sometimes updated from the host.
300 /// Note: we cannot remove this mutex, as host parameter change call setDirtyWhole directly.
301 /// TODO: we want to remove this lock, the host thread may avoid doing it directly.
302 UncheckedMutex _dirtyRectMutex;
303 }
304