1 /* 2 * Copyright 2012 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 #include "EdgeWalker_Test.h" 8 #include "Intersection_Tests.h" 9 #include "SkBitmap.h" 10 11 static SkBitmap bitmap; 12 13 static void testSimplifyCoincidentInner() { 14 SkPath path, out; 15 path.setFillType(SkPath::kWinding_FillType); 16 path.addRect(10, 10, 60, 60, SkPath::kCCW_Direction); 17 path.addRect(20, 20, 50, 50, SkPath::kCW_Direction); 18 path.addRect(20, 30, 40, 40, SkPath::kCW_Direction); 19 testSimplify(path, true, out, bitmap); 20 } 21 22 static void testSimplifyCoincidentVertical() { 23 SkPath path, out; 24 path.setFillType(SkPath::kWinding_FillType); 25 path.addRect(10, 10, 30, 30); 26 path.addRect(10, 30, 30, 40); 27 simplify(path, true, out); 28 SkRect rect; 29 if (!out.isRect(&rect)) { 30 SkDebugf("%s expected rect\n", __FUNCTION__); 31 } 32 if (rect != SkRect::MakeLTRB(10, 10, 30, 40)) { 33 SkDebugf("%s expected union\n", __FUNCTION__); 34 } 35 } 36 37 static void testSimplifyCoincidentHorizontal() { 38 SkPath path, out; 39 path.setFillType(SkPath::kWinding_FillType); 40 path.addRect(10, 10, 30, 30); 41 path.addRect(30, 10, 40, 30); 42 simplify(path, true, out); 43 SkRect rect; 44 if (!out.isRect(&rect)) { 45 SkDebugf("%s expected rect\n", __FUNCTION__); 46 } 47 if (rect != SkRect::MakeLTRB(10, 10, 40, 30)) { 48 SkDebugf("%s expected union\n", __FUNCTION__); 49 } 50 } 51 52 static void testSimplifyMulti() { 53 SkPath path, out; 54 path.setFillType(SkPath::kWinding_FillType); 55 path.addRect(10, 10, 30, 30); 56 path.addRect(20, 20, 40, 40); 57 simplify(path, true, out); 58 SkPath expected; 59 expected.setFillType(SkPath::kEvenOdd_FillType); 60 expected.moveTo(10,10); // two cutout corners 61 expected.lineTo(10,30); 62 expected.lineTo(20,30); 63 expected.lineTo(20,40); 64 expected.lineTo(40,40); 65 expected.lineTo(40,20); 66 expected.lineTo(30,20); 67 expected.lineTo(30,10); 68 expected.lineTo(10,10); 69 expected.close(); 70 if (out != expected) { 71 SkDebugf("%s expected equal\n", __FUNCTION__); 72 } 73 74 path = out; 75 path.addRect(30, 10, 40, 20); 76 path.addRect(10, 30, 20, 40); 77 simplify(path, true, out); 78 SkRect rect; 79 if (!out.isRect(&rect)) { 80 SkDebugf("%s expected rect\n", __FUNCTION__); 81 } 82 if (rect != SkRect::MakeLTRB(10, 10, 40, 40)) { 83 SkDebugf("%s expected union\n", __FUNCTION__); 84 } 85 86 path = out; 87 path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction); 88 simplify(path, true, out); 89 if (!out.isEmpty()) { 90 SkDebugf("%s expected empty\n", __FUNCTION__); 91 } 92 } 93 94 static void testSimplifyAddL() { 95 SkPath path, out; 96 path.moveTo(10,10); // 'L' shape 97 path.lineTo(10,40); 98 path.lineTo(40,40); 99 path.lineTo(40,20); 100 path.lineTo(30,20); 101 path.lineTo(30,10); 102 path.lineTo(10,10); 103 path.close(); 104 path.addRect(30, 10, 40, 20); // missing notch of 'L' 105 simplify(path, true, out); 106 SkRect rect; 107 if (!out.isRect(&rect)) { 108 SkDebugf("%s expected rect\n", __FUNCTION__); 109 } 110 if (rect != SkRect::MakeLTRB(10, 10, 40, 40)) { 111 SkDebugf("%s expected union\n", __FUNCTION__); 112 } 113 } 114 115 static void testSimplifyCoincidentCCW() { 116 SkPath path, out; 117 path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction); 118 path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction); 119 simplify(path, true, out); 120 SkRect rect; 121 if (!out.isRect(&rect)) { 122 SkDebugf("%s expected rect\n", __FUNCTION__); 123 } 124 if (rect != SkRect::MakeLTRB(10, 10, 40, 40)) { 125 SkDebugf("%s expected union\n", __FUNCTION__); 126 } 127 } 128 129 static void testSimplifyCoincidentCW() { 130 SkPath path, out; 131 path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction); 132 path.addRect(10, 10, 40, 40, SkPath::kCW_Direction); 133 simplify(path, true, out); 134 if (!out.isEmpty()) { 135 SkDebugf("%s expected empty\n", __FUNCTION__); 136 } 137 } 138 139 static void testSimplifyCorner() { 140 SkPath path, out; 141 path.addRect(10, 10, 20, 20, SkPath::kCCW_Direction); 142 path.addRect(20, 20, 40, 40, SkPath::kCW_Direction); 143 simplify(path, true, out); 144 SkTDArray<SkRect> boundsArray; 145 contourBounds(out, boundsArray); 146 if (boundsArray.count() != 2) { 147 SkDebugf("%s expected 2 contours\n", __FUNCTION__); 148 return; 149 } 150 SkRect one = SkRect::MakeLTRB(10, 10, 20, 20); 151 SkRect two = SkRect::MakeLTRB(20, 20, 40, 40); 152 if ((boundsArray[0] != one && boundsArray[0] != two) 153 || (boundsArray[1] != one && boundsArray[1] != two)) { 154 SkDebugf("%s expected match\n", __FUNCTION__); 155 } 156 } 157 158 static void testSimplifyDiagonal() { 159 SkRect rect2 = SkRect::MakeXYWH(10, 10, 10, 10); 160 for (size_t outDir = SkPath::kCW_Direction; outDir <= SkPath::kCCW_Direction; ++outDir) { 161 for (size_t inDir = SkPath::kCW_Direction; inDir <= SkPath::kCCW_Direction; ++inDir) { 162 for (int x = 0; x <= 20; x += 20) { 163 for (int y = 0; y <= 20; y += 20) { 164 SkPath path, out; 165 SkRect rect1 = SkRect::MakeXYWH(x, y, 10, 10); 166 path.addRect(rect1, static_cast<SkPath::Direction>(outDir)); 167 path.addRect(rect2, static_cast<SkPath::Direction>(inDir)); 168 simplify(path, true, out); 169 SkPath::Iter iter(out, false); 170 SkPoint pts[4], lastLine[2]; 171 SkPath::Verb verb; 172 SkRect bounds[2]; 173 bounds[0].setEmpty(); 174 bounds[1].setEmpty(); 175 SkRect* boundsPtr = bounds; 176 int count = 0, segments = 0; 177 bool lastLineSet = false; 178 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 179 switch (verb) { 180 case SkPath::kMove_Verb: 181 if (!boundsPtr->isEmpty()) { 182 SkASSERT(boundsPtr == bounds); 183 ++boundsPtr; 184 } 185 boundsPtr->set(pts[0].fX, pts[0].fY, pts[0].fX, pts[0].fY); 186 count = 0; 187 lastLineSet = false; 188 break; 189 case SkPath::kLine_Verb: 190 if (lastLineSet) { 191 SkASSERT((lastLine[1].fX - lastLine[0].fX) * 192 (pts[1].fY - lastLine[0].fY) != 193 (lastLine[1].fY - lastLine[0].fY) * 194 (pts[1].fX - lastLine[0].fX)); 195 } 196 lastLineSet = true; 197 lastLine[0] = pts[0]; 198 lastLine[1] = pts[1]; 199 count = 1; 200 ++segments; 201 break; 202 case SkPath::kClose_Verb: 203 count = 0; 204 break; 205 default: 206 SkDEBUGFAIL("bad verb"); 207 return; 208 } 209 for (int i = 1; i <= count; ++i) { 210 boundsPtr->growToInclude(pts[i].fX, pts[i].fY); 211 } 212 } 213 if (boundsPtr != bounds) { 214 SkASSERT((bounds[0] == rect1 || bounds[1] == rect1) 215 && (bounds[0] == rect2 || bounds[1] == rect2)); 216 } else { 217 SkASSERT(segments == 8); 218 } 219 } 220 } 221 } 222 } 223 } 224 225 static void assertOneContour(const SkPath& out, bool edge, bool extend) { 226 SkPath::Iter iter(out, false); 227 SkPoint pts[4]; 228 SkPath::Verb verb; 229 SkRect bounds; 230 bounds.setEmpty(); 231 int count = 0; 232 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 233 switch (verb) { 234 case SkPath::kMove_Verb: 235 SkASSERT(count == 0); 236 break; 237 case SkPath::kLine_Verb: 238 SkASSERT(pts[0].fX == pts[1].fX || pts[0].fY == pts[1].fY); 239 ++count; 240 break; 241 case SkPath::kClose_Verb: 242 break; 243 default: 244 SkDEBUGFAIL("bad verb"); 245 return; 246 } 247 } 248 SkASSERT(count == (extend ? 4 : edge ? 6 : 8)); 249 } 250 251 static void testSimplifyCoincident() { 252 // outside to inside, outside to right, outside to outside 253 // left to inside, left to right, left to outside 254 // inside to right, inside to outside 255 // repeat above for left, right, bottom 256 SkScalar start[] = { 0, 10, 20 }; 257 size_t startCount = sizeof(start) / sizeof(start[0]); 258 SkScalar stop[] = { 30, 40, 50 }; 259 size_t stopCount = sizeof(stop) / sizeof(stop[0]); 260 SkRect rect2 = SkRect::MakeXYWH(10, 10, 30, 30); 261 for (size_t outDir = SkPath::kCW_Direction; outDir <= SkPath::kCCW_Direction; ++outDir) { 262 for (size_t inDir = SkPath::kCW_Direction; inDir <= SkPath::kCCW_Direction; ++inDir) { 263 for (size_t startIndex = 0; startIndex < startCount; ++startIndex) { 264 for (size_t stopIndex = 0; stopIndex < stopCount; ++stopIndex) { 265 bool extend = start[startIndex] == rect2.fLeft && stop[stopIndex] == rect2.fRight; 266 bool edge = start[startIndex] == rect2.fLeft || stop[stopIndex] == rect2.fRight; 267 SkRect rect1 = SkRect::MakeLTRB(start[startIndex], 0, stop[stopIndex], 10); 268 SkPath path, out; 269 path.addRect(rect1, static_cast<SkPath::Direction>(outDir)); 270 path.addRect(rect2, static_cast<SkPath::Direction>(inDir)); 271 simplify(path, true, out); 272 assertOneContour(out, edge, extend); 273 274 path.reset(); 275 rect1 = SkRect::MakeLTRB(start[startIndex], 40, stop[stopIndex], 50); 276 path.addRect(rect1, static_cast<SkPath::Direction>(outDir)); 277 path.addRect(rect2, static_cast<SkPath::Direction>(inDir)); 278 simplify(path, true, out); 279 assertOneContour(out, edge, extend); 280 281 path.reset(); 282 rect1 = SkRect::MakeLTRB(0, start[startIndex], 10, stop[stopIndex]); 283 path.addRect(rect1, static_cast<SkPath::Direction>(outDir)); 284 path.addRect(rect2, static_cast<SkPath::Direction>(inDir)); 285 simplify(path, true, out); 286 assertOneContour(out, edge, extend); 287 288 path.reset(); 289 rect1 = SkRect::MakeLTRB(40, start[startIndex], 50, stop[stopIndex]); 290 path.addRect(rect1, static_cast<SkPath::Direction>(outDir)); 291 path.addRect(rect2, static_cast<SkPath::Direction>(inDir)); 292 simplify(path, true, out); 293 assertOneContour(out, edge, extend); 294 } 295 } 296 } 297 } 298 } 299 300 static void testSimplifyOverlap() { 301 SkScalar start[] = { 0, 10, 20 }; 302 size_t startCount = sizeof(start) / sizeof(start[0]); 303 SkScalar stop[] = { 30, 40, 50 }; 304 size_t stopCount = sizeof(stop) / sizeof(stop[0]); 305 SkRect rect2 = SkRect::MakeXYWH(10, 10, 30, 30); 306 for (size_t dir = SkPath::kCW_Direction; dir <= SkPath::kCCW_Direction; ++dir) { 307 for (size_t lefty = 0; lefty < startCount; ++lefty) { 308 for (size_t righty = 0; righty < stopCount; ++righty) { 309 for (size_t toppy = 0; toppy < startCount; ++toppy) { 310 for (size_t botty = 0; botty < stopCount; ++botty) { 311 SkRect rect1 = SkRect::MakeLTRB(start[lefty], start[toppy], 312 stop[righty], stop[botty]); 313 SkPath path, out; 314 path.addRect(rect1, static_cast<SkPath::Direction>(dir)); 315 path.addRect(rect2, static_cast<SkPath::Direction>(dir)); 316 testSimplify(path, true, out, bitmap); 317 } 318 } 319 } 320 } 321 } 322 } 323 324 static void testSimplifyOverlapTiny() { 325 SkScalar start[] = { 0, 1, 2 }; 326 size_t startCount = sizeof(start) / sizeof(start[0]); 327 SkScalar stop[] = { 3, 4, 5 }; 328 size_t stopCount = sizeof(stop) / sizeof(stop[0]); 329 SkRect rect2 = SkRect::MakeXYWH(1, 1, 3, 3); 330 for (size_t dir = SkPath::kCW_Direction; dir <= SkPath::kCCW_Direction; ++dir) { 331 for (size_t lefty = 0; lefty < startCount; ++lefty) { 332 for (size_t righty = 0; righty < stopCount; ++righty) { 333 for (size_t toppy = 0; toppy < startCount; ++toppy) { 334 for (size_t botty = 0; botty < stopCount; ++botty) { 335 SkRect rect1 = SkRect::MakeLTRB(start[lefty], start[toppy], 336 stop[righty], stop[botty]); 337 SkPath path, out; 338 path.addRect(rect1, static_cast<SkPath::Direction>(dir)); 339 path.addRect(rect2, static_cast<SkPath::Direction>(dir)); 340 simplify(path, true, out); 341 comparePathsTiny(path, out); 342 } 343 } 344 } 345 } 346 } 347 } 348 349 static void testSimplifyDegenerate() { 350 SkScalar start[] = { 0, 10, 20 }; 351 size_t startCount = sizeof(start) / sizeof(start[0]); 352 SkScalar stop[] = { 30, 40, 50 }; 353 size_t stopCount = sizeof(stop) / sizeof(stop[0]); 354 SkRect rect2 = SkRect::MakeXYWH(10, 10, 30, 30); 355 for (size_t outDir = SkPath::kCW_Direction; outDir <= SkPath::kCCW_Direction; ++outDir) { 356 for (size_t inDir = SkPath::kCW_Direction; inDir <= SkPath::kCCW_Direction; ++inDir) { 357 for (size_t startIndex = 0; startIndex < startCount; ++startIndex) { 358 for (size_t stopIndex = 0; stopIndex < stopCount; ++stopIndex) { 359 SkRect rect1 = SkRect::MakeLTRB(start[startIndex], 0, stop[stopIndex], 0); 360 SkPath path, out; 361 path.addRect(rect1, static_cast<SkPath::Direction>(outDir)); 362 path.addRect(rect2, static_cast<SkPath::Direction>(inDir)); 363 simplify(path, true, out); 364 SkRect rect; 365 if (!out.isRect(&rect)) { 366 SkDebugf("%s 1 expected rect\n", __FUNCTION__); 367 } 368 if (rect != rect2) { 369 SkDebugf("%s 1 expected union\n", __FUNCTION__); 370 } 371 372 path.reset(); 373 rect1 = SkRect::MakeLTRB(start[startIndex], 40, stop[stopIndex], 40); 374 path.addRect(rect1, static_cast<SkPath::Direction>(outDir)); 375 path.addRect(rect2, static_cast<SkPath::Direction>(inDir)); 376 simplify(path, true, out); 377 if (!out.isRect(&rect)) { 378 SkDebugf("%s 2 expected rect\n", __FUNCTION__); 379 } 380 if (rect != rect2) { 381 SkDebugf("%s 2 expected union\n", __FUNCTION__); 382 } 383 384 path.reset(); 385 rect1 = SkRect::MakeLTRB(0, start[startIndex], 0, stop[stopIndex]); 386 path.addRect(rect1, static_cast<SkPath::Direction>(outDir)); 387 path.addRect(rect2, static_cast<SkPath::Direction>(inDir)); 388 simplify(path, true, out); 389 if (!out.isRect(&rect)) { 390 SkDebugf("%s 3 expected rect\n", __FUNCTION__); 391 } 392 if (rect != rect2) { 393 SkDebugf("%s 3 expected union\n", __FUNCTION__); 394 } 395 396 path.reset(); 397 rect1 = SkRect::MakeLTRB(40, start[startIndex], 40, stop[stopIndex]); 398 path.addRect(rect1, static_cast<SkPath::Direction>(outDir)); 399 path.addRect(rect2, static_cast<SkPath::Direction>(inDir)); 400 simplify(path, true, out); 401 if (!out.isRect(&rect)) { 402 SkDebugf("%s 4 expected rect\n", __FUNCTION__); 403 } 404 if (rect != rect2) { 405 SkDebugf("%s 4 expected union\n", __FUNCTION__); 406 } 407 } 408 } 409 } 410 } 411 } 412 413 static void testSimplifyDegenerate1() { 414 SkPath path, out; 415 path.setFillType(SkPath::kWinding_FillType); 416 path.addRect( 0, 0, 0, 30); 417 path.addRect(10, 10, 40, 40); 418 simplify(path, true, out); 419 SkRect rect; 420 if (!out.isRect(&rect)) { 421 SkDebugf("%s expected rect\n", __FUNCTION__); 422 } 423 if (rect != SkRect::MakeLTRB(10, 10, 40, 40)) { 424 SkDebugf("%s expected union\n", __FUNCTION__); 425 } 426 } 427 428 static void (*simplifyTests[])() = { 429 testSimplifyCoincidentInner, 430 testSimplifyOverlapTiny, 431 testSimplifyDegenerate1, 432 testSimplifyCorner, 433 testSimplifyDegenerate, 434 testSimplifyOverlap, 435 testSimplifyDiagonal, 436 testSimplifyCoincident, 437 testSimplifyCoincidentCW, 438 testSimplifyCoincidentCCW, 439 testSimplifyCoincidentVertical, 440 testSimplifyCoincidentHorizontal, 441 testSimplifyAddL, 442 testSimplifyMulti, 443 }; 444 445 static size_t simplifyTestsCount = sizeof(simplifyTests) / sizeof(simplifyTests[0]); 446 447 static void (*firstTest)() = 0; 448 449 void SimplifyRectangularPaths_Test() { 450 size_t index = 0; 451 if (firstTest) { 452 while (index < simplifyTestsCount && simplifyTests[index] != firstTest) { 453 ++index; 454 } 455 } 456 for ( ; index < simplifyTestsCount; ++index) { 457 if (simplifyTests[index] == testSimplifyCorner) { 458 // testSimplifyCorner fails because it expects two contours, where 459 // only one is returned. Both results are reasonable, but if two 460 // contours are desirable, or if we provide an option to choose 461 // between longer contours and more contours, turn this back on. For 462 // the moment, testSimplifyDiagonal also checks the test case, and 463 // permits either two rects or one non-crossing poly as valid 464 // unreported results. 465 continue; 466 } 467 (*simplifyTests[index])(); 468 } 469 } 470
