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
18 #include <map>
19 #include <set>
20 #include "platform/common/rs_log.h"
21 #include "platform/common/rs_innovation.h"
22
23 namespace OHOS {
24 namespace Rosen {
25 namespace Occlusion {
26 static Rect _s_empty_rect_ { 0, 0, 0, 0 };
27 static Rect _s_invalid_rect_ { 0, 0, -1, -1 };
28 bool Region::_s_so_loaded_ = false;
29 void (*Region::regionOpFromSO)(Region& r1, Region& r2, Region& res, Region::OP op) = nullptr;
30
31
operator <<(std::ostream & os,const Rect & r)32 std::ostream& operator<<(std::ostream& os, const Rect& r)
33 {
34 os << "{" << r.left_ << "," << r.top_ << "," << r.right_ << "," << r.bottom_ << "}";
35 return os;
36 }
37
EventSortByY(const Event & e1,const Event & e2)38 bool EventSortByY(const Event& e1, const Event& e2)
39 {
40 if (e1.y_ == e2.y_) {
41 return e1.type_ < e2.type_;
42 }
43 return e1.y_ < e2.y_;
44 }
45
Update(int updateStart,int updateEnd,Event::Type type)46 void Node::Update(int updateStart, int updateEnd, Event::Type type)
47 {
48 if (updateStart >= updateEnd) {
49 return;
50 }
51 if (updateStart == start_ && updateEnd == end_) {
52 if (type == Event::Type::OPEN || type == Event::Type::CLOSE) {
53 positive_count_ += type;
54 } else {
55 negative_count_ += type;
56 }
57 } else {
58 if (left_ == nullptr) {
59 left_ = new Node { start_, mid_ };
60 }
61 if (right_ == nullptr) {
62 right_ = new Node { mid_, end_ };
63 }
64 left_->Update(updateStart, mid_ < updateEnd ? mid_ : updateEnd, type);
65 right_->Update(mid_ > updateStart ? mid_ : updateStart, updateEnd, type);
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.GetRegionRects().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.GetRegionRects().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
InitDynamicLibraryFunction()211 void Region::InitDynamicLibraryFunction()
212 {
213 if (RSInnovation::_s_regionOpFromSo != nullptr) {
214 regionOpFromSO = reinterpret_cast<void (*)(Region & r1, Region & r2, Region & res, Region::OP op)>
215 (RSInnovation::_s_regionOpFromSo);
216 }
217 return;
218 }
219
RegionOp(Region & r1,Region & r2,Region & res,Region::OP op)220 void Region::RegionOp(Region& r1, Region& r2, Region& res, Region::OP op)
221 {
222 if (r1.IsEmpty()) {
223 if (op == Region::OP::AND || op == Region::OP::SUB) {
224 res = Region();
225 return;
226 } else {
227 res = r2;
228 return;
229 }
230 }
231 if (r2.IsEmpty()) {
232 if (op == Region::OP::AND) {
233 res = Region();
234 return;
235 } else {
236 res = r1;
237 return;
238 }
239 }
240 if (RSInnovation::_s_occlusionCullingFuncLoaded && RSInnovation::_s_occlusionCullingSoEnabled) {
241 regionOpFromSO(r1, r2, res, op);
242 } else {
243 RegionOpLocal(r1, r2, res, op);
244 }
245 }
246
RegionOpLocal(Region & r1,Region & r2,Region & res,Region::OP op)247 void Region::RegionOpLocal(Region& r1, Region& r2, Region& res, Region::OP op)
248 {
249 r1.MakeBound();
250 r2.MakeBound();
251 res.GetRegionRects().clear();
252 std::vector<Event> events;
253 std::set<int> xs;
254
255 for (auto& r : r1.GetRegionRects()) {
256 events.emplace_back(Event { r.top_, Event::Type::OPEN, r.left_, r.right_ });
257 events.emplace_back(Event { r.bottom_, Event::Type::CLOSE, r.left_, r.right_ });
258 xs.insert(r.left_);
259 xs.insert(r.right_);
260 }
261 for (auto& r : r2.GetRegionRects()) {
262 events.emplace_back(Event { r.top_, Event::Type::VOID_OPEN, r.left_, r.right_ });
263 events.emplace_back(Event { r.bottom_, Event::Type::VOID_CLOSE, r.left_, r.right_ });
264 xs.insert(r.left_);
265 xs.insert(r.right_);
266 }
267
268 if (events.size() == 0) {
269 return;
270 }
271
272 std::map<int, int> indexOf;
273 std::vector<int> indexAt;
274 MakeEnumerate(xs, indexOf, indexAt);
275 sort(events.begin(), events.end(), EventSortByY);
276
277 Node rootNode { 0, static_cast<int>(indexOf.size() - 1) };
278
279 std::vector<Range> ranges;
280 Rects r;
281 r.preY = events[0].y_;
282 r.curY = events[0].y_;
283 for (auto& e : events) {
284 r.curY = e.y_;
285 ranges.clear();
286 getRange(ranges, rootNode, op);
287 if (r.curY > r.preY) {
288 UpdateRects(r, ranges, indexAt, res);
289 }
290 rootNode.Update(indexOf[e.left_], indexOf[e.right_], e.type_);
291 r.preY = r.curY;
292 }
293 copy(r.preRects.begin(), r.preRects.end(), back_inserter(res.GetRegionRects()));
294 res.MakeBound();
295 }
296
OperationSelf(Region & r,Region::OP op)297 Region& Region::OperationSelf(Region& r, Region::OP op)
298 {
299 Region r1(*this);
300 RegionOp(r1, r, *this, op);
301 return *this;
302 }
303
AndSelf(Region & r)304 Region& Region::AndSelf(Region& r)
305 {
306 return OperationSelf(r, Region::OP::AND);
307 }
308
OrSelf(Region & r)309 Region& Region::OrSelf(Region& r)
310 {
311 return OperationSelf(r, Region::OP::OR);
312 }
313
XOrSelf(Region & r)314 Region& Region::XOrSelf(Region& r)
315 {
316 return OperationSelf(r, Region::OP::XOR);
317 }
318
SubSelf(Region & r)319 Region& Region::SubSelf(Region& r)
320 {
321 return OperationSelf(r, Region::OP::SUB);
322 }
323
And(Region & r)324 Region Region::And(Region& r)
325 {
326 Region res;
327 RegionOp(*this, r, res, Region::OP::AND);
328 return res;
329 }
330
Or(Region & r)331 Region Region::Or(Region& r)
332 {
333 Region res;
334 RegionOp(*this, r, res, Region::OP::OR);
335 return res;
336 }
337
Xor(Region & r)338 Region Region::Xor(Region& r)
339 {
340 Region res;
341 RegionOp(*this, r, res, Region::OP::XOR);
342 return res;
343 }
344
Sub(Region & r)345 Region Region::Sub(Region& r)
346 {
347 Region res;
348 RegionOp(*this, r, res, Region::OP::SUB);
349 return res;
350 }
351
operator <<(std::ostream & os,const Region & r)352 std::ostream& operator<<(std::ostream& os, const Region& r)
353 {
354 os << "{";
355 os << r.GetSize() << ": ";
356 for (const Rect& rect : r.GetRegionRects()) {
357 os << rect;
358 }
359 os << "}" << std::endl;
360 return os;
361 }
362 } // namespace Occlusion
363 } // namespace Rosen
364 } // namespace OHOS
365