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