1 /*
2  * Copyright (C) 2015 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 #include "ClipArea.h"
17 
18 #include "utils/LinearAllocator.h"
19 
20 #include <SkPath.h>
21 #include <limits>
22 #include <type_traits>
23 
24 namespace android {
25 namespace uirenderer {
26 
handlePoint(Rect & transformedBounds,const Matrix4 & transform,float x,float y)27 static void handlePoint(Rect& transformedBounds, const Matrix4& transform, float x, float y) {
28     Vertex v = {x, y};
29     transform.mapPoint(v.x, v.y);
30     transformedBounds.expandToCover(v.x, v.y);
31 }
32 
transformAndCalculateBounds(const Rect & r,const Matrix4 & transform)33 Rect transformAndCalculateBounds(const Rect& r, const Matrix4& transform) {
34     const float kMinFloat = std::numeric_limits<float>::lowest();
35     const float kMaxFloat = std::numeric_limits<float>::max();
36     Rect transformedBounds = {kMaxFloat, kMaxFloat, kMinFloat, kMinFloat};
37     handlePoint(transformedBounds, transform, r.left, r.top);
38     handlePoint(transformedBounds, transform, r.right, r.top);
39     handlePoint(transformedBounds, transform, r.left, r.bottom);
40     handlePoint(transformedBounds, transform, r.right, r.bottom);
41     return transformedBounds;
42 }
43 
dump() const44 void ClipBase::dump() const {
45     ALOGD("mode %d" RECT_STRING, mode, RECT_ARGS(rect));
46 }
47 
48 /*
49  * TransformedRectangle
50  */
51 
TransformedRectangle()52 TransformedRectangle::TransformedRectangle() {}
53 
TransformedRectangle(const Rect & bounds,const Matrix4 & transform)54 TransformedRectangle::TransformedRectangle(const Rect& bounds, const Matrix4& transform)
55         : mBounds(bounds), mTransform(transform) {}
56 
canSimplyIntersectWith(const TransformedRectangle & other) const57 bool TransformedRectangle::canSimplyIntersectWith(const TransformedRectangle& other) const {
58     return mTransform == other.mTransform;
59 }
60 
intersectWith(const TransformedRectangle & other)61 void TransformedRectangle::intersectWith(const TransformedRectangle& other) {
62     mBounds.doIntersect(other.mBounds);
63 }
64 
isEmpty() const65 bool TransformedRectangle::isEmpty() const {
66     return mBounds.isEmpty();
67 }
68 
69 /*
70  * RectangleList
71  */
72 
RectangleList()73 RectangleList::RectangleList() : mTransformedRectanglesCount(0) {}
74 
isEmpty() const75 bool RectangleList::isEmpty() const {
76     if (mTransformedRectanglesCount < 1) {
77         return true;
78     }
79 
80     for (int i = 0; i < mTransformedRectanglesCount; i++) {
81         if (mTransformedRectangles[i].isEmpty()) {
82             return true;
83         }
84     }
85     return false;
86 }
87 
getTransformedRectanglesCount() const88 int RectangleList::getTransformedRectanglesCount() const {
89     return mTransformedRectanglesCount;
90 }
91 
getTransformedRectangle(int i) const92 const TransformedRectangle& RectangleList::getTransformedRectangle(int i) const {
93     return mTransformedRectangles[i];
94 }
95 
setEmpty()96 void RectangleList::setEmpty() {
97     mTransformedRectanglesCount = 0;
98 }
99 
set(const Rect & bounds,const Matrix4 & transform)100 void RectangleList::set(const Rect& bounds, const Matrix4& transform) {
101     mTransformedRectanglesCount = 1;
102     mTransformedRectangles[0] = TransformedRectangle(bounds, transform);
103 }
104 
intersectWith(const Rect & bounds,const Matrix4 & transform)105 bool RectangleList::intersectWith(const Rect& bounds, const Matrix4& transform) {
106     TransformedRectangle newRectangle(bounds, transform);
107 
108     // Try to find a rectangle with a compatible transformation
109     int index = 0;
110     for (; index < mTransformedRectanglesCount; index++) {
111         TransformedRectangle& tr(mTransformedRectangles[index]);
112         if (tr.canSimplyIntersectWith(newRectangle)) {
113             tr.intersectWith(newRectangle);
114             return true;
115         }
116     }
117 
118     // Add it to the list if there is room
119     if (index < kMaxTransformedRectangles) {
120         mTransformedRectangles[index] = newRectangle;
121         mTransformedRectanglesCount += 1;
122         return true;
123     }
124 
125     // This rectangle list is full
126     return false;
127 }
128 
calculateBounds() const129 Rect RectangleList::calculateBounds() const {
130     Rect bounds;
131     for (int index = 0; index < mTransformedRectanglesCount; index++) {
132         const TransformedRectangle& tr(mTransformedRectangles[index]);
133         if (index == 0) {
134             bounds = tr.transformedBounds();
135         } else {
136             bounds.doIntersect(tr.transformedBounds());
137         }
138     }
139     return bounds;
140 }
141 
pathFromTransformedRectangle(const Rect & bounds,const Matrix4 & transform)142 static SkPath pathFromTransformedRectangle(const Rect& bounds, const Matrix4& transform) {
143     SkPath rectPath;
144     SkPath rectPathTransformed;
145     rectPath.addRect(bounds.left, bounds.top, bounds.right, bounds.bottom);
146     SkMatrix skTransform;
147     transform.copyTo(skTransform);
148     rectPath.transform(skTransform, &rectPathTransformed);
149     return rectPathTransformed;
150 }
151 
convertToRegion(const SkRegion & clip) const152 SkRegion RectangleList::convertToRegion(const SkRegion& clip) const {
153     SkRegion rectangleListAsRegion;
154     for (int index = 0; index < mTransformedRectanglesCount; index++) {
155         const TransformedRectangle& tr(mTransformedRectangles[index]);
156         SkPath rectPathTransformed =
157                 pathFromTransformedRectangle(tr.getBounds(), tr.getTransform());
158         if (index == 0) {
159             rectangleListAsRegion.setPath(rectPathTransformed, clip);
160         } else {
161             SkRegion rectRegion;
162             rectRegion.setPath(rectPathTransformed, clip);
163             rectangleListAsRegion.op(rectRegion, SkRegion::kIntersect_Op);
164         }
165     }
166     return rectangleListAsRegion;
167 }
168 
transform(const Matrix4 & transform)169 void RectangleList::transform(const Matrix4& transform) {
170     for (int index = 0; index < mTransformedRectanglesCount; index++) {
171         mTransformedRectangles[index].transform(transform);
172     }
173 }
174 
175 /*
176  * ClipArea
177  */
178 
ClipArea()179 ClipArea::ClipArea() : mMode(ClipMode::Rectangle) {}
180 
181 /*
182  * Interface
183  */
184 
setViewportDimensions(int width,int height)185 void ClipArea::setViewportDimensions(int width, int height) {
186     mPostViewportClipObserved = false;
187     mViewportBounds.set(0, 0, width, height);
188     mClipRect = mViewportBounds;
189 }
190 
setEmpty()191 void ClipArea::setEmpty() {
192     onClipUpdated();
193     mMode = ClipMode::Rectangle;
194     mClipRect.setEmpty();
195     mClipRegion.setEmpty();
196     mRectangleList.setEmpty();
197 }
198 
setClip(float left,float top,float right,float bottom)199 void ClipArea::setClip(float left, float top, float right, float bottom) {
200     onClipUpdated();
201     mMode = ClipMode::Rectangle;
202     mClipRect.set(left, top, right, bottom);
203     mClipRegion.setEmpty();
204 }
205 
clipRectWithTransform(const Rect & r,const mat4 * transform,SkRegion::Op op)206 void ClipArea::clipRectWithTransform(const Rect& r, const mat4* transform, SkRegion::Op op) {
207     if (op == SkRegion::kReplace_Op) mReplaceOpObserved = true;
208     if (!mPostViewportClipObserved && op == SkRegion::kIntersect_Op) op = SkRegion::kReplace_Op;
209     onClipUpdated();
210     switch (mMode) {
211         case ClipMode::Rectangle:
212             rectangleModeClipRectWithTransform(r, transform, op);
213             break;
214         case ClipMode::RectangleList:
215             rectangleListModeClipRectWithTransform(r, transform, op);
216             break;
217         case ClipMode::Region:
218             regionModeClipRectWithTransform(r, transform, op);
219             break;
220     }
221 }
222 
clipRegion(const SkRegion & region,SkRegion::Op op)223 void ClipArea::clipRegion(const SkRegion& region, SkRegion::Op op) {
224     if (op == SkRegion::kReplace_Op) mReplaceOpObserved = true;
225     if (!mPostViewportClipObserved && op == SkRegion::kIntersect_Op) op = SkRegion::kReplace_Op;
226     onClipUpdated();
227     enterRegionMode();
228     mClipRegion.op(region, op);
229     onClipRegionUpdated();
230 }
231 
clipPathWithTransform(const SkPath & path,const mat4 * transform,SkRegion::Op op)232 void ClipArea::clipPathWithTransform(const SkPath& path, const mat4* transform, SkRegion::Op op) {
233     if (op == SkRegion::kReplace_Op) mReplaceOpObserved = true;
234     if (!mPostViewportClipObserved && op == SkRegion::kIntersect_Op) op = SkRegion::kReplace_Op;
235     onClipUpdated();
236     SkMatrix skTransform;
237     transform->copyTo(skTransform);
238     SkPath transformed;
239     path.transform(skTransform, &transformed);
240     SkRegion region;
241     regionFromPath(transformed, region);
242     enterRegionMode();
243     mClipRegion.op(region, op);
244     onClipRegionUpdated();
245 }
246 
247 /*
248  * Rectangle mode
249  */
250 
enterRectangleMode()251 void ClipArea::enterRectangleMode() {
252     // Entering rectangle mode discards any
253     // existing clipping information from the other modes.
254     // The only way this occurs is by a clip setting operation.
255     mMode = ClipMode::Rectangle;
256 }
257 
rectangleModeClipRectWithTransform(const Rect & r,const mat4 * transform,SkRegion::Op op)258 void ClipArea::rectangleModeClipRectWithTransform(const Rect& r, const mat4* transform,
259                                                   SkRegion::Op op) {
260     if (op == SkRegion::kReplace_Op && transform->rectToRect()) {
261         mClipRect = r;
262         transform->mapRect(mClipRect);
263         return;
264     } else if (op != SkRegion::kIntersect_Op) {
265         enterRegionMode();
266         regionModeClipRectWithTransform(r, transform, op);
267         return;
268     }
269 
270     if (transform->rectToRect()) {
271         Rect transformed(r);
272         transform->mapRect(transformed);
273         mClipRect.doIntersect(transformed);
274         return;
275     }
276 
277     enterRectangleListMode();
278     rectangleListModeClipRectWithTransform(r, transform, op);
279 }
280 
281 /*
282  * RectangleList mode implementation
283  */
284 
enterRectangleListMode()285 void ClipArea::enterRectangleListMode() {
286     // Is is only legal to enter rectangle list mode from
287     // rectangle mode, since rectangle list mode cannot represent
288     // all clip areas that can be represented by a region.
289     ALOG_ASSERT(mMode == ClipMode::Rectangle);
290     mMode = ClipMode::RectangleList;
291     mRectangleList.set(mClipRect, Matrix4::identity());
292 }
293 
rectangleListModeClipRectWithTransform(const Rect & r,const mat4 * transform,SkRegion::Op op)294 void ClipArea::rectangleListModeClipRectWithTransform(const Rect& r, const mat4* transform,
295                                                       SkRegion::Op op) {
296     if (op != SkRegion::kIntersect_Op || !mRectangleList.intersectWith(r, *transform)) {
297         enterRegionMode();
298         regionModeClipRectWithTransform(r, transform, op);
299     }
300 }
301 
302 /*
303  * Region mode implementation
304  */
305 
enterRegionMode()306 void ClipArea::enterRegionMode() {
307     ClipMode oldMode = mMode;
308     mMode = ClipMode::Region;
309     if (oldMode != ClipMode::Region) {
310         if (oldMode == ClipMode::Rectangle) {
311             mClipRegion.setRect(mClipRect.toSkIRect());
312         } else {
313             mClipRegion = mRectangleList.convertToRegion(createViewportRegion());
314             onClipRegionUpdated();
315         }
316     }
317 }
318 
regionModeClipRectWithTransform(const Rect & r,const mat4 * transform,SkRegion::Op op)319 void ClipArea::regionModeClipRectWithTransform(const Rect& r, const mat4* transform,
320                                                SkRegion::Op op) {
321     SkPath transformedRect = pathFromTransformedRectangle(r, *transform);
322     SkRegion transformedRectRegion;
323     regionFromPath(transformedRect, transformedRectRegion);
324     mClipRegion.op(transformedRectRegion, op);
325     onClipRegionUpdated();
326 }
327 
onClipRegionUpdated()328 void ClipArea::onClipRegionUpdated() {
329     if (!mClipRegion.isEmpty()) {
330         mClipRect.set(mClipRegion.getBounds());
331 
332         if (mClipRegion.isRect()) {
333             mClipRegion.setEmpty();
334             enterRectangleMode();
335         }
336     } else {
337         mClipRect.setEmpty();
338     }
339 }
340 
341 /**
342  * Clip serialization
343  */
344 
serializeClip(LinearAllocator & allocator)345 const ClipBase* ClipArea::serializeClip(LinearAllocator& allocator) {
346     if (!mPostViewportClipObserved) {
347         // Only initial clip-to-viewport observed, so no serialization of clip necessary
348         return nullptr;
349     }
350 
351     static_assert(std::is_trivially_destructible<Rect>::value,
352                   "expect Rect to be trivially destructible");
353     static_assert(std::is_trivially_destructible<RectangleList>::value,
354                   "expect RectangleList to be trivially destructible");
355 
356     if (mLastSerialization == nullptr) {
357         ClipBase* serialization = nullptr;
358         switch (mMode) {
359             case ClipMode::Rectangle:
360                 serialization = allocator.create<ClipRect>(mClipRect);
361                 break;
362             case ClipMode::RectangleList:
363                 serialization = allocator.create<ClipRectList>(mRectangleList);
364                 serialization->rect = mRectangleList.calculateBounds();
365                 break;
366             case ClipMode::Region:
367                 serialization = allocator.create<ClipRegion>(mClipRegion);
368                 serialization->rect.set(mClipRegion.getBounds());
369                 break;
370         }
371         serialization->intersectWithRoot = mReplaceOpObserved;
372         // TODO: this is only done for draw time, should eventually avoid for record time
373         serialization->rect.snapToPixelBoundaries();
374         mLastSerialization = serialization;
375     }
376     return mLastSerialization;
377 }
378 
getRectList(const ClipBase * scb)379 inline static const RectangleList& getRectList(const ClipBase* scb) {
380     return reinterpret_cast<const ClipRectList*>(scb)->rectList;
381 }
382 
getRegion(const ClipBase * scb)383 inline static const SkRegion& getRegion(const ClipBase* scb) {
384     return reinterpret_cast<const ClipRegion*>(scb)->region;
385 }
386 
387 // Conservative check for too many rectangles to fit in rectangle list.
388 // For simplicity, doesn't account for rect merging
cannotFitInRectangleList(const ClipArea & clipArea,const ClipBase * scb)389 static bool cannotFitInRectangleList(const ClipArea& clipArea, const ClipBase* scb) {
390     int currentRectCount = clipArea.isRectangleList()
391                                    ? clipArea.getRectangleList().getTransformedRectanglesCount()
392                                    : 1;
393     int recordedRectCount = (scb->mode == ClipMode::RectangleList)
394                                     ? getRectList(scb).getTransformedRectanglesCount()
395                                     : 1;
396     return currentRectCount + recordedRectCount > RectangleList::kMaxTransformedRectangles;
397 }
398 
399 static const ClipRect sEmptyClipRect(Rect(0, 0));
400 
serializeIntersectedClip(LinearAllocator & allocator,const ClipBase * recordedClip,const Matrix4 & recordedClipTransform)401 const ClipBase* ClipArea::serializeIntersectedClip(LinearAllocator& allocator,
402                                                    const ClipBase* recordedClip,
403                                                    const Matrix4& recordedClipTransform) {
404     // if no recordedClip passed, just serialize current state
405     if (!recordedClip) return serializeClip(allocator);
406 
407     // if either is empty, clip is empty
408     if (CC_UNLIKELY(recordedClip->rect.isEmpty()) || mClipRect.isEmpty()) return &sEmptyClipRect;
409 
410     if (!mLastResolutionResult || recordedClip != mLastResolutionClip ||
411         recordedClipTransform != mLastResolutionTransform) {
412         mLastResolutionClip = recordedClip;
413         mLastResolutionTransform = recordedClipTransform;
414 
415         if (CC_LIKELY(mMode == ClipMode::Rectangle && recordedClip->mode == ClipMode::Rectangle &&
416                       recordedClipTransform.rectToRect())) {
417             // common case - result is a single rectangle
418             auto rectClip = allocator.create<ClipRect>(recordedClip->rect);
419             recordedClipTransform.mapRect(rectClip->rect);
420             rectClip->rect.doIntersect(mClipRect);
421             rectClip->rect.snapToPixelBoundaries();
422             mLastResolutionResult = rectClip;
423         } else if (CC_UNLIKELY(mMode == ClipMode::Region ||
424                                recordedClip->mode == ClipMode::Region ||
425                                cannotFitInRectangleList(*this, recordedClip))) {
426             // region case
427             SkRegion other;
428             switch (recordedClip->mode) {
429                 case ClipMode::Rectangle:
430                     if (CC_LIKELY(recordedClipTransform.rectToRect())) {
431                         // simple transform, skip creating SkPath
432                         Rect resultClip(recordedClip->rect);
433                         recordedClipTransform.mapRect(resultClip);
434                         other.setRect(resultClip.toSkIRect());
435                     } else {
436                         SkPath transformedRect = pathFromTransformedRectangle(
437                                 recordedClip->rect, recordedClipTransform);
438                         other.setPath(transformedRect, createViewportRegion());
439                     }
440                     break;
441                 case ClipMode::RectangleList: {
442                     RectangleList transformedList(getRectList(recordedClip));
443                     transformedList.transform(recordedClipTransform);
444                     other = transformedList.convertToRegion(createViewportRegion());
445                     break;
446                 }
447                 case ClipMode::Region:
448                     other = getRegion(recordedClip);
449                     applyTransformToRegion(recordedClipTransform, &other);
450             }
451 
452             ClipRegion* regionClip = allocator.create<ClipRegion>();
453             switch (mMode) {
454                 case ClipMode::Rectangle:
455                     regionClip->region.op(mClipRect.toSkIRect(), other, SkRegion::kIntersect_Op);
456                     break;
457                 case ClipMode::RectangleList:
458                     regionClip->region.op(mRectangleList.convertToRegion(createViewportRegion()),
459                                           other, SkRegion::kIntersect_Op);
460                     break;
461                 case ClipMode::Region:
462                     regionClip->region.op(mClipRegion, other, SkRegion::kIntersect_Op);
463                     break;
464             }
465             // Don't need to snap, since region's in int bounds
466             regionClip->rect.set(regionClip->region.getBounds());
467             mLastResolutionResult = regionClip;
468         } else {
469             auto rectListClip = allocator.create<ClipRectList>(mRectangleList);
470             auto&& rectList = rectListClip->rectList;
471             if (mMode == ClipMode::Rectangle) {
472                 rectList.set(mClipRect, Matrix4::identity());
473             }
474 
475             if (recordedClip->mode == ClipMode::Rectangle) {
476                 rectList.intersectWith(recordedClip->rect, recordedClipTransform);
477             } else {
478                 const RectangleList& other = getRectList(recordedClip);
479                 for (int i = 0; i < other.getTransformedRectanglesCount(); i++) {
480                     auto&& tr = other.getTransformedRectangle(i);
481                     Matrix4 totalTransform(recordedClipTransform);
482                     totalTransform.multiply(tr.getTransform());
483                     rectList.intersectWith(tr.getBounds(), totalTransform);
484                 }
485             }
486             rectListClip->rect = rectList.calculateBounds();
487             rectListClip->rect.snapToPixelBoundaries();
488             mLastResolutionResult = rectListClip;
489         }
490     }
491     return mLastResolutionResult;
492 }
493 
applyClip(const ClipBase * clip,const Matrix4 & transform)494 void ClipArea::applyClip(const ClipBase* clip, const Matrix4& transform) {
495     if (!clip) return;  // nothing to do
496 
497     if (CC_LIKELY(clip->mode == ClipMode::Rectangle)) {
498         clipRectWithTransform(clip->rect, &transform, SkRegion::kIntersect_Op);
499     } else if (CC_LIKELY(clip->mode == ClipMode::RectangleList)) {
500         auto&& rectList = getRectList(clip);
501         for (int i = 0; i < rectList.getTransformedRectanglesCount(); i++) {
502             auto&& tr = rectList.getTransformedRectangle(i);
503             Matrix4 totalTransform(transform);
504             totalTransform.multiply(tr.getTransform());
505             clipRectWithTransform(tr.getBounds(), &totalTransform, SkRegion::kIntersect_Op);
506         }
507     } else {
508         SkRegion region(getRegion(clip));
509         applyTransformToRegion(transform, &region);
510         clipRegion(region, SkRegion::kIntersect_Op);
511     }
512 }
513 
applyTransformToRegion(const Matrix4 & transform,SkRegion * region)514 void ClipArea::applyTransformToRegion(const Matrix4& transform, SkRegion* region) {
515     if (transform.rectToRect() && !transform.isPureTranslate()) {
516         // handle matrices with scale manually by mapping each rect
517         SkRegion other;
518         SkRegion::Iterator it(*region);
519         while (!it.done()) {
520             Rect rect(it.rect());
521             transform.mapRect(rect);
522             rect.snapGeometryToPixelBoundaries(true);
523             other.op(rect.left, rect.top, rect.right, rect.bottom, SkRegion::kUnion_Op);
524             it.next();
525         }
526         region->swap(other);
527     } else {
528         // TODO: handle non-translate transforms properly!
529         region->translate(transform.getTranslateX(), transform.getTranslateY());
530     }
531 }
532 
533 } /* namespace uirenderer */
534 } /* namespace android */
535