SkEdgeClipper.cpp revision 13b77e83076d3735a86926f6f48741e1360c525c
1 2/* 3 * Copyright 2009 The Android Open Source Project 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 "SkEdgeClipper.h" 11#include "SkGeometry.h" 12 13static bool quick_reject(const SkRect& bounds, const SkRect& clip) { 14 return bounds.fTop >= clip.fBottom || bounds.fBottom <= clip.fTop; 15} 16 17static inline void clamp_le(SkScalar& value, SkScalar max) { 18 if (value > max) { 19 value = max; 20 } 21} 22 23static inline void clamp_ge(SkScalar& value, SkScalar min) { 24 if (value < min) { 25 value = min; 26 } 27} 28 29/* src[] must be monotonic in Y. This routine copies src into dst, and sorts 30 it to be increasing in Y. If it had to reverse the order of the points, 31 it returns true, otherwise it returns false 32 */ 33static bool sort_increasing_Y(SkPoint dst[], const SkPoint src[], int count) { 34 // we need the data to be monotonically increasing in Y 35 if (src[0].fY > src[count - 1].fY) { 36 for (int i = 0; i < count; i++) { 37 dst[i] = src[count - i - 1]; 38 } 39 return true; 40 } else { 41 memcpy(dst, src, count * sizeof(SkPoint)); 42 return false; 43 } 44} 45 46/////////////////////////////////////////////////////////////////////////////// 47 48static bool chopMonoQuadAt(SkScalar c0, SkScalar c1, SkScalar c2, 49 SkScalar target, SkScalar* t) { 50 /* Solve F(t) = y where F(t) := [0](1-t)^2 + 2[1]t(1-t) + [2]t^2 51 * We solve for t, using quadratic equation, hence we have to rearrange 52 * our cooefficents to look like At^2 + Bt + C 53 */ 54 SkScalar A = c0 - c1 - c1 + c2; 55 SkScalar B = 2*(c1 - c0); 56 SkScalar C = c0 - target; 57 58 SkScalar roots[2]; // we only expect one, but make room for 2 for safety 59 int count = SkFindUnitQuadRoots(A, B, C, roots); 60 if (count) { 61 *t = roots[0]; 62 return true; 63 } 64 return false; 65} 66 67static bool chopMonoQuadAtY(SkPoint pts[3], SkScalar y, SkScalar* t) { 68 return chopMonoQuadAt(pts[0].fY, pts[1].fY, pts[2].fY, y, t); 69} 70 71static bool chopMonoQuadAtX(SkPoint pts[3], SkScalar x, SkScalar* t) { 72 return chopMonoQuadAt(pts[0].fX, pts[1].fX, pts[2].fX, x, t); 73} 74 75// Modify pts[] in place so that it is clipped in Y to the clip rect 76static void chop_quad_in_Y(SkPoint pts[3], const SkRect& clip) { 77 SkScalar t; 78 SkPoint tmp[5]; // for SkChopQuadAt 79 80 // are we partially above 81 if (pts[0].fY < clip.fTop) { 82 if (chopMonoQuadAtY(pts, clip.fTop, &t)) { 83 // take the 2nd chopped quad 84 SkChopQuadAt(pts, tmp, t); 85 // clamp to clean up imprecise numerics in the chop 86 tmp[2].fY = clip.fTop; 87 clamp_ge(tmp[3].fY, clip.fTop); 88 89 pts[0] = tmp[2]; 90 pts[1] = tmp[3]; 91 } else { 92 // if chopMonoQuadAtY failed, then we may have hit inexact numerics 93 // so we just clamp against the top 94 for (int i = 0; i < 3; i++) { 95 if (pts[i].fY < clip.fTop) { 96 pts[i].fY = clip.fTop; 97 } 98 } 99 } 100 } 101 102 // are we partially below 103 if (pts[2].fY > clip.fBottom) { 104 if (chopMonoQuadAtY(pts, clip.fBottom, &t)) { 105 SkChopQuadAt(pts, tmp, t); 106 // clamp to clean up imprecise numerics in the chop 107 clamp_le(tmp[1].fY, clip.fBottom); 108 tmp[2].fY = clip.fBottom; 109 110 pts[1] = tmp[1]; 111 pts[2] = tmp[2]; 112 } else { 113 // if chopMonoQuadAtY failed, then we may have hit inexact numerics 114 // so we just clamp against the bottom 115 for (int i = 0; i < 3; i++) { 116 if (pts[i].fY > clip.fBottom) { 117 pts[i].fY = clip.fBottom; 118 } 119 } 120 } 121 } 122} 123 124// srcPts[] must be monotonic in X and Y 125void SkEdgeClipper::clipMonoQuad(const SkPoint srcPts[3], const SkRect& clip) { 126 SkPoint pts[3]; 127 bool reverse = sort_increasing_Y(pts, srcPts, 3); 128 129 // are we completely above or below 130 if (pts[2].fY <= clip.fTop || pts[0].fY >= clip.fBottom) { 131 return; 132 } 133 134 // Now chop so that pts is contained within clip in Y 135 chop_quad_in_Y(pts, clip); 136 137 if (pts[0].fX > pts[2].fX) { 138 SkTSwap<SkPoint>(pts[0], pts[2]); 139 reverse = !reverse; 140 } 141 SkASSERT(pts[0].fX <= pts[1].fX); 142 SkASSERT(pts[1].fX <= pts[2].fX); 143 144 // Now chop in X has needed, and record the segments 145 146 if (pts[2].fX <= clip.fLeft) { // wholly to the left 147 this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse); 148 return; 149 } 150 if (pts[0].fX >= clip.fRight) { // wholly to the right 151 this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse); 152 return; 153 } 154 155 SkScalar t; 156 SkPoint tmp[5]; // for SkChopQuadAt 157 158 // are we partially to the left 159 if (pts[0].fX < clip.fLeft) { 160 if (chopMonoQuadAtX(pts, clip.fLeft, &t)) { 161 SkChopQuadAt(pts, tmp, t); 162 this->appendVLine(clip.fLeft, tmp[0].fY, tmp[2].fY, reverse); 163 // clamp to clean up imprecise numerics in the chop 164 tmp[2].fX = clip.fLeft; 165 clamp_ge(tmp[3].fX, clip.fLeft); 166 167 pts[0] = tmp[2]; 168 pts[1] = tmp[3]; 169 } else { 170 // if chopMonoQuadAtY failed, then we may have hit inexact numerics 171 // so we just clamp against the left 172 this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse); 173 return; 174 } 175 } 176 177 // are we partially to the right 178 if (pts[2].fX > clip.fRight) { 179 if (chopMonoQuadAtX(pts, clip.fRight, &t)) { 180 SkChopQuadAt(pts, tmp, t); 181 // clamp to clean up imprecise numerics in the chop 182 clamp_le(tmp[1].fX, clip.fRight); 183 tmp[2].fX = clip.fRight; 184 185 this->appendQuad(tmp, reverse); 186 this->appendVLine(clip.fRight, tmp[2].fY, tmp[4].fY, reverse); 187 } else { 188 // if chopMonoQuadAtY failed, then we may have hit inexact numerics 189 // so we just clamp against the right 190 this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse); 191 } 192 } else { // wholly inside the clip 193 this->appendQuad(pts, reverse); 194 } 195} 196 197bool SkEdgeClipper::clipQuad(const SkPoint srcPts[3], const SkRect& clip) { 198 fCurrPoint = fPoints; 199 fCurrVerb = fVerbs; 200 201 SkRect bounds; 202 bounds.set(srcPts, 3); 203 204 if (!quick_reject(bounds, clip)) { 205 SkPoint monoY[5]; 206 int countY = SkChopQuadAtYExtrema(srcPts, monoY); 207 for (int y = 0; y <= countY; y++) { 208 SkPoint monoX[5]; 209 int countX = SkChopQuadAtXExtrema(&monoY[y * 2], monoX); 210 for (int x = 0; x <= countX; x++) { 211 this->clipMonoQuad(&monoX[x * 2], clip); 212 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs); 213 SkASSERT(fCurrPoint - fPoints <= kMaxPoints); 214 } 215 } 216 } 217 218 *fCurrVerb = SkPath::kDone_Verb; 219 fCurrPoint = fPoints; 220 fCurrVerb = fVerbs; 221 return SkPath::kDone_Verb != fVerbs[0]; 222} 223 224/////////////////////////////////////////////////////////////////////////////// 225 226static SkScalar eval_cubic_coeff(SkScalar A, SkScalar B, SkScalar C, 227 SkScalar D, SkScalar t) { 228 return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D); 229} 230 231/* Given 4 cubic points (either Xs or Ys), and a target X or Y, compute the 232 t value such that cubic(t) = target 233 */ 234static bool chopMonoCubicAt(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3, 235 SkScalar target, SkScalar* t) { 236 // SkASSERT(c0 <= c1 && c1 <= c2 && c2 <= c3); 237 SkASSERT(c0 < target && target < c3); 238 239 SkScalar D = c0 - target; 240 SkScalar A = c3 + 3*(c1 - c2) - c0; 241 SkScalar B = 3*(c2 - c1 - c1 + c0); 242 SkScalar C = 3*(c1 - c0); 243 244 const SkScalar TOLERANCE = SK_Scalar1 / 4096; 245 SkScalar minT = 0; 246 SkScalar maxT = SK_Scalar1; 247 SkScalar mid; 248 249 // This is a lot of iterations. Is there a faster way? 250 for (int i = 0; i < 24; i++) { 251 mid = SkScalarAve(minT, maxT); 252 SkScalar delta = eval_cubic_coeff(A, B, C, D, mid); 253 if (delta < 0) { 254 minT = mid; 255 delta = -delta; 256 } else { 257 maxT = mid; 258 } 259 if (delta < TOLERANCE) { 260 break; 261 } 262 } 263 *t = mid; 264// SkDebugf("-- evalCubicAt %d delta %g\n", i, eval_cubic_coeff(A, B, C, D, *t)); 265 return true; 266} 267 268static bool chopMonoCubicAtY(SkPoint pts[4], SkScalar y, SkScalar* t) { 269 return chopMonoCubicAt(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY, y, t); 270} 271 272static bool chopMonoCubicAtX(SkPoint pts[4], SkScalar x, SkScalar* t) { 273 return chopMonoCubicAt(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, x, t); 274} 275 276// Modify pts[] in place so that it is clipped in Y to the clip rect 277static void chop_cubic_in_Y(SkPoint pts[4], const SkRect& clip) { 278 279 // are we partially above 280 if (pts[0].fY < clip.fTop) { 281 SkScalar t; 282 if (chopMonoCubicAtY(pts, clip.fTop, &t)) { 283 SkPoint tmp[7]; 284 SkChopCubicAt(pts, tmp, t); 285 286 // tmp[3, 4].fY should all be to the below clip.fTop, and 287 // still be monotonic in Y. Since we can't trust the numerics of 288 // the chopper, we force those conditions now 289 tmp[3].fY = clip.fTop; 290 clamp_ge(tmp[4].fY, clip.fTop); 291 292 pts[0] = tmp[3]; 293 pts[1] = tmp[4]; 294 pts[2] = tmp[5]; 295 } else { 296 // if chopMonoCubicAtY failed, then we may have hit inexact numerics 297 // so we just clamp against the top 298 for (int i = 0; i < 4; i++) { 299 clamp_ge(pts[i].fY, clip.fTop); 300 } 301 } 302 } 303 304 // are we partially below 305 if (pts[3].fY > clip.fBottom) { 306 SkScalar t; 307 if (chopMonoCubicAtY(pts, clip.fBottom, &t)) { 308 SkPoint tmp[7]; 309 SkChopCubicAt(pts, tmp, t); 310 tmp[3].fY = clip.fBottom; 311 clamp_le(tmp[2].fY, clip.fBottom); 312 313 pts[1] = tmp[1]; 314 pts[2] = tmp[2]; 315 pts[3] = tmp[3]; 316 } else { 317 // if chopMonoCubicAtY failed, then we may have hit inexact numerics 318 // so we just clamp against the bottom 319 for (int i = 0; i < 4; i++) { 320 clamp_le(pts[i].fY, clip.fBottom); 321 } 322 } 323 } 324} 325 326// srcPts[] must be monotonic in X and Y 327void SkEdgeClipper::clipMonoCubic(const SkPoint src[4], const SkRect& clip) { 328 SkPoint pts[4]; 329 bool reverse = sort_increasing_Y(pts, src, 4); 330 331 // are we completely above or below 332 if (pts[3].fY <= clip.fTop || pts[0].fY >= clip.fBottom) { 333 return; 334 } 335 336 // Now chop so that pts is contained within clip in Y 337 chop_cubic_in_Y(pts, clip); 338 339 if (pts[0].fX > pts[3].fX) { 340 SkTSwap<SkPoint>(pts[0], pts[3]); 341 SkTSwap<SkPoint>(pts[1], pts[2]); 342 reverse = !reverse; 343 } 344 345 // Now chop in X has needed, and record the segments 346 347 if (pts[3].fX <= clip.fLeft) { // wholly to the left 348 this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse); 349 return; 350 } 351 if (pts[0].fX >= clip.fRight) { // wholly to the right 352 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse); 353 return; 354 } 355 356 // are we partially to the left 357 if (pts[0].fX < clip.fLeft) { 358 SkScalar t; 359 if (chopMonoCubicAtX(pts, clip.fLeft, &t)) { 360 SkPoint tmp[7]; 361 SkChopCubicAt(pts, tmp, t); 362 this->appendVLine(clip.fLeft, tmp[0].fY, tmp[3].fY, reverse); 363 364 // tmp[3, 4, 5].fX should all be to the right of clip.fLeft, and 365 // still be monotonic in X. Since we can't trust the numerics of 366 // the chopper, we force those conditions now 367 tmp[3].fX = clip.fLeft; 368 clamp_ge(tmp[4].fX, clip.fLeft); 369 clamp_ge(tmp[5].fX, tmp[4].fX); 370 371 pts[0] = tmp[3]; 372 pts[1] = tmp[4]; 373 pts[2] = tmp[5]; 374 } else { 375 // if chopMonocubicAtY failed, then we may have hit inexact numerics 376 // so we just clamp against the left 377 this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse); 378 return; 379 } 380 } 381 382 // are we partially to the right 383 if (pts[3].fX > clip.fRight) { 384 SkScalar t; 385 if (chopMonoCubicAtX(pts, clip.fRight, &t)) { 386 SkPoint tmp[7]; 387 SkChopCubicAt(pts, tmp, t); 388 tmp[3].fX = clip.fRight; 389 clamp_le(tmp[2].fX, clip.fRight); 390 clamp_le(tmp[1].fX, tmp[2].fX); 391 392 this->appendCubic(tmp, reverse); 393 this->appendVLine(clip.fRight, tmp[3].fY, tmp[6].fY, reverse); 394 } else { 395 // if chopMonoCubicAtX failed, then we may have hit inexact numerics 396 // so we just clamp against the right 397 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse); 398 } 399 } else { // wholly inside the clip 400 this->appendCubic(pts, reverse); 401 } 402} 403 404bool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) { 405 fCurrPoint = fPoints; 406 fCurrVerb = fVerbs; 407 408 SkRect bounds; 409 bounds.set(srcPts, 4); 410 411 if (!quick_reject(bounds, clip)) { 412 SkPoint monoY[10]; 413 int countY = SkChopCubicAtYExtrema(srcPts, monoY); 414 for (int y = 0; y <= countY; y++) { 415 // sk_assert_monotonic_y(&monoY[y * 3], 4); 416 SkPoint monoX[10]; 417 int countX = SkChopCubicAtXExtrema(&monoY[y * 3], monoX); 418 for (int x = 0; x <= countX; x++) { 419 // sk_assert_monotonic_y(&monoX[x * 3], 4); 420 // sk_assert_monotonic_x(&monoX[x * 3], 4); 421 this->clipMonoCubic(&monoX[x * 3], clip); 422 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs); 423 SkASSERT(fCurrPoint - fPoints <= kMaxPoints); 424 } 425 } 426 } 427 428 *fCurrVerb = SkPath::kDone_Verb; 429 fCurrPoint = fPoints; 430 fCurrVerb = fVerbs; 431 return SkPath::kDone_Verb != fVerbs[0]; 432} 433 434/////////////////////////////////////////////////////////////////////////////// 435 436void SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1, 437 bool reverse) { 438 *fCurrVerb++ = SkPath::kLine_Verb; 439 440 if (reverse) { 441 SkTSwap<SkScalar>(y0, y1); 442 } 443 fCurrPoint[0].set(x, y0); 444 fCurrPoint[1].set(x, y1); 445 fCurrPoint += 2; 446} 447 448void SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) { 449 *fCurrVerb++ = SkPath::kQuad_Verb; 450 451 if (reverse) { 452 fCurrPoint[0] = pts[2]; 453 fCurrPoint[2] = pts[0]; 454 } else { 455 fCurrPoint[0] = pts[0]; 456 fCurrPoint[2] = pts[2]; 457 } 458 fCurrPoint[1] = pts[1]; 459 fCurrPoint += 3; 460} 461 462void SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) { 463 *fCurrVerb++ = SkPath::kCubic_Verb; 464 465 if (reverse) { 466 for (int i = 0; i < 4; i++) { 467 fCurrPoint[i] = pts[3 - i]; 468 } 469 } else { 470 memcpy(fCurrPoint, pts, 4 * sizeof(SkPoint)); 471 } 472 fCurrPoint += 4; 473} 474 475SkPath::Verb SkEdgeClipper::next(SkPoint pts[]) { 476 SkPath::Verb verb = *fCurrVerb; 477 478 switch (verb) { 479 case SkPath::kLine_Verb: 480 memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint)); 481 fCurrPoint += 2; 482 fCurrVerb += 1; 483 break; 484 case SkPath::kQuad_Verb: 485 memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint)); 486 fCurrPoint += 3; 487 fCurrVerb += 1; 488 break; 489 case SkPath::kCubic_Verb: 490 memcpy(pts, fCurrPoint, 4 * sizeof(SkPoint)); 491 fCurrPoint += 4; 492 fCurrVerb += 1; 493 break; 494 case SkPath::kDone_Verb: 495 break; 496 default: 497 SkDEBUGFAIL("unexpected verb in quadclippper2 iter"); 498 break; 499 } 500 return verb; 501} 502 503/////////////////////////////////////////////////////////////////////////////// 504 505#ifdef SK_DEBUG 506static void assert_monotonic(const SkScalar coord[], int count) { 507 if (coord[0] > coord[(count - 1) * 2]) { 508 for (int i = 1; i < count; i++) { 509 SkASSERT(coord[2 * (i - 1)] >= coord[i * 2]); 510 } 511 } else if (coord[0] < coord[(count - 1) * 2]) { 512 for (int i = 1; i < count; i++) { 513 SkASSERT(coord[2 * (i - 1)] <= coord[i * 2]); 514 } 515 } else { 516 for (int i = 1; i < count; i++) { 517 SkASSERT(coord[2 * (i - 1)] == coord[i * 2]); 518 } 519 } 520} 521 522void sk_assert_monotonic_y(const SkPoint pts[], int count) { 523 if (count > 1) { 524 assert_monotonic(&pts[0].fY, count); 525 } 526} 527 528void sk_assert_monotonic_x(const SkPoint pts[], int count) { 529 if (count > 1) { 530 assert_monotonic(&pts[0].fX, count); 531 } 532} 533#endif 534