14431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org/* 24431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org * Copyright 2013 Google Inc. 34431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org * 44431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org * Use of this source code is governed by a BSD-style license that can be 54431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org * found in the LICENSE file. 64431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org */ 74431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#include "PathOpsTestCommon.h" 84431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#include "SkIntersections.h" 94431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#include "SkOpSegment.h" 104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#include "SkPathOpsTriangle.h" 114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#include "SkRandom.h" 124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#include "SkTArray.h" 134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#include "SkTSort.h" 144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#include "Test.h" 154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic bool gPathOpsAngleIdeasVerbose = false; 174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic bool gPathOpsAngleIdeasEnableBruteCheck = false; 184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgclass PathOpsAngleTester { 204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgpublic: 214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org static int ConvexHullOverlaps(const SkOpAngle& lh, const SkOpAngle& rh) { 224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return lh.convexHullOverlaps(rh); 234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org static int EndsIntersect(const SkOpAngle& lh, const SkOpAngle& rh) { 264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return lh.endsIntersect(rh); 274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org}; 294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstruct TRange { 314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double tMin1; 324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double tMin2; 334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double t1; 344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double t2; 354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double tMin; 364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double a1; 374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double a2; 384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool ccw; 394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org}; 404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic double testArc(skiatest::Reporter* reporter, const SkDQuad& quad, const SkDQuad& arcRef, 424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int octant) { 434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDQuad arc = arcRef; 444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector offset = {quad[0].fX, quad[0].fY}; 454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org arc[0] += offset; 464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org arc[1] += offset; 474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org arc[2] += offset; 484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkIntersections i; 494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org i.intersect(arc, quad); 504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (i.used() == 0) { 514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return -1; 524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int smallest = -1; 544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double t = 2; 554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int idx = 0; idx < i.used(); ++idx) { 564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (i[0][idx] > 1 || i[0][idx] < 0) { 574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org i.reset(); 584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org i.intersect(arc, quad); 594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (i[1][idx] > 1 || i[1][idx] < 0) { 614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org i.reset(); 624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org i.intersect(arc, quad); 634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (t > i[1][idx]) { 654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org smallest = idx; 664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org t = i[1][idx]; 674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, smallest >= 0); 704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, t >= 0 && t <= 1); 714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return i[1][smallest]; 724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic void orderQuads(skiatest::Reporter* reporter, const SkDQuad& quad, double radius, 754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkTArray<double, false>* tArray) { 764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double r = radius; 774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s = r * SK_ScalarTanPIOver8; 784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double m = r * SK_ScalarRoot2Over2; 794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // construct circle from quads 804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDQuad circle[8] = {{{{ r, 0}, { r, -s}, { m, -m}}}, 814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{ m, -m}, { s, -r}, { 0, -r}}}, 824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{ 0, -r}, {-s, -r}, {-m, -m}}}, 834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{-m, -m}, {-r, -s}, {-r, 0}}}, 844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{-r, 0}, {-r, s}, {-m, m}}}, 854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{-m, m}, {-s, r}, { 0, r}}}, 864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{ 0, r}, { s, r}, { m, m}}}, 874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{ m, m}, { r, s}, { r, 0}}}}; 884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int octant = 0; octant < 8; ++octant) { 894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double t = testArc(reporter, quad, circle[octant], octant); 904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (t < 0) { 914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int index = 0; index < tArray->count(); ++index) { 944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double matchT = (*tArray)[index]; 954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (approximately_equal(t, matchT)) { 964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org goto next; 974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org tArray->push_back(t); 1004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgnext: ; 1014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 1034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 1044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic double quadAngle(skiatest::Reporter* reporter, const SkDQuad& quad, double t) { 1054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDVector& pt = quad.ptAtT(t) - quad[0]; 1064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double angle = (atan2(pt.fY, pt.fX) + SK_ScalarPI) * 8 / (SK_ScalarPI * 2); 1074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, angle >= 0 && angle <= 8); 1084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return angle; 1094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 1104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 1114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic bool angleDirection(double a1, double a2) { 1124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double delta = a1 - a2; 1134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return (delta < 4 && delta > 0) || delta < -4; 1144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 1154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 1164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic void setQuadHullSweep(const SkDQuad& quad, SkDVector sweep[2]) { 1174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sweep[0] = quad[1] - quad[0]; 1184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sweep[1] = quad[2] - quad[0]; 1194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 1204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 1214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic double distEndRatio(double dist, const SkDQuad& quad) { 1224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector v[] = {quad[2] - quad[0], quad[1] - quad[0], quad[2] - quad[1]}; 1234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double longest = SkTMax(v[0].length(), SkTMax(v[1].length(), v[2].length())); 1244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return longest / dist; 1254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 1264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 1274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic bool checkParallel(skiatest::Reporter* reporter, const SkDQuad& quad1, const SkDQuad& quad2) { 1284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector sweep[2], tweep[2]; 1294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org setQuadHullSweep(quad1, sweep); 1304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org setQuadHullSweep(quad2, tweep); 1314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // if the ctrl tangents are not nearly parallel, use them 1324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // solve for opposite direction displacement scale factor == m 1334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x 1344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1] 1354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x) 1364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.x) 1374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x 1384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y) 1394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // m = v1.cross(v2) / v1.dot(v2) 1404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s0dt0 = sweep[0].dot(tweep[0]); 1414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, s0dt0 != 0); 1424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s0xt0 = sweep[0].crossCheck(tweep[0]); 1434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double m = s0xt0 / s0dt0; 1444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double sDist = sweep[0].length() * m; 1454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double tDist = tweep[0].length() * m; 1464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool useS = fabs(sDist) < fabs(tDist); 1474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double mFactor = fabs(useS ? distEndRatio(sDist, quad1) : distEndRatio(tDist, quad2)); 1484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (mFactor < 5000) { // empirically found limit 1494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return s0xt0 < 0; 1504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector m0 = quad1.ptAtT(0.5) - quad1[0]; 1524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector m1 = quad2.ptAtT(0.5) - quad2[0]; 1534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return m0.crossCheck(m1) < 0; 1544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 1554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 1564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org/* returns 1574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org -1 if overlaps 1584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 0 if no overlap cw 1594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 1 if no overlap ccw 1604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org*/ 1614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic int quadHullsOverlap(skiatest::Reporter* reporter, const SkDQuad& quad1, 1624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDQuad& quad2) { 1634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector sweep[2], tweep[2]; 1644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org setQuadHullSweep(quad1, sweep); 1654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org setQuadHullSweep(quad2, tweep); 1664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s0xs1 = sweep[0].crossCheck(sweep[1]); 1674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s0xt0 = sweep[0].crossCheck(tweep[0]); 1684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s1xt0 = sweep[1].crossCheck(tweep[0]); 1694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool tBetweenS = s0xs1 > 0 ? s0xt0 > 0 && s1xt0 < 0 : s0xt0 < 0 && s1xt0 > 0; 1704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s0xt1 = sweep[0].crossCheck(tweep[1]); 1714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s1xt1 = sweep[1].crossCheck(tweep[1]); 1724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org tBetweenS |= s0xs1 > 0 ? s0xt1 > 0 && s1xt1 < 0 : s0xt1 < 0 && s1xt1 > 0; 1734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double t0xt1 = tweep[0].crossCheck(tweep[1]); 1744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (tBetweenS) { 1754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return -1; 1764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if ((s0xt0 == 0 && s1xt1 == 0) || (s1xt0 == 0 && s0xt1 == 0)) { // s0 to s1 equals t0 to t1 1784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return -1; 1794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool sBetweenT = t0xt1 > 0 ? s0xt0 < 0 && s0xt1 > 0 : s0xt0 > 0 && s0xt1 < 0; 1814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sBetweenT |= t0xt1 > 0 ? s1xt0 < 0 && s1xt1 > 0 : s1xt0 > 0 && s1xt1 < 0; 1824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (sBetweenT) { 1834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return -1; 1844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // if all of the sweeps are in the same half plane, then the order of any pair is enough 1864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (s0xt0 >= 0 && s0xt1 >= 0 && s1xt0 >= 0 && s1xt1 >= 0) { 1874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return 0; 1884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (s0xt0 <= 0 && s0xt1 <= 0 && s1xt0 <= 0 && s1xt1 <= 0) { 1904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return 1; 1914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // if the outside sweeps are greater than 180 degress: 1934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // first assume the inital tangents are the ordering 1944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // if the midpoint direction matches the inital order, that is enough 1954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector m0 = quad1.ptAtT(0.5) - quad1[0]; 1964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector m1 = quad2.ptAtT(0.5) - quad2[0]; 1974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double m0xm1 = m0.crossCheck(m1); 1984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (s0xt0 > 0 && m0xm1 > 0) { 1994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return 0; 2004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (s0xt0 < 0 && m0xm1 < 0) { 2024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return 1; 2034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, s0xt0 != 0); 2054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return checkParallel(reporter, quad1, quad2); 2064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 2074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 2084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic double radianSweep(double start, double end) { 2094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double sweep = end - start; 2104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (sweep > SK_ScalarPI) { 2114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sweep -= 2 * SK_ScalarPI; 2124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else if (sweep < -SK_ScalarPI) { 2134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sweep += 2 * SK_ScalarPI; 2144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return sweep; 2164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 2174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 2184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic bool radianBetween(double start, double test, double end) { 2194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double startToEnd = radianSweep(start, end); 2204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double startToTest = radianSweep(start, test); 2214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double testToEnd = radianSweep(test, end); 2224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return (startToTest <= 0 && testToEnd <= 0 && startToTest >= startToEnd) || 2234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org (startToTest >= 0 && testToEnd >= 0 && startToTest <= startToEnd); 2244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 2254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 2264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic bool orderTRange(skiatest::Reporter* reporter, const SkDQuad& quad1, const SkDQuad& quad2, 2274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double r, TRange* result) { 2284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkTArray<double, false> t1Array, t2Array; 2294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org orderQuads(reporter, quad1, r, &t1Array); 2304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org orderQuads(reporter,quad2, r, &t2Array); 2314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!t1Array.count() || !t2Array.count()) { 2324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return false; 2334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkTQSort<double>(t1Array.begin(), t1Array.end() - 1); 2354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkTQSort<double>(t2Array.begin(), t2Array.end() - 1); 2364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double t1 = result->tMin1 = t1Array[0]; 2374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double t2 = result->tMin2 = t2Array[0]; 2384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double a1 = quadAngle(reporter,quad1, t1); 2394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double a2 = quadAngle(reporter,quad2, t2); 2404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (approximately_equal(a1, a2)) { 2414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return false; 2424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool refCCW = angleDirection(a1, a2); 2444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org result->t1 = t1; 2454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org result->t2 = t2; 2464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org result->tMin = SkTMin(t1, t2); 2474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org result->a1 = a1; 2484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org result->a2 = a2; 2494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org result->ccw = refCCW; 2504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return true; 2514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 2524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 2534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic bool equalPoints(const SkDPoint& pt1, const SkDPoint& pt2, double max) { 2544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return approximately_zero_when_compared_to(pt1.fX - pt2.fX, max) 2554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org && approximately_zero_when_compared_to(pt1.fY - pt2.fY, max); 2564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 2574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 2584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic double maxDist(const SkDQuad& quad) { 2594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDRect bounds; 2604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bounds.setBounds(quad); 2614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector corner[4] = { 2624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org { bounds.fLeft - quad[0].fX, bounds.fTop - quad[0].fY }, 2634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org { bounds.fRight - quad[0].fX, bounds.fTop - quad[0].fY }, 2644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org { bounds.fLeft - quad[0].fX, bounds.fBottom - quad[0].fY }, 2654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org { bounds.fRight - quad[0].fX, bounds.fBottom - quad[0].fY } 2664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org }; 2674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double max = 0; 2684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (unsigned index = 0; index < SK_ARRAY_COUNT(corner); ++index) { 2694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org max = SkTMax(max, corner[index].length()); 2704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return max; 2724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 2734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 2744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic double maxQuad(const SkDQuad& quad) { 2754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double max = 0; 2764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int index = 0; index < 2; ++index) { 2774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org max = SkTMax(max, fabs(quad[index].fX)); 2784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org max = SkTMax(max, fabs(quad[index].fY)); 2794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return max; 2814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 2824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 2834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic bool bruteMinT(skiatest::Reporter* reporter, const SkDQuad& quad1, const SkDQuad& quad2, 2844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org TRange* lowerRange, TRange* upperRange) { 2854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double maxRadius = SkTMin(maxDist(quad1), maxDist(quad2)); 2864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double maxQuads = SkTMax(maxQuad(quad1), maxQuad(quad2)); 2874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double r = maxRadius / 2; 2884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double rStep = r / 2; 2894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDPoint best1 = {SK_ScalarInfinity, SK_ScalarInfinity}; 2904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDPoint best2 = {SK_ScalarInfinity, SK_ScalarInfinity}; 2914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int bestCCW = -1; 2924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double bestR = maxRadius; 2934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org upperRange->tMin = 0; 2944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org lowerRange->tMin = 1; 2954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 2964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { // find upper bounds of single result 2974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org TRange tRange; 2984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool stepUp = orderTRange(reporter, quad1, quad2, r, &tRange); 2994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (stepUp) { 3004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDPoint pt1 = quad1.ptAtT(tRange.t1); 3014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (equalPoints(pt1, best1, maxQuads)) { 3024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org break; 3034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org best1 = pt1; 3054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDPoint pt2 = quad2.ptAtT(tRange.t2); 3064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (equalPoints(pt2, best2, maxQuads)) { 3074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org break; 3084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org best2 = pt2; 3104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (gPathOpsAngleIdeasVerbose) { 3114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("u bestCCW=%d ccw=%d bestMin=%1.9g:%1.9g r=%1.9g tMin=%1.9g\n", 3124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bestCCW, tRange.ccw, lowerRange->tMin, upperRange->tMin, r, 3134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org tRange.tMin); 3144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (bestCCW >= 0 && bestCCW != (int) tRange.ccw) { 3164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (tRange.tMin < upperRange->tMin) { 3174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org upperRange->tMin = 0; 3184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 3194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org stepUp = false; 3204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (upperRange->tMin < tRange.tMin) { 3234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bestCCW = tRange.ccw; 3244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bestR = r; 3254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org *upperRange = tRange; 3264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (lowerRange->tMin > tRange.tMin) { 3284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org *lowerRange = tRange; 3294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org r += stepUp ? rStep : -rStep; 3324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org rStep /= 2; 3334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while (rStep > FLT_EPSILON); 3344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (bestCCW < 0) { 3354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, bestR < maxRadius); 3364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return false; 3374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double lastHighR = bestR; 3394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org r = bestR / 2; 3404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org rStep = r / 2; 3414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { // find lower bounds of single result 3424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org TRange tRange; 3434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool success = orderTRange(reporter, quad1, quad2, r, &tRange); 3444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (success) { 3454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (gPathOpsAngleIdeasVerbose) { 3464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("l bestCCW=%d ccw=%d bestMin=%1.9g:%1.9g r=%1.9g tMin=%1.9g\n", 3474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bestCCW, tRange.ccw, lowerRange->tMin, upperRange->tMin, r, 3484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org tRange.tMin); 3494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (bestCCW != (int) tRange.ccw || upperRange->tMin < tRange.tMin) { 3514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bestCCW = tRange.ccw; 3524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org *upperRange = tRange; 3534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bestR = lastHighR; 3544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org break; // need to establish a new upper bounds 3554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDPoint pt1 = quad1.ptAtT(tRange.t1); 3574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDPoint pt2 = quad2.ptAtT(tRange.t2); 3584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (equalPoints(pt1, best1, maxQuads)) { 3594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org goto breakOut; 3604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org best1 = pt1; 3624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (equalPoints(pt2, best2, maxQuads)) { 3634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org goto breakOut; 3644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org best2 = pt2; 3664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (equalPoints(pt1, pt2, maxQuads)) { 3674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org success = false; 3684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 3694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (upperRange->tMin < tRange.tMin) { 3704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org *upperRange = tRange; 3714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (lowerRange->tMin > tRange.tMin) { 3734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org *lowerRange = tRange; 3744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org lastHighR = SkTMin(r, lastHighR); 3774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org r += success ? -rStep : rStep; 3794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org rStep /= 2; 3804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while (rStep > FLT_EPSILON); 3814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while (rStep > FLT_EPSILON); 3824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgbreakOut: 3834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (gPathOpsAngleIdeasVerbose) { 3844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("l a2-a1==%1.9g\n", lowerRange->a2 - lowerRange->a1); 3854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return true; 3874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 3884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 3894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic void bruteForce(skiatest::Reporter* reporter, const SkDQuad& quad1, const SkDQuad& quad2, 3904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool ccw) { 3914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!gPathOpsAngleIdeasEnableBruteCheck) { 3924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 3934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org TRange lowerRange, upperRange; 3954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool result = bruteMinT(reporter, quad1, quad2, &lowerRange, &upperRange); 3964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, result); 3974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double angle = fabs(lowerRange.a2 - lowerRange.a1); 3984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, angle > 3.998 || ccw == upperRange.ccw); 3994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 4004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 4014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic bool bruteForceCheck(skiatest::Reporter* reporter, const SkDQuad& quad1, 4024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDQuad& quad2, bool ccw) { 4034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org TRange lowerRange, upperRange; 4044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool result = bruteMinT(reporter, quad1, quad2, &lowerRange, &upperRange); 4054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, result); 4064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return ccw == upperRange.ccw; 4074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 4084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 4094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgclass PathOpsSegmentTester { 4104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgpublic: 4114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org static void ConstructQuad(SkOpSegment* segment, SkPoint shortQuad[3]) { 4124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org segment->debugConstructQuad(shortQuad); 4134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org}; 4154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 4164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic void makeSegment(const SkDQuad& quad, SkPoint shortQuad[3], SkOpSegment* result) { 4174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org shortQuad[0] = quad[0].asSkPoint(); 4184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org shortQuad[1] = quad[1].asSkPoint(); 4194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org shortQuad[2] = quad[2].asSkPoint(); 4204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org PathOpsSegmentTester::ConstructQuad(result, shortQuad); 4214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 4224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 4234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic void testQuadAngles(skiatest::Reporter* reporter, const SkDQuad& quad1, const SkDQuad& quad2, 4244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int testNo) { 4254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkPoint shortQuads[2][3]; 4264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpSegment seg[2]; 4274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org makeSegment(quad1, shortQuads[0], &seg[0]); 4284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org makeSegment(quad2, shortQuads[1], &seg[1]); 429dac1d17027dcaa5596885a9f333979418b35001ccaryclark int realOverlap = PathOpsAngleTester::ConvexHullOverlaps(*seg[0].debugLastAngle(), 430dac1d17027dcaa5596885a9f333979418b35001ccaryclark *seg[1].debugLastAngle()); 4314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDPoint& origin = quad1[0]; 4324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, origin == quad2[0]); 4334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double a1s = atan2(origin.fY - quad1[1].fY, quad1[1].fX - origin.fX); 4344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double a1e = atan2(origin.fY - quad1[2].fY, quad1[2].fX - origin.fX); 4354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double a2s = atan2(origin.fY - quad2[1].fY, quad2[1].fX - origin.fX); 4364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double a2e = atan2(origin.fY - quad2[2].fY, quad2[2].fX - origin.fX); 4374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool oldSchoolOverlap = radianBetween(a1s, a2s, a1e) 4384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org || radianBetween(a1s, a2e, a1e) || radianBetween(a2s, a1s, a2e) 4394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org || radianBetween(a2s, a1e, a2e); 4404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int overlap = quadHullsOverlap(reporter, quad1, quad2); 4414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool realMatchesOverlap = realOverlap == overlap || SK_ScalarPI - fabs(a2s - a1s) < 0.002; 4424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (realOverlap != overlap) { 4434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("\nSK_ScalarPI - fabs(a2s - a1s) = %1.9g\n", SK_ScalarPI - fabs(a2s - a1s)); 4444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!realMatchesOverlap) { 4464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org DumpQ(quad1, quad2, testNo); 4474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, realMatchesOverlap); 4494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (oldSchoolOverlap != (overlap < 0)) { 4504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org overlap = quadHullsOverlap(reporter, quad1, quad2); // set a breakpoint and debug if assert fires 4514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, oldSchoolOverlap == (overlap < 0)); 4524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector v1s = quad1[1] - quad1[0]; 4544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector v1e = quad1[2] - quad1[0]; 4554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector v2s = quad2[1] - quad2[0]; 4564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector v2e = quad2[2] - quad2[0]; 4574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double vDir[2] = { v1s.cross(v1e), v2s.cross(v2e) }; 4584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool ray1In2 = v1s.cross(v2s) * vDir[1] <= 0 && v1s.cross(v2e) * vDir[1] >= 0; 4594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool ray2In1 = v2s.cross(v1s) * vDir[0] <= 0 && v2s.cross(v1e) * vDir[0] >= 0; 4604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (overlap >= 0) { 4614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // verify that hulls really don't overlap 4624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, !ray1In2); 4634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, !ray2In1); 4644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool ctrl1In2 = v1e.cross(v2s) * vDir[1] <= 0 && v1e.cross(v2e) * vDir[1] >= 0; 4654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, !ctrl1In2); 4664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool ctrl2In1 = v2e.cross(v1s) * vDir[0] <= 0 && v2e.cross(v1e) * vDir[0] >= 0; 4674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, !ctrl2In1); 4684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // check answer against reference 4694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bruteForce(reporter, quad1, quad2, overlap > 0); 4704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // continue end point rays and see if they intersect the opposite curve 4724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDLine rays[] = {{{origin, quad2[2]}}, {{origin, quad1[2]}}}; 4734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDQuad* quads[] = {&quad1, &quad2}; 4744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector midSpokes[2]; 4754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkIntersections intersect[2]; 4764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double minX, minY, maxX, maxY; 4774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org minX = minY = SK_ScalarInfinity; 4784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org maxX = maxY = -SK_ScalarInfinity; 4794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double maxWidth = 0; 4804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool useIntersect = false; 4814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double smallestTs[] = {1, 1}; 4824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (unsigned index = 0; index < SK_ARRAY_COUNT(quads); ++index) { 4834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDQuad& q = *quads[index]; 4844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org midSpokes[index] = q.ptAtT(0.5) - origin; 4854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org minX = SkTMin(SkTMin(SkTMin(minX, origin.fX), q[1].fX), q[2].fX); 4864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org minY = SkTMin(SkTMin(SkTMin(minY, origin.fY), q[1].fY), q[2].fY); 4874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org maxX = SkTMax(SkTMax(SkTMax(maxX, origin.fX), q[1].fX), q[2].fX); 4884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org maxY = SkTMax(SkTMax(SkTMax(maxY, origin.fY), q[1].fY), q[2].fY); 4894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org maxWidth = SkTMax(maxWidth, SkTMax(maxX - minX, maxY - minY)); 4904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org intersect[index].intersectRay(q, rays[index]); 4914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkIntersections& i = intersect[index]; 4924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, i.used() >= 1); 4934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool foundZero = false; 4944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double smallT = 1; 4954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int idx2 = 0; idx2 < i.used(); ++idx2) { 4964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double t = i[0][idx2]; 4974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (t == 0) { 4984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org foundZero = true; 4994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 5004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (smallT > t) { 5024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org smallT = t; 5034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, foundZero == true); 5064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (smallT == 1) { 5074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 5084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector ray = q.ptAtT(smallT) - origin; 5104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector end = rays[index][1] - origin; 5114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (ray.fX * end.fX < 0 || ray.fY * end.fY < 0) { 5124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 5134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double rayDist = ray.length(); 5154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double endDist = end.length(); 5164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double delta = fabs(rayDist - endDist) / maxWidth; 5174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (delta > 1e-4) { 5184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org useIntersect ^= true; 5194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org smallestTs[index] = smallT; 5214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool firstInside; 5234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (useIntersect) { 5244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int sIndex = (int) (smallestTs[1] < 1); 5254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, smallestTs[sIndex ^ 1] == 1); 5264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double t = smallestTs[sIndex]; 5274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDQuad& q = *quads[sIndex]; 5284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector ray = q.ptAtT(t) - origin; 5294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector end = rays[sIndex][1] - origin; 5304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double rayDist = ray.length(); 5314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double endDist = end.length(); 5324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector mid = q.ptAtT(t / 2) - origin; 5334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double midXray = mid.crossCheck(ray); 5344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (gPathOpsAngleIdeasVerbose) { 5354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("rayDist>endDist:%d sIndex==0:%d vDir[sIndex]<0:%d midXray<0:%d\n", 5364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org rayDist > endDist, sIndex == 0, vDir[sIndex] < 0, midXray < 0); 5374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(SkScalarSignAsInt(SkDoubleToScalar(midXray)) 5394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org == SkScalarSignAsInt(SkDoubleToScalar(vDir[sIndex]))); 5404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org firstInside = (rayDist > endDist) ^ (sIndex == 0) ^ (vDir[sIndex] < 0); 5414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else if (overlap >= 0) { 5424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; // answer has already been determined 5434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 5444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org firstInside = checkParallel(reporter, quad1, quad2); 5454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (overlap < 0) { 5474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDEBUGCODE(int realEnds =) 548dac1d17027dcaa5596885a9f333979418b35001ccaryclark PathOpsAngleTester::EndsIntersect(*seg[0].debugLastAngle(), 549dac1d17027dcaa5596885a9f333979418b35001ccaryclark *seg[1].debugLastAngle()); 5504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(realEnds == (firstInside ? 1 : 0)); 5514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bruteForce(reporter, quad1, quad2, firstInside); 5534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 5544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 5554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgDEF_TEST(PathOpsAngleOverlapHullsOne, reporter) { 5564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// gPathOpsAngleIdeasVerbose = true; 5574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDQuad quads[] = { 5584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org{{{939.4808349609375, 914.355224609375}, {-357.7921142578125, 590.842529296875}, {736.8936767578125, -350.717529296875}}}, 5594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org{{{939.4808349609375, 914.355224609375}, {-182.85418701171875, 634.4552001953125}, {-509.62615966796875, 576.1182861328125}}} 5604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org }; 5614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int index = 0; index < (int) SK_ARRAY_COUNT(quads); index += 2) { 5624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org testQuadAngles(reporter, quads[index], quads[index + 1], 0); 5634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 5654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 5664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgDEF_TEST(PathOpsAngleOverlapHulls, reporter) { 5674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default 5684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 5694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkRandom ran; 5714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int index = 0; index < 100000; ++index) { 5724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (index % 1000 == 999) SkDebugf("."); 5734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDPoint origin = {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}; 5744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDQuad quad1 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}, 5754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}}; 5764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (quad1[0] == quad1[2]) { 5774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 5784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDQuad quad2 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}, 5804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}}; 5814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (quad2[0] == quad2[2]) { 5824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 5834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkIntersections i; 5854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org i.intersect(quad1, quad2); 5864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, i.used() >= 1); 5874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (i.used() > 1) { 5884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 5894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org testQuadAngles(reporter, quad1, quad2, index); 5914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 5934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 5944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgDEF_TEST(PathOpsAngleBruteT, reporter) { 5954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default 5964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 5974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkRandom ran; 5994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double smaller = SK_Scalar1; 6004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDQuad small[2]; 6014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDEBUGCODE(int smallIndex); 6024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int index = 0; index < 100000; ++index) { 6034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDPoint origin = {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}; 6044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDQuad quad1 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}, 6054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}}; 6064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (quad1[0] == quad1[2]) { 6074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 6084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 6094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDQuad quad2 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}, 6104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}}; 6114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (quad2[0] == quad2[2]) { 6124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 6134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 6144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkIntersections i; 6154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org i.intersect(quad1, quad2); 6164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, i.used() >= 1); 6174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (i.used() > 1) { 6184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 6194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 6204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org TRange lowerRange, upperRange; 6214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool result = bruteMinT(reporter, quad1, quad2, &lowerRange, &upperRange); 6224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, result); 6234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double min = SkTMin(upperRange.t1, upperRange.t2); 6244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (smaller > min) { 6254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org small[0] = quad1; 6264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org small[1] = quad2; 6274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDEBUGCODE(smallIndex = index); 6284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org smaller = min; 6294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 6304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 6314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#ifdef SK_DEBUG 6324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org DumpQ(small[0], small[1], smallIndex); 6334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 6344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 6354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 6364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgDEF_TEST(PathOpsAngleBruteTOne, reporter) { 6374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// gPathOpsAngleIdeasVerbose = true; 6384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDQuad quads[] = { 6394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org{{{-770.8492431640625, 948.2369384765625}, {-853.37066650390625, 972.0301513671875}, {-200.62042236328125, -26.7174072265625}}}, 6404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org{{{-770.8492431640625, 948.2369384765625}, {513.602783203125, 578.8681640625}, {960.641357421875, -813.69757080078125}}}, 6414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org{{{563.8267822265625, -107.4566650390625}, {-44.67724609375, -136.57452392578125}, {492.3856201171875, -268.79644775390625}}}, 6424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org{{{563.8267822265625, -107.4566650390625}, {708.049072265625, -100.77789306640625}, {-48.88226318359375, 967.9022216796875}}}, 6434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org{{{598.857421875, 846.345458984375}, {-644.095703125, -316.12921142578125}, {-97.64599609375, 20.6158447265625}}}, 6444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org{{{598.857421875, 846.345458984375}, {715.7142333984375, 955.3599853515625}, {-919.9478759765625, 691.611328125}}}, 6454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org }; 6464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org TRange lowerRange, upperRange; 6474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bruteMinT(reporter, quads[0], quads[1], &lowerRange, &upperRange); 6484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bruteMinT(reporter, quads[2], quads[3], &lowerRange, &upperRange); 6494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bruteMinT(reporter, quads[4], quads[5], &lowerRange, &upperRange); 6504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 6514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 6524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org/* 6534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgThe sorting problem happens when the inital tangents are not a true indicator of the curve direction 6544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgNearly always, the initial tangents do give the right answer, 6554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgso the trick is to figure out when the initial tangent cannot be trusted. 6564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgIf the convex hulls of both curves are in the same half plane, and not overlapping, sorting the 6574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orghulls is enough. 6584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgIf the hulls overlap, and have the same general direction, then intersect the shorter end point ray 6594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgwith the opposing curve, and see on which side of the shorter curve the opposing intersection lies. 6604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgOtherwise, if the control vector is extremely short, likely the point on curve must be computed 6614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgIf moving the control point slightly can change the sign of the cross product, either answer could 6624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgbe "right". 6634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgWe need to determine how short is extremely short. Move the control point a set percentage of 6644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgthe largest length to determine how stable the curve is vis-a-vis the initial tangent. 6654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org*/ 6664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 6674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic const SkDQuad extremeTests[][2] = { 6684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org { 6694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{-708.0077926931004,-154.61669472244046}, 6704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-707.9234268635319,-154.30459999551294}, 6714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {505.58447265625,-504.9130859375}}}, 6724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{-708.0077926931004,-154.61669472244046}, 6734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-711.127526325141,-163.9446090624656}, 6744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-32.39227294921875,-906.3277587890625}}}, 6754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org }, { 6764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{-708.0077926931004,-154.61669472244046}, 6774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-708.2875337527566,-154.36676458635623}, 6784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {505.58447265625,-504.9130859375}}}, 6794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{-708.0077926931004,-154.61669472244046}, 6804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-708.4111557216864,-154.5366642875255}, 6814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-32.39227294921875,-906.3277587890625}}}, 6824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org }, { 6834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{-609.0230951752058,-267.5435593490574}, 6844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-594.1120809906336,-136.08492475411555}, 6854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {505.58447265625,-504.9130859375}}}, 6864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{-609.0230951752058,-267.5435593490574}, 6874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-693.7467719138988,-341.3259237831895}, 6884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-32.39227294921875,-906.3277587890625}}} 6894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org }, { 6904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{-708.0077926931004,-154.61669472244046}, 6914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-707.9994640658723,-154.58588461064852}, 6924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {505.58447265625,-504.9130859375}}}, 6934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{-708.0077926931004,-154.61669472244046}, 6944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-708.0239418990758,-154.6403553507124}, 6954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-32.39227294921875,-906.3277587890625}}} 6964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org }, { 6974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{-708.0077926931004,-154.61669472244046}, 6984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-707.9993222215099,-154.55999389855003}, 6994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {68.88981098017803,296.9273945411635}}}, 7004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{-708.0077926931004,-154.61669472244046}, 7014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-708.0509091919608,-154.64675214697067}, 7024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-777.4871194247767,-995.1470120113145}}} 7034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org }, { 7044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{-708.0077926931004,-154.61669472244046}, 7054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-708.0060491116379,-154.60889321524968}, 7064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {229.97088707895057,-430.0569357467175}}}, 7074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{-708.0077926931004,-154.61669472244046}, 7084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-708.013911296257,-154.6219143988058}, 7094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {138.13162892614037,-573.3689311737394}}} 7104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org }, { 7114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{-543.2570545751013,-237.29243831075053}, 7124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-452.4119186056987,-143.47223056267802}, 7134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {229.97088707895057,-430.0569357467175}}}, 7144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{{-543.2570545751013,-237.29243831075053}, 7154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {-660.5330371214436,-362.0016148388}, 7164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {138.13162892614037,-573.3689311737394}}}, 7174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org }, 7184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org}; 7194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 7204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic double endCtrlRatio(const SkDQuad quad) { 7214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector longEdge = quad[2] - quad[0]; 7224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double longLen = longEdge.length(); 7234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector shortEdge = quad[1] - quad[0]; 7244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double shortLen = shortEdge.length(); 7254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return longLen / shortLen; 7264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 7274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 7284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic void computeMV(const SkDQuad& quad, const SkDVector& v, double m, SkDVector mV[2]) { 7294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDPoint mPta = {quad[1].fX - m * v.fY, quad[1].fY + m * v.fX}; 7304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDPoint mPtb = {quad[1].fX + m * v.fY, quad[1].fY - m * v.fX}; 7314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org mV[0] = mPta - quad[0]; 7324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org mV[1] = mPtb - quad[0]; 7334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 7344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 7354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic double mDistance(skiatest::Reporter* reporter, bool agrees, const SkDQuad& q1, 7364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDQuad& q2) { 7374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (1 && agrees) { 7384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return SK_ScalarMax; 7394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 7404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // how close is the angle from inflecting in the opposite direction? 7414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector v1 = q1[1] - q1[0]; 7424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector v2 = q2[1] - q2[0]; 7434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double dir = v1.crossCheck(v2); 7444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, dir != 0); 7454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // solve for opposite direction displacement scale factor == m 7464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x 7474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1] 7484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x) 7494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.x) 7504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x 7514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y) 7524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // m = v1.cross(v2) / v1.dot(v2) 7534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double div = v1.dot(v2); 7544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, div != 0); 7554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double m = dir / div; 7564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector mV1[2], mV2[2]; 7574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org computeMV(q1, v1, m, mV1); 7584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org computeMV(q2, v2, m, mV2); 7594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double dist1 = v1.length() * m; 7604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double dist2 = v2.length() * m; 7614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (gPathOpsAngleIdeasVerbose) { 7624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%c r1=%1.9g r2=%1.9g m=%1.9g dist1=%1.9g dist2=%1.9g " 7634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org " dir%c 1a=%1.9g 1b=%1.9g 2a=%1.9g 2b=%1.9g\n", agrees ? 'T' : 'F', 7644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org endCtrlRatio(q1), endCtrlRatio(q2), m, dist1, dist2, dir > 0 ? '+' : '-', 7654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org mV1[0].crossCheck(v2), mV1[1].crossCheck(v2), 7664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org mV2[0].crossCheck(v1), mV2[1].crossCheck(v1)); 7674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 7684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (1) { 7694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool use1 = fabs(dist1) < fabs(dist2); 7704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (gPathOpsAngleIdeasVerbose) { 7714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%c dist=%1.9g r=%1.9g\n", agrees ? 'T' : 'F', use1 ? dist1 : dist2, 7724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org use1 ? distEndRatio(dist1, q1) : distEndRatio(dist2, q2)); 7734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 7744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return fabs(use1 ? distEndRatio(dist1, q1) : distEndRatio(dist2, q2)); 7754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 7764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return SK_ScalarMax; 7774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 7784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 7794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgstatic void midPointAgrees(skiatest::Reporter* reporter, const SkDQuad& q1, const SkDQuad& q2, 7804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool ccw) { 7814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDPoint mid1 = q1.ptAtT(0.5); 7824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector m1 = mid1 - q1[0]; 7834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDPoint mid2 = q2.ptAtT(0.5); 7844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector m2 = mid2 - q2[0]; 7854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, ccw ? m1.crossCheck(m2) < 0 : m1.crossCheck(m2) > 0); 7864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 7874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 7884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgDEF_TEST(PathOpsAngleExtreme, reporter) { 7894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default 7904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 7914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 7924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double maxR = SK_ScalarMax; 7934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int index = 0; index < (int) SK_ARRAY_COUNT(extremeTests); ++index) { 7944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDQuad& quad1 = extremeTests[index][0]; 7954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDQuad& quad2 = extremeTests[index][1]; 7964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (gPathOpsAngleIdeasVerbose) { 7974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%s %d\n", __FUNCTION__, index); 7984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 7994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, quad1[0] == quad2[0]); 8004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkIntersections i; 8014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org i.intersect(quad1, quad2); 8024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, i.used() == 1); 8034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, i.pt(0) == quad1[0]); 8044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int overlap = quadHullsOverlap(reporter, quad1, quad2); 8054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, overlap >= 0); 8064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector sweep[2], tweep[2]; 8074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org setQuadHullSweep(quad1, sweep); 8084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org setQuadHullSweep(quad2, tweep); 8094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s0xt0 = sweep[0].crossCheck(tweep[0]); 8104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org REPORTER_ASSERT(reporter, s0xt0 != 0); 8114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool ccw = s0xt0 < 0; 8124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool agrees = bruteForceCheck(reporter, quad1, quad2, ccw); 8134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org maxR = SkTMin(maxR, mDistance(reporter, agrees, quad1, quad2)); 8144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (agrees) { 8154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 8164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 8174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org midPointAgrees(reporter, quad1, quad2, !ccw); 8184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDQuad q1 = quad1; 8194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDQuad q2 = quad2; 8204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double loFail = 1; 8214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double hiPass = 2; 8224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // double vectors until t passes 8234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 8244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org q1[1].fX = quad1[0].fX * (1 - hiPass) + quad1[1].fX * hiPass; 8254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org q1[1].fY = quad1[0].fY * (1 - hiPass) + quad1[1].fY * hiPass; 8264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org q2[1].fX = quad2[0].fX * (1 - hiPass) + quad2[1].fX * hiPass; 8274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org q2[1].fY = quad2[0].fY * (1 - hiPass) + quad2[1].fY * hiPass; 8284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org agrees = bruteForceCheck(reporter, q1, q2, ccw); 8294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org maxR = SkTMin(maxR, mDistance(reporter, agrees, q1, q2)); 8304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (agrees) { 8314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org break; 8324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 8334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org midPointAgrees(reporter, quad1, quad2, !ccw); 8344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org loFail = hiPass; 8354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org hiPass *= 2; 8364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while (true); 8374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // binary search to find minimum pass 8384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double midTest = (loFail + hiPass) / 2; 8394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double step = (hiPass - loFail) / 4; 8404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org while (step > FLT_EPSILON) { 8414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org q1[1].fX = quad1[0].fX * (1 - midTest) + quad1[1].fX * midTest; 8424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org q1[1].fY = quad1[0].fY * (1 - midTest) + quad1[1].fY * midTest; 8434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org q2[1].fX = quad2[0].fX * (1 - midTest) + quad2[1].fX * midTest; 8444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org q2[1].fY = quad2[0].fY * (1 - midTest) + quad2[1].fY * midTest; 8454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org agrees = bruteForceCheck(reporter, q1, q2, ccw); 8464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org maxR = SkTMin(maxR, mDistance(reporter, agrees, q1, q2)); 8474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!agrees) { 8484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org midPointAgrees(reporter, quad1, quad2, !ccw); 8494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 8504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org midTest += agrees ? -step : step; 8514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org step /= 2; 8524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 8534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#ifdef SK_DEBUG 8544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// DumpQ(q1, q2, 999); 8554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 8564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 8574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (gPathOpsAngleIdeasVerbose) { 8584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("maxR=%1.9g\n", maxR); 8594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 8604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 861