1a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com/* 2a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com * Copyright 2013 Google Inc. 3a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com * 4a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com * Use of this source code is governed by a BSD-style license that can be 5a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com * found in the LICENSE file. 6a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com */ 78d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com#include "PathOpsTestCommon.h" 8a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com#include "SkIntersections.h" 9a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com#include "SkPathOpsCubic.h" 10a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com#include "SkPathOpsQuad.h" 114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#include "SkRandom.h" 12a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com#include "SkReduceOrder.h" 13a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com#include "Test.h" 14a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com 15e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclarkstatic struct quadCubic { 16a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com SkDCubic cubic; 17a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com SkDQuad quad; 18a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com int answerCount; 19a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com SkDPoint answers[2]; 20a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com} quadCubicTests[] = { 214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if 0 // FIXME : this should not fail (root problem behind skpcarrot_is24 ) 224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{{1020.08099,672.161987}, {1020.08002,630.73999}, {986.502014,597.161987}, {945.080994,597.161987}}}, 234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{1020,672}, {1020,640.93396}, {998.03302,618.96698}}}, 1, 244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{1019.421, 662.449}}}, 254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 27f54ad6f488845d0fc27734984e39185e15370fbcskia.committer@gmail.com {{{{778, 14089}, {778, 14091.208984375}, {776.20916748046875, 14093}, {774, 14093}}}, 28f54ad6f488845d0fc27734984e39185e15370fbcskia.committer@gmail.com {{{778, 14089}, {777.99957275390625, 14090.65625}, {776.82843017578125, 14091.828125}}}, 2, 29f54ad6f488845d0fc27734984e39185e15370fbcskia.committer@gmail.com {{778, 14089}, {776.82855609581270,14091.828250841330}}}, 30a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com 31a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com {{{{1110, 817}, {1110.55225f, 817}, {1111, 817.447693f}, {1111, 818}}}, 32a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com {{{1110.70715f, 817.292908f}, {1110.41406f, 817.000122f}, {1110, 817}}}, 2, 33a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com {{1110, 817}, {1110.70715f, 817.292908f}}}, 34a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com 35a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com {{{{1110, 817}, {1110.55225f, 817}, {1111, 817.447693f}, {1111, 818}}}, 36a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com {{{1111, 818}, {1110.99988f, 817.585876f}, {1110.70715f, 817.292908f}}}, 2, 37a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com {{1110.70715f, 817.292908f}, {1111, 818}}}, 38a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com 39a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com {{{{55, 207}, {52.238574981689453, 207}, {50, 204.76142883300781}, {50, 202}}}, 40a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com {{{55, 207}, {52.929431915283203, 206.99949645996094}, 41a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com {51.464466094970703, 205.53553771972656}}}, 2, 42a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com {{55, 207}, {51.464466094970703, 205.53553771972656}}}, 43a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com 44b0a0589f8ac0254ec1beba9db2fc32a2bedb31e5skia.committer@gmail.com {{{{49, 47}, {49, 74.614250183105469}, {26.614250183105469, 97}, {-1, 97}}}, 457eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com {{{-8.659739592076221e-015, 96.991401672363281}, {20.065492630004883, 96.645187377929688}, 467eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com {34.355339050292969, 82.355339050292969}}}, 2, 47a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com {{34.355339050292969,82.355339050292969}, {34.28654835573549, 82.424006509351585}}}, 487eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com 492b34fe01d7b5736b212eb4886afc723a7b9241aeskia.committer@gmail.com {{{{10,234}, {10,229.58172607421875}, {13.581720352172852,226}, {18,226}}}, 507eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com {{{18,226}, {14.686291694641113,226}, {12.342399597167969,228.3424072265625}}}, 1, 517eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com {{18,226}, {0,0}}}, 52a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com 532b34fe01d7b5736b212eb4886afc723a7b9241aeskia.committer@gmail.com {{{{10,234}, {10,229.58172607421875}, {13.581720352172852,226}, {18,226}}}, 547eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com {{{12.342399597167969,228.3424072265625}, {10,230.68629455566406}, {10,234}}}, 1, 557eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com {{10,234}, {0,0}}}, 56a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com}; 57a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com 584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic const int quadCubicTests_count = (int) SK_ARRAY_COUNT(quadCubicTests); 59a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com 604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic void cubicQuadIntersection(skiatest::Reporter* reporter, int index) { 614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int iIndex = static_cast<int>(index); 624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDCubic& cubic = quadCubicTests[index].cubic; 634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(ValidCubic(cubic)); 644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDQuad& quad = quadCubicTests[index].quad; 654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(ValidQuad(quad)); 664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkReduceOrder reduce1; 674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkReduceOrder reduce2; 684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int order1 = reduce1.reduce(cubic, SkReduceOrder::kNo_Quadratics); 694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int order2 = reduce2.reduce(quad); 704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (order1 != 4) { 714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("[%d] cubic order=%d\n", iIndex, order1); 724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, 0); 734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (order2 != 3) { 754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("[%d] quad order=%d\n", iIndex, order2); 764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, 0); 774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkIntersections i; 794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int roots = i.intersect(cubic, quad); 804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(roots == quadCubicTests[index].answerCount); 814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int pt = 0; pt < roots; ++pt) { 824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double tt1 = i[0][pt]; 834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDPoint xy1 = cubic.ptAtT(tt1); 844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double tt2 = i[1][pt]; 854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDPoint xy2 = quad.ptAtT(tt2); 864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!xy1.approximatelyEqual(xy2)) { 874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", 884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org __FUNCTION__, iIndex, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.fX, xy2.fY); 89a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com } 904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); 914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool found = false; 924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int idx2 = 0; idx2 < quadCubicTests[index].answerCount; ++idx2) { 934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org found |= quadCubicTests[index].answers[idx2].approximatelyEqual(xy1); 94a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com } 954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!found) { 964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%s [%d,%d] xy1=(%g,%g) != \n", 974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org __FUNCTION__, iIndex, pt, xy1.fX, xy1.fY); 984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, found); 1004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org reporter->bumpTestCount(); 1024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 1034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 1044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgDEF_TEST(PathOpsCubicQuadIntersection, reporter) { 1054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int index = 0; index < quadCubicTests_count; ++index) { 1064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org cubicQuadIntersection(reporter, index); 1074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org reporter->bumpTestCount(); 1084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 1104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 1114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgDEF_TEST(PathOpsCubicQuadIntersectionOneOff, reporter) { 1124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org cubicQuadIntersection(reporter, 0); 1134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 1144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 1154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic bool gPathOpCubicQuadSlopVerbose = false; 1164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic const int kCubicToQuadSubdivisionDepth = 8; // slots reserved for cubic to quads subdivision 1174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 1184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// determine that slop required after quad/quad finds a candidate intersection 1194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// use the cross of the tangents plus the distance from 1 or 0 as knobs 1204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgDEF_TEST(PathOpsCubicQuadSlop, reporter) { 1214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // create a random non-selfintersecting cubic 1224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // break it into quadratics 1234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // offset the quadratic, measuring the slop required to find the intersection 1244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!gPathOpCubicQuadSlopVerbose) { // takes a while to run -- so exclude it by default 1254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 1264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int results[101]; 1284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sk_bzero(results, sizeof(results)); 1294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double minCross[101]; 1304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sk_bzero(minCross, sizeof(minCross)); 1314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double maxCross[101]; 1324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sk_bzero(maxCross, sizeof(maxCross)); 1334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double sumCross[101]; 1344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sk_bzero(sumCross, sizeof(sumCross)); 1354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int foundOne = 0; 1364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int slopCount = 1; 1374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkRandom ran; 1384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int index = 0; index < 10000000; ++index) { 1394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (index % 1000 == 999) SkDebugf("."); 1404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDCubic cubic = {{ 1414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}, 1424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}, 1434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}, 1444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)} 1454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org }}; 146a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com SkIntersections i; 1474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (i.intersect(cubic)) { 1484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 1494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkSTArray<kCubicToQuadSubdivisionDepth, double, true> ts; 1514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org cubic.toQuadraticTs(cubic.calcPrecision(), &ts); 1524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double tStart = 0; 1534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int tsCount = ts.count(); 1544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int i1 = 0; i1 <= tsCount; ++i1) { 1554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const double tEnd = i1 < tsCount ? ts[i1] : 1; 1564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDCubic part = cubic.subDivide(tStart, tEnd); 1574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDQuad quad = part.toQuad(); 1584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkReduceOrder reducer; 1594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int order = reducer.reduce(quad); 1604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (order != 3) { 1614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 162a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com } 1634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int i2 = 0; i2 < 100; ++i2) { 1644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDPoint endDisplacement = {ran.nextRangeF(-100, 100), ran.nextRangeF(-100, 100)}; 1654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDQuad nearby = {{ 1664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {quad[0].fX + endDisplacement.fX, quad[0].fY + endDisplacement.fY}, 1674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {quad[1].fX + ran.nextRangeF(-100, 100), quad[1].fY + ran.nextRangeF(-100, 100)}, 1684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {quad[2].fX - endDisplacement.fX, quad[2].fY - endDisplacement.fY} 1694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org }}; 1704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org order = reducer.reduce(nearby); 1714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (order != 3) { 1724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 1734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkIntersections locals; 1754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org locals.allowNear(false); 1764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org locals.intersect(quad, nearby); 1774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (locals.used() != 1) { 1784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 1794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // brute force find actual intersection 1814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDLine cubicLine = {{ {0, 0}, {cubic[0].fX, cubic[0].fY } }}; 1824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkIntersections liner; 1834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int i3; 1844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int found = -1; 1854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int foundErr = true; 1864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (i3 = 1; i3 <= 1000; ++i3) { 1874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org cubicLine[0] = cubicLine[1]; 1884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org cubicLine[1] = cubic.ptAtT(i3 / 1000.); 1894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org liner.reset(); 1904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org liner.allowNear(false); 1914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org liner.intersect(nearby, cubicLine); 1924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (liner.used() == 0) { 1934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 1944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (liner.used() > 1) { 1964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org foundErr = true; 1974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org break; 1984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (found > 0) { 2004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org foundErr = true; 2014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org break; 2024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org foundErr = false; 2044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org found = i3; 2054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (foundErr) { 2074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 2084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector dist = liner.pt(0) - locals.pt(0); 2104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector qV = nearby.dxdyAtT(locals[0][0]); 2114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double cubicT = (found - 1 + liner[1][0]) / 1000.; 2124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector cV = cubic.dxdyAtT(cubicT); 2134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double qxc = qV.crossCheck(cV); 2144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double qvLen = qV.length(); 2154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double cvLen = cV.length(); 2164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double maxLen = SkTMax(qvLen, cvLen); 2174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org qxc /= maxLen; 2184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double quadT = tStart + (tEnd - tStart) * locals[0][0]; 2194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double diffT = fabs(cubicT - quadT); 2204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int diffIdx = (int) (diffT * 100); 2214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org results[diffIdx]++; 2224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double absQxc = fabs(qxc); 2234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (sumCross[diffIdx] == 0) { 2244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org minCross[diffIdx] = maxCross[diffIdx] = sumCross[diffIdx] = absQxc; 2254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 2264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org minCross[diffIdx] = SkTMin(minCross[diffIdx], absQxc); 2274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org maxCross[diffIdx] = SkTMax(maxCross[diffIdx], absQxc); 2284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sumCross[diffIdx] += absQxc; 2294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (diffIdx >= 20) { 2314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if 01 2324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("cubic={{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}" 2334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org " quad={{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}" 2344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org " {{{%1.9g,%1.9g}, {%1.9g,%1.9g}}}" 235a1ed7aec95eb8c77d1a39834fea476780007cadeskia.committer@gmail.com " qT=%1.9g cT=%1.9g dist=%1.9g cross=%1.9g\n", 2364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org cubic[0].fX, cubic[0].fY, cubic[1].fX, cubic[1].fY, 2374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org cubic[2].fX, cubic[2].fY, cubic[3].fX, cubic[3].fY, 2384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org nearby[0].fX, nearby[0].fY, nearby[1].fX, nearby[1].fY, 239a1ed7aec95eb8c77d1a39834fea476780007cadeskia.committer@gmail.com nearby[2].fX, nearby[2].fY, 2404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org liner.pt(0).fX, liner.pt(0).fY, 2414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org locals.pt(0).fX, locals.pt(0).fY, quadT, cubicT, dist.length(), qxc); 2424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#else 2434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("qT=%1.9g cT=%1.9g dist=%1.9g cross=%1.9g\n", 2444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org quadT, cubicT, dist.length(), qxc); 2454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("<div id=\"slop%d\">\n", ++slopCount); 2464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("{{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}\n" 2474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org "{{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}\n" 2484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org "{{{%1.9g,%1.9g}, {%1.9g,%1.9g}}}\n", 2494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org cubic[0].fX, cubic[0].fY, cubic[1].fX, cubic[1].fY, 2504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org cubic[2].fX, cubic[2].fY, cubic[3].fX, cubic[3].fY, 2514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org nearby[0].fX, nearby[0].fY, nearby[1].fX, nearby[1].fY, 252a1ed7aec95eb8c77d1a39834fea476780007cadeskia.committer@gmail.com nearby[2].fX, nearby[2].fY, 2534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org liner.pt(0).fX, liner.pt(0).fY, 2544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org locals.pt(0).fX, locals.pt(0).fY); 2554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("</div>\n\n"); 2564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 2574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org ++foundOne; 259a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com } 2604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org tStart = tEnd; 261a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com } 2624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (++foundOne >= 100000) { 2634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org break; 2644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if 01 2674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("slopCount=%d\n", slopCount); 2684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int max = 100; 2694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org while (results[max] == 0) { 2704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org --max; 2714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int i = 0; i <= max; ++i) { 2734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (i > 0 && i % 10 == 0) { 2744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("\n"); 2754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%d ", results[i]); 2774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("min\n"); 2794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int i = 0; i <= max; ++i) { 2804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (i > 0 && i % 10 == 0) { 2814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("\n"); 2824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%1.9g ", minCross[i]); 2844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("max\n"); 2864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int i = 0; i <= max; ++i) { 2874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (i > 0 && i % 10 == 0) { 2884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("\n"); 2894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%1.9g ", maxCross[i]); 2914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("avg\n"); 2934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int i = 0; i <= max; ++i) { 2944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (i > 0 && i % 10 == 0) { 2954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("\n"); 2964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%1.9g ", sumCross[i] / results[i]); 2984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#else 3004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int i = 1; i < slopCount; ++i) { 3014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf(" slop%d,\n", i); 302a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com } 3034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 3044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("\n"); 305a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com} 306