1 /* 2 * Copyright 2012 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 "SkPathOpsLine.h" 8 9 SkDPoint SkDLine::ptAtT(double t) const { 10 if (0 == t) { 11 return fPts[0]; 12 } 13 if (1 == t) { 14 return fPts[1]; 15 } 16 double one_t = 1 - t; 17 SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY + t * fPts[1].fY }; 18 return result; 19 } 20 21 double SkDLine::exactPoint(const SkDPoint& xy) const { 22 if (xy == fPts[0]) { // do cheapest test first 23 return 0; 24 } 25 if (xy == fPts[1]) { 26 return 1; 27 } 28 return -1; 29 } 30 31 double SkDLine::nearPoint(const SkDPoint& xy, bool* unequal) const { 32 if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX) 33 || !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) { 34 return -1; 35 } 36 // project a perpendicular ray from the point to the line; find the T on the line 37 SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line 38 double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay 39 SkDVector ab0 = xy - fPts[0]; 40 double numer = len.fX * ab0.fX + ab0.fY * len.fY; 41 if (!between(0, numer, denom)) { 42 return -1; 43 } 44 if (!denom) { 45 return 0; 46 } 47 double t = numer / denom; 48 SkDPoint realPt = ptAtT(t); 49 double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ? 50 // find the ordinal in the original line with the largest unsigned exponent 51 double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 52 double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 53 largest = SkTMax(largest, -tiniest); 54 if (!AlmostEqualUlps_Pin(largest, largest + dist)) { // is the dist within ULPS tolerance? 55 return -1; 56 } 57 if (unequal) { 58 *unequal = (float) largest != (float) (largest + dist); 59 } 60 t = SkPinT(t); // a looser pin breaks skpwww_lptemp_com_3 61 SkASSERT(between(0, t, 1)); 62 return t; 63 } 64 65 bool SkDLine::nearRay(const SkDPoint& xy) const { 66 // project a perpendicular ray from the point to the line; find the T on the line 67 SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line 68 double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay 69 SkDVector ab0 = xy - fPts[0]; 70 double numer = len.fX * ab0.fX + ab0.fY * len.fY; 71 double t = numer / denom; 72 SkDPoint realPt = ptAtT(t); 73 double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ? 74 // find the ordinal in the original line with the largest unsigned exponent 75 double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 76 double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 77 largest = SkTMax(largest, -tiniest); 78 return RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance? 79 } 80 81 double SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) { 82 if (xy.fY == y) { 83 if (xy.fX == left) { 84 return 0; 85 } 86 if (xy.fX == right) { 87 return 1; 88 } 89 } 90 return -1; 91 } 92 93 double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) { 94 if (!AlmostBequalUlps(xy.fY, y)) { 95 return -1; 96 } 97 if (!AlmostBetweenUlps(left, xy.fX, right)) { 98 return -1; 99 } 100 double t = (xy.fX - left) / (right - left); 101 t = SkPinT(t); 102 SkASSERT(between(0, t, 1)); 103 double realPtX = (1 - t) * left + t * right; 104 SkDVector distU = {xy.fY - y, xy.fX - realPtX}; 105 double distSq = distU.fX * distU.fX + distU.fY * distU.fY; 106 double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ? 107 double tiniest = SkTMin(SkTMin(y, left), right); 108 double largest = SkTMax(SkTMax(y, left), right); 109 largest = SkTMax(largest, -tiniest); 110 if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? 111 return -1; 112 } 113 return t; 114 } 115 116 double SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, double x) { 117 if (xy.fX == x) { 118 if (xy.fY == top) { 119 return 0; 120 } 121 if (xy.fY == bottom) { 122 return 1; 123 } 124 } 125 return -1; 126 } 127 128 double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) { 129 if (!AlmostBequalUlps(xy.fX, x)) { 130 return -1; 131 } 132 if (!AlmostBetweenUlps(top, xy.fY, bottom)) { 133 return -1; 134 } 135 double t = (xy.fY - top) / (bottom - top); 136 t = SkPinT(t); 137 SkASSERT(between(0, t, 1)); 138 double realPtY = (1 - t) * top + t * bottom; 139 SkDVector distU = {xy.fX - x, xy.fY - realPtY}; 140 double distSq = distU.fX * distU.fX + distU.fY * distU.fY; 141 double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ? 142 double tiniest = SkTMin(SkTMin(x, top), bottom); 143 double largest = SkTMax(SkTMax(x, top), bottom); 144 largest = SkTMax(largest, -tiniest); 145 if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? 146 return -1; 147 } 148 return t; 149 } 150
