1/*
2 * Copyright 2012 The Android Open Source Project
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#define LOG_TAG "PathRenderer"
9#define LOG_NDEBUG 1
10#define ATRACE_TAG ATRACE_TAG_GRAPHICS
11
12#define VERTEX_DEBUG 0
13
14#include <SkPath.h>
15#include <SkStrokeRec.h>
16
17#include <stdlib.h>
18#include <stdint.h>
19#include <sys/types.h>
20
21#include <SkTypes.h>
22#include <SkTraceEvent.h>
23#include <SkMatrix.h>
24#include <SkPoint.h>
25
26#ifdef VERBOSE
27#define ALOGV SkDebugf
28#else
29#define ALOGV(x, ...)
30#endif
31
32#include "AndroidPathRenderer.h"
33#include "Vertex.h"
34
35namespace android {
36namespace uirenderer {
37
38#define THRESHOLD 0.5f
39
40SkRect PathRenderer::ComputePathBounds(const SkPath& path, const SkPaint* paint) {
41    SkRect bounds = path.getBounds();
42    if (paint->getStyle() != SkPaint::kFill_Style) {
43        float outset = paint->getStrokeWidth() * 0.5f;
44        bounds.outset(outset, outset);
45    }
46    return bounds;
47}
48
49inline void computeInverseScales(const SkMatrix* transform, float &inverseScaleX, float& inverseScaleY) {
50    if (transform && transform->getType() & (SkMatrix::kScale_Mask|SkMatrix::kAffine_Mask|SkMatrix::kPerspective_Mask)) {
51        float m00 = transform->getScaleX();
52        float m01 = transform->getSkewY();
53        float m10 = transform->getSkewX();
54        float m11 = transform->getScaleY();
55        float scaleX = sk_float_sqrt(m00 * m00 + m01 * m01);
56        float scaleY = sk_float_sqrt(m10 * m10 + m11 * m11);
57        inverseScaleX = (scaleX != 0) ? (1.0f / scaleX) : 1.0f;
58        inverseScaleY = (scaleY != 0) ? (1.0f / scaleY) : 1.0f;
59    } else {
60        inverseScaleX = 1.0f;
61        inverseScaleY = 1.0f;
62    }
63}
64
65inline void copyVertex(Vertex* destPtr, const Vertex* srcPtr) {
66    Vertex::set(destPtr, srcPtr->position[0], srcPtr->position[1]);
67}
68
69inline void copyAlphaVertex(AlphaVertex* destPtr, const AlphaVertex* srcPtr) {
70    AlphaVertex::set(destPtr, srcPtr->position[0], srcPtr->position[1], srcPtr->alpha);
71}
72
73/**
74 * Produces a pseudo-normal for a vertex, given the normals of the two incoming lines. If the offset
75 * from each vertex in a perimeter is calculated, the resultant lines connecting the offset vertices
76 * will be offset by 1.0
77 *
78 * Note that we can't add and normalize the two vectors, that would result in a rectangle having an
79 * offset of (sqrt(2)/2, sqrt(2)/2) at each corner, instead of (1, 1)
80 *
81 * NOTE: assumes angles between normals 90 degrees or less
82 */
83inline SkVector totalOffsetFromNormals(const SkVector& normalA, const SkVector& normalB) {
84    SkVector pseudoNormal = normalA + normalB;
85    pseudoNormal.scale(1.0f / (1.0f + sk_float_abs(normalA.dot(normalB))));
86    return pseudoNormal;
87}
88
89inline void scaleOffsetForStrokeWidth(SkVector& offset, float halfStrokeWidth,
90        float inverseScaleX, float inverseScaleY) {
91    if (halfStrokeWidth == 0.0f) {
92        // hairline - compensate for scale
93        offset.fX *= 0.5f * inverseScaleX;
94        offset.fY *= 0.5f * inverseScaleY;
95    } else {
96        offset.scale(halfStrokeWidth);
97    }
98}
99
100static void getFillVerticesFromPerimeter(const SkTArray<Vertex, true>& perimeter, VertexBuffer* vertexBuffer) {
101    Vertex* buffer = vertexBuffer->alloc<Vertex>(perimeter.count());
102
103    int currentIndex = 0;
104    // zig zag between all previous points on the inside of the hull to create a
105    // triangle strip that fills the hull
106    int srcAindex = 0;
107    int srcBindex = perimeter.count() - 1;
108    while (srcAindex <= srcBindex) {
109        copyVertex(&buffer[currentIndex++], &perimeter[srcAindex]);
110        if (srcAindex == srcBindex) break;
111        copyVertex(&buffer[currentIndex++], &perimeter[srcBindex]);
112        srcAindex++;
113        srcBindex--;
114    }
115}
116
117static void getStrokeVerticesFromPerimeter(const SkTArray<Vertex, true>& perimeter, float halfStrokeWidth,
118        VertexBuffer* vertexBuffer, float inverseScaleX, float inverseScaleY) {
119    Vertex* buffer = vertexBuffer->alloc<Vertex>(perimeter.count() * 2 + 2);
120
121    int currentIndex = 0;
122    const Vertex* last = &(perimeter[perimeter.count() - 1]);
123    const Vertex* current = &(perimeter[0]);
124    SkVector lastNormal;
125    lastNormal.set(current->position[1] - last->position[1],
126                   last->position[0] - current->position[0]);
127    lastNormal.normalize();
128    for (int i = 0; i < perimeter.count(); i++) {
129        const Vertex* next = &(perimeter[i + 1 >= perimeter.count() ? 0 : i + 1]);
130        SkVector nextNormal;
131        nextNormal.set(next->position[1] - current->position[1],
132                       current->position[0] - next->position[0]);
133        nextNormal.normalize();
134
135        SkVector totalOffset = totalOffsetFromNormals(lastNormal, nextNormal);
136        scaleOffsetForStrokeWidth(totalOffset, halfStrokeWidth, inverseScaleX, inverseScaleY);
137
138        Vertex::set(&buffer[currentIndex++],
139                current->position[0] + totalOffset.fX,
140                current->position[1] + totalOffset.fY);
141
142        Vertex::set(&buffer[currentIndex++],
143                current->position[0] - totalOffset.fX,
144                current->position[1] - totalOffset.fY);
145
146        last = current;
147        current = next;
148        lastNormal = nextNormal;
149    }
150
151    // wrap around to beginning
152    copyVertex(&buffer[currentIndex++], &buffer[0]);
153    copyVertex(&buffer[currentIndex++], &buffer[1]);
154}
155
156static void getStrokeVerticesFromUnclosedVertices(const SkTArray<Vertex, true>& vertices, float halfStrokeWidth,
157        VertexBuffer* vertexBuffer, float inverseScaleX, float inverseScaleY) {
158    Vertex* buffer = vertexBuffer->alloc<Vertex>(vertices.count() * 2);
159
160    int currentIndex = 0;
161    const Vertex* current = &(vertices[0]);
162    SkVector lastNormal;
163    for (int i = 0; i < vertices.count() - 1; i++) {
164        const Vertex* next = &(vertices[i + 1]);
165        SkVector nextNormal;
166        nextNormal.set(next->position[1] - current->position[1],
167                       current->position[0] - next->position[0]);
168        nextNormal.normalize();
169
170        SkVector totalOffset;
171        if (i == 0) {
172            totalOffset = nextNormal;
173        } else {
174            totalOffset = totalOffsetFromNormals(lastNormal, nextNormal);
175        }
176        scaleOffsetForStrokeWidth(totalOffset, halfStrokeWidth, inverseScaleX, inverseScaleY);
177
178        Vertex::set(&buffer[currentIndex++],
179                current->position[0] + totalOffset.fX,
180                current->position[1] + totalOffset.fY);
181
182        Vertex::set(&buffer[currentIndex++],
183                current->position[0] - totalOffset.fX,
184                current->position[1] - totalOffset.fY);
185
186        current = next;
187        lastNormal = nextNormal;
188    }
189
190    SkVector totalOffset = lastNormal;
191    scaleOffsetForStrokeWidth(totalOffset, halfStrokeWidth, inverseScaleX, inverseScaleY);
192
193    Vertex::set(&buffer[currentIndex++],
194            current->position[0] + totalOffset.fX,
195            current->position[1] + totalOffset.fY);
196    Vertex::set(&buffer[currentIndex++],
197            current->position[0] - totalOffset.fX,
198            current->position[1] - totalOffset.fY);
199#if VERTEX_DEBUG
200    for (unsigned int i = 0; i < vertexBuffer.getSize(); i++) {
201        SkDebugf("point at %f %f", buffer[i].position[0], buffer[i].position[1]);
202    }
203#endif
204}
205
206static void getFillVerticesFromPerimeterAA(const SkTArray<Vertex, true>& perimeter, VertexBuffer* vertexBuffer,
207         float inverseScaleX, float inverseScaleY) {
208    AlphaVertex* buffer = vertexBuffer->alloc<AlphaVertex>(perimeter.count() * 3 + 2);
209
210    // generate alpha points - fill Alpha vertex gaps in between each point with
211    // alpha 0 vertex, offset by a scaled normal.
212    int currentIndex = 0;
213    const Vertex* last = &(perimeter[perimeter.count() - 1]);
214    const Vertex* current = &(perimeter[0]);
215    SkVector lastNormal;
216    lastNormal.set(current->position[1] - last->position[1],
217                   last->position[0] - current->position[0]);
218    lastNormal.normalize();
219    for (int i = 0; i < perimeter.count(); i++) {
220        const Vertex* next = &(perimeter[i + 1 >= perimeter.count() ? 0 : i + 1]);
221        SkVector nextNormal;
222        nextNormal.set(next->position[1] - current->position[1],
223                       current->position[0] - next->position[0]);
224        nextNormal.normalize();
225
226        // AA point offset from original point is that point's normal, such that each side is offset
227        // by .5 pixels
228        SkVector totalOffset = totalOffsetFromNormals(lastNormal, nextNormal);
229        totalOffset.fX *= 0.5f * inverseScaleX;
230        totalOffset.fY *= 0.5f * inverseScaleY;
231
232        AlphaVertex::set(&buffer[currentIndex++],
233                current->position[0] + totalOffset.fX,
234                current->position[1] + totalOffset.fY,
235                0.0f);
236        AlphaVertex::set(&buffer[currentIndex++],
237                current->position[0] - totalOffset.fX,
238                current->position[1] - totalOffset.fY,
239                1.0f);
240
241        last = current;
242        current = next;
243        lastNormal = nextNormal;
244    }
245
246    // wrap around to beginning
247    copyAlphaVertex(&buffer[currentIndex++], &buffer[0]);
248    copyAlphaVertex(&buffer[currentIndex++], &buffer[1]);
249
250    // zig zag between all previous points on the inside of the hull to create a
251    // triangle strip that fills the hull, repeating the first inner point to
252    // create degenerate tris to start inside path
253    int srcAindex = 0;
254    int srcBindex = perimeter.count() - 1;
255    while (srcAindex <= srcBindex) {
256        copyAlphaVertex(&buffer[currentIndex++], &buffer[srcAindex * 2 + 1]);
257        if (srcAindex == srcBindex) break;
258        copyAlphaVertex(&buffer[currentIndex++], &buffer[srcBindex * 2 + 1]);
259        srcAindex++;
260        srcBindex--;
261    }
262
263#if VERTEX_DEBUG
264    for (unsigned int i = 0; i < vertexBuffer.getSize(); i++) {
265        SkDebugf("point at %f %f, alpha %f", buffer[i].position[0], buffer[i].position[1], buffer[i].alpha);
266    }
267#endif
268}
269
270
271static void getStrokeVerticesFromUnclosedVerticesAA(const SkTArray<Vertex, true>& vertices, float halfStrokeWidth,
272        VertexBuffer* vertexBuffer, float inverseScaleX, float inverseScaleY) {
273    AlphaVertex* buffer = vertexBuffer->alloc<AlphaVertex>(6 * vertices.count() + 2);
274
275    // avoid lines smaller than hairline since they break triangle based sampling. instead reducing
276    // alpha value (TODO: support different X/Y scale)
277    float maxAlpha = 1.0f;
278    if (halfStrokeWidth != 0 && inverseScaleX == inverseScaleY &&
279            halfStrokeWidth * inverseScaleX < 0.5f) {
280        maxAlpha *= (2 * halfStrokeWidth) / inverseScaleX;
281        halfStrokeWidth = 0.0f;
282    }
283
284    // there is no outer/inner here, using them for consistency with below approach
285    int offset = 2 * (vertices.count() - 2);
286    int currentAAOuterIndex = 2;
287    int currentAAInnerIndex = 2 * offset + 5; // reversed
288    int currentStrokeIndex = currentAAInnerIndex + 7;
289
290    const Vertex* last = &(vertices[0]);
291    const Vertex* current = &(vertices[1]);
292    SkVector lastNormal;
293    lastNormal.set(current->position[1] - last->position[1],
294                   last->position[0] - current->position[0]);
295    lastNormal.normalize();
296
297    {
298        // start cap
299        SkVector totalOffset = lastNormal;
300        SkVector AAOffset = totalOffset;
301        AAOffset.fX *= 0.5f * inverseScaleX;
302        AAOffset.fY *= 0.5f * inverseScaleY;
303
304        SkVector innerOffset = totalOffset;
305        scaleOffsetForStrokeWidth(innerOffset, halfStrokeWidth, inverseScaleX, inverseScaleY);
306        SkVector outerOffset = innerOffset + AAOffset;
307        innerOffset -= AAOffset;
308
309        // TODO: support square cap by changing this offset to incorporate halfStrokeWidth
310        SkVector capAAOffset;
311        capAAOffset.set(AAOffset.fY, -AAOffset.fX);
312        AlphaVertex::set(&buffer[0],
313                last->position[0] + outerOffset.fX + capAAOffset.fX,
314                last->position[1] + outerOffset.fY + capAAOffset.fY,
315                0.0f);
316        AlphaVertex::set(&buffer[1],
317                last->position[0] + innerOffset.fX - capAAOffset.fX,
318                last->position[1] + innerOffset.fY - capAAOffset.fY,
319                maxAlpha);
320
321        AlphaVertex::set(&buffer[2 * offset + 6],
322                last->position[0] - outerOffset.fX + capAAOffset.fX,
323                last->position[1] - outerOffset.fY + capAAOffset.fY,
324                0.0f);
325        AlphaVertex::set(&buffer[2 * offset + 7],
326                last->position[0] - innerOffset.fX - capAAOffset.fX,
327                last->position[1] - innerOffset.fY - capAAOffset.fY,
328                maxAlpha);
329        copyAlphaVertex(&buffer[2 * offset + 8], &buffer[0]);
330        copyAlphaVertex(&buffer[2 * offset + 9], &buffer[1]);
331        copyAlphaVertex(&buffer[2 * offset + 10], &buffer[1]); // degenerate tris (the only two!)
332        copyAlphaVertex(&buffer[2 * offset + 11], &buffer[2 * offset + 7]);
333    }
334
335    for (int i = 1; i < vertices.count() - 1; i++) {
336        const Vertex* next = &(vertices[i + 1]);
337        SkVector nextNormal;
338        nextNormal.set(next->position[1] - current->position[1],
339                       current->position[0] - next->position[0]);
340        nextNormal.normalize();
341
342        SkVector totalOffset = totalOffsetFromNormals(lastNormal, nextNormal);
343        SkVector AAOffset = totalOffset;
344        AAOffset.fX *= 0.5f * inverseScaleX;
345        AAOffset.fY *= 0.5f * inverseScaleY;
346
347        SkVector innerOffset = totalOffset;
348        scaleOffsetForStrokeWidth(innerOffset, halfStrokeWidth, inverseScaleX, inverseScaleY);
349        SkVector outerOffset = innerOffset + AAOffset;
350        innerOffset -= AAOffset;
351
352        AlphaVertex::set(&buffer[currentAAOuterIndex++],
353                current->position[0] + outerOffset.fX,
354                current->position[1] + outerOffset.fY,
355                0.0f);
356        AlphaVertex::set(&buffer[currentAAOuterIndex++],
357                current->position[0] + innerOffset.fX,
358                current->position[1] + innerOffset.fY,
359                maxAlpha);
360
361        AlphaVertex::set(&buffer[currentStrokeIndex++],
362                current->position[0] + innerOffset.fX,
363                current->position[1] + innerOffset.fY,
364                maxAlpha);
365        AlphaVertex::set(&buffer[currentStrokeIndex++],
366                current->position[0] - innerOffset.fX,
367                current->position[1] - innerOffset.fY,
368                maxAlpha);
369
370        AlphaVertex::set(&buffer[currentAAInnerIndex--],
371                current->position[0] - innerOffset.fX,
372                current->position[1] - innerOffset.fY,
373                maxAlpha);
374        AlphaVertex::set(&buffer[currentAAInnerIndex--],
375                current->position[0] - outerOffset.fX,
376                current->position[1] - outerOffset.fY,
377                0.0f);
378
379        last = current;
380        current = next;
381        lastNormal = nextNormal;
382    }
383
384    {
385        // end cap
386        SkVector totalOffset = lastNormal;
387        SkVector AAOffset = totalOffset;
388        AAOffset.fX *= 0.5f * inverseScaleX;
389        AAOffset.fY *= 0.5f * inverseScaleY;
390
391        SkVector innerOffset = totalOffset;
392        scaleOffsetForStrokeWidth(innerOffset, halfStrokeWidth, inverseScaleX, inverseScaleY);
393        SkVector outerOffset = innerOffset + AAOffset;
394        innerOffset -= AAOffset;
395
396        // TODO: support square cap by changing this offset to incorporate halfStrokeWidth
397        SkVector capAAOffset;
398        capAAOffset.set(-AAOffset.fY, AAOffset.fX);
399
400        AlphaVertex::set(&buffer[offset + 2],
401                current->position[0] + outerOffset.fX + capAAOffset.fX,
402                current->position[1] + outerOffset.fY + capAAOffset.fY,
403                0.0f);
404        AlphaVertex::set(&buffer[offset + 3],
405                current->position[0] + innerOffset.fX - capAAOffset.fX,
406                current->position[1] + innerOffset.fY - capAAOffset.fY,
407                maxAlpha);
408
409        AlphaVertex::set(&buffer[offset + 4],
410                current->position[0] - outerOffset.fX + capAAOffset.fX,
411                current->position[1] - outerOffset.fY + capAAOffset.fY,
412                0.0f);
413        AlphaVertex::set(&buffer[offset + 5],
414                current->position[0] - innerOffset.fX - capAAOffset.fX,
415                current->position[1] - innerOffset.fY - capAAOffset.fY,
416                maxAlpha);
417
418        copyAlphaVertex(&buffer[vertexBuffer->getSize() - 2], &buffer[offset + 3]);
419        copyAlphaVertex(&buffer[vertexBuffer->getSize() - 1], &buffer[offset + 5]);
420    }
421
422#if VERTEX_DEBUG
423    for (unsigned int i = 0; i < vertexBuffer.getSize(); i++) {
424        SkDebugf("point at %f %f, alpha %f", buffer[i].position[0], buffer[i].position[1], buffer[i].alpha);
425    }
426#endif
427}
428
429
430static void getStrokeVerticesFromPerimeterAA(const SkTArray<Vertex, true>& perimeter, float halfStrokeWidth,
431        VertexBuffer* vertexBuffer, float inverseScaleX, float inverseScaleY) {
432    AlphaVertex* buffer = vertexBuffer->alloc<AlphaVertex>(6 * perimeter.count() + 8);
433
434    // avoid lines smaller than hairline since they break triangle based sampling. instead reducing
435    // alpha value (TODO: support different X/Y scale)
436    float maxAlpha = 1.0f;
437    if (halfStrokeWidth != 0 && inverseScaleX == inverseScaleY &&
438            halfStrokeWidth * inverseScaleX < 0.5f) {
439        maxAlpha *= (2 * halfStrokeWidth) / inverseScaleX;
440        halfStrokeWidth = 0.0f;
441    }
442
443    int offset = 2 * perimeter.count() + 3;
444    int currentAAOuterIndex = 0;
445    int currentStrokeIndex = offset;
446    int currentAAInnerIndex = offset * 2;
447
448    const Vertex* last = &(perimeter[perimeter.count() - 1]);
449    const Vertex* current = &(perimeter[0]);
450    SkVector lastNormal;
451    lastNormal.set(current->position[1] - last->position[1],
452                   last->position[0] - current->position[0]);
453    lastNormal.normalize();
454    for (int i = 0; i < perimeter.count(); i++) {
455        const Vertex* next = &(perimeter[i + 1 >= perimeter.count() ? 0 : i + 1]);
456        SkVector nextNormal;
457        nextNormal.set(next->position[1] - current->position[1],
458                       current->position[0] - next->position[0]);
459        nextNormal.normalize();
460
461        SkVector totalOffset = totalOffsetFromNormals(lastNormal, nextNormal);
462        SkVector AAOffset = totalOffset;
463        AAOffset.fX *= 0.5f * inverseScaleX;
464        AAOffset.fY *= 0.5f * inverseScaleY;
465
466        SkVector innerOffset = totalOffset;
467        scaleOffsetForStrokeWidth(innerOffset, halfStrokeWidth, inverseScaleX, inverseScaleY);
468        SkVector outerOffset = innerOffset + AAOffset;
469        innerOffset -= AAOffset;
470
471        AlphaVertex::set(&buffer[currentAAOuterIndex++],
472                current->position[0] + outerOffset.fX,
473                current->position[1] + outerOffset.fY,
474                0.0f);
475        AlphaVertex::set(&buffer[currentAAOuterIndex++],
476                current->position[0] + innerOffset.fX,
477                current->position[1] + innerOffset.fY,
478                maxAlpha);
479
480        AlphaVertex::set(&buffer[currentStrokeIndex++],
481                current->position[0] + innerOffset.fX,
482                current->position[1] + innerOffset.fY,
483                maxAlpha);
484        AlphaVertex::set(&buffer[currentStrokeIndex++],
485                current->position[0] - innerOffset.fX,
486                current->position[1] - innerOffset.fY,
487                maxAlpha);
488
489        AlphaVertex::set(&buffer[currentAAInnerIndex++],
490                current->position[0] - innerOffset.fX,
491                current->position[1] - innerOffset.fY,
492                maxAlpha);
493        AlphaVertex::set(&buffer[currentAAInnerIndex++],
494                current->position[0] - outerOffset.fX,
495                current->position[1] - outerOffset.fY,
496                0.0f);
497
498        last = current;
499        current = next;
500        lastNormal = nextNormal;
501    }
502
503    // wrap each strip around to beginning, creating degenerate tris to bridge strips
504    copyAlphaVertex(&buffer[currentAAOuterIndex++], &buffer[0]);
505    copyAlphaVertex(&buffer[currentAAOuterIndex++], &buffer[1]);
506    copyAlphaVertex(&buffer[currentAAOuterIndex++], &buffer[1]);
507
508    copyAlphaVertex(&buffer[currentStrokeIndex++], &buffer[offset]);
509    copyAlphaVertex(&buffer[currentStrokeIndex++], &buffer[offset + 1]);
510    copyAlphaVertex(&buffer[currentStrokeIndex++], &buffer[offset + 1]);
511
512    copyAlphaVertex(&buffer[currentAAInnerIndex++], &buffer[2 * offset]);
513    copyAlphaVertex(&buffer[currentAAInnerIndex++], &buffer[2 * offset + 1]);
514    // don't need to create last degenerate tri
515
516#if VERTEX_DEBUG
517    for (unsigned int i = 0; i < vertexBuffer.getSize(); i++) {
518        SkDebugf("point at %f %f, alpha %f", buffer[i].position[0], buffer[i].position[1], buffer[i].alpha);
519    }
520#endif
521}
522
523void PathRenderer::ConvexPathVertices(const SkPath &path, const SkStrokeRec& stroke, bool isAA,
524        const SkMatrix* transform, VertexBuffer* vertexBuffer) {
525
526    SkStrokeRec::Style style = stroke.getStyle();
527
528    float inverseScaleX, inverseScaleY;
529    computeInverseScales(transform, inverseScaleX, inverseScaleY);
530
531    SkTArray<Vertex, true> tempVertices;
532    float threshInvScaleX = inverseScaleX;
533    float threshInvScaleY = inverseScaleY;
534    if (style == SkStrokeRec::kStroke_Style) {
535        // alter the bezier recursion threshold values we calculate in order to compensate for
536        // expansion done after the path vertices are found
537        SkRect bounds = path.getBounds();
538        if (!bounds.isEmpty()) {
539            threshInvScaleX *= bounds.width() / (bounds.width() + stroke.getWidth());
540            threshInvScaleY *= bounds.height() / (bounds.height() + stroke.getWidth());
541        }
542    }
543
544    // force close if we're filling the path, since fill path expects closed perimeter.
545    bool forceClose = style != SkStrokeRec::kStroke_Style;
546    bool wasClosed = ConvexPathPerimeterVertices(path, forceClose, threshInvScaleX * threshInvScaleX,
547            threshInvScaleY * threshInvScaleY, &tempVertices);
548
549    if (!tempVertices.count()) {
550        // path was empty, return without allocating vertex buffer
551        return;
552    }
553
554#if VERTEX_DEBUG
555    for (unsigned int i = 0; i < tempVertices.count(); i++) {
556        SkDebugf("orig path: point at %f %f", tempVertices[i].position[0], tempVertices[i].position[1]);
557    }
558#endif
559
560    if (style == SkStrokeRec::kStroke_Style) {
561        float halfStrokeWidth = stroke.getWidth() * 0.5f;
562        if (!isAA) {
563            if (wasClosed) {
564                getStrokeVerticesFromPerimeter(tempVertices, halfStrokeWidth, vertexBuffer,
565                        inverseScaleX, inverseScaleY);
566            } else {
567                getStrokeVerticesFromUnclosedVertices(tempVertices, halfStrokeWidth, vertexBuffer,
568                        inverseScaleX, inverseScaleY);
569            }
570
571        } else {
572            if (wasClosed) {
573                getStrokeVerticesFromPerimeterAA(tempVertices, halfStrokeWidth, vertexBuffer,
574                        inverseScaleX, inverseScaleY);
575            } else {
576                getStrokeVerticesFromUnclosedVerticesAA(tempVertices, halfStrokeWidth, vertexBuffer,
577                        inverseScaleX, inverseScaleY);
578            }
579        }
580    } else {
581        // For kStrokeAndFill style, the path should be adjusted externally, as it will be treated as a fill here.
582        if (!isAA) {
583            getFillVerticesFromPerimeter(tempVertices, vertexBuffer);
584        } else {
585            getFillVerticesFromPerimeterAA(tempVertices, vertexBuffer, inverseScaleX, inverseScaleY);
586        }
587    }
588}
589
590
591static void pushToVector(SkTArray<Vertex, true>* vertices, float x, float y) {
592    // TODO: make this not yuck
593    vertices->push_back();
594    Vertex* newVertex = &((*vertices)[vertices->count() - 1]);
595    Vertex::set(newVertex, x, y);
596}
597
598bool PathRenderer::ConvexPathPerimeterVertices(const SkPath& path, bool forceClose,
599        float sqrInvScaleX, float sqrInvScaleY, SkTArray<Vertex, true>* outputVertices) {
600
601
602    // TODO: to support joins other than sharp miter, join vertices should be labelled in the
603    // perimeter, or resolved into more vertices. Reconsider forceClose-ing in that case.
604    SkPath::Iter iter(path, forceClose);
605    SkPoint pts[4];
606    SkPath::Verb v;
607
608    while (SkPath::kDone_Verb != (v = iter.next(pts))) {
609            switch (v) {
610                case SkPath::kMove_Verb:
611                    pushToVector(outputVertices, pts[0].x(), pts[0].y());
612                    ALOGV("Move to pos %f %f", pts[0].x(), pts[0].y());
613                    break;
614                case SkPath::kClose_Verb:
615                    ALOGV("Close at pos %f %f", pts[0].x(), pts[0].y());
616                    break;
617                case SkPath::kLine_Verb:
618                    ALOGV("kLine_Verb %f %f -> %f %f",
619                            pts[0].x(), pts[0].y(),
620                            pts[1].x(), pts[1].y());
621
622                    pushToVector(outputVertices, pts[1].x(), pts[1].y());
623                    break;
624                case SkPath::kQuad_Verb:
625                    ALOGV("kQuad_Verb");
626                    RecursiveQuadraticBezierVertices(
627                            pts[0].x(), pts[0].y(),
628                            pts[2].x(), pts[2].y(),
629                            pts[1].x(), pts[1].y(),
630                            sqrInvScaleX, sqrInvScaleY, outputVertices);
631                    break;
632                case SkPath::kCubic_Verb:
633                    ALOGV("kCubic_Verb");
634                    RecursiveCubicBezierVertices(
635                            pts[0].x(), pts[0].y(),
636                            pts[1].x(), pts[1].y(),
637                            pts[3].x(), pts[3].y(),
638                            pts[2].x(), pts[2].y(),
639                        sqrInvScaleX, sqrInvScaleY, outputVertices);
640                    break;
641                default:
642                    break;
643            }
644    }
645
646    int size = outputVertices->count();
647    if (size >= 2 && (*outputVertices)[0].position[0] == (*outputVertices)[size - 1].position[0] &&
648            (*outputVertices)[0].position[1] == (*outputVertices)[size - 1].position[1]) {
649        outputVertices->pop_back();
650        return true;
651    }
652    return false;
653}
654
655void PathRenderer::RecursiveCubicBezierVertices(
656        float p1x, float p1y, float c1x, float c1y,
657        float p2x, float p2y, float c2x, float c2y,
658        float sqrInvScaleX, float sqrInvScaleY, SkTArray<Vertex, true>* outputVertices) {
659    float dx = p2x - p1x;
660    float dy = p2y - p1y;
661    float d1 = sk_float_abs((c1x - p2x) * dy - (c1y - p2y) * dx);
662    float d2 = sk_float_abs((c2x - p2x) * dy - (c2y - p2y) * dx);
663    float d = d1 + d2;
664
665    // multiplying by sqrInvScaleY/X equivalent to multiplying in dimensional scale factors
666
667    if (d * d < THRESHOLD * THRESHOLD * (dx * dx * sqrInvScaleY + dy * dy * sqrInvScaleX)) {
668        // below thresh, draw line by adding endpoint
669        pushToVector(outputVertices, p2x, p2y);
670    } else {
671        float p1c1x = (p1x + c1x) * 0.5f;
672        float p1c1y = (p1y + c1y) * 0.5f;
673        float p2c2x = (p2x + c2x) * 0.5f;
674        float p2c2y = (p2y + c2y) * 0.5f;
675
676        float c1c2x = (c1x + c2x) * 0.5f;
677        float c1c2y = (c1y + c2y) * 0.5f;
678
679        float p1c1c2x = (p1c1x + c1c2x) * 0.5f;
680        float p1c1c2y = (p1c1y + c1c2y) * 0.5f;
681
682        float p2c1c2x = (p2c2x + c1c2x) * 0.5f;
683        float p2c1c2y = (p2c2y + c1c2y) * 0.5f;
684
685        float mx = (p1c1c2x + p2c1c2x) * 0.5f;
686        float my = (p1c1c2y + p2c1c2y) * 0.5f;
687
688        RecursiveCubicBezierVertices(
689                p1x, p1y, p1c1x, p1c1y,
690                mx, my, p1c1c2x, p1c1c2y,
691                sqrInvScaleX, sqrInvScaleY, outputVertices);
692        RecursiveCubicBezierVertices(
693                mx, my, p2c1c2x, p2c1c2y,
694                p2x, p2y, p2c2x, p2c2y,
695                sqrInvScaleX, sqrInvScaleY, outputVertices);
696    }
697}
698
699void PathRenderer::RecursiveQuadraticBezierVertices(
700        float ax, float ay,
701        float bx, float by,
702        float cx, float cy,
703        float sqrInvScaleX, float sqrInvScaleY, SkTArray<Vertex, true>* outputVertices) {
704    float dx = bx - ax;
705    float dy = by - ay;
706    float d = (cx - bx) * dy - (cy - by) * dx;
707
708    if (d * d < THRESHOLD * THRESHOLD * (dx * dx * sqrInvScaleY + dy * dy * sqrInvScaleX)) {
709        // below thresh, draw line by adding endpoint
710        pushToVector(outputVertices, bx, by);
711    } else {
712        float acx = (ax + cx) * 0.5f;
713        float bcx = (bx + cx) * 0.5f;
714        float acy = (ay + cy) * 0.5f;
715        float bcy = (by + cy) * 0.5f;
716
717        // midpoint
718        float mx = (acx + bcx) * 0.5f;
719        float my = (acy + bcy) * 0.5f;
720
721        RecursiveQuadraticBezierVertices(ax, ay, mx, my, acx, acy,
722                sqrInvScaleX, sqrInvScaleY, outputVertices);
723        RecursiveQuadraticBezierVertices(mx, my, bx, by, bcx, bcy,
724                sqrInvScaleX, sqrInvScaleY, outputVertices);
725    }
726}
727
728}; // namespace uirenderer
729}; // namespace android
730