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