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