• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
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