libs/hwui/PathTessellator.cpp

   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                 break;
1009             }
1010     }
1011
1012     bool wasClosed = false;
1013     int size = outputVertices.size();
1014     if (size >= 2 && outputVertices[0].x == outputVertices[size - 1].x &&
1015             outputVertices[0].y == outputVertices[size - 1].y) {
1016         outputVertices.pop_back();
1017         wasClosed = true;
1018     }
1019
1020     // ensure output vector is clockwise
1021     clockwiseEnforcer.reverseVectorIfNotClockwise(outputVertices);
1022     return wasClosed;
1023 }
1024
1025 ///////////////////////////////////////////////////////////////////////////////
1026 // Bezier approximation
1027 //
1028 // All the inputs and outputs here are in path coordinates.
1029 // We convert the error threshold from screen coordinates into path coordinates.
1030 ///////////////////////////////////////////////////////////////////////////////
1031
1032 // Get a threshold in path coordinates, by scaling the thresholdSquared from screen coordinates.
1033 // TODO: Document the math behind this algorithm.
1034 static inline float getThreshold(const PathApproximationInfo& info, float dx, float dy) {
1035     // multiplying by sqrInvScaleY/X equivalent to multiplying in dimensional scale factors
1036     float scale = (dx * dx * info.sqrInvScaleY + dy * dy * info.sqrInvScaleX);
1037     return info.thresholdSquared * scale;
1038 }
1039
1040 void PathTessellator::recursiveCubicBezierVertices(
1041         float p1x, float p1y, float c1x, float c1y,
1042         float p2x, float p2y, float c2x, float c2y,
1043         const PathApproximationInfo& approximationInfo,
1044         std::vector<Vertex>& outputVertices, int depth) {
1045     float dx = p2x - p1x;
1046     float dy = p2y - p1y;
1047     float d1 = fabs((c1x - p2x) * dy - (c1y - p2y) * dx);
1048     float d2 = fabs((c2x - p2x) * dy - (c2y - p2y) * dx);
1049     float d = d1 + d2;
1050
1051     if (depth >= MAX_DEPTH
1052             || d * d <= getThreshold(approximationInfo, dx, dy)) {
1053         // below thresh, draw line by adding endpoint
1054         outputVertices.push_back(Vertex{p2x, p2y});
1055     } else {
1056         float p1c1x = (p1x + c1x) * 0.5f;
1057         float p1c1y = (p1y + c1y) * 0.5f;
1058         float p2c2x = (p2x + c2x) * 0.5f;
1059         float p2c2y = (p2y + c2y) * 0.5f;
1060
1061         float c1c2x = (c1x + c2x) * 0.5f;
1062         float c1c2y = (c1y + c2y) * 0.5f;
1063
1064         float p1c1c2x = (p1c1x + c1c2x) * 0.5f;
1065         float p1c1c2y = (p1c1y + c1c2y) * 0.5f;
1066
1067         float p2c1c2x = (p2c2x + c1c2x) * 0.5f;
1068         float p2c1c2y = (p2c2y + c1c2y) * 0.5f;
1069
1070         float mx = (p1c1c2x + p2c1c2x) * 0.5f;
1071         float my = (p1c1c2y + p2c1c2y) * 0.5f;
1072
1073         recursiveCubicBezierVertices(
1074                 p1x, p1y, p1c1x, p1c1y,
1075                 mx, my, p1c1c2x, p1c1c2y,
1076                 approximationInfo, outputVertices, depth + 1);
1077         recursiveCubicBezierVertices(
1078                 mx, my, p2c1c2x, p2c1c2y,
1079                 p2x, p2y, p2c2x, p2c2y,
1080                 approximationInfo, outputVertices, depth + 1);
1081     }
1082 }
1083
1084 void PathTessellator::recursiveQuadraticBezierVertices(
1085         float ax, float ay,
1086         float bx, float by,
1087         float cx, float cy,
1088         const PathApproximationInfo& approximationInfo,
1089         std::vector<Vertex>& outputVertices, int depth) {
1090     float dx = bx - ax;
1091     float dy = by - ay;
1092     // d is the cross product of vector (B-A) and (C-B).
1093     float d = (cx - bx) * dy - (cy - by) * dx;
1094
1095     if (depth >= MAX_DEPTH
1096             || d * d <= getThreshold(approximationInfo, dx, dy)) {
1097         // below thresh, draw line by adding endpoint
1098         outputVertices.push_back(Vertex{bx, by});
1099     } else {
1100         float acx = (ax + cx) * 0.5f;
1101         float bcx = (bx + cx) * 0.5f;
1102         float acy = (ay + cy) * 0.5f;
1103         float bcy = (by + cy) * 0.5f;
1104
1105         // midpoint
1106         float mx = (acx + bcx) * 0.5f;
1107         float my = (acy + bcy) * 0.5f;
1108
1109         recursiveQuadraticBezierVertices(ax, ay, mx, my, acx, acy,
1110                 approximationInfo, outputVertices, depth + 1);
1111         recursiveQuadraticBezierVertices(mx, my, bx, by, bcx, bcy,
1112                 approximationInfo, outputVertices, depth + 1);
1113     }
1114 }
1115
1116 }; // namespace uirenderer
1117 }; // namespace android