1 /* 2 * Copyright 2015 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 #include "SkPathOpsBounds.h" 8 #include "SkPathOpsRect.h" 9 #include "SkPathOpsCurve.h" 10 11 // this cheats and assumes that the perpendicular to the point is the closest ray to the curve 12 // this case (where the line and the curve are nearly coincident) may be the only case that counts 13 double SkDCurve::nearPoint(SkPath::Verb verb, const SkDPoint& xy, const SkDPoint& opp) const { 14 int count = SkPathOpsVerbToPoints(verb); 15 double minX = fCubic.fPts[0].fX; 16 double maxX = minX; 17 for (int index = 1; index <= count; ++index) { 18 minX = SkTMin(minX, fCubic.fPts[index].fX); 19 maxX = SkTMax(maxX, fCubic.fPts[index].fX); 20 } 21 if (!AlmostBetweenUlps(minX, xy.fX, maxX)) { 22 return -1; 23 } 24 double minY = fCubic.fPts[0].fY; 25 double maxY = minY; 26 for (int index = 1; index <= count; ++index) { 27 minY = SkTMin(minY, fCubic.fPts[index].fY); 28 maxY = SkTMax(maxY, fCubic.fPts[index].fY); 29 } 30 if (!AlmostBetweenUlps(minY, xy.fY, maxY)) { 31 return -1; 32 } 33 SkIntersections i; 34 SkDLine perp = {{ xy, { xy.fX + opp.fY - xy.fY, xy.fY + xy.fX - opp.fX }}}; 35 (*CurveDIntersectRay[verb])(*this, perp, &i); 36 int minIndex = -1; 37 double minDist = FLT_MAX; 38 for (int index = 0; index < i.used(); ++index) { 39 double dist = xy.distance(i.pt(index)); 40 if (minDist > dist) { 41 minDist = dist; 42 minIndex = index; 43 } 44 } 45 if (minIndex < 0) { 46 return -1; 47 } 48 double largest = SkTMax(SkTMax(maxX, maxY), -SkTMin(minX, minY)); 49 if (!AlmostEqualUlps_Pin(largest, largest + minDist)) { // is distance within ULPS tolerance? 50 return -1; 51 } 52 return SkPinT(i[0][minIndex]); 53 } 54 55 void SkDCurve::offset(SkPath::Verb verb, const SkDVector& off) { 56 int count = SkPathOpsVerbToPoints(verb); 57 for (int index = 0; index <= count; ++index) { 58 fCubic.fPts[index] += off; 59 } 60 } 61 62 void SkDCurve::setConicBounds(const SkPoint curve[3], SkScalar curveWeight, 63 double tStart, double tEnd, SkPathOpsBounds* bounds) { 64 SkDConic dCurve; 65 dCurve.set(curve, curveWeight); 66 SkDRect dRect; 67 dRect.setBounds(dCurve, fConic, tStart, tEnd); 68 bounds->set(SkDoubleToScalar(dRect.fLeft), SkDoubleToScalar(dRect.fTop), 69 SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom)); 70 } 71 72 void SkDCurve::setCubicBounds(const SkPoint curve[4], SkScalar , 73 double tStart, double tEnd, SkPathOpsBounds* bounds) { 74 SkDCubic dCurve; 75 dCurve.set(curve); 76 SkDRect dRect; 77 dRect.setBounds(dCurve, fCubic, tStart, tEnd); 78 bounds->set(SkDoubleToScalar(dRect.fLeft), SkDoubleToScalar(dRect.fTop), 79 SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom)); 80 } 81 82 void SkDCurve::setQuadBounds(const SkPoint curve[3], SkScalar , 83 double tStart, double tEnd, SkPathOpsBounds* bounds) { 84 SkDQuad dCurve; 85 dCurve.set(curve); 86 SkDRect dRect; 87 dRect.setBounds(dCurve, fQuad, tStart, tEnd); 88 bounds->set(SkDoubleToScalar(dRect.fLeft), SkDoubleToScalar(dRect.fTop), 89 SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom)); 90 } 91 92 void SkDCurveSweep::setCurveHullSweep(SkPath::Verb verb) { 93 fOrdered = true; 94 fSweep[0] = fCurve[1] - fCurve[0]; 95 if (SkPath::kLine_Verb == verb) { 96 fSweep[1] = fSweep[0]; 97 fIsCurve = false; 98 return; 99 } 100 fSweep[1] = fCurve[2] - fCurve[0]; 101 // OPTIMIZE: I do the following float check a lot -- probably need a 102 // central place for this val-is-small-compared-to-curve check 103 double maxVal = 0; 104 for (int index = 0; index <= SkPathOpsVerbToPoints(verb); ++index) { 105 maxVal = SkTMax(maxVal, SkTMax(SkTAbs(fCurve[index].fX), 106 SkTAbs(fCurve[index].fY))); 107 } 108 { 109 if (SkPath::kCubic_Verb != verb) { 110 if (roughly_zero_when_compared_to(fSweep[0].fX, maxVal) 111 && roughly_zero_when_compared_to(fSweep[0].fY, maxVal)) { 112 fSweep[0] = fSweep[1]; 113 } 114 goto setIsCurve; 115 } 116 SkDVector thirdSweep = fCurve[3] - fCurve[0]; 117 if (fSweep[0].fX == 0 && fSweep[0].fY == 0) { 118 fSweep[0] = fSweep[1]; 119 fSweep[1] = thirdSweep; 120 if (roughly_zero_when_compared_to(fSweep[0].fX, maxVal) 121 && roughly_zero_when_compared_to(fSweep[0].fY, maxVal)) { 122 fSweep[0] = fSweep[1]; 123 fCurve[1] = fCurve[3]; 124 } 125 goto setIsCurve; 126 } 127 double s1x3 = fSweep[0].crossCheck(thirdSweep); 128 double s3x2 = thirdSweep.crossCheck(fSweep[1]); 129 if (s1x3 * s3x2 >= 0) { // if third vector is on or between first two vectors 130 goto setIsCurve; 131 } 132 double s2x1 = fSweep[1].crossCheck(fSweep[0]); 133 // FIXME: If the sweep of the cubic is greater than 180 degrees, we're in trouble 134 // probably such wide sweeps should be artificially subdivided earlier so that never happens 135 SkASSERT(s1x3 * s2x1 < 0 || s1x3 * s3x2 < 0); 136 if (s3x2 * s2x1 < 0) { 137 SkASSERT(s2x1 * s1x3 > 0); 138 fSweep[0] = fSweep[1]; 139 fOrdered = false; 140 } 141 fSweep[1] = thirdSweep; 142 } 143 setIsCurve: 144 fIsCurve = fSweep[0].crossCheck(fSweep[1]) != 0; 145 } 146
