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 "SkAnalyticEdge.h" 9 #include "SkEdge.h" 10 #include "SkEdgeBuilder.h" 11 #include "SkEdgeClipper.h" 12 #include "SkGeometry.h" 13 #include "SkLineClipper.h" 14 #include "SkPath.h" 15 #include "SkPathPriv.h" 16 #include "SkSafeMath.h" 17 #include "SkTo.h" 18 19 SkEdgeBuilder::Combine SkBasicEdgeBuilder::combineVertical(const SkEdge* edge, SkEdge* last) { 20 if (last->fCurveCount || last->fDX || edge->fX != last->fX) { 21 return kNo_Combine; 22 } 23 if (edge->fWinding == last->fWinding) { 24 if (edge->fLastY + 1 == last->fFirstY) { 25 last->fFirstY = edge->fFirstY; 26 return kPartial_Combine; 27 } 28 if (edge->fFirstY == last->fLastY + 1) { 29 last->fLastY = edge->fLastY; 30 return kPartial_Combine; 31 } 32 return kNo_Combine; 33 } 34 if (edge->fFirstY == last->fFirstY) { 35 if (edge->fLastY == last->fLastY) { 36 return kTotal_Combine; 37 } 38 if (edge->fLastY < last->fLastY) { 39 last->fFirstY = edge->fLastY + 1; 40 return kPartial_Combine; 41 } 42 last->fFirstY = last->fLastY + 1; 43 last->fLastY = edge->fLastY; 44 last->fWinding = edge->fWinding; 45 return kPartial_Combine; 46 } 47 if (edge->fLastY == last->fLastY) { 48 if (edge->fFirstY > last->fFirstY) { 49 last->fLastY = edge->fFirstY - 1; 50 return kPartial_Combine; 51 } 52 last->fLastY = last->fFirstY - 1; 53 last->fFirstY = edge->fFirstY; 54 last->fWinding = edge->fWinding; 55 return kPartial_Combine; 56 } 57 return kNo_Combine; 58 } 59 60 SkEdgeBuilder::Combine SkAnalyticEdgeBuilder::combineVertical(const SkAnalyticEdge* edge, 61 SkAnalyticEdge* last) { 62 auto approximately_equal = [](SkFixed a, SkFixed b) { 63 return SkAbs32(a - b) < 0x100; 64 }; 65 66 if (last->fCurveCount || last->fDX || edge->fX != last->fX) { 67 return kNo_Combine; 68 } 69 if (edge->fWinding == last->fWinding) { 70 if (edge->fLowerY == last->fUpperY) { 71 last->fUpperY = edge->fUpperY; 72 last->fY = last->fUpperY; 73 return kPartial_Combine; 74 } 75 if (approximately_equal(edge->fUpperY, last->fLowerY)) { 76 last->fLowerY = edge->fLowerY; 77 return kPartial_Combine; 78 } 79 return kNo_Combine; 80 } 81 if (approximately_equal(edge->fUpperY, last->fUpperY)) { 82 if (approximately_equal(edge->fLowerY, last->fLowerY)) { 83 return kTotal_Combine; 84 } 85 if (edge->fLowerY < last->fLowerY) { 86 last->fUpperY = edge->fLowerY; 87 last->fY = last->fUpperY; 88 return kPartial_Combine; 89 } 90 last->fUpperY = last->fLowerY; 91 last->fY = last->fUpperY; 92 last->fLowerY = edge->fLowerY; 93 last->fWinding = edge->fWinding; 94 return kPartial_Combine; 95 } 96 if (approximately_equal(edge->fLowerY, last->fLowerY)) { 97 if (edge->fUpperY > last->fUpperY) { 98 last->fLowerY = edge->fUpperY; 99 return kPartial_Combine; 100 } 101 last->fLowerY = last->fUpperY; 102 last->fUpperY = edge->fUpperY; 103 last->fY = last->fUpperY; 104 last->fWinding = edge->fWinding; 105 return kPartial_Combine; 106 } 107 return kNo_Combine; 108 } 109 110 template <typename Edge> 111 static bool is_vertical(const Edge* edge) { 112 return edge->fDX == 0 113 && edge->fCurveCount == 0; 114 } 115 116 // TODO: we can deallocate the edge if edge->setFoo() fails 117 // or when we don't use it (kPartial_Combine or kTotal_Combine). 118 119 void SkBasicEdgeBuilder::addLine(const SkPoint pts[]) { 120 SkEdge* edge = fAlloc.make<SkEdge>(); 121 if (edge->setLine(pts[0], pts[1], fClipShift)) { 122 Combine combine = is_vertical(edge) && !fList.empty() 123 ? this->combineVertical(edge, (SkEdge*)fList.top()) 124 : kNo_Combine; 125 126 switch (combine) { 127 case kTotal_Combine: fList.pop(); break; 128 case kPartial_Combine: break; 129 case kNo_Combine: fList.push_back(edge); break; 130 } 131 } 132 } 133 void SkAnalyticEdgeBuilder::addLine(const SkPoint pts[]) { 134 SkAnalyticEdge* edge = fAlloc.make<SkAnalyticEdge>(); 135 if (edge->setLine(pts[0], pts[1])) { 136 137 Combine combine = is_vertical(edge) && !fList.empty() 138 ? this->combineVertical(edge, (SkAnalyticEdge*)fList.top()) 139 : kNo_Combine; 140 141 switch (combine) { 142 case kTotal_Combine: fList.pop(); break; 143 case kPartial_Combine: break; 144 case kNo_Combine: fList.push_back(edge); break; 145 } 146 } 147 } 148 void SkBezierEdgeBuilder::addLine(const SkPoint pts[]) { 149 SkLine* line = fAlloc.make<SkLine>(); 150 if (line->set(pts)) { 151 fList.push_back(line); 152 } 153 } 154 155 void SkBasicEdgeBuilder::addQuad(const SkPoint pts[]) { 156 SkQuadraticEdge* edge = fAlloc.make<SkQuadraticEdge>(); 157 if (edge->setQuadratic(pts, fClipShift)) { 158 fList.push_back(edge); 159 } 160 } 161 void SkAnalyticEdgeBuilder::addQuad(const SkPoint pts[]) { 162 SkAnalyticQuadraticEdge* edge = fAlloc.make<SkAnalyticQuadraticEdge>(); 163 if (edge->setQuadratic(pts)) { 164 fList.push_back(edge); 165 } 166 } 167 void SkBezierEdgeBuilder::addQuad(const SkPoint pts[]) { 168 SkQuad* quad = fAlloc.make<SkQuad>(); 169 if (quad->set(pts)) { 170 fList.push_back(quad); 171 } 172 } 173 174 void SkBasicEdgeBuilder::addCubic(const SkPoint pts[]) { 175 SkCubicEdge* edge = fAlloc.make<SkCubicEdge>(); 176 if (edge->setCubic(pts, fClipShift)) { 177 fList.push_back(edge); 178 } 179 } 180 void SkAnalyticEdgeBuilder::addCubic(const SkPoint pts[]) { 181 SkAnalyticCubicEdge* edge = fAlloc.make<SkAnalyticCubicEdge>(); 182 if (edge->setCubic(pts)) { 183 fList.push_back(edge); 184 } 185 } 186 void SkBezierEdgeBuilder::addCubic(const SkPoint pts[]) { 187 SkCubic* cubic = fAlloc.make<SkCubic>(); 188 if (cubic->set(pts)) { 189 fList.push_back(cubic); 190 } 191 } 192 193 // TODO: merge addLine() and addPolyLine()? 194 195 SkEdgeBuilder::Combine SkBasicEdgeBuilder::addPolyLine(SkPoint pts[], 196 char* arg_edge, char** arg_edgePtr) { 197 auto edge = (SkEdge*) arg_edge; 198 auto edgePtr = (SkEdge**)arg_edgePtr; 199 200 if (edge->setLine(pts[0], pts[1], fClipShift)) { 201 return is_vertical(edge) && edgePtr > (SkEdge**)fEdgeList 202 ? this->combineVertical(edge, edgePtr[-1]) 203 : kNo_Combine; 204 } 205 return SkEdgeBuilder::kPartial_Combine; // A convenient lie. Same do-nothing behavior. 206 } 207 SkEdgeBuilder::Combine SkAnalyticEdgeBuilder::addPolyLine(SkPoint pts[], 208 char* arg_edge, char** arg_edgePtr) { 209 auto edge = (SkAnalyticEdge*) arg_edge; 210 auto edgePtr = (SkAnalyticEdge**)arg_edgePtr; 211 212 if (edge->setLine(pts[0], pts[1])) { 213 return is_vertical(edge) && edgePtr > (SkAnalyticEdge**)fEdgeList 214 ? this->combineVertical(edge, edgePtr[-1]) 215 : kNo_Combine; 216 } 217 return SkEdgeBuilder::kPartial_Combine; // As above. 218 } 219 SkEdgeBuilder::Combine SkBezierEdgeBuilder::addPolyLine(SkPoint pts[], 220 char* arg_edge, char** arg_edgePtr) { 221 auto edge = (SkLine*)arg_edge; 222 223 if (edge->set(pts)) { 224 return kNo_Combine; 225 } 226 return SkEdgeBuilder::kPartial_Combine; // As above. 227 } 228 229 SkRect SkBasicEdgeBuilder::recoverClip(const SkIRect& src) const { 230 return { SkIntToScalar(src.fLeft >> fClipShift), 231 SkIntToScalar(src.fTop >> fClipShift), 232 SkIntToScalar(src.fRight >> fClipShift), 233 SkIntToScalar(src.fBottom >> fClipShift), }; 234 } 235 SkRect SkAnalyticEdgeBuilder::recoverClip(const SkIRect& src) const { 236 return SkRect::Make(src); 237 } 238 SkRect SkBezierEdgeBuilder::recoverClip(const SkIRect& src) const { 239 return SkRect::Make(src); 240 } 241 242 char* SkBasicEdgeBuilder::allocEdges(size_t n, size_t* size) { 243 *size = sizeof(SkEdge); 244 return (char*)fAlloc.makeArrayDefault<SkEdge>(n); 245 } 246 char* SkAnalyticEdgeBuilder::allocEdges(size_t n, size_t* size) { 247 *size = sizeof(SkAnalyticEdge); 248 return (char*)fAlloc.makeArrayDefault<SkAnalyticEdge>(n); 249 } 250 char* SkBezierEdgeBuilder::allocEdges(size_t n, size_t* size) { 251 *size = sizeof(SkLine); 252 return (char*)fAlloc.makeArrayDefault<SkLine>(n); 253 } 254 255 // TODO: maybe get rid of buildPoly() entirely? 256 int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip, bool canCullToTheRight) { 257 SkPath::Iter iter(path, true); 258 SkPoint pts[4]; 259 SkPath::Verb verb; 260 261 size_t maxEdgeCount = path.countPoints(); 262 if (iclip) { 263 // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since 264 // we turn portions that are clipped out on the left/right into vertical 265 // segments. 266 SkSafeMath safe; 267 maxEdgeCount = safe.mul(maxEdgeCount, SkLineClipper::kMaxClippedLineSegments); 268 if (!safe) { 269 return 0; 270 } 271 } 272 273 size_t edgeSize; 274 char* edge = this->allocEdges(maxEdgeCount, &edgeSize); 275 276 SkDEBUGCODE(char* edgeStart = edge); 277 char** edgePtr = fAlloc.makeArrayDefault<char*>(maxEdgeCount); 278 fEdgeList = (void**)edgePtr; 279 280 if (iclip) { 281 SkRect clip = this->recoverClip(*iclip); 282 283 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 284 switch (verb) { 285 case SkPath::kMove_Verb: 286 case SkPath::kClose_Verb: 287 // we ignore these, and just get the whole segment from 288 // the corresponding line/quad/cubic verbs 289 break; 290 case SkPath::kLine_Verb: { 291 SkPoint lines[SkLineClipper::kMaxPoints]; 292 int lineCount = SkLineClipper::ClipLine(pts, clip, lines, canCullToTheRight); 293 SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments); 294 for (int i = 0; i < lineCount; i++) { 295 switch( this->addPolyLine(lines + i, edge, edgePtr) ) { 296 case kTotal_Combine: edgePtr--; break; 297 case kPartial_Combine: break; 298 case kNo_Combine: *edgePtr++ = edge; 299 edge += edgeSize; 300 } 301 } 302 break; 303 } 304 default: 305 SkDEBUGFAIL("unexpected verb"); 306 break; 307 } 308 } 309 } else { 310 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 311 switch (verb) { 312 case SkPath::kMove_Verb: 313 case SkPath::kClose_Verb: 314 // we ignore these, and just get the whole segment from 315 // the corresponding line/quad/cubic verbs 316 break; 317 case SkPath::kLine_Verb: { 318 switch( this->addPolyLine(pts, edge, edgePtr) ) { 319 case kTotal_Combine: edgePtr--; break; 320 case kPartial_Combine: break; 321 case kNo_Combine: *edgePtr++ = edge; 322 edge += edgeSize; 323 } 324 break; 325 } 326 default: 327 SkDEBUGFAIL("unexpected verb"); 328 break; 329 } 330 } 331 } 332 SkASSERT((size_t)(edge - edgeStart) <= maxEdgeCount * edgeSize); 333 SkASSERT((size_t)(edgePtr - (char**)fEdgeList) <= maxEdgeCount); 334 return SkToInt(edgePtr - (char**)fEdgeList); 335 } 336 337 int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, bool canCullToTheRight) { 338 SkAutoConicToQuads quadder; 339 const SkScalar conicTol = SK_Scalar1 / 4; 340 341 SkPath::Iter iter(path, true); 342 SkPoint pts[4]; 343 SkPath::Verb verb; 344 345 bool is_finite = true; 346 347 if (iclip) { 348 SkRect clip = this->recoverClip(*iclip); 349 SkEdgeClipper clipper(canCullToTheRight); 350 351 auto apply_clipper = [this, &clipper, &is_finite] { 352 SkPoint pts[4]; 353 SkPath::Verb verb; 354 355 while ((verb = clipper.next(pts)) != SkPath::kDone_Verb) { 356 const int count = SkPathPriv::PtsInIter(verb); 357 if (!SkScalarsAreFinite(&pts[0].fX, count*2)) { 358 is_finite = false; 359 return; 360 } 361 switch (verb) { 362 case SkPath::kLine_Verb: this->addLine (pts); break; 363 case SkPath::kQuad_Verb: this->addQuad (pts); break; 364 case SkPath::kCubic_Verb: this->addCubic(pts); break; 365 default: break; 366 } 367 } 368 }; 369 370 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 371 switch (verb) { 372 case SkPath::kMove_Verb: 373 case SkPath::kClose_Verb: 374 // we ignore these, and just get the whole segment from 375 // the corresponding line/quad/cubic verbs 376 break; 377 case SkPath::kLine_Verb: 378 if (clipper.clipLine(pts[0], pts[1], clip)) { 379 apply_clipper(); 380 } 381 break; 382 case SkPath::kQuad_Verb: 383 if (clipper.clipQuad(pts, clip)) { 384 apply_clipper(); 385 } 386 break; 387 case SkPath::kConic_Verb: { 388 const SkPoint* quadPts = quadder.computeQuads( 389 pts, iter.conicWeight(), conicTol); 390 for (int i = 0; i < quadder.countQuads(); ++i) { 391 if (clipper.clipQuad(quadPts, clip)) { 392 apply_clipper(); 393 } 394 quadPts += 2; 395 } 396 } break; 397 case SkPath::kCubic_Verb: 398 if (clipper.clipCubic(pts, clip)) { 399 apply_clipper(); 400 } 401 break; 402 default: 403 SkDEBUGFAIL("unexpected verb"); 404 break; 405 } 406 } 407 } else { 408 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 409 auto handle_quad = [this](const SkPoint pts[3]) { 410 SkPoint monoX[5]; 411 int n = SkChopQuadAtYExtrema(pts, monoX); 412 for (int i = 0; i <= n; i++) { 413 this->addQuad(&monoX[i * 2]); 414 } 415 }; 416 417 switch (verb) { 418 case SkPath::kMove_Verb: 419 case SkPath::kClose_Verb: 420 // we ignore these, and just get the whole segment from 421 // the corresponding line/quad/cubic verbs 422 break; 423 case SkPath::kLine_Verb: 424 this->addLine(pts); 425 break; 426 case SkPath::kQuad_Verb: { 427 handle_quad(pts); 428 break; 429 } 430 case SkPath::kConic_Verb: { 431 const SkPoint* quadPts = quadder.computeQuads( 432 pts, iter.conicWeight(), conicTol); 433 for (int i = 0; i < quadder.countQuads(); ++i) { 434 handle_quad(quadPts); 435 quadPts += 2; 436 } 437 } break; 438 case SkPath::kCubic_Verb: { 439 if (!this->chopCubics()) { 440 this->addCubic(pts); 441 break; 442 } 443 SkPoint monoY[10]; 444 int n = SkChopCubicAtYExtrema(pts, monoY); 445 for (int i = 0; i <= n; i++) { 446 this->addCubic(&monoY[i * 3]); 447 } 448 break; 449 } 450 default: 451 SkDEBUGFAIL("unexpected verb"); 452 break; 453 } 454 } 455 } 456 fEdgeList = fList.begin(); 457 return is_finite ? fList.count() : 0; 458 } 459 460 int SkEdgeBuilder::buildEdges(const SkPath& path, 461 const SkIRect* shiftedClip) { 462 // If we're convex, then we need both edges, even if the right edge is past the clip. 463 const bool canCullToTheRight = !path.isConvex(); 464 465 // We can use our buildPoly() optimization if all the segments are lines. 466 // (Edges are homogenous and stored contiguously in memory, no need for indirection.) 467 const int count = SkPath::kLine_SegmentMask == path.getSegmentMasks() 468 ? this->buildPoly(path, shiftedClip, canCullToTheRight) 469 : this->build (path, shiftedClip, canCullToTheRight); 470 471 SkASSERT(count >= 0); 472 473 // If we can't cull to the right, we should have count > 1 (or 0), 474 // unless we're in DAA which doesn't need to chop edges at y extrema. 475 // For example, a single cubic edge with a valley shape \_/ is fine for DAA. 476 if (!canCullToTheRight && count == 1) { 477 SkASSERT(!this->chopCubics()); 478 } 479 480 return count; 481 } 482
