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 void copyVertex(Vertex* destPtr, const Vertex* srcPtr) {
70    Vertex::set(destPtr, srcPtr->position[0], srcPtr->position[1]);
71}
72
73inline 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 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
227/**
228 * Fills a vertexBuffer with non-alpha vertices similar to getStrokeVerticesFromPerimeter, except:
229 *
230 * 1 - Doesn't need to wrap around, since the input vertices are unclosed
231 *
232 * 2 - can zig-zag across 'extra' vertices at either end, to create round caps
233 */
234void getStrokeVerticesFromUnclosedVertices(const PaintInfo& paintInfo,
235        const Vector<Vertex>& vertices, VertexBuffer& vertexBuffer) {
236    const int extra = paintInfo.capExtraDivisions();
237    const int allocSize = (vertices.size() + extra) * 2;
238
239    Vertex* buffer = vertexBuffer.alloc<Vertex>(allocSize);
240
241    if (extra > 0) {
242        // tessellate both round caps
243        const int last = vertices.size() - 1;
244        float beginTheta = atan2(
245                - (vertices[0].position[0] - vertices[1].position[0]),
246                vertices[0].position[1] - vertices[1].position[1]);
247        float endTheta = atan2(
248                - (vertices[last].position[0] - vertices[last - 1].position[0]),
249                vertices[last].position[1] - vertices[last - 1].position[1]);
250
251        const float dTheta = PI / (extra + 1);
252        const float radialScale = 2.0f / (1 + cos(dTheta));
253
254        int capOffset;
255        for (int i = 0; i < extra; i++) {
256            if (i < extra / 2) {
257                capOffset = extra - 2 * i - 1;
258            } else {
259                capOffset = 2 * i - extra;
260            }
261
262            beginTheta += dTheta;
263            vec2 beginRadialOffset(cos(beginTheta), sin(beginTheta));
264            paintInfo.scaleOffsetForStrokeWidth(beginRadialOffset);
265            Vertex::set(&buffer[capOffset],
266                    vertices[0].position[0] + beginRadialOffset.x,
267                    vertices[0].position[1] + beginRadialOffset.y);
268
269            endTheta += dTheta;
270            vec2 endRadialOffset(cos(endTheta), sin(endTheta));
271            paintInfo.scaleOffsetForStrokeWidth(endRadialOffset);
272            Vertex::set(&buffer[allocSize - 1 - capOffset],
273                    vertices[last].position[0] + endRadialOffset.x,
274                    vertices[last].position[1] + endRadialOffset.y);
275        }
276    }
277
278    int currentIndex = extra;
279    const Vertex* current = &(vertices[0]);
280    vec2 lastNormal;
281    for (unsigned int i = 0; i < vertices.size() - 1; i++) {
282        const Vertex* next = &(vertices[i + 1]);
283        vec2 nextNormal(next->position[1] - current->position[1],
284                current->position[0] - next->position[0]);
285        nextNormal.normalize();
286
287        vec2 totalOffset;
288        if (i == 0) {
289            totalOffset = nextNormal;
290        } else {
291            totalOffset = totalOffsetFromNormals(lastNormal, nextNormal);
292        }
293        paintInfo.scaleOffsetForStrokeWidth(totalOffset);
294
295        Vertex::set(&buffer[currentIndex++],
296                current->position[0] + totalOffset.x,
297                current->position[1] + totalOffset.y);
298
299        Vertex::set(&buffer[currentIndex++],
300                current->position[0] - totalOffset.x,
301                current->position[1] - totalOffset.y);
302
303        current = next;
304        lastNormal = nextNormal;
305    }
306
307    vec2 totalOffset = lastNormal;
308    paintInfo.scaleOffsetForStrokeWidth(totalOffset);
309
310    Vertex::set(&buffer[currentIndex++],
311            current->position[0] + totalOffset.x,
312            current->position[1] + totalOffset.y);
313    Vertex::set(&buffer[currentIndex++],
314            current->position[0] - totalOffset.x,
315            current->position[1] - totalOffset.y);
316
317    DEBUG_DUMP_BUFFER();
318}
319
320/**
321 * Populates a vertexBuffer with AlphaVertices to create an anti-aliased fill shape tessellation
322 *
323 * 1 - create the AA perimeter of unit width, by zig-zagging at each point around the perimeter of
324 * the shape (using 2 * perimeter.size() vertices)
325 *
326 * 2 - wrap around to the beginning to complete the perimeter (2 vertices)
327 *
328 * 3 - zig zag back and forth inside the shape to fill it (using perimeter.size() vertices)
329 */
330void getFillVerticesFromPerimeterAA(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter,
331        VertexBuffer& vertexBuffer) {
332    AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(perimeter.size() * 3 + 2);
333
334    // generate alpha points - fill Alpha vertex gaps in between each point with
335    // alpha 0 vertex, offset by a scaled normal.
336    int currentIndex = 0;
337    const Vertex* last = &(perimeter[perimeter.size() - 1]);
338    const Vertex* current = &(perimeter[0]);
339    vec2 lastNormal(current->position[1] - last->position[1],
340            last->position[0] - current->position[0]);
341    lastNormal.normalize();
342    for (unsigned int i = 0; i < perimeter.size(); i++) {
343        const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]);
344        vec2 nextNormal(next->position[1] - current->position[1],
345                current->position[0] - next->position[0]);
346        nextNormal.normalize();
347
348        // AA point offset from original point is that point's normal, such that each side is offset
349        // by .5 pixels
350        vec2 totalOffset = paintInfo.deriveAAOffset(totalOffsetFromNormals(lastNormal, nextNormal));
351
352        AlphaVertex::set(&buffer[currentIndex++],
353                current->position[0] + totalOffset.x,
354                current->position[1] + totalOffset.y,
355                0.0f);
356        AlphaVertex::set(&buffer[currentIndex++],
357                current->position[0] - totalOffset.x,
358                current->position[1] - totalOffset.y,
359                1.0f);
360
361        last = current;
362        current = next;
363        lastNormal = nextNormal;
364    }
365
366    // wrap around to beginning
367    copyAlphaVertex(&buffer[currentIndex++], &buffer[0]);
368    copyAlphaVertex(&buffer[currentIndex++], &buffer[1]);
369
370    // zig zag between all previous points on the inside of the hull to create a
371    // triangle strip that fills the hull, repeating the first inner point to
372    // create degenerate tris to start inside path
373    int srcAindex = 0;
374    int srcBindex = perimeter.size() - 1;
375    while (srcAindex <= srcBindex) {
376        copyAlphaVertex(&buffer[currentIndex++], &buffer[srcAindex * 2 + 1]);
377        if (srcAindex == srcBindex) break;
378        copyAlphaVertex(&buffer[currentIndex++], &buffer[srcBindex * 2 + 1]);
379        srcAindex++;
380        srcBindex--;
381    }
382
383    DEBUG_DUMP_BUFFER();
384}
385
386/**
387 * Stores geometry for a single, AA-perimeter (potentially rounded) cap
388 *
389 * For explanation of constants and general methodoloyg, see comments for
390 * getStrokeVerticesFromUnclosedVerticesAA() below.
391 */
392inline void storeCapAA(const PaintInfo& paintInfo, const Vector<Vertex>& vertices,
393        AlphaVertex* buffer, bool isFirst, vec2 normal, int offset) {
394    const int extra = paintInfo.capExtraDivisions();
395    const int extraOffset = (extra + 1) / 2;
396    const int capIndex = isFirst
397            ? 2 * offset + 6 + 2 * (extra + extraOffset)
398            : offset + 2 + 2 * extraOffset;
399    if (isFirst) normal *= -1;
400
401    // TODO: this normal should be scaled by radialScale if extra != 0, see totalOffsetFromNormals()
402    vec2 AAOffset = paintInfo.deriveAAOffset(normal);
403
404    vec2 strokeOffset = normal;
405    paintInfo.scaleOffsetForStrokeWidth(strokeOffset);
406    vec2 outerOffset = strokeOffset + AAOffset;
407    vec2 innerOffset = strokeOffset - AAOffset;
408
409    vec2 capAAOffset;
410    if (paintInfo.cap != SkPaint::kRound_Cap) {
411        // if the cap is square or butt, the inside primary cap vertices will be inset in two
412        // directions - both normal to the stroke, and parallel to it.
413        capAAOffset = vec2(-AAOffset.y, AAOffset.x);
414    }
415
416    // determine referencePoint, the center point for the 4 primary cap vertices
417    const Vertex* point = isFirst ? vertices.begin() : (vertices.end() - 1);
418    vec2 referencePoint(point->position[0], point->position[1]);
419    if (paintInfo.cap == SkPaint::kSquare_Cap) {
420        // To account for square cap, move the primary cap vertices (that create the AA edge) by the
421        // stroke offset vector (rotated to be parallel to the stroke)
422        referencePoint += vec2(-strokeOffset.y, strokeOffset.x);
423    }
424
425    AlphaVertex::set(&buffer[capIndex + 0],
426            referencePoint.x + outerOffset.x + capAAOffset.x,
427            referencePoint.y + outerOffset.y + capAAOffset.y,
428            0.0f);
429    AlphaVertex::set(&buffer[capIndex + 1],
430            referencePoint.x + innerOffset.x - capAAOffset.x,
431            referencePoint.y + innerOffset.y - capAAOffset.y,
432            paintInfo.maxAlpha);
433
434    bool isRound = paintInfo.cap == SkPaint::kRound_Cap;
435
436    const int postCapIndex = (isRound && isFirst) ? (2 * extraOffset - 2) : capIndex + (2 * extra);
437    AlphaVertex::set(&buffer[postCapIndex + 2],
438            referencePoint.x - outerOffset.x + capAAOffset.x,
439            referencePoint.y - outerOffset.y + capAAOffset.y,
440            0.0f);
441    AlphaVertex::set(&buffer[postCapIndex + 3],
442            referencePoint.x - innerOffset.x - capAAOffset.x,
443            referencePoint.y - innerOffset.y - capAAOffset.y,
444            paintInfo.maxAlpha);
445
446    if (isRound) {
447        const float dTheta = PI / (extra + 1);
448        const float radialScale = 2.0f / (1 + cos(dTheta));
449        float theta = atan2(normal.y, normal.x);
450        int capPerimIndex = capIndex + 2;
451
452        for (int i = 0; i < extra; i++) {
453            theta += dTheta;
454
455            vec2 radialOffset(cos(theta), sin(theta));
456
457            // scale to compensate for pinching at sharp angles, see totalOffsetFromNormals()
458            radialOffset *= radialScale;
459
460            AAOffset = paintInfo.deriveAAOffset(radialOffset);
461            paintInfo.scaleOffsetForStrokeWidth(radialOffset);
462            AlphaVertex::set(&buffer[capPerimIndex++],
463                    referencePoint.x + radialOffset.x + AAOffset.x,
464                    referencePoint.y + radialOffset.y + AAOffset.y,
465                    0.0f);
466            AlphaVertex::set(&buffer[capPerimIndex++],
467                    referencePoint.x + radialOffset.x - AAOffset.x,
468                    referencePoint.y + radialOffset.y - AAOffset.y,
469                    paintInfo.maxAlpha);
470
471            if (isFirst && i == extra - extraOffset) {
472                //copy most recent two points to first two points
473                copyAlphaVertex(&buffer[0], &buffer[capPerimIndex - 2]);
474                copyAlphaVertex(&buffer[1], &buffer[capPerimIndex - 1]);
475
476                capPerimIndex = 2; // start writing the rest of the round cap at index 2
477            }
478        }
479
480        if (isFirst) {
481            const int startCapFillIndex = capIndex + 2 * (extra - extraOffset) + 4;
482            int capFillIndex = startCapFillIndex;
483            for (int i = 0; i < extra + 2; i += 2) {
484                copyAlphaVertex(&buffer[capFillIndex++], &buffer[1 + i]);
485                // TODO: to support odd numbers of divisions, break here on the last iteration
486                copyAlphaVertex(&buffer[capFillIndex++], &buffer[startCapFillIndex - 3 - i]);
487            }
488        } else {
489            int capFillIndex = 6 * vertices.size() + 2 + 6 * extra - (extra + 2);
490            for (int i = 0; i < extra + 2; i += 2) {
491                copyAlphaVertex(&buffer[capFillIndex++], &buffer[capIndex + 1 + i]);
492                // TODO: to support odd numbers of divisions, break here on the last iteration
493                copyAlphaVertex(&buffer[capFillIndex++], &buffer[capIndex + 3 + 2 * extra - i]);
494            }
495        }
496        return;
497    }
498    if (isFirst) {
499        copyAlphaVertex(&buffer[0], &buffer[postCapIndex + 2]);
500        copyAlphaVertex(&buffer[1], &buffer[postCapIndex + 3]);
501        copyAlphaVertex(&buffer[postCapIndex + 4], &buffer[1]); // degenerate tris (the only two!)
502        copyAlphaVertex(&buffer[postCapIndex + 5], &buffer[postCapIndex + 1]);
503    } else {
504        copyAlphaVertex(&buffer[6 * vertices.size()], &buffer[postCapIndex + 1]);
505        copyAlphaVertex(&buffer[6 * vertices.size() + 1], &buffer[postCapIndex + 3]);
506    }
507}
508
509/*
510the geometry for an aa, capped stroke consists of the following:
511
512       # vertices       |    function
513----------------------------------------------------------------------
514a) 2                    | Start AA perimeter
515b) 2, 2 * roundDivOff   | First half of begin cap's perimeter
516                        |
517   2 * middlePts        | 'Outer' or 'Top' AA perimeter half (between caps)
518                        |
519a) 4                    | End cap's
520b) 2, 2 * roundDivs, 2  |    AA perimeter
521                        |
522   2 * middlePts        | 'Inner' or 'bottom' AA perimeter half
523                        |
524a) 6                    | Begin cap's perimeter
525b) 2, 2*(rD - rDO + 1), | Last half of begin cap's perimeter
526       roundDivs, 2     |
527                        |
528   2 * middlePts        | Stroke's full opacity center strip
529                        |
530a) 2                    | end stroke
531b) 2, roundDivs         |    (and end cap fill, for round)
532
533Notes:
534* rows starting with 'a)' denote the Butt or Square cap vertex use, 'b)' denote Round
535
536* 'middlePts' is (number of points in the unclosed input vertex list, minus 2) times two
537
538* 'roundDivs' or 'rD' is the number of extra vertices (beyond the minimum of 2) that define the
539        round cap's shape, and is at least two. This will increase with cap size to sufficiently
540        define the cap's level of tessellation.
541
542* 'roundDivOffset' or 'rDO' is the point about halfway along the start cap's round perimeter, where
543        the stream of vertices for the AA perimeter starts. By starting and ending the perimeter at
544        this offset, the fill of the stroke is drawn from this point with minimal extra vertices.
545
546This means the outer perimeter starts at:
547    outerIndex = (2) OR (2 + 2 * roundDivOff)
548the inner perimeter (since it is filled in reverse) starts at:
549    innerIndex = outerIndex + (4 * middlePts) + ((4) OR (4 + 2 * roundDivs)) - 1
550the stroke starts at:
551    strokeIndex = innerIndex + 1 + ((6) OR (6 + 3 * roundDivs - 2 * roundDivOffset))
552
553The total needed allocated space is either:
554    2 + 4 + 6 + 2 + 3 * (2 * middlePts) = 14 + 6 * middlePts = 2 + 6 * pts
555or, for rounded caps:
556    (2 + 2 * rDO) + (4 + 2 * rD) + (2 * (rD - rDO + 1)
557            + roundDivs + 4) + (2 + roundDivs) + 3 * (2 * middlePts)
558    = 14 + 6 * middlePts + 6 * roundDivs
559    = 2 + 6 * pts + 6 * roundDivs
560 */
561void getStrokeVerticesFromUnclosedVerticesAA(const PaintInfo& paintInfo,
562        const Vector<Vertex>& vertices, VertexBuffer& vertexBuffer) {
563
564    const int extra = paintInfo.capExtraDivisions();
565    const int allocSize = 6 * vertices.size() + 2 + 6 * extra;
566
567    AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(allocSize);
568
569    const int extraOffset = (extra + 1) / 2;
570    int offset = 2 * (vertices.size() - 2);
571    // there is no outer/inner here, using them for consistency with below approach
572    int currentAAOuterIndex = 2 + 2 * extraOffset;
573    int currentAAInnerIndex = currentAAOuterIndex + (2 * offset) + 3 + (2 * extra);
574    int currentStrokeIndex = currentAAInnerIndex + 7 + (3 * extra - 2 * extraOffset);
575
576    const Vertex* last = &(vertices[0]);
577    const Vertex* current = &(vertices[1]);
578    vec2 lastNormal(current->position[1] - last->position[1],
579            last->position[0] - current->position[0]);
580    lastNormal.normalize();
581
582    // TODO: use normal from bezier traversal for cap, instead of from vertices
583    storeCapAA(paintInfo, vertices, buffer, true, lastNormal, offset);
584
585    for (unsigned int i = 1; i < vertices.size() - 1; i++) {
586        const Vertex* next = &(vertices[i + 1]);
587        vec2 nextNormal(next->position[1] - current->position[1],
588                current->position[0] - next->position[0]);
589        nextNormal.normalize();
590
591        vec2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal);
592        vec2 AAOffset = paintInfo.deriveAAOffset(totalOffset);
593
594        vec2 innerOffset = totalOffset;
595        paintInfo.scaleOffsetForStrokeWidth(innerOffset);
596        vec2 outerOffset = innerOffset + AAOffset;
597        innerOffset -= AAOffset;
598
599        AlphaVertex::set(&buffer[currentAAOuterIndex++],
600                current->position[0] + outerOffset.x,
601                current->position[1] + outerOffset.y,
602                0.0f);
603        AlphaVertex::set(&buffer[currentAAOuterIndex++],
604                current->position[0] + innerOffset.x,
605                current->position[1] + innerOffset.y,
606                paintInfo.maxAlpha);
607
608        AlphaVertex::set(&buffer[currentStrokeIndex++],
609                current->position[0] + innerOffset.x,
610                current->position[1] + innerOffset.y,
611                paintInfo.maxAlpha);
612        AlphaVertex::set(&buffer[currentStrokeIndex++],
613                current->position[0] - innerOffset.x,
614                current->position[1] - innerOffset.y,
615                paintInfo.maxAlpha);
616
617        AlphaVertex::set(&buffer[currentAAInnerIndex--],
618                current->position[0] - innerOffset.x,
619                current->position[1] - innerOffset.y,
620                paintInfo.maxAlpha);
621        AlphaVertex::set(&buffer[currentAAInnerIndex--],
622                current->position[0] - outerOffset.x,
623                current->position[1] - outerOffset.y,
624                0.0f);
625
626        current = next;
627        lastNormal = nextNormal;
628    }
629
630    // TODO: use normal from bezier traversal for cap, instead of from vertices
631    storeCapAA(paintInfo, vertices, buffer, false, lastNormal, offset);
632
633    DEBUG_DUMP_ALPHA_BUFFER();
634}
635
636
637void getStrokeVerticesFromPerimeterAA(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter,
638        VertexBuffer& vertexBuffer) {
639    AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(6 * perimeter.size() + 8);
640
641    int offset = 2 * perimeter.size() + 3;
642    int currentAAOuterIndex = 0;
643    int currentStrokeIndex = offset;
644    int currentAAInnerIndex = offset * 2;
645
646    const Vertex* last = &(perimeter[perimeter.size() - 1]);
647    const Vertex* current = &(perimeter[0]);
648    vec2 lastNormal(current->position[1] - last->position[1],
649            last->position[0] - current->position[0]);
650    lastNormal.normalize();
651    for (unsigned int i = 0; i < perimeter.size(); i++) {
652        const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]);
653        vec2 nextNormal(next->position[1] - current->position[1],
654                current->position[0] - next->position[0]);
655        nextNormal.normalize();
656
657        vec2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal);
658        vec2 AAOffset = paintInfo.deriveAAOffset(totalOffset);
659
660        vec2 innerOffset = totalOffset;
661        paintInfo.scaleOffsetForStrokeWidth(innerOffset);
662        vec2 outerOffset = innerOffset + AAOffset;
663        innerOffset -= AAOffset;
664
665        AlphaVertex::set(&buffer[currentAAOuterIndex++],
666                current->position[0] + outerOffset.x,
667                current->position[1] + outerOffset.y,
668                0.0f);
669        AlphaVertex::set(&buffer[currentAAOuterIndex++],
670                current->position[0] + innerOffset.x,
671                current->position[1] + innerOffset.y,
672                paintInfo.maxAlpha);
673
674        AlphaVertex::set(&buffer[currentStrokeIndex++],
675                current->position[0] + innerOffset.x,
676                current->position[1] + innerOffset.y,
677                paintInfo.maxAlpha);
678        AlphaVertex::set(&buffer[currentStrokeIndex++],
679                current->position[0] - innerOffset.x,
680                current->position[1] - innerOffset.y,
681                paintInfo.maxAlpha);
682
683        AlphaVertex::set(&buffer[currentAAInnerIndex++],
684                current->position[0] - innerOffset.x,
685                current->position[1] - innerOffset.y,
686                paintInfo.maxAlpha);
687        AlphaVertex::set(&buffer[currentAAInnerIndex++],
688                current->position[0] - outerOffset.x,
689                current->position[1] - outerOffset.y,
690                0.0f);
691
692        last = current;
693        current = next;
694        lastNormal = nextNormal;
695    }
696
697    // wrap each strip around to beginning, creating degenerate tris to bridge strips
698    copyAlphaVertex(&buffer[currentAAOuterIndex++], &buffer[0]);
699    copyAlphaVertex(&buffer[currentAAOuterIndex++], &buffer[1]);
700    copyAlphaVertex(&buffer[currentAAOuterIndex++], &buffer[1]);
701
702    copyAlphaVertex(&buffer[currentStrokeIndex++], &buffer[offset]);
703    copyAlphaVertex(&buffer[currentStrokeIndex++], &buffer[offset + 1]);
704    copyAlphaVertex(&buffer[currentStrokeIndex++], &buffer[offset + 1]);
705
706    copyAlphaVertex(&buffer[currentAAInnerIndex++], &buffer[2 * offset]);
707    copyAlphaVertex(&buffer[currentAAInnerIndex++], &buffer[2 * offset + 1]);
708    // don't need to create last degenerate tri
709
710    DEBUG_DUMP_ALPHA_BUFFER();
711}
712
713void PathTessellator::tessellatePath(const SkPath &path, const SkPaint* paint,
714        const mat4 *transform, VertexBuffer& vertexBuffer) {
715    ATRACE_CALL();
716
717    const PaintInfo paintInfo(paint, transform);
718
719    Vector<Vertex> tempVertices;
720    float threshInvScaleX = paintInfo.inverseScaleX;
721    float threshInvScaleY = paintInfo.inverseScaleY;
722    if (paintInfo.style == SkPaint::kStroke_Style) {
723        // alter the bezier recursion threshold values we calculate in order to compensate for
724        // expansion done after the path vertices are found
725        SkRect bounds = path.getBounds();
726        if (!bounds.isEmpty()) {
727            threshInvScaleX *= bounds.width() / (bounds.width() + paint->getStrokeWidth());
728            threshInvScaleY *= bounds.height() / (bounds.height() + paint->getStrokeWidth());
729        }
730    }
731
732    // force close if we're filling the path, since fill path expects closed perimeter.
733    bool forceClose = paintInfo.style != SkPaint::kStroke_Style;
734    bool wasClosed = approximatePathOutlineVertices(path, forceClose,
735            threshInvScaleX * threshInvScaleX, threshInvScaleY * threshInvScaleY, tempVertices);
736
737    if (!tempVertices.size()) {
738        // path was empty, return without allocating vertex buffer
739        return;
740    }
741
742#if VERTEX_DEBUG
743    for (unsigned int i = 0; i < tempVertices.size(); i++) {
744        ALOGD("orig path: point at %f %f",
745                tempVertices[i].position[0], tempVertices[i].position[1]);
746    }
747#endif
748
749    if (paintInfo.style == SkPaint::kStroke_Style) {
750        if (!paintInfo.isAA) {
751            if (wasClosed) {
752                getStrokeVerticesFromPerimeter(paintInfo, tempVertices, vertexBuffer);
753            } else {
754                getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer);
755            }
756
757        } else {
758            if (wasClosed) {
759                getStrokeVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer);
760            } else {
761                getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer);
762            }
763        }
764    } else {
765        // For kStrokeAndFill style, the path should be adjusted externally.
766        // It will be treated as a fill here.
767        if (!paintInfo.isAA) {
768            getFillVerticesFromPerimeter(tempVertices, vertexBuffer);
769        } else {
770            getFillVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer);
771        }
772    }
773}
774
775static void expandRectToCoverVertex(SkRect& rect, const Vertex& vertex) {
776    rect.fLeft = fminf(rect.fLeft, vertex.position[0]);
777    rect.fTop = fminf(rect.fTop, vertex.position[1]);
778    rect.fRight = fmaxf(rect.fRight, vertex.position[0]);
779    rect.fBottom = fmaxf(rect.fBottom, vertex.position[1]);
780}
781
782void PathTessellator::tessellateLines(const float* points, int count, SkPaint* paint,
783        const mat4* transform, SkRect& bounds, VertexBuffer& vertexBuffer) {
784    ATRACE_CALL();
785    const PaintInfo paintInfo(paint, transform);
786
787    const int extra = paintInfo.capExtraDivisions();
788    int numLines = count / 4;
789    int lineAllocSize;
790    // pre-allocate space for lines in the buffer, and degenerate tris in between
791    if (paintInfo.isAA) {
792        lineAllocSize = 6 * (2) + 2 + 6 * extra;
793        vertexBuffer.alloc<AlphaVertex>(numLines * lineAllocSize + (numLines - 1) * 2);
794    } else {
795        lineAllocSize = 2 * ((2) + extra);
796        vertexBuffer.alloc<Vertex>(numLines * lineAllocSize + (numLines - 1) * 2);
797    }
798
799    Vector<Vertex> tempVertices;
800    tempVertices.push();
801    tempVertices.push();
802    Vertex* tempVerticesData = tempVertices.editArray();
803    bounds.set(points[0], points[1], points[0], points[1]);
804    for (int i = 0; i < count; i += 4) {
805        Vertex::set(&(tempVerticesData[0]), points[i + 0], points[i + 1]);
806        Vertex::set(&(tempVerticesData[1]), points[i + 2], points[i + 3]);
807
808        if (paintInfo.isAA) {
809            getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer);
810        } else {
811            getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer);
812        }
813
814        // calculate bounds
815        expandRectToCoverVertex(bounds, tempVerticesData[0]);
816        expandRectToCoverVertex(bounds, tempVerticesData[1]);
817    }
818
819    expandBoundsForStroke(bounds, paint, true); // force-expand bounds to incorporate stroke
820
821    // since multiple objects tessellated into buffer, separate them with degen tris
822    if (paintInfo.isAA) {
823        vertexBuffer.createDegenerateSeparators<AlphaVertex>(lineAllocSize);
824    } else {
825        vertexBuffer.createDegenerateSeparators<Vertex>(lineAllocSize);
826    }
827}
828
829///////////////////////////////////////////////////////////////////////////////
830// Simple path line approximation
831///////////////////////////////////////////////////////////////////////////////
832
833void pushToVector(Vector<Vertex>& vertices, float x, float y) {
834    // TODO: make this not yuck
835    vertices.push();
836    Vertex* newVertex = &(vertices.editArray()[vertices.size() - 1]);
837    Vertex::set(newVertex, x, y);
838}
839
840bool PathTessellator::approximatePathOutlineVertices(const SkPath& path, bool forceClose,
841        float sqrInvScaleX, float sqrInvScaleY, Vector<Vertex>& outputVertices) {
842    ATRACE_CALL();
843
844    // TODO: to support joins other than sharp miter, join vertices should be labelled in the
845    // perimeter, or resolved into more vertices. Reconsider forceClose-ing in that case.
846    SkPath::Iter iter(path, forceClose);
847    SkPoint pts[4];
848    SkPath::Verb v;
849    while (SkPath::kDone_Verb != (v = iter.next(pts))) {
850            switch (v) {
851            case SkPath::kMove_Verb:
852                pushToVector(outputVertices, pts[0].x(), pts[0].y());
853                ALOGV("Move to pos %f %f", pts[0].x(), pts[0].y());
854                break;
855            case SkPath::kClose_Verb:
856                ALOGV("Close at pos %f %f", pts[0].x(), pts[0].y());
857                break;
858            case SkPath::kLine_Verb:
859                ALOGV("kLine_Verb %f %f -> %f %f", pts[0].x(), pts[0].y(), pts[1].x(), pts[1].y());
860                pushToVector(outputVertices, pts[1].x(), pts[1].y());
861                break;
862            case SkPath::kQuad_Verb:
863                ALOGV("kQuad_Verb");
864                recursiveQuadraticBezierVertices(
865                        pts[0].x(), pts[0].y(),
866                        pts[2].x(), pts[2].y(),
867                        pts[1].x(), pts[1].y(),
868                        sqrInvScaleX, sqrInvScaleY, outputVertices);
869                break;
870            case SkPath::kCubic_Verb:
871                ALOGV("kCubic_Verb");
872                recursiveCubicBezierVertices(
873                        pts[0].x(), pts[0].y(),
874                        pts[1].x(), pts[1].y(),
875                        pts[3].x(), pts[3].y(),
876                        pts[2].x(), pts[2].y(),
877                        sqrInvScaleX, sqrInvScaleY, outputVertices);
878                break;
879            default:
880                break;
881            }
882    }
883
884    int size = outputVertices.size();
885    if (size >= 2 && outputVertices[0].position[0] == outputVertices[size - 1].position[0] &&
886            outputVertices[0].position[1] == outputVertices[size - 1].position[1]) {
887        outputVertices.pop();
888        return true;
889    }
890    return false;
891}
892
893///////////////////////////////////////////////////////////////////////////////
894// Bezier approximation
895///////////////////////////////////////////////////////////////////////////////
896
897void PathTessellator::recursiveCubicBezierVertices(
898        float p1x, float p1y, float c1x, float c1y,
899        float p2x, float p2y, float c2x, float c2y,
900        float sqrInvScaleX, float sqrInvScaleY, Vector<Vertex>& outputVertices) {
901    float dx = p2x - p1x;
902    float dy = p2y - p1y;
903    float d1 = fabs((c1x - p2x) * dy - (c1y - p2y) * dx);
904    float d2 = fabs((c2x - p2x) * dy - (c2y - p2y) * dx);
905    float d = d1 + d2;
906
907    // multiplying by sqrInvScaleY/X equivalent to multiplying in dimensional scale factors
908
909    if (d * d < THRESHOLD * THRESHOLD * (dx * dx * sqrInvScaleY + dy * dy * sqrInvScaleX)) {
910        // below thresh, draw line by adding endpoint
911        pushToVector(outputVertices, p2x, p2y);
912    } else {
913        float p1c1x = (p1x + c1x) * 0.5f;
914        float p1c1y = (p1y + c1y) * 0.5f;
915        float p2c2x = (p2x + c2x) * 0.5f;
916        float p2c2y = (p2y + c2y) * 0.5f;
917
918        float c1c2x = (c1x + c2x) * 0.5f;
919        float c1c2y = (c1y + c2y) * 0.5f;
920
921        float p1c1c2x = (p1c1x + c1c2x) * 0.5f;
922        float p1c1c2y = (p1c1y + c1c2y) * 0.5f;
923
924        float p2c1c2x = (p2c2x + c1c2x) * 0.5f;
925        float p2c1c2y = (p2c2y + c1c2y) * 0.5f;
926
927        float mx = (p1c1c2x + p2c1c2x) * 0.5f;
928        float my = (p1c1c2y + p2c1c2y) * 0.5f;
929
930        recursiveCubicBezierVertices(
931                p1x, p1y, p1c1x, p1c1y,
932                mx, my, p1c1c2x, p1c1c2y,
933                sqrInvScaleX, sqrInvScaleY, outputVertices);
934        recursiveCubicBezierVertices(
935                mx, my, p2c1c2x, p2c1c2y,
936                p2x, p2y, p2c2x, p2c2y,
937                sqrInvScaleX, sqrInvScaleY, outputVertices);
938    }
939}
940
941void PathTessellator::recursiveQuadraticBezierVertices(
942        float ax, float ay,
943        float bx, float by,
944        float cx, float cy,
945        float sqrInvScaleX, float sqrInvScaleY, Vector<Vertex>& outputVertices) {
946    float dx = bx - ax;
947    float dy = by - ay;
948    float d = (cx - bx) * dy - (cy - by) * dx;
949
950    if (d * d < THRESHOLD * THRESHOLD * (dx * dx * sqrInvScaleY + dy * dy * sqrInvScaleX)) {
951        // below thresh, draw line by adding endpoint
952        pushToVector(outputVertices, bx, by);
953    } else {
954        float acx = (ax + cx) * 0.5f;
955        float bcx = (bx + cx) * 0.5f;
956        float acy = (ay + cy) * 0.5f;
957        float bcy = (by + cy) * 0.5f;
958
959        // midpoint
960        float mx = (acx + bcx) * 0.5f;
961        float my = (acy + bcy) * 0.5f;
962
963        recursiveQuadraticBezierVertices(ax, ay, mx, my, acx, acy,
964                sqrInvScaleX, sqrInvScaleY, outputVertices);
965        recursiveQuadraticBezierVertices(mx, my, bx, by, bcx, bcy,
966                sqrInvScaleX, sqrInvScaleY, outputVertices);
967    }
968}
969
970}; // namespace uirenderer
971}; // namespace android
972