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