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