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