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 <assert.h> 14 15 #include <algorithm> 16 17 namespace webrtc { 18 19 DesktopRegion::RowSpan::RowSpan(int32_t left, int32_t right) 20 : left(left), right(right) { 21 } 22 23 DesktopRegion::Row::Row(int32_t top, int32_t bottom) 24 : top(top), bottom(bottom) { 25 } 26 27 DesktopRegion::Row::~Row() {} 28 29 DesktopRegion::DesktopRegion() {} 30 31 DesktopRegion::DesktopRegion(const DesktopRect& rect) { 32 AddRect(rect); 33 } 34 35 DesktopRegion::DesktopRegion(const DesktopRect* rects, int count) { 36 AddRects(rects, count); 37 } 38 39 DesktopRegion::DesktopRegion(const DesktopRegion& other) { 40 *this = other; 41 } 42 43 DesktopRegion::~DesktopRegion() { 44 Clear(); 45 } 46 47 DesktopRegion& DesktopRegion::operator=(const DesktopRegion& other) { 48 Clear(); 49 rows_ = other.rows_; 50 for (Rows::iterator it = rows_.begin(); it != rows_.end(); ++it) { 51 // Copy each row. 52 Row* row = it->second; 53 it->second = new Row(*row); 54 } 55 return *this; 56 } 57 58 bool DesktopRegion::Equals(const DesktopRegion& region) const { 59 // Iterate over rows of the tow regions and compare each row. 60 Rows::const_iterator it1 = rows_.begin(); 61 Rows::const_iterator it2 = region.rows_.begin(); 62 while (it1 != rows_.end()) { 63 if (it2 == region.rows_.end() || 64 it1->first != it2->first || 65 it1->second->top != it2->second->top || 66 it1->second->bottom != it2->second->bottom || 67 it1->second->spans != it2->second->spans) { 68 return false; 69 } 70 ++it1; 71 ++it2; 72 } 73 return it2 == region.rows_.end(); 74 } 75 76 void DesktopRegion::Clear() { 77 for (Rows::iterator row = rows_.begin(); row != rows_.end(); ++row) { 78 delete row->second; 79 } 80 rows_.clear(); 81 } 82 83 void DesktopRegion::SetRect(const DesktopRect& rect) { 84 Clear(); 85 AddRect(rect); 86 } 87 88 void DesktopRegion::AddRect(const DesktopRect& rect) { 89 if (rect.is_empty()) 90 return; 91 92 // Top of the part of the |rect| that hasn't been inserted yet. Increased as 93 // we iterate over the rows until it reaches |rect.bottom()|. 94 int top = rect.top(); 95 96 // Iterate over all rows that may intersect with |rect| and add new rows when 97 // necessary. 98 Rows::iterator row = rows_.upper_bound(top); 99 while (top < rect.bottom()) { 100 if (row == rows_.end() || top < row->second->top) { 101 // If |top| is above the top of the current |row| then add a new row above 102 // the current one. 103 int32_t bottom = rect.bottom(); 104 if (row != rows_.end() && row->second->top < bottom) 105 bottom = row->second->top; 106 row = rows_.insert( 107 row, Rows::value_type(bottom, new Row(top, bottom))); 108 } else if (top > row->second->top) { 109 // If the |top| falls in the middle of the |row| then split |row| into 110 // two, at |top|, and leave |row| referring to the lower of the two, 111 // ready to insert a new span into. 112 assert(top <= row->second->bottom); 113 Rows::iterator new_row = rows_.insert( 114 row, Rows::value_type(top, new Row(row->second->top, top))); 115 row->second->top = top; 116 new_row->second->spans = row->second->spans; 117 } 118 119 if (rect.bottom() < row->second->bottom) { 120 // If the bottom of the |rect| falls in the middle of the |row| split 121 // |row| into two, at |top|, and leave |row| referring to the upper of 122 // the two, ready to insert a new span into. 123 Rows::iterator new_row = rows_.insert( 124 row, Rows::value_type(rect.bottom(), new Row(top, rect.bottom()))); 125 row->second->top = rect.bottom(); 126 new_row->second->spans = row->second->spans; 127 row = new_row; 128 } 129 130 // Add a new span to the current row. 131 AddSpanToRow(row->second, rect.left(), rect.right()); 132 top = row->second->bottom; 133 134 MergeWithPrecedingRow(row); 135 136 // Move to the next row. 137 ++row; 138 } 139 140 if (row != rows_.end()) 141 MergeWithPrecedingRow(row); 142 } 143 144 void DesktopRegion::AddRects(const DesktopRect* rects, int count) { 145 for (int i = 0; i < count; ++i) { 146 AddRect(rects[i]); 147 } 148 } 149 150 void DesktopRegion::MergeWithPrecedingRow(Rows::iterator row) { 151 assert(row != rows_.end()); 152 153 if (row != rows_.begin()) { 154 Rows::iterator previous_row = row; 155 previous_row--; 156 157 // If |row| and |previous_row| are next to each other and contain the same 158 // set of spans then they can be merged. 159 if (previous_row->second->bottom == row->second->top && 160 previous_row->second->spans == row->second->spans) { 161 row->second->top = previous_row->second->top; 162 delete previous_row->second; 163 rows_.erase(previous_row); 164 } 165 } 166 } 167 168 void DesktopRegion::AddRegion(const DesktopRegion& region) { 169 // TODO(sergeyu): This function is not optimized - potentially it can iterate 170 // over rows of the two regions similar to how it works in Intersect(). 171 for (Iterator it(region); !it.IsAtEnd(); it.Advance()) { 172 AddRect(it.rect()); 173 } 174 } 175 176 void DesktopRegion::Intersect(const DesktopRegion& region1, 177 const DesktopRegion& region2) { 178 Clear(); 179 180 Rows::const_iterator it1 = region1.rows_.begin(); 181 Rows::const_iterator end1 = region1.rows_.end(); 182 Rows::const_iterator it2 = region2.rows_.begin(); 183 Rows::const_iterator end2 = region2.rows_.end(); 184 if (it1 == end1 || it2 == end2) 185 return; 186 187 while (it1 != end1 && it2 != end2) { 188 // Arrange for |it1| to always be the top-most of the rows. 189 if (it2->second->top < it1->second->top) { 190 std::swap(it1, it2); 191 std::swap(end1, end2); 192 } 193 194 // Skip |it1| if it doesn't intersect |it2| at all. 195 if (it1->second->bottom <= it2->second->top) { 196 ++it1; 197 continue; 198 } 199 200 // Top of the |it1| row is above the top of |it2|, so top of the 201 // intersection is always the top of |it2|. 202 int32_t top = it2->second->top; 203 int32_t bottom = std::min(it1->second->bottom, it2->second->bottom); 204 205 Rows::iterator new_row = rows_.insert( 206 rows_.end(), Rows::value_type(bottom, new Row(top, bottom))); 207 IntersectRows(it1->second->spans, it2->second->spans, 208 &new_row->second->spans); 209 if (new_row->second->spans.empty()) { 210 delete new_row->second; 211 rows_.erase(new_row); 212 } else { 213 MergeWithPrecedingRow(new_row); 214 } 215 216 // If |it1| was completely consumed, move to the next one. 217 if (it1->second->bottom == bottom) 218 ++it1; 219 // If |it2| was completely consumed, move to the next one. 220 if (it2->second->bottom == bottom) 221 ++it2; 222 } 223 } 224 225 // static 226 void DesktopRegion::IntersectRows(const RowSpanSet& set1, 227 const RowSpanSet& set2, 228 RowSpanSet* output) { 229 RowSpanSet::const_iterator it1 = set1.begin(); 230 RowSpanSet::const_iterator end1 = set1.end(); 231 RowSpanSet::const_iterator it2 = set2.begin(); 232 RowSpanSet::const_iterator end2 = set2.end(); 233 assert(it1 != end1 && it2 != end2); 234 235 do { 236 // Arrange for |it1| to always be the left-most of the spans. 237 if (it2->left < it1->left) { 238 std::swap(it1, it2); 239 std::swap(end1, end2); 240 } 241 242 // Skip |it1| if it doesn't intersect |it2| at all. 243 if (it1->right <= it2->left) { 244 ++it1; 245 continue; 246 } 247 248 int32_t left = it2->left; 249 int32_t right = std::min(it1->right, it2->right); 250 assert(left < right); 251 252 output->push_back(RowSpan(left, right)); 253 254 // If |it1| was completely consumed, move to the next one. 255 if (it1->right == right) 256 ++it1; 257 // If |it2| was completely consumed, move to the next one. 258 if (it2->right == right) 259 ++it2; 260 } while (it1 != end1 && it2 != end2); 261 } 262 263 void DesktopRegion::IntersectWith(const DesktopRegion& region) { 264 DesktopRegion old_region; 265 Swap(&old_region); 266 Intersect(old_region, region); 267 } 268 269 void DesktopRegion::IntersectWith(const DesktopRect& rect) { 270 DesktopRegion region; 271 region.AddRect(rect); 272 IntersectWith(region); 273 } 274 275 void DesktopRegion::Subtract(const DesktopRegion& region) { 276 if (region.rows_.empty()) 277 return; 278 279 // |row_b| refers to the current row being subtracted. 280 Rows::const_iterator row_b = region.rows_.begin(); 281 282 // Current vertical position at which subtraction is happening. 283 int top = row_b->second->top; 284 285 // |row_a| refers to the current row we are subtracting from. Skip all rows 286 // above |top|. 287 Rows::iterator row_a = rows_.upper_bound(top); 288 289 // Step through rows of the both regions subtracting content of |row_b| from 290 // |row_a|. 291 while (row_a != rows_.end() && row_b != region.rows_.end()) { 292 // Skip |row_a| if it doesn't intersect with the |row_b|. 293 if (row_a->second->bottom <= top) { 294 // Each output row is merged with previously-processed rows before further 295 // rows are processed. 296 MergeWithPrecedingRow(row_a); 297 ++row_a; 298 continue; 299 } 300 301 if (top > row_a->second->top) { 302 // If |top| falls in the middle of |row_a| then split |row_a| into two, at 303 // |top|, and leave |row_a| referring to the lower of the two, ready to 304 // subtract spans from. 305 assert(top <= row_a->second->bottom); 306 Rows::iterator new_row = rows_.insert( 307 row_a, Rows::value_type(top, new Row(row_a->second->top, top))); 308 row_a->second->top = top; 309 new_row->second->spans = row_a->second->spans; 310 } else if (top < row_a->second->top) { 311 // If the |top| is above |row_a| then skip the range between |top| and 312 // top of |row_a| because it's empty. 313 top = row_a->second->top; 314 if (top >= row_b->second->bottom) { 315 ++row_b; 316 if (row_b != region.rows_.end()) 317 top = row_b->second->top; 318 continue; 319 } 320 } 321 322 if (row_b->second->bottom < row_a->second->bottom) { 323 // If the bottom of |row_b| falls in the middle of the |row_a| split 324 // |row_a| into two, at |top|, and leave |row_a| referring to the upper of 325 // the two, ready to subtract spans from. 326 int bottom = row_b->second->bottom; 327 Rows::iterator new_row = 328 rows_.insert(row_a, Rows::value_type(bottom, new Row(top, bottom))); 329 row_a->second->top = bottom; 330 new_row->second->spans = row_a->second->spans; 331 row_a = new_row; 332 } 333 334 // At this point the vertical range covered by |row_a| lays within the 335 // range covered by |row_b|. Subtract |row_b| spans from |row_a|. 336 RowSpanSet new_spans; 337 SubtractRows(row_a->second->spans, row_b->second->spans, &new_spans); 338 new_spans.swap(row_a->second->spans); 339 top = row_a->second->bottom; 340 341 if (top >= row_b->second->bottom) { 342 ++row_b; 343 if (row_b != region.rows_.end()) 344 top = row_b->second->top; 345 } 346 347 // Check if the row is empty after subtraction and delete it. Otherwise move 348 // to the next one. 349 if (row_a->second->spans.empty()) { 350 Rows::iterator row_to_delete = row_a; 351 ++row_a; 352 delete row_to_delete->second; 353 rows_.erase(row_to_delete); 354 } else { 355 MergeWithPrecedingRow(row_a); 356 ++row_a; 357 } 358 } 359 360 if (row_a != rows_.end()) 361 MergeWithPrecedingRow(row_a); 362 } 363 364 void DesktopRegion::Subtract(const DesktopRect& rect) { 365 DesktopRegion region; 366 region.AddRect(rect); 367 Subtract(region); 368 } 369 370 void DesktopRegion::Translate(int32_t dx, int32_t dy) { 371 Rows new_rows; 372 373 for (Rows::iterator it = rows_.begin(); it != rows_.end(); ++it) { 374 Row* row = it->second; 375 376 row->top += dy; 377 row->bottom += dy; 378 379 if (dx != 0) { 380 // Translate each span. 381 for (RowSpanSet::iterator span = row->spans.begin(); 382 span != row->spans.end(); ++span) { 383 span->left += dx; 384 span->right += dx; 385 } 386 } 387 388 if (dy != 0) 389 new_rows.insert(new_rows.end(), Rows::value_type(row->bottom, row)); 390 } 391 392 if (dy != 0) 393 new_rows.swap(rows_); 394 } 395 396 void DesktopRegion::Swap(DesktopRegion* region) { 397 rows_.swap(region->rows_); 398 } 399 400 // static 401 bool DesktopRegion::CompareSpanRight(const RowSpan& r, int32_t value) { 402 return r.right < value; 403 } 404 405 // static 406 bool DesktopRegion::CompareSpanLeft(const RowSpan& r, int32_t value) { 407 return r.left < value; 408 } 409 410 // static 411 void DesktopRegion::AddSpanToRow(Row* row, int left, int right) { 412 // First check if the new span is located to the right of all existing spans. 413 // This is an optimization to avoid binary search in the case when rectangles 414 // are inserted sequentially from left to right. 415 if (row->spans.empty() || left > row->spans.back().right) { 416 row->spans.push_back(RowSpan(left, right)); 417 return; 418 } 419 420 // Find the first span that ends at or after |left|. 421 RowSpanSet::iterator start = 422 std::lower_bound(row->spans.begin(), row->spans.end(), left, 423 CompareSpanRight); 424 assert(start < row->spans.end()); 425 426 // Find the first span that starts after |right|. 427 RowSpanSet::iterator end = 428 std::lower_bound(start, row->spans.end(), right + 1, CompareSpanLeft); 429 if (end == row->spans.begin()) { 430 // There are no overlaps. Just insert the new span at the beginning. 431 row->spans.insert(row->spans.begin(), RowSpan(left, right)); 432 return; 433 } 434 435 // Move end to the left, so that it points the last span that ends at or 436 // before |right|. 437 end--; 438 439 // At this point [start, end] is the range of spans that intersect with the 440 // new one. 441 if (end < start) { 442 // There are no overlaps. Just insert the new span at the correct position. 443 row->spans.insert(start, RowSpan(left, right)); 444 return; 445 } 446 447 left = std::min(left, start->left); 448 right = std::max(right, end->right); 449 450 // Replace range [start, end] with the new span. 451 *start = RowSpan(left, right); 452 ++start; 453 ++end; 454 if (start < end) 455 row->spans.erase(start, end); 456 } 457 458 // static 459 bool DesktopRegion::IsSpanInRow(const Row& row, const RowSpan& span) { 460 // Find the first span that starts at or after |span.left| and then check if 461 // it's the same span. 462 RowSpanSet::const_iterator it = 463 std::lower_bound(row.spans.begin(), row.spans.end(), span.left, 464 CompareSpanLeft); 465 return it != row.spans.end() && *it == span; 466 } 467 468 // static 469 void DesktopRegion::SubtractRows(const RowSpanSet& set_a, 470 const RowSpanSet& set_b, 471 RowSpanSet* output) { 472 assert(!set_a.empty() && !set_b.empty()); 473 474 RowSpanSet::const_iterator it_b = set_b.begin(); 475 476 // Iterate over all spans in |set_a| adding parts of it that do not intersect 477 // with |set_b| to the |output|. 478 for (RowSpanSet::const_iterator it_a = set_a.begin(); it_a != set_a.end(); 479 ++it_a) { 480 // If there is no intersection then append the current span and continue. 481 if (it_b == set_b.end() || it_a->right < it_b->left) { 482 output->push_back(*it_a); 483 continue; 484 } 485 486 // Iterate over |set_b| spans that may intersect with |it_a|. 487 int pos = it_a->left; 488 while (it_b != set_b.end() && it_b->left < it_a->right) { 489 if (it_b->left > pos) 490 output->push_back(RowSpan(pos, it_b->left)); 491 if (it_b->right > pos) { 492 pos = it_b->right; 493 if (pos >= it_a->right) 494 break; 495 } 496 ++it_b; 497 } 498 if (pos < it_a->right) 499 output->push_back(RowSpan(pos, it_a->right)); 500 } 501 } 502 503 DesktopRegion::Iterator::Iterator(const DesktopRegion& region) 504 : region_(region), 505 row_(region.rows_.begin()), 506 previous_row_(region.rows_.end()) { 507 if (!IsAtEnd()) { 508 assert(row_->second->spans.size() > 0); 509 row_span_ = row_->second->spans.begin(); 510 UpdateCurrentRect(); 511 } 512 } 513 514 bool DesktopRegion::Iterator::IsAtEnd() const { 515 return row_ == region_.rows_.end(); 516 } 517 518 void DesktopRegion::Iterator::Advance() { 519 assert(!IsAtEnd()); 520 521 while (true) { 522 ++row_span_; 523 if (row_span_ == row_->second->spans.end()) { 524 previous_row_ = row_; 525 ++row_; 526 if (row_ != region_.rows_.end()) { 527 assert(row_->second->spans.size() > 0); 528 row_span_ = row_->second->spans.begin(); 529 } 530 } 531 532 if (IsAtEnd()) 533 return; 534 535 // If the same span exists on the previous row then skip it, as we've 536 // already returned this span merged into the previous one, via 537 // UpdateCurrentRect(). 538 if (previous_row_ != region_.rows_.end() && 539 previous_row_->second->bottom == row_->second->top && 540 IsSpanInRow(*previous_row_->second, *row_span_)) { 541 continue; 542 } 543 544 break; 545 } 546 547 assert(!IsAtEnd()); 548 UpdateCurrentRect(); 549 } 550 551 void DesktopRegion::Iterator::UpdateCurrentRect() { 552 // Merge the current rectangle with the matching spans from later rows. 553 int bottom; 554 Rows::const_iterator bottom_row = row_; 555 Rows::const_iterator previous; 556 do { 557 bottom = bottom_row->second->bottom; 558 previous = bottom_row; 559 ++bottom_row; 560 } while (bottom_row != region_.rows_.end() && 561 previous->second->bottom == bottom_row->second->top && 562 IsSpanInRow(*bottom_row->second, *row_span_)); 563 rect_ = DesktopRect::MakeLTRB(row_span_->left, row_->second->top, 564 row_span_->right, bottom); 565 } 566 567 } // namespace webrtc 568