1 2 /* 3 * Copyright 2011 Google Inc. 4 * 5 * Use of this source code is governed by a BSD-style license that can be 6 * found in the LICENSE file. 7 */ 8 9 #include "GrAAHairLinePathRenderer.h" 10 11 #include "GrContext.h" 12 #include "GrDrawState.h" 13 #include "GrGpu.h" 14 #include "GrIndexBuffer.h" 15 #include "GrPathUtils.h" 16 #include "SkGeometry.h" 17 #include "SkStroke.h" 18 #include "SkTemplates.h" 19 20 namespace { 21 // quadratics are rendered as 5-sided polys in order to bound the 22 // AA stroke around the center-curve. See comments in push_quad_index_buffer and 23 // bloat_quad. 24 static const int kVertsPerQuad = 5; 25 static const int kIdxsPerQuad = 9; 26 27 static const int kVertsPerLineSeg = 4; 28 static const int kIdxsPerLineSeg = 6; 29 30 static const int kNumQuadsInIdxBuffer = 256; 31 static const size_t kQuadIdxSBufize = kIdxsPerQuad * 32 sizeof(uint16_t) * 33 kNumQuadsInIdxBuffer; 34 35 bool push_quad_index_data(GrIndexBuffer* qIdxBuffer) { 36 uint16_t* data = (uint16_t*) qIdxBuffer->lock(); 37 bool tempData = NULL == data; 38 if (tempData) { 39 data = SkNEW_ARRAY(uint16_t, kNumQuadsInIdxBuffer * kIdxsPerQuad); 40 } 41 for (int i = 0; i < kNumQuadsInIdxBuffer; ++i) { 42 43 // Each quadratic is rendered as a five sided polygon. This poly bounds 44 // the quadratic's bounding triangle but has been expanded so that the 45 // 1-pixel wide area around the curve is inside the poly. 46 // If a,b,c are the original control points then the poly a0,b0,c0,c1,a1 47 // that is rendered would look like this: 48 // b0 49 // b 50 // 51 // a0 c0 52 // a c 53 // a1 c1 54 // Each is drawn as three triangles specified by these 9 indices: 55 int baseIdx = i * kIdxsPerQuad; 56 uint16_t baseVert = (uint16_t)(i * kVertsPerQuad); 57 data[0 + baseIdx] = baseVert + 0; // a0 58 data[1 + baseIdx] = baseVert + 1; // a1 59 data[2 + baseIdx] = baseVert + 2; // b0 60 data[3 + baseIdx] = baseVert + 2; // b0 61 data[4 + baseIdx] = baseVert + 4; // c1 62 data[5 + baseIdx] = baseVert + 3; // c0 63 data[6 + baseIdx] = baseVert + 1; // a1 64 data[7 + baseIdx] = baseVert + 4; // c1 65 data[8 + baseIdx] = baseVert + 2; // b0 66 } 67 if (tempData) { 68 bool ret = qIdxBuffer->updateData(data, kQuadIdxSBufize); 69 delete[] data; 70 return ret; 71 } else { 72 qIdxBuffer->unlock(); 73 return true; 74 } 75 } 76 } 77 78 GrPathRenderer* GrAAHairLinePathRenderer::Create(GrContext* context) { 79 const GrIndexBuffer* lIdxBuffer = context->getQuadIndexBuffer(); 80 if (NULL == lIdxBuffer) { 81 return NULL; 82 } 83 GrGpu* gpu = context->getGpu(); 84 GrIndexBuffer* qIdxBuf = gpu->createIndexBuffer(kQuadIdxSBufize, false); 85 SkAutoTUnref<GrIndexBuffer> qIdxBuffer(qIdxBuf); 86 if (NULL == qIdxBuf || 87 !push_quad_index_data(qIdxBuf)) { 88 return NULL; 89 } 90 return SkNEW_ARGS(GrAAHairLinePathRenderer, 91 (context, lIdxBuffer, qIdxBuf)); 92 } 93 94 GrAAHairLinePathRenderer::GrAAHairLinePathRenderer( 95 const GrContext* context, 96 const GrIndexBuffer* linesIndexBuffer, 97 const GrIndexBuffer* quadsIndexBuffer) { 98 fLinesIndexBuffer = linesIndexBuffer; 99 linesIndexBuffer->ref(); 100 fQuadsIndexBuffer = quadsIndexBuffer; 101 quadsIndexBuffer->ref(); 102 } 103 104 GrAAHairLinePathRenderer::~GrAAHairLinePathRenderer() { 105 fLinesIndexBuffer->unref(); 106 fQuadsIndexBuffer->unref(); 107 } 108 109 namespace { 110 111 typedef SkTArray<SkPoint, true> PtArray; 112 #define PREALLOC_PTARRAY(N) SkSTArray<(N),SkPoint, true> 113 typedef SkTArray<int, true> IntArray; 114 115 // Takes 178th time of logf on Z600 / VC2010 116 int get_float_exp(float x) { 117 GR_STATIC_ASSERT(sizeof(int) == sizeof(float)); 118 #if GR_DEBUG 119 static bool tested; 120 if (!tested) { 121 tested = true; 122 GrAssert(get_float_exp(0.25f) == -2); 123 GrAssert(get_float_exp(0.3f) == -2); 124 GrAssert(get_float_exp(0.5f) == -1); 125 GrAssert(get_float_exp(1.f) == 0); 126 GrAssert(get_float_exp(2.f) == 1); 127 GrAssert(get_float_exp(2.5f) == 1); 128 GrAssert(get_float_exp(8.f) == 3); 129 GrAssert(get_float_exp(100.f) == 6); 130 GrAssert(get_float_exp(1000.f) == 9); 131 GrAssert(get_float_exp(1024.f) == 10); 132 GrAssert(get_float_exp(3000000.f) == 21); 133 } 134 #endif 135 const int* iptr = (const int*)&x; 136 return (((*iptr) & 0x7f800000) >> 23) - 127; 137 } 138 139 // we subdivide the quads to avoid huge overfill 140 // if it returns -1 then should be drawn as lines 141 int num_quad_subdivs(const SkPoint p[3]) { 142 static const SkScalar gDegenerateToLineTol = SK_Scalar1; 143 static const SkScalar gDegenerateToLineTolSqd = 144 SkScalarMul(gDegenerateToLineTol, gDegenerateToLineTol); 145 146 if (p[0].distanceToSqd(p[1]) < gDegenerateToLineTolSqd || 147 p[1].distanceToSqd(p[2]) < gDegenerateToLineTolSqd) { 148 return -1; 149 } 150 151 SkScalar dsqd = p[1].distanceToLineBetweenSqd(p[0], p[2]); 152 if (dsqd < gDegenerateToLineTolSqd) { 153 return -1; 154 } 155 156 if (p[2].distanceToLineBetweenSqd(p[1], p[0]) < gDegenerateToLineTolSqd) { 157 return -1; 158 } 159 160 static const int kMaxSub = 4; 161 // tolerance of triangle height in pixels 162 // tuned on windows Quadro FX 380 / Z600 163 // trade off of fill vs cpu time on verts 164 // maybe different when do this using gpu (geo or tess shaders) 165 static const SkScalar gSubdivTol = 175 * SK_Scalar1; 166 167 if (dsqd <= SkScalarMul(gSubdivTol, gSubdivTol)) { 168 return 0; 169 } else { 170 // subdividing the quad reduces d by 4. so we want x = log4(d/tol) 171 // = log4(d*d/tol*tol)/2 172 // = log2(d*d/tol*tol) 173 174 #ifdef SK_SCALAR_IS_FLOAT 175 // +1 since we're ignoring the mantissa contribution. 176 int log = get_float_exp(dsqd/(gSubdivTol*gSubdivTol)) + 1; 177 log = GrMin(GrMax(0, log), kMaxSub); 178 return log; 179 #else 180 SkScalar log = SkScalarLog( 181 SkScalarDiv(dsqd, 182 SkScalarMul(gSubdivTol, gSubdivTol))); 183 static const SkScalar conv = SkScalarInvert(SkScalarLog(2)); 184 log = SkScalarMul(log, conv); 185 return GrMin(GrMax(0, SkScalarCeilToInt(log)),kMaxSub); 186 #endif 187 } 188 } 189 190 /** 191 * Generates the lines and quads to be rendered. Lines are always recorded in 192 * device space. We will do a device space bloat to account for the 1pixel 193 * thickness. 194 * Quads are recorded in device space unless m contains 195 * perspective, then in they are in src space. We do this because we will 196 * subdivide large quads to reduce over-fill. This subdivision has to be 197 * performed before applying the perspective matrix. 198 */ 199 int generate_lines_and_quads(const SkPath& path, 200 const SkMatrix& m, 201 const GrIRect& devClipBounds, 202 PtArray* lines, 203 PtArray* quads, 204 IntArray* quadSubdivCnts) { 205 SkPath::Iter iter(path, false); 206 207 int totalQuadCount = 0; 208 GrRect bounds; 209 GrIRect ibounds; 210 211 bool persp = m.hasPerspective(); 212 213 for (;;) { 214 GrPoint pts[4]; 215 GrPoint devPts[4]; 216 GrPathCmd cmd = (GrPathCmd)iter.next(pts); 217 switch (cmd) { 218 case kMove_PathCmd: 219 break; 220 case kLine_PathCmd: 221 m.mapPoints(devPts, pts, 2); 222 bounds.setBounds(devPts, 2); 223 bounds.outset(SK_Scalar1, SK_Scalar1); 224 bounds.roundOut(&ibounds); 225 if (SkIRect::Intersects(devClipBounds, ibounds)) { 226 SkPoint* pts = lines->push_back_n(2); 227 pts[0] = devPts[0]; 228 pts[1] = devPts[1]; 229 } 230 break; 231 case kQuadratic_PathCmd: 232 m.mapPoints(devPts, pts, 3); 233 bounds.setBounds(devPts, 3); 234 bounds.outset(SK_Scalar1, SK_Scalar1); 235 bounds.roundOut(&ibounds); 236 if (SkIRect::Intersects(devClipBounds, ibounds)) { 237 int subdiv = num_quad_subdivs(devPts); 238 GrAssert(subdiv >= -1); 239 if (-1 == subdiv) { 240 SkPoint* pts = lines->push_back_n(4); 241 pts[0] = devPts[0]; 242 pts[1] = devPts[1]; 243 pts[2] = devPts[1]; 244 pts[3] = devPts[2]; 245 } else { 246 // when in perspective keep quads in src space 247 SkPoint* qPts = persp ? pts : devPts; 248 SkPoint* pts = quads->push_back_n(3); 249 pts[0] = qPts[0]; 250 pts[1] = qPts[1]; 251 pts[2] = qPts[2]; 252 quadSubdivCnts->push_back() = subdiv; 253 totalQuadCount += 1 << subdiv; 254 } 255 } 256 break; 257 case kCubic_PathCmd: 258 m.mapPoints(devPts, pts, 4); 259 bounds.setBounds(devPts, 4); 260 bounds.outset(SK_Scalar1, SK_Scalar1); 261 bounds.roundOut(&ibounds); 262 if (SkIRect::Intersects(devClipBounds, ibounds)) { 263 PREALLOC_PTARRAY(32) q; 264 // we don't need a direction if we aren't constraining the subdivision 265 static const SkPath::Direction kDummyDir = SkPath::kCCW_Direction; 266 // We convert cubics to quadratics (for now). 267 // In perspective have to do conversion in src space. 268 if (persp) { 269 SkScalar tolScale = 270 GrPathUtils::scaleToleranceToSrc(SK_Scalar1, m, 271 path.getBounds()); 272 GrPathUtils::convertCubicToQuads(pts, tolScale, false, kDummyDir, &q); 273 } else { 274 GrPathUtils::convertCubicToQuads(devPts, SK_Scalar1, false, kDummyDir, &q); 275 } 276 for (int i = 0; i < q.count(); i += 3) { 277 SkPoint* qInDevSpace; 278 // bounds has to be calculated in device space, but q is 279 // in src space when there is perspective. 280 if (persp) { 281 m.mapPoints(devPts, &q[i], 3); 282 bounds.setBounds(devPts, 3); 283 qInDevSpace = devPts; 284 } else { 285 bounds.setBounds(&q[i], 3); 286 qInDevSpace = &q[i]; 287 } 288 bounds.outset(SK_Scalar1, SK_Scalar1); 289 bounds.roundOut(&ibounds); 290 if (SkIRect::Intersects(devClipBounds, ibounds)) { 291 int subdiv = num_quad_subdivs(qInDevSpace); 292 GrAssert(subdiv >= -1); 293 if (-1 == subdiv) { 294 SkPoint* pts = lines->push_back_n(4); 295 // lines should always be in device coords 296 pts[0] = qInDevSpace[0]; 297 pts[1] = qInDevSpace[1]; 298 pts[2] = qInDevSpace[1]; 299 pts[3] = qInDevSpace[2]; 300 } else { 301 SkPoint* pts = quads->push_back_n(3); 302 // q is already in src space when there is no 303 // perspective and dev coords otherwise. 304 pts[0] = q[0 + i]; 305 pts[1] = q[1 + i]; 306 pts[2] = q[2 + i]; 307 quadSubdivCnts->push_back() = subdiv; 308 totalQuadCount += 1 << subdiv; 309 } 310 } 311 } 312 } 313 break; 314 case kClose_PathCmd: 315 break; 316 case kEnd_PathCmd: 317 return totalQuadCount; 318 } 319 } 320 } 321 322 struct Vertex { 323 GrPoint fPos; 324 union { 325 struct { 326 SkScalar fA; 327 SkScalar fB; 328 SkScalar fC; 329 } fLine; 330 GrVec fQuadCoord; 331 struct { 332 SkScalar fBogus[4]; 333 }; 334 }; 335 }; 336 GR_STATIC_ASSERT(sizeof(Vertex) == 3 * sizeof(GrPoint)); 337 338 void intersect_lines(const SkPoint& ptA, const SkVector& normA, 339 const SkPoint& ptB, const SkVector& normB, 340 SkPoint* result) { 341 342 SkScalar lineAW = -normA.dot(ptA); 343 SkScalar lineBW = -normB.dot(ptB); 344 345 SkScalar wInv = SkScalarMul(normA.fX, normB.fY) - 346 SkScalarMul(normA.fY, normB.fX); 347 wInv = SkScalarInvert(wInv); 348 349 result->fX = SkScalarMul(normA.fY, lineBW) - SkScalarMul(lineAW, normB.fY); 350 result->fX = SkScalarMul(result->fX, wInv); 351 352 result->fY = SkScalarMul(lineAW, normB.fX) - SkScalarMul(normA.fX, lineBW); 353 result->fY = SkScalarMul(result->fY, wInv); 354 } 355 356 void bloat_quad(const SkPoint qpts[3], const SkMatrix* toDevice, 357 const SkMatrix* toSrc, Vertex verts[kVertsPerQuad]) { 358 GrAssert(!toDevice == !toSrc); 359 // original quad is specified by tri a,b,c 360 SkPoint a = qpts[0]; 361 SkPoint b = qpts[1]; 362 SkPoint c = qpts[2]; 363 364 // this should be in the src space, not dev coords, when we have perspective 365 GrPathUtils::QuadUVMatrix DevToUV(qpts); 366 367 if (toDevice) { 368 toDevice->mapPoints(&a, 1); 369 toDevice->mapPoints(&b, 1); 370 toDevice->mapPoints(&c, 1); 371 } 372 // make a new poly where we replace a and c by a 1-pixel wide edges orthog 373 // to edges ab and bc: 374 // 375 // before | after 376 // | b0 377 // b | 378 // | 379 // | a0 c0 380 // a c | a1 c1 381 // 382 // edges a0->b0 and b0->c0 are parallel to original edges a->b and b->c, 383 // respectively. 384 Vertex& a0 = verts[0]; 385 Vertex& a1 = verts[1]; 386 Vertex& b0 = verts[2]; 387 Vertex& c0 = verts[3]; 388 Vertex& c1 = verts[4]; 389 390 SkVector ab = b; 391 ab -= a; 392 SkVector ac = c; 393 ac -= a; 394 SkVector cb = b; 395 cb -= c; 396 397 // We should have already handled degenerates 398 GrAssert(ab.length() > 0 && cb.length() > 0); 399 400 ab.normalize(); 401 SkVector abN; 402 abN.setOrthog(ab, SkVector::kLeft_Side); 403 if (abN.dot(ac) > 0) { 404 abN.negate(); 405 } 406 407 cb.normalize(); 408 SkVector cbN; 409 cbN.setOrthog(cb, SkVector::kLeft_Side); 410 if (cbN.dot(ac) < 0) { 411 cbN.negate(); 412 } 413 414 a0.fPos = a; 415 a0.fPos += abN; 416 a1.fPos = a; 417 a1.fPos -= abN; 418 419 c0.fPos = c; 420 c0.fPos += cbN; 421 c1.fPos = c; 422 c1.fPos -= cbN; 423 424 intersect_lines(a0.fPos, abN, c0.fPos, cbN, &b0.fPos); 425 426 if (toSrc) { 427 toSrc->mapPointsWithStride(&verts[0].fPos, sizeof(Vertex), kVertsPerQuad); 428 } 429 DevToUV.apply<kVertsPerQuad, sizeof(Vertex), sizeof(GrPoint)>(verts); 430 } 431 432 void add_quads(const SkPoint p[3], 433 int subdiv, 434 const SkMatrix* toDevice, 435 const SkMatrix* toSrc, 436 Vertex** vert) { 437 GrAssert(subdiv >= 0); 438 if (subdiv) { 439 SkPoint newP[5]; 440 SkChopQuadAtHalf(p, newP); 441 add_quads(newP + 0, subdiv-1, toDevice, toSrc, vert); 442 add_quads(newP + 2, subdiv-1, toDevice, toSrc, vert); 443 } else { 444 bloat_quad(p, toDevice, toSrc, *vert); 445 *vert += kVertsPerQuad; 446 } 447 } 448 449 void add_line(const SkPoint p[2], 450 int rtHeight, 451 const SkMatrix* toSrc, 452 Vertex** vert) { 453 const SkPoint& a = p[0]; 454 const SkPoint& b = p[1]; 455 456 SkVector orthVec = b; 457 orthVec -= a; 458 459 if (orthVec.setLength(SK_Scalar1)) { 460 orthVec.setOrthog(orthVec); 461 462 SkScalar lineC = -(a.dot(orthVec)); 463 for (int i = 0; i < kVertsPerLineSeg; ++i) { 464 (*vert)[i].fPos = (i < 2) ? a : b; 465 if (0 == i || 3 == i) { 466 (*vert)[i].fPos -= orthVec; 467 } else { 468 (*vert)[i].fPos += orthVec; 469 } 470 (*vert)[i].fLine.fA = orthVec.fX; 471 (*vert)[i].fLine.fB = orthVec.fY; 472 (*vert)[i].fLine.fC = lineC; 473 } 474 if (NULL != toSrc) { 475 toSrc->mapPointsWithStride(&(*vert)->fPos, 476 sizeof(Vertex), 477 kVertsPerLineSeg); 478 } 479 } else { 480 // just make it degenerate and likely offscreen 481 (*vert)[0].fPos.set(SK_ScalarMax, SK_ScalarMax); 482 (*vert)[1].fPos.set(SK_ScalarMax, SK_ScalarMax); 483 (*vert)[2].fPos.set(SK_ScalarMax, SK_ScalarMax); 484 (*vert)[3].fPos.set(SK_ScalarMax, SK_ScalarMax); 485 } 486 487 *vert += kVertsPerLineSeg; 488 } 489 490 } 491 492 bool GrAAHairLinePathRenderer::createGeom( 493 const SkPath& path, 494 GrDrawTarget* target, 495 int* lineCnt, 496 int* quadCnt, 497 GrDrawTarget::AutoReleaseGeometry* arg) { 498 const GrDrawState& drawState = target->getDrawState(); 499 int rtHeight = drawState.getRenderTarget()->height(); 500 501 GrIRect devClipBounds; 502 target->getClip()->getConservativeBounds(drawState.getRenderTarget(), 503 &devClipBounds); 504 505 GrVertexLayout layout = GrDrawState::kEdge_VertexLayoutBit; 506 SkMatrix viewM = drawState.getViewMatrix(); 507 508 PREALLOC_PTARRAY(128) lines; 509 PREALLOC_PTARRAY(128) quads; 510 IntArray qSubdivs; 511 *quadCnt = generate_lines_and_quads(path, viewM, devClipBounds, 512 &lines, &quads, &qSubdivs); 513 514 *lineCnt = lines.count() / 2; 515 int vertCnt = kVertsPerLineSeg * *lineCnt + kVertsPerQuad * *quadCnt; 516 517 GrAssert(sizeof(Vertex) == GrDrawState::VertexSize(layout)); 518 519 if (!arg->set(target, layout, vertCnt, 0)) { 520 return false; 521 } 522 523 Vertex* verts = reinterpret_cast<Vertex*>(arg->vertices()); 524 525 const SkMatrix* toDevice = NULL; 526 const SkMatrix* toSrc = NULL; 527 SkMatrix ivm; 528 529 if (viewM.hasPerspective()) { 530 if (viewM.invert(&ivm)) { 531 toDevice = &viewM; 532 toSrc = &ivm; 533 } 534 } 535 536 for (int i = 0; i < *lineCnt; ++i) { 537 add_line(&lines[2*i], rtHeight, toSrc, &verts); 538 } 539 540 int unsubdivQuadCnt = quads.count() / 3; 541 for (int i = 0; i < unsubdivQuadCnt; ++i) { 542 GrAssert(qSubdivs[i] >= 0); 543 add_quads(&quads[3*i], qSubdivs[i], toDevice, toSrc, &verts); 544 } 545 546 return true; 547 } 548 549 bool GrAAHairLinePathRenderer::canDrawPath(const SkPath& path, 550 const SkStrokeRec& stroke, 551 const GrDrawTarget* target, 552 bool antiAlias) const { 553 if (!stroke.isHairlineStyle() || !antiAlias) { 554 return false; 555 } 556 557 static const uint32_t gReqDerivMask = SkPath::kCubic_SegmentMask | 558 SkPath::kQuad_SegmentMask; 559 if (!target->getCaps().shaderDerivativeSupport() && 560 (gReqDerivMask & path.getSegmentMasks())) { 561 return false; 562 } 563 return true; 564 } 565 566 bool GrAAHairLinePathRenderer::onDrawPath(const SkPath& path, 567 const SkStrokeRec&, 568 GrDrawTarget* target, 569 bool antiAlias) { 570 571 int lineCnt; 572 int quadCnt; 573 GrDrawTarget::AutoReleaseGeometry arg; 574 if (!this->createGeom(path, 575 target, 576 &lineCnt, 577 &quadCnt, 578 &arg)) { 579 return false; 580 } 581 582 GrDrawState::AutoDeviceCoordDraw adcd; 583 GrDrawState* drawState = target->drawState(); 584 // createGeom transforms the geometry to device space when the matrix does not have 585 // perspective. 586 if (!drawState->getViewMatrix().hasPerspective()) { 587 adcd.set(drawState); 588 if (!adcd.succeeded()) { 589 return false; 590 } 591 } 592 593 // TODO: See whether rendering lines as degenerate quads improves perf 594 // when we have a mix 595 596 GrDrawState::VertexEdgeType oldEdgeType = drawState->getVertexEdgeType(); 597 598 target->setIndexSourceToBuffer(fLinesIndexBuffer); 599 int lines = 0; 600 int nBufLines = fLinesIndexBuffer->maxQuads(); 601 drawState->setVertexEdgeType(GrDrawState::kHairLine_EdgeType); 602 while (lines < lineCnt) { 603 int n = GrMin(lineCnt - lines, nBufLines); 604 target->drawIndexed(kTriangles_GrPrimitiveType, 605 kVertsPerLineSeg*lines, // startV 606 0, // startI 607 kVertsPerLineSeg*n, // vCount 608 kIdxsPerLineSeg*n); // iCount 609 lines += n; 610 } 611 612 target->setIndexSourceToBuffer(fQuadsIndexBuffer); 613 int quads = 0; 614 drawState->setVertexEdgeType(GrDrawState::kHairQuad_EdgeType); 615 while (quads < quadCnt) { 616 int n = GrMin(quadCnt - quads, kNumQuadsInIdxBuffer); 617 target->drawIndexed(kTriangles_GrPrimitiveType, 618 4 * lineCnt + kVertsPerQuad*quads, // startV 619 0, // startI 620 kVertsPerQuad*n, // vCount 621 kIdxsPerQuad*n); // iCount 622 quads += n; 623 } 624 drawState->setVertexEdgeType(oldEdgeType); 625 return true; 626 } 627
