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