1/*
2 * Copyright (C) 2014 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
17#include <utils/JenkinsHash.h>
18#include <utils/Trace.h>
19
20#include "Caches.h"
21#include "PathTessellator.h"
22#include "ShadowTessellator.h"
23#include "TessellationCache.h"
24
25#include "thread/Signal.h"
26#include "thread/Task.h"
27#include "thread/TaskProcessor.h"
28
29namespace android {
30namespace uirenderer {
31
32///////////////////////////////////////////////////////////////////////////////
33// Cache entries
34///////////////////////////////////////////////////////////////////////////////
35
36TessellationCache::Description::Description()
37        : type(Type::None)
38        , scaleX(1.0f)
39        , scaleY(1.0f)
40        , aa(false)
41        , cap(SkPaint::kDefault_Cap)
42        , style(SkPaint::kFill_Style)
43        , strokeWidth(1.0f) {
44    // Shape bits should be set to zeroes, because they are used for hash calculation.
45    memset(&shape, 0, sizeof(Shape));
46}
47
48TessellationCache::Description::Description(Type type, const Matrix4& transform,
49                                            const SkPaint& paint)
50        : type(type)
51        , aa(paint.isAntiAlias())
52        , cap(paint.getStrokeCap())
53        , style(paint.getStyle())
54        , strokeWidth(paint.getStrokeWidth()) {
55    PathTessellator::extractTessellationScales(transform, &scaleX, &scaleY);
56    // Shape bits should be set to zeroes, because they are used for hash calculation.
57    memset(&shape, 0, sizeof(Shape));
58}
59
60bool TessellationCache::Description::operator==(const TessellationCache::Description& rhs) const {
61    if (type != rhs.type) return false;
62    if (scaleX != rhs.scaleX) return false;
63    if (scaleY != rhs.scaleY) return false;
64    if (aa != rhs.aa) return false;
65    if (cap != rhs.cap) return false;
66    if (style != rhs.style) return false;
67    if (strokeWidth != rhs.strokeWidth) return false;
68    if (type == Type::None) return true;
69    const Shape::RoundRect& lRect = shape.roundRect;
70    const Shape::RoundRect& rRect = rhs.shape.roundRect;
71
72    if (lRect.width != rRect.width) return false;
73    if (lRect.height != rRect.height) return false;
74    if (lRect.rx != rRect.rx) return false;
75    return lRect.ry == rRect.ry;
76}
77
78hash_t TessellationCache::Description::hash() const {
79    uint32_t hash = JenkinsHashMix(0, static_cast<int>(type));
80    hash = JenkinsHashMix(hash, aa);
81    hash = JenkinsHashMix(hash, cap);
82    hash = JenkinsHashMix(hash, style);
83    hash = JenkinsHashMix(hash, android::hash_type(strokeWidth));
84    hash = JenkinsHashMix(hash, android::hash_type(scaleX));
85    hash = JenkinsHashMix(hash, android::hash_type(scaleY));
86    hash = JenkinsHashMixBytes(hash, (uint8_t*)&shape, sizeof(Shape));
87    return JenkinsHashWhiten(hash);
88}
89
90void TessellationCache::Description::setupMatrixAndPaint(Matrix4* matrix, SkPaint* paint) const {
91    matrix->loadScale(scaleX, scaleY, 1.0f);
92    paint->setAntiAlias(aa);
93    paint->setStrokeCap(cap);
94    paint->setStyle(style);
95    paint->setStrokeWidth(strokeWidth);
96}
97
98TessellationCache::ShadowDescription::ShadowDescription() : nodeKey(nullptr) {
99    memset(&matrixData, 0, sizeof(matrixData));
100}
101
102TessellationCache::ShadowDescription::ShadowDescription(const SkPath* nodeKey,
103                                                        const Matrix4* drawTransform)
104        : nodeKey(nodeKey) {
105    memcpy(&matrixData, drawTransform->data, sizeof(matrixData));
106}
107
108bool TessellationCache::ShadowDescription::operator==(
109        const TessellationCache::ShadowDescription& rhs) const {
110    return nodeKey == rhs.nodeKey && memcmp(&matrixData, &rhs.matrixData, sizeof(matrixData)) == 0;
111}
112
113hash_t TessellationCache::ShadowDescription::hash() const {
114    uint32_t hash = JenkinsHashMixBytes(0, (uint8_t*)&nodeKey, sizeof(const void*));
115    hash = JenkinsHashMixBytes(hash, (uint8_t*)&matrixData, sizeof(matrixData));
116    return JenkinsHashWhiten(hash);
117}
118
119///////////////////////////////////////////////////////////////////////////////
120// General purpose tessellation task processing
121///////////////////////////////////////////////////////////////////////////////
122
123class TessellationCache::TessellationTask : public Task<VertexBuffer*> {
124public:
125    TessellationTask(Tessellator tessellator, const Description& description)
126            : tessellator(tessellator), description(description) {}
127
128    ~TessellationTask() {}
129
130    Tessellator tessellator;
131    Description description;
132};
133
134class TessellationCache::TessellationProcessor : public TaskProcessor<VertexBuffer*> {
135public:
136    explicit TessellationProcessor(Caches& caches) : TaskProcessor<VertexBuffer*>(&caches.tasks) {}
137    ~TessellationProcessor() {}
138
139    virtual void onProcess(const sp<Task<VertexBuffer*> >& task) override {
140        TessellationTask* t = static_cast<TessellationTask*>(task.get());
141        ATRACE_NAME("shape tessellation");
142        VertexBuffer* buffer = t->tessellator(t->description);
143        t->setResult(buffer);
144    }
145};
146
147class TessellationCache::Buffer {
148public:
149    explicit Buffer(const sp<Task<VertexBuffer*> >& task) : mTask(task), mBuffer(nullptr) {}
150
151    ~Buffer() {
152        mTask.clear();
153        delete mBuffer;
154    }
155
156    unsigned int getSize() {
157        blockOnPrecache();
158        return mBuffer->getSize();
159    }
160
161    const VertexBuffer* getVertexBuffer() {
162        blockOnPrecache();
163        return mBuffer;
164    }
165
166private:
167    void blockOnPrecache() {
168        if (mTask != nullptr) {
169            mBuffer = mTask->getResult();
170            LOG_ALWAYS_FATAL_IF(mBuffer == nullptr, "Failed to precache");
171            mTask.clear();
172        }
173    }
174    sp<Task<VertexBuffer*> > mTask;
175    VertexBuffer* mBuffer;
176};
177
178///////////////////////////////////////////////////////////////////////////////
179// Shadow tessellation task processing
180///////////////////////////////////////////////////////////////////////////////
181
182static void mapPointFakeZ(Vector3& point, const mat4* transformXY, const mat4* transformZ) {
183    // map z coordinate with true 3d matrix
184    point.z = transformZ->mapZ(point);
185
186    // map x,y coordinates with draw/Skia matrix
187    transformXY->mapPoint(point.x, point.y);
188}
189
190static void reverseVertexArray(Vertex* polygon, int len) {
191    int n = len / 2;
192    for (int i = 0; i < n; i++) {
193        Vertex tmp = polygon[i];
194        int k = len - 1 - i;
195        polygon[i] = polygon[k];
196        polygon[k] = tmp;
197    }
198}
199
200void tessellateShadows(const Matrix4* drawTransform, const Rect* localClip, bool isCasterOpaque,
201                       const SkPath* casterPerimeter, const Matrix4* casterTransformXY,
202                       const Matrix4* casterTransformZ, const Vector3& lightCenter,
203                       float lightRadius, VertexBuffer& ambientBuffer, VertexBuffer& spotBuffer) {
204    // tessellate caster outline into a 2d polygon
205    std::vector<Vertex> casterVertices2d;
206    const float casterRefinementThreshold = 2.0f;
207    PathTessellator::approximatePathOutlineVertices(*casterPerimeter, casterRefinementThreshold,
208                                                    casterVertices2d);
209
210    // Shadow requires CCW for now. TODO: remove potential double-reverse
211    reverseVertexArray(&casterVertices2d.front(), casterVertices2d.size());
212
213    if (casterVertices2d.size() == 0) return;
214
215    // map 2d caster poly into 3d
216    const int casterVertexCount = casterVertices2d.size();
217    Vector3 casterPolygon[casterVertexCount];
218    float minZ = FLT_MAX;
219    float maxZ = -FLT_MAX;
220    for (int i = 0; i < casterVertexCount; i++) {
221        const Vertex& point2d = casterVertices2d[i];
222        casterPolygon[i] = (Vector3){point2d.x, point2d.y, 0};
223        mapPointFakeZ(casterPolygon[i], casterTransformXY, casterTransformZ);
224        minZ = std::min(minZ, casterPolygon[i].z);
225        maxZ = std::max(maxZ, casterPolygon[i].z);
226    }
227
228    // map the centroid of the caster into 3d
229    Vector2 centroid = ShadowTessellator::centroid2d(
230            reinterpret_cast<const Vector2*>(&casterVertices2d.front()), casterVertexCount);
231    Vector3 centroid3d = {centroid.x, centroid.y, 0};
232    mapPointFakeZ(centroid3d, casterTransformXY, casterTransformZ);
233
234    // if the caster intersects the z=0 plane, lift it in Z so it doesn't
235    if (minZ < SHADOW_MIN_CASTER_Z) {
236        float casterLift = SHADOW_MIN_CASTER_Z - minZ;
237        for (int i = 0; i < casterVertexCount; i++) {
238            casterPolygon[i].z += casterLift;
239        }
240        centroid3d.z += casterLift;
241    }
242
243    // Check whether we want to draw the shadow at all by checking the caster's bounds against clip.
244    // We only have ortho projection, so we can just ignore the Z in caster for
245    // simple rejection calculation.
246    Rect casterBounds(casterPerimeter->getBounds());
247    casterTransformXY->mapRect(casterBounds);
248
249    // actual tessellation of both shadows
250    ShadowTessellator::tessellateAmbientShadow(isCasterOpaque, casterPolygon, casterVertexCount,
251                                               centroid3d, casterBounds, *localClip, maxZ,
252                                               ambientBuffer);
253
254    ShadowTessellator::tessellateSpotShadow(isCasterOpaque, casterPolygon, casterVertexCount,
255                                            centroid3d, *drawTransform, lightCenter, lightRadius,
256                                            casterBounds, *localClip, spotBuffer);
257}
258
259class ShadowProcessor : public TaskProcessor<TessellationCache::vertexBuffer_pair_t> {
260public:
261    explicit ShadowProcessor(Caches& caches)
262            : TaskProcessor<TessellationCache::vertexBuffer_pair_t>(&caches.tasks) {}
263    ~ShadowProcessor() {}
264
265    virtual void onProcess(const sp<Task<TessellationCache::vertexBuffer_pair_t> >& task) override {
266        TessellationCache::ShadowTask* t = static_cast<TessellationCache::ShadowTask*>(task.get());
267        ATRACE_NAME("shadow tessellation");
268
269        tessellateShadows(&t->drawTransform, &t->localClip, t->opaque, &t->casterPerimeter,
270                          &t->transformXY, &t->transformZ, t->lightCenter, t->lightRadius,
271                          t->ambientBuffer, t->spotBuffer);
272
273        t->setResult(TessellationCache::vertexBuffer_pair_t(&t->ambientBuffer, &t->spotBuffer));
274    }
275};
276
277///////////////////////////////////////////////////////////////////////////////
278// Cache constructor/destructor
279///////////////////////////////////////////////////////////////////////////////
280
281TessellationCache::TessellationCache()
282        : mMaxSize(MB(1))
283        , mCache(LruCache<Description, Buffer*>::kUnlimitedCapacity)
284        , mShadowCache(
285                  LruCache<ShadowDescription, Task<vertexBuffer_pair_t*>*>::kUnlimitedCapacity) {
286    mCache.setOnEntryRemovedListener(&mBufferRemovedListener);
287    mShadowCache.setOnEntryRemovedListener(&mBufferPairRemovedListener);
288    mDebugEnabled = Properties::debugLevel & kDebugCaches;
289}
290
291TessellationCache::~TessellationCache() {
292    mCache.clear();
293}
294
295///////////////////////////////////////////////////////////////////////////////
296// Size management
297///////////////////////////////////////////////////////////////////////////////
298
299uint32_t TessellationCache::getSize() {
300    LruCache<Description, Buffer*>::Iterator iter(mCache);
301    uint32_t size = 0;
302    while (iter.next()) {
303        size += iter.value()->getSize();
304    }
305    return size;
306}
307
308uint32_t TessellationCache::getMaxSize() {
309    return mMaxSize;
310}
311
312///////////////////////////////////////////////////////////////////////////////
313// Caching
314///////////////////////////////////////////////////////////////////////////////
315
316void TessellationCache::trim() {
317    uint32_t size = getSize();
318    while (size > mMaxSize) {
319        size -= mCache.peekOldestValue()->getSize();
320        mCache.removeOldest();
321    }
322    mShadowCache.clear();
323}
324
325void TessellationCache::clear() {
326    mCache.clear();
327    mShadowCache.clear();
328}
329
330///////////////////////////////////////////////////////////////////////////////
331// Callbacks
332///////////////////////////////////////////////////////////////////////////////
333
334void TessellationCache::BufferRemovedListener::operator()(Description& description,
335                                                          Buffer*& buffer) {
336    delete buffer;
337}
338
339///////////////////////////////////////////////////////////////////////////////
340// Shadows
341///////////////////////////////////////////////////////////////////////////////
342
343void TessellationCache::precacheShadows(const Matrix4* drawTransform, const Rect& localClip,
344                                        bool opaque, const SkPath* casterPerimeter,
345                                        const Matrix4* transformXY, const Matrix4* transformZ,
346                                        const Vector3& lightCenter, float lightRadius) {
347    ShadowDescription key(casterPerimeter, drawTransform);
348
349    if (mShadowCache.get(key)) return;
350    sp<ShadowTask> task = new ShadowTask(drawTransform, localClip, opaque, casterPerimeter,
351                                         transformXY, transformZ, lightCenter, lightRadius);
352    if (mShadowProcessor == nullptr) {
353        mShadowProcessor = new ShadowProcessor(Caches::getInstance());
354    }
355    mShadowProcessor->add(task);
356    task->incStrong(nullptr);  // not using sp<>s, so manually ref while in the cache
357    mShadowCache.put(key, task.get());
358}
359
360sp<TessellationCache::ShadowTask> TessellationCache::getShadowTask(
361        const Matrix4* drawTransform, const Rect& localClip, bool opaque,
362        const SkPath* casterPerimeter, const Matrix4* transformXY, const Matrix4* transformZ,
363        const Vector3& lightCenter, float lightRadius) {
364    ShadowDescription key(casterPerimeter, drawTransform);
365    ShadowTask* task = static_cast<ShadowTask*>(mShadowCache.get(key));
366    if (!task) {
367        precacheShadows(drawTransform, localClip, opaque, casterPerimeter, transformXY, transformZ,
368                        lightCenter, lightRadius);
369        task = static_cast<ShadowTask*>(mShadowCache.get(key));
370    }
371    LOG_ALWAYS_FATAL_IF(task == nullptr, "shadow not precached");
372    return task;
373}
374
375///////////////////////////////////////////////////////////////////////////////
376// Tessellation precaching
377///////////////////////////////////////////////////////////////////////////////
378
379TessellationCache::Buffer* TessellationCache::getOrCreateBuffer(const Description& entry,
380                                                                Tessellator tessellator) {
381    Buffer* buffer = mCache.get(entry);
382    if (!buffer) {
383        // not cached, enqueue a task to fill the buffer
384        sp<TessellationTask> task = new TessellationTask(tessellator, entry);
385        buffer = new Buffer(task);
386
387        if (mProcessor == nullptr) {
388            mProcessor = new TessellationProcessor(Caches::getInstance());
389        }
390        mProcessor->add(task);
391        bool inserted = mCache.put(entry, buffer);
392        // Note to the static analyzer that this insert should always succeed.
393        LOG_ALWAYS_FATAL_IF(!inserted, "buffers shouldn't spontaneously appear in the cache");
394    }
395    return buffer;
396}
397
398static VertexBuffer* tessellatePath(const TessellationCache::Description& description,
399                                    const SkPath& path) {
400    Matrix4 matrix;
401    SkPaint paint;
402    description.setupMatrixAndPaint(&matrix, &paint);
403    VertexBuffer* buffer = new VertexBuffer();
404    PathTessellator::tessellatePath(path, &paint, matrix, *buffer);
405    return buffer;
406}
407
408///////////////////////////////////////////////////////////////////////////////
409// RoundRect
410///////////////////////////////////////////////////////////////////////////////
411
412static VertexBuffer* tessellateRoundRect(const TessellationCache::Description& description) {
413    SkRect rect =
414            SkRect::MakeWH(description.shape.roundRect.width, description.shape.roundRect.height);
415    float rx = description.shape.roundRect.rx;
416    float ry = description.shape.roundRect.ry;
417    if (description.style == SkPaint::kStrokeAndFill_Style) {
418        float outset = description.strokeWidth / 2;
419        rect.outset(outset, outset);
420        rx += outset;
421        ry += outset;
422    }
423    SkPath path;
424    path.addRoundRect(rect, rx, ry);
425    return tessellatePath(description, path);
426}
427
428TessellationCache::Buffer* TessellationCache::getRoundRectBuffer(const Matrix4& transform,
429                                                                 const SkPaint& paint, float width,
430                                                                 float height, float rx, float ry) {
431    Description entry(Description::Type::RoundRect, transform, paint);
432    entry.shape.roundRect.width = width;
433    entry.shape.roundRect.height = height;
434    entry.shape.roundRect.rx = rx;
435    entry.shape.roundRect.ry = ry;
436    return getOrCreateBuffer(entry, &tessellateRoundRect);
437}
438const VertexBuffer* TessellationCache::getRoundRect(const Matrix4& transform, const SkPaint& paint,
439                                                    float width, float height, float rx, float ry) {
440    return getRoundRectBuffer(transform, paint, width, height, rx, ry)->getVertexBuffer();
441}
442
443};  // namespace uirenderer
444};  // namespace android
445