1 /*
2 * Copyright (c) 2013 The WebRTC project authors. All Rights Reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11 #include "modules/desktop_capture/desktop_region.h"
12
13 #include <stdlib.h>
14
15 #include <algorithm>
16 #include <cstdint>
17
18 #include "test/gtest.h"
19
20 namespace webrtc {
21
22 namespace {
23
RadmonInt(int max)24 int RadmonInt(int max) {
25 return (rand() / 256) % max;
26 }
27
CompareRegion(const DesktopRegion & region,const DesktopRect rects[],int rects_size)28 void CompareRegion(const DesktopRegion& region,
29 const DesktopRect rects[],
30 int rects_size) {
31 DesktopRegion::Iterator it(region);
32 for (int i = 0; i < rects_size; ++i) {
33 SCOPED_TRACE(i);
34 ASSERT_FALSE(it.IsAtEnd());
35 EXPECT_TRUE(it.rect().equals(rects[i]))
36 << it.rect().left() << "-" << it.rect().right() << "."
37 << it.rect().top() << "-" << it.rect().bottom() << " "
38 << rects[i].left() << "-" << rects[i].right() << "." << rects[i].top()
39 << "-" << rects[i].bottom();
40 it.Advance();
41 }
42 EXPECT_TRUE(it.IsAtEnd());
43 }
44
45 } // namespace
46
47 // Verify that regions are empty when created.
TEST(DesktopRegionTest,Empty)48 TEST(DesktopRegionTest, Empty) {
49 DesktopRegion r;
50 CompareRegion(r, NULL, 0);
51 }
52
53 // Verify that empty rectangles are ignored.
TEST(DesktopRegionTest,AddEmpty)54 TEST(DesktopRegionTest, AddEmpty) {
55 DesktopRegion r;
56 DesktopRect rect = DesktopRect::MakeXYWH(1, 2, 0, 0);
57 r.AddRect(rect);
58 CompareRegion(r, NULL, 0);
59 }
60
61 // Verify that regions with a single rectangles are handled properly.
TEST(DesktopRegionTest,SingleRect)62 TEST(DesktopRegionTest, SingleRect) {
63 DesktopRegion r;
64 DesktopRect rect = DesktopRect::MakeXYWH(1, 2, 3, 4);
65 r.AddRect(rect);
66 CompareRegion(r, &rect, 1);
67 }
68
69 // Verify that non-overlapping rectangles are not merged.
TEST(DesktopRegionTest,NonOverlappingRects)70 TEST(DesktopRegionTest, NonOverlappingRects) {
71 struct Case {
72 int count;
73 DesktopRect rects[4];
74 } cases[] = {
75 {1, {DesktopRect::MakeXYWH(10, 10, 10, 10)}},
76 {2,
77 {DesktopRect::MakeXYWH(10, 10, 10, 10),
78 DesktopRect::MakeXYWH(30, 10, 10, 15)}},
79 {2,
80 {DesktopRect::MakeXYWH(10, 10, 10, 10),
81 DesktopRect::MakeXYWH(10, 30, 10, 5)}},
82 {3,
83 {DesktopRect::MakeXYWH(10, 10, 10, 9),
84 DesktopRect::MakeXYWH(30, 10, 15, 10),
85 DesktopRect::MakeXYWH(10, 30, 8, 10)}},
86 {4,
87 {DesktopRect::MakeXYWH(0, 0, 30, 10),
88 DesktopRect::MakeXYWH(40, 0, 10, 30),
89 DesktopRect::MakeXYWH(0, 20, 10, 30),
90 DesktopRect::MakeXYWH(20, 40, 30, 10)}},
91 {4,
92 {DesktopRect::MakeXYWH(0, 0, 10, 100),
93 DesktopRect::MakeXYWH(20, 10, 30, 10),
94 DesktopRect::MakeXYWH(20, 30, 30, 10),
95 DesktopRect::MakeXYWH(20, 50, 30, 10)}},
96 };
97
98 for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
99 SCOPED_TRACE(i);
100
101 DesktopRegion r;
102
103 for (int j = 0; j < cases[i].count; ++j) {
104 r.AddRect(cases[i].rects[j]);
105 }
106 CompareRegion(r, cases[i].rects, cases[i].count);
107
108 SCOPED_TRACE("Reverse");
109
110 // Try inserting rects in reverse order.
111 r.Clear();
112 for (int j = cases[i].count - 1; j >= 0; --j) {
113 r.AddRect(cases[i].rects[j]);
114 }
115 CompareRegion(r, cases[i].rects, cases[i].count);
116 }
117 }
118
TEST(DesktopRegionTest,TwoRects)119 TEST(DesktopRegionTest, TwoRects) {
120 struct Case {
121 DesktopRect input_rect1;
122 DesktopRect input_rect2;
123 int expected_count;
124 DesktopRect expected_rects[3];
125 } cases[] = {
126 // Touching rectangles that merge into one.
127 {DesktopRect::MakeLTRB(100, 100, 200, 200),
128 DesktopRect::MakeLTRB(0, 100, 100, 200),
129 1,
130 {DesktopRect::MakeLTRB(0, 100, 200, 200)}},
131 {DesktopRect::MakeLTRB(100, 100, 200, 200),
132 DesktopRect::MakeLTRB(100, 0, 200, 100),
133 1,
134 {DesktopRect::MakeLTRB(100, 0, 200, 200)}},
135
136 // Rectangles touching on the vertical edge.
137 {DesktopRect::MakeLTRB(100, 100, 200, 200),
138 DesktopRect::MakeLTRB(0, 150, 100, 250),
139 3,
140 {DesktopRect::MakeLTRB(100, 100, 200, 150),
141 DesktopRect::MakeLTRB(0, 150, 200, 200),
142 DesktopRect::MakeLTRB(0, 200, 100, 250)}},
143 {DesktopRect::MakeLTRB(100, 100, 200, 200),
144 DesktopRect::MakeLTRB(0, 50, 100, 150),
145 3,
146 {DesktopRect::MakeLTRB(0, 50, 100, 100),
147 DesktopRect::MakeLTRB(0, 100, 200, 150),
148 DesktopRect::MakeLTRB(100, 150, 200, 200)}},
149 {DesktopRect::MakeLTRB(100, 100, 200, 200),
150 DesktopRect::MakeLTRB(0, 120, 100, 180),
151 3,
152 {DesktopRect::MakeLTRB(100, 100, 200, 120),
153 DesktopRect::MakeLTRB(0, 120, 200, 180),
154 DesktopRect::MakeLTRB(100, 180, 200, 200)}},
155
156 // Rectangles touching on the horizontal edge.
157 {DesktopRect::MakeLTRB(100, 100, 200, 200),
158 DesktopRect::MakeLTRB(150, 0, 250, 100),
159 2,
160 {DesktopRect::MakeLTRB(150, 0, 250, 100),
161 DesktopRect::MakeLTRB(100, 100, 200, 200)}},
162 {DesktopRect::MakeLTRB(100, 100, 200, 200),
163 DesktopRect::MakeLTRB(50, 0, 150, 100),
164 2,
165 {DesktopRect::MakeLTRB(50, 0, 150, 100),
166 DesktopRect::MakeLTRB(100, 100, 200, 200)}},
167 {DesktopRect::MakeLTRB(100, 100, 200, 200),
168 DesktopRect::MakeLTRB(120, 0, 180, 100),
169 2,
170 {DesktopRect::MakeLTRB(120, 0, 180, 100),
171 DesktopRect::MakeLTRB(100, 100, 200, 200)}},
172
173 // Overlapping rectangles.
174 {DesktopRect::MakeLTRB(100, 100, 200, 200),
175 DesktopRect::MakeLTRB(50, 50, 150, 150),
176 3,
177 {DesktopRect::MakeLTRB(50, 50, 150, 100),
178 DesktopRect::MakeLTRB(50, 100, 200, 150),
179 DesktopRect::MakeLTRB(100, 150, 200, 200)}},
180 {DesktopRect::MakeLTRB(100, 100, 200, 200),
181 DesktopRect::MakeLTRB(150, 50, 250, 150),
182 3,
183 {DesktopRect::MakeLTRB(150, 50, 250, 100),
184 DesktopRect::MakeLTRB(100, 100, 250, 150),
185 DesktopRect::MakeLTRB(100, 150, 200, 200)}},
186 {DesktopRect::MakeLTRB(100, 100, 200, 200),
187 DesktopRect::MakeLTRB(0, 120, 150, 180),
188 3,
189 {DesktopRect::MakeLTRB(100, 100, 200, 120),
190 DesktopRect::MakeLTRB(0, 120, 200, 180),
191 DesktopRect::MakeLTRB(100, 180, 200, 200)}},
192 {DesktopRect::MakeLTRB(100, 100, 200, 200),
193 DesktopRect::MakeLTRB(120, 0, 180, 150),
194 2,
195 {DesktopRect::MakeLTRB(120, 0, 180, 100),
196 DesktopRect::MakeLTRB(100, 100, 200, 200)}},
197 {DesktopRect::MakeLTRB(100, 0, 200, 300),
198 DesktopRect::MakeLTRB(0, 100, 300, 200),
199 3,
200 {DesktopRect::MakeLTRB(100, 0, 200, 100),
201 DesktopRect::MakeLTRB(0, 100, 300, 200),
202 DesktopRect::MakeLTRB(100, 200, 200, 300)}},
203
204 // One rectangle enclosing another.
205 {DesktopRect::MakeLTRB(100, 100, 200, 200),
206 DesktopRect::MakeLTRB(150, 150, 180, 180),
207 1,
208 {DesktopRect::MakeLTRB(100, 100, 200, 200)}},
209 {DesktopRect::MakeLTRB(100, 100, 200, 200),
210 DesktopRect::MakeLTRB(100, 100, 180, 180),
211 1,
212 {DesktopRect::MakeLTRB(100, 100, 200, 200)}},
213 {DesktopRect::MakeLTRB(100, 100, 200, 200),
214 DesktopRect::MakeLTRB(150, 150, 200, 200),
215 1,
216 {DesktopRect::MakeLTRB(100, 100, 200, 200)}},
217 };
218
219 for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
220 SCOPED_TRACE(i);
221
222 DesktopRegion r;
223
224 r.AddRect(cases[i].input_rect1);
225 r.AddRect(cases[i].input_rect2);
226 CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
227
228 SCOPED_TRACE("Reverse");
229
230 // Run the same test with rectangles inserted in reverse order.
231 r.Clear();
232 r.AddRect(cases[i].input_rect2);
233 r.AddRect(cases[i].input_rect1);
234 CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
235 }
236 }
237
238 // Verify that DesktopRegion::AddRectToRow() works correctly by creating a row
239 // of not overlapping rectangles and insert an overlapping rectangle into the
240 // row at different positions. Result is verified by building a map of the
241 // region in an array and comparing it with the expected values.
TEST(DesktopRegionTest,SameRow)242 TEST(DesktopRegionTest, SameRow) {
243 const int kMapWidth = 50;
244 const int kLastRectSizes[] = {3, 27};
245
246 DesktopRegion base_region;
247 bool base_map[kMapWidth] = {
248 false,
249 };
250
251 base_region.AddRect(DesktopRect::MakeXYWH(5, 0, 5, 1));
252 std::fill_n(base_map + 5, 5, true);
253 base_region.AddRect(DesktopRect::MakeXYWH(15, 0, 5, 1));
254 std::fill_n(base_map + 15, 5, true);
255 base_region.AddRect(DesktopRect::MakeXYWH(25, 0, 5, 1));
256 std::fill_n(base_map + 25, 5, true);
257 base_region.AddRect(DesktopRect::MakeXYWH(35, 0, 5, 1));
258 std::fill_n(base_map + 35, 5, true);
259 base_region.AddRect(DesktopRect::MakeXYWH(45, 0, 5, 1));
260 std::fill_n(base_map + 45, 5, true);
261
262 for (size_t i = 0; i < sizeof(kLastRectSizes) / sizeof(kLastRectSizes[0]);
263 i++) {
264 int last_rect_size = kLastRectSizes[i];
265 for (int x = 0; x < kMapWidth - last_rect_size; x++) {
266 SCOPED_TRACE(x);
267
268 DesktopRegion r = base_region;
269 r.AddRect(DesktopRect::MakeXYWH(x, 0, last_rect_size, 1));
270
271 bool expected_map[kMapWidth];
272 std::copy(base_map, base_map + kMapWidth, expected_map);
273 std::fill_n(expected_map + x, last_rect_size, true);
274
275 bool map[kMapWidth] = {
276 false,
277 };
278
279 int pos = -1;
280 for (DesktopRegion::Iterator it(r); !it.IsAtEnd(); it.Advance()) {
281 EXPECT_GT(it.rect().left(), pos);
282 pos = it.rect().right();
283 std::fill_n(map + it.rect().left(), it.rect().width(), true);
284 }
285
286 EXPECT_TRUE(std::equal(map, map + kMapWidth, expected_map));
287 }
288 }
289 }
290
TEST(DesktopRegionTest,ComplexRegions)291 TEST(DesktopRegionTest, ComplexRegions) {
292 struct Case {
293 int input_count;
294 DesktopRect input_rects[4];
295 int expected_count;
296 DesktopRect expected_rects[6];
297 } cases[] = {
298 {3,
299 {
300 DesktopRect::MakeLTRB(100, 100, 200, 200),
301 DesktopRect::MakeLTRB(0, 100, 100, 200),
302 DesktopRect::MakeLTRB(310, 110, 320, 120),
303 },
304 2,
305 {DesktopRect::MakeLTRB(0, 100, 200, 200),
306 DesktopRect::MakeLTRB(310, 110, 320, 120)}},
307 {3,
308 {DesktopRect::MakeLTRB(100, 100, 200, 200),
309 DesktopRect::MakeLTRB(50, 50, 150, 150),
310 DesktopRect::MakeLTRB(300, 125, 350, 175)},
311 4,
312 {DesktopRect::MakeLTRB(50, 50, 150, 100),
313 DesktopRect::MakeLTRB(50, 100, 200, 150),
314 DesktopRect::MakeLTRB(300, 125, 350, 175),
315 DesktopRect::MakeLTRB(100, 150, 200, 200)}},
316 {4,
317 {DesktopRect::MakeLTRB(0, 0, 30, 30),
318 DesktopRect::MakeLTRB(10, 10, 40, 40),
319 DesktopRect::MakeLTRB(20, 20, 50, 50),
320 DesktopRect::MakeLTRB(50, 0, 65, 15)},
321 6,
322 {DesktopRect::MakeLTRB(0, 0, 30, 10),
323 DesktopRect::MakeLTRB(50, 0, 65, 15),
324 DesktopRect::MakeLTRB(0, 10, 40, 20),
325 DesktopRect::MakeLTRB(0, 20, 50, 30),
326 DesktopRect::MakeLTRB(10, 30, 50, 40),
327 DesktopRect::MakeLTRB(20, 40, 50, 50)}},
328 {3,
329 {DesktopRect::MakeLTRB(10, 10, 40, 20),
330 DesktopRect::MakeLTRB(10, 30, 40, 40),
331 DesktopRect::MakeLTRB(10, 20, 40, 30)},
332 1,
333 {DesktopRect::MakeLTRB(10, 10, 40, 40)}},
334 };
335
336 for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
337 SCOPED_TRACE(i);
338
339 DesktopRegion r;
340 r.AddRects(cases[i].input_rects, cases[i].input_count);
341 CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
342
343 // Try inserting rectangles in reverse order.
344 r.Clear();
345 for (int j = cases[i].input_count - 1; j >= 0; --j) {
346 r.AddRect(cases[i].input_rects[j]);
347 }
348 CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
349 }
350 }
351
TEST(DesktopRegionTest,Equals)352 TEST(DesktopRegionTest, Equals) {
353 struct Region {
354 int count;
355 DesktopRect rects[4];
356 int id;
357 } regions[] = {
358 // Same region with one of the rectangles 1 pixel wider/taller.
359 {2,
360 {DesktopRect::MakeLTRB(0, 100, 200, 200),
361 DesktopRect::MakeLTRB(310, 110, 320, 120)},
362 0},
363 {2,
364 {DesktopRect::MakeLTRB(0, 100, 201, 200),
365 DesktopRect::MakeLTRB(310, 110, 320, 120)},
366 1},
367 {2,
368 {DesktopRect::MakeLTRB(0, 100, 200, 201),
369 DesktopRect::MakeLTRB(310, 110, 320, 120)},
370 2},
371
372 // Same region with one of the rectangles shifted horizontally and
373 // vertically.
374 {4,
375 {DesktopRect::MakeLTRB(0, 0, 30, 30),
376 DesktopRect::MakeLTRB(10, 10, 40, 40),
377 DesktopRect::MakeLTRB(20, 20, 50, 50),
378 DesktopRect::MakeLTRB(50, 0, 65, 15)},
379 3},
380 {4,
381 {DesktopRect::MakeLTRB(0, 0, 30, 30),
382 DesktopRect::MakeLTRB(10, 10, 40, 40),
383 DesktopRect::MakeLTRB(20, 20, 50, 50),
384 DesktopRect::MakeLTRB(50, 1, 65, 16)},
385 4},
386 {4,
387 {DesktopRect::MakeLTRB(0, 0, 30, 30),
388 DesktopRect::MakeLTRB(10, 10, 40, 40),
389 DesktopRect::MakeLTRB(20, 20, 50, 50),
390 DesktopRect::MakeLTRB(51, 0, 66, 15)},
391 5},
392
393 // Same region defined by a different set of rectangles - one of the
394 // rectangle is split horizontally into two.
395 {3,
396 {DesktopRect::MakeLTRB(100, 100, 200, 200),
397 DesktopRect::MakeLTRB(50, 50, 150, 150),
398 DesktopRect::MakeLTRB(300, 125, 350, 175)},
399 6},
400 {4,
401 {DesktopRect::MakeLTRB(100, 100, 200, 200),
402 DesktopRect::MakeLTRB(50, 50, 100, 150),
403 DesktopRect::MakeLTRB(100, 50, 150, 150),
404 DesktopRect::MakeLTRB(300, 125, 350, 175)},
405 6},
406
407 // Rectangle region defined by a set of rectangles that merge into one.
408 {3,
409 {DesktopRect::MakeLTRB(10, 10, 40, 20),
410 DesktopRect::MakeLTRB(10, 30, 40, 40),
411 DesktopRect::MakeLTRB(10, 20, 40, 30)},
412 7},
413 {1, {DesktopRect::MakeLTRB(10, 10, 40, 40)}, 7},
414 };
415 int kTotalRegions = sizeof(regions) / sizeof(Region);
416
417 for (int i = 0; i < kTotalRegions; ++i) {
418 SCOPED_TRACE(i);
419
420 DesktopRegion r1(regions[i].rects, regions[i].count);
421 for (int j = 0; j < kTotalRegions; ++j) {
422 SCOPED_TRACE(j);
423
424 DesktopRegion r2(regions[j].rects, regions[j].count);
425 EXPECT_EQ(regions[i].id == regions[j].id, r1.Equals(r2));
426 }
427 }
428 }
429
TEST(DesktopRegionTest,Translate)430 TEST(DesktopRegionTest, Translate) {
431 struct Case {
432 int input_count;
433 DesktopRect input_rects[4];
434 int dx;
435 int dy;
436 int expected_count;
437 DesktopRect expected_rects[5];
438 } cases[] = {
439 {3,
440 {DesktopRect::MakeLTRB(0, 0, 30, 30),
441 DesktopRect::MakeLTRB(10, 10, 40, 40),
442 DesktopRect::MakeLTRB(20, 20, 50, 50)},
443 3,
444 5,
445 5,
446 {DesktopRect::MakeLTRB(3, 5, 33, 15),
447 DesktopRect::MakeLTRB(3, 15, 43, 25),
448 DesktopRect::MakeLTRB(3, 25, 53, 35),
449 DesktopRect::MakeLTRB(13, 35, 53, 45),
450 DesktopRect::MakeLTRB(23, 45, 53, 55)}},
451 };
452
453 for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
454 SCOPED_TRACE(i);
455
456 DesktopRegion r(cases[i].input_rects, cases[i].input_count);
457 r.Translate(cases[i].dx, cases[i].dy);
458 CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
459 }
460 }
461
TEST(DesktopRegionTest,Intersect)462 TEST(DesktopRegionTest, Intersect) {
463 struct Case {
464 int input1_count;
465 DesktopRect input1_rects[4];
466 int input2_count;
467 DesktopRect input2_rects[4];
468 int expected_count;
469 DesktopRect expected_rects[5];
470 } cases[] = {
471 {1,
472 {DesktopRect::MakeLTRB(0, 0, 100, 100)},
473 1,
474 {DesktopRect::MakeLTRB(50, 50, 150, 150)},
475 1,
476 {DesktopRect::MakeLTRB(50, 50, 100, 100)}},
477
478 {1,
479 {DesktopRect::MakeLTRB(100, 0, 200, 300)},
480 1,
481 {DesktopRect::MakeLTRB(0, 100, 300, 200)},
482 1,
483 {DesktopRect::MakeLTRB(100, 100, 200, 200)}},
484
485 {1,
486 {DesktopRect::MakeLTRB(0, 0, 100, 100)},
487 2,
488 {DesktopRect::MakeLTRB(50, 10, 150, 30),
489 DesktopRect::MakeLTRB(50, 30, 160, 50)},
490 1,
491 {DesktopRect::MakeLTRB(50, 10, 100, 50)}},
492
493 {1,
494 {DesktopRect::MakeLTRB(0, 0, 100, 100)},
495 2,
496 {DesktopRect::MakeLTRB(50, 10, 150, 30),
497 DesktopRect::MakeLTRB(50, 30, 90, 50)},
498 2,
499 {DesktopRect::MakeLTRB(50, 10, 100, 30),
500 DesktopRect::MakeLTRB(50, 30, 90, 50)}},
501 {1,
502 {DesktopRect::MakeLTRB(0, 0, 100, 100)},
503 1,
504 {DesktopRect::MakeLTRB(100, 50, 200, 200)},
505 0,
506 {}},
507 };
508
509 for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
510 SCOPED_TRACE(i);
511
512 DesktopRegion r1(cases[i].input1_rects, cases[i].input1_count);
513 DesktopRegion r2(cases[i].input2_rects, cases[i].input2_count);
514
515 DesktopRegion r;
516 r.Intersect(r1, r2);
517
518 CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
519 }
520 }
521
TEST(DesktopRegionTest,Subtract)522 TEST(DesktopRegionTest, Subtract) {
523 struct Case {
524 int input1_count;
525 DesktopRect input1_rects[4];
526 int input2_count;
527 DesktopRect input2_rects[4];
528 int expected_count;
529 DesktopRect expected_rects[5];
530 } cases[] = {
531 // Subtract one rect from another.
532 {1,
533 {DesktopRect::MakeLTRB(0, 0, 100, 100)},
534 1,
535 {DesktopRect::MakeLTRB(50, 50, 150, 150)},
536 2,
537 {DesktopRect::MakeLTRB(0, 0, 100, 50),
538 DesktopRect::MakeLTRB(0, 50, 50, 100)}},
539
540 {1,
541 {DesktopRect::MakeLTRB(0, 0, 100, 100)},
542 1,
543 {DesktopRect::MakeLTRB(-50, -50, 50, 50)},
544 2,
545 {DesktopRect::MakeLTRB(50, 0, 100, 50),
546 DesktopRect::MakeLTRB(0, 50, 100, 100)}},
547
548 {1,
549 {DesktopRect::MakeLTRB(0, 0, 100, 100)},
550 1,
551 {DesktopRect::MakeLTRB(-50, 50, 50, 150)},
552 2,
553 {DesktopRect::MakeLTRB(0, 0, 100, 50),
554 DesktopRect::MakeLTRB(50, 50, 100, 100)}},
555
556 {1,
557 {DesktopRect::MakeLTRB(0, 0, 100, 100)},
558 1,
559 {DesktopRect::MakeLTRB(50, 50, 150, 70)},
560 3,
561 {DesktopRect::MakeLTRB(0, 0, 100, 50),
562 DesktopRect::MakeLTRB(0, 50, 50, 70),
563 DesktopRect::MakeLTRB(0, 70, 100, 100)}},
564
565 {1,
566 {DesktopRect::MakeLTRB(0, 0, 100, 100)},
567 1,
568 {DesktopRect::MakeLTRB(50, 50, 70, 70)},
569 4,
570 {DesktopRect::MakeLTRB(0, 0, 100, 50),
571 DesktopRect::MakeLTRB(0, 50, 50, 70),
572 DesktopRect::MakeLTRB(70, 50, 100, 70),
573 DesktopRect::MakeLTRB(0, 70, 100, 100)}},
574
575 // Empty result.
576 {1,
577 {DesktopRect::MakeLTRB(0, 0, 100, 100)},
578 1,
579 {DesktopRect::MakeLTRB(0, 0, 100, 100)},
580 0,
581 {}},
582
583 {1,
584 {DesktopRect::MakeLTRB(0, 0, 100, 100)},
585 1,
586 {DesktopRect::MakeLTRB(-10, -10, 110, 110)},
587 0,
588 {}},
589
590 {2,
591 {DesktopRect::MakeLTRB(0, 0, 100, 100),
592 DesktopRect::MakeLTRB(50, 50, 150, 150)},
593 2,
594 {DesktopRect::MakeLTRB(0, 0, 100, 100),
595 DesktopRect::MakeLTRB(50, 50, 150, 150)},
596 0,
597 {}},
598
599 // One rect out of disjoint set.
600 {3,
601 {DesktopRect::MakeLTRB(0, 0, 10, 10),
602 DesktopRect::MakeLTRB(20, 20, 30, 30),
603 DesktopRect::MakeLTRB(40, 0, 50, 10)},
604 1,
605 {DesktopRect::MakeLTRB(20, 20, 30, 30)},
606 2,
607 {DesktopRect::MakeLTRB(0, 0, 10, 10),
608 DesktopRect::MakeLTRB(40, 0, 50, 10)}},
609
610 // Row merging.
611 {3,
612 {DesktopRect::MakeLTRB(0, 0, 100, 50),
613 DesktopRect::MakeLTRB(0, 50, 150, 70),
614 DesktopRect::MakeLTRB(0, 70, 100, 100)},
615 1,
616 {DesktopRect::MakeLTRB(100, 50, 150, 70)},
617 1,
618 {DesktopRect::MakeLTRB(0, 0, 100, 100)}},
619
620 // No-op subtraction.
621 {1,
622 {DesktopRect::MakeLTRB(0, 0, 100, 100)},
623 1,
624 {DesktopRect::MakeLTRB(100, 0, 200, 100)},
625 1,
626 {DesktopRect::MakeLTRB(0, 0, 100, 100)}},
627
628 {1,
629 {DesktopRect::MakeLTRB(0, 0, 100, 100)},
630 1,
631 {DesktopRect::MakeLTRB(-100, 0, 0, 100)},
632 1,
633 {DesktopRect::MakeLTRB(0, 0, 100, 100)}},
634
635 {1,
636 {DesktopRect::MakeLTRB(0, 0, 100, 100)},
637 1,
638 {DesktopRect::MakeLTRB(0, 100, 0, 200)},
639 1,
640 {DesktopRect::MakeLTRB(0, 0, 100, 100)}},
641
642 {1,
643 {DesktopRect::MakeLTRB(0, 0, 100, 100)},
644 1,
645 {DesktopRect::MakeLTRB(0, -100, 100, 0)},
646 1,
647 {DesktopRect::MakeLTRB(0, 0, 100, 100)}},
648 };
649
650 for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
651 SCOPED_TRACE(i);
652
653 DesktopRegion r1(cases[i].input1_rects, cases[i].input1_count);
654 DesktopRegion r2(cases[i].input2_rects, cases[i].input2_count);
655
656 r1.Subtract(r2);
657
658 CompareRegion(r1, cases[i].expected_rects, cases[i].expected_count);
659 }
660 }
661
662 // Verify that DesktopRegion::SubtractRows() works correctly by creating a row
663 // of not overlapping rectangles and subtracting a set of rectangle. Result
664 // is verified by building a map of the region in an array and comparing it with
665 // the expected values.
TEST(DesktopRegionTest,SubtractRectOnSameRow)666 TEST(DesktopRegionTest, SubtractRectOnSameRow) {
667 const int kMapWidth = 50;
668
669 struct SpanSet {
670 int count;
671 struct Range {
672 int start;
673 int end;
674 } spans[3];
675 } span_sets[] = {
676 {1, {{0, 3}}},
677 {1, {{0, 5}}},
678 {1, {{0, 7}}},
679 {1, {{0, 12}}},
680 {2, {{0, 3}, {4, 5}, {6, 16}}},
681 };
682
683 DesktopRegion base_region;
684 bool base_map[kMapWidth] = {
685 false,
686 };
687
688 base_region.AddRect(DesktopRect::MakeXYWH(5, 0, 5, 1));
689 std::fill_n(base_map + 5, 5, true);
690 base_region.AddRect(DesktopRect::MakeXYWH(15, 0, 5, 1));
691 std::fill_n(base_map + 15, 5, true);
692 base_region.AddRect(DesktopRect::MakeXYWH(25, 0, 5, 1));
693 std::fill_n(base_map + 25, 5, true);
694 base_region.AddRect(DesktopRect::MakeXYWH(35, 0, 5, 1));
695 std::fill_n(base_map + 35, 5, true);
696 base_region.AddRect(DesktopRect::MakeXYWH(45, 0, 5, 1));
697 std::fill_n(base_map + 45, 5, true);
698
699 for (size_t i = 0; i < sizeof(span_sets) / sizeof(span_sets[0]); i++) {
700 SCOPED_TRACE(i);
701 SpanSet& span_set = span_sets[i];
702 int span_set_end = span_set.spans[span_set.count - 1].end;
703 for (int x = 0; x < kMapWidth - span_set_end; ++x) {
704 SCOPED_TRACE(x);
705
706 DesktopRegion r = base_region;
707
708 bool expected_map[kMapWidth];
709 std::copy(base_map, base_map + kMapWidth, expected_map);
710
711 DesktopRegion region2;
712 for (int span = 0; span < span_set.count; span++) {
713 std::fill_n(x + expected_map + span_set.spans[span].start,
714 span_set.spans[span].end - span_set.spans[span].start,
715 false);
716 region2.AddRect(DesktopRect::MakeLTRB(x + span_set.spans[span].start, 0,
717 x + span_set.spans[span].end, 1));
718 }
719 r.Subtract(region2);
720
721 bool map[kMapWidth] = {
722 false,
723 };
724
725 int pos = -1;
726 for (DesktopRegion::Iterator it(r); !it.IsAtEnd(); it.Advance()) {
727 EXPECT_GT(it.rect().left(), pos);
728 pos = it.rect().right();
729 std::fill_n(map + it.rect().left(), it.rect().width(), true);
730 }
731
732 EXPECT_TRUE(std::equal(map, map + kMapWidth, expected_map));
733 }
734 }
735 }
736
737 // Verify that DesktopRegion::Subtract() works correctly by creating a column of
738 // not overlapping rectangles and subtracting a set of rectangle on the same
739 // column. Result is verified by building a map of the region in an array and
740 // comparing it with the expected values.
TEST(DesktopRegionTest,SubtractRectOnSameCol)741 TEST(DesktopRegionTest, SubtractRectOnSameCol) {
742 const int kMapHeight = 50;
743
744 struct SpanSet {
745 int count;
746 struct Range {
747 int start;
748 int end;
749 } spans[3];
750 } span_sets[] = {
751 {1, {{0, 3}}},
752 {1, {{0, 5}}},
753 {1, {{0, 7}}},
754 {1, {{0, 12}}},
755 {2, {{0, 3}, {4, 5}, {6, 16}}},
756 };
757
758 DesktopRegion base_region;
759 bool base_map[kMapHeight] = {
760 false,
761 };
762
763 base_region.AddRect(DesktopRect::MakeXYWH(0, 5, 1, 5));
764 std::fill_n(base_map + 5, 5, true);
765 base_region.AddRect(DesktopRect::MakeXYWH(0, 15, 1, 5));
766 std::fill_n(base_map + 15, 5, true);
767 base_region.AddRect(DesktopRect::MakeXYWH(0, 25, 1, 5));
768 std::fill_n(base_map + 25, 5, true);
769 base_region.AddRect(DesktopRect::MakeXYWH(0, 35, 1, 5));
770 std::fill_n(base_map + 35, 5, true);
771 base_region.AddRect(DesktopRect::MakeXYWH(0, 45, 1, 5));
772 std::fill_n(base_map + 45, 5, true);
773
774 for (size_t i = 0; i < sizeof(span_sets) / sizeof(span_sets[0]); i++) {
775 SCOPED_TRACE(i);
776 SpanSet& span_set = span_sets[i];
777 int span_set_end = span_set.spans[span_set.count - 1].end;
778 for (int y = 0; y < kMapHeight - span_set_end; ++y) {
779 SCOPED_TRACE(y);
780
781 DesktopRegion r = base_region;
782
783 bool expected_map[kMapHeight];
784 std::copy(base_map, base_map + kMapHeight, expected_map);
785
786 DesktopRegion region2;
787 for (int span = 0; span < span_set.count; span++) {
788 std::fill_n(y + expected_map + span_set.spans[span].start,
789 span_set.spans[span].end - span_set.spans[span].start,
790 false);
791 region2.AddRect(DesktopRect::MakeLTRB(0, y + span_set.spans[span].start,
792 1, y + span_set.spans[span].end));
793 }
794 r.Subtract(region2);
795
796 bool map[kMapHeight] = {
797 false,
798 };
799
800 int pos = -1;
801 for (DesktopRegion::Iterator it(r); !it.IsAtEnd(); it.Advance()) {
802 EXPECT_GT(it.rect().top(), pos);
803 pos = it.rect().bottom();
804 std::fill_n(map + it.rect().top(), it.rect().height(), true);
805 }
806
807 for (int j = 0; j < kMapHeight; j++) {
808 EXPECT_EQ(expected_map[j], map[j]) << "j = " << j;
809 }
810 }
811 }
812 }
813
TEST(DesktopRegionTest,DISABLED_Performance)814 TEST(DesktopRegionTest, DISABLED_Performance) {
815 for (int c = 0; c < 1000; ++c) {
816 DesktopRegion r;
817 for (int i = 0; i < 10; ++i) {
818 r.AddRect(
819 DesktopRect::MakeXYWH(RadmonInt(1000), RadmonInt(1000), 200, 200));
820 }
821
822 for (int i = 0; i < 1000; ++i) {
823 r.AddRect(DesktopRect::MakeXYWH(RadmonInt(1000), RadmonInt(1000),
824 5 + RadmonInt(10) * 5,
825 5 + RadmonInt(10) * 5));
826 }
827
828 // Iterate over the rectangles.
829 for (DesktopRegion::Iterator it(r); !it.IsAtEnd(); it.Advance()) {
830 }
831 }
832 }
833
834 } // namespace webrtc
835