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 "src/pathops/SkPathOpsLine.h"
8
ptAtT(double t) const9 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
exactPoint(const SkDPoint & xy) const21 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
nearPoint(const SkDPoint & xy,bool * unequal) const31 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
nearRay(const SkDPoint & xy) const65 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
ExactPointH(const SkDPoint & xy,double left,double right,double y)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
NearPointH(const SkDPoint & xy,double left,double right,double y)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
ExactPointV(const SkDPoint & xy,double top,double bottom,double x)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
NearPointV(const SkDPoint & xy,double top,double bottom,double x)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