tor-browser

desktop_region.cc (17532B)

---

/*
*  Copyright (c) 2013 The WebRTC project authors. All Rights Reserved.
*
*  Use of this source code is governed by a BSD-style license
*  that can be found in the LICENSE file in the root of the source
*  tree. An additional intellectual property rights grant can be found
*  in the file PATENTS.  All contributing project authors may
*  be found in the AUTHORS file in the root of the source tree.
*/

#include "modules/desktop_capture/desktop_region.h"

#include <algorithm>
#include <cstdint>
#include <utility>

#include "modules/desktop_capture/desktop_geometry.h"
#include "rtc_base/checks.h"

namespace webrtc {

DesktopRegion::RowSpan::RowSpan(int32_t left, int32_t right)
   : left(left), right(right) {}

DesktopRegion::Row::Row(const Row&) = default;
DesktopRegion::Row::Row(Row&&) = default;

DesktopRegion::Row::Row(int32_t top, int32_t bottom)
   : top(top), bottom(bottom) {}

DesktopRegion::Row::~Row() {}

DesktopRegion::DesktopRegion() {}

DesktopRegion::DesktopRegion(const DesktopRect& rect) {
 AddRect(rect);
}

DesktopRegion::DesktopRegion(const DesktopRect* rects, int count) {
 AddRects(rects, count);
}

DesktopRegion::DesktopRegion(const DesktopRegion& other) {
 *this = other;
}

DesktopRegion::~DesktopRegion() {
 Clear();
}

DesktopRegion& DesktopRegion::operator=(const DesktopRegion& other) {
 Clear();
 rows_ = other.rows_;
 for (Rows::iterator it = rows_.begin(); it != rows_.end(); ++it) {
   // Copy each row.
   Row* row = it->second;
   it->second = new Row(*row);
 }
 return *this;
}

bool DesktopRegion::Equals(const DesktopRegion& region) const {
 // Iterate over rows of the tow regions and compare each row.
 Rows::const_iterator it1 = rows_.begin();
 Rows::const_iterator it2 = region.rows_.begin();
 while (it1 != rows_.end()) {
   if (it2 == region.rows_.end() || it1->first != it2->first ||
       it1->second->top != it2->second->top ||
       it1->second->bottom != it2->second->bottom ||
       it1->second->spans != it2->second->spans) {
     return false;
   }
   ++it1;
   ++it2;
 }
 return it2 == region.rows_.end();
}

void DesktopRegion::Clear() {
 for (Rows::iterator row = rows_.begin(); row != rows_.end(); ++row) {
   delete row->second;
 }
 rows_.clear();
}

void DesktopRegion::SetRect(const DesktopRect& rect) {
 Clear();
 AddRect(rect);
}

void DesktopRegion::AddRect(const DesktopRect& rect) {
 if (rect.is_empty())
   return;

 // Top of the part of the `rect` that hasn't been inserted yet. Increased as
 // we iterate over the rows until it reaches `rect.bottom()`.
 int top = rect.top();

 // Iterate over all rows that may intersect with `rect` and add new rows when
 // necessary.
 Rows::iterator row = rows_.upper_bound(top);
 while (top < rect.bottom()) {
   if (row == rows_.end() || top < row->second->top) {
     // If `top` is above the top of the current `row` then add a new row above
     // the current one.
     int32_t bottom = rect.bottom();
     if (row != rows_.end() && row->second->top < bottom)
       bottom = row->second->top;
     row = rows_.insert(row, Rows::value_type(bottom, new Row(top, bottom)));
   } else if (top > row->second->top) {
     // If the `top` falls in the middle of the `row` then split `row` into
     // two, at `top`, and leave `row` referring to the lower of the two,
     // ready to insert a new span into.
     RTC_DCHECK_LE(top, row->second->bottom);
     Rows::iterator new_row = rows_.insert(
         row, Rows::value_type(top, new Row(row->second->top, top)));
     row->second->top = top;
     new_row->second->spans = row->second->spans;
   }

   if (rect.bottom() < row->second->bottom) {
     // If the bottom of the `rect` falls in the middle of the `row` split
     // `row` into two, at `top`, and leave `row` referring to the upper of
     // the two, ready to insert a new span into.
     Rows::iterator new_row = rows_.insert(
         row, Rows::value_type(rect.bottom(), new Row(top, rect.bottom())));
     row->second->top = rect.bottom();
     new_row->second->spans = row->second->spans;
     row = new_row;
   }

   // Add a new span to the current row.
   AddSpanToRow(row->second, rect.left(), rect.right());
   top = row->second->bottom;

   MergeWithPrecedingRow(row);

   // Move to the next row.
   ++row;
 }

 if (row != rows_.end())
   MergeWithPrecedingRow(row);
}

void DesktopRegion::AddRects(const DesktopRect* rects, int count) {
 for (int i = 0; i < count; ++i) {
   AddRect(rects[i]);
 }
}

void DesktopRegion::MergeWithPrecedingRow(Rows::iterator row) {
 RTC_DCHECK(row != rows_.end());

 if (row != rows_.begin()) {
   Rows::iterator previous_row = row;
   previous_row--;

   // If `row` and `previous_row` are next to each other and contain the same
   // set of spans then they can be merged.
   if (previous_row->second->bottom == row->second->top &&
       previous_row->second->spans == row->second->spans) {
     row->second->top = previous_row->second->top;
     delete previous_row->second;
     rows_.erase(previous_row);
   }
 }
}

void DesktopRegion::AddRegion(const DesktopRegion& region) {
 // TODO(sergeyu): This function is not optimized - potentially it can iterate
 // over rows of the two regions similar to how it works in Intersect().
 for (Iterator it(region); !it.IsAtEnd(); it.Advance()) {
   AddRect(it.rect());
 }
}

void DesktopRegion::Intersect(const DesktopRegion& region1,
                             const DesktopRegion& region2) {
 Clear();

 Rows::const_iterator it1 = region1.rows_.begin();
 Rows::const_iterator end1 = region1.rows_.end();
 Rows::const_iterator it2 = region2.rows_.begin();
 Rows::const_iterator end2 = region2.rows_.end();
 if (it1 == end1 || it2 == end2)
   return;

 while (it1 != end1 && it2 != end2) {
   // Arrange for `it1` to always be the top-most of the rows.
   if (it2->second->top < it1->second->top) {
     std::swap(it1, it2);
     std::swap(end1, end2);
   }

   // Skip `it1` if it doesn't intersect `it2` at all.
   if (it1->second->bottom <= it2->second->top) {
     ++it1;
     continue;
   }

   // Top of the `it1` row is above the top of `it2`, so top of the
   // intersection is always the top of `it2`.
   int32_t top = it2->second->top;
   int32_t bottom = std::min(it1->second->bottom, it2->second->bottom);

   Rows::iterator new_row = rows_.insert(
       rows_.end(), Rows::value_type(bottom, new Row(top, bottom)));
   IntersectRows(it1->second->spans, it2->second->spans,
                 &new_row->second->spans);
   if (new_row->second->spans.empty()) {
     delete new_row->second;
     rows_.erase(new_row);
   } else {
     MergeWithPrecedingRow(new_row);
   }

   // If `it1` was completely consumed, move to the next one.
   if (it1->second->bottom == bottom)
     ++it1;
   // If `it2` was completely consumed, move to the next one.
   if (it2->second->bottom == bottom)
     ++it2;
 }
}

// static
void DesktopRegion::IntersectRows(const RowSpanSet& set1,
                                 const RowSpanSet& set2,
                                 RowSpanSet* output) {
 RowSpanSet::const_iterator it1 = set1.begin();
 RowSpanSet::const_iterator end1 = set1.end();
 RowSpanSet::const_iterator it2 = set2.begin();
 RowSpanSet::const_iterator end2 = set2.end();
 RTC_DCHECK(it1 != end1 && it2 != end2);

 do {
   // Arrange for `it1` to always be the left-most of the spans.
   if (it2->left < it1->left) {
     std::swap(it1, it2);
     std::swap(end1, end2);
   }

   // Skip `it1` if it doesn't intersect `it2` at all.
   if (it1->right <= it2->left) {
     ++it1;
     continue;
   }

   int32_t left = it2->left;
   int32_t right = std::min(it1->right, it2->right);
   RTC_DCHECK_LT(left, right);

   output->push_back(RowSpan(left, right));

   // If `it1` was completely consumed, move to the next one.
   if (it1->right == right)
     ++it1;
   // If `it2` was completely consumed, move to the next one.
   if (it2->right == right)
     ++it2;
 } while (it1 != end1 && it2 != end2);
}

void DesktopRegion::IntersectWith(const DesktopRegion& region) {
 DesktopRegion old_region;
 Swap(&old_region);
 Intersect(old_region, region);
}

void DesktopRegion::IntersectWith(const DesktopRect& rect) {
 DesktopRegion region;
 region.AddRect(rect);
 IntersectWith(region);
}

void DesktopRegion::Subtract(const DesktopRegion& region) {
 if (region.rows_.empty())
   return;

 // `row_b` refers to the current row being subtracted.
 Rows::const_iterator row_b = region.rows_.begin();

 // Current vertical position at which subtraction is happening.
 int top = row_b->second->top;

 // `row_a` refers to the current row we are subtracting from. Skip all rows
 // above `top`.
 Rows::iterator row_a = rows_.upper_bound(top);

 // Step through rows of the both regions subtracting content of `row_b` from
 // `row_a`.
 while (row_a != rows_.end() && row_b != region.rows_.end()) {
   // Skip `row_a` if it doesn't intersect with the `row_b`.
   if (row_a->second->bottom <= top) {
     // Each output row is merged with previously-processed rows before further
     // rows are processed.
     MergeWithPrecedingRow(row_a);
     ++row_a;
     continue;
   }

   if (top > row_a->second->top) {
     // If `top` falls in the middle of `row_a` then split `row_a` into two, at
     // `top`, and leave `row_a` referring to the lower of the two, ready to
     // subtract spans from.
     RTC_DCHECK_LE(top, row_a->second->bottom);
     Rows::iterator new_row = rows_.insert(
         row_a, Rows::value_type(top, new Row(row_a->second->top, top)));
     row_a->second->top = top;
     new_row->second->spans = row_a->second->spans;
   } else if (top < row_a->second->top) {
     // If the `top` is above `row_a` then skip the range between `top` and
     // top of `row_a` because it's empty.
     top = row_a->second->top;
     if (top >= row_b->second->bottom) {
       ++row_b;
       if (row_b != region.rows_.end())
         top = row_b->second->top;
       continue;
     }
   }

   if (row_b->second->bottom < row_a->second->bottom) {
     // If the bottom of `row_b` falls in the middle of the `row_a` split
     // `row_a` into two, at `top`, and leave `row_a` referring to the upper of
     // the two, ready to subtract spans from.
     int bottom = row_b->second->bottom;
     Rows::iterator new_row =
         rows_.insert(row_a, Rows::value_type(bottom, new Row(top, bottom)));
     row_a->second->top = bottom;
     new_row->second->spans = row_a->second->spans;
     row_a = new_row;
   }

   // At this point the vertical range covered by `row_a` lays within the
   // range covered by `row_b`. Subtract `row_b` spans from `row_a`.
   RowSpanSet new_spans;
   SubtractRows(row_a->second->spans, row_b->second->spans, &new_spans);
   new_spans.swap(row_a->second->spans);
   top = row_a->second->bottom;

   if (top >= row_b->second->bottom) {
     ++row_b;
     if (row_b != region.rows_.end())
       top = row_b->second->top;
   }

   // Check if the row is empty after subtraction and delete it. Otherwise move
   // to the next one.
   if (row_a->second->spans.empty()) {
     Rows::iterator row_to_delete = row_a;
     ++row_a;
     delete row_to_delete->second;
     rows_.erase(row_to_delete);
   } else {
     MergeWithPrecedingRow(row_a);
     ++row_a;
   }
 }

 if (row_a != rows_.end())
   MergeWithPrecedingRow(row_a);
}

void DesktopRegion::Subtract(const DesktopRect& rect) {
 DesktopRegion region;
 region.AddRect(rect);
 Subtract(region);
}

void DesktopRegion::Translate(int32_t dx, int32_t dy) {
 Rows new_rows;

 for (Rows::iterator it = rows_.begin(); it != rows_.end(); ++it) {
   Row* row = it->second;

   row->top += dy;
   row->bottom += dy;

   if (dx != 0) {
     // Translate each span.
     for (RowSpanSet::iterator span = row->spans.begin();
          span != row->spans.end(); ++span) {
       span->left += dx;
       span->right += dx;
     }
   }

   if (dy != 0)
     new_rows.insert(new_rows.end(), Rows::value_type(row->bottom, row));
 }

 if (dy != 0)
   new_rows.swap(rows_);
}

void DesktopRegion::Swap(DesktopRegion* region) {
 rows_.swap(region->rows_);
}

// static
bool DesktopRegion::CompareSpanRight(const RowSpan& r, int32_t value) {
 return r.right < value;
}

// static
bool DesktopRegion::CompareSpanLeft(const RowSpan& r, int32_t value) {
 return r.left < value;
}

// static
void DesktopRegion::AddSpanToRow(Row* row, int left, int right) {
 // First check if the new span is located to the right of all existing spans.
 // This is an optimization to avoid binary search in the case when rectangles
 // are inserted sequentially from left to right.
 if (row->spans.empty() || left > row->spans.back().right) {
   row->spans.push_back(RowSpan(left, right));
   return;
 }

 // Find the first span that ends at or after `left`.
 RowSpanSet::iterator start = std::lower_bound(
     row->spans.begin(), row->spans.end(), left, CompareSpanRight);
 RTC_DCHECK(start < row->spans.end());

 // Find the first span that starts after `right`.
 RowSpanSet::iterator end =
     std::lower_bound(start, row->spans.end(), right + 1, CompareSpanLeft);
 if (end == row->spans.begin()) {
   // There are no overlaps. Just insert the new span at the beginning.
   row->spans.insert(row->spans.begin(), RowSpan(left, right));
   return;
 }

 // Move end to the left, so that it points the last span that ends at or
 // before `right`.
 end--;

 // At this point [start, end] is the range of spans that intersect with the
 // new one.
 if (end < start) {
   // There are no overlaps. Just insert the new span at the correct position.
   row->spans.insert(start, RowSpan(left, right));
   return;
 }

 left = std::min(left, start->left);
 right = std::max(right, end->right);

 // Replace range [start, end] with the new span.
 *start = RowSpan(left, right);
 ++start;
 ++end;
 if (start < end)
   row->spans.erase(start, end);
}

// static
bool DesktopRegion::IsSpanInRow(const Row& row, const RowSpan& span) {
 // Find the first span that starts at or after `span.left` and then check if
 // it's the same span.
 RowSpanSet::const_iterator it = std::lower_bound(
     row.spans.begin(), row.spans.end(), span.left, CompareSpanLeft);
 return it != row.spans.end() && *it == span;
}

// static
void DesktopRegion::SubtractRows(const RowSpanSet& set_a,
                                const RowSpanSet& set_b,
                                RowSpanSet* output) {
 RTC_DCHECK(!set_a.empty() && !set_b.empty());

 RowSpanSet::const_iterator it_b = set_b.begin();

 // Iterate over all spans in `set_a` adding parts of it that do not intersect
 // with `set_b` to the `output`.
 for (RowSpanSet::const_iterator it_a = set_a.begin(); it_a != set_a.end();
      ++it_a) {
   // If there is no intersection then append the current span and continue.
   if (it_b == set_b.end() || it_a->right < it_b->left) {
     output->push_back(*it_a);
     continue;
   }

   // Iterate over `set_b` spans that may intersect with `it_a`.
   int pos = it_a->left;
   while (it_b != set_b.end() && it_b->left < it_a->right) {
     if (it_b->left > pos)
       output->push_back(RowSpan(pos, it_b->left));
     if (it_b->right > pos) {
       pos = it_b->right;
       if (pos >= it_a->right)
         break;
     }
     ++it_b;
   }
   if (pos < it_a->right)
     output->push_back(RowSpan(pos, it_a->right));
 }
}

DesktopRegion::Iterator::Iterator(const DesktopRegion& region)
   : region_(region),
     row_(region.rows_.begin()),
     previous_row_(region.rows_.end()) {
 if (!IsAtEnd()) {
   RTC_DCHECK_GT(row_->second->spans.size(), 0);
   row_span_ = row_->second->spans.begin();
   UpdateCurrentRect();
 }
}

DesktopRegion::Iterator::~Iterator() {}

bool DesktopRegion::Iterator::IsAtEnd() const {
 return row_ == region_.rows_.end();
}

void DesktopRegion::Iterator::Advance() {
 RTC_DCHECK(!IsAtEnd());

 while (true) {
   ++row_span_;
   if (row_span_ == row_->second->spans.end()) {
     previous_row_ = row_;
     ++row_;
     if (row_ != region_.rows_.end()) {
       RTC_DCHECK_GT(row_->second->spans.size(), 0);
       row_span_ = row_->second->spans.begin();
     }
   }

   if (IsAtEnd())
     return;

   // If the same span exists on the previous row then skip it, as we've
   // already returned this span merged into the previous one, via
   // UpdateCurrentRect().
   if (previous_row_ != region_.rows_.end() &&
       previous_row_->second->bottom == row_->second->top &&
       IsSpanInRow(*previous_row_->second, *row_span_)) {
     continue;
   }

   break;
 }

 RTC_DCHECK(!IsAtEnd());
 UpdateCurrentRect();
}

void DesktopRegion::Iterator::UpdateCurrentRect() {
 // Merge the current rectangle with the matching spans from later rows.
 int bottom;
 Rows::const_iterator bottom_row = row_;
 Rows::const_iterator previous;
 do {
   bottom = bottom_row->second->bottom;
   previous = bottom_row;
   ++bottom_row;
 } while (bottom_row != region_.rows_.end() &&
          previous->second->bottom == bottom_row->second->top &&
          IsSpanInRow(*bottom_row->second, *row_span_));
 rect_ = DesktopRect::MakeLTRB(row_span_->left, row_->second->top,
                               row_span_->right, bottom);
}

}  // namespace webrtc