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