SkEdgeClipper.cpp revision a3d901099d7d295cd7d9df4114e874d9ccfff447
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 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 53/////////////////////////////////////////////////////////////////////////////// 54 55static 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 74static 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 78static 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 83static 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 128void 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 196bool 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 225static 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 */ 233static 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 266static 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 270static 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 275static 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 clamp_ge(tmp[3].fY, clip.fTop); 284 clamp_ge(tmp[4].fY, clip.fTop); 285 clamp_ge(tmp[5].fY, clip.fTop); 286 pts[0] = tmp[3]; 287 pts[1] = tmp[4]; 288 pts[2] = tmp[5]; 289 } else { 290 // if chopMonoCubicAtY failed, then we may have hit inexact numerics 291 // so we just clamp against the top 292 for (int i = 0; i < 4; i++) { 293 clamp_ge(pts[i].fY, clip.fTop); 294 } 295 } 296 } 297 298 // are we partially below 299 if (pts[3].fY > clip.fBottom) { 300 if (chopMonoCubicAtY(pts, clip.fBottom, &t)) { 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 319void 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 SkScalar t; 349 SkPoint tmp[7]; 350 351 // are we partially to the left 352 if (pts[0].fX < clip.fLeft) { 353 if (chopMonoCubicAtX(pts, clip.fLeft, &t)) { 354 SkChopCubicAt(pts, tmp, t); 355 this->appendVLine(clip.fLeft, tmp[0].fY, tmp[3].fY, reverse); 356 clamp_ge(tmp[3].fX, clip.fLeft); 357 clamp_ge(tmp[4].fX, clip.fLeft); 358 clamp_ge(tmp[5].fX, clip.fLeft); 359 pts[0] = tmp[3]; 360 pts[1] = tmp[4]; 361 pts[2] = tmp[5]; 362 } else { 363 // if chopMonocubicAtY failed, then we may have hit inexact numerics 364 // so we just clamp against the left 365 this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse); 366 return; 367 } 368 } 369 370 // are we partially to the right 371 if (pts[3].fX > clip.fRight) { 372 if (chopMonoCubicAtX(pts, clip.fRight, &t)) { 373 SkChopCubicAt(pts, tmp, t); 374 clamp_le(tmp[1].fX, clip.fRight); 375 clamp_le(tmp[2].fX, clip.fRight); 376 clamp_le(tmp[3].fX, clip.fRight); 377 this->appendCubic(tmp, reverse); 378 this->appendVLine(clip.fRight, tmp[3].fY, tmp[6].fY, reverse); 379 } else { 380 // if chopMonoCubicAtX failed, then we may have hit inexact numerics 381 // so we just clamp against the right 382 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse); 383 } 384 } else { // wholly inside the clip 385 this->appendCubic(pts, reverse); 386 } 387} 388 389bool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) { 390 fCurrPoint = fPoints; 391 fCurrVerb = fVerbs; 392 393 SkRect bounds; 394 bounds.set(srcPts, 4); 395 396 if (!quick_reject(bounds, clip)) { 397 SkPoint monoY[10]; 398 int countY = SkChopCubicAtYExtrema(srcPts, monoY); 399 for (int y = 0; y <= countY; y++) { 400 // sk_assert_monotonic_y(&monoY[y * 3], 4); 401 SkPoint monoX[10]; 402 int countX = SkChopCubicAtXExtrema(&monoY[y * 3], monoX); 403 for (int x = 0; x <= countX; x++) { 404 // sk_assert_monotonic_y(&monoX[x * 3], 4); 405 // sk_assert_monotonic_x(&monoX[x * 3], 4); 406 this->clipMonoCubic(&monoX[x * 3], clip); 407 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs); 408 SkASSERT(fCurrPoint - fPoints <= kMaxPoints); 409 } 410 } 411 } 412 413 *fCurrVerb = SkPath::kDone_Verb; 414 fCurrPoint = fPoints; 415 fCurrVerb = fVerbs; 416 return SkPath::kDone_Verb != fVerbs[0]; 417} 418 419/////////////////////////////////////////////////////////////////////////////// 420 421void SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1, 422 bool reverse) { 423 *fCurrVerb++ = SkPath::kLine_Verb; 424 425 if (reverse) { 426 SkTSwap<SkScalar>(y0, y1); 427 } 428 fCurrPoint[0].set(x, y0); 429 fCurrPoint[1].set(x, y1); 430 fCurrPoint += 2; 431} 432 433void SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) { 434 *fCurrVerb++ = SkPath::kQuad_Verb; 435 436 if (reverse) { 437 fCurrPoint[0] = pts[2]; 438 fCurrPoint[2] = pts[0]; 439 } else { 440 fCurrPoint[0] = pts[0]; 441 fCurrPoint[2] = pts[2]; 442 } 443 fCurrPoint[1] = pts[1]; 444 fCurrPoint += 3; 445} 446 447void SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) { 448 *fCurrVerb++ = SkPath::kCubic_Verb; 449 450 if (reverse) { 451 for (int i = 0; i < 4; i++) { 452 fCurrPoint[i] = pts[3 - i]; 453 } 454 } else { 455 memcpy(fCurrPoint, pts, 4 * sizeof(SkPoint)); 456 } 457 fCurrPoint += 4; 458} 459 460SkPath::Verb SkEdgeClipper::next(SkPoint pts[]) { 461 SkPath::Verb verb = *fCurrVerb; 462 463 switch (verb) { 464 case SkPath::kLine_Verb: 465 memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint)); 466 fCurrPoint += 2; 467 fCurrVerb += 1; 468 break; 469 case SkPath::kQuad_Verb: 470 memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint)); 471 fCurrPoint += 3; 472 fCurrVerb += 1; 473 break; 474 case SkPath::kCubic_Verb: 475 memcpy(pts, fCurrPoint, 4 * sizeof(SkPoint)); 476 fCurrPoint += 4; 477 fCurrVerb += 1; 478 break; 479 case SkPath::kDone_Verb: 480 break; 481 default: 482 SkASSERT(!"unexpected verb in quadclippper2 iter"); 483 break; 484 } 485 return verb; 486} 487 488/////////////////////////////////////////////////////////////////////////////// 489 490#ifdef SK_DEBUG 491static void assert_monotonic(const SkScalar coord[], int count) { 492 if (coord[0] > coord[(count - 1) * 2]) { 493 for (int i = 1; i < count; i++) { 494 SkASSERT(coord[2 * (i - 1)] >= coord[i * 2]); 495 } 496 } else 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 { 501 for (int i = 1; i < count; i++) { 502 SkASSERT(coord[2 * (i - 1)] == coord[i * 2]); 503 } 504 } 505} 506 507void sk_assert_monotonic_y(const SkPoint pts[], int count) { 508 if (count > 1) { 509 assert_monotonic(&pts[0].fY, count); 510 } 511} 512 513void sk_assert_monotonic_x(const SkPoint pts[], int count) { 514 if (count > 1) { 515 assert_monotonic(&pts[0].fX, count); 516 } 517} 518#endif 519