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 10 #include "GrTesselatedPathRenderer.h" 11 12 #include "GrDrawState.h" 13 #include "GrPathUtils.h" 14 #include "GrPoint.h" 15 #include "GrRenderTarget.h" 16 #include "GrTDArray.h" 17 18 #include "SkTemplates.h" 19 20 #include <limits.h> 21 #include <sk_glu.h> 22 23 typedef GrTDArray<GrDrawState::Edge> GrEdgeArray; 24 typedef GrTDArray<GrPoint> GrPointArray; 25 typedef GrTDArray<uint16_t> GrIndexArray; 26 typedef void (*TESSCB)(); 27 28 // limit the allowable vertex range to approximately half of the representable 29 // IEEE exponent in order to avoid overflow when doing multiplies between 30 // vertex components, 31 const float kMaxVertexValue = 1e18f; 32 33 static inline GrDrawState::Edge computeEdge(const GrPoint& p, 34 const GrPoint& q, 35 float sign) { 36 GrVec tangent = GrVec::Make(p.fY - q.fY, q.fX - p.fX); 37 float scale = sign / tangent.length(); 38 float cross2 = p.fX * q.fY - q.fX * p.fY; 39 return GrDrawState::Edge(tangent.fX * scale, 40 tangent.fY * scale, 41 cross2 * scale); 42 } 43 44 static inline GrPoint sanitizePoint(const GrPoint& pt) { 45 GrPoint r; 46 r.fX = SkScalarPin(pt.fX, -kMaxVertexValue, kMaxVertexValue); 47 r.fY = SkScalarPin(pt.fY, -kMaxVertexValue, kMaxVertexValue); 48 return r; 49 } 50 51 class GrTess { 52 public: 53 GrTess(int count, unsigned winding_rule) { 54 fTess = Sk_gluNewTess(); 55 Sk_gluTessProperty(fTess, GLU_TESS_WINDING_RULE, winding_rule); 56 Sk_gluTessNormal(fTess, 0.0f, 0.0f, 1.0f); 57 Sk_gluTessCallback(fTess, GLU_TESS_BEGIN_DATA, (TESSCB) &beginCB); 58 Sk_gluTessCallback(fTess, GLU_TESS_VERTEX_DATA, (TESSCB) &vertexCB); 59 Sk_gluTessCallback(fTess, GLU_TESS_END_DATA, (TESSCB) &endCB); 60 Sk_gluTessCallback(fTess, GLU_TESS_EDGE_FLAG_DATA, (TESSCB) &edgeFlagCB); 61 Sk_gluTessCallback(fTess, GLU_TESS_COMBINE_DATA, (TESSCB) &combineCB); 62 fInVertices = new double[count * 3]; 63 } 64 virtual ~GrTess() { 65 Sk_gluDeleteTess(fTess); 66 delete[] fInVertices; 67 } 68 void addVertex(const GrPoint& pt, int index) { 69 if (index > USHRT_MAX) return; 70 double* inVertex = &fInVertices[index * 3]; 71 inVertex[0] = pt.fX; 72 inVertex[1] = pt.fY; 73 inVertex[2] = 0.0; 74 *fVertices.append() = pt; 75 Sk_gluTessVertex(fTess, inVertex, reinterpret_cast<void*>(index)); 76 } 77 void addVertices(const GrPoint* points, const uint16_t* contours, int numContours) { 78 Sk_gluTessBeginPolygon(fTess, this); 79 size_t i = 0; 80 for (int j = 0; j < numContours; ++j) { 81 Sk_gluTessBeginContour(fTess); 82 size_t end = i + contours[j]; 83 for (; i < end; ++i) { 84 addVertex(points[i], i); 85 } 86 Sk_gluTessEndContour(fTess); 87 } 88 Sk_gluTessEndPolygon(fTess); 89 } 90 GLUtesselator* tess() { return fTess; } 91 const GrPointArray& vertices() const { return fVertices; } 92 protected: 93 virtual void begin(GLenum type) = 0; 94 virtual void vertex(int index) = 0; 95 virtual void edgeFlag(bool flag) = 0; 96 virtual void end() = 0; 97 virtual int combine(GLdouble coords[3], int vertexIndices[4], 98 GLfloat weight[4]) = 0; 99 static void beginCB(GLenum type, void* data) { 100 static_cast<GrTess*>(data)->begin(type); 101 } 102 static void vertexCB(void* vertexData, void* data) { 103 static_cast<GrTess*>(data)->vertex(reinterpret_cast<long>(vertexData)); 104 } 105 static void edgeFlagCB(GLboolean flag, void* data) { 106 static_cast<GrTess*>(data)->edgeFlag(flag != 0); 107 } 108 static void endCB(void* data) { 109 static_cast<GrTess*>(data)->end(); 110 } 111 static void combineCB(GLdouble coords[3], void* vertexData[4], 112 GLfloat weight[4], void **outData, void* data) { 113 int vertexIndex[4]; 114 vertexIndex[0] = reinterpret_cast<long>(vertexData[0]); 115 vertexIndex[1] = reinterpret_cast<long>(vertexData[1]); 116 vertexIndex[2] = reinterpret_cast<long>(vertexData[2]); 117 vertexIndex[3] = reinterpret_cast<long>(vertexData[3]); 118 GrTess* tess = static_cast<GrTess*>(data); 119 int outIndex = tess->combine(coords, vertexIndex, weight); 120 *reinterpret_cast<long*>(outData) = outIndex; 121 } 122 protected: 123 GLUtesselator* fTess; 124 GrPointArray fVertices; 125 double* fInVertices; 126 }; 127 128 class GrPolygonTess : public GrTess { 129 public: 130 GrPolygonTess(int count, unsigned winding_rule) 131 : GrTess(count, winding_rule) { 132 } 133 ~GrPolygonTess() { 134 } 135 const GrIndexArray& indices() const { return fIndices; } 136 protected: 137 virtual void begin(GLenum type) { 138 GR_DEBUGASSERT(type == GL_TRIANGLES); 139 } 140 virtual void vertex(int index) { 141 *fIndices.append() = index; 142 } 143 virtual void edgeFlag(bool flag) {} 144 virtual void end() {} 145 virtual int combine(GLdouble coords[3], int vertexIndices[4], 146 GLfloat weight[4]) { 147 int index = fVertices.count(); 148 GrPoint p = GrPoint::Make(static_cast<float>(coords[0]), 149 static_cast<float>(coords[1])); 150 *fVertices.append() = p; 151 return index; 152 } 153 protected: 154 GrIndexArray fIndices; 155 }; 156 157 class GrEdgePolygonTess : public GrPolygonTess { 158 public: 159 GrEdgePolygonTess(int count, unsigned winding_rule, const SkMatrix& matrix) 160 : GrPolygonTess(count, winding_rule), 161 fMatrix(matrix), 162 fEdgeFlag(false), 163 fEdgeVertex(-1), 164 fTriStartVertex(-1), 165 fEdges(NULL) { 166 } 167 ~GrEdgePolygonTess() { 168 delete[] fEdges; 169 } 170 const GrDrawState::Edge* edges() const { return fEdges; } 171 private: 172 void addEdge(int index0, int index1) { 173 GrPoint p = fVertices[index0]; 174 GrPoint q = fVertices[index1]; 175 fMatrix.mapPoints(&p, 1); 176 fMatrix.mapPoints(&q, 1); 177 p = sanitizePoint(p); 178 q = sanitizePoint(q); 179 if (p == q) return; 180 GrDrawState::Edge edge = computeEdge(p, q, 1.0f); 181 fEdges[index0 * 2 + 1] = edge; 182 fEdges[index1 * 2] = edge; 183 } 184 virtual void begin(GLenum type) { 185 GR_DEBUGASSERT(type == GL_TRIANGLES); 186 int count = fVertices.count() * 2; 187 fEdges = new GrDrawState::Edge[count]; 188 memset(fEdges, 0, count * sizeof(GrDrawState::Edge)); 189 } 190 virtual void edgeFlag(bool flag) { 191 fEdgeFlag = flag; 192 } 193 virtual void vertex(int index) { 194 bool triStart = fIndices.count() % 3 == 0; 195 GrPolygonTess::vertex(index); 196 if (fEdgeVertex != -1) { 197 if (triStart) { 198 addEdge(fEdgeVertex, fTriStartVertex); 199 } else { 200 addEdge(fEdgeVertex, index); 201 } 202 } 203 if (triStart) { 204 fTriStartVertex = index; 205 } 206 if (fEdgeFlag) { 207 fEdgeVertex = index; 208 } else { 209 fEdgeVertex = -1; 210 } 211 } 212 virtual void end() { 213 if (fEdgeVertex != -1) { 214 addEdge(fEdgeVertex, fTriStartVertex); 215 } 216 } 217 GrMatrix fMatrix; 218 bool fEdgeFlag; 219 int fEdgeVertex, fTriStartVertex; 220 GrDrawState::Edge* fEdges; 221 }; 222 223 class GrBoundaryTess : public GrTess { 224 public: 225 GrBoundaryTess(int count, unsigned winding_rule) 226 : GrTess(count, winding_rule), 227 fContourStart(0) { 228 Sk_gluTessProperty(fTess, GLU_TESS_BOUNDARY_ONLY, 1); 229 } 230 ~GrBoundaryTess() { 231 } 232 GrPointArray& contourPoints() { return fContourPoints; } 233 const GrIndexArray& contours() const { return fContours; } 234 private: 235 virtual void begin(GLenum type) { 236 fContourStart = fContourPoints.count(); 237 } 238 virtual void vertex(int index) { 239 *fContourPoints.append() = fVertices.at(index); 240 } 241 virtual void edgeFlag(bool flag) {} 242 virtual void end() { 243 *fContours.append() = fContourPoints.count() - fContourStart; 244 } 245 virtual int combine(GLdouble coords[3], int vertexIndices[4], 246 GLfloat weight[4]) { 247 int index = fVertices.count(); 248 *fVertices.append() = GrPoint::Make(static_cast<float>(coords[0]), 249 static_cast<float>(coords[1])); 250 return index; 251 } 252 GrPointArray fContourPoints; 253 GrIndexArray fContours; 254 size_t fContourStart; 255 }; 256 257 static bool nearlyEqual(float a, float b) { 258 return fabsf(a - b) < 0.0001f; 259 } 260 261 static bool nearlyEqual(const GrPoint& a, const GrPoint& b) { 262 return nearlyEqual(a.fX, b.fX) && nearlyEqual(a.fY, b.fY); 263 } 264 265 static bool parallel(const GrDrawState::Edge& a, const GrDrawState::Edge& b) { 266 return (nearlyEqual(a.fX, b.fX) && nearlyEqual(a.fY, b.fY)) || 267 (nearlyEqual(a.fX, -b.fX) && nearlyEqual(a.fY, -b.fY)); 268 } 269 270 static unsigned fill_type_to_glu_winding_rule(GrPathFill fill) { 271 switch (fill) { 272 case kWinding_PathFill: 273 return GLU_TESS_WINDING_NONZERO; 274 case kEvenOdd_PathFill: 275 return GLU_TESS_WINDING_ODD; 276 case kInverseWinding_PathFill: 277 return GLU_TESS_WINDING_POSITIVE; 278 case kInverseEvenOdd_PathFill: 279 return GLU_TESS_WINDING_ODD; 280 case kHairLine_PathFill: 281 return GLU_TESS_WINDING_NONZERO; // FIXME: handle this 282 default: 283 GrAssert(!"Unknown path fill!"); 284 return 0; 285 } 286 } 287 288 GrTesselatedPathRenderer::GrTesselatedPathRenderer() { 289 } 290 291 static bool isCCW(const GrPoint* pts, int count) { 292 GrVec v1, v2; 293 do { 294 v1 = pts[1] - pts[0]; 295 v2 = pts[2] - pts[1]; 296 pts++; 297 count--; 298 } while (nearlyEqual(v1, v2) && count > 3); 299 return v1.cross(v2) < 0; 300 } 301 302 static bool validEdge(const GrDrawState::Edge& edge) { 303 return !(edge.fX == 0.0f && edge.fY == 0.0f && edge.fZ == 0.0f); 304 } 305 306 static size_t computeEdgesAndIntersect(const GrMatrix& matrix, 307 const GrMatrix& inverse, 308 GrPoint* vertices, 309 size_t numVertices, 310 GrEdgeArray* edges, 311 float sign) { 312 if (numVertices < 3) { 313 return 0; 314 } 315 matrix.mapPoints(vertices, numVertices); 316 if (sign == 0.0f) { 317 sign = isCCW(vertices, numVertices) ? -1.0f : 1.0f; 318 } 319 GrPoint p = sanitizePoint(vertices[numVertices - 1]); 320 for (size_t i = 0; i < numVertices; ++i) { 321 GrPoint q = sanitizePoint(vertices[i]); 322 if (p == q) { 323 continue; 324 } 325 GrDrawState::Edge edge = computeEdge(p, q, sign); 326 edge.fZ += 0.5f; // Offset by half a pixel along the tangent. 327 *edges->append() = edge; 328 p = q; 329 } 330 int count = edges->count(); 331 if (count == 0) { 332 return 0; 333 } 334 GrDrawState::Edge prev_edge = edges->at(0); 335 for (int i = 0; i < count; ++i) { 336 GrDrawState::Edge edge = edges->at(i < count - 1 ? i + 1 : 0); 337 if (parallel(edge, prev_edge)) { 338 // 3 points are collinear; offset by half the tangent instead 339 vertices[i].fX -= edge.fX * 0.5f; 340 vertices[i].fY -= edge.fY * 0.5f; 341 } else { 342 vertices[i] = prev_edge.intersect(edge); 343 } 344 inverse.mapPoints(&vertices[i], 1); 345 prev_edge = edge; 346 } 347 return edges->count(); 348 } 349 350 bool GrTesselatedPathRenderer::onDrawPath(const SkPath& path, 351 GrPathFill fill, 352 const GrVec* translate, 353 GrDrawTarget* target, 354 GrDrawState::StageMask stageMask, 355 bool antiAlias) { 356 357 GrDrawTarget::AutoStateRestore asr(target); 358 GrDrawState* drawState = target->drawState(); 359 // face culling doesn't make sense here 360 GrAssert(GrDrawState::kBoth_DrawFace == drawState->getDrawFace()); 361 362 GrMatrix viewM = drawState->getViewMatrix(); 363 364 GrScalar tol = GR_Scalar1; 365 tol = GrPathUtils::scaleToleranceToSrc(tol, viewM, path.getBounds()); 366 GrScalar tolSqd = GrMul(tol, tol); 367 368 int subpathCnt; 369 int maxPts = GrPathUtils::worstCasePointCount(path, &subpathCnt, tol); 370 371 GrVertexLayout layout = 0; 372 for (int s = 0; s < GrDrawState::kNumStages; ++s) { 373 if ((1 << s) & stageMask) { 374 layout |= GrDrawTarget::StagePosAsTexCoordVertexLayoutBit(s); 375 } 376 } 377 378 bool inverted = GrIsFillInverted(fill); 379 if (inverted) { 380 maxPts += 4; 381 subpathCnt++; 382 } 383 if (maxPts > USHRT_MAX) { 384 return false; 385 } 386 SkAutoSTMalloc<8, GrPoint> baseMem(maxPts); 387 GrPoint* base = baseMem; 388 GrPoint* vert = base; 389 GrPoint* subpathBase = base; 390 391 SkAutoSTMalloc<8, uint16_t> subpathVertCount(subpathCnt); 392 393 GrPoint pts[4]; 394 SkPath::Iter iter(path, false); 395 396 bool first = true; 397 int subpath = 0; 398 399 for (;;) { 400 switch (iter.next(pts)) { 401 case kMove_PathCmd: 402 if (!first) { 403 subpathVertCount[subpath] = vert-subpathBase; 404 subpathBase = vert; 405 ++subpath; 406 } 407 *vert = pts[0]; 408 vert++; 409 break; 410 case kLine_PathCmd: 411 *vert = pts[1]; 412 vert++; 413 break; 414 case kQuadratic_PathCmd: { 415 GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2], 416 tolSqd, &vert, 417 GrPathUtils::quadraticPointCount(pts, tol)); 418 break; 419 } 420 case kCubic_PathCmd: { 421 GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3], 422 tolSqd, &vert, 423 GrPathUtils::cubicPointCount(pts, tol)); 424 break; 425 } 426 case kClose_PathCmd: 427 break; 428 case kEnd_PathCmd: 429 subpathVertCount[subpath] = vert-subpathBase; 430 ++subpath; // this could be only in debug 431 goto FINISHED; 432 } 433 first = false; 434 } 435 FINISHED: 436 if (NULL != translate && 0 != translate->fX && 0 != translate->fY) { 437 for (int i = 0; i < vert - base; i++) { 438 base[i].offset(translate->fX, translate->fY); 439 } 440 } 441 442 if (inverted) { 443 GrRect bounds; 444 GrAssert(NULL != drawState->getRenderTarget()); 445 bounds.setLTRB(0, 0, 446 GrIntToScalar(drawState->getRenderTarget()->width()), 447 GrIntToScalar(drawState->getRenderTarget()->height())); 448 GrMatrix vmi; 449 if (drawState->getViewInverse(&vmi)) { 450 vmi.mapRect(&bounds); 451 } 452 *vert++ = GrPoint::Make(bounds.fLeft, bounds.fTop); 453 *vert++ = GrPoint::Make(bounds.fLeft, bounds.fBottom); 454 *vert++ = GrPoint::Make(bounds.fRight, bounds.fBottom); 455 *vert++ = GrPoint::Make(bounds.fRight, bounds.fTop); 456 subpathVertCount[subpath++] = 4; 457 } 458 459 GrAssert(subpath == subpathCnt); 460 GrAssert((vert - base) <= maxPts); 461 462 size_t count = vert - base; 463 464 if (count < 3) { 465 return true; 466 } 467 468 if (subpathCnt == 1 && !inverted && path.isConvex()) { 469 if (antiAlias) { 470 GrEdgeArray edges; 471 GrMatrix inverse, matrix = drawState->getViewMatrix(); 472 drawState->getViewInverse(&inverse); 473 474 count = computeEdgesAndIntersect(matrix, inverse, base, count, &edges, 0.0f); 475 size_t maxEdges = target->getMaxEdges(); 476 if (count == 0) { 477 return true; 478 } 479 if (count <= maxEdges) { 480 // All edges fit; upload all edges and draw all verts as a fan 481 target->setVertexSourceToArray(layout, base, count); 482 drawState->setEdgeAAData(&edges[0], count); 483 target->drawNonIndexed(kTriangleFan_PrimitiveType, 0, count); 484 } else { 485 // Upload "maxEdges" edges and verts at a time, and draw as 486 // separate fans 487 for (size_t i = 0; i < count - 2; i += maxEdges - 2) { 488 edges[i] = edges[0]; 489 base[i] = base[0]; 490 int size = GR_CT_MIN(count - i, maxEdges); 491 target->setVertexSourceToArray(layout, &base[i], size); 492 drawState->setEdgeAAData(&edges[i], size); 493 target->drawNonIndexed(kTriangleFan_PrimitiveType, 0, size); 494 } 495 } 496 drawState->setEdgeAAData(NULL, 0); 497 } else { 498 target->setVertexSourceToArray(layout, base, count); 499 target->drawNonIndexed(kTriangleFan_PrimitiveType, 0, count); 500 } 501 return true; 502 } 503 504 if (antiAlias) { 505 // Run the tesselator once to get the boundaries. 506 GrBoundaryTess btess(count, fill_type_to_glu_winding_rule(fill)); 507 btess.addVertices(base, subpathVertCount, subpathCnt); 508 509 GrMatrix inverse, matrix = drawState->getViewMatrix(); 510 if (!drawState->getViewInverse(&inverse)) { 511 return false; 512 } 513 514 if (btess.vertices().count() > USHRT_MAX) { 515 return false; 516 } 517 518 // Inflate the boundary, and run the tesselator again to generate 519 // interior polys. 520 const GrPointArray& contourPoints = btess.contourPoints(); 521 const GrIndexArray& contours = btess.contours(); 522 GrEdgePolygonTess ptess(contourPoints.count(), GLU_TESS_WINDING_NONZERO, matrix); 523 524 size_t i = 0; 525 Sk_gluTessBeginPolygon(ptess.tess(), &ptess); 526 for (int contour = 0; contour < contours.count(); ++contour) { 527 int count = contours[contour]; 528 GrEdgeArray edges; 529 int newCount = computeEdgesAndIntersect(matrix, inverse, &btess.contourPoints()[i], count, &edges, 1.0f); 530 Sk_gluTessBeginContour(ptess.tess()); 531 for (int j = 0; j < newCount; j++) { 532 ptess.addVertex(contourPoints[i + j], ptess.vertices().count()); 533 } 534 i += count; 535 Sk_gluTessEndContour(ptess.tess()); 536 } 537 538 Sk_gluTessEndPolygon(ptess.tess()); 539 540 if (ptess.vertices().count() > USHRT_MAX) { 541 return false; 542 } 543 544 // Draw the resulting polys and upload their edge data. 545 drawState->enableState(GrDrawState::kEdgeAAConcave_StateBit); 546 const GrPointArray& vertices = ptess.vertices(); 547 const GrIndexArray& indices = ptess.indices(); 548 const GrDrawState::Edge* edges = ptess.edges(); 549 GR_DEBUGASSERT(indices.count() % 3 == 0); 550 for (int i = 0; i < indices.count(); i += 3) { 551 GrPoint tri_verts[3]; 552 int index0 = indices[i]; 553 int index1 = indices[i + 1]; 554 int index2 = indices[i + 2]; 555 tri_verts[0] = vertices[index0]; 556 tri_verts[1] = vertices[index1]; 557 tri_verts[2] = vertices[index2]; 558 GrDrawState::Edge tri_edges[6]; 559 int t = 0; 560 const GrDrawState::Edge& edge0 = edges[index0 * 2]; 561 const GrDrawState::Edge& edge1 = edges[index0 * 2 + 1]; 562 const GrDrawState::Edge& edge2 = edges[index1 * 2]; 563 const GrDrawState::Edge& edge3 = edges[index1 * 2 + 1]; 564 const GrDrawState::Edge& edge4 = edges[index2 * 2]; 565 const GrDrawState::Edge& edge5 = edges[index2 * 2 + 1]; 566 if (validEdge(edge0) && validEdge(edge1)) { 567 tri_edges[t++] = edge0; 568 tri_edges[t++] = edge1; 569 } 570 if (validEdge(edge2) && validEdge(edge3)) { 571 tri_edges[t++] = edge2; 572 tri_edges[t++] = edge3; 573 } 574 if (validEdge(edge4) && validEdge(edge5)) { 575 tri_edges[t++] = edge4; 576 tri_edges[t++] = edge5; 577 } 578 drawState->setEdgeAAData(&tri_edges[0], t); 579 target->setVertexSourceToArray(layout, &tri_verts[0], 3); 580 target->drawNonIndexed(kTriangles_PrimitiveType, 0, 3); 581 } 582 drawState->setEdgeAAData(NULL, 0); 583 drawState->disableState(GrDrawState::kEdgeAAConcave_StateBit); 584 return true; 585 } 586 587 GrPolygonTess ptess(count, fill_type_to_glu_winding_rule(fill)); 588 ptess.addVertices(base, subpathVertCount, subpathCnt); 589 const GrPointArray& vertices = ptess.vertices(); 590 const GrIndexArray& indices = ptess.indices(); 591 if (indices.count() > 0) { 592 target->setVertexSourceToArray(layout, vertices.begin(), vertices.count()); 593 target->setIndexSourceToArray(indices.begin(), indices.count()); 594 target->drawIndexed(kTriangles_PrimitiveType, 595 0, 596 0, 597 vertices.count(), 598 indices.count()); 599 } 600 return true; 601 } 602 603 bool GrTesselatedPathRenderer::canDrawPath(const SkPath& path, 604 GrPathFill fill, 605 const GrDrawTarget* target, 606 bool antiAlias) const { 607 return kHairLine_PathFill != fill; 608 } 609 610