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