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