107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Copyright 2012 Google Inc. 307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * 407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * found in the LICENSE file. 607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkIntersections.h" 807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkOpAngle.h" 9cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#include "SkOpSegment.h" 1007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsCurve.h" 11b76d3b677713693137936ff813b92c4be48af173commit-bot@chromium.org#include "SkTSort.h" 1207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 13cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#if DEBUG_ANGLE 14cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#include "SkString.h" 15cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#endif 16cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com 17cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com/* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest 18cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com positive y. The largest angle has a positive x and a zero y. */ 19cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com 20cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#if DEBUG_ANGLE 214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org static bool CompareResult(SkString* bugOut, int append, bool compare) { 224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%s %c %d\n", bugOut->c_str(), compare ? 'T' : 'F', append); 23cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return compare; 24cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 25cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com 26cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com #define COMPARE_RESULT(append, compare) CompareResult(&bugOut, append, compare) 27cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#else 288f6ef4010f6835c5ce9ede180e50a6a58512a81eskia.committer@gmail.com #define COMPARE_RESULT(append, compare) compare 29a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com#endif 30a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com 314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org/* quarter angle values for sector 324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org31 x > 0, y == 0 horizontal line (to the right) 344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org0 x > 0, y == epsilon quad/cubic horizontal tangent eventually going +y 354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org1 x > 0, y > 0, x > y nearer horizontal angle 364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org2 x + e == y quad/cubic 45 going horiz 374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org3 x > 0, y > 0, x == y 45 angle 384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org4 x == y + e quad/cubic 45 going vert 394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org5 x > 0, y > 0, x < y nearer vertical angle 404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org6 x == epsilon, y > 0 quad/cubic vertical tangent eventually going +x 414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org7 x == 0, y > 0 vertical line (to the top) 424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 8 7 6 444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 9 | 5 454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 10 | 4 464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 11 | 3 474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 12 \ | / 2 484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 13 | 1 494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 14 | 0 504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 15 --------------+------------- 31 514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 16 | 30 524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 17 | 29 534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 18 / | \ 28 544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 19 | 27 554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 20 | 26 564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 21 | 25 574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 22 23 24 584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org*/ 594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// return true if lh < this < rh 614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgbool SkOpAngle::after(const SkOpAngle* test) const { 624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkOpAngle& lh = *test; 634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkOpAngle& rh = *lh.fNext; 644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(&lh != &rh); 654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_ANGLE 664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkString bugOut; 674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g" 684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g" 694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__, 704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org lh.fSegment->debugID(), lh.debugID(), lh.fSectorStart, lh.fSectorEnd, 714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org lh.fSegment->t(lh.fStart), lh.fSegment->t(lh.fEnd), 724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSegment->debugID(), debugID(), fSectorStart, fSectorEnd, fSegment->t(fStart), 734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSegment->t(fEnd), 744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org rh.fSegment->debugID(), rh.debugID(), rh.fSectorStart, rh.fSectorEnd, 754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd)); 764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (lh.fComputeSector && !const_cast<SkOpAngle&>(lh).computeSector()) { 784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return COMPARE_RESULT(1, true); 794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (fComputeSector && !const_cast<SkOpAngle*>(this)->computeSector()) { 814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return COMPARE_RESULT(2, true); 824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (rh.fComputeSector && !const_cast<SkOpAngle&>(rh).computeSector()) { 844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return COMPARE_RESULT(3, true); 854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_ANGLE // reset bugOut with computed sectors 874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g" 884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g" 894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__, 904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org lh.fSegment->debugID(), lh.debugID(), lh.fSectorStart, lh.fSectorEnd, 914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org lh.fSegment->t(lh.fStart), lh.fSegment->t(lh.fEnd), 924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSegment->debugID(), debugID(), fSectorStart, fSectorEnd, fSegment->t(fStart), 934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSegment->t(fEnd), 944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org rh.fSegment->debugID(), rh.debugID(), rh.fSectorStart, rh.fSectorEnd, 954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd)); 964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool ltrOverlap = (lh.fSectorMask | rh.fSectorMask) & fSectorMask; 984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool lrOverlap = lh.fSectorMask & rh.fSectorMask; 994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int lrOrder; // set to -1 if either order works 1004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!lrOverlap) { // no lh/rh sector overlap 1014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!ltrOverlap) { // no lh/this/rh sector overlap 1024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return COMPARE_RESULT(4, (lh.fSectorEnd > rh.fSectorStart) 1034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org ^ (fSectorStart > lh.fSectorEnd) ^ (fSectorStart > rh.fSectorStart)); 1044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int lrGap = (rh.fSectorStart - lh.fSectorStart + 32) & 0x1f; 1064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org /* A tiny change can move the start +/- 4. The order can only be determined if 1074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org lr gap is not 12 to 20 or -12 to -20. 1084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org -31 ..-21 1 1094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org -20 ..-12 -1 1104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org -11 .. -1 0 1114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 0 shouldn't get here 1124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 11 .. 1 1 1134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 12 .. 20 -1 1144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 21 .. 31 0 1154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org */ 1164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org lrOrder = lrGap > 20 ? 0 : lrGap > 11 ? -1 : 1; 1174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 1184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org lrOrder = (int) lh.orderable(rh); 1194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!ltrOverlap) { 1204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return COMPARE_RESULT(5, !lrOrder); 1214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int ltOrder; 1244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT((lh.fSectorMask & fSectorMask) || (rh.fSectorMask & fSectorMask)); 1254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (lh.fSectorMask & fSectorMask) { 1264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org ltOrder = (int) lh.orderable(*this); 1274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 1284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int ltGap = (fSectorStart - lh.fSectorStart + 32) & 0x1f; 1294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org ltOrder = ltGap > 20 ? 0 : ltGap > 11 ? -1 : 1; 1304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int trOrder; 1324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (rh.fSectorMask & fSectorMask) { 1334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org trOrder = (int) orderable(rh); 1344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 1354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int trGap = (rh.fSectorStart - fSectorStart + 32) & 0x1f; 1364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org trOrder = trGap > 20 ? 0 : trGap > 11 ? -1 : 1; 1374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (lrOrder >= 0 && ltOrder >= 0 && trOrder >= 0) { 1394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return COMPARE_RESULT(7, lrOrder ? (ltOrder & trOrder) : (ltOrder | trOrder)); 1404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(lrOrder >= 0 || ltOrder >= 0 || trOrder >= 0); 1424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// There's not enough information to sort. Get the pairs of angles in opposite planes. 1434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// If an order is < 0, the pair is already in an opposite plane. Check the remaining pairs. 1444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // FIXME : once all variants are understood, rewrite this more simply 1454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (ltOrder == 0 && lrOrder == 0) { 1464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(trOrder < 0); 1474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // FIXME : once this is verified to work, remove one opposite angle call 1484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDEBUGCODE(bool lrOpposite = lh.oppositePlanes(rh)); 1494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool ltOpposite = lh.oppositePlanes(*this); 1504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(lrOpposite != ltOpposite); 1514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return COMPARE_RESULT(8, ltOpposite); 1524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else if (ltOrder == 1 && trOrder == 0) { 1534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(lrOrder < 0); 1544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDEBUGCODE(bool ltOpposite = lh.oppositePlanes(*this)); 1554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool trOpposite = oppositePlanes(rh); 1564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(ltOpposite != trOpposite); 1574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return COMPARE_RESULT(9, trOpposite); 1584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else if (lrOrder == 1 && trOrder == 1) { 1594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(ltOrder < 0); 1604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDEBUGCODE(bool trOpposite = oppositePlanes(rh)); 1614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool lrOpposite = lh.oppositePlanes(rh); 1624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(lrOpposite != trOpposite); 1634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return COMPARE_RESULT(10, lrOpposite); 1644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (lrOrder < 0) { 1664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (ltOrder < 0) { 1674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return COMPARE_RESULT(11, trOrder); 1684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return COMPARE_RESULT(12, ltOrder); 1704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return COMPARE_RESULT(13, !lrOrder); 1724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 1734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 1744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// given a line, see if the opposite curve's convex hull is all on one side 1754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// returns -1=not on one side 0=this CW of test 1=this CCW of test 1764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgint SkOpAngle::allOnOneSide(const SkOpAngle& test) const { 1774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(!fIsCurve); 1784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(test.fIsCurve); 1794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDPoint& origin = test.fCurvePart[0]; 1804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkVector line; 1814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (fSegment->verb() == SkPath::kLine_Verb) { 1824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkPoint* linePts = fSegment->pts(); 1834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int lineStart = fStart < fEnd ? 0 : 1; 1844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org line = linePts[lineStart ^ 1] - linePts[lineStart]; 1854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 1864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkPoint shortPts[2] = { fCurvePart[0].asSkPoint(), fCurvePart[1].asSkPoint() }; 1874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org line = shortPts[1] - shortPts[0]; 1884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org float crosses[3]; 1904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkPath::Verb testVerb = test.fSegment->verb(); 1914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int iMax = SkPathOpsVerbToPoints(testVerb); 1924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// SkASSERT(origin == test.fCurveHalf[0]); 1934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDCubic& testCurve = test.fCurvePart; 1944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// do { 1954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int index = 1; index <= iMax; ++index) { 1964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org float xy1 = (float) (line.fX * (testCurve[index].fY - origin.fY)); 1974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org float xy2 = (float) (line.fY * (testCurve[index].fX - origin.fX)); 1984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org crosses[index - 1] = AlmostEqualUlps(xy1, xy2) ? 0 : xy1 - xy2; 1994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (crosses[0] * crosses[1] < 0) { 2014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return -1; 2024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (SkPath::kCubic_Verb == testVerb) { 2044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (crosses[0] * crosses[2] < 0 || crosses[1] * crosses[2] < 0) { 2054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return -1; 2064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (crosses[0]) { 2094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return crosses[0] < 0; 2104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (crosses[1]) { 2124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return crosses[1] < 0; 2134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (SkPath::kCubic_Verb == testVerb && crosses[2]) { 2154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return crosses[2] < 0; 2164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fUnorderable = true; 2184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return -1; 2194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 2204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 2214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgbool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) const { 222cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double absX = fabs(x); 223cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double absY = fabs(y); 224cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double length = absX < absY ? absX / 2 + absY : absX + absY / 2; 225cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com int exponent; 226cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com (void) frexp(length, &exponent); 227cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double epsilon = ldexp(FLT_EPSILON, exponent); 228cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkPath::Verb verb = fSegment->verb(); 229cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkASSERT(verb == SkPath::kQuad_Verb || verb == SkPath::kCubic_Verb); 230cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com // FIXME: the quad and cubic factors are made up ; determine actual values 231cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double slop = verb == SkPath::kQuad_Verb ? 4 * epsilon : 512 * epsilon; 232cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double xSlop = slop; 233cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double ySlop = x * y < 0 ? -xSlop : xSlop; // OPTIMIZATION: use copysign / _copysign ? 234cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double x1 = x - xSlop; 235cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double y1 = y + ySlop; 236cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double x_ry1 = x1 * ry; 237cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double rx_y1 = rx * y1; 238cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com *result = x_ry1 < rx_y1; 239cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double x2 = x + xSlop; 240cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double y2 = y - ySlop; 241cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double x_ry2 = x2 * ry; 242cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double rx_y2 = rx * y2; 243cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com bool less2 = x_ry2 < rx_y2; 244cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return *result == less2; 245cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com} 24607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgbool SkOpAngle::checkCrossesZero() const { 2484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int start = SkTMin(fSectorStart, fSectorEnd); 2494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int end = SkTMax(fSectorStart, fSectorEnd); 2504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool crossesZero = end - start > 16; 2514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return crossesZero; 2524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 25307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgbool SkOpAngle::checkParallel(const SkOpAngle& rh) const { 2554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector scratch[2]; 2564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDVector* sweep, * tweep; 2574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!fUnorderedSweep) { 2584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sweep = fSweep; 2594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 2604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org scratch[0] = fCurvePart[1] - fCurvePart[0]; 2614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sweep = &scratch[0]; 2624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!rh.fUnorderedSweep) { 2644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org tweep = rh.fSweep; 2654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 2664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org scratch[1] = rh.fCurvePart[1] - rh.fCurvePart[0]; 2674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org tweep = &scratch[1]; 2684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s0xt0 = sweep->crossCheck(*tweep); 2704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (tangentsDiverge(rh, s0xt0)) { 2714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return s0xt0 < 0; 2724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector m0 = fSegment->dPtAtT(midT()) - fCurvePart[0]; 2744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector m1 = rh.fSegment->dPtAtT(rh.midT()) - rh.fCurvePart[0]; 2754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double m0xm1 = m0.crossCheck(m1); 2764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (m0xm1 == 0) { 2774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fUnorderable = true; 2784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org rh.fUnorderable = true; 2794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return true; 2804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return m0xm1 < 0; 2824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 2834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 2844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// the original angle is too short to get meaningful sector information 2854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// lengthen it until it is long enough to be meaningful or leave it unset if lengthening it 2864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// would cause it to intersect one of the adjacent angles 2874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgbool SkOpAngle::computeSector() { 2884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (fComputedSector) { 2894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // FIXME: logically, this should return !fUnorderable, but doing so breaks testQuadratic51 2904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // -- but in general, this code may not work so this may be the least of problems 2914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // adding the bang fixes testQuads46x in release, however 292dac1d17027dcaa5596885a9f333979418b35001ccaryclark return !fUnorderable; 2934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 2944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(fSegment->verb() != SkPath::kLine_Verb && small()); 2954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fComputedSector = true; 2964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int step = fStart < fEnd ? 1 : -1; 2974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int limit = step > 0 ? fSegment->count() : -1; 2984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int checkEnd = fEnd; 2994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 3004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// advance end 3014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkOpSpan& span = fSegment->span(checkEnd); 3024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkOpSegment* other = span.fOther; 3034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int oCount = other->count(); 3044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int oIndex = 0; oIndex < oCount; ++oIndex) { 3054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkOpSpan& oSpan = other->span(oIndex); 3064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (oSpan.fOther != fSegment) { 3074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 3084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (oSpan.fOtherIndex == checkEnd) { 3104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 3114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!approximately_equal(oSpan.fOtherT, span.fT)) { 3134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 3144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org goto recomputeSector; 316cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 3174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org checkEnd += step; 3184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while (checkEnd != limit); 3194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgrecomputeSector: 3204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (checkEnd == fEnd || checkEnd - step == fEnd) { 3214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fUnorderable = true; 3224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return false; 323cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 3248cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org int saveEnd = fEnd; 325dac1d17027dcaa5596885a9f333979418b35001ccaryclark fComputedEnd = fEnd = checkEnd - step; 3264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org setSpans(); 3274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org setSector(); 3288cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org fEnd = saveEnd; 3294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return !fUnorderable; 3304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 3314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 3324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// returns -1 if overlaps 0 if no overlap cw 1 if no overlap ccw 3334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgint SkOpAngle::convexHullOverlaps(const SkOpAngle& rh) const { 3344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDVector* sweep = fSweep; 3354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDVector* tweep = rh.fSweep; 3364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s0xs1 = sweep[0].crossCheck(sweep[1]); 3374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s0xt0 = sweep[0].crossCheck(tweep[0]); 3384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s1xt0 = sweep[1].crossCheck(tweep[0]); 3394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool tBetweenS = s0xs1 > 0 ? s0xt0 > 0 && s1xt0 < 0 : s0xt0 < 0 && s1xt0 > 0; 3404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s0xt1 = sweep[0].crossCheck(tweep[1]); 3414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s1xt1 = sweep[1].crossCheck(tweep[1]); 3424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org tBetweenS |= s0xs1 > 0 ? s0xt1 > 0 && s1xt1 < 0 : s0xt1 < 0 && s1xt1 > 0; 3434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double t0xt1 = tweep[0].crossCheck(tweep[1]); 3444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (tBetweenS) { 3454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return -1; 3464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if ((s0xt0 == 0 && s1xt1 == 0) || (s1xt0 == 0 && s0xt1 == 0)) { // s0 to s1 equals t0 to t1 3484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return -1; 3494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool sBetweenT = t0xt1 > 0 ? s0xt0 < 0 && s0xt1 > 0 : s0xt0 > 0 && s0xt1 < 0; 3514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sBetweenT |= t0xt1 > 0 ? s1xt0 < 0 && s1xt1 > 0 : s1xt0 > 0 && s1xt1 < 0; 3524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (sBetweenT) { 3534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return -1; 3544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // if all of the sweeps are in the same half plane, then the order of any pair is enough 3564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (s0xt0 >= 0 && s0xt1 >= 0 && s1xt0 >= 0 && s1xt1 >= 0) { 3574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return 0; 3584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (s0xt0 <= 0 && s0xt1 <= 0 && s1xt0 <= 0 && s1xt1 <= 0) { 3604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return 1; 3614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // if the outside sweeps are greater than 180 degress: 3634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // first assume the inital tangents are the ordering 3644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // if the midpoint direction matches the inital order, that is enough 3654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector m0 = fSegment->dPtAtT(midT()) - fCurvePart[0]; 3664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector m1 = rh.fSegment->dPtAtT(rh.midT()) - rh.fCurvePart[0]; 3674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double m0xm1 = m0.crossCheck(m1); 3684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (s0xt0 > 0 && m0xm1 > 0) { 3694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return 0; 3704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (s0xt0 < 0 && m0xm1 < 0) { 3724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return 1; 3734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (tangentsDiverge(rh, s0xt0)) { 3754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return s0xt0 < 0; 3764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return m0xm1 < 0; 3784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 3794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 3804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// OPTIMIZATION: longest can all be either lazily computed here or precomputed in setup 3814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgdouble SkOpAngle::distEndRatio(double dist) const { 3824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double longest = 0; 3834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkOpSegment& segment = *this->segment(); 3844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int ptCount = SkPathOpsVerbToPoints(segment.verb()); 3854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkPoint* pts = segment.pts(); 3864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int idx1 = 0; idx1 <= ptCount - 1; ++idx1) { 3874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int idx2 = idx1 + 1; idx2 <= ptCount; ++idx2) { 3884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (idx1 == idx2) { 3894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 390cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 3914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector v; 3924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org v.set(pts[idx2] - pts[idx1]); 3934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double lenSq = v.lengthSquared(); 3944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org longest = SkTMax(longest, lenSq); 3954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 3974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return sqrt(longest) / dist; 3984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 3994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 4004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgbool SkOpAngle::endsIntersect(const SkOpAngle& rh) const { 4014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkPath::Verb lVerb = fSegment->verb(); 4024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkPath::Verb rVerb = rh.fSegment->verb(); 4034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int lPts = SkPathOpsVerbToPoints(lVerb); 4044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int rPts = SkPathOpsVerbToPoints(rVerb); 4054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDLine rays[] = {{{fCurvePart[0], rh.fCurvePart[rPts]}}, 4064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{fCurvePart[0], fCurvePart[lPts]}}}; 4074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (rays[0][1] == rays[1][1]) { 4084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return checkParallel(rh); 4094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double smallTs[2] = {-1, -1}; 4114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool limited[2] = {false, false}; 4124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int index = 0; index < 2; ++index) { 4134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkOpSegment& segment = index ? *rh.fSegment : *fSegment; 4144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkIntersections i; 4154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org (*CurveIntersectRay[index ? rPts : lPts])(segment.pts(), rays[index], &i); 4164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// SkASSERT(i.used() >= 1); 417dac1d17027dcaa5596885a9f333979418b35001ccaryclark// if (i.used() <= 1) { 418dac1d17027dcaa5596885a9f333979418b35001ccaryclark// continue; 419dac1d17027dcaa5596885a9f333979418b35001ccaryclark// } 4204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double tStart = segment.t(index ? rh.fStart : fStart); 421dac1d17027dcaa5596885a9f333979418b35001ccaryclark double tEnd = segment.t(index ? rh.fComputedEnd : fComputedEnd); 422dac1d17027dcaa5596885a9f333979418b35001ccaryclark bool testAscends = index ? rh.fStart < rh.fComputedEnd : fStart < fComputedEnd; 4234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double t = testAscends ? 0 : 1; 4244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int idx2 = 0; idx2 < i.used(); ++idx2) { 4254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double testT = i[0][idx2]; 4264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!approximately_between_orderable(tStart, testT, tEnd)) { 4274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 4287eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 4294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (approximately_equal_orderable(tStart, testT)) { 4304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 431cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 4324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org smallTs[index] = t = testAscends ? SkTMax(t, testT) : SkTMin(t, testT); 4334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org limited[index] = approximately_equal_orderable(t, tEnd); 43407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 43507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 4364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if 0 4374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (smallTs[0] < 0 && smallTs[1] < 0) { // if neither ray intersects, do endpoint sort 4384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double m0xm1 = 0; 4394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (lVerb == SkPath::kLine_Verb) { 4404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(rVerb != SkPath::kLine_Verb); 4414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector m0 = rays[1][1] - fCurvePart[0]; 4424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDPoint endPt; 4434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org endPt.set(rh.fSegment->pts()[rh.fStart < rh.fEnd ? rPts : 0]); 4444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector m1 = endPt - fCurvePart[0]; 4454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org m0xm1 = m0.crossCheck(m1); 4467eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 4474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (rVerb == SkPath::kLine_Verb) { 4484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDPoint endPt; 4494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org endPt.set(fSegment->pts()[fStart < fEnd ? lPts : 0]); 4504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector m0 = endPt - fCurvePart[0]; 4514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector m1 = rays[0][1] - fCurvePart[0]; 4524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org m0xm1 = m0.crossCheck(m1); 4534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (m0xm1 != 0) { 4554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return m0xm1 < 0; 4564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4587eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com#endif 4594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool sRayLonger = false; 4604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector sCept = {0, 0}; 4614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double sCeptT = -1; 4624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int sIndex = -1; 4634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool useIntersect = false; 4644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int index = 0; index < 2; ++index) { 4654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (smallTs[index] < 0) { 4664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 4674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkOpSegment& segment = index ? *rh.fSegment : *fSegment; 4694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDPoint& dPt = segment.dPtAtT(smallTs[index]); 4704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector cept = dPt - rays[index][0]; 4714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // If this point is on the curve, it should have been detected earlier by ordinary 4724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // curve intersection. This may be hard to determine in general, but for lines, 4734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // the point could be close to or equal to its end, but shouldn't be near the start. 4744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if ((index ? lPts : rPts) == 1) { 4754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector total = rays[index][1] - rays[index][0]; 4764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (cept.lengthSquared() * 2 < total.lengthSquared()) { 4774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 4784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector end = rays[index][1] - rays[index][0]; 4814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (cept.fX * end.fX < 0 || cept.fY * end.fY < 0) { 4824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 4834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double rayDist = cept.length(); 4854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double endDist = end.length(); 4864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool rayLonger = rayDist > endDist; 4874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (limited[0] && limited[1] && rayLonger) { 4884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org useIntersect = true; 4894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sRayLonger = rayLonger; 4904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sCept = cept; 4914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sCeptT = smallTs[index]; 4924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sIndex = index; 4934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org break; 4944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double delta = fabs(rayDist - endDist); 4964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double minX, minY, maxX, maxY; 4974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org minX = minY = SK_ScalarInfinity; 4984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org maxX = maxY = -SK_ScalarInfinity; 4994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDCubic& curve = index ? rh.fCurvePart : fCurvePart; 5004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int ptCount = index ? rPts : lPts; 5014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int idx2 = 0; idx2 <= ptCount; ++idx2) { 5024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org minX = SkTMin(minX, curve[idx2].fX); 5034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org minY = SkTMin(minY, curve[idx2].fY); 5044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org maxX = SkTMax(maxX, curve[idx2].fX); 5054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org maxY = SkTMax(maxY, curve[idx2].fY); 5064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double maxWidth = SkTMax(maxX - minX, maxY - minY); 5084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org delta /= maxWidth; 5094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (delta > 1e-4 && (useIntersect ^= true)) { // FIXME: move this magic number 5104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sRayLonger = rayLonger; 5114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sCept = cept; 5124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sCeptT = smallTs[index]; 5134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sIndex = index; 5144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (useIntersect) { 5174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDCubic& curve = sIndex ? rh.fCurvePart : fCurvePart; 5184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkOpSegment& segment = sIndex ? *rh.fSegment : *fSegment; 5194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double tStart = segment.t(sIndex ? rh.fStart : fStart); 5204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector mid = segment.dPtAtT(tStart + (sCeptT - tStart) / 2) - curve[0]; 5214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double septDir = mid.crossCheck(sCept); 5224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!septDir) { 5234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return checkParallel(rh); 5244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return sRayLonger ^ (sIndex == 0) ^ (septDir < 0); 5264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 5274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return checkParallel(rh); 5284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 5304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 5314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// Most of the time, the first one can be found trivially by detecting the smallest sector value. 5324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// If all angles have the same sector value, actual sorting is required. 5334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgconst SkOpAngle* SkOpAngle::findFirst() const { 5344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkOpAngle* best = this; 5354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int bestStart = SkTMin(fSectorStart, fSectorEnd); 5364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkOpAngle* angle = this; 5374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org while ((angle = angle->fNext) != this) { 5384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int angleEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd); 5394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (angleEnd < bestStart) { 5404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return angle; // we wrapped around 5414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd); 5434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (bestStart > angleStart) { 5444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org best = angle; 5454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bestStart = angleStart; 5464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // back up to the first possible angle 5494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkOpAngle* firstBest = best; 5504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle = best; 5514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int bestEnd = SkTMax(best->fSectorStart, best->fSectorEnd); 5524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org while ((angle = angle->previous()) != firstBest) { 5534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (angle->fStop) { 554a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com break; 55507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd); 5574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // angles that are smaller by one aren't necessary better, since the larger may be a line 558a1ed7aec95eb8c77d1a39834fea476780007cadeskia.committer@gmail.com // and the smaller may be a curve that curls to the other side of the line. 5594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (bestEnd + 1 < angleStart) { 5604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return best; 5614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org best = angle; 5634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bestEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd); 5644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // in the case where all angles are nearly in the same sector, check the order to find the best 5664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org firstBest = best; 5674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle = best; 5684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 5694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle = angle->fNext; 5704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (angle->fStop) { 5714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return firstBest; 5724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool orderable = best->orderable(*angle); // note: may return an unorderable angle 5744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (orderable == 0) { 5754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return angle; 5764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org best = angle; 5784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while (angle != firstBest); 5794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // if the angles are equally ordered, fall back on the initial tangent 5804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool foundBelow = false; 5814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org while ((angle = angle->fNext)) { 5824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector scratch[2]; 5834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDVector* sweep; 5844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!angle->fUnorderedSweep) { 5854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sweep = angle->fSweep; 5864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 5874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org scratch[0] = angle->fCurvePart[1] - angle->fCurvePart[0]; 5884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org sweep = &scratch[0]; 5894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool isAbove = sweep->fY <= 0; 5914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (isAbove && foundBelow) { 5924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return angle; 5934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org foundBelow |= !isAbove; 5954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (angle == firstBest) { 5964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return NULL; // should not loop around 5974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 5994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(0); // should never get here 6004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return NULL; 6014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 6024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 6034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org/* y<0 y==0 y>0 x<0 x==0 x>0 xy<0 xy==0 xy>0 6044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 0 x x x 6054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 1 x x x 6064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 2 x x x 6074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 3 x x x 6084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 4 x x x 6094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 5 x x x 6104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 6 x x x 6114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 7 x x x 6124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 8 x x x 6134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 9 x x x 6144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 10 x x x 6154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 11 x x x 6164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 12 x x x 6174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 13 x x x 6184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 14 x x x 6194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 15 x x x 6204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org*/ 6214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgint SkOpAngle::findSector(SkPath::Verb verb, double x, double y) const { 6224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double absX = fabs(x); 6234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double absY = fabs(y); 6244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double xy = SkPath::kLine_Verb == verb || !AlmostEqualUlps(absX, absY) ? absX - absY : 0; 6254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // If there are four quadrants and eight octants, and since the Latin for sixteen is sedecim, 6264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // one could coin the term sedecimant for a space divided into 16 sections. 6274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // http://english.stackexchange.com/questions/133688/word-for-something-partitioned-into-16-parts 6284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org static const int sedecimant[3][3][3] = { 6294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // y<0 y==0 y>0 6304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // x<0 x==0 x>0 x<0 x==0 x>0 x<0 x==0 x>0 6314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{ 4, 3, 2}, { 7, -1, 15}, {10, 11, 12}}, // abs(x) < abs(y) 6324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{ 5, -1, 1}, {-1, -1, -1}, { 9, -1, 13}}, // abs(x) == abs(y) 6334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org {{ 6, 3, 0}, { 7, -1, 15}, { 8, 11, 14}}, // abs(x) > abs(y) 6344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org }; 6354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int sector = sedecimant[(xy >= 0) + (xy > 0)][(y >= 0) + (y > 0)][(x >= 0) + (x > 0)] * 2 + 1; 6364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(SkPath::kLine_Verb == verb || sector >= 0); 6374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return sector; 6384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 6394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 6404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// OPTIMIZE: if this loops to only one other angle, after first compare fails, insert on other side 6414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// OPTIMIZE: return where insertion succeeded. Then, start next insertion on opposite side 6424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgvoid SkOpAngle::insert(SkOpAngle* angle) { 6434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (angle->fNext) { 6444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (loopCount() >= angle->loopCount()) { 6454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!merge(angle)) { 6464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 6474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 6484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else if (fNext) { 6494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!angle->merge(this)) { 6504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 6514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 6524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 6534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle->insert(this); 6544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 6554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 65607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool singleton = NULL == fNext; 6584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (singleton) { 6594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fNext = this; 660a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com } 6614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* next = fNext; 6624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (next->fNext == this) { 6638cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (angle->overlap(*this)) { 6648cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org return; 6658cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 6664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (singleton || angle->after(this)) { 6674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org this->fNext = angle; 6684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle->fNext = next; 6694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 6704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org next->fNext = angle; 6714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle->fNext = this; 6724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 6734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org debugValidateNext(); 6744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 6754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 6764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* last = this; 6774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 6784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(last->fNext == next); 6798cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (angle->overlap(*last) || angle->overlap(*next)) { 6808cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org return; 6818cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 6824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (angle->after(last)) { 6834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org last->fNext = angle; 6844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle->fNext = next; 6854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org debugValidateNext(); 6864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 6874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 6884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org last = next; 6894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org next = next->fNext; 6904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (last == this && next->fUnorderable) { 6914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fUnorderable = true; 6924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 6934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 6944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(last != this); 6954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while (true); 69607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 69707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 698cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.combool SkOpAngle::isHorizontal() const { 6994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return !fIsCurve && fSweep[0].fY == 0; 70007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 70107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 7024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgSkOpSpan* SkOpAngle::lastMarked() const { 7034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (fLastMarked) { 7044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (fLastMarked->fChased) { 7054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return NULL; 7064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 7074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fLastMarked->fChased = true; 70807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return fLastMarked; 7104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 7114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 7128cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.orgbool SkOpAngle::loopContains(const SkOpAngle& test) const { 7138cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (!fNext) { 7148cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org return false; 7158cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 7168cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org const SkOpAngle* first = this; 7178cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org const SkOpAngle* loop = this; 7188cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org const SkOpSegment* tSegment = test.fSegment; 7198cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org double tStart = tSegment->span(test.fStart).fT; 7208cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org double tEnd = tSegment->span(test.fEnd).fT; 7218cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org do { 7228cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org const SkOpSegment* lSegment = loop->fSegment; 7238cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org // FIXME : use precisely_equal ? or compare points exactly ? 7248cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (lSegment != tSegment) { 7258cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org continue; 7268cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 7278cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org double lStart = lSegment->span(loop->fStart).fT; 7288cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (lStart != tEnd) { 7298cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org continue; 7308cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 7318cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org double lEnd = lSegment->span(loop->fEnd).fT; 7328cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (lEnd == tStart) { 7338cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org return true; 7348cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 7358cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } while ((loop = loop->fNext) != first); 7368cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org return false; 7378cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org} 7388cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org 7394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgint SkOpAngle::loopCount() const { 7404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int count = 0; 7414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkOpAngle* first = this; 7424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkOpAngle* next = this; 7434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 7444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org next = next->fNext; 7454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org ++count; 7464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while (next && next != first); 7474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return count; 7484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 7494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 7504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// OPTIMIZATION: can this be done better in after when angles are sorted? 7514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgvoid SkOpAngle::markStops() { 7524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* angle = this; 7534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int lastEnd = SkTMax(fSectorStart, fSectorEnd); 7544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 7554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle = angle->fNext; 7564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd); 7574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // angles that are smaller by one aren't necessary better, since the larger may be a line 758a1ed7aec95eb8c77d1a39834fea476780007cadeskia.committer@gmail.com // and the smaller may be a curve that curls to the other side of the line. 7594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (lastEnd + 1 < angleStart) { 7604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle->fStop = true; 7614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 7624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org lastEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd); 7634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while (angle != this); 7644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 7654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 7664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgbool SkOpAngle::merge(SkOpAngle* angle) { 7674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(fNext); 7684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(angle->fNext); 7694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* working = angle; 7704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 7714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (this == working) { 7724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return false; 7734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 7744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org working = working->fNext; 7754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while (working != angle); 7764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 7774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* next = working->fNext; 7784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org working->fNext = NULL; 7794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org insert(working); 7804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org working = next; 7814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while (working != angle); 7824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // it's likely that a pair of the angles are unorderable 7834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_ANGLE 7844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* last = angle; 7854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org working = angle->fNext; 7864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 7874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(last->fNext == working); 7884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org last->fNext = working->fNext; 7894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(working->after(last)); 7904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org last->fNext = working; 7914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org last = working; 7924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org working = working->fNext; 7934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while (last != angle); 7944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 7954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org debugValidateNext(); 7964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return true; 7974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 7984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 7994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgdouble SkOpAngle::midT() const { 8004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return (fSegment->t(fStart) + fSegment->t(fEnd)) / 2; 8014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 8024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 8034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgbool SkOpAngle::oppositePlanes(const SkOpAngle& rh) const { 8044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int startSpan = abs(rh.fSectorStart - fSectorStart); 8054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return startSpan >= 8; 8064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 8074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 8084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgbool SkOpAngle::orderable(const SkOpAngle& rh) const { 8094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int result; 8104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!fIsCurve) { 8114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!rh.fIsCurve) { 8124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double leftX = fTangentHalf.dx(); 8134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double leftY = fTangentHalf.dy(); 8144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double rightX = rh.fTangentHalf.dx(); 8154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double rightY = rh.fTangentHalf.dy(); 8164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double x_ry = leftX * rightY; 8174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double rx_y = rightX * leftY; 8184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (x_ry == rx_y) { 8194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (leftX * rightX < 0 || leftY * rightY < 0) { 8204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return true; // exactly 180 degrees apart 8214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 8224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org goto unorderable; 8234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 8244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(x_ry != rx_y); // indicates an undetected coincidence -- worth finding earlier 8254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return x_ry < rx_y; 8264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 8274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if ((result = allOnOneSide(rh)) >= 0) { 8284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return result; 8294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 8304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (fUnorderable || approximately_zero(rh.fSide)) { 8314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org goto unorderable; 8324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 8334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else if (!rh.fIsCurve) { 8344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if ((result = rh.allOnOneSide(*this)) >= 0) { 8354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return !result; 8364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 8374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (rh.fUnorderable || approximately_zero(fSide)) { 8384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org goto unorderable; 8394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 84007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 8414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if ((result = convexHullOverlaps(rh)) >= 0) { 8424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return result; 8434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 8444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return endsIntersect(rh); 8454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgunorderable: 8464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fUnorderable = true; 8474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org rh.fUnorderable = true; 8484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return true; 8494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 8504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 8518cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.orgbool SkOpAngle::overlap(const SkOpAngle& other) const { 8528cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org int min = SkTMin(fStart, fEnd); 8538cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org const SkOpSpan& span = fSegment->span(min); 8548cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org const SkOpSegment* oSeg = other.fSegment; 8558cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org int oMin = SkTMin(other.fStart, other.fEnd); 8568cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org const SkOpSpan& oSpan = oSeg->span(oMin); 8578cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (!span.fSmall && !oSpan.fSmall) { 8588cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org return false; 8598cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 8608cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (fSegment->span(fStart).fPt != oSeg->span(other.fStart).fPt) { 8618cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org return false; 8628cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 8638cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org // see if small span is contained by opposite span 8648cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org return span.fSmall ? oSeg->containsPt(fSegment->span(fEnd).fPt, other.fEnd, other.fStart) 8658cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org : fSegment->containsPt(oSeg->span(other.fEnd).fPt, fEnd, fStart); 8668cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org} 8678cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org 8684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// OPTIMIZE: if this shows up in a profile, add a previous pointer 8694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// as is, this should be rarely called 8704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgSkOpAngle* SkOpAngle::previous() const { 8714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* last = fNext; 8724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 8734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* next = last->fNext; 8744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (next == this) { 8754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return last; 8764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 8774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org last = next; 8784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while (true); 87907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 88007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 881cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.comvoid SkOpAngle::set(const SkOpSegment* segment, int start, int end) { 88207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fSegment = segment; 88307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fStart = start; 884dac1d17027dcaa5596885a9f333979418b35001ccaryclark fComputedEnd = fEnd = end; 8854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fNext = NULL; 8864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fComputeSector = fComputedSector = false; 8874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fStop = false; 88807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com setSpans(); 8894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org setSector(); 8904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 8914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 8924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgvoid SkOpAngle::setCurveHullSweep() { 8934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fUnorderedSweep = false; 8944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSweep[0] = fCurvePart[1] - fCurvePart[0]; 8954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (SkPath::kLine_Verb == fSegment->verb()) { 8964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSweep[1] = fSweep[0]; 8974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 8984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 8994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSweep[1] = fCurvePart[2] - fCurvePart[0]; 9004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (SkPath::kCubic_Verb != fSegment->verb()) { 9014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!fSweep[0].fX && !fSweep[0].fY) { 9024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSweep[0] = fSweep[1]; 9034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 9044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 9054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 9064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDVector thirdSweep = fCurvePart[3] - fCurvePart[0]; 9074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (fSweep[0].fX == 0 && fSweep[0].fY == 0) { 9084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSweep[0] = fSweep[1]; 9094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSweep[1] = thirdSweep; 9104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (fSweep[0].fX == 0 && fSweep[0].fY == 0) { 9114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSweep[0] = fSweep[1]; 9124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fCurvePart[1] = fCurvePart[3]; 9134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fIsCurve = false; 9144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 9154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 9164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 9174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s1x3 = fSweep[0].crossCheck(thirdSweep); 9184431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s3x2 = thirdSweep.crossCheck(fSweep[1]); 9194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (s1x3 * s3x2 >= 0) { // if third vector is on or between first two vectors 9204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 9214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 9224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s2x1 = fSweep[1].crossCheck(fSweep[0]); 9234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // FIXME: If the sweep of the cubic is greater than 180 degrees, we're in trouble 9244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // probably such wide sweeps should be artificially subdivided earlier so that never happens 9254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(s1x3 * s2x1 < 0 || s1x3 * s3x2 < 0); 9264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (s3x2 * s2x1 < 0) { 9274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(s2x1 * s1x3 > 0); 9284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSweep[0] = fSweep[1]; 9294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fUnorderedSweep = true; 9304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 9314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSweep[1] = thirdSweep; 9324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 9334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 9344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgvoid SkOpAngle::setSector() { 9354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkPath::Verb verb = fSegment->verb(); 9364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (SkPath::kLine_Verb != verb && small()) { 9374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSectorStart = fSectorEnd = -1; 9384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSectorMask = 0; 9394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fComputeSector = true; // can't determine sector until segment length can be found 9404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 9414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 9424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSectorStart = findSector(verb, fSweep[0].fX, fSweep[0].fY); 9434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!fIsCurve) { // if it's a line or line-like, note that both sectors are the same 9444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(fSectorStart >= 0); 9454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSectorEnd = fSectorStart; 9464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSectorMask = 1 << fSectorStart; 9474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 9484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 9494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(SkPath::kLine_Verb != verb); 9504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSectorEnd = findSector(verb, fSweep[1].fX, fSweep[1].fY); 9514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (fSectorEnd == fSectorStart) { 9524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT((fSectorStart & 3) != 3); // if the sector has no span, it can't be an exact angle 9534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSectorMask = 1 << fSectorStart; 9544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return; 9554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 9564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool crossesZero = checkCrossesZero(); 9574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int start = SkTMin(fSectorStart, fSectorEnd); 9584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool curveBendsCCW = (fSectorStart == start) ^ crossesZero; 9594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // bump the start and end of the sector span if they are on exact compass points 9604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if ((fSectorStart & 3) == 3) { 9614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSectorStart = (fSectorStart + (curveBendsCCW ? 1 : 31)) & 0x1f; 9624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 9634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if ((fSectorEnd & 3) == 3) { 9644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSectorEnd = (fSectorEnd + (curveBendsCCW ? 31 : 1)) & 0x1f; 9654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 9664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org crossesZero = checkCrossesZero(); 9674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org start = SkTMin(fSectorStart, fSectorEnd); 9684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int end = SkTMax(fSectorStart, fSectorEnd); 9694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!crossesZero) { 9704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSectorMask = (unsigned) -1 >> (31 - end + start) << start; 9714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 9724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSectorMask = (unsigned) -1 >> (31 - start) | (-1 << end); 9734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 97407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 97507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 97607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comvoid SkOpAngle::setSpans() { 977570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com fUnorderable = fSegment->isTiny(this); 978570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com fLastMarked = NULL; 979570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com const SkPoint* pts = fSegment->pts(); 9804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDEBUGCODE(fCurvePart[2].fX = fCurvePart[2].fY = fCurvePart[3].fX = fCurvePart[3].fY 9814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org = SK_ScalarNaN); 9824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSegment->subDivide(fStart, fEnd, &fCurvePart); 9834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org setCurveHullSweep(); 9844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkPath::Verb verb = fSegment->verb(); 9854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (verb != SkPath::kLine_Verb 9864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org && !(fIsCurve = fSweep[0].crossCheck(fSweep[1]) != 0)) { 9874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDLine lineHalf; 9884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org lineHalf[0].set(fCurvePart[0].asSkPoint()); 9894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org lineHalf[1].set(fCurvePart[SkPathOpsVerbToPoints(verb)].asSkPoint()); 9904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fTangentHalf.lineEndPoints(lineHalf); 9914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSide = 0; 9924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 9934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org switch (verb) { 99407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com case SkPath::kLine_Verb: { 995570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkASSERT(fStart != fEnd); 9964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkPoint& cP1 = pts[fStart < fEnd]; 9974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDLine lineHalf; 9984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org lineHalf[0].set(fSegment->span(fStart).fPt); 9994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org lineHalf[1].set(cP1); 10004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fTangentHalf.lineEndPoints(lineHalf); 100107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fSide = 0; 10024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fIsCurve = false; 10034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } return; 100407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com case SkPath::kQuad_Verb: { 10054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkLineParameters tangentPart; 10064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDQuad& quad2 = *SkTCast<SkDQuad*>(&fCurvePart); 10074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org (void) tangentPart.quadEndPoints(quad2); 10084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSide = -tangentPart.pointDistance(fCurvePart[2]); // not normalized -- compare sign only 1009cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } break; 1010cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com case SkPath::kCubic_Verb: { 10114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkLineParameters tangentPart; 10124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org (void) tangentPart.cubicPart(fCurvePart); 10134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fSide = -tangentPart.pointDistance(fCurvePart[3]); 1014b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com double testTs[4]; 1015b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com // OPTIMIZATION: keep inflections precomputed with cubic segment? 1016cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com int testCount = SkDCubic::FindInflections(pts, testTs); 10174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double startT = fSegment->t(fStart); 1018cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double endT = fSegment->t(fEnd); 1019b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com double limitT = endT; 1020b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com int index; 1021b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com for (index = 0; index < testCount; ++index) { 10224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!::between(startT, testTs[index], limitT)) { 1023b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com testTs[index] = -1; 1024b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com } 1025b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com } 1026b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com testTs[testCount++] = startT; 1027b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com testTs[testCount++] = endT; 1028b76d3b677713693137936ff813b92c4be48af173commit-bot@chromium.org SkTQSort<double>(testTs, &testTs[testCount - 1]); 1029b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com double bestSide = 0; 1030b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com int testCases = (testCount << 1) - 1; 1031b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com index = 0; 1032b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com while (testTs[index] < 0) { 1033b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com ++index; 1034b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com } 1035b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com index <<= 1; 1036b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com for (; index < testCases; ++index) { 1037b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com int testIndex = index >> 1; 1038b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com double testT = testTs[testIndex]; 1039b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com if (index & 1) { 1040b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com testT = (testT + testTs[testIndex + 1]) / 2; 1041b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com } 1042b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com // OPTIMIZE: could avoid call for t == startT, endT 1043cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkDPoint pt = dcubic_xy_at_t(pts, testT); 10444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkLineParameters tangentPart; 10454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org tangentPart.cubicEndPoints(fCurvePart); 10464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double testSide = tangentPart.pointDistance(pt); 1047b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com if (fabs(bestSide) < fabs(testSide)) { 1048b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com bestSide = testSide; 1049b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com } 105007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 1051b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com fSide = -bestSide; // compare sign only 105207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } break; 105307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com default: 105407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(0); 105507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 10564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 10574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 10584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgbool SkOpAngle::small() const { 10594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int min = SkMin32(fStart, fEnd); 10604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int max = SkMax32(fStart, fEnd); 10614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org for (int index = min; index < max; ++index) { 10624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkOpSpan& mSpan = fSegment->span(index); 10634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!mSpan.fSmall) { 10644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return false; 10654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1066570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 10674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return true; 1068570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 1069570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 10704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgbool SkOpAngle::tangentsDiverge(const SkOpAngle& rh, double s0xt0) const { 10714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (s0xt0 == 0) { 10724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return false; 10734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 10744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // if the ctrl tangents are not nearly parallel, use them 10754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // solve for opposite direction displacement scale factor == m 10764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x 10774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1] 10784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x) 10794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.x) 10804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x 10814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y) 10824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // m = v1.cross(v2) / v1.dot(v2) 10834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDVector* sweep = fSweep; 10844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org const SkDVector* tweep = rh.fSweep; 10854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double s0dt0 = sweep[0].dot(tweep[0]); 10864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!s0dt0) { 10874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return true; 10884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 10894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(s0dt0 != 0); 10904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double m = s0xt0 / s0dt0; 10914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double sDist = sweep[0].length() * m; 10924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double tDist = tweep[0].length() * m; 10934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool useS = fabs(sDist) < fabs(tDist); 10944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double mFactor = fabs(useS ? distEndRatio(sDist) : rh.distEndRatio(tDist)); 10954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return mFactor < 5000; // empirically found limit 109607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 1097dac1d17027dcaa5596885a9f333979418b35001ccaryclark 1098dac1d17027dcaa5596885a9f333979418b35001ccaryclarkSkOpAngleSet::SkOpAngleSet() 1099dac1d17027dcaa5596885a9f333979418b35001ccaryclark : fAngles(NULL) 1100dac1d17027dcaa5596885a9f333979418b35001ccaryclark#if DEBUG_ANGLE 1101dac1d17027dcaa5596885a9f333979418b35001ccaryclark , fCount(0) 1102dac1d17027dcaa5596885a9f333979418b35001ccaryclark#endif 1103dac1d17027dcaa5596885a9f333979418b35001ccaryclark{ 1104dac1d17027dcaa5596885a9f333979418b35001ccaryclark} 1105dac1d17027dcaa5596885a9f333979418b35001ccaryclark 1106dac1d17027dcaa5596885a9f333979418b35001ccaryclarkSkOpAngleSet::~SkOpAngleSet() { 1107dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkDELETE(fAngles); 1108dac1d17027dcaa5596885a9f333979418b35001ccaryclark} 1109dac1d17027dcaa5596885a9f333979418b35001ccaryclark 1110dac1d17027dcaa5596885a9f333979418b35001ccaryclarkSkOpAngle& SkOpAngleSet::push_back() { 1111dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (!fAngles) { 1112dac1d17027dcaa5596885a9f333979418b35001ccaryclark fAngles = SkNEW_ARGS(SkChunkAlloc, (2)); 1113dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 1114dac1d17027dcaa5596885a9f333979418b35001ccaryclark void* ptr = fAngles->allocThrow(sizeof(SkOpAngle)); 1115dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpAngle* angle = (SkOpAngle*) ptr; 1116dac1d17027dcaa5596885a9f333979418b35001ccaryclark#if DEBUG_ANGLE 1117dac1d17027dcaa5596885a9f333979418b35001ccaryclark angle->setID(++fCount); 1118dac1d17027dcaa5596885a9f333979418b35001ccaryclark#endif 1119dac1d17027dcaa5596885a9f333979418b35001ccaryclark return *angle; 1120dac1d17027dcaa5596885a9f333979418b35001ccaryclark} 1121dac1d17027dcaa5596885a9f333979418b35001ccaryclark 1122dac1d17027dcaa5596885a9f333979418b35001ccaryclarkvoid SkOpAngleSet::reset() { 1123dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (fAngles) { 1124dac1d17027dcaa5596885a9f333979418b35001ccaryclark fAngles->reset(); 1125dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 1126dac1d17027dcaa5596885a9f333979418b35001ccaryclark} 1127