SkEdgeClipper.cpp revision fbfcd5602128ec010c82cb733c9cdc0a3254f9f3
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 clamp_ge(tmp[4].fY, clip.fTop); 290 clamp_ge(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 tmp[3].fY = clip.fBottom; 311 clamp_le(tmp[2].fY, clip.fBottom); 312 clamp_le(tmp[1].fY, tmp[2].fY); 313 314 pts[1] = tmp[1]; 315 pts[2] = tmp[2]; 316 pts[3] = tmp[3]; 317 } else { 318 // if chopMonoCubicAtY failed, then we may have hit inexact numerics 319 // so we just clamp against the bottom 320 for (int i = 0; i < 4; i++) { 321 clamp_le(pts[i].fY, clip.fBottom); 322 } 323 } 324 } 325} 326 327// srcPts[] must be monotonic in X and Y 328void SkEdgeClipper::clipMonoCubic(const SkPoint src[4], const SkRect& clip) { 329 SkPoint pts[4]; 330 bool reverse = sort_increasing_Y(pts, src, 4); 331 332 // are we completely above or below 333 if (pts[3].fY <= clip.fTop || pts[0].fY >= clip.fBottom) { 334 return; 335 } 336 337 // Now chop so that pts is contained within clip in Y 338 chop_cubic_in_Y(pts, clip); 339 340 if (pts[0].fX > pts[3].fX) { 341 SkTSwap<SkPoint>(pts[0], pts[3]); 342 SkTSwap<SkPoint>(pts[1], pts[2]); 343 reverse = !reverse; 344 } 345 346 // Now chop in X has needed, and record the segments 347 348 if (pts[3].fX <= clip.fLeft) { // wholly to the left 349 this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse); 350 return; 351 } 352 if (pts[0].fX >= clip.fRight) { // wholly to the right 353 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse); 354 return; 355 } 356 357 // are we partially to the left 358 if (pts[0].fX < clip.fLeft) { 359 SkScalar t; 360 if (chopMonoCubicAtX(pts, clip.fLeft, &t)) { 361 SkPoint tmp[7]; 362 SkChopCubicAt(pts, tmp, t); 363 this->appendVLine(clip.fLeft, tmp[0].fY, tmp[3].fY, reverse); 364 365 // tmp[3, 4, 5].fX should all be to the right of clip.fLeft, and 366 // still be monotonic in X. Since we can't trust the numerics of 367 // the chopper, we force those conditions now 368 tmp[3].fX = clip.fLeft; 369 clamp_ge(tmp[4].fX, clip.fLeft); 370 clamp_ge(tmp[5].fX, tmp[4].fX); 371 372 pts[0] = tmp[3]; 373 pts[1] = tmp[4]; 374 pts[2] = tmp[5]; 375 } else { 376 // if chopMonocubicAtY failed, then we may have hit inexact numerics 377 // so we just clamp against the left 378 this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse); 379 return; 380 } 381 } 382 383 // are we partially to the right 384 if (pts[3].fX > clip.fRight) { 385 SkScalar t; 386 if (chopMonoCubicAtX(pts, clip.fRight, &t)) { 387 SkPoint tmp[7]; 388 SkChopCubicAt(pts, tmp, t); 389 tmp[3].fX = clip.fRight; 390 clamp_le(tmp[2].fX, clip.fRight); 391 clamp_le(tmp[1].fX, tmp[2].fX); 392 393 this->appendCubic(tmp, reverse); 394 this->appendVLine(clip.fRight, tmp[3].fY, tmp[6].fY, reverse); 395 } else { 396 // if chopMonoCubicAtX failed, then we may have hit inexact numerics 397 // so we just clamp against the right 398 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse); 399 } 400 } else { // wholly inside the clip 401 this->appendCubic(pts, reverse); 402 } 403} 404 405bool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) { 406 fCurrPoint = fPoints; 407 fCurrVerb = fVerbs; 408 409 SkRect bounds; 410 bounds.set(srcPts, 4); 411 412 if (!quick_reject(bounds, clip)) { 413 SkPoint monoY[10]; 414 int countY = SkChopCubicAtYExtrema(srcPts, monoY); 415 for (int y = 0; y <= countY; y++) { 416 // sk_assert_monotonic_y(&monoY[y * 3], 4); 417 SkPoint monoX[10]; 418 int countX = SkChopCubicAtXExtrema(&monoY[y * 3], monoX); 419 for (int x = 0; x <= countX; x++) { 420 // sk_assert_monotonic_y(&monoX[x * 3], 4); 421 // sk_assert_monotonic_x(&monoX[x * 3], 4); 422 this->clipMonoCubic(&monoX[x * 3], clip); 423 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs); 424 SkASSERT(fCurrPoint - fPoints <= kMaxPoints); 425 } 426 } 427 } 428 429 *fCurrVerb = SkPath::kDone_Verb; 430 fCurrPoint = fPoints; 431 fCurrVerb = fVerbs; 432 return SkPath::kDone_Verb != fVerbs[0]; 433} 434 435/////////////////////////////////////////////////////////////////////////////// 436 437void SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1, 438 bool reverse) { 439 *fCurrVerb++ = SkPath::kLine_Verb; 440 441 if (reverse) { 442 SkTSwap<SkScalar>(y0, y1); 443 } 444 fCurrPoint[0].set(x, y0); 445 fCurrPoint[1].set(x, y1); 446 fCurrPoint += 2; 447} 448 449void SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) { 450 *fCurrVerb++ = SkPath::kQuad_Verb; 451 452 if (reverse) { 453 fCurrPoint[0] = pts[2]; 454 fCurrPoint[2] = pts[0]; 455 } else { 456 fCurrPoint[0] = pts[0]; 457 fCurrPoint[2] = pts[2]; 458 } 459 fCurrPoint[1] = pts[1]; 460 fCurrPoint += 3; 461} 462 463void SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) { 464 *fCurrVerb++ = SkPath::kCubic_Verb; 465 466 if (reverse) { 467 for (int i = 0; i < 4; i++) { 468 fCurrPoint[i] = pts[3 - i]; 469 } 470 } else { 471 memcpy(fCurrPoint, pts, 4 * sizeof(SkPoint)); 472 } 473 fCurrPoint += 4; 474} 475 476SkPath::Verb SkEdgeClipper::next(SkPoint pts[]) { 477 SkPath::Verb verb = *fCurrVerb; 478 479 switch (verb) { 480 case SkPath::kLine_Verb: 481 memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint)); 482 fCurrPoint += 2; 483 fCurrVerb += 1; 484 break; 485 case SkPath::kQuad_Verb: 486 memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint)); 487 fCurrPoint += 3; 488 fCurrVerb += 1; 489 break; 490 case SkPath::kCubic_Verb: 491 memcpy(pts, fCurrPoint, 4 * sizeof(SkPoint)); 492 fCurrPoint += 4; 493 fCurrVerb += 1; 494 break; 495 case SkPath::kDone_Verb: 496 break; 497 default: 498 SkDEBUGFAIL("unexpected verb in quadclippper2 iter"); 499 break; 500 } 501 return verb; 502} 503 504/////////////////////////////////////////////////////////////////////////////// 505 506#ifdef SK_DEBUG 507static void assert_monotonic(const SkScalar coord[], int count) { 508 if (coord[0] > coord[(count - 1) * 2]) { 509 for (int i = 1; i < count; i++) { 510 SkASSERT(coord[2 * (i - 1)] >= coord[i * 2]); 511 } 512 } else if (coord[0] < coord[(count - 1) * 2]) { 513 for (int i = 1; i < count; i++) { 514 SkASSERT(coord[2 * (i - 1)] <= coord[i * 2]); 515 } 516 } else { 517 for (int i = 1; i < count; i++) { 518 SkASSERT(coord[2 * (i - 1)] == coord[i * 2]); 519 } 520 } 521} 522 523void sk_assert_monotonic_y(const SkPoint pts[], int count) { 524 if (count > 1) { 525 assert_monotonic(&pts[0].fY, count); 526 } 527} 528 529void sk_assert_monotonic_x(const SkPoint pts[], int count) { 530 if (count > 1) { 531 assert_monotonic(&pts[0].fX, count); 532 } 533} 534#endif 535