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