src/gpu/GrAAHairLinePathRenderer.cpp

   1 /*
   2  * Copyright 2011 Google Inc.
   3  *
   4  * Use of this source code is governed by a BSD-style license that can be
   5  * found in the LICENSE file.
   6  */
   7
   8 #include "GrAAHairLinePathRenderer.h"
   9
  10 #include "GrBatch.h"
  11 #include "GrBatchTarget.h"
  12 #include "GrBufferAllocPool.h"
  13 #include "GrContext.h"
  14 #include "GrDefaultGeoProcFactory.h"
  15 #include "GrDrawTargetCaps.h"
  16 #include "GrGpu.h"
  17 #include "GrIndexBuffer.h"
  18 #include "GrPathUtils.h"
  19 #include "GrPipelineBuilder.h"
  20 #include "GrProcessor.h"
  21 #include "SkGeometry.h"
  22 #include "SkStroke.h"
  23 #include "SkTemplates.h"
  24
  25 #include "effects/GrBezierEffect.h"
  26
  27 // quadratics are rendered as 5-sided polys in order to bound the
  28 // AA stroke around the center-curve. See comments in push_quad_index_buffer and
  29 // bloat_quad. Quadratics and conics share an index buffer
  30
  31 // lines are rendered as:
  32 //      *______________*
  33 //      |\ -_______   /|
  34 //      | \        \ / |
  35 //      |  *--------*  |
  36 //      | /  ______/ \ |
  37 //      */_-__________\*
  38 // For: 6 vertices and 18 indices (for 6 triangles)
  39
  40 // Each quadratic is rendered as a five sided polygon. This poly bounds
  41 // the quadratic's bounding triangle but has been expanded so that the
  42 // 1-pixel wide area around the curve is inside the poly.
  43 // If a,b,c are the original control points then the poly a0,b0,c0,c1,a1
  44 // that is rendered would look like this:
  45 //              b0
  46 //              b
  47 //
  48 //     a0              c0
  49 //      a            c
  50 //       a1       c1
  51 // Each is drawn as three triangles ((a0,a1,b0), (b0,c1,c0), (a1,c1,b0))
  52 // specified by these 9 indices:
  53 static const uint16_t kQuadIdxBufPattern[] = {
  54     0, 1, 2,
  55     2, 4, 3,
  56     1, 4, 2
  57 };
  58
  59 static const int kIdxsPerQuad = SK_ARRAY_COUNT(kQuadIdxBufPattern);
  60 static const int kQuadNumVertices = 5;
  61 static const int kQuadsNumInIdxBuffer = 256;
  62
  63
  64 // Each line segment is rendered as two quads and two triangles.
  65 // p0 and p1 have alpha = 1 while all other points have alpha = 0.
  66 // The four external points are offset 1 pixel perpendicular to the
  67 // line and half a pixel parallel to the line.
  68 //
  69 // p4                  p5
  70 //      p0         p1
  71 // p2                  p3
  72 //
  73 // Each is drawn as six triangles specified by these 18 indices:
  74
  75 static const uint16_t kLineSegIdxBufPattern[] = {
  76     0, 1, 3,
  77     0, 3, 2,
  78     0, 4, 5,
  79     0, 5, 1,
  80     0, 2, 4,
  81     1, 5, 3
  82 };
  83
  84 static const int kIdxsPerLineSeg = SK_ARRAY_COUNT(kLineSegIdxBufPattern);
  85 static const int kLineSegNumVertices = 6;
  86 static const int kLineSegsNumInIdxBuffer = 256;
  87
  88 GrPathRenderer* GrAAHairLinePathRenderer::Create(GrContext* context) {
  89     GrGpu* gpu = context->getGpu();
  90     GrIndexBuffer* qIdxBuf = gpu->createInstancedIndexBuffer(kQuadIdxBufPattern,
  91                                                              kIdxsPerQuad,
  92                                                              kQuadsNumInIdxBuffer,
  93                                                              kQuadNumVertices);
  94     SkAutoTUnref<GrIndexBuffer> qIdxBuffer(qIdxBuf);
  95     GrIndexBuffer* lIdxBuf = gpu->createInstancedIndexBuffer(kLineSegIdxBufPattern,
  96                                                              kIdxsPerLineSeg,
  97                                                              kLineSegsNumInIdxBuffer,
  98                                                              kLineSegNumVertices);
  99     SkAutoTUnref<GrIndexBuffer> lIdxBuffer(lIdxBuf);
 100     return SkNEW_ARGS(GrAAHairLinePathRenderer,
 101                       (context, lIdxBuf, qIdxBuf));
 102 }
 103
 104 GrAAHairLinePathRenderer::GrAAHairLinePathRenderer(
 105                                         const GrContext* context,
 106                                         const GrIndexBuffer* linesIndexBuffer,
 107                                         const GrIndexBuffer* quadsIndexBuffer) {
 108     fLinesIndexBuffer = linesIndexBuffer;
 109     linesIndexBuffer->ref();
 110     fQuadsIndexBuffer = quadsIndexBuffer;
 111     quadsIndexBuffer->ref();
 112 }
 113
 114 GrAAHairLinePathRenderer::~GrAAHairLinePathRenderer() {
 115     fLinesIndexBuffer->unref();
 116     fQuadsIndexBuffer->unref();
 117 }
 118
 119 namespace {
 120
 121 #define PREALLOC_PTARRAY(N) SkSTArray<(N),SkPoint, true>
 122
 123 // Takes 178th time of logf on Z600 / VC2010
 124 int get_float_exp(float x) {
 125     GR_STATIC_ASSERT(sizeof(int) == sizeof(float));
 126 #ifdef SK_DEBUG
 127     static bool tested;
 128     if (!tested) {
 129         tested = true;
 130         SkASSERT(get_float_exp(0.25f) == -2);
 131         SkASSERT(get_float_exp(0.3f) == -2);
 132         SkASSERT(get_float_exp(0.5f) == -1);
 133         SkASSERT(get_float_exp(1.f) == 0);
 134         SkASSERT(get_float_exp(2.f) == 1);
 135         SkASSERT(get_float_exp(2.5f) == 1);
 136         SkASSERT(get_float_exp(8.f) == 3);
 137         SkASSERT(get_float_exp(100.f) == 6);
 138         SkASSERT(get_float_exp(1000.f) == 9);
 139         SkASSERT(get_float_exp(1024.f) == 10);
 140         SkASSERT(get_float_exp(3000000.f) == 21);
 141     }
 142 #endif
 143     const int* iptr = (const int*)&x;
 144     return (((*iptr) & 0x7f800000) >> 23) - 127;
 145 }
 146
 147 // Uses the max curvature function for quads to estimate
 148 // where to chop the conic. If the max curvature is not
 149 // found along the curve segment it will return 1 and
 150 // dst[0] is the original conic. If it returns 2 the dst[0]
 151 // and dst[1] are the two new conics.
 152 int split_conic(const SkPoint src[3], SkConic dst[2], const SkScalar weight) {
 153     SkScalar t = SkFindQuadMaxCurvature(src);
 154     if (t == 0) {
 155         if (dst) {
 156             dst[0].set(src, weight);
 157         }
 158         return 1;
 159     } else {
 160         if (dst) {
 161             SkConic conic;
 162             conic.set(src, weight);
 163             conic.chopAt(t, dst);
 164         }
 165         return 2;
 166     }
 167 }
 168
 169 // Calls split_conic on the entire conic and then once more on each subsection.
 170 // Most cases will result in either 1 conic (chop point is not within t range)
 171 // or 3 points (split once and then one subsection is split again).
 172 int chop_conic(const SkPoint src[3], SkConic dst[4], const SkScalar weight) {
 173     SkConic dstTemp[2];
 174     int conicCnt = split_conic(src, dstTemp, weight);
 175     if (2 == conicCnt) {
 176         int conicCnt2 = split_conic(dstTemp[0].fPts, dst, dstTemp[0].fW);
 177         conicCnt = conicCnt2 + split_conic(dstTemp[1].fPts, &dst[conicCnt2], dstTemp[1].fW);
 178     } else {
 179         dst[0] = dstTemp[0];
 180     }
 181     return conicCnt;
 182 }
 183
 184 // returns 0 if quad/conic is degen or close to it
 185 // in this case approx the path with lines
 186 // otherwise returns 1
 187 int is_degen_quad_or_conic(const SkPoint p[3], SkScalar* dsqd) {
 188     static const SkScalar gDegenerateToLineTol = SK_Scalar1;
 189     static const SkScalar gDegenerateToLineTolSqd =
 190         SkScalarMul(gDegenerateToLineTol, gDegenerateToLineTol);
 191
 192     if (p[0].distanceToSqd(p[1]) < gDegenerateToLineTolSqd ||
 193         p[1].distanceToSqd(p[2]) < gDegenerateToLineTolSqd) {
 194         return 1;
 195     }
 196
 197     *dsqd = p[1].distanceToLineBetweenSqd(p[0], p[2]);
 198     if (*dsqd < gDegenerateToLineTolSqd) {
 199         return 1;
 200     }
 201
 202     if (p[2].distanceToLineBetweenSqd(p[1], p[0]) < gDegenerateToLineTolSqd) {
 203         return 1;
 204     }
 205     return 0;
 206 }
 207
 208 int is_degen_quad_or_conic(const SkPoint p[3]) {
 209     SkScalar dsqd;
 210     return is_degen_quad_or_conic(p, &dsqd);
 211 }
 212
 213 // we subdivide the quads to avoid huge overfill
 214 // if it returns -1 then should be drawn as lines
 215 int num_quad_subdivs(const SkPoint p[3]) {
 216     SkScalar dsqd;
 217     if (is_degen_quad_or_conic(p, &dsqd)) {
 218         return -1;
 219     }
 220
 221     // tolerance of triangle height in pixels
 222     // tuned on windows  Quadro FX 380 / Z600
 223     // trade off of fill vs cpu time on verts
 224     // maybe different when do this using gpu (geo or tess shaders)
 225     static const SkScalar gSubdivTol = 175 * SK_Scalar1;
 226
 227     if (dsqd <= SkScalarMul(gSubdivTol, gSubdivTol)) {
 228         return 0;
 229     } else {
 230         static const int kMaxSub = 4;
 231         // subdividing the quad reduces d by 4. so we want x = log4(d/tol)
 232         // = log4(d*d/tol*tol)/2
 233         // = log2(d*d/tol*tol)
 234
 235         // +1 since we're ignoring the mantissa contribution.
 236         int log = get_float_exp(dsqd/(gSubdivTol*gSubdivTol)) + 1;
 237         log = SkTMin(SkTMax(0, log), kMaxSub);
 238         return log;
 239     }
 240 }
 241
 242 /**
 243  * Generates the lines and quads to be rendered. Lines are always recorded in
 244  * device space. We will do a device space bloat to account for the 1pixel
 245  * thickness.
 246  * Quads are recorded in device space unless m contains
 247  * perspective, then in they are in src space. We do this because we will
 248  * subdivide large quads to reduce over-fill. This subdivision has to be
 249  * performed before applying the perspective matrix.
 250  */
 251 int gather_lines_and_quads(const SkPath& path,
 252                            const SkMatrix& m,
 253                            const SkIRect& devClipBounds,
 254                            GrAAHairLinePathRenderer::PtArray* lines,
 255                            GrAAHairLinePathRenderer::PtArray* quads,
 256                            GrAAHairLinePathRenderer::PtArray* conics,
 257                            GrAAHairLinePathRenderer::IntArray* quadSubdivCnts,
 258                            GrAAHairLinePathRenderer::FloatArray* conicWeights) {
 259     SkPath::Iter iter(path, false);
 260
 261     int totalQuadCount = 0;
 262     SkRect bounds;
 263     SkIRect ibounds;
 264
 265     bool persp = m.hasPerspective();
 266
 267     for (;;) {
 268         SkPoint pathPts[4];
 269         SkPoint devPts[4];
 270         SkPath::Verb verb = iter.next(pathPts);
 271         switch (verb) {
 272             case SkPath::kConic_Verb: {
 273                 SkConic dst[4];
 274                 // We chop the conics to create tighter clipping to hide error
 275                 // that appears near max curvature of very thin conics. Thin
 276                 // hyperbolas with high weight still show error.
 277                 int conicCnt = chop_conic(pathPts, dst, iter.conicWeight());
 278                 for (int i = 0; i < conicCnt; ++i) {
 279                     SkPoint* chopPnts = dst[i].fPts;
 280                     m.mapPoints(devPts, chopPnts, 3);
 281                     bounds.setBounds(devPts, 3);
 282                     bounds.outset(SK_Scalar1, SK_Scalar1);
 283                     bounds.roundOut(&ibounds);
 284                     if (SkIRect::Intersects(devClipBounds, ibounds)) {
 285                         if (is_degen_quad_or_conic(devPts)) {
 286                             SkPoint* pts = lines->push_back_n(4);
 287                             pts[0] = devPts[0];
 288                             pts[1] = devPts[1];
 289                             pts[2] = devPts[1];
 290                             pts[3] = devPts[2];
 291                         } else {
 292                             // when in perspective keep conics in src space
 293                             SkPoint* cPts = persp ? chopPnts : devPts;
 294                             SkPoint* pts = conics->push_back_n(3);
 295                             pts[0] = cPts[0];
 296                             pts[1] = cPts[1];
 297                             pts[2] = cPts[2];
 298                             conicWeights->push_back() = dst[i].fW;
 299                         }
 300                     }
 301                 }
 302                 break;
 303             }
 304             case SkPath::kMove_Verb:
 305                 break;
 306             case SkPath::kLine_Verb:
 307                 m.mapPoints(devPts, pathPts, 2);
 308                 bounds.setBounds(devPts, 2);
 309                 bounds.outset(SK_Scalar1, SK_Scalar1);
 310                 bounds.roundOut(&ibounds);
 311                 if (SkIRect::Intersects(devClipBounds, ibounds)) {
 312                     SkPoint* pts = lines->push_back_n(2);
 313                     pts[0] = devPts[0];
 314                     pts[1] = devPts[1];
 315                 }
 316                 break;
 317             case SkPath::kQuad_Verb: {
 318                 SkPoint choppedPts[5];
 319                 // Chopping the quad helps when the quad is either degenerate or nearly degenerate.
 320                 // When it is degenerate it allows the approximation with lines to work since the
 321                 // chop point (if there is one) will be at the parabola's vertex. In the nearly
 322                 // degenerate the QuadUVMatrix computed for the points is almost singular which
 323                 // can cause rendering artifacts.
 324                 int n = SkChopQuadAtMaxCurvature(pathPts, choppedPts);
 325                 for (int i = 0; i < n; ++i) {
 326                     SkPoint* quadPts = choppedPts + i * 2;
 327                     m.mapPoints(devPts, quadPts, 3);
 328                     bounds.setBounds(devPts, 3);
 329                     bounds.outset(SK_Scalar1, SK_Scalar1);
 330                     bounds.roundOut(&ibounds);
 331
 332                     if (SkIRect::Intersects(devClipBounds, ibounds)) {
 333                         int subdiv = num_quad_subdivs(devPts);
 334                         SkASSERT(subdiv >= -1);
 335                         if (-1 == subdiv) {
 336                             SkPoint* pts = lines->push_back_n(4);
 337                             pts[0] = devPts[0];
 338                             pts[1] = devPts[1];
 339                             pts[2] = devPts[1];
 340                             pts[3] = devPts[2];
 341                         } else {
 342                             // when in perspective keep quads in src space
 343                             SkPoint* qPts = persp ? quadPts : devPts;
 344                             SkPoint* pts = quads->push_back_n(3);
 345                             pts[0] = qPts[0];
 346                             pts[1] = qPts[1];
 347                             pts[2] = qPts[2];
 348                             quadSubdivCnts->push_back() = subdiv;
 349                             totalQuadCount += 1 << subdiv;
 350                         }
 351                     }
 352                 }
 353                 break;
 354             }
 355             case SkPath::kCubic_Verb:
 356                 m.mapPoints(devPts, pathPts, 4);
 357                 bounds.setBounds(devPts, 4);
 358                 bounds.outset(SK_Scalar1, SK_Scalar1);
 359                 bounds.roundOut(&ibounds);
 360                 if (SkIRect::Intersects(devClipBounds, ibounds)) {
 361                     PREALLOC_PTARRAY(32) q;
 362                     // we don't need a direction if we aren't constraining the subdivision
 363                     static const SkPath::Direction kDummyDir = SkPath::kCCW_Direction;
 364                     // We convert cubics to quadratics (for now).
 365                     // In perspective have to do conversion in src space.
 366                     if (persp) {
 367                         SkScalar tolScale =
 368                             GrPathUtils::scaleToleranceToSrc(SK_Scalar1, m,
 369                                                              path.getBounds());
 370                         GrPathUtils::convertCubicToQuads(pathPts, tolScale, false, kDummyDir, &q);
 371                     } else {
 372                         GrPathUtils::convertCubicToQuads(devPts, SK_Scalar1, false, kDummyDir, &q);
 373                     }
 374                     for (int i = 0; i < q.count(); i += 3) {
 375                         SkPoint* qInDevSpace;
 376                         // bounds has to be calculated in device space, but q is
 377                         // in src space when there is perspective.
 378                         if (persp) {
 379                             m.mapPoints(devPts, &q[i], 3);
 380                             bounds.setBounds(devPts, 3);
 381                             qInDevSpace = devPts;
 382                         } else {
 383                             bounds.setBounds(&q[i], 3);
 384                             qInDevSpace = &q[i];
 385                         }
 386                         bounds.outset(SK_Scalar1, SK_Scalar1);
 387                         bounds.roundOut(&ibounds);
 388                         if (SkIRect::Intersects(devClipBounds, ibounds)) {
 389                             int subdiv = num_quad_subdivs(qInDevSpace);
 390                             SkASSERT(subdiv >= -1);
 391                             if (-1 == subdiv) {
 392                                 SkPoint* pts = lines->push_back_n(4);
 393                                 // lines should always be in device coords
 394                                 pts[0] = qInDevSpace[0];
 395                                 pts[1] = qInDevSpace[1];
 396                                 pts[2] = qInDevSpace[1];
 397                                 pts[3] = qInDevSpace[2];
 398                             } else {
 399                                 SkPoint* pts = quads->push_back_n(3);
 400                                 // q is already in src space when there is no
 401                                 // perspective and dev coords otherwise.
 402                                 pts[0] = q[0 + i];
 403                                 pts[1] = q[1 + i];
 404                                 pts[2] = q[2 + i];
 405                                 quadSubdivCnts->push_back() = subdiv;
 406                                 totalQuadCount += 1 << subdiv;
 407                             }
 408                         }
 409                     }
 410                 }
 411                 break;
 412             case SkPath::kClose_Verb:
 413                 break;
 414             case SkPath::kDone_Verb:
 415                 return totalQuadCount;
 416         }
 417     }
 418 }
 419
 420 struct LineVertex {
 421     SkPoint fPos;
 422     float fCoverage;
 423 };
 424
 425 struct BezierVertex {
 426     SkPoint fPos;
 427     union {
 428         struct {
 429             SkScalar fK;
 430             SkScalar fL;
 431             SkScalar fM;
 432         } fConic;
 433         SkVector   fQuadCoord;
 434         struct {
 435             SkScalar fBogus[4];
 436         };
 437     };
 438 };
 439
 440 GR_STATIC_ASSERT(sizeof(BezierVertex) == 3 * sizeof(SkPoint));
 441
 442 void intersect_lines(const SkPoint& ptA, const SkVector& normA,
 443                      const SkPoint& ptB, const SkVector& normB,
 444                      SkPoint* result) {
 445
 446     SkScalar lineAW = -normA.dot(ptA);
 447     SkScalar lineBW = -normB.dot(ptB);
 448
 449     SkScalar wInv = SkScalarMul(normA.fX, normB.fY) -
 450         SkScalarMul(normA.fY, normB.fX);
 451     wInv = SkScalarInvert(wInv);
 452
 453     result->fX = SkScalarMul(normA.fY, lineBW) - SkScalarMul(lineAW, normB.fY);
 454     result->fX = SkScalarMul(result->fX, wInv);
 455
 456     result->fY = SkScalarMul(lineAW, normB.fX) - SkScalarMul(normA.fX, lineBW);
 457     result->fY = SkScalarMul(result->fY, wInv);
 458 }
 459
 460 void set_uv_quad(const SkPoint qpts[3], BezierVertex verts[kQuadNumVertices]) {
 461     // this should be in the src space, not dev coords, when we have perspective
 462     GrPathUtils::QuadUVMatrix DevToUV(qpts);
 463     DevToUV.apply<kQuadNumVertices, sizeof(BezierVertex), sizeof(SkPoint)>(verts);
 464 }
 465
 466 void bloat_quad(const SkPoint qpts[3], const SkMatrix* toDevice,
 467                 const SkMatrix* toSrc, BezierVertex verts[kQuadNumVertices]) {
 468     SkASSERT(!toDevice == !toSrc);
 469     // original quad is specified by tri a,b,c
 470     SkPoint a = qpts[0];
 471     SkPoint b = qpts[1];
 472     SkPoint c = qpts[2];
 473
 474     if (toDevice) {
 475         toDevice->mapPoints(&a, 1);
 476         toDevice->mapPoints(&b, 1);
 477         toDevice->mapPoints(&c, 1);
 478     }
 479     // make a new poly where we replace a and c by a 1-pixel wide edges orthog
 480     // to edges ab and bc:
 481     //
 482     //   before       |        after
 483     //                |              b0
 484     //         b      |
 485     //                |
 486     //                |     a0            c0
 487     // a         c    |        a1       c1
 488     //
 489     // edges a0->b0 and b0->c0 are parallel to original edges a->b and b->c,
 490     // respectively.
 491     BezierVertex& a0 = verts[0];
 492     BezierVertex& a1 = verts[1];
 493     BezierVertex& b0 = verts[2];
 494     BezierVertex& c0 = verts[3];
 495     BezierVertex& c1 = verts[4];
 496
 497     SkVector ab = b;
 498     ab -= a;
 499     SkVector ac = c;
 500     ac -= a;
 501     SkVector cb = b;
 502     cb -= c;
 503
 504     // We should have already handled degenerates
 505     SkASSERT(ab.length() > 0 && cb.length() > 0);
 506
 507     ab.normalize();
 508     SkVector abN;
 509     abN.setOrthog(ab, SkVector::kLeft_Side);
 510     if (abN.dot(ac) > 0) {
 511         abN.negate();
 512     }
 513
 514     cb.normalize();
 515     SkVector cbN;
 516     cbN.setOrthog(cb, SkVector::kLeft_Side);
 517     if (cbN.dot(ac) < 0) {
 518         cbN.negate();
 519     }
 520
 521     a0.fPos = a;
 522     a0.fPos += abN;
 523     a1.fPos = a;
 524     a1.fPos -= abN;
 525
 526     c0.fPos = c;
 527     c0.fPos += cbN;
 528     c1.fPos = c;
 529     c1.fPos -= cbN;
 530
 531     intersect_lines(a0.fPos, abN, c0.fPos, cbN, &b0.fPos);
 532
 533     if (toSrc) {
 534         toSrc->mapPointsWithStride(&verts[0].fPos, sizeof(BezierVertex), kQuadNumVertices);
 535     }
 536 }
 537
 538 // Equations based off of Loop-Blinn Quadratic GPU Rendering
 539 // Input Parametric:
 540 // P(t) = (P0*(1-t)^2 + 2*w*P1*t*(1-t) + P2*t^2) / (1-t)^2 + 2*w*t*(1-t) + t^2)
 541 // Output Implicit:
 542 // f(x, y, w) = f(P) = K^2 - LM
 543 // K = dot(k, P), L = dot(l, P), M = dot(m, P)
 544 // k, l, m are calculated in function GrPathUtils::getConicKLM
 545 void set_conic_coeffs(const SkPoint p[3], BezierVertex verts[kQuadNumVertices],
 546                       const SkScalar weight) {
 547     SkScalar klm[9];
 548
 549     GrPathUtils::getConicKLM(p, weight, klm);
 550
 551     for (int i = 0; i < kQuadNumVertices; ++i) {
 552         const SkPoint pnt = verts[i].fPos;
 553         verts[i].fConic.fK = pnt.fX * klm[0] + pnt.fY * klm[1] + klm[2];
 554         verts[i].fConic.fL = pnt.fX * klm[3] + pnt.fY * klm[4] + klm[5];
 555         verts[i].fConic.fM = pnt.fX * klm[6] + pnt.fY * klm[7] + klm[8];
 556     }
 557 }
 558
 559 void add_conics(const SkPoint p[3],
 560                 const SkScalar weight,
 561                 const SkMatrix* toDevice,
 562                 const SkMatrix* toSrc,
 563                 BezierVertex** vert) {
 564     bloat_quad(p, toDevice, toSrc, *vert);
 565     set_conic_coeffs(p, *vert, weight);
 566     *vert += kQuadNumVertices;
 567 }
 568
 569 void add_quads(const SkPoint p[3],
 570                int subdiv,
 571                const SkMatrix* toDevice,
 572                const SkMatrix* toSrc,
 573                BezierVertex** vert) {
 574     SkASSERT(subdiv >= 0);
 575     if (subdiv) {
 576         SkPoint newP[5];
 577         SkChopQuadAtHalf(p, newP);
 578         add_quads(newP + 0, subdiv-1, toDevice, toSrc, vert);
 579         add_quads(newP + 2, subdiv-1, toDevice, toSrc, vert);
 580     } else {
 581         bloat_quad(p, toDevice, toSrc, *vert);
 582         set_uv_quad(p, *vert);
 583         *vert += kQuadNumVertices;
 584     }
 585 }
 586
 587 void add_line(const SkPoint p[2],
 588               const SkMatrix* toSrc,
 589               uint8_t coverage,
 590               LineVertex** vert) {
 591     const SkPoint& a = p[0];
 592     const SkPoint& b = p[1];
 593
 594     SkVector ortho, vec = b;
 595     vec -= a;
 596
 597     if (vec.setLength(SK_ScalarHalf)) {
 598         // Create a vector orthogonal to 'vec' and of unit length
 599         ortho.fX = 2.0f * vec.fY;
 600         ortho.fY = -2.0f * vec.fX;
 601
 602         float floatCoverage = GrNormalizeByteToFloat(coverage);
 603
 604         (*vert)[0].fPos = a;
 605         (*vert)[0].fCoverage = floatCoverage;
 606         (*vert)[1].fPos = b;
 607         (*vert)[1].fCoverage = floatCoverage;
 608         (*vert)[2].fPos = a - vec + ortho;
 609         (*vert)[2].fCoverage = 0;
 610         (*vert)[3].fPos = b + vec + ortho;
 611         (*vert)[3].fCoverage = 0;
 612         (*vert)[4].fPos = a - vec - ortho;
 613         (*vert)[4].fCoverage = 0;
 614         (*vert)[5].fPos = b + vec - ortho;
 615         (*vert)[5].fCoverage = 0;
 616
 617         if (toSrc) {
 618             toSrc->mapPointsWithStride(&(*vert)->fPos,
 619                                        sizeof(LineVertex),
 620                                        kLineSegNumVertices);
 621         }
 622     } else {
 623         // just make it degenerate and likely offscreen
 624         for (int i = 0; i < kLineSegNumVertices; ++i) {
 625             (*vert)[i].fPos.set(SK_ScalarMax, SK_ScalarMax);
 626         }
 627     }
 628
 629     *vert += kLineSegNumVertices;
 630 }
 631
 632 }
 633
 634 ///////////////////////////////////////////////////////////////////////////////
 635
 636 bool GrAAHairLinePathRenderer::canDrawPath(const GrDrawTarget* target,
 637                                            const GrPipelineBuilder* pipelineBuilder,
 638                                            const SkMatrix& viewMatrix,
 639                                            const SkPath& path,
 640                                            const SkStrokeRec& stroke,
 641                                            bool antiAlias) const {
 642     if (!antiAlias) {
 643         return false;
 644     }
 645
 646     if (!IsStrokeHairlineOrEquivalent(stroke, viewMatrix, NULL)) {
 647         return false;
 648     }
 649
 650     if (SkPath::kLine_SegmentMask == path.getSegmentMasks() ||
 651         target->caps()->shaderDerivativeSupport()) {
 652         return true;
 653     }
 654     return false;
 655 }
 656
 657 template <class VertexType>
 658 bool check_bounds(const SkMatrix& viewMatrix, const SkRect& devBounds, void* vertices, int vCount)
 659 {
 660     SkRect tolDevBounds = devBounds;
 661     // The bounds ought to be tight, but in perspective the below code runs the verts
 662     // through the view matrix to get back to dev coords, which can introduce imprecision.
 663     if (viewMatrix.hasPerspective()) {
 664         tolDevBounds.outset(SK_Scalar1 / 1000, SK_Scalar1 / 1000);
 665     } else {
 666         // Non-persp matrices cause this path renderer to draw in device space.
 667         SkASSERT(viewMatrix.isIdentity());
 668     }
 669     SkRect actualBounds;
 670
 671     VertexType* verts = reinterpret_cast<VertexType*>(vertices);
 672     bool first = true;
 673     for (int i = 0; i < vCount; ++i) {
 674         SkPoint pos = verts[i].fPos;
 675         // This is a hack to workaround the fact that we move some degenerate segments offscreen.
 676         if (SK_ScalarMax == pos.fX) {
 677             continue;
 678         }
 679         viewMatrix.mapPoints(&pos, 1);
 680         if (first) {
 681             actualBounds.set(pos.fX, pos.fY, pos.fX, pos.fY);
 682             first = false;
 683         } else {
 684             actualBounds.growToInclude(pos.fX, pos.fY);
 685         }
 686     }
 687     if (!first) {
 688         return tolDevBounds.contains(actualBounds);
 689     }
 690
 691     return true;
 692 }
 693
 694 class AAHairlineBatch : public GrBatch {
 695 public:
 696     struct Geometry {
 697         GrColor fColor;
 698         uint8_t fCoverage;
 699         SkMatrix fViewMatrix;
 700         SkPath fPath;
 701         SkDEBUGCODE(SkRect fDevBounds;)
 702         SkIRect fDevClipBounds;
 703     };
 704
 705     // TODO Batch itself should not hold on to index buffers.  Instead, these should live in the
 706     // cache.
 707     static GrBatch* Create(const Geometry& geometry, const GrIndexBuffer* linesIndexBuffer,
 708                            const GrIndexBuffer* quadsIndexBuffer) {
 709         return SkNEW_ARGS(AAHairlineBatch, (geometry, linesIndexBuffer, quadsIndexBuffer));
 710     }
 711
 712     const char* name() const override { return "AAHairlineBatch"; }
 713
 714     void getInvariantOutputColor(GrInitInvariantOutput* out) const override {
 715         // When this is called on a batch, there is only one geometry bundle
 716         out->setKnownFourComponents(fGeoData[0].fColor);
 717     }
 718     void getInvariantOutputCoverage(GrInitInvariantOutput* out) const override {
 719         out->setUnknownSingleComponent();
 720     }
 721
 722     void initBatchTracker(const GrPipelineInfo& init) override {
 723         // Handle any color overrides
 724         if (init.fColorIgnored) {
 725             fGeoData[0].fColor = GrColor_ILLEGAL;
 726         } else if (GrColor_ILLEGAL != init.fOverrideColor) {
 727             fGeoData[0].fColor = init.fOverrideColor;
 728         }
 729
 730         // setup batch properties
 731         fBatch.fColorIgnored = init.fColorIgnored;
 732         fBatch.fColor = fGeoData[0].fColor;
 733         fBatch.fUsesLocalCoords = init.fUsesLocalCoords;
 734         fBatch.fCoverageIgnored = init.fCoverageIgnored;
 735         fBatch.fCoverage = fGeoData[0].fCoverage;
 736         SkDEBUGCODE(fBatch.fDevBounds = fGeoData[0].fDevBounds;)
 737     }
 738
 739     void generateGeometry(GrBatchTarget* batchTarget, const GrPipeline* pipeline) override;
 740
 741     SkSTArray<1, Geometry, true>* geoData() { return &fGeoData; }
 742
 743 private:
 744     typedef SkTArray<SkPoint, true> PtArray;
 745     typedef SkTArray<int, true> IntArray;
 746     typedef SkTArray<float, true> FloatArray;
 747
 748     AAHairlineBatch(const Geometry& geometry, const GrIndexBuffer* linesIndexBuffer,
 749                     const GrIndexBuffer* quadsIndexBuffer)
 750         : fLinesIndexBuffer(linesIndexBuffer)
 751         , fQuadsIndexBuffer(quadsIndexBuffer) {
 752         SkASSERT(linesIndexBuffer && quadsIndexBuffer);
 753         this->initClassID<AAHairlineBatch>();
 754         fGeoData.push_back(geometry);
 755     }
 756
 757     bool onCombineIfPossible(GrBatch* t) override {
 758         AAHairlineBatch* that = t->cast<AAHairlineBatch>();
 759
 760         if (this->viewMatrix().hasPerspective() != that->viewMatrix().hasPerspective()) {
 761             return false;
 762         }
 763
 764         // We go to identity if we don't have perspective
 765         if (this->viewMatrix().hasPerspective() &&
 766             !this->viewMatrix().cheapEqualTo(that->viewMatrix())) {
 767             return false;
 768         }
 769
 770         // TODO we can actually batch hairlines if they are the same color in a kind of bulk method
 771         // but we haven't implemented this yet
 772         // TODO investigate going to vertex color and coverage?
 773         if (this->coverage() != that->coverage()) {
 774             return false;
 775         }
 776
 777         if (this->color() != that->color()) {
 778             return false;
 779         }
 780
 781         SkASSERT(this->usesLocalCoords() == that->usesLocalCoords());
 782         if (this->usesLocalCoords() && !this->viewMatrix().cheapEqualTo(that->viewMatrix())) {
 783             return false;
 784         }
 785
 786         fGeoData.push_back_n(that->geoData()->count(), that->geoData()->begin());
 787         return true;
 788     }
 789
 790     GrColor color() const { return fBatch.fColor; }
 791     uint8_t coverage() const { return fBatch.fCoverage; }
 792     bool usesLocalCoords() const { return fBatch.fUsesLocalCoords; }
 793     const SkMatrix& viewMatrix() const { return fGeoData[0].fViewMatrix; }
 794
 795     struct BatchTracker {
 796         GrColor fColor;
 797         uint8_t fCoverage;
 798         SkRect fDevBounds;
 799         bool fUsesLocalCoords;
 800         bool fColorIgnored;
 801         bool fCoverageIgnored;
 802     };
 803
 804     BatchTracker fBatch;
 805     SkSTArray<1, Geometry, true> fGeoData;
 806     const GrIndexBuffer* fLinesIndexBuffer;
 807     const GrIndexBuffer* fQuadsIndexBuffer;
 808 };
 809
 810 void AAHairlineBatch::generateGeometry(GrBatchTarget* batchTarget, const GrPipeline* pipeline) {
 811     // Setup the viewmatrix and localmatrix for the GrGeometryProcessor.
 812     SkMatrix invert;
 813     if (!this->viewMatrix().invert(&invert)) {
 814         return;
 815     }
 816
 817     // we will transform to identity space if the viewmatrix does not have perspective
 818     bool hasPerspective = this->viewMatrix().hasPerspective();
 819     const SkMatrix* geometryProcessorViewM = &SkMatrix::I();
 820     const SkMatrix* geometryProcessorLocalM = &invert;
 821     const SkMatrix* toDevice = NULL;
 822     const SkMatrix* toSrc = NULL;
 823     if (hasPerspective) {
 824         geometryProcessorViewM = &this->viewMatrix();
 825         geometryProcessorLocalM = &SkMatrix::I();
 826         toDevice = &this->viewMatrix();
 827         toSrc = &invert;
 828     }
 829
 830     // Setup geometry processors for worst case
 831     uint32_t gpFlags = GrDefaultGeoProcFactory::kPosition_GPType |
 832                        GrDefaultGeoProcFactory::kCoverage_GPType;
 833
 834     SkAutoTUnref<const GrGeometryProcessor> lineGP(
 835             GrDefaultGeoProcFactory::Create(gpFlags,
 836                                             this->color(),
 837                                             *geometryProcessorViewM,
 838                                             *geometryProcessorLocalM,
 839                                             false,
 840                                             this->coverage()));
 841
 842     SkAutoTUnref<const GrGeometryProcessor> quadGP(
 843             GrQuadEffect::Create(this->color(),
 844                                  *geometryProcessorViewM,
 845                                  kHairlineAA_GrProcessorEdgeType,
 846                                  batchTarget->caps(),
 847                                  *geometryProcessorLocalM,
 848                                  this->coverage()));
 849
 850     SkAutoTUnref<const GrGeometryProcessor> conicGP(
 851             GrConicEffect::Create(this->color(),
 852                                   *geometryProcessorViewM,
 853                                   kHairlineAA_GrProcessorEdgeType,
 854                                   batchTarget->caps(),
 855                                   *geometryProcessorLocalM,
 856                                   this->coverage()));
 857
 858     // This is hand inlined for maximum performance.
 859     PREALLOC_PTARRAY(128) lines;
 860     PREALLOC_PTARRAY(128) quads;
 861     PREALLOC_PTARRAY(128) conics;
 862     IntArray qSubdivs;
 863     FloatArray cWeights;
 864     int quadCount = 0;
 865
 866     int instanceCount = fGeoData.count();
 867     for (int i = 0; i < instanceCount; i++) {
 868         const Geometry& args = fGeoData[i];
 869         quadCount += gather_lines_and_quads(args.fPath, args.fViewMatrix, args.fDevClipBounds,
 870                                             &lines, &quads, &conics, &qSubdivs, &cWeights);
 871     }
 872
 873     int lineCount = lines.count() / 2;
 874     int conicCount = conics.count() / 3;
 875
 876     // do lines first
 877     if (lineCount) {
 878         batchTarget->initDraw(lineGP, pipeline);
 879
 880         // TODO remove this when batch is everywhere
 881         GrPipelineInfo init;
 882         init.fColorIgnored = fBatch.fColorIgnored;
 883         init.fOverrideColor = GrColor_ILLEGAL;
 884         init.fCoverageIgnored = fBatch.fCoverageIgnored;
 885         init.fUsesLocalCoords = this->usesLocalCoords();
 886         lineGP->initBatchTracker(batchTarget->currentBatchTracker(), init);
 887
 888         const GrVertexBuffer* vertexBuffer;
 889         int firstVertex;
 890
 891         size_t vertexStride = lineGP->getVertexStride();
 892         int vertexCount = kLineSegNumVertices * lineCount;
 893         void *vertices = batchTarget->vertexPool()->makeSpace(vertexStride,
 894                                                               vertexCount,
 895                                                               &vertexBuffer,
 896                                                               &firstVertex);
 897
 898         if (!vertices) {
 899             SkDebugf("Could not allocate vertices\n");
 900             return;
 901         }
 902
 903         SkASSERT(lineGP->getVertexStride() == sizeof(LineVertex));
 904
 905         LineVertex* verts = reinterpret_cast<LineVertex*>(vertices);
 906         for (int i = 0; i < lineCount; ++i) {
 907             add_line(&lines[2*i], toSrc, this->coverage(), &verts);
 908         }
 909
 910         {
 911             GrDrawTarget::DrawInfo info;
 912             info.setVertexBuffer(vertexBuffer);
 913             info.setIndexBuffer(fLinesIndexBuffer);
 914             info.setPrimitiveType(kTriangles_GrPrimitiveType);
 915             info.setStartIndex(0);
 916
 917             int lines = 0;
 918             while (lines < lineCount) {
 919                 int n = SkTMin(lineCount - lines, kLineSegsNumInIdxBuffer);
 920
 921                 info.setStartVertex(kLineSegNumVertices*lines + firstVertex);
 922                 info.setVertexCount(kLineSegNumVertices*n);
 923                 info.setIndexCount(kIdxsPerLineSeg*n);
 924                 batchTarget->draw(info);
 925
 926                 lines += n;
 927             }
 928         }
 929     }
 930
 931     if (quadCount || conicCount) {
 932         const GrVertexBuffer* vertexBuffer;
 933         int firstVertex;
 934
 935         size_t vertexStride = sizeof(BezierVertex);
 936         int vertexCount = kQuadNumVertices * quadCount + kQuadNumVertices * conicCount;
 937         void *vertices = batchTarget->vertexPool()->makeSpace(vertexStride,
 938                                                               vertexCount,
 939                                                               &vertexBuffer,
 940                                                               &firstVertex);
 941
 942         if (!vertices) {
 943             SkDebugf("Could not allocate vertices\n");
 944             return;
 945         }
 946
 947         // Setup vertices
 948         BezierVertex* verts = reinterpret_cast<BezierVertex*>(vertices);
 949
 950         int unsubdivQuadCnt = quads.count() / 3;
 951         for (int i = 0; i < unsubdivQuadCnt; ++i) {
 952             SkASSERT(qSubdivs[i] >= 0);
 953             add_quads(&quads[3*i], qSubdivs[i], toDevice, toSrc, &verts);
 954         }
 955
 956         // Start Conics
 957         for (int i = 0; i < conicCount; ++i) {
 958             add_conics(&conics[3*i], cWeights[i], toDevice, toSrc, &verts);
 959         }
 960
 961         if (quadCount > 0) {
 962             batchTarget->initDraw(quadGP, pipeline);
 963
 964             // TODO remove this when batch is everywhere
 965             GrPipelineInfo init;
 966             init.fColorIgnored = fBatch.fColorIgnored;
 967             init.fOverrideColor = GrColor_ILLEGAL;
 968             init.fCoverageIgnored = fBatch.fCoverageIgnored;
 969             init.fUsesLocalCoords = this->usesLocalCoords();
 970             quadGP->initBatchTracker(batchTarget->currentBatchTracker(), init);
 971
 972             {
 973                GrDrawTarget::DrawInfo info;
 974                info.setVertexBuffer(vertexBuffer);
 975                info.setIndexBuffer(fQuadsIndexBuffer);
 976                info.setPrimitiveType(kTriangles_GrPrimitiveType);
 977                info.setStartIndex(0);
 978
 979                int quads = 0;
 980                while (quads < quadCount) {
 981                    int n = SkTMin(quadCount - quads, kQuadsNumInIdxBuffer);
 982
 983                    info.setStartVertex(kQuadNumVertices*quads + firstVertex);
 984                    info.setVertexCount(kQuadNumVertices*n);
 985                    info.setIndexCount(kIdxsPerQuad*n);
 986                    batchTarget->draw(info);
 987
 988                    quads += n;
 989                }
 990            }
 991         }
 992
 993         if (conicCount > 0) {
 994             batchTarget->initDraw(conicGP, pipeline);
 995
 996             // TODO remove this when batch is everywhere
 997             GrPipelineInfo init;
 998             init.fColorIgnored = fBatch.fColorIgnored;
 999             init.fOverrideColor = GrColor_ILLEGAL;
1000             init.fCoverageIgnored = fBatch.fCoverageIgnored;
1001             init.fUsesLocalCoords = this->usesLocalCoords();
1002             conicGP->initBatchTracker(batchTarget->currentBatchTracker(), init);
1003
1004             {
1005                 GrDrawTarget::DrawInfo info;
1006                 info.setVertexBuffer(vertexBuffer);
1007                 info.setIndexBuffer(fQuadsIndexBuffer);
1008                 info.setPrimitiveType(kTriangles_GrPrimitiveType);
1009                 info.setStartIndex(0);
1010
1011                 int conics = 0;
1012                 while (conics < conicCount) {
1013                     int n = SkTMin(conicCount - conics, kQuadsNumInIdxBuffer);
1014
1015                     info.setStartVertex(kQuadNumVertices*(quadCount + conics) + firstVertex);
1016                     info.setVertexCount(kQuadNumVertices*n);
1017                     info.setIndexCount(kIdxsPerQuad*n);
1018                     batchTarget->draw(info);
1019
1020                     conics += n;
1021                 }
1022             }
1023         }
1024     }
1025 }
1026
1027 bool GrAAHairLinePathRenderer::onDrawPath(GrDrawTarget* target,
1028                                           GrPipelineBuilder* pipelineBuilder,
1029                                           GrColor color,
1030                                           const SkMatrix& viewMatrix,
1031                                           const SkPath& path,
1032                                           const SkStrokeRec& stroke,
1033                                           bool) {
1034     if (!fLinesIndexBuffer || !fQuadsIndexBuffer) {
1035         SkDebugf("unable to allocate indices\n");
1036         return false;
1037     }
1038
1039     SkScalar hairlineCoverage;
1040     uint8_t newCoverage = 0xff;
1041     if (IsStrokeHairlineOrEquivalent(stroke, viewMatrix, &hairlineCoverage)) {
1042         newCoverage = SkScalarRoundToInt(hairlineCoverage * 0xff);
1043     }
1044
1045     SkIRect devClipBounds;
1046     pipelineBuilder->clip().getConservativeBounds(pipelineBuilder->getRenderTarget(),
1047                                                   &devClipBounds);
1048
1049     // This outset was determined experimentally by running skps and gms.  It probably could be a
1050     // bit tighter
1051     SkRect devRect = path.getBounds();
1052     viewMatrix.mapRect(&devRect);
1053     devRect.outset(2, 2);
1054
1055     AAHairlineBatch::Geometry geometry;
1056     geometry.fColor = color;
1057     geometry.fCoverage = newCoverage;
1058     geometry.fViewMatrix = viewMatrix;
1059     geometry.fPath = path;
1060     SkDEBUGCODE(geometry.fDevBounds = devRect;)
1061     geometry.fDevClipBounds = devClipBounds;
1062
1063     SkAutoTUnref<GrBatch> batch(AAHairlineBatch::Create(geometry, fLinesIndexBuffer,
1064                                                         fQuadsIndexBuffer));
1065     target->drawBatch(pipelineBuilder, batch, &devRect);
1066
1067     return true;
1068 }