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 
16 #include "common/rs_occlusion_region.h"
17 #include "common/rs_occlusion_region_helper.h"
18 
19 #include <map>
20 #include <set>
21 #include "platform/common/rs_innovation.h"
22 
23 namespace OHOS {
24 namespace Rosen {
25 namespace Occlusion {
26 
operator <<(std::ostream & os,const Rect & r)27 std::ostream& operator<<(std::ostream& os, const Rect& r)
28 {
29     os << "{" << r.left_ << "," << r.top_ << "," << r.right_ << "," << r.bottom_ << "}";
30     return os;
31 }
32 
EventSortByY(const Event & e1,const Event & e2)33 bool EventSortByY(const Event& e1, const Event& e2)
34 {
35     if (e1.y_ == e2.y_) {
36         return e1.type_ < e2.type_;
37     }
38     return e1.y_ < e2.y_;
39 }
40 
Update(int updateStart,int updateEnd,Event::Type type)41 void Node::Update(int updateStart, int updateEnd, Event::Type type)
42 {
43     if (updateStart >= updateEnd) {
44         return;
45     }
46     if (updateStart == start_ && updateEnd == end_) {
47         if (type == Event::Type::OPEN || type == Event::Type::CLOSE) {
48             positive_count_ += type;
49         } else {
50             negative_count_ += type;
51         }
52     } else {
53         if (left_ == nullptr) {
54             left_ = new Node { start_, mid_ };
55         }
56         if (right_ == nullptr) {
57             right_ = new Node { mid_, end_ };
58         }
59         // In case the heap memory allocation fails
60         if (left_ != nullptr) {
61             left_->Update(updateStart, mid_ < updateEnd ? mid_ : updateEnd, type);
62         }
63         if (right_ != nullptr) {
64             right_->Update(mid_ > updateStart ? mid_ : updateStart, updateEnd, type);
65         }
66     }
67 }
68 
GetAndRange(std::vector<Range> & res,bool isParentNodePos=false,bool isParentNodeNeg=false)69 void Node::GetAndRange(std::vector<Range>& res, bool isParentNodePos = false, bool isParentNodeNeg = false)
70 {
71     bool isPos = isParentNodePos || (positive_count_ > 0);
72     bool isNeg = isParentNodeNeg || (negative_count_ > 0);
73     if (isPos && isNeg) {
74         PushRange(res);
75     } else {
76         if (left_ != nullptr) {
77             left_->GetAndRange(res, isPos, isNeg);
78         }
79         if (right_ != nullptr) {
80             right_->GetAndRange(res, isPos, isNeg);
81         }
82     }
83 }
84 
GetOrRange(std::vector<Range> & res,bool isParentNodePos=false,bool isParentNodeNeg=false)85 void Node::GetOrRange(std::vector<Range>& res, bool isParentNodePos = false, bool isParentNodeNeg = false)
86 {
87     bool isPos = isParentNodePos || (positive_count_ > 0);
88     bool isNeg = isParentNodeNeg || (negative_count_ > 0);
89     if (isPos || isNeg) {
90         PushRange(res);
91     } else {
92         if (left_ != nullptr) {
93             left_->GetOrRange(res, isPos, isNeg);
94         }
95         if (right_ != nullptr) {
96             right_->GetOrRange(res, isPos, isNeg);
97         }
98     }
99 }
100 
GetXOrRange(std::vector<Range> & res,bool isParentNodePos=false,bool isParentNodeNeg=false)101 void Node::GetXOrRange(std::vector<Range>& res, bool isParentNodePos = false, bool isParentNodeNeg = false)
102 {
103     bool isPos = isParentNodePos || (positive_count_ > 0);
104     bool isNeg = isParentNodeNeg || (negative_count_ > 0);
105     if (((isPos && !isNeg) || (!isPos && isNeg)) && IsLeaf()) {
106         PushRange(res);
107     } else if (isPos && isNeg) {
108         return;
109     } else {
110         if (left_ != nullptr) {
111             left_->GetXOrRange(res, isPos, isNeg);
112         }
113         if (right_ != nullptr) {
114             right_->GetXOrRange(res, isPos, isNeg);
115         }
116     }
117 }
118 
GetSubRange(std::vector<Range> & res,bool isParentNodePos=false,bool isParentNodeNeg=false)119 void Node::GetSubRange(std::vector<Range>& res, bool isParentNodePos = false, bool isParentNodeNeg = false)
120 {
121     bool isPos = isParentNodePos || (positive_count_ > 0);
122     bool isNeg = isParentNodeNeg || (negative_count_ > 0);
123     if (IsLeaf() && isPos && !isNeg) {
124         PushRange(res);
125     } else if (isNeg) {
126         return;
127     } else {
128         if (left_ != nullptr) {
129             left_->GetSubRange(res, isPos, isNeg);
130         }
131         if (right_ != nullptr) {
132             right_->GetSubRange(res, isPos, isNeg);
133         }
134     }
135 }
136 
MakeEnumerate(std::set<int> & ys,std::map<int,int> & indexOf,std::vector<int> & indexAt)137 void MakeEnumerate(std::set<int>& ys, std::map<int, int>& indexOf, std::vector<int>& indexAt)
138 {
139     auto it = ys.begin();
140     int index = 0;
141     while (it != ys.end()) {
142         indexOf[*it] = index++;
143         indexAt.push_back(*it);
144         ++it;
145     }
146     return;
147 }
148 
getRange(std::vector<Range> & ranges,Node & node,Region::OP op)149 void Region::getRange(std::vector<Range>& ranges, Node& node, Region::OP op)
150 {
151     switch (op) {
152         case Region::OP::AND:
153             node.GetAndRange(ranges);
154             break;
155         case Region::OP::OR:
156             node.GetOrRange(ranges);
157             break;
158         case Region::OP::XOR:
159             node.GetXOrRange(ranges);
160             break;
161         case Region::OP::SUB:
162             node.GetSubRange(ranges);
163             break;
164         default:
165             break;
166     }
167     return;
168 }
169 
UpdateRects(Rects & r,std::vector<Range> & ranges,std::vector<int> & indexAt,Region & res)170 void Region::UpdateRects(Rects& r, std::vector<Range>& ranges, std::vector<int>& indexAt, Region& res)
171 {
172     uint32_t i = 0;
173     uint32_t j = 0;
174     while (i < r.preRects.size() && j < ranges.size()) {
175         if (r.preRects[i].left_ == indexAt[ranges[j].start_] && r.preRects[i].right_ == indexAt[ranges[j].end_]) {
176             r.curRects.emplace_back(Rect { r.preRects[i].left_, r.preRects[i].top_, r.preRects[i].right_, r.curY });
177             i++;
178             j++;
179         } else if (r.preRects[i].right_ < indexAt[ranges[j].end_]) {
180             res.GetRegionRectsRef().push_back(r.preRects[i]);
181             i++;
182         } else {
183             r.curRects.emplace_back(Rect { indexAt[ranges[j].start_], r.preY, indexAt[ranges[j].end_], r.curY });
184             j++;
185         }
186     }
187     for (; j < ranges.size(); j++) {
188         r.curRects.emplace_back(Rect { indexAt[ranges[j].start_], r.preY, indexAt[ranges[j].end_], r.curY });
189     }
190     for (; i < r.preRects.size(); i++) {
191         res.GetRegionRectsRef().push_back(r.preRects[i]);
192     }
193     r.preRects.clear();
194     r.preRects.swap(r.curRects);
195     return;
196 }
197 
MakeBound()198 void Region::MakeBound()
199 {
200     if (rects_.size()) {
201         bound_ = rects_[0];
202         for (const auto& r : rects_) {
203             bound_.left_ = std::min(r.left_, bound_.left_);
204             bound_.top_ = std::min(r.top_, bound_.top_);
205             bound_.right_ = std::max(r.right_, bound_.right_);
206             bound_.bottom_ = std::max(r.bottom_, bound_.bottom_);
207         }
208     }
209 }
210 
RegionOp(Region & r1,Region & r2,Region & res,Region::OP op)211 void Region::RegionOp(Region& r1, Region& r2, Region& res, Region::OP op)
212 {
213     if (r1.IsEmpty()) {
214         if (op == Region::OP::AND || op == Region::OP::SUB) {
215             res = Region();
216         } else {
217             res = r2;
218         }
219         return;
220     }
221     if (r2.IsEmpty()) {
222         if (op == Region::OP::AND) {
223             res = Region();
224         } else {
225             res = r1;
226         }
227         return;
228     }
229     RegionOpAccelate(r1, r2, res, op);
230 }
231 
RegionOpLocal(Region & r1,Region & r2,Region & res,Region::OP op)232 void Region::RegionOpLocal(Region& r1, Region& r2, Region& res, Region::OP op)
233 {
234     r1.MakeBound();
235     r2.MakeBound();
236     res.GetRegionRectsRef().clear();
237     std::vector<Event> events;
238     std::set<int> xs;
239 
240     for (auto& r : r1.GetRegionRects()) {
241         events.emplace_back(Event { r.top_, Event::Type::OPEN, r.left_, r.right_ });
242         events.emplace_back(Event { r.bottom_, Event::Type::CLOSE, r.left_, r.right_ });
243         xs.insert(r.left_);
244         xs.insert(r.right_);
245     }
246     for (auto& r : r2.GetRegionRects()) {
247         events.emplace_back(Event { r.top_, Event::Type::VOID_OPEN, r.left_, r.right_ });
248         events.emplace_back(Event { r.bottom_, Event::Type::VOID_CLOSE, r.left_, r.right_ });
249         xs.insert(r.left_);
250         xs.insert(r.right_);
251     }
252 
253     if (events.size() == 0) {
254         return;
255     }
256 
257     std::map<int, int> indexOf;
258     std::vector<int> indexAt;
259     MakeEnumerate(xs, indexOf, indexAt);
260     sort(events.begin(), events.end(), EventSortByY);
261 
262     Node rootNode { 0, static_cast<int>(indexOf.size() - 1) };
263 
264     std::vector<Range> ranges;
265     Rects r;
266     r.preY = events[0].y_;
267     r.curY = events[0].y_;
268     for (auto& e : events) {
269         r.curY = e.y_;
270         ranges.clear();
271         getRange(ranges, rootNode, op);
272         if (r.curY > r.preY) {
273             UpdateRects(r, ranges, indexAt, res);
274         }
275         rootNode.Update(indexOf[e.left_], indexOf[e.right_], e.type_);
276         r.preY = r.curY;
277     }
278     copy(r.preRects.begin(), r.preRects.end(), back_inserter(res.GetRegionRectsRef()));
279     res.MakeBound();
280 }
281 
RegionOpAccelate(Region & r1,Region & r2,Region & res,Region::OP op)282 void Region::RegionOpAccelate(Region& r1, Region& r2, Region& res, Region::OP op)
283 {
284     RectsPtr lhs(r1.CBegin(), r1.Size());
285     RectsPtr rhs(r2.CBegin(), r2.Size());
286     Assembler assembler(res);
287     OuterLooper outer(lhs, rhs);
288     Rect current(0, 0, 0, 0); // init value is irrelevant
289     do {
290         InnerLooper inner(outer);
291         RectType relationship = outer.NextScanline(current.top_, current.bottom_);
292         if (op == Region::OP::AND && relationship != RectType::LHS_RHS_BOTH) {
293             continue;
294         }
295         if (op == Region::OP::SUB && relationship == RectType::RHS_ONLY) {
296             continue;
297         }
298         inner.Init(relationship);
299         do {
300             RectType rectType = inner.NextRect(current.left_, current.right_);
301             if (((static_cast<uint32_t>(op) & static_cast<uint32_t>(rectType)) != 0) && !current.IsEmpty()) {
302                 assembler.Insert(current);
303             }
304         } while (!inner.IsDone());
305     } while (!outer.isDone());
306     assembler.FlushVerticalSpan();
307     return;
308 }
309 
OperationSelf(Region & r,Region::OP op)310 Region& Region::OperationSelf(Region& r, Region::OP op)
311 {
312     Region r1(*this);
313     RegionOp(r1, r, *this, op);
314     return *this;
315 }
316 
AndSelf(Region & r)317 Region& Region::AndSelf(Region& r)
318 {
319     return OperationSelf(r, Region::OP::AND);
320 }
321 
OrSelf(Region & r)322 Region& Region::OrSelf(Region& r)
323 {
324     return OperationSelf(r, Region::OP::OR);
325 }
326 
XOrSelf(Region & r)327 Region& Region::XOrSelf(Region& r)
328 {
329     return OperationSelf(r, Region::OP::XOR);
330 }
331 
SubSelf(Region & r)332 Region& Region::SubSelf(Region& r)
333 {
334     return OperationSelf(r, Region::OP::SUB);
335 }
336 
And(Region & r)337 Region Region::And(Region& r)
338 {
339     Region res;
340     RegionOp(*this, r, res, Region::OP::AND);
341     return res;
342 }
343 
Or(Region & r)344 Region Region::Or(Region& r)
345 {
346     Region res;
347     RegionOp(*this, r, res, Region::OP::OR);
348     return res;
349 }
350 
Xor(Region & r)351 Region Region::Xor(Region& r)
352 {
353     Region res;
354     RegionOp(*this, r, res, Region::OP::XOR);
355     return res;
356 }
357 
Sub(Region & r)358 Region Region::Sub(Region& r)
359 {
360     Region res;
361     RegionOp(*this, r, res, Region::OP::SUB);
362     return res;
363 }
364 
operator <<(std::ostream & os,const Region & r)365 std::ostream& operator<<(std::ostream& os, const Region& r)
366 {
367     os << "{";
368     os << r.GetSize() << ": ";
369     for (const Rect& rect : r.GetRegionRects()) {
370         os << rect;
371     }
372     os << "}" << std::endl;
373     return os;
374 }
375 
Area() const376 int Region::Area() const
377 {
378     int areaSum = 0;
379     for (const auto& rect : GetRegionRects()) {
380         areaSum += rect.Area();
381     }
382     return areaSum;
383 }
384 
IntersectArea(const Rect & r) const385 int Region::IntersectArea(const Rect& r) const
386 {
387     if (r.IsEmpty()) {
388         return 0;
389     }
390     int areaSum = 0;
391     for (const auto& rect : GetRegionRects()) {
392         areaSum += rect.IntersectArea(r);
393     }
394     return areaSum;
395 }
396 
397 } // namespace Occlusion
398 } // namespace Rosen
399 } // namespace OHOS
400