GrAAConvexPathRenderer.cpp revision c26d94fd7dc0b00cd6d0e42d28285f4a38aff021
1 2/* 3 * Copyright 2012 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 "GrAAConvexPathRenderer.h" 10 11#include "GrContext.h" 12#include "GrDrawState.h" 13#include "GrDrawTargetCaps.h" 14#include "GrPathUtils.h" 15#include "SkString.h" 16#include "SkStrokeRec.h" 17#include "SkTrace.h" 18 19GrAAConvexPathRenderer::GrAAConvexPathRenderer() { 20} 21 22namespace { 23 24struct Segment { 25 enum { 26 // These enum values are assumed in member functions below. 27 kLine = 0, 28 kQuad = 1, 29 } fType; 30 31 // line uses one pt, quad uses 2 pts 32 GrPoint fPts[2]; 33 // normal to edge ending at each pt 34 GrVec fNorms[2]; 35 // is the corner where the previous segment meets this segment 36 // sharp. If so, fMid is a normalized bisector facing outward. 37 GrVec fMid; 38 39 int countPoints() { 40 GR_STATIC_ASSERT(0 == kLine && 1 == kQuad); 41 return fType + 1; 42 } 43 const SkPoint& endPt() const { 44 GR_STATIC_ASSERT(0 == kLine && 1 == kQuad); 45 return fPts[fType]; 46 }; 47 const SkPoint& endNorm() const { 48 GR_STATIC_ASSERT(0 == kLine && 1 == kQuad); 49 return fNorms[fType]; 50 }; 51}; 52 53typedef SkTArray<Segment, true> SegmentArray; 54 55void center_of_mass(const SegmentArray& segments, SkPoint* c) { 56 SkScalar area = 0; 57 SkPoint center = {0, 0}; 58 int count = segments.count(); 59 SkPoint p0 = {0, 0}; 60 if (count > 2) { 61 // We translate the polygon so that the first point is at the origin. 62 // This avoids some precision issues with small area polygons far away 63 // from the origin. 64 p0 = segments[0].endPt(); 65 SkPoint pi; 66 SkPoint pj; 67 // the first and last iteration of the below loop would compute 68 // zeros since the starting / ending point is (0,0). So instead we start 69 // at i=1 and make the last iteration i=count-2. 70 pj = segments[1].endPt() - p0; 71 for (int i = 1; i < count - 1; ++i) { 72 pi = pj; 73 const SkPoint pj = segments[i + 1].endPt() - p0; 74 75 SkScalar t = SkScalarMul(pi.fX, pj.fY) - SkScalarMul(pj.fX, pi.fY); 76 area += t; 77 center.fX += (pi.fX + pj.fX) * t; 78 center.fY += (pi.fY + pj.fY) * t; 79 80 } 81 } 82 // If the poly has no area then we instead return the average of 83 // its points. 84 if (SkScalarNearlyZero(area)) { 85 SkPoint avg; 86 avg.set(0, 0); 87 for (int i = 0; i < count; ++i) { 88 const SkPoint& pt = segments[i].endPt(); 89 avg.fX += pt.fX; 90 avg.fY += pt.fY; 91 } 92 SkScalar denom = SK_Scalar1 / count; 93 avg.scale(denom); 94 *c = avg; 95 } else { 96 area *= 3; 97 area = SkScalarDiv(SK_Scalar1, area); 98 center.fX = SkScalarMul(center.fX, area); 99 center.fY = SkScalarMul(center.fY, area); 100 // undo the translate of p0 to the origin. 101 *c = center + p0; 102 } 103 GrAssert(!SkScalarIsNaN(c->fX) && !SkScalarIsNaN(c->fY)); 104} 105 106void compute_vectors(SegmentArray* segments, 107 SkPoint* fanPt, 108 SkPath::Direction dir, 109 int* vCount, 110 int* iCount) { 111 center_of_mass(*segments, fanPt); 112 int count = segments->count(); 113 114 // Make the normals point towards the outside 115 GrPoint::Side normSide; 116 if (dir == SkPath::kCCW_Direction) { 117 normSide = GrPoint::kRight_Side; 118 } else { 119 normSide = GrPoint::kLeft_Side; 120 } 121 122 *vCount = 0; 123 *iCount = 0; 124 // compute normals at all points 125 for (int a = 0; a < count; ++a) { 126 const Segment& sega = (*segments)[a]; 127 int b = (a + 1) % count; 128 Segment& segb = (*segments)[b]; 129 130 const GrPoint* prevPt = &sega.endPt(); 131 int n = segb.countPoints(); 132 for (int p = 0; p < n; ++p) { 133 segb.fNorms[p] = segb.fPts[p] - *prevPt; 134 segb.fNorms[p].normalize(); 135 segb.fNorms[p].setOrthog(segb.fNorms[p], normSide); 136 prevPt = &segb.fPts[p]; 137 } 138 if (Segment::kLine == segb.fType) { 139 *vCount += 5; 140 *iCount += 9; 141 } else { 142 *vCount += 6; 143 *iCount += 12; 144 } 145 } 146 147 // compute mid-vectors where segments meet. TODO: Detect shallow corners 148 // and leave out the wedges and close gaps by stitching segments together. 149 for (int a = 0; a < count; ++a) { 150 const Segment& sega = (*segments)[a]; 151 int b = (a + 1) % count; 152 Segment& segb = (*segments)[b]; 153 segb.fMid = segb.fNorms[0] + sega.endNorm(); 154 segb.fMid.normalize(); 155 // corner wedges 156 *vCount += 4; 157 *iCount += 6; 158 } 159} 160 161struct DegenerateTestData { 162 DegenerateTestData() { fStage = kInitial; } 163 bool isDegenerate() const { return kNonDegenerate != fStage; } 164 enum { 165 kInitial, 166 kPoint, 167 kLine, 168 kNonDegenerate 169 } fStage; 170 GrPoint fFirstPoint; 171 GrVec fLineNormal; 172 SkScalar fLineC; 173}; 174 175void update_degenerate_test(DegenerateTestData* data, const GrPoint& pt) { 176 static const SkScalar TOL = (SK_Scalar1 / 16); 177 static const SkScalar TOL_SQD = SkScalarMul(TOL, TOL); 178 179 switch (data->fStage) { 180 case DegenerateTestData::kInitial: 181 data->fFirstPoint = pt; 182 data->fStage = DegenerateTestData::kPoint; 183 break; 184 case DegenerateTestData::kPoint: 185 if (pt.distanceToSqd(data->fFirstPoint) > TOL_SQD) { 186 data->fLineNormal = pt - data->fFirstPoint; 187 data->fLineNormal.normalize(); 188 data->fLineNormal.setOrthog(data->fLineNormal); 189 data->fLineC = -data->fLineNormal.dot(data->fFirstPoint); 190 data->fStage = DegenerateTestData::kLine; 191 } 192 break; 193 case DegenerateTestData::kLine: 194 if (SkScalarAbs(data->fLineNormal.dot(pt) + data->fLineC) > TOL) { 195 data->fStage = DegenerateTestData::kNonDegenerate; 196 } 197 case DegenerateTestData::kNonDegenerate: 198 break; 199 default: 200 GrCrash("Unexpected degenerate test stage."); 201 } 202} 203 204inline bool get_direction(const SkPath& path, const SkMatrix& m, SkPath::Direction* dir) { 205 if (!path.cheapComputeDirection(dir)) { 206 return false; 207 } 208 // check whether m reverses the orientation 209 GrAssert(!m.hasPerspective()); 210 SkScalar det2x2 = SkScalarMul(m.get(SkMatrix::kMScaleX), m.get(SkMatrix::kMScaleY)) - 211 SkScalarMul(m.get(SkMatrix::kMSkewX), m.get(SkMatrix::kMSkewY)); 212 if (det2x2 < 0) { 213 *dir = SkPath::OppositeDirection(*dir); 214 } 215 return true; 216} 217 218bool get_segments(const SkPath& path, 219 const SkMatrix& m, 220 SegmentArray* segments, 221 SkPoint* fanPt, 222 int* vCount, 223 int* iCount) { 224 SkPath::Iter iter(path, true); 225 // This renderer over-emphasizes very thin path regions. We use the distance 226 // to the path from the sample to compute coverage. Every pixel intersected 227 // by the path will be hit and the maximum distance is sqrt(2)/2. We don't 228 // notice that the sample may be close to a very thin area of the path and 229 // thus should be very light. This is particularly egregious for degenerate 230 // line paths. We detect paths that are very close to a line (zero area) and 231 // draw nothing. 232 DegenerateTestData degenerateData; 233 SkPath::Direction dir; 234 // get_direction can fail for some degenerate paths. 235 if (!get_direction(path, m, &dir)) { 236 return false; 237 } 238 239 for (;;) { 240 GrPoint pts[4]; 241 GrPathCmd cmd = (GrPathCmd)iter.next(pts); 242 switch (cmd) { 243 case kMove_PathCmd: 244 m.mapPoints(pts, 1); 245 update_degenerate_test(°enerateData, pts[0]); 246 break; 247 case kLine_PathCmd: { 248 m.mapPoints(pts + 1, 1); 249 update_degenerate_test(°enerateData, pts[1]); 250 segments->push_back(); 251 segments->back().fType = Segment::kLine; 252 segments->back().fPts[0] = pts[1]; 253 break; 254 } 255 case kQuadratic_PathCmd: 256 m.mapPoints(pts + 1, 2); 257 update_degenerate_test(°enerateData, pts[1]); 258 update_degenerate_test(°enerateData, pts[2]); 259 segments->push_back(); 260 segments->back().fType = Segment::kQuad; 261 segments->back().fPts[0] = pts[1]; 262 segments->back().fPts[1] = pts[2]; 263 break; 264 case kCubic_PathCmd: { 265 m.mapPoints(pts, 4); 266 update_degenerate_test(°enerateData, pts[1]); 267 update_degenerate_test(°enerateData, pts[2]); 268 update_degenerate_test(°enerateData, pts[3]); 269 // unlike quads and lines, the pts[0] will also be read (in 270 // convertCubicToQuads). 271 SkSTArray<15, SkPoint, true> quads; 272 GrPathUtils::convertCubicToQuads(pts, SK_Scalar1, true, dir, &quads); 273 int count = quads.count(); 274 for (int q = 0; q < count; q += 3) { 275 segments->push_back(); 276 segments->back().fType = Segment::kQuad; 277 segments->back().fPts[0] = quads[q + 1]; 278 segments->back().fPts[1] = quads[q + 2]; 279 } 280 break; 281 }; 282 case kEnd_PathCmd: 283 if (degenerateData.isDegenerate()) { 284 return false; 285 } else { 286 compute_vectors(segments, fanPt, dir, vCount, iCount); 287 return true; 288 } 289 default: 290 break; 291 } 292 } 293} 294 295struct QuadVertex { 296 GrPoint fPos; 297 GrPoint fUV; 298 SkScalar fD0; 299 SkScalar fD1; 300}; 301 302void create_vertices(const SegmentArray& segments, 303 const SkPoint& fanPt, 304 QuadVertex* verts, 305 uint16_t* idxs) { 306 int v = 0; 307 int i = 0; 308 309 int count = segments.count(); 310 for (int a = 0; a < count; ++a) { 311 const Segment& sega = segments[a]; 312 int b = (a + 1) % count; 313 const Segment& segb = segments[b]; 314 315 // FIXME: These tris are inset in the 1 unit arc around the corner 316 verts[v + 0].fPos = sega.endPt(); 317 verts[v + 1].fPos = verts[v + 0].fPos + sega.endNorm(); 318 verts[v + 2].fPos = verts[v + 0].fPos + segb.fMid; 319 verts[v + 3].fPos = verts[v + 0].fPos + segb.fNorms[0]; 320 verts[v + 0].fUV.set(0,0); 321 verts[v + 1].fUV.set(0,-SK_Scalar1); 322 verts[v + 2].fUV.set(0,-SK_Scalar1); 323 verts[v + 3].fUV.set(0,-SK_Scalar1); 324 verts[v + 0].fD0 = verts[v + 0].fD1 = -SK_Scalar1; 325 verts[v + 1].fD0 = verts[v + 1].fD1 = -SK_Scalar1; 326 verts[v + 2].fD0 = verts[v + 2].fD1 = -SK_Scalar1; 327 verts[v + 3].fD0 = verts[v + 3].fD1 = -SK_Scalar1; 328 329 idxs[i + 0] = v + 0; 330 idxs[i + 1] = v + 2; 331 idxs[i + 2] = v + 1; 332 idxs[i + 3] = v + 0; 333 idxs[i + 4] = v + 3; 334 idxs[i + 5] = v + 2; 335 336 v += 4; 337 i += 6; 338 339 if (Segment::kLine == segb.fType) { 340 verts[v + 0].fPos = fanPt; 341 verts[v + 1].fPos = sega.endPt(); 342 verts[v + 2].fPos = segb.fPts[0]; 343 344 verts[v + 3].fPos = verts[v + 1].fPos + segb.fNorms[0]; 345 verts[v + 4].fPos = verts[v + 2].fPos + segb.fNorms[0]; 346 347 // we draw the line edge as a degenerate quad (u is 0, v is the 348 // signed distance to the edge) 349 SkScalar dist = fanPt.distanceToLineBetween(verts[v + 1].fPos, 350 verts[v + 2].fPos); 351 verts[v + 0].fUV.set(0, dist); 352 verts[v + 1].fUV.set(0, 0); 353 verts[v + 2].fUV.set(0, 0); 354 verts[v + 3].fUV.set(0, -SK_Scalar1); 355 verts[v + 4].fUV.set(0, -SK_Scalar1); 356 357 verts[v + 0].fD0 = verts[v + 0].fD1 = -SK_Scalar1; 358 verts[v + 1].fD0 = verts[v + 1].fD1 = -SK_Scalar1; 359 verts[v + 2].fD0 = verts[v + 2].fD1 = -SK_Scalar1; 360 verts[v + 3].fD0 = verts[v + 3].fD1 = -SK_Scalar1; 361 verts[v + 4].fD0 = verts[v + 4].fD1 = -SK_Scalar1; 362 363 idxs[i + 0] = v + 0; 364 idxs[i + 1] = v + 2; 365 idxs[i + 2] = v + 1; 366 367 idxs[i + 3] = v + 3; 368 idxs[i + 4] = v + 1; 369 idxs[i + 5] = v + 2; 370 371 idxs[i + 6] = v + 4; 372 idxs[i + 7] = v + 3; 373 idxs[i + 8] = v + 2; 374 375 v += 5; 376 i += 9; 377 } else { 378 GrPoint qpts[] = {sega.endPt(), segb.fPts[0], segb.fPts[1]}; 379 380 GrVec midVec = segb.fNorms[0] + segb.fNorms[1]; 381 midVec.normalize(); 382 383 verts[v + 0].fPos = fanPt; 384 verts[v + 1].fPos = qpts[0]; 385 verts[v + 2].fPos = qpts[2]; 386 verts[v + 3].fPos = qpts[0] + segb.fNorms[0]; 387 verts[v + 4].fPos = qpts[2] + segb.fNorms[1]; 388 verts[v + 5].fPos = qpts[1] + midVec; 389 390 SkScalar c = segb.fNorms[0].dot(qpts[0]); 391 verts[v + 0].fD0 = -segb.fNorms[0].dot(fanPt) + c; 392 verts[v + 1].fD0 = 0.f; 393 verts[v + 2].fD0 = -segb.fNorms[0].dot(qpts[2]) + c; 394 verts[v + 3].fD0 = -SK_ScalarMax/100; 395 verts[v + 4].fD0 = -SK_ScalarMax/100; 396 verts[v + 5].fD0 = -SK_ScalarMax/100; 397 398 c = segb.fNorms[1].dot(qpts[2]); 399 verts[v + 0].fD1 = -segb.fNorms[1].dot(fanPt) + c; 400 verts[v + 1].fD1 = -segb.fNorms[1].dot(qpts[0]) + c; 401 verts[v + 2].fD1 = 0.f; 402 verts[v + 3].fD1 = -SK_ScalarMax/100; 403 verts[v + 4].fD1 = -SK_ScalarMax/100; 404 verts[v + 5].fD1 = -SK_ScalarMax/100; 405 406 GrPathUtils::QuadUVMatrix toUV(qpts); 407 toUV.apply<6, sizeof(QuadVertex), sizeof(GrPoint)>(verts + v); 408 409 idxs[i + 0] = v + 3; 410 idxs[i + 1] = v + 1; 411 idxs[i + 2] = v + 2; 412 idxs[i + 3] = v + 4; 413 idxs[i + 4] = v + 3; 414 idxs[i + 5] = v + 2; 415 416 idxs[i + 6] = v + 5; 417 idxs[i + 7] = v + 3; 418 idxs[i + 8] = v + 4; 419 420 idxs[i + 9] = v + 0; 421 idxs[i + 10] = v + 2; 422 idxs[i + 11] = v + 1; 423 424 v += 6; 425 i += 12; 426 } 427 } 428} 429 430} 431 432bool GrAAConvexPathRenderer::canDrawPath(const SkPath& path, 433 const SkStrokeRec& stroke, 434 const GrDrawTarget* target, 435 bool antiAlias) const { 436 return (target->caps()->shaderDerivativeSupport() && antiAlias && 437 stroke.isFillStyle() && !path.isInverseFillType() && path.isConvex()); 438} 439 440bool GrAAConvexPathRenderer::onDrawPath(const SkPath& origPath, 441 const SkStrokeRec&, 442 GrDrawTarget* target, 443 bool antiAlias) { 444 445 const SkPath* path = &origPath; 446 if (path->isEmpty()) { 447 return true; 448 } 449 GrDrawState* drawState = target->drawState(); 450 451 GrDrawState::AutoDeviceCoordDraw adcd(drawState); 452 if (!adcd.succeeded()) { 453 return false; 454 } 455 const SkMatrix* vm = &adcd.getOriginalMatrix(); 456 457 // We use the fact that SkPath::transform path does subdivision based on 458 // perspective. Otherwise, we apply the view matrix when copying to the 459 // segment representation. 460 SkPath tmpPath; 461 if (vm->hasPerspective()) { 462 origPath.transform(*vm, &tmpPath); 463 path = &tmpPath; 464 vm = &SkMatrix::I(); 465 } 466 467 QuadVertex *verts; 468 uint16_t* idxs; 469 470 int vCount; 471 int iCount; 472 enum { 473 kPreallocSegmentCnt = 512 / sizeof(Segment), 474 }; 475 SkSTArray<kPreallocSegmentCnt, Segment, true> segments; 476 SkPoint fanPt; 477 478 if (!get_segments(*path, *vm, &segments, &fanPt, &vCount, &iCount)) { 479 return false; 480 } 481 482 // position + edge 483 static const GrVertexAttrib kAttribs[] = { 484 {kVec2f_GrVertexAttribType, 0}, 485 {kVec4f_GrVertexAttribType, sizeof(GrPoint)} 486 }; 487 static const GrAttribBindings bindings = GrDrawState::kEdge_AttribBindingsBit; 488 489 drawState->setVertexAttribs(kAttribs, SK_ARRAY_COUNT(kAttribs)); 490 drawState->setAttribIndex(GrDrawState::kPosition_AttribIndex, 0); 491 drawState->setAttribIndex(GrDrawState::kEdge_AttribIndex, 1); 492 drawState->setAttribBindings(bindings); 493 GrDrawTarget::AutoReleaseGeometry arg(target, vCount, iCount); 494 if (!arg.succeeded()) { 495 return false; 496 } 497 GrAssert(sizeof(QuadVertex) == drawState->getVertexSize()); 498 verts = reinterpret_cast<QuadVertex*>(arg.vertices()); 499 idxs = reinterpret_cast<uint16_t*>(arg.indices()); 500 501 create_vertices(segments, fanPt, verts, idxs); 502 503 GrDrawState::VertexEdgeType oldEdgeType = drawState->getVertexEdgeType(); 504 drawState->setVertexEdgeType(GrDrawState::kQuad_EdgeType); 505 target->drawIndexed(kTriangles_GrPrimitiveType, 506 0, // start vertex 507 0, // start index 508 vCount, 509 iCount); 510 drawState->setVertexEdgeType(oldEdgeType); 511 512 return true; 513} 514