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 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 125 void 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 if (!this->canCullToTheRight()) { 152 this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse); 153 } 154 return; 155 } 156 157 SkScalar t; 158 SkPoint tmp[5]; // for SkChopQuadAt 159 160 // are we partially to the left 161 if (pts[0].fX < clip.fLeft) { 162 if (chopMonoQuadAtX(pts, clip.fLeft, &t)) { 163 SkChopQuadAt(pts, tmp, t); 164 this->appendVLine(clip.fLeft, tmp[0].fY, tmp[2].fY, reverse); 165 // clamp to clean up imprecise numerics in the chop 166 tmp[2].fX = clip.fLeft; 167 clamp_ge(tmp[3].fX, clip.fLeft); 168 169 pts[0] = tmp[2]; 170 pts[1] = tmp[3]; 171 } else { 172 // if chopMonoQuadAtY failed, then we may have hit inexact numerics 173 // so we just clamp against the left 174 this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse); 175 return; 176 } 177 } 178 179 // are we partially to the right 180 if (pts[2].fX > clip.fRight) { 181 if (chopMonoQuadAtX(pts, clip.fRight, &t)) { 182 SkChopQuadAt(pts, tmp, t); 183 // clamp to clean up imprecise numerics in the chop 184 clamp_le(tmp[1].fX, clip.fRight); 185 tmp[2].fX = clip.fRight; 186 187 this->appendQuad(tmp, reverse); 188 this->appendVLine(clip.fRight, tmp[2].fY, tmp[4].fY, reverse); 189 } else { 190 // if chopMonoQuadAtY failed, then we may have hit inexact numerics 191 // so we just clamp against the right 192 this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse); 193 } 194 } else { // wholly inside the clip 195 this->appendQuad(pts, reverse); 196 } 197 } 198 199 bool SkEdgeClipper::clipQuad(const SkPoint srcPts[3], const SkRect& clip) { 200 fCurrPoint = fPoints; 201 fCurrVerb = fVerbs; 202 203 SkRect bounds; 204 bounds.set(srcPts, 3); 205 206 if (!quick_reject(bounds, clip)) { 207 SkPoint monoY[5]; 208 int countY = SkChopQuadAtYExtrema(srcPts, monoY); 209 for (int y = 0; y <= countY; y++) { 210 SkPoint monoX[5]; 211 int countX = SkChopQuadAtXExtrema(&monoY[y * 2], monoX); 212 for (int x = 0; x <= countX; x++) { 213 this->clipMonoQuad(&monoX[x * 2], clip); 214 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs); 215 SkASSERT(fCurrPoint - fPoints <= kMaxPoints); 216 } 217 } 218 } 219 220 *fCurrVerb = SkPath::kDone_Verb; 221 fCurrPoint = fPoints; 222 fCurrVerb = fVerbs; 223 return SkPath::kDone_Verb != fVerbs[0]; 224 } 225 226 /////////////////////////////////////////////////////////////////////////////// 227 228 static SkScalar mono_cubic_closestT(const SkScalar src[], SkScalar x) { 229 SkScalar t = 0.5f; 230 SkScalar lastT; 231 SkScalar bestT SK_INIT_TO_AVOID_WARNING; 232 SkScalar step = 0.25f; 233 SkScalar D = src[0]; 234 SkScalar A = src[6] + 3*(src[2] - src[4]) - D; 235 SkScalar B = 3*(src[4] - src[2] - src[2] + D); 236 SkScalar C = 3*(src[2] - D); 237 x -= D; 238 SkScalar closest = SK_ScalarMax; 239 do { 240 SkScalar loc = ((A * t + B) * t + C) * t; 241 SkScalar dist = SkScalarAbs(loc - x); 242 if (closest > dist) { 243 closest = dist; 244 bestT = t; 245 } 246 lastT = t; 247 t += loc < x ? step : -step; 248 step *= 0.5f; 249 } while (closest > 0.25f && lastT != t); 250 return bestT; 251 } 252 253 static void chop_mono_cubic_at_y(SkPoint src[4], SkScalar y, SkPoint dst[7]) { 254 if (SkChopMonoCubicAtY(src, y, dst)) { 255 return; 256 } 257 SkChopCubicAt(src, dst, mono_cubic_closestT(&src->fY, y)); 258 } 259 260 // Modify pts[] in place so that it is clipped in Y to the clip rect 261 static void chop_cubic_in_Y(SkPoint pts[4], const SkRect& clip) { 262 263 // are we partially above 264 if (pts[0].fY < clip.fTop) { 265 SkPoint tmp[7]; 266 chop_mono_cubic_at_y(pts, clip.fTop, tmp); 267 // tmp[3, 4].fY should all be to the below clip.fTop. 268 // Since we can't trust the numerics of 269 // the chopper, we force those conditions now 270 tmp[3].fY = clip.fTop; 271 clamp_ge(tmp[4].fY, clip.fTop); 272 273 pts[0] = tmp[3]; 274 pts[1] = tmp[4]; 275 pts[2] = tmp[5]; 276 } 277 278 // are we partially below 279 if (pts[3].fY > clip.fBottom) { 280 SkPoint tmp[7]; 281 chop_mono_cubic_at_y(pts, clip.fBottom, tmp); 282 tmp[3].fY = clip.fBottom; 283 clamp_le(tmp[2].fY, clip.fBottom); 284 285 pts[1] = tmp[1]; 286 pts[2] = tmp[2]; 287 pts[3] = tmp[3]; 288 } 289 } 290 291 static void chop_mono_cubic_at_x(SkPoint src[4], SkScalar x, SkPoint dst[7]) { 292 if (SkChopMonoCubicAtX(src, x, dst)) { 293 return; 294 } 295 SkChopCubicAt(src, dst, mono_cubic_closestT(&src->fX, x)); 296 } 297 298 // srcPts[] must be monotonic in X and Y 299 void SkEdgeClipper::clipMonoCubic(const SkPoint src[4], const SkRect& clip) { 300 SkPoint pts[4]; 301 bool reverse = sort_increasing_Y(pts, src, 4); 302 303 // are we completely above or below 304 if (pts[3].fY <= clip.fTop || pts[0].fY >= clip.fBottom) { 305 return; 306 } 307 308 // Now chop so that pts is contained within clip in Y 309 chop_cubic_in_Y(pts, clip); 310 311 if (pts[0].fX > pts[3].fX) { 312 SkTSwap<SkPoint>(pts[0], pts[3]); 313 SkTSwap<SkPoint>(pts[1], pts[2]); 314 reverse = !reverse; 315 } 316 317 // Now chop in X has needed, and record the segments 318 319 if (pts[3].fX <= clip.fLeft) { // wholly to the left 320 this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse); 321 return; 322 } 323 if (pts[0].fX >= clip.fRight) { // wholly to the right 324 if (!this->canCullToTheRight()) { 325 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse); 326 } 327 return; 328 } 329 330 // are we partially to the left 331 if (pts[0].fX < clip.fLeft) { 332 SkPoint tmp[7]; 333 chop_mono_cubic_at_x(pts, clip.fLeft, tmp); 334 this->appendVLine(clip.fLeft, tmp[0].fY, tmp[3].fY, reverse); 335 336 // tmp[3, 4].fX should all be to the right of clip.fLeft. 337 // Since we can't trust the numerics of 338 // the chopper, we force those conditions now 339 tmp[3].fX = clip.fLeft; 340 clamp_ge(tmp[4].fX, clip.fLeft); 341 342 pts[0] = tmp[3]; 343 pts[1] = tmp[4]; 344 pts[2] = tmp[5]; 345 } 346 347 // are we partially to the right 348 if (pts[3].fX > clip.fRight) { 349 SkPoint tmp[7]; 350 chop_mono_cubic_at_x(pts, clip.fRight, tmp); 351 tmp[3].fX = clip.fRight; 352 clamp_le(tmp[2].fX, clip.fRight); 353 354 this->appendCubic(tmp, reverse); 355 this->appendVLine(clip.fRight, tmp[3].fY, tmp[6].fY, reverse); 356 } else { // wholly inside the clip 357 this->appendCubic(pts, reverse); 358 } 359 } 360 361 static bool quick_reject_in_y(const SkPoint pts[4], const SkRect& clip) { 362 Sk4s ys(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY); 363 Sk4s t(clip.top()); 364 Sk4s b(clip.bottom()); 365 366 return (ys < t).allTrue() || (ys > b).allTrue(); 367 } 368 369 bool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) { 370 fCurrPoint = fPoints; 371 fCurrVerb = fVerbs; 372 373 if (!quick_reject_in_y(srcPts, clip)) { 374 SkPoint monoY[10]; 375 int countY = SkChopCubicAtYExtrema(srcPts, monoY); 376 for (int y = 0; y <= countY; y++) { 377 SkPoint monoX[10]; 378 int countX = SkChopCubicAtXExtrema(&monoY[y * 3], monoX); 379 for (int x = 0; x <= countX; x++) { 380 this->clipMonoCubic(&monoX[x * 3], clip); 381 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs); 382 SkASSERT(fCurrPoint - fPoints <= kMaxPoints); 383 } 384 } 385 } 386 387 *fCurrVerb = SkPath::kDone_Verb; 388 fCurrPoint = fPoints; 389 fCurrVerb = fVerbs; 390 return SkPath::kDone_Verb != fVerbs[0]; 391 } 392 393 /////////////////////////////////////////////////////////////////////////////// 394 395 void SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1, 396 bool reverse) { 397 *fCurrVerb++ = SkPath::kLine_Verb; 398 399 if (reverse) { 400 SkTSwap<SkScalar>(y0, y1); 401 } 402 fCurrPoint[0].set(x, y0); 403 fCurrPoint[1].set(x, y1); 404 fCurrPoint += 2; 405 } 406 407 void SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) { 408 *fCurrVerb++ = SkPath::kQuad_Verb; 409 410 if (reverse) { 411 fCurrPoint[0] = pts[2]; 412 fCurrPoint[2] = pts[0]; 413 } else { 414 fCurrPoint[0] = pts[0]; 415 fCurrPoint[2] = pts[2]; 416 } 417 fCurrPoint[1] = pts[1]; 418 fCurrPoint += 3; 419 } 420 421 void SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) { 422 *fCurrVerb++ = SkPath::kCubic_Verb; 423 424 if (reverse) { 425 for (int i = 0; i < 4; i++) { 426 fCurrPoint[i] = pts[3 - i]; 427 } 428 } else { 429 memcpy(fCurrPoint, pts, 4 * sizeof(SkPoint)); 430 } 431 fCurrPoint += 4; 432 } 433 434 SkPath::Verb SkEdgeClipper::next(SkPoint pts[]) { 435 SkPath::Verb verb = *fCurrVerb; 436 437 switch (verb) { 438 case SkPath::kLine_Verb: 439 memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint)); 440 fCurrPoint += 2; 441 fCurrVerb += 1; 442 break; 443 case SkPath::kQuad_Verb: 444 memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint)); 445 fCurrPoint += 3; 446 fCurrVerb += 1; 447 break; 448 case SkPath::kCubic_Verb: 449 memcpy(pts, fCurrPoint, 4 * sizeof(SkPoint)); 450 fCurrPoint += 4; 451 fCurrVerb += 1; 452 break; 453 case SkPath::kDone_Verb: 454 break; 455 default: 456 SkDEBUGFAIL("unexpected verb in quadclippper2 iter"); 457 break; 458 } 459 return verb; 460 } 461 462 /////////////////////////////////////////////////////////////////////////////// 463 464 #ifdef SK_DEBUG 465 static void assert_monotonic(const SkScalar coord[], int count) { 466 if (coord[0] > coord[(count - 1) * 2]) { 467 for (int i = 1; i < count; i++) { 468 SkASSERT(coord[2 * (i - 1)] >= coord[i * 2]); 469 } 470 } else if (coord[0] < coord[(count - 1) * 2]) { 471 for (int i = 1; i < count; i++) { 472 SkASSERT(coord[2 * (i - 1)] <= coord[i * 2]); 473 } 474 } else { 475 for (int i = 1; i < count; i++) { 476 SkASSERT(coord[2 * (i - 1)] == coord[i * 2]); 477 } 478 } 479 } 480 481 void sk_assert_monotonic_y(const SkPoint pts[], int count) { 482 if (count > 1) { 483 assert_monotonic(&pts[0].fY, count); 484 } 485 } 486 487 void sk_assert_monotonic_x(const SkPoint pts[], int count) { 488 if (count > 1) { 489 assert_monotonic(&pts[0].fX, count); 490 } 491 } 492 #endif 493
