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 17SkEdgeBuilder::SkEdgeBuilder() : fAlloc(16*1024) { 18 fEdgeList = nullptr; 19} 20 21SkEdgeBuilder::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 62static inline bool approximatelyEqual(SkFixed a, SkFixed b) { 63 return SkAbs32(a - b) < 0x100; 64} 65 66SkEdgeBuilder::Combine SkEdgeBuilder::CombineVertical( 67 const SkAnalyticEdge* edge, SkAnalyticEdge* last) { 68 SkASSERT(fAnalyticAA); 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 113bool SkEdgeBuilder::vertical_line(const SkEdge* edge) { 114 return !edge->fDX && !edge->fCurveCount; 115} 116 117bool SkEdgeBuilder::vertical_line(const SkAnalyticEdge* edge) { 118 SkASSERT(fAnalyticAA); 119 return !edge->fDX && !edge->fCurveCount; 120} 121 122void SkEdgeBuilder::addLine(const SkPoint pts[]) { 123 if (fAnalyticAA) { 124 SkAnalyticEdge* edge = fAlloc.make<SkAnalyticEdge>(); 125 if (edge->setLine(pts[0], pts[1])) { 126 if (vertical_line(edge) && fList.count()) { 127 Combine combine = CombineVertical(edge, (SkAnalyticEdge*)*(fList.end() - 1)); 128 if (kNo_Combine != combine) { 129 if (kTotal_Combine == combine) { 130 fList.pop(); 131 } 132 goto unallocate_analytic_edge; 133 } 134 } 135 fList.push(edge); 136 } else { 137unallocate_analytic_edge: 138 ; 139 // TODO: unallocate edge from storage... 140 } 141 } else { 142 SkEdge* edge = fAlloc.make<SkEdge>(); 143 if (edge->setLine(pts[0], pts[1], fShiftUp)) { 144 if (vertical_line(edge) && fList.count()) { 145 Combine combine = CombineVertical(edge, (SkEdge*)*(fList.end() - 1)); 146 if (kNo_Combine != combine) { 147 if (kTotal_Combine == combine) { 148 fList.pop(); 149 } 150 goto unallocate_edge; 151 } 152 } 153 fList.push(edge); 154 } else { 155unallocate_edge: 156 ; 157 // TODO: unallocate edge from storage... 158 } 159 } 160} 161 162void SkEdgeBuilder::addQuad(const SkPoint pts[]) { 163 if (fAnalyticAA) { 164 SkAnalyticQuadraticEdge* edge = fAlloc.make<SkAnalyticQuadraticEdge>(); 165 if (edge->setQuadratic(pts)) { 166 fList.push(edge); 167 } else { 168 // TODO: unallocate edge from storage... 169 } 170 } else { 171 SkQuadraticEdge* edge = fAlloc.make<SkQuadraticEdge>(); 172 if (edge->setQuadratic(pts, fShiftUp)) { 173 fList.push(edge); 174 } else { 175 // TODO: unallocate edge from storage... 176 } 177 } 178} 179 180void SkEdgeBuilder::addCubic(const SkPoint pts[]) { 181 if (fAnalyticAA) { 182 SkAnalyticCubicEdge* edge = fAlloc.make<SkAnalyticCubicEdge>(); 183 if (edge->setCubic(pts)) { 184 fList.push(edge); 185 } else { 186 // TODO: unallocate edge from storage... 187 } 188 } else { 189 SkCubicEdge* edge = fAlloc.make<SkCubicEdge>(); 190 if (edge->setCubic(pts, fShiftUp)) { 191 fList.push(edge); 192 } else { 193 // TODO: unallocate edge from storage... 194 } 195 } 196} 197 198void SkEdgeBuilder::addClipper(SkEdgeClipper* clipper) { 199 SkPoint pts[4]; 200 SkPath::Verb verb; 201 202 while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) { 203 switch (verb) { 204 case SkPath::kLine_Verb: 205 this->addLine(pts); 206 break; 207 case SkPath::kQuad_Verb: 208 this->addQuad(pts); 209 break; 210 case SkPath::kCubic_Verb: 211 this->addCubic(pts); 212 break; 213 default: 214 break; 215 } 216 } 217} 218 219/////////////////////////////////////////////////////////////////////////////// 220 221static void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) { 222 dst->set(SkIntToScalar(src.fLeft >> shift), 223 SkIntToScalar(src.fTop >> shift), 224 SkIntToScalar(src.fRight >> shift), 225 SkIntToScalar(src.fBottom >> shift)); 226} 227 228SkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkEdge* edge, SkEdge** edgePtr) { 229 return !vertical_line(edge) || edgePtr <= (SkEdge**)fEdgeList ? kNo_Combine : 230 CombineVertical(edge, edgePtr[-1]); 231} 232 233SkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkAnalyticEdge* edge, 234 SkAnalyticEdge** edgePtr) { 235 SkASSERT(fAnalyticAA); 236 return !vertical_line(edge) || edgePtr <= (SkAnalyticEdge**)fEdgeList ? kNo_Combine : 237 CombineVertical(edge, edgePtr[-1]); 238} 239 240int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip, int shiftUp, 241 bool canCullToTheRight) { 242 SkPath::Iter iter(path, true); 243 SkPoint pts[4]; 244 SkPath::Verb verb; 245 246 int maxEdgeCount = path.countPoints(); 247 if (iclip) { 248 // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since 249 // we turn portions that are clipped out on the left/right into vertical 250 // segments. 251 maxEdgeCount *= SkLineClipper::kMaxClippedLineSegments; 252 } 253 254 size_t edgeSize = fAnalyticAA ? sizeof(SkAnalyticEdge) : sizeof(SkEdge); 255 char* edge = fAnalyticAA ? (char*)fAlloc.makeArrayDefault<SkAnalyticEdge>(maxEdgeCount) 256 : (char*)fAlloc.makeArrayDefault<SkEdge>(maxEdgeCount); 257 258 SkDEBUGCODE(char* edgeStart = edge); 259 char** edgePtr = fAlloc.makeArrayDefault<char*>(maxEdgeCount); 260 fEdgeList = (void**)edgePtr; 261 262 if (iclip) { 263 SkRect clip; 264 setShiftedClip(&clip, *iclip, shiftUp); 265 266 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 267 switch (verb) { 268 case SkPath::kMove_Verb: 269 case SkPath::kClose_Verb: 270 // we ignore these, and just get the whole segment from 271 // the corresponding line/quad/cubic verbs 272 break; 273 case SkPath::kLine_Verb: { 274 SkPoint lines[SkLineClipper::kMaxPoints]; 275 int lineCount = SkLineClipper::ClipLine(pts, clip, lines, canCullToTheRight); 276 SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments); 277 for (int i = 0; i < lineCount; i++) { 278 bool setLineResult = fAnalyticAA ? 279 ((SkAnalyticEdge*)edge)->setLine(lines[i], lines[i + 1]) : 280 ((SkEdge*)edge)->setLine(lines[i], lines[i + 1], shiftUp); 281 if (setLineResult) { 282 Combine combine = fAnalyticAA ? 283 checkVertical((SkAnalyticEdge*)edge, (SkAnalyticEdge**)edgePtr) : 284 checkVertical((SkEdge*)edge, (SkEdge**)edgePtr); 285 if (kNo_Combine == combine) { 286 *edgePtr++ = edge; 287 edge += edgeSize; 288 } else if (kTotal_Combine == combine) { 289 --edgePtr; 290 } 291 } 292 } 293 break; 294 } 295 default: 296 SkDEBUGFAIL("unexpected verb"); 297 break; 298 } 299 } 300 } else { 301 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 302 switch (verb) { 303 case SkPath::kMove_Verb: 304 case SkPath::kClose_Verb: 305 // we ignore these, and just get the whole segment from 306 // the corresponding line/quad/cubic verbs 307 break; 308 case SkPath::kLine_Verb: { 309 bool setLineResult = fAnalyticAA ? 310 ((SkAnalyticEdge*)edge)->setLine(pts[0], pts[1]) : 311 ((SkEdge*)edge)->setLine(pts[0], pts[1], shiftUp); 312 if (setLineResult) { 313 Combine combine = fAnalyticAA ? 314 checkVertical((SkAnalyticEdge*)edge, (SkAnalyticEdge**)edgePtr) : 315 checkVertical((SkEdge*)edge, (SkEdge**)edgePtr); 316 if (kNo_Combine == combine) { 317 *edgePtr++ = edge; 318 edge += edgeSize; 319 } else if (kTotal_Combine == combine) { 320 --edgePtr; 321 } 322 } 323 break; 324 } 325 default: 326 SkDEBUGFAIL("unexpected verb"); 327 break; 328 } 329 } 330 } 331 SkASSERT((size_t)(edge - edgeStart) <= maxEdgeCount * edgeSize); 332 SkASSERT(edgePtr - (char**)fEdgeList <= maxEdgeCount); 333 return SkToInt(edgePtr - (char**)fEdgeList); 334} 335 336static void handle_quad(SkEdgeBuilder* builder, const SkPoint pts[3]) { 337 SkPoint monoX[5]; 338 int n = SkChopQuadAtYExtrema(pts, monoX); 339 for (int i = 0; i <= n; i++) { 340 builder->addQuad(&monoX[i * 2]); 341 } 342} 343 344int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, int shiftUp, 345 bool canCullToTheRight, bool analyticAA) { 346 fAlloc.reset(); 347 fList.reset(); 348 fShiftUp = shiftUp; 349 fAnalyticAA = analyticAA; 350 351 if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) { 352 return this->buildPoly(path, iclip, shiftUp, canCullToTheRight); 353 } 354 355 SkAutoConicToQuads quadder; 356 const SkScalar conicTol = SK_Scalar1 / 4; 357 358 SkPath::Iter iter(path, true); 359 SkPoint pts[4]; 360 SkPath::Verb verb; 361 362 if (iclip) { 363 SkRect clip; 364 setShiftedClip(&clip, *iclip, shiftUp); 365 SkEdgeClipper clipper(canCullToTheRight); 366 367 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 368 switch (verb) { 369 case SkPath::kMove_Verb: 370 case SkPath::kClose_Verb: 371 // we ignore these, and just get the whole segment from 372 // the corresponding line/quad/cubic verbs 373 break; 374 case SkPath::kLine_Verb: 375 if (clipper.clipLine(pts[0], pts[1], clip)) { 376 this->addClipper(&clipper); 377 } 378 break; 379 case SkPath::kQuad_Verb: 380 if (clipper.clipQuad(pts, clip)) { 381 this->addClipper(&clipper); 382 } 383 break; 384 case SkPath::kConic_Verb: { 385 const SkPoint* quadPts = quadder.computeQuads( 386 pts, iter.conicWeight(), conicTol); 387 for (int i = 0; i < quadder.countQuads(); ++i) { 388 if (clipper.clipQuad(quadPts, clip)) { 389 this->addClipper(&clipper); 390 } 391 quadPts += 2; 392 } 393 } break; 394 case SkPath::kCubic_Verb: 395 if (clipper.clipCubic(pts, clip)) { 396 this->addClipper(&clipper); 397 } 398 break; 399 default: 400 SkDEBUGFAIL("unexpected verb"); 401 break; 402 } 403 } 404 } else { 405 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 406 switch (verb) { 407 case SkPath::kMove_Verb: 408 case SkPath::kClose_Verb: 409 // we ignore these, and just get the whole segment from 410 // the corresponding line/quad/cubic verbs 411 break; 412 case SkPath::kLine_Verb: 413 this->addLine(pts); 414 break; 415 case SkPath::kQuad_Verb: { 416 handle_quad(this, pts); 417 break; 418 } 419 case SkPath::kConic_Verb: { 420 const SkPoint* quadPts = quadder.computeQuads( 421 pts, iter.conicWeight(), conicTol); 422 for (int i = 0; i < quadder.countQuads(); ++i) { 423 handle_quad(this, quadPts); 424 quadPts += 2; 425 } 426 } break; 427 case SkPath::kCubic_Verb: { 428 SkPoint monoY[10]; 429 int n = SkChopCubicAtYExtrema(pts, monoY); 430 for (int i = 0; i <= n; i++) { 431 this->addCubic(&monoY[i * 3]); 432 } 433 break; 434 } 435 default: 436 SkDEBUGFAIL("unexpected verb"); 437 break; 438 } 439 } 440 } 441 fEdgeList = fList.begin(); 442 return fList.count(); 443} 444