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