SkEdgeClipper.cpp revision e01403096cc8fc15217d7de08c476c2056d8b9d0
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 int i; 249 for (i = 0; i < 16; i++) { 250 mid = SkScalarAve(minT, maxT); 251 SkScalar delta = eval_cubic_coeff(A, B, C, D, mid); 252 if (delta < 0) { 253 minT = mid; 254 delta = -delta; 255 } else { 256 maxT = mid; 257 } 258 if (delta < TOLERANCE) { 259 break; 260 } 261 } 262 *t = mid; 263// SkDebugf("-- evalCubicAt %d delta %g\n", i, eval_cubic_coeff(A, B, C, D, *t)); 264 return true; 265} 266 267static bool chopMonoCubicAtY(SkPoint pts[4], SkScalar y, SkScalar* t) { 268 return chopMonoCubicAt(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY, y, t); 269} 270 271static bool chopMonoCubicAtX(SkPoint pts[4], SkScalar x, SkScalar* t) { 272 return chopMonoCubicAt(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, x, t); 273} 274 275// Modify pts[] in place so that it is clipped in Y to the clip rect 276static void chop_cubic_in_Y(SkPoint pts[4], const SkRect& clip) { 277 278 // are we partially above 279 if (pts[0].fY < clip.fTop) { 280 SkScalar t; 281 if (chopMonoCubicAtY(pts, clip.fTop, &t)) { 282 SkPoint tmp[7]; 283 SkChopCubicAt(pts, tmp, t); 284 285 // tmp[3, 4, 5].fY should all be to the below clip.fTop, and 286 // still be monotonic in Y. Since we can't trust the numerics of 287 // the chopper, we force those conditions now 288 tmp[3].fY = clip.fTop; 289 tmp[4].fY = SkMaxScalar(tmp[4].fY, clip.fTop); 290 tmp[5].fY = SkMaxScalar(tmp[5].fY, tmp[4].fY); 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 clamp_le(tmp[1].fY, clip.fBottom); 311 clamp_le(tmp[2].fY, clip.fBottom); 312 clamp_le(tmp[3].fY, clip.fBottom); 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 tmp[4].fX = SkMaxScalar(tmp[4].fX, clip.fLeft); 369 tmp[5].fX = SkMaxScalar(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 clamp_le(tmp[1].fX, clip.fRight); 389 clamp_le(tmp[2].fX, clip.fRight); 390 clamp_le(tmp[3].fX, clip.fRight); 391 this->appendCubic(tmp, reverse); 392 this->appendVLine(clip.fRight, tmp[3].fY, tmp[6].fY, reverse); 393 } else { 394 // if chopMonoCubicAtX failed, then we may have hit inexact numerics 395 // so we just clamp against the right 396 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse); 397 } 398 } else { // wholly inside the clip 399 this->appendCubic(pts, reverse); 400 } 401} 402 403bool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) { 404 fCurrPoint = fPoints; 405 fCurrVerb = fVerbs; 406 407 SkRect bounds; 408 bounds.set(srcPts, 4); 409 410 if (!quick_reject(bounds, clip)) { 411 SkPoint monoY[10]; 412 int countY = SkChopCubicAtYExtrema(srcPts, monoY); 413 for (int y = 0; y <= countY; y++) { 414 // sk_assert_monotonic_y(&monoY[y * 3], 4); 415 SkPoint monoX[10]; 416 int countX = SkChopCubicAtXExtrema(&monoY[y * 3], monoX); 417 for (int x = 0; x <= countX; x++) { 418 // sk_assert_monotonic_y(&monoX[x * 3], 4); 419 // sk_assert_monotonic_x(&monoX[x * 3], 4); 420 this->clipMonoCubic(&monoX[x * 3], clip); 421 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs); 422 SkASSERT(fCurrPoint - fPoints <= kMaxPoints); 423 } 424 } 425 } 426 427 *fCurrVerb = SkPath::kDone_Verb; 428 fCurrPoint = fPoints; 429 fCurrVerb = fVerbs; 430 return SkPath::kDone_Verb != fVerbs[0]; 431} 432 433/////////////////////////////////////////////////////////////////////////////// 434 435void SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1, 436 bool reverse) { 437 *fCurrVerb++ = SkPath::kLine_Verb; 438 439 if (reverse) { 440 SkTSwap<SkScalar>(y0, y1); 441 } 442 fCurrPoint[0].set(x, y0); 443 fCurrPoint[1].set(x, y1); 444 fCurrPoint += 2; 445} 446 447void SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) { 448 *fCurrVerb++ = SkPath::kQuad_Verb; 449 450 if (reverse) { 451 fCurrPoint[0] = pts[2]; 452 fCurrPoint[2] = pts[0]; 453 } else { 454 fCurrPoint[0] = pts[0]; 455 fCurrPoint[2] = pts[2]; 456 } 457 fCurrPoint[1] = pts[1]; 458 fCurrPoint += 3; 459} 460 461void SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) { 462 *fCurrVerb++ = SkPath::kCubic_Verb; 463 464 if (reverse) { 465 for (int i = 0; i < 4; i++) { 466 fCurrPoint[i] = pts[3 - i]; 467 } 468 } else { 469 memcpy(fCurrPoint, pts, 4 * sizeof(SkPoint)); 470 } 471 fCurrPoint += 4; 472} 473 474SkPath::Verb SkEdgeClipper::next(SkPoint pts[]) { 475 SkPath::Verb verb = *fCurrVerb; 476 477 switch (verb) { 478 case SkPath::kLine_Verb: 479 memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint)); 480 fCurrPoint += 2; 481 fCurrVerb += 1; 482 break; 483 case SkPath::kQuad_Verb: 484 memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint)); 485 fCurrPoint += 3; 486 fCurrVerb += 1; 487 break; 488 case SkPath::kCubic_Verb: 489 memcpy(pts, fCurrPoint, 4 * sizeof(SkPoint)); 490 fCurrPoint += 4; 491 fCurrVerb += 1; 492 break; 493 case SkPath::kDone_Verb: 494 break; 495 default: 496 SkDEBUGFAIL("unexpected verb in quadclippper2 iter"); 497 break; 498 } 499 return verb; 500} 501 502/////////////////////////////////////////////////////////////////////////////// 503 504#ifdef SK_DEBUG 505static void assert_monotonic(const SkScalar coord[], int count) { 506 if (coord[0] > coord[(count - 1) * 2]) { 507 for (int i = 1; i < count; i++) { 508 SkASSERT(coord[2 * (i - 1)] >= coord[i * 2]); 509 } 510 } else if (coord[0] < coord[(count - 1) * 2]) { 511 for (int i = 1; i < count; i++) { 512 SkASSERT(coord[2 * (i - 1)] <= coord[i * 2]); 513 } 514 } else { 515 for (int i = 1; i < count; i++) { 516 SkASSERT(coord[2 * (i - 1)] == coord[i * 2]); 517 } 518 } 519} 520 521void sk_assert_monotonic_y(const SkPoint pts[], int count) { 522 if (count > 1) { 523 assert_monotonic(&pts[0].fY, count); 524 } 525} 526 527void sk_assert_monotonic_x(const SkPoint pts[], int count) { 528 if (count > 1) { 529 assert_monotonic(&pts[0].fX, count); 530 } 531} 532#endif 533