OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2013 Google Inc. | 2 * Copyright 2013 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 #include "PathOpsTestCommon.h" | 7 #include "PathOpsTestCommon.h" |
8 #include "SkIntersections.h" | 8 #include "SkIntersections.h" |
9 #include "SkOpContour.h" | |
10 #include "SkOpSegment.h" | 9 #include "SkOpSegment.h" |
| 10 #include "SkPathOpsTriangle.h" |
11 #include "SkRandom.h" | 11 #include "SkRandom.h" |
12 #include "SkTArray.h" | 12 #include "SkTArray.h" |
13 #include "SkTSort.h" | 13 #include "SkTSort.h" |
14 #include "Test.h" | 14 #include "Test.h" |
15 | 15 |
16 static bool gPathOpsAngleIdeasVerbose = false; | 16 static bool gPathOpsAngleIdeasVerbose = false; |
17 static bool gPathOpsAngleIdeasEnableBruteCheck = false; | 17 static bool gPathOpsAngleIdeasEnableBruteCheck = false; |
18 | 18 |
19 class PathOpsAngleTester { | 19 class PathOpsAngleTester { |
20 public: | 20 public: |
21 static int ConvexHullOverlaps(SkOpAngle& lh, SkOpAngle& rh) { | 21 static int ConvexHullOverlaps(const SkOpAngle& lh, const SkOpAngle& rh) { |
22 return lh.convexHullOverlaps(&rh); | 22 return lh.convexHullOverlaps(rh); |
23 } | 23 } |
24 | 24 |
25 static int EndsIntersect(SkOpAngle& lh, SkOpAngle& rh) { | 25 static int EndsIntersect(const SkOpAngle& lh, const SkOpAngle& rh) { |
26 return lh.endsIntersect(&rh); | 26 return lh.endsIntersect(rh); |
27 } | 27 } |
28 }; | 28 }; |
29 | 29 |
30 struct TRange { | 30 struct TRange { |
31 double tMin1; | 31 double tMin1; |
32 double tMin2; | 32 double tMin2; |
33 double t1; | 33 double t1; |
34 double t2; | 34 double t2; |
35 double tMin; | 35 double tMin; |
36 double a1; | 36 double a1; |
(...skipping 362 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
399 } | 399 } |
400 | 400 |
401 static bool bruteForceCheck(skiatest::Reporter* reporter, const SkDQuad& quad1, | 401 static bool bruteForceCheck(skiatest::Reporter* reporter, const SkDQuad& quad1, |
402 const SkDQuad& quad2, bool ccw) { | 402 const SkDQuad& quad2, bool ccw) { |
403 TRange lowerRange, upperRange; | 403 TRange lowerRange, upperRange; |
404 bool result = bruteMinT(reporter, quad1, quad2, &lowerRange, &upperRange); | 404 bool result = bruteMinT(reporter, quad1, quad2, &lowerRange, &upperRange); |
405 REPORTER_ASSERT(reporter, result); | 405 REPORTER_ASSERT(reporter, result); |
406 return ccw == upperRange.ccw; | 406 return ccw == upperRange.ccw; |
407 } | 407 } |
408 | 408 |
409 static void makeSegment(SkOpContour* contour, const SkDQuad& quad, SkPoint short
Quad[3], | 409 class PathOpsSegmentTester { |
410 SkChunkAlloc* allocator) { | 410 public: |
| 411 static void ConstructQuad(SkOpSegment* segment, SkPoint shortQuad[3]) { |
| 412 segment->debugConstructQuad(shortQuad); |
| 413 } |
| 414 }; |
| 415 |
| 416 static void makeSegment(const SkDQuad& quad, SkPoint shortQuad[3], SkOpSegment*
result) { |
411 shortQuad[0] = quad[0].asSkPoint(); | 417 shortQuad[0] = quad[0].asSkPoint(); |
412 shortQuad[1] = quad[1].asSkPoint(); | 418 shortQuad[1] = quad[1].asSkPoint(); |
413 shortQuad[2] = quad[2].asSkPoint(); | 419 shortQuad[2] = quad[2].asSkPoint(); |
414 contour->addQuad(shortQuad, allocator); | 420 PathOpsSegmentTester::ConstructQuad(result, shortQuad); |
415 } | 421 } |
416 | 422 |
417 static void testQuadAngles(skiatest::Reporter* reporter, const SkDQuad& quad1, c
onst SkDQuad& quad2, | 423 static void testQuadAngles(skiatest::Reporter* reporter, const SkDQuad& quad1, c
onst SkDQuad& quad2, |
418 int testNo, SkChunkAlloc* allocator) { | 424 int testNo) { |
419 SkPoint shortQuads[2][3]; | 425 SkPoint shortQuads[2][3]; |
420 | 426 SkOpSegment seg[2]; |
421 SkOpContour contour; | 427 makeSegment(quad1, shortQuads[0], &seg[0]); |
422 SkOpGlobalState state(NULL PATH_OPS_DEBUG_PARAMS(&contour)); | 428 makeSegment(quad2, shortQuads[1], &seg[1]); |
423 contour.init(&state, false, false); | 429 int realOverlap = PathOpsAngleTester::ConvexHullOverlaps(*seg[0].debugLastAn
gle(), |
424 makeSegment(&contour, quad1, shortQuads[0], allocator); | 430 *seg[1].debugLastAngle()); |
425 makeSegment(&contour, quad1, shortQuads[1], allocator); | |
426 SkOpSegment* seg1 = contour.first(); | |
427 seg1->debugAddAngle(0, 1, allocator); | |
428 SkOpSegment* seg2 = seg1->next(); | |
429 seg2->debugAddAngle(0, 1, allocator); | |
430 int realOverlap = PathOpsAngleTester::ConvexHullOverlaps(*seg1->debugLastAng
le(), | |
431 *seg2->debugLastAngle()); | |
432 const SkDPoint& origin = quad1[0]; | 431 const SkDPoint& origin = quad1[0]; |
433 REPORTER_ASSERT(reporter, origin == quad2[0]); | 432 REPORTER_ASSERT(reporter, origin == quad2[0]); |
434 double a1s = atan2(origin.fY - quad1[1].fY, quad1[1].fX - origin.fX); | 433 double a1s = atan2(origin.fY - quad1[1].fY, quad1[1].fX - origin.fX); |
435 double a1e = atan2(origin.fY - quad1[2].fY, quad1[2].fX - origin.fX); | 434 double a1e = atan2(origin.fY - quad1[2].fY, quad1[2].fX - origin.fX); |
436 double a2s = atan2(origin.fY - quad2[1].fY, quad2[1].fX - origin.fX); | 435 double a2s = atan2(origin.fY - quad2[1].fY, quad2[1].fX - origin.fX); |
437 double a2e = atan2(origin.fY - quad2[2].fY, quad2[2].fX - origin.fX); | 436 double a2e = atan2(origin.fY - quad2[2].fY, quad2[2].fX - origin.fX); |
438 bool oldSchoolOverlap = radianBetween(a1s, a2s, a1e) | 437 bool oldSchoolOverlap = radianBetween(a1s, a2s, a1e) |
439 || radianBetween(a1s, a2e, a1e) || radianBetween(a2s, a1s, a2e) | 438 || radianBetween(a1s, a2e, a1e) || radianBetween(a2s, a1s, a2e) |
440 || radianBetween(a2s, a1e, a2e); | 439 || radianBetween(a2s, a1e, a2e); |
441 int overlap = quadHullsOverlap(reporter, quad1, quad2); | 440 int overlap = quadHullsOverlap(reporter, quad1, quad2); |
(...skipping 97 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
539 SkASSERT(SkScalarSignAsInt(SkDoubleToScalar(midXray)) | 538 SkASSERT(SkScalarSignAsInt(SkDoubleToScalar(midXray)) |
540 == SkScalarSignAsInt(SkDoubleToScalar(vDir[sIndex]))); | 539 == SkScalarSignAsInt(SkDoubleToScalar(vDir[sIndex]))); |
541 firstInside = (rayDist > endDist) ^ (sIndex == 0) ^ (vDir[sIndex] < 0); | 540 firstInside = (rayDist > endDist) ^ (sIndex == 0) ^ (vDir[sIndex] < 0); |
542 } else if (overlap >= 0) { | 541 } else if (overlap >= 0) { |
543 return; // answer has already been determined | 542 return; // answer has already been determined |
544 } else { | 543 } else { |
545 firstInside = checkParallel(reporter, quad1, quad2); | 544 firstInside = checkParallel(reporter, quad1, quad2); |
546 } | 545 } |
547 if (overlap < 0) { | 546 if (overlap < 0) { |
548 SkDEBUGCODE(int realEnds =) | 547 SkDEBUGCODE(int realEnds =) |
549 PathOpsAngleTester::EndsIntersect(*seg1->debugLastAngle(), | 548 PathOpsAngleTester::EndsIntersect(*seg[0].debugLastAngle(), |
550 *seg2->debugLastAngle()); | 549 *seg[1].debugLastAngle()); |
551 SkASSERT(realEnds == (firstInside ? 1 : 0)); | 550 SkASSERT(realEnds == (firstInside ? 1 : 0)); |
552 } | 551 } |
553 bruteForce(reporter, quad1, quad2, firstInside); | 552 bruteForce(reporter, quad1, quad2, firstInside); |
554 } | 553 } |
555 | 554 |
556 DEF_TEST(PathOpsAngleOverlapHullsOne, reporter) { | 555 DEF_TEST(PathOpsAngleOverlapHullsOne, reporter) { |
557 SkChunkAlloc allocator(4096); | |
558 // gPathOpsAngleIdeasVerbose = true; | 556 // gPathOpsAngleIdeasVerbose = true; |
559 const SkDQuad quads[] = { | 557 const SkDQuad quads[] = { |
560 {{{939.4808349609375, 914.355224609375}, {-357.7921142578125, 590.842529296875},
{736.8936767578125, -350.717529296875}}}, | 558 {{{939.4808349609375, 914.355224609375}, {-357.7921142578125, 590.842529296875},
{736.8936767578125, -350.717529296875}}}, |
561 {{{939.4808349609375, 914.355224609375}, {-182.85418701171875, 634.4552001953125
}, {-509.62615966796875, 576.1182861328125}}} | 559 {{{939.4808349609375, 914.355224609375}, {-182.85418701171875, 634.4552001953125
}, {-509.62615966796875, 576.1182861328125}}} |
562 }; | 560 }; |
563 for (int index = 0; index < (int) SK_ARRAY_COUNT(quads); index += 2) { | 561 for (int index = 0; index < (int) SK_ARRAY_COUNT(quads); index += 2) { |
564 testQuadAngles(reporter, quads[index], quads[index + 1], 0, &allocator); | 562 testQuadAngles(reporter, quads[index], quads[index + 1], 0); |
565 } | 563 } |
566 } | 564 } |
567 | 565 |
568 DEF_TEST(PathOpsAngleOverlapHulls, reporter) { | 566 DEF_TEST(PathOpsAngleOverlapHulls, reporter) { |
569 SkChunkAlloc allocator(4096); | |
570 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it
by default | 567 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it
by default |
571 return; | 568 return; |
572 } | 569 } |
573 SkRandom ran; | 570 SkRandom ran; |
574 for (int index = 0; index < 100000; ++index) { | 571 for (int index = 0; index < 100000; ++index) { |
575 if (index % 1000 == 999) SkDebugf("."); | 572 if (index % 1000 == 999) SkDebugf("."); |
576 SkDPoint origin = {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 10
00)}; | 573 SkDPoint origin = {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 10
00)}; |
577 SkDQuad quad1 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-
1000, 1000)}, | 574 SkDQuad quad1 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-
1000, 1000)}, |
578 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}}; | 575 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}}; |
579 if (quad1[0] == quad1[2]) { | 576 if (quad1[0] == quad1[2]) { |
580 continue; | 577 continue; |
581 } | 578 } |
582 SkDQuad quad2 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-
1000, 1000)}, | 579 SkDQuad quad2 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-
1000, 1000)}, |
583 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}}; | 580 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}}; |
584 if (quad2[0] == quad2[2]) { | 581 if (quad2[0] == quad2[2]) { |
585 continue; | 582 continue; |
586 } | 583 } |
587 SkIntersections i; | 584 SkIntersections i; |
588 i.intersect(quad1, quad2); | 585 i.intersect(quad1, quad2); |
589 REPORTER_ASSERT(reporter, i.used() >= 1); | 586 REPORTER_ASSERT(reporter, i.used() >= 1); |
590 if (i.used() > 1) { | 587 if (i.used() > 1) { |
591 continue; | 588 continue; |
592 } | 589 } |
593 testQuadAngles(reporter, quad1, quad2, index, &allocator); | 590 testQuadAngles(reporter, quad1, quad2, index); |
594 } | 591 } |
595 } | 592 } |
596 | 593 |
597 DEF_TEST(PathOpsAngleBruteT, reporter) { | 594 DEF_TEST(PathOpsAngleBruteT, reporter) { |
598 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it
by default | 595 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it
by default |
599 return; | 596 return; |
600 } | 597 } |
601 SkRandom ran; | 598 SkRandom ran; |
602 double smaller = SK_Scalar1; | 599 double smaller = SK_Scalar1; |
603 SkDQuad small[2]; | 600 SkDQuad small[2]; |
(...skipping 250 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
854 step /= 2; | 851 step /= 2; |
855 } | 852 } |
856 #ifdef SK_DEBUG | 853 #ifdef SK_DEBUG |
857 // DumpQ(q1, q2, 999); | 854 // DumpQ(q1, q2, 999); |
858 #endif | 855 #endif |
859 } | 856 } |
860 if (gPathOpsAngleIdeasVerbose) { | 857 if (gPathOpsAngleIdeasVerbose) { |
861 SkDebugf("maxR=%1.9g\n", maxR); | 858 SkDebugf("maxR=%1.9g\n", maxR); |
862 } | 859 } |
863 } | 860 } |
OLD | NEW |