Line data Source code
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 0 : DesktopRegion::RowSpan::RowSpan(int32_t left, int32_t right)
20 0 : : left(left), right(right) {
21 0 : }
22 :
23 : DesktopRegion::Row::Row(const Row&) = default;
24 : DesktopRegion::Row::Row(Row&&) = default;
25 :
26 0 : DesktopRegion::Row::Row(int32_t top, int32_t bottom)
27 0 : : top(top), bottom(bottom) {
28 0 : }
29 :
30 0 : DesktopRegion::Row::~Row() {}
31 :
32 0 : DesktopRegion::DesktopRegion() {}
33 :
34 0 : DesktopRegion::DesktopRegion(const DesktopRect& rect) {
35 0 : AddRect(rect);
36 0 : }
37 :
38 0 : DesktopRegion::DesktopRegion(const DesktopRect* rects, int count) {
39 0 : AddRects(rects, count);
40 0 : }
41 :
42 0 : DesktopRegion::DesktopRegion(const DesktopRegion& other) {
43 0 : *this = other;
44 0 : }
45 :
46 0 : DesktopRegion::~DesktopRegion() {
47 0 : Clear();
48 0 : }
49 :
50 0 : DesktopRegion& DesktopRegion::operator=(const DesktopRegion& other) {
51 0 : Clear();
52 0 : rows_ = other.rows_;
53 0 : for (Rows::iterator it = rows_.begin(); it != rows_.end(); ++it) {
54 : // Copy each row.
55 0 : Row* row = it->second;
56 0 : it->second = new Row(*row);
57 : }
58 0 : return *this;
59 : }
60 :
61 0 : bool DesktopRegion::Equals(const DesktopRegion& region) const {
62 : // Iterate over rows of the tow regions and compare each row.
63 0 : Rows::const_iterator it1 = rows_.begin();
64 0 : Rows::const_iterator it2 = region.rows_.begin();
65 0 : while (it1 != rows_.end()) {
66 0 : if (it2 == region.rows_.end() ||
67 0 : it1->first != it2->first ||
68 0 : it1->second->top != it2->second->top ||
69 0 : it1->second->bottom != it2->second->bottom ||
70 0 : it1->second->spans != it2->second->spans) {
71 0 : return false;
72 : }
73 0 : ++it1;
74 0 : ++it2;
75 : }
76 0 : return it2 == region.rows_.end();
77 : }
78 :
79 0 : void DesktopRegion::Clear() {
80 0 : for (Rows::iterator row = rows_.begin(); row != rows_.end(); ++row) {
81 0 : delete row->second;
82 : }
83 0 : rows_.clear();
84 0 : }
85 :
86 0 : void DesktopRegion::SetRect(const DesktopRect& rect) {
87 0 : Clear();
88 0 : AddRect(rect);
89 0 : }
90 :
91 0 : void DesktopRegion::AddRect(const DesktopRect& rect) {
92 0 : if (rect.is_empty())
93 0 : 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 0 : int top = rect.top();
98 :
99 : // Iterate over all rows that may intersect with |rect| and add new rows when
100 : // necessary.
101 0 : Rows::iterator row = rows_.upper_bound(top);
102 0 : while (top < rect.bottom()) {
103 0 : 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 0 : int32_t bottom = rect.bottom();
107 0 : if (row != rows_.end() && row->second->top < bottom)
108 0 : bottom = row->second->top;
109 : row = rows_.insert(
110 0 : row, Rows::value_type(bottom, new Row(top, bottom)));
111 0 : } 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 0 : assert(top <= row->second->bottom);
116 : Rows::iterator new_row = rows_.insert(
117 0 : row, Rows::value_type(top, new Row(row->second->top, top)));
118 0 : row->second->top = top;
119 0 : new_row->second->spans = row->second->spans;
120 : }
121 :
122 0 : 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 0 : row, Rows::value_type(rect.bottom(), new Row(top, rect.bottom())));
128 0 : row->second->top = rect.bottom();
129 0 : new_row->second->spans = row->second->spans;
130 0 : row = new_row;
131 : }
132 :
133 : // Add a new span to the current row.
134 0 : AddSpanToRow(row->second, rect.left(), rect.right());
135 0 : top = row->second->bottom;
136 :
137 0 : MergeWithPrecedingRow(row);
138 :
139 : // Move to the next row.
140 0 : ++row;
141 : }
142 :
143 0 : if (row != rows_.end())
144 0 : MergeWithPrecedingRow(row);
145 : }
146 :
147 0 : void DesktopRegion::AddRects(const DesktopRect* rects, int count) {
148 0 : for (int i = 0; i < count; ++i) {
149 0 : AddRect(rects[i]);
150 : }
151 0 : }
152 :
153 0 : void DesktopRegion::MergeWithPrecedingRow(Rows::iterator row) {
154 0 : assert(row != rows_.end());
155 :
156 0 : if (row != rows_.begin()) {
157 0 : Rows::iterator previous_row = row;
158 0 : 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 0 : if (previous_row->second->bottom == row->second->top &&
163 0 : previous_row->second->spans == row->second->spans) {
164 0 : row->second->top = previous_row->second->top;
165 0 : delete previous_row->second;
166 0 : rows_.erase(previous_row);
167 : }
168 : }
169 0 : }
170 :
171 0 : 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 0 : for (Iterator it(region); !it.IsAtEnd(); it.Advance()) {
175 0 : AddRect(it.rect());
176 : }
177 0 : }
178 :
179 0 : void DesktopRegion::Intersect(const DesktopRegion& region1,
180 : const DesktopRegion& region2) {
181 0 : Clear();
182 :
183 0 : Rows::const_iterator it1 = region1.rows_.begin();
184 0 : Rows::const_iterator end1 = region1.rows_.end();
185 0 : Rows::const_iterator it2 = region2.rows_.begin();
186 0 : Rows::const_iterator end2 = region2.rows_.end();
187 0 : if (it1 == end1 || it2 == end2)
188 0 : return;
189 :
190 0 : while (it1 != end1 && it2 != end2) {
191 : // Arrange for |it1| to always be the top-most of the rows.
192 0 : if (it2->second->top < it1->second->top) {
193 0 : std::swap(it1, it2);
194 0 : std::swap(end1, end2);
195 : }
196 :
197 : // Skip |it1| if it doesn't intersect |it2| at all.
198 0 : if (it1->second->bottom <= it2->second->top) {
199 0 : ++it1;
200 0 : 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 0 : int32_t top = it2->second->top;
206 0 : int32_t bottom = std::min(it1->second->bottom, it2->second->bottom);
207 :
208 : Rows::iterator new_row = rows_.insert(
209 0 : rows_.end(), Rows::value_type(bottom, new Row(top, bottom)));
210 0 : IntersectRows(it1->second->spans, it2->second->spans,
211 0 : &new_row->second->spans);
212 0 : if (new_row->second->spans.empty()) {
213 0 : delete new_row->second;
214 0 : rows_.erase(new_row);
215 : } else {
216 0 : MergeWithPrecedingRow(new_row);
217 : }
218 :
219 : // If |it1| was completely consumed, move to the next one.
220 0 : if (it1->second->bottom == bottom)
221 0 : ++it1;
222 : // If |it2| was completely consumed, move to the next one.
223 0 : if (it2->second->bottom == bottom)
224 0 : ++it2;
225 : }
226 : }
227 :
228 : // static
229 0 : void DesktopRegion::IntersectRows(const RowSpanSet& set1,
230 : const RowSpanSet& set2,
231 : RowSpanSet* output) {
232 0 : RowSpanSet::const_iterator it1 = set1.begin();
233 0 : RowSpanSet::const_iterator end1 = set1.end();
234 0 : RowSpanSet::const_iterator it2 = set2.begin();
235 0 : RowSpanSet::const_iterator end2 = set2.end();
236 0 : assert(it1 != end1 && it2 != end2);
237 :
238 0 : do {
239 : // Arrange for |it1| to always be the left-most of the spans.
240 0 : if (it2->left < it1->left) {
241 0 : std::swap(it1, it2);
242 0 : std::swap(end1, end2);
243 : }
244 :
245 : // Skip |it1| if it doesn't intersect |it2| at all.
246 0 : if (it1->right <= it2->left) {
247 0 : ++it1;
248 0 : continue;
249 : }
250 :
251 0 : int32_t left = it2->left;
252 0 : int32_t right = std::min(it1->right, it2->right);
253 0 : assert(left < right);
254 :
255 0 : output->push_back(RowSpan(left, right));
256 :
257 : // If |it1| was completely consumed, move to the next one.
258 0 : if (it1->right == right)
259 0 : ++it1;
260 : // If |it2| was completely consumed, move to the next one.
261 0 : if (it2->right == right)
262 0 : ++it2;
263 0 : } while (it1 != end1 && it2 != end2);
264 0 : }
265 :
266 0 : void DesktopRegion::IntersectWith(const DesktopRegion& region) {
267 0 : DesktopRegion old_region;
268 0 : Swap(&old_region);
269 0 : Intersect(old_region, region);
270 0 : }
271 :
272 0 : void DesktopRegion::IntersectWith(const DesktopRect& rect) {
273 0 : DesktopRegion region;
274 0 : region.AddRect(rect);
275 0 : IntersectWith(region);
276 0 : }
277 :
278 0 : void DesktopRegion::Subtract(const DesktopRegion& region) {
279 0 : if (region.rows_.empty())
280 0 : return;
281 :
282 : // |row_b| refers to the current row being subtracted.
283 0 : Rows::const_iterator row_b = region.rows_.begin();
284 :
285 : // Current vertical position at which subtraction is happening.
286 0 : 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 0 : 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 0 : while (row_a != rows_.end() && row_b != region.rows_.end()) {
295 : // Skip |row_a| if it doesn't intersect with the |row_b|.
296 0 : if (row_a->second->bottom <= top) {
297 : // Each output row is merged with previously-processed rows before further
298 : // rows are processed.
299 0 : MergeWithPrecedingRow(row_a);
300 0 : ++row_a;
301 0 : continue;
302 : }
303 :
304 0 : 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 0 : assert(top <= row_a->second->bottom);
309 : Rows::iterator new_row = rows_.insert(
310 0 : row_a, Rows::value_type(top, new Row(row_a->second->top, top)));
311 0 : row_a->second->top = top;
312 0 : new_row->second->spans = row_a->second->spans;
313 0 : } 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 0 : top = row_a->second->top;
317 0 : if (top >= row_b->second->bottom) {
318 0 : ++row_b;
319 0 : if (row_b != region.rows_.end())
320 0 : top = row_b->second->top;
321 0 : continue;
322 : }
323 : }
324 :
325 0 : 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 0 : int bottom = row_b->second->bottom;
330 : Rows::iterator new_row =
331 0 : rows_.insert(row_a, Rows::value_type(bottom, new Row(top, bottom)));
332 0 : row_a->second->top = bottom;
333 0 : new_row->second->spans = row_a->second->spans;
334 0 : 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 0 : RowSpanSet new_spans;
340 0 : SubtractRows(row_a->second->spans, row_b->second->spans, &new_spans);
341 0 : new_spans.swap(row_a->second->spans);
342 0 : top = row_a->second->bottom;
343 :
344 0 : if (top >= row_b->second->bottom) {
345 0 : ++row_b;
346 0 : if (row_b != region.rows_.end())
347 0 : 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 0 : if (row_a->second->spans.empty()) {
353 0 : Rows::iterator row_to_delete = row_a;
354 0 : ++row_a;
355 0 : delete row_to_delete->second;
356 0 : rows_.erase(row_to_delete);
357 : } else {
358 0 : MergeWithPrecedingRow(row_a);
359 0 : ++row_a;
360 : }
361 : }
362 :
363 0 : if (row_a != rows_.end())
364 0 : MergeWithPrecedingRow(row_a);
365 : }
366 :
367 0 : void DesktopRegion::Subtract(const DesktopRect& rect) {
368 0 : DesktopRegion region;
369 0 : region.AddRect(rect);
370 0 : Subtract(region);
371 0 : }
372 :
373 0 : void DesktopRegion::Translate(int32_t dx, int32_t dy) {
374 0 : Rows new_rows;
375 :
376 0 : for (Rows::iterator it = rows_.begin(); it != rows_.end(); ++it) {
377 0 : Row* row = it->second;
378 :
379 0 : row->top += dy;
380 0 : row->bottom += dy;
381 :
382 0 : if (dx != 0) {
383 : // Translate each span.
384 0 : for (RowSpanSet::iterator span = row->spans.begin();
385 0 : span != row->spans.end(); ++span) {
386 0 : span->left += dx;
387 0 : span->right += dx;
388 : }
389 : }
390 :
391 0 : if (dy != 0)
392 0 : new_rows.insert(new_rows.end(), Rows::value_type(row->bottom, row));
393 : }
394 :
395 0 : if (dy != 0)
396 0 : new_rows.swap(rows_);
397 0 : }
398 :
399 0 : void DesktopRegion::Swap(DesktopRegion* region) {
400 0 : rows_.swap(region->rows_);
401 0 : }
402 :
403 : // static
404 0 : bool DesktopRegion::CompareSpanRight(const RowSpan& r, int32_t value) {
405 0 : return r.right < value;
406 : }
407 :
408 : // static
409 0 : bool DesktopRegion::CompareSpanLeft(const RowSpan& r, int32_t value) {
410 0 : return r.left < value;
411 : }
412 :
413 : // static
414 0 : 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 0 : if (row->spans.empty() || left > row->spans.back().right) {
419 0 : row->spans.push_back(RowSpan(left, right));
420 0 : 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 0 : CompareSpanRight);
427 0 : assert(start < row->spans.end());
428 :
429 : // Find the first span that starts after |right|.
430 : RowSpanSet::iterator end =
431 0 : std::lower_bound(start, row->spans.end(), right + 1, CompareSpanLeft);
432 0 : if (end == row->spans.begin()) {
433 : // There are no overlaps. Just insert the new span at the beginning.
434 0 : row->spans.insert(row->spans.begin(), RowSpan(left, right));
435 0 : return;
436 : }
437 :
438 : // Move end to the left, so that it points the last span that ends at or
439 : // before |right|.
440 0 : end--;
441 :
442 : // At this point [start, end] is the range of spans that intersect with the
443 : // new one.
444 0 : if (end < start) {
445 : // There are no overlaps. Just insert the new span at the correct position.
446 0 : row->spans.insert(start, RowSpan(left, right));
447 0 : return;
448 : }
449 :
450 0 : left = std::min(left, start->left);
451 0 : right = std::max(right, end->right);
452 :
453 : // Replace range [start, end] with the new span.
454 0 : *start = RowSpan(left, right);
455 0 : ++start;
456 0 : ++end;
457 0 : if (start < end)
458 0 : row->spans.erase(start, end);
459 : }
460 :
461 : // static
462 0 : 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 0 : CompareSpanLeft);
468 0 : return it != row.spans.end() && *it == span;
469 : }
470 :
471 : // static
472 0 : void DesktopRegion::SubtractRows(const RowSpanSet& set_a,
473 : const RowSpanSet& set_b,
474 : RowSpanSet* output) {
475 0 : assert(!set_a.empty() && !set_b.empty());
476 :
477 0 : 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 0 : 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 0 : if (it_b == set_b.end() || it_a->right < it_b->left) {
485 0 : output->push_back(*it_a);
486 0 : continue;
487 : }
488 :
489 : // Iterate over |set_b| spans that may intersect with |it_a|.
490 0 : int pos = it_a->left;
491 0 : while (it_b != set_b.end() && it_b->left < it_a->right) {
492 0 : if (it_b->left > pos)
493 0 : output->push_back(RowSpan(pos, it_b->left));
494 0 : if (it_b->right > pos) {
495 0 : pos = it_b->right;
496 0 : if (pos >= it_a->right)
497 0 : break;
498 : }
499 0 : ++it_b;
500 : }
501 0 : if (pos < it_a->right)
502 0 : output->push_back(RowSpan(pos, it_a->right));
503 : }
504 0 : }
505 :
506 0 : DesktopRegion::Iterator::Iterator(const DesktopRegion& region)
507 : : region_(region),
508 0 : row_(region.rows_.begin()),
509 0 : previous_row_(region.rows_.end()) {
510 0 : if (!IsAtEnd()) {
511 0 : assert(row_->second->spans.size() > 0);
512 0 : row_span_ = row_->second->spans.begin();
513 0 : UpdateCurrentRect();
514 : }
515 0 : }
516 :
517 0 : DesktopRegion::Iterator::~Iterator() {}
518 :
519 0 : bool DesktopRegion::Iterator::IsAtEnd() const {
520 0 : return row_ == region_.rows_.end();
521 : }
522 :
523 0 : void DesktopRegion::Iterator::Advance() {
524 0 : assert(!IsAtEnd());
525 :
526 : while (true) {
527 0 : ++row_span_;
528 0 : if (row_span_ == row_->second->spans.end()) {
529 0 : previous_row_ = row_;
530 0 : ++row_;
531 0 : if (row_ != region_.rows_.end()) {
532 0 : assert(row_->second->spans.size() > 0);
533 0 : row_span_ = row_->second->spans.begin();
534 : }
535 : }
536 :
537 0 : if (IsAtEnd())
538 0 : 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 0 : if (previous_row_ != region_.rows_.end() &&
544 0 : previous_row_->second->bottom == row_->second->top &&
545 0 : IsSpanInRow(*previous_row_->second, *row_span_)) {
546 0 : continue;
547 : }
548 :
549 0 : break;
550 : }
551 :
552 0 : assert(!IsAtEnd());
553 0 : UpdateCurrentRect();
554 : }
555 :
556 0 : void DesktopRegion::Iterator::UpdateCurrentRect() {
557 : // Merge the current rectangle with the matching spans from later rows.
558 : int bottom;
559 0 : Rows::const_iterator bottom_row = row_;
560 0 : Rows::const_iterator previous;
561 0 : do {
562 0 : bottom = bottom_row->second->bottom;
563 0 : previous = bottom_row;
564 0 : ++bottom_row;
565 0 : } while (bottom_row != region_.rows_.end() &&
566 0 : previous->second->bottom == bottom_row->second->top &&
567 0 : IsSpanInRow(*bottom_row->second, *row_span_));
568 0 : rect_ = DesktopRect::MakeLTRB(row_span_->left, row_->second->top,
569 0 : row_span_->right, bottom);
570 0 : }
571 :
572 : } // namespace webrtc
|
