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