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