1/*
2 * Copyright (C) 2012 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#define LOG_TAG "PathTessellator"
18#define LOG_NDEBUG 1
19#define ATRACE_TAG ATRACE_TAG_GRAPHICS
20
21#define VERTEX_DEBUG 0
22
23#if VERTEX_DEBUG
24#define DEBUG_DUMP_ALPHA_BUFFER() \
25    for (unsigned int i = 0; i < vertexBuffer.getSize(); i++) { \
26        ALOGD("point %d at %f %f, alpha %f", \
27        i, buffer[i].position[0], buffer[i].position[1], buffer[i].alpha); \
28    }
29#define DEBUG_DUMP_BUFFER() \
30    for (unsigned int i = 0; i < vertexBuffer.getSize(); i++) { \
31        ALOGD("point %d at %f %f", i, buffer[i].position[0], buffer[i].position[1]); \
32    }
33#else
34#define DEBUG_DUMP_ALPHA_BUFFER()
35#define DEBUG_DUMP_BUFFER()
36#endif
37
38#include <SkPath.h>
39#include <SkPaint.h>
40
41#include <stdlib.h>
42#include <stdint.h>
43#include <sys/types.h>
44
45#include <utils/Log.h>
46#include <utils/Trace.h>
47
48#include "PathTessellator.h"
49#include "Matrix.h"
50#include "Vector.h"
51#include "Vertex.h"
52
53namespace android {
54namespace uirenderer {
55
56#define THRESHOLD 0.5f
57#define ROUND_CAP_THRESH 0.25f
58#define PI 3.1415926535897932f
59
60void PathTessellator::expandBoundsForStroke(SkRect& bounds, const SkPaint* paint,
61        bool forceExpand) {
62    if (forceExpand || paint->getStyle() != SkPaint::kFill_Style) {
63        float outset = paint->getStrokeWidth() * 0.5f;
64        if (outset == 0) outset = 0.5f; // account for hairline
65        bounds.outset(outset, outset);
66    }
67}
68
69inline static void copyVertex(Vertex* destPtr, const Vertex* srcPtr) {
70    Vertex::set(destPtr, srcPtr->position[0], srcPtr->position[1]);
71}
72
73inline static void copyAlphaVertex(AlphaVertex* destPtr, const AlphaVertex* srcPtr) {
74    AlphaVertex::set(destPtr, srcPtr->position[0], srcPtr->position[1], srcPtr->alpha);
75}
76
77/**
78 * Produces a pseudo-normal for a vertex, given the normals of the two incoming lines. If the offset
79 * from each vertex in a perimeter is calculated, the resultant lines connecting the offset vertices
80 * will be offset by 1.0
81 *
82 * Note that we can't add and normalize the two vectors, that would result in a rectangle having an
83 * offset of (sqrt(2)/2, sqrt(2)/2) at each corner, instead of (1, 1)
84 *
85 * NOTE: assumes angles between normals 90 degrees or less
86 */
87inline static vec2 totalOffsetFromNormals(const vec2& normalA, const vec2& normalB) {
88    return (normalA + normalB) / (1 + fabs(normalA.dot(normalB)));
89}
90
91/**
92 * Structure used for storing useful information about the SkPaint and scale used for tessellating
93 */
94struct PaintInfo {
95public:
96    PaintInfo(const SkPaint* paint, const mat4 *transform) :
97            style(paint->getStyle()), cap(paint->getStrokeCap()), isAA(paint->isAntiAlias()),
98            inverseScaleX(1.0f), inverseScaleY(1.0f),
99            halfStrokeWidth(paint->getStrokeWidth() * 0.5f), maxAlpha(1.0f) {
100        // compute inverse scales
101        if (CC_UNLIKELY(!transform->isPureTranslate())) {
102            float m00 = transform->data[Matrix4::kScaleX];
103            float m01 = transform->data[Matrix4::kSkewY];
104            float m10 = transform->data[Matrix4::kSkewX];
105            float m11 = transform->data[Matrix4::kScaleY];
106            float scaleX = sqrt(m00 * m00 + m01 * m01);
107            float scaleY = sqrt(m10 * m10 + m11 * m11);
108            inverseScaleX = (scaleX != 0) ? (1.0f / scaleX) : 1.0f;
109            inverseScaleY = (scaleY != 0) ? (1.0f / scaleY) : 1.0f;
110        }
111
112        if (isAA && halfStrokeWidth != 0 && inverseScaleX == inverseScaleY &&
113                2 * halfStrokeWidth < inverseScaleX) {
114            maxAlpha *= (2 * halfStrokeWidth) / inverseScaleX;
115            halfStrokeWidth = 0.0f;
116        }
117    }
118
119    SkPaint::Style style;
120    SkPaint::Cap cap;
121    bool isAA;
122    float inverseScaleX;
123    float inverseScaleY;
124    float halfStrokeWidth;
125    float maxAlpha;
126
127    inline void scaleOffsetForStrokeWidth(vec2& offset) const {
128        if (halfStrokeWidth == 0.0f) {
129            // hairline - compensate for scale
130            offset.x *= 0.5f * inverseScaleX;
131            offset.y *= 0.5f * inverseScaleY;
132        } else {
133            offset *= halfStrokeWidth;
134        }
135    }
136
137    /**
138     * NOTE: the input will not always be a normal, especially for sharp edges - it should be the
139     * result of totalOffsetFromNormals (see documentation there)
140     */
141    inline vec2 deriveAAOffset(const vec2& offset) const {
142        return vec2(offset.x * 0.5f * inverseScaleX,
143            offset.y * 0.5f * inverseScaleY);
144    }
145
146    /**
147     * Returns the number of cap divisions beyond the minimum 2 (kButt_Cap/kSquareCap will return 0)
148     * Should only be used when stroking and drawing caps
149     */
150    inline int capExtraDivisions() const {
151        if (cap == SkPaint::kRound_Cap) {
152            if (halfStrokeWidth == 0.0f) return 2;
153
154            // ROUND_CAP_THRESH is the maximum error for polygonal approximation of the round cap
155            const float errConst = (-ROUND_CAP_THRESH / halfStrokeWidth + 1);
156            const float targetCosVal = 2 * errConst * errConst - 1;
157            int neededDivisions = (int)(ceilf(PI / acos(targetCosVal)/2)) * 2;
158            return neededDivisions;
159        }
160        return 0;
161    }
162};
163
164void getFillVerticesFromPerimeter(const Vector<Vertex>& perimeter, VertexBuffer& vertexBuffer) {
165    Vertex* buffer = vertexBuffer.alloc<Vertex>(perimeter.size());
166
167    int currentIndex = 0;
168    // zig zag between all previous points on the inside of the hull to create a
169    // triangle strip that fills the hull
170    int srcAindex = 0;
171    int srcBindex = perimeter.size() - 1;
172    while (srcAindex <= srcBindex) {
173        copyVertex(&buffer[currentIndex++], &perimeter[srcAindex]);
174        if (srcAindex == srcBindex) break;
175        copyVertex(&buffer[currentIndex++], &perimeter[srcBindex]);
176        srcAindex++;
177        srcBindex--;
178    }
179}
180
181/*
182 * Fills a vertexBuffer with non-alpha vertices, zig-zagging at each perimeter point to create a
183 * tri-strip as wide as the stroke.
184 *
185 * Uses an additional 2 vertices at the end to wrap around, closing the tri-strip
186 * (for a total of perimeter.size() * 2 + 2 vertices)
187 */
188void getStrokeVerticesFromPerimeter(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter,
189        VertexBuffer& vertexBuffer) {
190    Vertex* buffer = vertexBuffer.alloc<Vertex>(perimeter.size() * 2 + 2);
191
192    int currentIndex = 0;
193    const Vertex* last = &(perimeter[perimeter.size() - 1]);
194    const Vertex* current = &(perimeter[0]);
195    vec2 lastNormal(current->position[1] - last->position[1],
196            last->position[0] - current->position[0]);
197    lastNormal.normalize();
198    for (unsigned int i = 0; i < perimeter.size(); i++) {
199        const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]);
200        vec2 nextNormal(next->position[1] - current->position[1],
201                current->position[0] - next->position[0]);
202        nextNormal.normalize();
203
204        vec2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal);
205        paintInfo.scaleOffsetForStrokeWidth(totalOffset);
206
207        Vertex::set(&buffer[currentIndex++],
208                current->position[0] + totalOffset.x,
209                current->position[1] + totalOffset.y);
210
211        Vertex::set(&buffer[currentIndex++],
212                current->position[0] - totalOffset.x,
213                current->position[1] - totalOffset.y);
214
215        last = current;
216        current = next;
217        lastNormal = nextNormal;
218    }
219
220    // wrap around to beginning
221    copyVertex(&buffer[currentIndex++], &buffer[0]);
222    copyVertex(&buffer[currentIndex++], &buffer[1]);
223
224    DEBUG_DUMP_BUFFER();
225}
226
227static inline void storeBeginEnd(const PaintInfo& paintInfo, const Vertex& center,
228        const vec2& normal, Vertex* buffer, int& currentIndex, bool begin) {
229    vec2 strokeOffset = normal;
230    paintInfo.scaleOffsetForStrokeWidth(strokeOffset);
231
232    vec2 referencePoint(center.position[0], center.position[1]);
233    if (paintInfo.cap == SkPaint::kSquare_Cap) {
234        referencePoint += vec2(-strokeOffset.y, strokeOffset.x) * (begin ? -1 : 1);
235    }
236
237    Vertex::set(&buffer[currentIndex++], referencePoint + strokeOffset);
238    Vertex::set(&buffer[currentIndex++], referencePoint - strokeOffset);
239}
240
241/**
242 * Fills a vertexBuffer with non-alpha vertices similar to getStrokeVerticesFromPerimeter, except:
243 *
244 * 1 - Doesn't need to wrap around, since the input vertices are unclosed
245 *
246 * 2 - can zig-zag across 'extra' vertices at either end, to create round caps
247 */
248void getStrokeVerticesFromUnclosedVertices(const PaintInfo& paintInfo,
249        const Vector<Vertex>& vertices, VertexBuffer& vertexBuffer) {
250    const int extra = paintInfo.capExtraDivisions();
251    const int allocSize = (vertices.size() + extra) * 2;
252    Vertex* buffer = vertexBuffer.alloc<Vertex>(allocSize);
253
254    const int lastIndex = vertices.size() - 1;
255    if (extra > 0) {
256        // tessellate both round caps
257        float beginTheta = atan2(
258                    - (vertices[0].position[0] - vertices[1].position[0]),
259                    vertices[0].position[1] - vertices[1].position[1]);
260        float endTheta = atan2(
261                    - (vertices[lastIndex].position[0] - vertices[lastIndex - 1].position[0]),
262                    vertices[lastIndex].position[1] - vertices[lastIndex - 1].position[1]);
263        const float dTheta = PI / (extra + 1);
264        const float radialScale = 2.0f / (1 + cos(dTheta));
265
266        int capOffset;
267        for (int i = 0; i < extra; i++) {
268            if (i < extra / 2) {
269                capOffset = extra - 2 * i - 1;
270            } else {
271                capOffset = 2 * i - extra;
272            }
273
274            beginTheta += dTheta;
275            vec2 beginRadialOffset(cos(beginTheta), sin(beginTheta));
276            paintInfo.scaleOffsetForStrokeWidth(beginRadialOffset);
277            Vertex::set(&buffer[capOffset],
278                    vertices[0].position[0] + beginRadialOffset.x,
279                    vertices[0].position[1] + beginRadialOffset.y);
280
281            endTheta += dTheta;
282            vec2 endRadialOffset(cos(endTheta), sin(endTheta));
283            paintInfo.scaleOffsetForStrokeWidth(endRadialOffset);
284            Vertex::set(&buffer[allocSize - 1 - capOffset],
285                    vertices[lastIndex].position[0] + endRadialOffset.x,
286                    vertices[lastIndex].position[1] + endRadialOffset.y);
287        }
288    }
289
290    int currentIndex = extra;
291    const Vertex* last = &(vertices[0]);
292    const Vertex* current = &(vertices[1]);
293    vec2 lastNormal(current->position[1] - last->position[1],
294                last->position[0] - current->position[0]);
295    lastNormal.normalize();
296
297    storeBeginEnd(paintInfo, vertices[0], lastNormal, buffer, currentIndex, true);
298
299    for (unsigned int i = 1; i < vertices.size() - 1; i++) {
300        const Vertex* next = &(vertices[i + 1]);
301        vec2 nextNormal(next->position[1] - current->position[1],
302                current->position[0] - next->position[0]);
303        nextNormal.normalize();
304
305        vec2 strokeOffset  = totalOffsetFromNormals(lastNormal, nextNormal);
306        paintInfo.scaleOffsetForStrokeWidth(strokeOffset);
307
308        vec2 center(current->position[0], current->position[1]);
309        Vertex::set(&buffer[currentIndex++], center + strokeOffset);
310        Vertex::set(&buffer[currentIndex++], center - strokeOffset);
311
312        current = next;
313        lastNormal = nextNormal;
314    }
315
316    storeBeginEnd(paintInfo, vertices[lastIndex], lastNormal, buffer, currentIndex, false);
317
318    DEBUG_DUMP_BUFFER();
319}
320
321/**
322 * Populates a vertexBuffer with AlphaVertices to create an anti-aliased fill shape tessellation
323 *
324 * 1 - create the AA perimeter of unit width, by zig-zagging at each point around the perimeter of
325 * the shape (using 2 * perimeter.size() vertices)
326 *
327 * 2 - wrap around to the beginning to complete the perimeter (2 vertices)
328 *
329 * 3 - zig zag back and forth inside the shape to fill it (using perimeter.size() vertices)
330 */
331void getFillVerticesFromPerimeterAA(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter,
332        VertexBuffer& vertexBuffer) {
333    AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(perimeter.size() * 3 + 2);
334
335    // generate alpha points - fill Alpha vertex gaps in between each point with
336    // alpha 0 vertex, offset by a scaled normal.
337    int currentIndex = 0;
338    const Vertex* last = &(perimeter[perimeter.size() - 1]);
339    const Vertex* current = &(perimeter[0]);
340    vec2 lastNormal(current->position[1] - last->position[1],
341            last->position[0] - current->position[0]);
342    lastNormal.normalize();
343    for (unsigned int i = 0; i < perimeter.size(); i++) {
344        const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]);
345        vec2 nextNormal(next->position[1] - current->position[1],
346                current->position[0] - next->position[0]);
347        nextNormal.normalize();
348
349        // AA point offset from original point is that point's normal, such that each side is offset
350        // by .5 pixels
351        vec2 totalOffset = paintInfo.deriveAAOffset(totalOffsetFromNormals(lastNormal, nextNormal));
352
353        AlphaVertex::set(&buffer[currentIndex++],
354                current->position[0] + totalOffset.x,
355                current->position[1] + totalOffset.y,
356                0.0f);
357        AlphaVertex::set(&buffer[currentIndex++],
358                current->position[0] - totalOffset.x,
359                current->position[1] - totalOffset.y,
360                1.0f);
361
362        last = current;
363        current = next;
364        lastNormal = nextNormal;
365    }
366
367    // wrap around to beginning
368    copyAlphaVertex(&buffer[currentIndex++], &buffer[0]);
369    copyAlphaVertex(&buffer[currentIndex++], &buffer[1]);
370
371    // zig zag between all previous points on the inside of the hull to create a
372    // triangle strip that fills the hull, repeating the first inner point to
373    // create degenerate tris to start inside path
374    int srcAindex = 0;
375    int srcBindex = perimeter.size() - 1;
376    while (srcAindex <= srcBindex) {
377        copyAlphaVertex(&buffer[currentIndex++], &buffer[srcAindex * 2 + 1]);
378        if (srcAindex == srcBindex) break;
379        copyAlphaVertex(&buffer[currentIndex++], &buffer[srcBindex * 2 + 1]);
380        srcAindex++;
381        srcBindex--;
382    }
383
384    DEBUG_DUMP_BUFFER();
385}
386
387/**
388 * Stores geometry for a single, AA-perimeter (potentially rounded) cap
389 *
390 * For explanation of constants and general methodoloyg, see comments for
391 * getStrokeVerticesFromUnclosedVerticesAA() below.
392 */
393inline static void storeCapAA(const PaintInfo& paintInfo, const Vector<Vertex>& vertices,
394        AlphaVertex* buffer, bool isFirst, vec2 normal, int offset) {
395    const int extra = paintInfo.capExtraDivisions();
396    const int extraOffset = (extra + 1) / 2;
397    const int capIndex = isFirst
398            ? 2 * offset + 6 + 2 * (extra + extraOffset)
399            : offset + 2 + 2 * extraOffset;
400    if (isFirst) normal *= -1;
401
402    // TODO: this normal should be scaled by radialScale if extra != 0, see totalOffsetFromNormals()
403    vec2 AAOffset = paintInfo.deriveAAOffset(normal);
404
405    vec2 strokeOffset = normal;
406    paintInfo.scaleOffsetForStrokeWidth(strokeOffset);
407    vec2 outerOffset = strokeOffset + AAOffset;
408    vec2 innerOffset = strokeOffset - AAOffset;
409
410    vec2 capAAOffset;
411    if (paintInfo.cap != SkPaint::kRound_Cap) {
412        // if the cap is square or butt, the inside primary cap vertices will be inset in two
413        // directions - both normal to the stroke, and parallel to it.
414        capAAOffset = vec2(-AAOffset.y, AAOffset.x);
415    }
416
417    // determine referencePoint, the center point for the 4 primary cap vertices
418    const Vertex* point = isFirst ? vertices.begin() : (vertices.end() - 1);
419    vec2 referencePoint(point->position[0], point->position[1]);
420    if (paintInfo.cap == SkPaint::kSquare_Cap) {
421        // To account for square cap, move the primary cap vertices (that create the AA edge) by the
422        // stroke offset vector (rotated to be parallel to the stroke)
423        referencePoint += vec2(-strokeOffset.y, strokeOffset.x);
424    }
425
426    AlphaVertex::set(&buffer[capIndex + 0],
427            referencePoint.x + outerOffset.x + capAAOffset.x,
428            referencePoint.y + outerOffset.y + capAAOffset.y,
429            0.0f);
430    AlphaVertex::set(&buffer[capIndex + 1],
431            referencePoint.x + innerOffset.x - capAAOffset.x,
432            referencePoint.y + innerOffset.y - capAAOffset.y,
433            paintInfo.maxAlpha);
434
435    bool isRound = paintInfo.cap == SkPaint::kRound_Cap;
436
437    const int postCapIndex = (isRound && isFirst) ? (2 * extraOffset - 2) : capIndex + (2 * extra);
438    AlphaVertex::set(&buffer[postCapIndex + 2],
439            referencePoint.x - outerOffset.x + capAAOffset.x,
440            referencePoint.y - outerOffset.y + capAAOffset.y,
441            0.0f);
442    AlphaVertex::set(&buffer[postCapIndex + 3],
443            referencePoint.x - innerOffset.x - capAAOffset.x,
444            referencePoint.y - innerOffset.y - capAAOffset.y,
445            paintInfo.maxAlpha);
446
447    if (isRound) {
448        const float dTheta = PI / (extra + 1);
449        const float radialScale = 2.0f / (1 + cos(dTheta));
450        float theta = atan2(normal.y, normal.x);
451        int capPerimIndex = capIndex + 2;
452
453        for (int i = 0; i < extra; i++) {
454            theta += dTheta;
455
456            vec2 radialOffset(cos(theta), sin(theta));
457
458            // scale to compensate for pinching at sharp angles, see totalOffsetFromNormals()
459            radialOffset *= radialScale;
460
461            AAOffset = paintInfo.deriveAAOffset(radialOffset);
462            paintInfo.scaleOffsetForStrokeWidth(radialOffset);
463            AlphaVertex::set(&buffer[capPerimIndex++],
464                    referencePoint.x + radialOffset.x + AAOffset.x,
465                    referencePoint.y + radialOffset.y + AAOffset.y,
466                    0.0f);
467            AlphaVertex::set(&buffer[capPerimIndex++],
468                    referencePoint.x + radialOffset.x - AAOffset.x,
469                    referencePoint.y + radialOffset.y - AAOffset.y,
470                    paintInfo.maxAlpha);
471
472            if (isFirst && i == extra - extraOffset) {
473                //copy most recent two points to first two points
474                copyAlphaVertex(&buffer[0], &buffer[capPerimIndex - 2]);
475                copyAlphaVertex(&buffer[1], &buffer[capPerimIndex - 1]);
476
477                capPerimIndex = 2; // start writing the rest of the round cap at index 2
478            }
479        }
480
481        if (isFirst) {
482            const int startCapFillIndex = capIndex + 2 * (extra - extraOffset) + 4;
483            int capFillIndex = startCapFillIndex;
484            for (int i = 0; i < extra + 2; i += 2) {
485                copyAlphaVertex(&buffer[capFillIndex++], &buffer[1 + i]);
486                // TODO: to support odd numbers of divisions, break here on the last iteration
487                copyAlphaVertex(&buffer[capFillIndex++], &buffer[startCapFillIndex - 3 - i]);
488            }
489        } else {
490            int capFillIndex = 6 * vertices.size() + 2 + 6 * extra - (extra + 2);
491            for (int i = 0; i < extra + 2; i += 2) {
492                copyAlphaVertex(&buffer[capFillIndex++], &buffer[capIndex + 1 + i]);
493                // TODO: to support odd numbers of divisions, break here on the last iteration
494                copyAlphaVertex(&buffer[capFillIndex++], &buffer[capIndex + 3 + 2 * extra - i]);
495            }
496        }
497        return;
498    }
499    if (isFirst) {
500        copyAlphaVertex(&buffer[0], &buffer[postCapIndex + 2]);
501        copyAlphaVertex(&buffer[1], &buffer[postCapIndex + 3]);
502        copyAlphaVertex(&buffer[postCapIndex + 4], &buffer[1]); // degenerate tris (the only two!)
503        copyAlphaVertex(&buffer[postCapIndex + 5], &buffer[postCapIndex + 1]);
504    } else {
505        copyAlphaVertex(&buffer[6 * vertices.size()], &buffer[postCapIndex + 1]);
506        copyAlphaVertex(&buffer[6 * vertices.size() + 1], &buffer[postCapIndex + 3]);
507    }
508}
509
510/*
511the geometry for an aa, capped stroke consists of the following:
512
513       # vertices       |    function
514----------------------------------------------------------------------
515a) 2                    | Start AA perimeter
516b) 2, 2 * roundDivOff   | First half of begin cap's perimeter
517                        |
518   2 * middlePts        | 'Outer' or 'Top' AA perimeter half (between caps)
519                        |
520a) 4                    | End cap's
521b) 2, 2 * roundDivs, 2  |    AA perimeter
522                        |
523   2 * middlePts        | 'Inner' or 'bottom' AA perimeter half
524                        |
525a) 6                    | Begin cap's perimeter
526b) 2, 2*(rD - rDO + 1), | Last half of begin cap's perimeter
527       roundDivs, 2     |
528                        |
529   2 * middlePts        | Stroke's full opacity center strip
530                        |
531a) 2                    | end stroke
532b) 2, roundDivs         |    (and end cap fill, for round)
533
534Notes:
535* rows starting with 'a)' denote the Butt or Square cap vertex use, 'b)' denote Round
536
537* 'middlePts' is (number of points in the unclosed input vertex list, minus 2) times two
538
539* 'roundDivs' or 'rD' is the number of extra vertices (beyond the minimum of 2) that define the
540        round cap's shape, and is at least two. This will increase with cap size to sufficiently
541        define the cap's level of tessellation.
542
543* 'roundDivOffset' or 'rDO' is the point about halfway along the start cap's round perimeter, where
544        the stream of vertices for the AA perimeter starts. By starting and ending the perimeter at
545        this offset, the fill of the stroke is drawn from this point with minimal extra vertices.
546
547This means the outer perimeter starts at:
548    outerIndex = (2) OR (2 + 2 * roundDivOff)
549the inner perimeter (since it is filled in reverse) starts at:
550    innerIndex = outerIndex + (4 * middlePts) + ((4) OR (4 + 2 * roundDivs)) - 1
551the stroke starts at:
552    strokeIndex = innerIndex + 1 + ((6) OR (6 + 3 * roundDivs - 2 * roundDivOffset))
553
554The total needed allocated space is either:
555    2 + 4 + 6 + 2 + 3 * (2 * middlePts) = 14 + 6 * middlePts = 2 + 6 * pts
556or, for rounded caps:
557    (2 + 2 * rDO) + (4 + 2 * rD) + (2 * (rD - rDO + 1)
558            + roundDivs + 4) + (2 + roundDivs) + 3 * (2 * middlePts)
559    = 14 + 6 * middlePts + 6 * roundDivs
560    = 2 + 6 * pts + 6 * roundDivs
561 */
562void getStrokeVerticesFromUnclosedVerticesAA(const PaintInfo& paintInfo,
563        const Vector<Vertex>& vertices, VertexBuffer& vertexBuffer) {
564
565    const int extra = paintInfo.capExtraDivisions();
566    const int allocSize = 6 * vertices.size() + 2 + 6 * extra;
567
568    AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(allocSize);
569
570    const int extraOffset = (extra + 1) / 2;
571    int offset = 2 * (vertices.size() - 2);
572    // there is no outer/inner here, using them for consistency with below approach
573    int currentAAOuterIndex = 2 + 2 * extraOffset;
574    int currentAAInnerIndex = currentAAOuterIndex + (2 * offset) + 3 + (2 * extra);
575    int currentStrokeIndex = currentAAInnerIndex + 7 + (3 * extra - 2 * extraOffset);
576
577    const Vertex* last = &(vertices[0]);
578    const Vertex* current = &(vertices[1]);
579    vec2 lastNormal(current->position[1] - last->position[1],
580            last->position[0] - current->position[0]);
581    lastNormal.normalize();
582
583    // TODO: use normal from bezier traversal for cap, instead of from vertices
584    storeCapAA(paintInfo, vertices, buffer, true, lastNormal, offset);
585
586    for (unsigned int i = 1; i < vertices.size() - 1; i++) {
587        const Vertex* next = &(vertices[i + 1]);
588        vec2 nextNormal(next->position[1] - current->position[1],
589                current->position[0] - next->position[0]);
590        nextNormal.normalize();
591
592        vec2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal);
593        vec2 AAOffset = paintInfo.deriveAAOffset(totalOffset);
594
595        vec2 innerOffset = totalOffset;
596        paintInfo.scaleOffsetForStrokeWidth(innerOffset);
597        vec2 outerOffset = innerOffset + AAOffset;
598        innerOffset -= AAOffset;
599
600        AlphaVertex::set(&buffer[currentAAOuterIndex++],
601                current->position[0] + outerOffset.x,
602                current->position[1] + outerOffset.y,
603                0.0f);
604        AlphaVertex::set(&buffer[currentAAOuterIndex++],
605                current->position[0] + innerOffset.x,
606                current->position[1] + innerOffset.y,
607                paintInfo.maxAlpha);
608
609        AlphaVertex::set(&buffer[currentStrokeIndex++],
610                current->position[0] + innerOffset.x,
611                current->position[1] + innerOffset.y,
612                paintInfo.maxAlpha);
613        AlphaVertex::set(&buffer[currentStrokeIndex++],
614                current->position[0] - innerOffset.x,
615                current->position[1] - innerOffset.y,
616                paintInfo.maxAlpha);
617
618        AlphaVertex::set(&buffer[currentAAInnerIndex--],
619                current->position[0] - innerOffset.x,
620                current->position[1] - innerOffset.y,
621                paintInfo.maxAlpha);
622        AlphaVertex::set(&buffer[currentAAInnerIndex--],
623                current->position[0] - outerOffset.x,
624                current->position[1] - outerOffset.y,
625                0.0f);
626
627        current = next;
628        lastNormal = nextNormal;
629    }
630
631    // TODO: use normal from bezier traversal for cap, instead of from vertices
632    storeCapAA(paintInfo, vertices, buffer, false, lastNormal, offset);
633
634    DEBUG_DUMP_ALPHA_BUFFER();
635}
636
637
638void getStrokeVerticesFromPerimeterAA(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter,
639        VertexBuffer& vertexBuffer) {
640    AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(6 * perimeter.size() + 8);
641
642    int offset = 2 * perimeter.size() + 3;
643    int currentAAOuterIndex = 0;
644    int currentStrokeIndex = offset;
645    int currentAAInnerIndex = offset * 2;
646
647    const Vertex* last = &(perimeter[perimeter.size() - 1]);
648    const Vertex* current = &(perimeter[0]);
649    vec2 lastNormal(current->position[1] - last->position[1],
650            last->position[0] - current->position[0]);
651    lastNormal.normalize();
652    for (unsigned int i = 0; i < perimeter.size(); i++) {
653        const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]);
654        vec2 nextNormal(next->position[1] - current->position[1],
655                current->position[0] - next->position[0]);
656        nextNormal.normalize();
657
658        vec2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal);
659        vec2 AAOffset = paintInfo.deriveAAOffset(totalOffset);
660
661        vec2 innerOffset = totalOffset;
662        paintInfo.scaleOffsetForStrokeWidth(innerOffset);
663        vec2 outerOffset = innerOffset + AAOffset;
664        innerOffset -= AAOffset;
665
666        AlphaVertex::set(&buffer[currentAAOuterIndex++],
667                current->position[0] + outerOffset.x,
668                current->position[1] + outerOffset.y,
669                0.0f);
670        AlphaVertex::set(&buffer[currentAAOuterIndex++],
671                current->position[0] + innerOffset.x,
672                current->position[1] + innerOffset.y,
673                paintInfo.maxAlpha);
674
675        AlphaVertex::set(&buffer[currentStrokeIndex++],
676                current->position[0] + innerOffset.x,
677                current->position[1] + innerOffset.y,
678                paintInfo.maxAlpha);
679        AlphaVertex::set(&buffer[currentStrokeIndex++],
680                current->position[0] - innerOffset.x,
681                current->position[1] - innerOffset.y,
682                paintInfo.maxAlpha);
683
684        AlphaVertex::set(&buffer[currentAAInnerIndex++],
685                current->position[0] - innerOffset.x,
686                current->position[1] - innerOffset.y,
687                paintInfo.maxAlpha);
688        AlphaVertex::set(&buffer[currentAAInnerIndex++],
689                current->position[0] - outerOffset.x,
690                current->position[1] - outerOffset.y,
691                0.0f);
692
693        last = current;
694        current = next;
695        lastNormal = nextNormal;
696    }
697
698    // wrap each strip around to beginning, creating degenerate tris to bridge strips
699    copyAlphaVertex(&buffer[currentAAOuterIndex++], &buffer[0]);
700    copyAlphaVertex(&buffer[currentAAOuterIndex++], &buffer[1]);
701    copyAlphaVertex(&buffer[currentAAOuterIndex++], &buffer[1]);
702
703    copyAlphaVertex(&buffer[currentStrokeIndex++], &buffer[offset]);
704    copyAlphaVertex(&buffer[currentStrokeIndex++], &buffer[offset + 1]);
705    copyAlphaVertex(&buffer[currentStrokeIndex++], &buffer[offset + 1]);
706
707    copyAlphaVertex(&buffer[currentAAInnerIndex++], &buffer[2 * offset]);
708    copyAlphaVertex(&buffer[currentAAInnerIndex++], &buffer[2 * offset + 1]);
709    // don't need to create last degenerate tri
710
711    DEBUG_DUMP_ALPHA_BUFFER();
712}
713
714void PathTessellator::tessellatePath(const SkPath &path, const SkPaint* paint,
715        const mat4 *transform, VertexBuffer& vertexBuffer) {
716    ATRACE_CALL();
717
718    const PaintInfo paintInfo(paint, transform);
719
720    Vector<Vertex> tempVertices;
721    float threshInvScaleX = paintInfo.inverseScaleX;
722    float threshInvScaleY = paintInfo.inverseScaleY;
723    if (paintInfo.style == SkPaint::kStroke_Style) {
724        // alter the bezier recursion threshold values we calculate in order to compensate for
725        // expansion done after the path vertices are found
726        SkRect bounds = path.getBounds();
727        if (!bounds.isEmpty()) {
728            threshInvScaleX *= bounds.width() / (bounds.width() + paint->getStrokeWidth());
729            threshInvScaleY *= bounds.height() / (bounds.height() + paint->getStrokeWidth());
730        }
731    }
732
733    // force close if we're filling the path, since fill path expects closed perimeter.
734    bool forceClose = paintInfo.style != SkPaint::kStroke_Style;
735    bool wasClosed = approximatePathOutlineVertices(path, forceClose,
736            threshInvScaleX * threshInvScaleX, threshInvScaleY * threshInvScaleY, tempVertices);
737
738    if (!tempVertices.size()) {
739        // path was empty, return without allocating vertex buffer
740        return;
741    }
742
743#if VERTEX_DEBUG
744    for (unsigned int i = 0; i < tempVertices.size(); i++) {
745        ALOGD("orig path: point at %f %f",
746                tempVertices[i].position[0], tempVertices[i].position[1]);
747    }
748#endif
749
750    if (paintInfo.style == SkPaint::kStroke_Style) {
751        if (!paintInfo.isAA) {
752            if (wasClosed) {
753                getStrokeVerticesFromPerimeter(paintInfo, tempVertices, vertexBuffer);
754            } else {
755                getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer);
756            }
757
758        } else {
759            if (wasClosed) {
760                getStrokeVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer);
761            } else {
762                getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer);
763            }
764        }
765    } else {
766        // For kStrokeAndFill style, the path should be adjusted externally.
767        // It will be treated as a fill here.
768        if (!paintInfo.isAA) {
769            getFillVerticesFromPerimeter(tempVertices, vertexBuffer);
770        } else {
771            getFillVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer);
772        }
773    }
774}
775
776static void expandRectToCoverVertex(SkRect& rect, float x, float y) {
777    rect.fLeft = fminf(rect.fLeft, x);
778    rect.fTop = fminf(rect.fTop, y);
779    rect.fRight = fmaxf(rect.fRight, x);
780    rect.fBottom = fmaxf(rect.fBottom, y);
781}
782static void expandRectToCoverVertex(SkRect& rect, const Vertex& vertex) {
783    expandRectToCoverVertex(rect, vertex.position[0], vertex.position[1]);
784}
785
786template <class TYPE>
787static void instanceVertices(VertexBuffer& srcBuffer, VertexBuffer& dstBuffer,
788        const float* points, int count, SkRect& bounds) {
789    bounds.set(points[0], points[1], points[0], points[1]);
790
791    int numPoints = count / 2;
792    int verticesPerPoint = srcBuffer.getVertexCount();
793    dstBuffer.alloc<TYPE>(numPoints * verticesPerPoint + (numPoints - 1) * 2);
794
795    for (int i = 0; i < count; i += 2) {
796        expandRectToCoverVertex(bounds, points[i + 0], points[i + 1]);
797        dstBuffer.copyInto<TYPE>(srcBuffer, points[i + 0], points[i + 1]);
798    }
799    dstBuffer.createDegenerateSeparators<TYPE>(verticesPerPoint);
800}
801
802void PathTessellator::tessellatePoints(const float* points, int count, SkPaint* paint,
803        const mat4* transform, SkRect& bounds, VertexBuffer& vertexBuffer) {
804    const PaintInfo paintInfo(paint, transform);
805
806    // determine point shape
807    SkPath path;
808    float radius = paintInfo.halfStrokeWidth;
809    if (radius == 0.0f) radius = 0.25f;
810
811    if (paintInfo.cap == SkPaint::kRound_Cap) {
812        path.addCircle(0, 0, radius);
813    } else {
814        path.addRect(-radius, -radius, radius, radius);
815    }
816
817    // calculate outline
818    Vector<Vertex> outlineVertices;
819    approximatePathOutlineVertices(path, true,
820            paintInfo.inverseScaleX * paintInfo.inverseScaleX,
821            paintInfo.inverseScaleY * paintInfo.inverseScaleY, outlineVertices);
822
823    if (!outlineVertices.size()) return;
824
825    // tessellate, then duplicate outline across points
826    int numPoints = count / 2;
827    VertexBuffer tempBuffer;
828    if (!paintInfo.isAA) {
829        getFillVerticesFromPerimeter(outlineVertices, tempBuffer);
830        instanceVertices<Vertex>(tempBuffer, vertexBuffer, points, count, bounds);
831    } else {
832        getFillVerticesFromPerimeterAA(paintInfo, outlineVertices, tempBuffer);
833        instanceVertices<AlphaVertex>(tempBuffer, vertexBuffer, points, count, bounds);
834    }
835
836    expandBoundsForStroke(bounds, paint, true); // force-expand bounds to incorporate stroke
837}
838
839void PathTessellator::tessellateLines(const float* points, int count, SkPaint* paint,
840        const mat4* transform, SkRect& bounds, VertexBuffer& vertexBuffer) {
841    ATRACE_CALL();
842    const PaintInfo paintInfo(paint, transform);
843
844    const int extra = paintInfo.capExtraDivisions();
845    int numLines = count / 4;
846    int lineAllocSize;
847    // pre-allocate space for lines in the buffer, and degenerate tris in between
848    if (paintInfo.isAA) {
849        lineAllocSize = 6 * (2) + 2 + 6 * extra;
850        vertexBuffer.alloc<AlphaVertex>(numLines * lineAllocSize + (numLines - 1) * 2);
851    } else {
852        lineAllocSize = 2 * ((2) + extra);
853        vertexBuffer.alloc<Vertex>(numLines * lineAllocSize + (numLines - 1) * 2);
854    }
855
856    Vector<Vertex> tempVertices;
857    tempVertices.push();
858    tempVertices.push();
859    Vertex* tempVerticesData = tempVertices.editArray();
860    bounds.set(points[0], points[1], points[0], points[1]);
861    for (int i = 0; i < count; i += 4) {
862        Vertex::set(&(tempVerticesData[0]), points[i + 0], points[i + 1]);
863        Vertex::set(&(tempVerticesData[1]), points[i + 2], points[i + 3]);
864
865        if (paintInfo.isAA) {
866            getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer);
867        } else {
868            getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer);
869        }
870
871        // calculate bounds
872        expandRectToCoverVertex(bounds, tempVerticesData[0]);
873        expandRectToCoverVertex(bounds, tempVerticesData[1]);
874    }
875
876    expandBoundsForStroke(bounds, paint, true); // force-expand bounds to incorporate stroke
877
878    // since multiple objects tessellated into buffer, separate them with degen tris
879    if (paintInfo.isAA) {
880        vertexBuffer.createDegenerateSeparators<AlphaVertex>(lineAllocSize);
881    } else {
882        vertexBuffer.createDegenerateSeparators<Vertex>(lineAllocSize);
883    }
884}
885
886///////////////////////////////////////////////////////////////////////////////
887// Simple path line approximation
888///////////////////////////////////////////////////////////////////////////////
889
890void pushToVector(Vector<Vertex>& vertices, float x, float y) {
891    // TODO: make this not yuck
892    vertices.push();
893    Vertex* newVertex = &(vertices.editArray()[vertices.size() - 1]);
894    Vertex::set(newVertex, x, y);
895}
896
897bool PathTessellator::approximatePathOutlineVertices(const SkPath& path, bool forceClose,
898        float sqrInvScaleX, float sqrInvScaleY, Vector<Vertex>& outputVertices) {
899    ATRACE_CALL();
900
901    // TODO: to support joins other than sharp miter, join vertices should be labelled in the
902    // perimeter, or resolved into more vertices. Reconsider forceClose-ing in that case.
903    SkPath::Iter iter(path, forceClose);
904    SkPoint pts[4];
905    SkPath::Verb v;
906    while (SkPath::kDone_Verb != (v = iter.next(pts))) {
907            switch (v) {
908            case SkPath::kMove_Verb:
909                pushToVector(outputVertices, pts[0].x(), pts[0].y());
910                ALOGV("Move to pos %f %f", pts[0].x(), pts[0].y());
911                break;
912            case SkPath::kClose_Verb:
913                ALOGV("Close at pos %f %f", pts[0].x(), pts[0].y());
914                break;
915            case SkPath::kLine_Verb:
916                ALOGV("kLine_Verb %f %f -> %f %f", pts[0].x(), pts[0].y(), pts[1].x(), pts[1].y());
917                pushToVector(outputVertices, pts[1].x(), pts[1].y());
918                break;
919            case SkPath::kQuad_Verb:
920                ALOGV("kQuad_Verb");
921                recursiveQuadraticBezierVertices(
922                        pts[0].x(), pts[0].y(),
923                        pts[2].x(), pts[2].y(),
924                        pts[1].x(), pts[1].y(),
925                        sqrInvScaleX, sqrInvScaleY, outputVertices);
926                break;
927            case SkPath::kCubic_Verb:
928                ALOGV("kCubic_Verb");
929                recursiveCubicBezierVertices(
930                        pts[0].x(), pts[0].y(),
931                        pts[1].x(), pts[1].y(),
932                        pts[3].x(), pts[3].y(),
933                        pts[2].x(), pts[2].y(),
934                        sqrInvScaleX, sqrInvScaleY, outputVertices);
935                break;
936            default:
937                break;
938            }
939    }
940
941    int size = outputVertices.size();
942    if (size >= 2 && outputVertices[0].position[0] == outputVertices[size - 1].position[0] &&
943            outputVertices[0].position[1] == outputVertices[size - 1].position[1]) {
944        outputVertices.pop();
945        return true;
946    }
947    return false;
948}
949
950///////////////////////////////////////////////////////////////////////////////
951// Bezier approximation
952///////////////////////////////////////////////////////////////////////////////
953
954void PathTessellator::recursiveCubicBezierVertices(
955        float p1x, float p1y, float c1x, float c1y,
956        float p2x, float p2y, float c2x, float c2y,
957        float sqrInvScaleX, float sqrInvScaleY, Vector<Vertex>& outputVertices) {
958    float dx = p2x - p1x;
959    float dy = p2y - p1y;
960    float d1 = fabs((c1x - p2x) * dy - (c1y - p2y) * dx);
961    float d2 = fabs((c2x - p2x) * dy - (c2y - p2y) * dx);
962    float d = d1 + d2;
963
964    // multiplying by sqrInvScaleY/X equivalent to multiplying in dimensional scale factors
965
966    if (d * d < THRESHOLD * THRESHOLD * (dx * dx * sqrInvScaleY + dy * dy * sqrInvScaleX)) {
967        // below thresh, draw line by adding endpoint
968        pushToVector(outputVertices, p2x, p2y);
969    } else {
970        float p1c1x = (p1x + c1x) * 0.5f;
971        float p1c1y = (p1y + c1y) * 0.5f;
972        float p2c2x = (p2x + c2x) * 0.5f;
973        float p2c2y = (p2y + c2y) * 0.5f;
974
975        float c1c2x = (c1x + c2x) * 0.5f;
976        float c1c2y = (c1y + c2y) * 0.5f;
977
978        float p1c1c2x = (p1c1x + c1c2x) * 0.5f;
979        float p1c1c2y = (p1c1y + c1c2y) * 0.5f;
980
981        float p2c1c2x = (p2c2x + c1c2x) * 0.5f;
982        float p2c1c2y = (p2c2y + c1c2y) * 0.5f;
983
984        float mx = (p1c1c2x + p2c1c2x) * 0.5f;
985        float my = (p1c1c2y + p2c1c2y) * 0.5f;
986
987        recursiveCubicBezierVertices(
988                p1x, p1y, p1c1x, p1c1y,
989                mx, my, p1c1c2x, p1c1c2y,
990                sqrInvScaleX, sqrInvScaleY, outputVertices);
991        recursiveCubicBezierVertices(
992                mx, my, p2c1c2x, p2c1c2y,
993                p2x, p2y, p2c2x, p2c2y,
994                sqrInvScaleX, sqrInvScaleY, outputVertices);
995    }
996}
997
998void PathTessellator::recursiveQuadraticBezierVertices(
999        float ax, float ay,
1000        float bx, float by,
1001        float cx, float cy,
1002        float sqrInvScaleX, float sqrInvScaleY, Vector<Vertex>& outputVertices) {
1003    float dx = bx - ax;
1004    float dy = by - ay;
1005    float d = (cx - bx) * dy - (cy - by) * dx;
1006
1007    if (d * d < THRESHOLD * THRESHOLD * (dx * dx * sqrInvScaleY + dy * dy * sqrInvScaleX)) {
1008        // below thresh, draw line by adding endpoint
1009        pushToVector(outputVertices, bx, by);
1010    } else {
1011        float acx = (ax + cx) * 0.5f;
1012        float bcx = (bx + cx) * 0.5f;
1013        float acy = (ay + cy) * 0.5f;
1014        float bcy = (by + cy) * 0.5f;
1015
1016        // midpoint
1017        float mx = (acx + bcx) * 0.5f;
1018        float my = (acy + bcy) * 0.5f;
1019
1020        recursiveQuadraticBezierVertices(ax, ay, mx, my, acx, acy,
1021                sqrInvScaleX, sqrInvScaleY, outputVertices);
1022        recursiveQuadraticBezierVertices(mx, my, bx, by, bcx, bcy,
1023                sqrInvScaleX, sqrInvScaleY, outputVertices);
1024    }
1025}
1026
1027}; // namespace uirenderer
1028}; // namespace android
1029