1 /*
2  * Copyright (c) 2022-2023 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 #ifndef RENDER_SERVICE_BASE_CORE_COMMON_RS_OCCLUSION_REGION_H
16 #define RENDER_SERVICE_BASE_CORE_COMMON_RS_OCCLUSION_REGION_H
17 
18 #include <algorithm>
19 #include <iostream>
20 #include <vector>
21 #include <string>
22 
23 #include "rs_rect.h"
24 #include "common/rs_macros.h"
25 #include "platform/common/rs_log.h"
26 
27 namespace OHOS {
28 namespace Rosen {
29 namespace Occlusion {
30 
31 constexpr int MAX_REGION_VALUE = 1000000;       // normal region value should not exceed 1000000
32 constexpr int MIN_REGION_VALUE = -1000000;      // normal region value should not less than -1000000
33 class Rect {
34 public:
35     // assumption: left-top is [0,0]
36     int left_ = 0;
37     int top_ = 0;
38     int right_ = 0;
39     int bottom_ = 0;
40 
Rect()41     Rect() : left_(0), top_(0), right_(0), bottom_(0) {}
42     Rect(int l, int t, int r, int b, bool checkValue = true)
43         : left_(l), top_(t), right_(r), bottom_(b)
44     {
45         if (checkValue) {
46             CheckAndCorrectValue();
47             if (left_ != l || top_ != t || right_ != r || bottom_ != b) {
48                 RS_LOGE("Occlusion::Rect initialized with invalid value, ltrb[%{public}d, %{public}d, %{public}d, "
49                     "%{public}d], should in range [%{public}d, %{public}d]",
50                     l, t, t, b, MIN_REGION_VALUE, MAX_REGION_VALUE);
51             }
52         }
53     }
54 
55     Rect(const RectI& r, bool checkValue = true)
56         : left_(r.left_), top_(r.top_), right_(r.GetRight()), bottom_(r.GetBottom())
57     {
58         if (checkValue) {
59             CheckAndCorrectValue();
60             if (left_ != r.left_ || top_ != r.top_ || right_ != r.GetRight() || bottom_ != r.GetBottom()) {
61                 RS_LOGE("Occlusion::Rect initialized with invalid value, ltrb[%{public}d, %{public}d, %{public}d, "
62                     "%{public}d], should in range [%{public}d, %{public}d]",
63                     r.left_, r.top_, r.GetRight(), r.GetBottom(), MIN_REGION_VALUE, MAX_REGION_VALUE);
64             }
65         }
66     }
67 
SetEmpty()68     void SetEmpty()
69     {
70         left_ = 0;
71         top_ = 0;
72         right_ = 0;
73         bottom_ = 0;
74     }
75 
IsEmpty()76     bool IsEmpty() const
77     {
78         return left_ >= right_ || top_ >= bottom_;
79     }
80 
81     bool operator==(const Rect& r) const
82     {
83         return left_ == r.left_ && top_ == r.top_ && right_ == r.right_ && bottom_ == r.bottom_;
84     }
85 
86     bool operator!=(const Rect& r) const
87     {
88         return !(*this == r);
89     }
90 
Intersect(const Rect & rect)91     Rect Intersect(const Rect& rect) const
92     {
93         int left = std::max(left_, rect.left_);
94         int top = std::max(top_, rect.top_);
95         int right = std::min(right_, rect.right_);
96         int bottom = std::min(bottom_, rect.bottom_);
97         if ((right - left <= 0) || (bottom - top <= 0)) {
98             return Rect(0, 0, 0, 0);
99         } else {
100             return Rect(left, top, right, bottom);
101         }
102     }
103 
IsIntersect(const Rect & rect)104     bool IsIntersect(const Rect& rect) const
105     {
106         int left = std::max(left_, rect.left_);
107         int top = std::max(top_, rect.top_);
108         int right = std::min(right_, rect.right_);
109         int bottom = std::min(bottom_, rect.bottom_);
110         return (right - left > 0) && (bottom - top > 0);
111     }
112 
GetRectInfo()113     std::string GetRectInfo() const
114     {
115         return std::string("[" +
116             std::to_string(left_) + ", " +
117             std::to_string(top_) + ", " +
118             std::to_string(right_ - left_) + ", " +
119             std::to_string(bottom_ - top_) + "]");
120     }
121 
ToRectI()122     RectI ToRectI() const
123     {
124         return RectI{left_, top_, right_ - left_, bottom_ - top_};
125     }
126 
Area()127     int Area() const
128     {
129         if (IsEmpty()) {
130             return 0;
131         }
132         return (right_ - left_) * (bottom_ - top_);
133     }
134 
IntersectArea(const Rect & r)135     int IntersectArea(const Rect& r) const
136     {
137         Rect res = this->Intersect(r);
138         return res.Area();
139     }
140 
141 private:
CheckAndCorrectValue()142     void CheckAndCorrectValue()
143     {
144         left_ = std::max(left_, MIN_REGION_VALUE);
145         top_ = std::max(top_, MIN_REGION_VALUE);
146         right_ = std::min(right_, MAX_REGION_VALUE);
147         bottom_ = std::min(bottom_, MAX_REGION_VALUE);
148         if (IsEmpty()) {
149             SetEmpty();
150         }
151     }
152 };
153 
154 std::ostream& operator<<(std::ostream& os, const Rect& r);
155 
156 /*
157     Event: Used for record a rect edge in/out event
158     y_: rect edge Y value
159     type: OPEN/CLOSE: lhs rect in/out; VOID_OPEN/VOID_CLOSE: rhs rect in/out
160 */
161 class Event {
162 public:
163     // Use different value to differentiate lhs and rhs ranges
164     enum Type { OPEN = 1, CLOSE = -1, VOID_OPEN = 2, VOID_CLOSE = -2 };
165     int y_ = 0;
166     Type type_ = Type::OPEN;
167     int left_ = 0;
168     int right_ = 0;
169 
Event(int y,Type type,int l,int r)170     Event(int y, Type type, int l, int r) : y_(y), type_(type), left_(l), right_(r) {}
171 };
172 bool EventSortByY(const Event& e1, const Event& e2);
173 
174 class Range {
175 public:
176     int start_ = 0;
177     int end_ = 0;
Range(int s,int e)178     Range(int s, int e) : start_(s), end_(e) {}
179     bool operator==(const Range& r)
180     {
181         return start_ == r.start_ && end_ == r.end_;
182     }
183 };
184 
185 class Node {
186 public:
187     int start_ = 0;
188     int end_ = 0;
189     int mid_ = 0;
190     int positive_count_ = 0; // used for counting current lhs ranges
191     int negative_count_ = 0; // used for counting current rhs ranges
192     Node* left_ = nullptr;
193     Node* right_ = nullptr;
194 
Node(int s,int e)195     Node(int s, int e) : start_(s), end_(e), mid_((s + e) >> 1) {}
~Node()196     ~Node()
197     {
198         if (left_ != nullptr) {
199             delete left_;
200             left_ = nullptr;
201         }
202         if (right_ != nullptr) {
203             delete right_;
204             right_ = nullptr;
205         }
206     }
207 
208     // push current node [start, end] into range result, merge last range if possible
PushRange(std::vector<Range> & res)209     inline void PushRange(std::vector<Range>& res)
210     {
211         if (res.size() > 0 && start_ == res[res.size() - 1].end_) {
212             // merge range with previous range if their end and start share same point
213             res[res.size() - 1].end_ = end_;
214         } else {
215             res.emplace_back(Range { start_, end_ });
216         }
217     }
218 
IsLeaf()219     inline bool IsLeaf()
220     {
221         return left_ == nullptr && right_ == nullptr;
222     }
223 
224     // update segment tree
225     void Update(int updateStart, int updateEnd, Event::Type type);
226     // get ranges where positive_count_ and negtive_count_ are both positive
227     void GetAndRange(std::vector<Range>& res, bool isParentNodePos, bool isParentNodeNeg);
228     // get ranges where positive_count_ or negtive_count_ is positive
229     void GetOrRange(std::vector<Range>& res, bool isParentNodePos, bool isParentNodeNeg);
230     // get ranges where either positive_count_ and negtive_count_ are both positive
231     void GetXOrRange(std::vector<Range>& res, bool isParentNodePos, bool isParentNodeNeg);
232     // get ranges where positive_count_ is positive and negtive_count_ not
233     void GetSubRange(std::vector<Range>& res, bool isParentNodePos, bool isParentNodeNeg);
234 };
235 
236 class RSB_EXPORT Region {
237 public:
238     enum OP {
239         // bit index 0: lhs
240         // bit index 1: lhs & rhs
241         // bit index 2: rhs
242         AND = 2, // 010
243         OR  = 7, // 111
244         XOR = 5, // 101
245         SUB = 1  // 001
246     };
247 
248     Region() = default;
Region(Rect r)249     Region(Rect r)
250     {
251         rects_.push_back(r);
252         bound_ = Rect { r };
253     }
254 
Region(const Region & reg)255     Region(const Region& reg) : rects_(reg.rects_), bound_(reg.bound_) {}
~Region()256     ~Region() {}
257 
Reset()258     void Reset()
259     {
260         rects_.clear();
261         bound_ = Rect {};
262     }
263 
GetRegionRectsRef()264     std::vector<Rect>& GetRegionRectsRef()
265     {
266         return rects_;
267     }
268 
GetRegionRects()269     const std::vector<Rect>& GetRegionRects() const
270     {
271         return rects_;
272     }
273 
GetRegionRectIs()274     std::vector<RectI> GetRegionRectIs() const
275     {
276         std::vector<RectI> rectIs;
277         for (const auto& rect : rects_) {
278             rectIs.emplace_back(rect.ToRectI());
279         }
280         return rectIs;
281     }
282 
GetSize()283     int GetSize() const
284     {
285         return rects_.size();
286     }
GetBound()287     Rect GetBound() const
288     {
289         return bound_;
290     }
GetBoundRef()291     Rect& GetBoundRef()
292     {
293         return bound_;
294     }
IsEmpty()295     bool IsEmpty() const
296     {
297         return rects_.size() == 0 || bound_.IsEmpty();
298     }
GetRegionInfo()299     std::string GetRegionInfo() const
300     {
301         std::string info;
302         if (IsEmpty()) {
303             info = "Region [Empty]";
304         } else {
305             info = "Region " + std::to_string(rects_.size()) + ": ";
306             for (auto& r : rects_) {
307                 info.append(r.GetRectInfo());
308             }
309         }
310         return info;
311     }
312 
CBegin()313     inline std::vector<Rect>::const_iterator CBegin() const
314     {
315         return rects_.cbegin();
316     }
CEnd()317     inline std::vector<Rect>::const_iterator CEnd() const
318     {
319         return rects_.cend();
320     }
Begin()321     inline std::vector<Rect>::iterator Begin()
322     {
323         return rects_.begin();
324     }
End()325     inline std::vector<Rect>::const_iterator End()
326     {
327         return rects_.end();
328     }
Size()329     inline size_t Size() const
330     {
331         return rects_.size();
332     }
333 
334     // bound of all region rects
335     void MakeBound();
336 
IsIntersectWith(const Rect & r)337     bool IsIntersectWith(const Rect& r) const
338     {
339         for (const Rect& rect : rects_) {
340             if (rect.IsIntersect(r)) {
341                 return true;
342             }
343         }
344         return false;
345     }
346 
347     /* core Region logic operation function, the return region's rects is guaranteed no-intersection
348         (rect in rects_ do not intersect with each other)
349     */
350     void RegionOp(Region& r1, Region& r2, Region& res, Region::OP op);
351     void RegionOpLocal(Region& r1, Region& r2, Region& res, Region::OP op);
352     void RegionOpAccelate(Region& r1, Region& r2, Region& res, Region::OP op);
353 
354     Region& OperationSelf(Region& r, Region::OP op);
355     // replace region with and result
356     Region& AndSelf(Region& r);
357     // replace region with or result
358     Region& OrSelf(Region& r);
359     // replace region with xor result
360     Region& XOrSelf(Region& r);
361     // replace region with sub result
362     Region& SubSelf(Region& r);
363 
364     // return intersection region
365     Region And(Region& r);
366     // return merge region
367     Region Or(Region& r);
368     // return merge region subtract intersection region
369     Region Xor(Region& r);
370     // return region belongs to Region(lhs) but not Region(rhs)
371     Region Sub(Region& r);
372 
373     // get current region's area, return the sum of the areas of all rectangles (as they are not intersect each other)
374     int Area() const;
375     // return the area of the region where the current region intersects the rectangle
376     int IntersectArea(const Rect& r) const;
377 
378 private:
379     class Rects {
380     public:
381         std::vector<Rect> preRects;
382         std::vector<Rect> curRects;
383         int preY = 0;
384         int curY = 0;
385     };
386     // get ranges from segmentTree node according to logical operation type
387     void getRange(std::vector<Range>& ranges, Node& node, OP op);
388     // update tmp rects and region according to current ranges
389     void UpdateRects(Rects& r, std::vector<Range>& ranges, std::vector<int>& indexAt, Region& res);
390 
391 private:
392     std::vector<Rect> rects_;
393     Rect bound_;
394     static bool _s_so_loaded_;
395 };
396 std::ostream& operator<<(std::ostream& os, const Region& r);
397 } // namespace Occlusion
398 } // namespace Rosen
399 } // namespace OHOS
400 #endif // RENDER_SERVICE_BASE_CORE_COMMON_RS_OCCLUSION_REGION_H