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