desktop_region_unittest.cc (31370B)
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 <algorithm> 14 #include <cstdlib> 15 16 #include "modules/desktop_capture/desktop_geometry.h" 17 #include "test/gtest.h" 18 19 namespace webrtc { 20 21 namespace { 22 23 int RadmonInt(int max) { 24 return (rand() / 256) % max; 25 } 26 27 void CompareRegion(const DesktopRegion& region, 28 const DesktopRect rects[], 29 int rects_size) { 30 DesktopRegion::Iterator it(region); 31 for (int i = 0; i < rects_size; ++i) { 32 SCOPED_TRACE(i); 33 ASSERT_FALSE(it.IsAtEnd()); 34 EXPECT_TRUE(it.rect().equals(rects[i])) 35 << it.rect().left() << "-" << it.rect().right() << "." 36 << it.rect().top() << "-" << it.rect().bottom() << " " 37 << rects[i].left() << "-" << rects[i].right() << "." << rects[i].top() 38 << "-" << rects[i].bottom(); 39 it.Advance(); 40 } 41 EXPECT_TRUE(it.IsAtEnd()); 42 } 43 44 } // namespace 45 46 // Verify that regions are empty when created. 47 TEST(DesktopRegionTest, Empty) { 48 DesktopRegion r; 49 CompareRegion(r, nullptr, 0); 50 } 51 52 // Verify that empty rectangles are ignored. 53 TEST(DesktopRegionTest, AddEmpty) { 54 DesktopRegion r; 55 DesktopRect rect = DesktopRect::MakeXYWH(1, 2, 0, 0); 56 r.AddRect(rect); 57 CompareRegion(r, nullptr, 0); 58 } 59 60 // Verify that regions with a single rectangles are handled properly. 61 TEST(DesktopRegionTest, SingleRect) { 62 DesktopRegion r; 63 DesktopRect rect = DesktopRect::MakeXYWH(1, 2, 3, 4); 64 r.AddRect(rect); 65 CompareRegion(r, &rect, 1); 66 } 67 68 // Verify that non-overlapping rectangles are not merged. 69 TEST(DesktopRegionTest, NonOverlappingRects) { 70 struct Case { 71 int count; 72 DesktopRect rects[4]; 73 } cases[] = { 74 {.count = 1, .rects = {DesktopRect::MakeXYWH(10, 10, 10, 10)}}, 75 {.count = 2, 76 .rects = {DesktopRect::MakeXYWH(10, 10, 10, 10), 77 DesktopRect::MakeXYWH(30, 10, 10, 15)}}, 78 {.count = 2, 79 .rects = {DesktopRect::MakeXYWH(10, 10, 10, 10), 80 DesktopRect::MakeXYWH(10, 30, 10, 5)}}, 81 {.count = 3, 82 .rects = {DesktopRect::MakeXYWH(10, 10, 10, 9), 83 DesktopRect::MakeXYWH(30, 10, 15, 10), 84 DesktopRect::MakeXYWH(10, 30, 8, 10)}}, 85 {.count = 4, 86 .rects = {DesktopRect::MakeXYWH(0, 0, 30, 10), 87 DesktopRect::MakeXYWH(40, 0, 10, 30), 88 DesktopRect::MakeXYWH(0, 20, 10, 30), 89 DesktopRect::MakeXYWH(20, 40, 30, 10)}}, 90 {.count = 4, 91 .rects = {DesktopRect::MakeXYWH(0, 0, 10, 100), 92 DesktopRect::MakeXYWH(20, 10, 30, 10), 93 DesktopRect::MakeXYWH(20, 30, 30, 10), 94 DesktopRect::MakeXYWH(20, 50, 30, 10)}}, 95 }; 96 97 for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) { 98 SCOPED_TRACE(i); 99 100 DesktopRegion r; 101 102 for (int j = 0; j < cases[i].count; ++j) { 103 r.AddRect(cases[i].rects[j]); 104 } 105 CompareRegion(r, cases[i].rects, cases[i].count); 106 107 SCOPED_TRACE("Reverse"); 108 109 // Try inserting rects in reverse order. 110 r.Clear(); 111 for (int j = cases[i].count - 1; j >= 0; --j) { 112 r.AddRect(cases[i].rects[j]); 113 } 114 CompareRegion(r, cases[i].rects, cases[i].count); 115 } 116 } 117 118 TEST(DesktopRegionTest, TwoRects) { 119 struct Case { 120 DesktopRect input_rect1; 121 DesktopRect input_rect2; 122 int expected_count; 123 DesktopRect expected_rects[3]; 124 } cases[] = { 125 // Touching rectangles that merge into one. 126 {.input_rect1 = DesktopRect::MakeLTRB(100, 100, 200, 200), 127 .input_rect2 = DesktopRect::MakeLTRB(0, 100, 100, 200), 128 .expected_count = 1, 129 .expected_rects = {DesktopRect::MakeLTRB(0, 100, 200, 200)}}, 130 {.input_rect1 = DesktopRect::MakeLTRB(100, 100, 200, 200), 131 .input_rect2 = DesktopRect::MakeLTRB(100, 0, 200, 100), 132 .expected_count = 1, 133 .expected_rects = {DesktopRect::MakeLTRB(100, 0, 200, 200)}}, 134 135 // Rectangles touching on the vertical edge. 136 {.input_rect1 = DesktopRect::MakeLTRB(100, 100, 200, 200), 137 .input_rect2 = DesktopRect::MakeLTRB(0, 150, 100, 250), 138 .expected_count = 3, 139 .expected_rects = {DesktopRect::MakeLTRB(100, 100, 200, 150), 140 DesktopRect::MakeLTRB(0, 150, 200, 200), 141 DesktopRect::MakeLTRB(0, 200, 100, 250)}}, 142 {.input_rect1 = DesktopRect::MakeLTRB(100, 100, 200, 200), 143 .input_rect2 = DesktopRect::MakeLTRB(0, 50, 100, 150), 144 .expected_count = 3, 145 .expected_rects = {DesktopRect::MakeLTRB(0, 50, 100, 100), 146 DesktopRect::MakeLTRB(0, 100, 200, 150), 147 DesktopRect::MakeLTRB(100, 150, 200, 200)}}, 148 {.input_rect1 = DesktopRect::MakeLTRB(100, 100, 200, 200), 149 .input_rect2 = DesktopRect::MakeLTRB(0, 120, 100, 180), 150 .expected_count = 3, 151 .expected_rects = {DesktopRect::MakeLTRB(100, 100, 200, 120), 152 DesktopRect::MakeLTRB(0, 120, 200, 180), 153 DesktopRect::MakeLTRB(100, 180, 200, 200)}}, 154 155 // Rectangles touching on the horizontal edge. 156 {.input_rect1 = DesktopRect::MakeLTRB(100, 100, 200, 200), 157 .input_rect2 = DesktopRect::MakeLTRB(150, 0, 250, 100), 158 .expected_count = 2, 159 .expected_rects = {DesktopRect::MakeLTRB(150, 0, 250, 100), 160 DesktopRect::MakeLTRB(100, 100, 200, 200)}}, 161 {.input_rect1 = DesktopRect::MakeLTRB(100, 100, 200, 200), 162 .input_rect2 = DesktopRect::MakeLTRB(50, 0, 150, 100), 163 .expected_count = 2, 164 .expected_rects = {DesktopRect::MakeLTRB(50, 0, 150, 100), 165 DesktopRect::MakeLTRB(100, 100, 200, 200)}}, 166 {.input_rect1 = DesktopRect::MakeLTRB(100, 100, 200, 200), 167 .input_rect2 = DesktopRect::MakeLTRB(120, 0, 180, 100), 168 .expected_count = 2, 169 .expected_rects = {DesktopRect::MakeLTRB(120, 0, 180, 100), 170 DesktopRect::MakeLTRB(100, 100, 200, 200)}}, 171 172 // Overlapping rectangles. 173 {.input_rect1 = DesktopRect::MakeLTRB(100, 100, 200, 200), 174 .input_rect2 = DesktopRect::MakeLTRB(50, 50, 150, 150), 175 .expected_count = 3, 176 .expected_rects = {DesktopRect::MakeLTRB(50, 50, 150, 100), 177 DesktopRect::MakeLTRB(50, 100, 200, 150), 178 DesktopRect::MakeLTRB(100, 150, 200, 200)}}, 179 {.input_rect1 = DesktopRect::MakeLTRB(100, 100, 200, 200), 180 .input_rect2 = DesktopRect::MakeLTRB(150, 50, 250, 150), 181 .expected_count = 3, 182 .expected_rects = {DesktopRect::MakeLTRB(150, 50, 250, 100), 183 DesktopRect::MakeLTRB(100, 100, 250, 150), 184 DesktopRect::MakeLTRB(100, 150, 200, 200)}}, 185 {.input_rect1 = DesktopRect::MakeLTRB(100, 100, 200, 200), 186 .input_rect2 = DesktopRect::MakeLTRB(0, 120, 150, 180), 187 .expected_count = 3, 188 .expected_rects = {DesktopRect::MakeLTRB(100, 100, 200, 120), 189 DesktopRect::MakeLTRB(0, 120, 200, 180), 190 DesktopRect::MakeLTRB(100, 180, 200, 200)}}, 191 {.input_rect1 = DesktopRect::MakeLTRB(100, 100, 200, 200), 192 .input_rect2 = DesktopRect::MakeLTRB(120, 0, 180, 150), 193 .expected_count = 2, 194 .expected_rects = {DesktopRect::MakeLTRB(120, 0, 180, 100), 195 DesktopRect::MakeLTRB(100, 100, 200, 200)}}, 196 {.input_rect1 = DesktopRect::MakeLTRB(100, 0, 200, 300), 197 .input_rect2 = DesktopRect::MakeLTRB(0, 100, 300, 200), 198 .expected_count = 3, 199 .expected_rects = {DesktopRect::MakeLTRB(100, 0, 200, 100), 200 DesktopRect::MakeLTRB(0, 100, 300, 200), 201 DesktopRect::MakeLTRB(100, 200, 200, 300)}}, 202 203 // One rectangle enclosing another. 204 {.input_rect1 = DesktopRect::MakeLTRB(100, 100, 200, 200), 205 .input_rect2 = DesktopRect::MakeLTRB(150, 150, 180, 180), 206 .expected_count = 1, 207 .expected_rects = {DesktopRect::MakeLTRB(100, 100, 200, 200)}}, 208 {.input_rect1 = DesktopRect::MakeLTRB(100, 100, 200, 200), 209 .input_rect2 = DesktopRect::MakeLTRB(100, 100, 180, 180), 210 .expected_count = 1, 211 .expected_rects = {DesktopRect::MakeLTRB(100, 100, 200, 200)}}, 212 {.input_rect1 = DesktopRect::MakeLTRB(100, 100, 200, 200), 213 .input_rect2 = DesktopRect::MakeLTRB(150, 150, 200, 200), 214 .expected_count = 1, 215 .expected_rects = {DesktopRect::MakeLTRB(100, 100, 200, 200)}}, 216 }; 217 218 for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) { 219 SCOPED_TRACE(i); 220 221 DesktopRegion r; 222 223 r.AddRect(cases[i].input_rect1); 224 r.AddRect(cases[i].input_rect2); 225 CompareRegion(r, cases[i].expected_rects, cases[i].expected_count); 226 227 SCOPED_TRACE("Reverse"); 228 229 // Run the same test with rectangles inserted in reverse order. 230 r.Clear(); 231 r.AddRect(cases[i].input_rect2); 232 r.AddRect(cases[i].input_rect1); 233 CompareRegion(r, cases[i].expected_rects, cases[i].expected_count); 234 } 235 } 236 237 // Verify that DesktopRegion::AddRectToRow() works correctly by creating a row 238 // of not overlapping rectangles and insert an overlapping rectangle into the 239 // row at different positions. Result is verified by building a map of the 240 // region in an array and comparing it with the expected values. 241 TEST(DesktopRegionTest, SameRow) { 242 const int kMapWidth = 50; 243 const int kLastRectSizes[] = {3, 27}; 244 245 DesktopRegion base_region; 246 bool base_map[kMapWidth] = { 247 false, 248 }; 249 250 base_region.AddRect(DesktopRect::MakeXYWH(5, 0, 5, 1)); 251 std::fill_n(base_map + 5, 5, true); 252 base_region.AddRect(DesktopRect::MakeXYWH(15, 0, 5, 1)); 253 std::fill_n(base_map + 15, 5, true); 254 base_region.AddRect(DesktopRect::MakeXYWH(25, 0, 5, 1)); 255 std::fill_n(base_map + 25, 5, true); 256 base_region.AddRect(DesktopRect::MakeXYWH(35, 0, 5, 1)); 257 std::fill_n(base_map + 35, 5, true); 258 base_region.AddRect(DesktopRect::MakeXYWH(45, 0, 5, 1)); 259 std::fill_n(base_map + 45, 5, true); 260 261 for (size_t i = 0; i < sizeof(kLastRectSizes) / sizeof(kLastRectSizes[0]); 262 i++) { 263 int last_rect_size = kLastRectSizes[i]; 264 for (int x = 0; x < kMapWidth - last_rect_size; x++) { 265 SCOPED_TRACE(x); 266 267 DesktopRegion r = base_region; 268 r.AddRect(DesktopRect::MakeXYWH(x, 0, last_rect_size, 1)); 269 270 bool expected_map[kMapWidth]; 271 std::copy(base_map, base_map + kMapWidth, expected_map); 272 std::fill_n(expected_map + x, last_rect_size, true); 273 274 bool map[kMapWidth] = { 275 false, 276 }; 277 278 int pos = -1; 279 for (DesktopRegion::Iterator it(r); !it.IsAtEnd(); it.Advance()) { 280 EXPECT_GT(it.rect().left(), pos); 281 pos = it.rect().right(); 282 std::fill_n(map + it.rect().left(), it.rect().width(), true); 283 } 284 285 EXPECT_TRUE(std::equal(map, map + kMapWidth, expected_map)); 286 } 287 } 288 } 289 290 TEST(DesktopRegionTest, ComplexRegions) { 291 struct Case { 292 int input_count; 293 DesktopRect input_rects[4]; 294 int expected_count; 295 DesktopRect expected_rects[6]; 296 } cases[] = { 297 {.input_count = 3, 298 .input_rects = 299 { 300 DesktopRect::MakeLTRB(100, 100, 200, 200), 301 DesktopRect::MakeLTRB(0, 100, 100, 200), 302 DesktopRect::MakeLTRB(310, 110, 320, 120), 303 }, 304 .expected_count = 2, 305 .expected_rects = {DesktopRect::MakeLTRB(0, 100, 200, 200), 306 DesktopRect::MakeLTRB(310, 110, 320, 120)}}, 307 {.input_count = 3, 308 .input_rects = {DesktopRect::MakeLTRB(100, 100, 200, 200), 309 DesktopRect::MakeLTRB(50, 50, 150, 150), 310 DesktopRect::MakeLTRB(300, 125, 350, 175)}, 311 .expected_count = 4, 312 .expected_rects = {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 {.input_count = 4, 317 .input_rects = {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 .expected_count = 6, 322 .expected_rects = {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 {.input_count = 3, 329 .input_rects = {DesktopRect::MakeLTRB(10, 10, 40, 20), 330 DesktopRect::MakeLTRB(10, 30, 40, 40), 331 DesktopRect::MakeLTRB(10, 20, 40, 30)}, 332 .expected_count = 1, 333 .expected_rects = {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 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 {.count = 2, 360 .rects = {DesktopRect::MakeLTRB(0, 100, 200, 200), 361 DesktopRect::MakeLTRB(310, 110, 320, 120)}, 362 .id = 0}, 363 {.count = 2, 364 .rects = {DesktopRect::MakeLTRB(0, 100, 201, 200), 365 DesktopRect::MakeLTRB(310, 110, 320, 120)}, 366 .id = 1}, 367 {.count = 2, 368 .rects = {DesktopRect::MakeLTRB(0, 100, 200, 201), 369 DesktopRect::MakeLTRB(310, 110, 320, 120)}, 370 .id = 2}, 371 372 // Same region with one of the rectangles shifted horizontally and 373 // vertically. 374 {.count = 4, 375 .rects = {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 .id = 3}, 380 {.count = 4, 381 .rects = {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 .id = 4}, 386 {.count = 4, 387 .rects = {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 .id = 5}, 392 393 // Same region defined by a different set of rectangles - one of the 394 // rectangle is split horizontally into two. 395 {.count = 3, 396 .rects = {DesktopRect::MakeLTRB(100, 100, 200, 200), 397 DesktopRect::MakeLTRB(50, 50, 150, 150), 398 DesktopRect::MakeLTRB(300, 125, 350, 175)}, 399 .id = 6}, 400 {.count = 4, 401 .rects = {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 .id = 6}, 406 407 // Rectangle region defined by a set of rectangles that merge into one. 408 {.count = 3, 409 .rects = {DesktopRect::MakeLTRB(10, 10, 40, 20), 410 DesktopRect::MakeLTRB(10, 30, 40, 40), 411 DesktopRect::MakeLTRB(10, 20, 40, 30)}, 412 .id = 7}, 413 {.count = 1, .rects = {DesktopRect::MakeLTRB(10, 10, 40, 40)}, .id = 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 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 {.input_count = 3, 440 .input_rects = {DesktopRect::MakeLTRB(0, 0, 30, 30), 441 DesktopRect::MakeLTRB(10, 10, 40, 40), 442 DesktopRect::MakeLTRB(20, 20, 50, 50)}, 443 .dx = 3, 444 .dy = 5, 445 .expected_count = 5, 446 .expected_rects = {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 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 {.input1_count = 1, 472 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}, 473 .input2_count = 1, 474 .input2_rects = {DesktopRect::MakeLTRB(50, 50, 150, 150)}, 475 .expected_count = 1, 476 .expected_rects = {DesktopRect::MakeLTRB(50, 50, 100, 100)}}, 477 478 {.input1_count = 1, 479 .input1_rects = {DesktopRect::MakeLTRB(100, 0, 200, 300)}, 480 .input2_count = 1, 481 .input2_rects = {DesktopRect::MakeLTRB(0, 100, 300, 200)}, 482 .expected_count = 1, 483 .expected_rects = {DesktopRect::MakeLTRB(100, 100, 200, 200)}}, 484 485 {.input1_count = 1, 486 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}, 487 .input2_count = 2, 488 .input2_rects = {DesktopRect::MakeLTRB(50, 10, 150, 30), 489 DesktopRect::MakeLTRB(50, 30, 160, 50)}, 490 .expected_count = 1, 491 .expected_rects = {DesktopRect::MakeLTRB(50, 10, 100, 50)}}, 492 493 {.input1_count = 1, 494 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}, 495 .input2_count = 2, 496 .input2_rects = {DesktopRect::MakeLTRB(50, 10, 150, 30), 497 DesktopRect::MakeLTRB(50, 30, 90, 50)}, 498 .expected_count = 2, 499 .expected_rects = {DesktopRect::MakeLTRB(50, 10, 100, 30), 500 DesktopRect::MakeLTRB(50, 30, 90, 50)}}, 501 {.input1_count = 1, 502 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}, 503 .input2_count = 1, 504 .input2_rects = {DesktopRect::MakeLTRB(100, 50, 200, 200)}, 505 .expected_count = 0, 506 .expected_rects = {}}, 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 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 {.input1_count = 1, 533 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}, 534 .input2_count = 1, 535 .input2_rects = {DesktopRect::MakeLTRB(50, 50, 150, 150)}, 536 .expected_count = 2, 537 .expected_rects = {DesktopRect::MakeLTRB(0, 0, 100, 50), 538 DesktopRect::MakeLTRB(0, 50, 50, 100)}}, 539 540 {.input1_count = 1, 541 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}, 542 .input2_count = 1, 543 .input2_rects = {DesktopRect::MakeLTRB(-50, -50, 50, 50)}, 544 .expected_count = 2, 545 .expected_rects = {DesktopRect::MakeLTRB(50, 0, 100, 50), 546 DesktopRect::MakeLTRB(0, 50, 100, 100)}}, 547 548 {.input1_count = 1, 549 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}, 550 .input2_count = 1, 551 .input2_rects = {DesktopRect::MakeLTRB(-50, 50, 50, 150)}, 552 .expected_count = 2, 553 .expected_rects = {DesktopRect::MakeLTRB(0, 0, 100, 50), 554 DesktopRect::MakeLTRB(50, 50, 100, 100)}}, 555 556 {.input1_count = 1, 557 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}, 558 .input2_count = 1, 559 .input2_rects = {DesktopRect::MakeLTRB(50, 50, 150, 70)}, 560 .expected_count = 3, 561 .expected_rects = {DesktopRect::MakeLTRB(0, 0, 100, 50), 562 DesktopRect::MakeLTRB(0, 50, 50, 70), 563 DesktopRect::MakeLTRB(0, 70, 100, 100)}}, 564 565 {.input1_count = 1, 566 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}, 567 .input2_count = 1, 568 .input2_rects = {DesktopRect::MakeLTRB(50, 50, 70, 70)}, 569 .expected_count = 4, 570 .expected_rects = {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 {.input1_count = 1, 577 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}, 578 .input2_count = 1, 579 .input2_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}, 580 .expected_count = 0, 581 .expected_rects = {}}, 582 583 {.input1_count = 1, 584 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}, 585 .input2_count = 1, 586 .input2_rects = {DesktopRect::MakeLTRB(-10, -10, 110, 110)}, 587 .expected_count = 0, 588 .expected_rects = {}}, 589 590 {.input1_count = 2, 591 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100), 592 DesktopRect::MakeLTRB(50, 50, 150, 150)}, 593 .input2_count = 2, 594 .input2_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100), 595 DesktopRect::MakeLTRB(50, 50, 150, 150)}, 596 .expected_count = 0, 597 .expected_rects = {}}, 598 599 // One rect out of disjoint set. 600 {.input1_count = 3, 601 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 10, 10), 602 DesktopRect::MakeLTRB(20, 20, 30, 30), 603 DesktopRect::MakeLTRB(40, 0, 50, 10)}, 604 .input2_count = 1, 605 .input2_rects = {DesktopRect::MakeLTRB(20, 20, 30, 30)}, 606 .expected_count = 2, 607 .expected_rects = {DesktopRect::MakeLTRB(0, 0, 10, 10), 608 DesktopRect::MakeLTRB(40, 0, 50, 10)}}, 609 610 // Row merging. 611 {.input1_count = 3, 612 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 100, 50), 613 DesktopRect::MakeLTRB(0, 50, 150, 70), 614 DesktopRect::MakeLTRB(0, 70, 100, 100)}, 615 .input2_count = 1, 616 .input2_rects = {DesktopRect::MakeLTRB(100, 50, 150, 70)}, 617 .expected_count = 1, 618 .expected_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}}, 619 620 // No-op subtraction. 621 {.input1_count = 1, 622 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}, 623 .input2_count = 1, 624 .input2_rects = {DesktopRect::MakeLTRB(100, 0, 200, 100)}, 625 .expected_count = 1, 626 .expected_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}}, 627 628 {.input1_count = 1, 629 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}, 630 .input2_count = 1, 631 .input2_rects = {DesktopRect::MakeLTRB(-100, 0, 0, 100)}, 632 .expected_count = 1, 633 .expected_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}}, 634 635 {.input1_count = 1, 636 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}, 637 .input2_count = 1, 638 .input2_rects = {DesktopRect::MakeLTRB(0, 100, 0, 200)}, 639 .expected_count = 1, 640 .expected_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}}, 641 642 {.input1_count = 1, 643 .input1_rects = {DesktopRect::MakeLTRB(0, 0, 100, 100)}, 644 .input2_count = 1, 645 .input2_rects = {DesktopRect::MakeLTRB(0, -100, 100, 0)}, 646 .expected_count = 1, 647 .expected_rects = {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. 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 {.count = 1, .spans = {{.start = 0, .end = 3}}}, 677 {.count = 1, .spans = {{.start = 0, .end = 5}}}, 678 {.count = 1, .spans = {{.start = 0, .end = 7}}}, 679 {.count = 1, .spans = {{.start = 0, .end = 12}}}, 680 {.count = 2, 681 .spans = {{.start = 0, .end = 3}, 682 {.start = 4, .end = 5}, 683 {.start = 6, .end = 16}}}, 684 }; 685 686 DesktopRegion base_region; 687 bool base_map[kMapWidth] = { 688 false, 689 }; 690 691 base_region.AddRect(DesktopRect::MakeXYWH(5, 0, 5, 1)); 692 std::fill_n(base_map + 5, 5, true); 693 base_region.AddRect(DesktopRect::MakeXYWH(15, 0, 5, 1)); 694 std::fill_n(base_map + 15, 5, true); 695 base_region.AddRect(DesktopRect::MakeXYWH(25, 0, 5, 1)); 696 std::fill_n(base_map + 25, 5, true); 697 base_region.AddRect(DesktopRect::MakeXYWH(35, 0, 5, 1)); 698 std::fill_n(base_map + 35, 5, true); 699 base_region.AddRect(DesktopRect::MakeXYWH(45, 0, 5, 1)); 700 std::fill_n(base_map + 45, 5, true); 701 702 for (size_t i = 0; i < sizeof(span_sets) / sizeof(span_sets[0]); i++) { 703 SCOPED_TRACE(i); 704 SpanSet& span_set = span_sets[i]; 705 int span_set_end = span_set.spans[span_set.count - 1].end; 706 for (int x = 0; x < kMapWidth - span_set_end; ++x) { 707 SCOPED_TRACE(x); 708 709 DesktopRegion r = base_region; 710 711 bool expected_map[kMapWidth]; 712 std::copy(base_map, base_map + kMapWidth, expected_map); 713 714 DesktopRegion region2; 715 for (int span = 0; span < span_set.count; span++) { 716 std::fill_n(x + expected_map + span_set.spans[span].start, 717 span_set.spans[span].end - span_set.spans[span].start, 718 false); 719 region2.AddRect(DesktopRect::MakeLTRB(x + span_set.spans[span].start, 0, 720 x + span_set.spans[span].end, 1)); 721 } 722 r.Subtract(region2); 723 724 bool map[kMapWidth] = { 725 false, 726 }; 727 728 int pos = -1; 729 for (DesktopRegion::Iterator it(r); !it.IsAtEnd(); it.Advance()) { 730 EXPECT_GT(it.rect().left(), pos); 731 pos = it.rect().right(); 732 std::fill_n(map + it.rect().left(), it.rect().width(), true); 733 } 734 735 EXPECT_TRUE(std::equal(map, map + kMapWidth, expected_map)); 736 } 737 } 738 } 739 740 // Verify that DesktopRegion::Subtract() works correctly by creating a column of 741 // not overlapping rectangles and subtracting a set of rectangle on the same 742 // column. Result is verified by building a map of the region in an array and 743 // comparing it with the expected values. 744 TEST(DesktopRegionTest, SubtractRectOnSameCol) { 745 const int kMapHeight = 50; 746 747 struct SpanSet { 748 int count; 749 struct Range { 750 int start; 751 int end; 752 } spans[3]; 753 } span_sets[] = { 754 {.count = 1, .spans = {{.start = 0, .end = 3}}}, 755 {.count = 1, .spans = {{.start = 0, .end = 5}}}, 756 {.count = 1, .spans = {{.start = 0, .end = 7}}}, 757 {.count = 1, .spans = {{.start = 0, .end = 12}}}, 758 {.count = 2, 759 .spans = {{.start = 0, .end = 3}, 760 {.start = 4, .end = 5}, 761 {.start = 6, .end = 16}}}, 762 }; 763 764 DesktopRegion base_region; 765 bool base_map[kMapHeight] = { 766 false, 767 }; 768 769 base_region.AddRect(DesktopRect::MakeXYWH(0, 5, 1, 5)); 770 std::fill_n(base_map + 5, 5, true); 771 base_region.AddRect(DesktopRect::MakeXYWH(0, 15, 1, 5)); 772 std::fill_n(base_map + 15, 5, true); 773 base_region.AddRect(DesktopRect::MakeXYWH(0, 25, 1, 5)); 774 std::fill_n(base_map + 25, 5, true); 775 base_region.AddRect(DesktopRect::MakeXYWH(0, 35, 1, 5)); 776 std::fill_n(base_map + 35, 5, true); 777 base_region.AddRect(DesktopRect::MakeXYWH(0, 45, 1, 5)); 778 std::fill_n(base_map + 45, 5, true); 779 780 for (size_t i = 0; i < sizeof(span_sets) / sizeof(span_sets[0]); i++) { 781 SCOPED_TRACE(i); 782 SpanSet& span_set = span_sets[i]; 783 int span_set_end = span_set.spans[span_set.count - 1].end; 784 for (int y = 0; y < kMapHeight - span_set_end; ++y) { 785 SCOPED_TRACE(y); 786 787 DesktopRegion r = base_region; 788 789 bool expected_map[kMapHeight]; 790 std::copy(base_map, base_map + kMapHeight, expected_map); 791 792 DesktopRegion region2; 793 for (int span = 0; span < span_set.count; span++) { 794 std::fill_n(y + expected_map + span_set.spans[span].start, 795 span_set.spans[span].end - span_set.spans[span].start, 796 false); 797 region2.AddRect(DesktopRect::MakeLTRB(0, y + span_set.spans[span].start, 798 1, y + span_set.spans[span].end)); 799 } 800 r.Subtract(region2); 801 802 bool map[kMapHeight] = { 803 false, 804 }; 805 806 int pos = -1; 807 for (DesktopRegion::Iterator it(r); !it.IsAtEnd(); it.Advance()) { 808 EXPECT_GT(it.rect().top(), pos); 809 pos = it.rect().bottom(); 810 std::fill_n(map + it.rect().top(), it.rect().height(), true); 811 } 812 813 for (int j = 0; j < kMapHeight; j++) { 814 EXPECT_EQ(expected_map[j], map[j]) << "j = " << j; 815 } 816 } 817 } 818 } 819 820 TEST(DesktopRegionTest, DISABLED_Performance) { 821 for (int c = 0; c < 1000; ++c) { 822 DesktopRegion r; 823 for (int i = 0; i < 10; ++i) { 824 r.AddRect( 825 DesktopRect::MakeXYWH(RadmonInt(1000), RadmonInt(1000), 200, 200)); 826 } 827 828 for (int i = 0; i < 1000; ++i) { 829 r.AddRect(DesktopRect::MakeXYWH(RadmonInt(1000), RadmonInt(1000), 830 5 + RadmonInt(10) * 5, 831 5 + RadmonInt(10) * 5)); 832 } 833 834 // Iterate over the rectangles. 835 for (DesktopRegion::Iterator it(r); !it.IsAtEnd(); it.Advance()) { 836 } 837 } 838 } 839 840 } // namespace webrtc