Implement DesktopRegion subtraction.
Region subtraction is used in chromoting client, so it's needed to
replace SkRegion.
R=wez@chromium.org
Review URL: https://webrtc-codereview.appspot.com/2205004
git-svn-id: http://webrtc.googlecode.com/svn/trunk@4741 4adac7df-926f-26a2-2b94-8c16560cd09d
diff --git a/webrtc/modules/desktop_capture/desktop_region.cc b/webrtc/modules/desktop_capture/desktop_region.cc
index 77e0472..4159cd4 100644
--- a/webrtc/modules/desktop_capture/desktop_region.cc
+++ b/webrtc/modules/desktop_capture/desktop_region.cc
@@ -107,7 +107,7 @@
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 of the two,
+ // two, at |top|, and leave |row| referring to the lower of the two,
// ready to insert a new span into.
assert(top <= row->second->bottom);
Rows::iterator new_row = rows_.insert(
@@ -272,6 +272,95 @@
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.
+ assert(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 (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;
@@ -370,6 +459,39 @@
return it != row.spans.end() && *it == span;
}
+// static
+void DesktopRegion::SubtractRows(const RowSpanSet& set_a,
+ const RowSpanSet& set_b,
+ RowSpanSet* output) {
+ assert(!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);
+ 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));
+ }
+ pos = it_b->right;
+ ++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()),
diff --git a/webrtc/modules/desktop_capture/desktop_region.h b/webrtc/modules/desktop_capture/desktop_region.h
index 04ea5e1..fc7c6ed 100644
--- a/webrtc/modules/desktop_capture/desktop_region.h
+++ b/webrtc/modules/desktop_capture/desktop_region.h
@@ -119,6 +119,12 @@
// Clips the region by the |rect|.
void IntersectWith(const DesktopRect& rect);
+ // Subtracts |region| from the current content of the region.
+ void Subtract(const DesktopRegion& region);
+
+ // Subtracts |rect| from the current content of the region.
+ void Subtract(const DesktopRect& rect);
+
// Adds (dx, dy) to the position of the region.
void Translate(int32_t dx, int32_t dy);
@@ -141,6 +147,10 @@
const RowSpanSet& set2,
RowSpanSet* output);
+ static void SubtractRows(const RowSpanSet& set_a,
+ const RowSpanSet& set_b,
+ RowSpanSet* output);
+
// Merges |row| with the row above it if they contain the same spans. Doesn't
// do anything if called with |row| set to rows_.begin() (i.e. first row of
// the region). If the rows were merged |row| remains a valid iterator to the
diff --git a/webrtc/modules/desktop_capture/desktop_region_unittest.cc b/webrtc/modules/desktop_capture/desktop_region_unittest.cc
index de4b326..2c21661 100644
--- a/webrtc/modules/desktop_capture/desktop_region_unittest.cc
+++ b/webrtc/modules/desktop_capture/desktop_region_unittest.cc
@@ -444,6 +444,104 @@
}
}
+TEST(DesktopRegionTest, Subtract) {
+ struct Case {
+ int input1_count;
+ DesktopRect input1_rects[4];
+ int input2_count;
+ DesktopRect input2_rects[4];
+ int expected_count;
+ DesktopRect expected_rects[5];
+ } cases[] = {
+ // Subtract one rect from another.
+ { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
+ 1, { DesktopRect::MakeLTRB(50, 50, 150, 150) },
+ 2, { DesktopRect::MakeLTRB(0, 0, 100, 50),
+ DesktopRect::MakeLTRB(0, 50, 50, 100) } },
+
+ { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
+ 1, { DesktopRect::MakeLTRB(-50, -50, 50, 50) },
+ 2, { DesktopRect::MakeLTRB(50, 0, 100, 50),
+ DesktopRect::MakeLTRB(0, 50, 100, 100) } },
+
+ { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
+ 1, { DesktopRect::MakeLTRB(-50, 50, 50, 150) },
+ 2, { DesktopRect::MakeLTRB(0, 0, 100, 50),
+ DesktopRect::MakeLTRB(50, 50, 100, 100) } },
+
+ { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
+ 1, { DesktopRect::MakeLTRB(50, 50, 150, 70) },
+ 3, { DesktopRect::MakeLTRB(0, 0, 100, 50),
+ DesktopRect::MakeLTRB(0, 50, 50, 70),
+ DesktopRect::MakeLTRB(0, 70, 100, 100) } },
+
+ { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
+ 1, { DesktopRect::MakeLTRB(50, 50, 70, 70) },
+ 4, { DesktopRect::MakeLTRB(0, 0, 100, 50),
+ DesktopRect::MakeLTRB(0, 50, 50, 70),
+ DesktopRect::MakeLTRB(70, 50, 100, 70),
+ DesktopRect::MakeLTRB(0, 70, 100, 100) } },
+
+ // Empty result.
+ { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
+ 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
+ 0, {} },
+
+ { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
+ 1, { DesktopRect::MakeLTRB(-10, -10, 110, 110) },
+ 0, {} },
+
+ { 2, { DesktopRect::MakeLTRB(0, 0, 100, 100),
+ DesktopRect::MakeLTRB(50, 50, 150, 150) },
+ 2, { DesktopRect::MakeLTRB(0, 0, 100, 100),
+ DesktopRect::MakeLTRB(50, 50, 150, 150) },
+ 0, {} },
+
+ // One rect out of disjoint set.
+ { 3, { DesktopRect::MakeLTRB(0, 0, 10, 10),
+ DesktopRect::MakeLTRB(20, 20, 30, 30),
+ DesktopRect::MakeLTRB(40, 0, 50, 10) },
+ 1, { DesktopRect::MakeLTRB(20, 20, 30, 30) },
+ 2, { DesktopRect::MakeLTRB(0, 0, 10, 10),
+ DesktopRect::MakeLTRB(40, 0, 50, 10) } },
+
+ // Row merging.
+ { 3, { DesktopRect::MakeLTRB(0, 0, 100, 50),
+ DesktopRect::MakeLTRB(0, 50, 150, 70),
+ DesktopRect::MakeLTRB(0, 70, 100, 100) },
+ 1, { DesktopRect::MakeLTRB(100, 50, 150, 70) },
+ 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) } },
+
+ // No-op subtraction.
+ { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
+ 1, { DesktopRect::MakeLTRB(100, 0, 200, 100) },
+ 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) } },
+
+ { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
+ 1, { DesktopRect::MakeLTRB(-100, 0, 0, 100) },
+ 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) } },
+
+ { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
+ 1, { DesktopRect::MakeLTRB(0, 100, 0, 200) },
+ 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) } },
+
+ { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
+ 1, { DesktopRect::MakeLTRB(0, -100, 100, 0) },
+ 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) } },
+ };
+
+ for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
+ SCOPED_TRACE(i);
+
+ DesktopRegion r1(cases[i].input1_rects, cases[i].input1_count);
+ DesktopRegion r2(cases[i].input2_rects, cases[i].input2_count);
+
+ r1.Subtract(r2);
+
+ CompareRegion(r1, cases[i].expected_rects, cases[i].expected_count);
+ }
+}
+
TEST(DesktopRegionTest, DISABLED_Performance) {
for (int c = 0; c < 1000; ++c) {
DesktopRegion r;