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 #ifndef MODULES_DESKTOP_CAPTURE_DESKTOP_REGION_H_
12 #define MODULES_DESKTOP_CAPTURE_DESKTOP_REGION_H_
13 
14 #include <stdint.h>
15 
16 #include <map>
17 #include <vector>
18 
19 #include "modules/desktop_capture/desktop_geometry.h"
20 #include "rtc_base/system/rtc_export.h"
21 
22 namespace webrtc {
23 
24 // DesktopRegion represents a region of the screen or window.
25 //
26 // Internally each region is stored as a set of rows where each row contains one
27 // or more rectangles aligned vertically.
28 class RTC_EXPORT DesktopRegion {
29  private:
30   // The following private types need to be declared first because they are used
31   // in the public Iterator.
32 
33   // RowSpan represents a horizontal span withing a single row.
34   struct RowSpan {
35     RowSpan(int32_t left, int32_t right);
36 
37     // Used by std::vector<>.
38     bool operator==(const RowSpan& that) const {
39       return left == that.left && right == that.right;
40     }
41 
42     int32_t left;
43     int32_t right;
44   };
45 
46   typedef std::vector<RowSpan> RowSpanSet;
47 
48   // Row represents a single row of a region. A row is set of rectangles that
49   // have the same vertical position.
50   struct Row {
51     Row(const Row&);
52     Row(Row&&);
53     Row(int32_t top, int32_t bottom);
54     ~Row();
55 
56     int32_t top;
57     int32_t bottom;
58 
59     RowSpanSet spans;
60   };
61 
62   // Type used to store list of rows in the region. The bottom position of row
63   // is used as the key so that rows are always ordered by their position. The
64   // map stores pointers to make Translate() more efficient.
65   typedef std::map<int, Row*> Rows;
66 
67  public:
68   // Iterator that can be used to iterate over rectangles of a DesktopRegion.
69   // The region must not be mutated while the iterator is used.
70   class RTC_EXPORT Iterator {
71    public:
72     explicit Iterator(const DesktopRegion& target);
73     ~Iterator();
74 
75     bool IsAtEnd() const;
76     void Advance();
77 
rect()78     const DesktopRect& rect() const { return rect_; }
79 
80    private:
81     const DesktopRegion& region_;
82 
83     // Updates |rect_| based on the current |row_| and |row_span_|. If
84     // |row_span_| matches spans on consecutive rows then they are also merged
85     // into |rect_|, to generate more efficient output.
86     void UpdateCurrentRect();
87 
88     Rows::const_iterator row_;
89     Rows::const_iterator previous_row_;
90     RowSpanSet::const_iterator row_span_;
91     DesktopRect rect_;
92   };
93 
94   DesktopRegion();
95   explicit DesktopRegion(const DesktopRect& rect);
96   DesktopRegion(const DesktopRect* rects, int count);
97   DesktopRegion(const DesktopRegion& other);
98   ~DesktopRegion();
99 
100   DesktopRegion& operator=(const DesktopRegion& other);
101 
is_empty()102   bool is_empty() const { return rows_.empty(); }
103 
104   bool Equals(const DesktopRegion& region) const;
105 
106   // Reset the region to be empty.
107   void Clear();
108 
109   // Reset region to contain just |rect|.
110   void SetRect(const DesktopRect& rect);
111 
112   // Adds specified rect(s) or region to the region.
113   void AddRect(const DesktopRect& rect);
114   void AddRects(const DesktopRect* rects, int count);
115   void AddRegion(const DesktopRegion& region);
116 
117   // Finds intersection of two regions and stores them in the current region.
118   void Intersect(const DesktopRegion& region1, const DesktopRegion& region2);
119 
120   // Same as above but intersects content of the current region with |region|.
121   void IntersectWith(const DesktopRegion& region);
122 
123   // Clips the region by the |rect|.
124   void IntersectWith(const DesktopRect& rect);
125 
126   // Subtracts |region| from the current content of the region.
127   void Subtract(const DesktopRegion& region);
128 
129   // Subtracts |rect| from the current content of the region.
130   void Subtract(const DesktopRect& rect);
131 
132   // Adds (dx, dy) to the position of the region.
133   void Translate(int32_t dx, int32_t dy);
134 
135   void Swap(DesktopRegion* region);
136 
137  private:
138   // Comparison functions used for std::lower_bound(). Compare left or right
139   // edges withs a given |value|.
140   static bool CompareSpanLeft(const RowSpan& r, int32_t value);
141   static bool CompareSpanRight(const RowSpan& r, int32_t value);
142 
143   // Adds a new span to the row, coalescing spans if necessary.
144   static void AddSpanToRow(Row* row, int32_t left, int32_t right);
145 
146   // Returns true if the |span| exists in the given |row|.
147   static bool IsSpanInRow(const Row& row, const RowSpan& rect);
148 
149   // Calculates the intersection of two sets of spans.
150   static void IntersectRows(const RowSpanSet& set1,
151                             const RowSpanSet& set2,
152                             RowSpanSet* output);
153 
154   static void SubtractRows(const RowSpanSet& set_a,
155                            const RowSpanSet& set_b,
156                            RowSpanSet* output);
157 
158   // Merges |row| with the row above it if they contain the same spans. Doesn't
159   // do anything if called with |row| set to rows_.begin() (i.e. first row of
160   // the region). If the rows were merged |row| remains a valid iterator to the
161   // merged row.
162   void MergeWithPrecedingRow(Rows::iterator row);
163 
164   Rows rows_;
165 };
166 
167 }  // namespace webrtc
168 
169 #endif  // MODULES_DESKTOP_CAPTURE_DESKTOP_REGION_H_
170