19166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com/* 29166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com * Copyright 2012 Google Inc. 39166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com * 49166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com * Use of this source code is governed by a BSD-style license that can be 59166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com * found in the LICENSE file. 69166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com */ 79166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com#include "PathOpsExtendedTest.h" 88d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com#include "PathOpsTestCommon.h" 99166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com#include "SkIntersections.h" 109166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com#include "SkPathOpsLine.h" 119166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com#include "SkPathOpsQuad.h" 129166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com#include "SkReduceOrder.h" 139166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com#include "Test.h" 149166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com 159166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.comstatic struct lineQuad { 169166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com SkDQuad quad; 179166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com SkDLine line; 189166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com int result; 199166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com SkDPoint expected[2]; 209166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com} lineQuadTests[] = { 219166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com // quad line results 229166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com {{{{1, 1}, {2, 1}, {0, 2}}}, {{{0, 0}, {1, 1}}}, 1, {{1, 1}, {0, 0}} }, 239166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com {{{{0, 0}, {1, 1}, {3, 1}}}, {{{0, 0}, {3, 1}}}, 2, {{0, 0}, {3, 1}} }, 249166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com {{{{2, 0}, {1, 1}, {2, 2}}}, {{{0, 0}, {0, 2}}}, 0, {{0, 0}, {0, 0}} }, 259166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com {{{{4, 0}, {0, 1}, {4, 2}}}, {{{3, 1}, {4, 1}}}, 0, {{0, 0}, {0, 0}} }, 269166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com {{{{0, 0}, {0, 1}, {1, 1}}}, {{{0, 1}, {1, 0}}}, 1, {{.25, .75}, {0, 0}} }, 279166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com}; 289166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com 29ad65a3e5fb1f94699f183551b828efbcc6a133cecaryclark@google.comstatic size_t lineQuadTests_count = SK_ARRAY_COUNT(lineQuadTests); 309166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com 319166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.comstatic int doIntersect(SkIntersections& intersections, const SkDQuad& quad, const SkDLine& line, 329166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com bool& flipped) { 339166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com int result; 349166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com flipped = false; 359166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com if (line[0].fX == line[1].fX) { 369166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com double top = line[0].fY; 379166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com double bottom = line[1].fY; 389166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com flipped = top > bottom; 399166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com if (flipped) { 409166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com SkTSwap<double>(top, bottom); 419166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com } 429166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com result = intersections.vertical(quad, top, bottom, line[0].fX, flipped); 439166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com } else if (line[0].fY == line[1].fY) { 449166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com double left = line[0].fX; 459166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com double right = line[1].fX; 469166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com flipped = left > right; 479166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com if (flipped) { 489166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com SkTSwap<double>(left, right); 499166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com } 509166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com result = intersections.horizontal(quad, left, right, line[0].fY, flipped); 519166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com } else { 529166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com intersections.intersect(quad, line); 539166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com result = intersections.used(); 549166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com } 559166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com return result; 569166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com} 579166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com 589166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.comstatic struct oneLineQuad { 599166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com SkDQuad quad; 609166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com SkDLine line; 619166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com} oneOffs[] = { 624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{{97.9337616,100}, {88,112.94265}, {88,130}}}, 634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{88.919838,120}, {107.058823,120}}}}, 64f54ad6f488845d0fc27734984e39185e15370fbcskia.committer@gmail.com {{{{447.96701049804687, 894.4381103515625}, {448.007080078125, 894.4239501953125}, 65f54ad6f488845d0fc27734984e39185e15370fbcskia.committer@gmail.com {448.0140380859375, 894.4215087890625}}}, 66a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com {{{490.43548583984375, 879.40740966796875}, {405.59262084960937, 909.435546875}}}}, 67570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com {{{{142.589081, 102.283646}, {149.821579, 100}, {158, 100}}}, 68570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com {{{90, 230}, {160, 60}}}}, 69fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com {{{{1101, 10}, {1101, 8.3431453704833984}, {1099.828857421875, 7.1711997985839844}}}, 70fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com {{{1099.828857421875,7.1711711883544922}, {1099.121337890625,7.8786783218383789}}}}, 71a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com {{{{973, 507}, {973, 508.24264526367187}, {972.12158203125, 509.12161254882812}}}, 72a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com {{{930, 467}, {973, 510}}}}, 739166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com {{{{369.848602, 145.680267}, {382.360413, 121.298294}, {406.207703, 121.298294}}}, 74fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com {{{406.207703, 121.298294}, {348.781738, 123.864815}}}}, 75fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com}; 769166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com 77ad65a3e5fb1f94699f183551b828efbcc6a133cecaryclark@google.comstatic size_t oneOffs_count = SK_ARRAY_COUNT(oneOffs); 789166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com 799166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.comstatic void testOneOffs(skiatest::Reporter* reporter) { 809166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com bool flipped = false; 819166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com for (size_t index = 0; index < oneOffs_count; ++index) { 829166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com const SkDQuad& quad = oneOffs[index].quad; 838d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com SkASSERT(ValidQuad(quad)); 849166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com const SkDLine& line = oneOffs[index].line; 858d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com SkASSERT(ValidLine(line)); 86a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com SkIntersections intersections; 879166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com int result = doIntersect(intersections, quad, line, flipped); 889166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com for (int inner = 0; inner < result; ++inner) { 899166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com double quadT = intersections[0][inner]; 904fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint quadXY = quad.ptAtT(quadT); 919166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com double lineT = intersections[1][inner]; 924fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint lineXY = line.ptAtT(lineT); 937eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (!quadXY.approximatelyEqual(lineXY)) { 947eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com quadXY.approximatelyEqual(lineXY); 957eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com SkDebugf(""); 967eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 979166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com REPORTER_ASSERT(reporter, quadXY.approximatelyEqual(lineXY)); 989166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com } 999166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com } 1009166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com} 1019166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com 10278e7b4e1b928fa69f672be3c743df6d6c3ecbcedtfarina@chromium.orgDEF_TEST(PathOpsQuadLineIntersectionOneOff, reporter) { 1039166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com testOneOffs(reporter); 104fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 105fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 10678e7b4e1b928fa69f672be3c743df6d6c3ecbcedtfarina@chromium.orgDEF_TEST(PathOpsQuadLineIntersection, reporter) { 1079166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com for (size_t index = 0; index < lineQuadTests_count; ++index) { 1089166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com int iIndex = static_cast<int>(index); 1099166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com const SkDQuad& quad = lineQuadTests[index].quad; 1108d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com SkASSERT(ValidQuad(quad)); 1119166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com const SkDLine& line = lineQuadTests[index].line; 1128d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com SkASSERT(ValidLine(line)); 1139166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com SkReduceOrder reducer1, reducer2; 114927b7028d44c46e9cbc18368f16ec2262d59d94dcaryclark@google.com int order1 = reducer1.reduce(quad); 1159166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com int order2 = reducer2.reduce(line); 1169166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com if (order1 < 3) { 1179166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com SkDebugf("%s [%d] quad order=%d\n", __FUNCTION__, iIndex, order1); 1189166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com REPORTER_ASSERT(reporter, 0); 1199166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com } 1209166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com if (order2 < 2) { 1219166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com SkDebugf("%s [%d] line order=%d\n", __FUNCTION__, iIndex, order2); 1229166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com REPORTER_ASSERT(reporter, 0); 1239166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com } 1249166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com SkIntersections intersections; 1259166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com bool flipped = false; 1269166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com int result = doIntersect(intersections, quad, line, flipped); 1279166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com REPORTER_ASSERT(reporter, result == lineQuadTests[index].result); 1289166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com if (intersections.used() <= 0) { 1299166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com continue; 1309166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com } 1319166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com for (int pt = 0; pt < result; ++pt) { 1329166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com double tt1 = intersections[0][pt]; 1339166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com REPORTER_ASSERT(reporter, tt1 >= 0 && tt1 <= 1); 1344fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint t1 = quad.ptAtT(tt1); 1359166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com double tt2 = intersections[1][pt]; 1369166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com REPORTER_ASSERT(reporter, tt2 >= 0 && tt2 <= 1); 1374fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint t2 = line.ptAtT(tt2); 1389166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com if (!t1.approximatelyEqual(t2)) { 1399166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com SkDebugf("%s [%d,%d] x!= t1=%1.9g (%1.9g,%1.9g) t2=%1.9g (%1.9g,%1.9g)\n", 1409166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com __FUNCTION__, iIndex, pt, tt1, t1.fX, t1.fY, tt2, t2.fX, t2.fY); 1419166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com REPORTER_ASSERT(reporter, 0); 1429166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com } 1439166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com if (!t1.approximatelyEqual(lineQuadTests[index].expected[0]) 1449166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com && (lineQuadTests[index].result == 1 1459166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com || !t1.approximatelyEqual(lineQuadTests[index].expected[1]))) { 1469166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com SkDebugf("%s t1=(%1.9g,%1.9g)\n", __FUNCTION__, t1.fX, t1.fY); 1479166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com REPORTER_ASSERT(reporter, 0); 1489166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com } 1499166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com } 1509166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com } 1519166dcb3a0e8784bea83d76ae01aa338c049ae05caryclark@google.com} 152