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 // Modify pts[] in place so that it is clipped in Y to the clip rect 229 static void chop_cubic_in_Y(SkPoint pts[4], const SkRect& clip) { 230 231 // are we partially above 232 if (pts[0].fY < clip.fTop) { 233 SkPoint tmp[7]; 234 if (SkChopMonoCubicAtY(pts, clip.fTop, tmp)) { 235 // tmp[3, 4].fY should all be to the below clip.fTop. 236 // Since we can't trust the numerics of 237 // the chopper, we force those conditions now 238 tmp[3].fY = clip.fTop; 239 clamp_ge(tmp[4].fY, clip.fTop); 240 241 pts[0] = tmp[3]; 242 pts[1] = tmp[4]; 243 pts[2] = tmp[5]; 244 } else { 245 // if chopMonoCubicAtY failed, then we may have hit inexact numerics 246 // so we just clamp against the top 247 for (int i = 0; i < 4; i++) { 248 clamp_ge(pts[i].fY, clip.fTop); 249 } 250 } 251 } 252 253 // are we partially below 254 if (pts[3].fY > clip.fBottom) { 255 SkPoint tmp[7]; 256 if (SkChopMonoCubicAtY(pts, clip.fBottom, tmp)) { 257 tmp[3].fY = clip.fBottom; 258 clamp_le(tmp[2].fY, clip.fBottom); 259 260 pts[1] = tmp[1]; 261 pts[2] = tmp[2]; 262 pts[3] = tmp[3]; 263 } else { 264 // if chopMonoCubicAtY failed, then we may have hit inexact numerics 265 // so we just clamp against the bottom 266 for (int i = 0; i < 4; i++) { 267 clamp_le(pts[i].fY, clip.fBottom); 268 } 269 } 270 } 271 } 272 273 // srcPts[] must be monotonic in X and Y 274 void SkEdgeClipper::clipMonoCubic(const SkPoint src[4], const SkRect& clip) { 275 SkPoint pts[4]; 276 bool reverse = sort_increasing_Y(pts, src, 4); 277 278 // are we completely above or below 279 if (pts[3].fY <= clip.fTop || pts[0].fY >= clip.fBottom) { 280 return; 281 } 282 283 // Now chop so that pts is contained within clip in Y 284 chop_cubic_in_Y(pts, clip); 285 286 if (pts[0].fX > pts[3].fX) { 287 SkTSwap<SkPoint>(pts[0], pts[3]); 288 SkTSwap<SkPoint>(pts[1], pts[2]); 289 reverse = !reverse; 290 } 291 292 // Now chop in X has needed, and record the segments 293 294 if (pts[3].fX <= clip.fLeft) { // wholly to the left 295 this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse); 296 return; 297 } 298 if (pts[0].fX >= clip.fRight) { // wholly to the right 299 if (!this->canCullToTheRight()) { 300 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse); 301 } 302 return; 303 } 304 305 // are we partially to the left 306 if (pts[0].fX < clip.fLeft) { 307 SkPoint tmp[7]; 308 if (SkChopMonoCubicAtX(pts, clip.fLeft, tmp)) { 309 this->appendVLine(clip.fLeft, tmp[0].fY, tmp[3].fY, reverse); 310 311 // tmp[3, 4].fX should all be to the right of clip.fLeft. 312 // Since we can't trust the numerics of 313 // the chopper, we force those conditions now 314 tmp[3].fX = clip.fLeft; 315 clamp_ge(tmp[4].fX, clip.fLeft); 316 317 pts[0] = tmp[3]; 318 pts[1] = tmp[4]; 319 pts[2] = tmp[5]; 320 } else { 321 // if chopMonocubicAtY failed, then we may have hit inexact numerics 322 // so we just clamp against the left 323 this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse); 324 return; 325 } 326 } 327 328 // are we partially to the right 329 if (pts[3].fX > clip.fRight) { 330 SkPoint tmp[7]; 331 if (SkChopMonoCubicAtX(pts, clip.fRight, tmp)) { 332 tmp[3].fX = clip.fRight; 333 clamp_le(tmp[2].fX, clip.fRight); 334 335 this->appendCubic(tmp, reverse); 336 this->appendVLine(clip.fRight, tmp[3].fY, tmp[6].fY, reverse); 337 } else { 338 // if chopMonoCubicAtX failed, then we may have hit inexact numerics 339 // so we just clamp against the right 340 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse); 341 } 342 } else { // wholly inside the clip 343 this->appendCubic(pts, reverse); 344 } 345 } 346 347 bool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) { 348 fCurrPoint = fPoints; 349 fCurrVerb = fVerbs; 350 351 SkRect bounds; 352 bounds.set(srcPts, 4); 353 354 if (!quick_reject(bounds, clip)) { 355 SkPoint monoY[10]; 356 int countY = SkChopCubicAtYExtrema(srcPts, monoY); 357 for (int y = 0; y <= countY; y++) { 358 SkPoint monoX[10]; 359 int countX = SkChopCubicAtXExtrema(&monoY[y * 3], monoX); 360 for (int x = 0; x <= countX; x++) { 361 this->clipMonoCubic(&monoX[x * 3], clip); 362 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs); 363 SkASSERT(fCurrPoint - fPoints <= kMaxPoints); 364 } 365 } 366 } 367 368 *fCurrVerb = SkPath::kDone_Verb; 369 fCurrPoint = fPoints; 370 fCurrVerb = fVerbs; 371 return SkPath::kDone_Verb != fVerbs[0]; 372 } 373 374 /////////////////////////////////////////////////////////////////////////////// 375 376 void SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1, 377 bool reverse) { 378 *fCurrVerb++ = SkPath::kLine_Verb; 379 380 if (reverse) { 381 SkTSwap<SkScalar>(y0, y1); 382 } 383 fCurrPoint[0].set(x, y0); 384 fCurrPoint[1].set(x, y1); 385 fCurrPoint += 2; 386 } 387 388 void SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) { 389 *fCurrVerb++ = SkPath::kQuad_Verb; 390 391 if (reverse) { 392 fCurrPoint[0] = pts[2]; 393 fCurrPoint[2] = pts[0]; 394 } else { 395 fCurrPoint[0] = pts[0]; 396 fCurrPoint[2] = pts[2]; 397 } 398 fCurrPoint[1] = pts[1]; 399 fCurrPoint += 3; 400 } 401 402 void SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) { 403 *fCurrVerb++ = SkPath::kCubic_Verb; 404 405 if (reverse) { 406 for (int i = 0; i < 4; i++) { 407 fCurrPoint[i] = pts[3 - i]; 408 } 409 } else { 410 memcpy(fCurrPoint, pts, 4 * sizeof(SkPoint)); 411 } 412 fCurrPoint += 4; 413 } 414 415 SkPath::Verb SkEdgeClipper::next(SkPoint pts[]) { 416 SkPath::Verb verb = *fCurrVerb; 417 418 switch (verb) { 419 case SkPath::kLine_Verb: 420 memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint)); 421 fCurrPoint += 2; 422 fCurrVerb += 1; 423 break; 424 case SkPath::kQuad_Verb: 425 memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint)); 426 fCurrPoint += 3; 427 fCurrVerb += 1; 428 break; 429 case SkPath::kCubic_Verb: 430 memcpy(pts, fCurrPoint, 4 * sizeof(SkPoint)); 431 fCurrPoint += 4; 432 fCurrVerb += 1; 433 break; 434 case SkPath::kDone_Verb: 435 break; 436 default: 437 SkDEBUGFAIL("unexpected verb in quadclippper2 iter"); 438 break; 439 } 440 return verb; 441 } 442 443 /////////////////////////////////////////////////////////////////////////////// 444 445 #ifdef SK_DEBUG 446 static void assert_monotonic(const SkScalar coord[], int count) { 447 if (coord[0] > coord[(count - 1) * 2]) { 448 for (int i = 1; i < count; i++) { 449 SkASSERT(coord[2 * (i - 1)] >= coord[i * 2]); 450 } 451 } else if (coord[0] < coord[(count - 1) * 2]) { 452 for (int i = 1; i < count; i++) { 453 SkASSERT(coord[2 * (i - 1)] <= coord[i * 2]); 454 } 455 } else { 456 for (int i = 1; i < count; i++) { 457 SkASSERT(coord[2 * (i - 1)] == coord[i * 2]); 458 } 459 } 460 } 461 462 void sk_assert_monotonic_y(const SkPoint pts[], int count) { 463 if (count > 1) { 464 assert_monotonic(&pts[0].fY, count); 465 } 466 } 467 468 void sk_assert_monotonic_x(const SkPoint pts[], int count) { 469 if (count > 1) { 470 assert_monotonic(&pts[0].fX, count); 471 } 472 } 473 #endif 474
