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