OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2012 Google Inc. | 2 * Copyright 2012 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 #include "SkPathOpsLine.h" | 7 #include "SkPathOpsLine.h" |
8 | 8 |
9 SkDLine SkDLine::subDivide(double t1, double t2) const { | 9 SkDLine SkDLine::subDivide(double t1, double t2) const { |
10 SkDVector delta = tangent(); | 10 SkDVector delta = tangent(); |
(...skipping 23 matching lines...) Expand all Loading... |
34 // =0 for P2 on the line | 34 // =0 for P2 on the line |
35 // <0 for P2 right of the line | 35 // <0 for P2 right of the line |
36 // See: the January 2001 Algorithm on Area of Triangles | 36 // See: the January 2001 Algorithm on Area of Triangles |
37 // return (float) ((P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y))
; | 37 // return (float) ((P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y))
; |
38 double SkDLine::isLeft(const SkDPoint& pt) const { | 38 double SkDLine::isLeft(const SkDPoint& pt) const { |
39 SkDVector p0 = fPts[1] - fPts[0]; | 39 SkDVector p0 = fPts[1] - fPts[0]; |
40 SkDVector p2 = pt - fPts[0]; | 40 SkDVector p2 = pt - fPts[0]; |
41 return p0.cross(p2); | 41 return p0.cross(p2); |
42 } | 42 } |
43 | 43 |
44 // OPTIMIZE: assert if t is 0 or 1 (caller shouldn't pass only 0/1) | 44 SkDPoint SkDLine::ptAtT(double t) const { |
45 SkDPoint SkDLine::xyAtT(double t) const { | 45 if (t == 0) { |
| 46 return fPts[0]; |
| 47 } |
| 48 if (t == 1) { |
| 49 return fPts[1]; |
| 50 } |
46 double one_t = 1 - t; | 51 double one_t = 1 - t; |
47 SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY
+ t * fPts[1].fY }; | 52 SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY
+ t * fPts[1].fY }; |
48 return result; | 53 return result; |
49 } | 54 } |
50 | 55 |
51 double SkDLine::exactPoint(const SkDPoint& xy) const { | 56 double SkDLine::exactPoint(const SkDPoint& xy) const { |
52 if (xy == fPts[0]) { // do cheapest test first | 57 if (xy == fPts[0]) { // do cheapest test first |
53 return 0; | 58 return 0; |
54 } | 59 } |
55 if (xy == fPts[1]) { | 60 if (xy == fPts[1]) { |
56 return 1; | 61 return 1; |
57 } | 62 } |
58 return -1; | 63 return -1; |
59 } | 64 } |
60 | 65 |
61 double SkDLine::nearPoint(const SkDPoint& xy) const { | 66 double SkDLine::nearPoint(const SkDPoint& xy) const { |
62 if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX) | 67 if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX) |
63 || !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) { | 68 || !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) { |
64 return -1; | 69 return -1; |
65 } | 70 } |
66 // project a perpendicular ray from the point to the line; find the T on the
line | 71 // 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 | 72 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 | 73 double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay |
69 SkDVector ab0 = xy - fPts[0]; | 74 SkDVector ab0 = xy - fPts[0]; |
70 double numer = len.fX * ab0.fX + ab0.fY * len.fY; | 75 double numer = len.fX * ab0.fX + ab0.fY * len.fY; |
71 if (!between(0, numer, denom)) { | 76 if (!between(0, numer, denom)) { |
72 return -1; | 77 return -1; |
73 } | 78 } |
74 double t = numer / denom; | 79 double t = numer / denom; |
75 SkDPoint realPt = xyAtT(t); | 80 SkDPoint realPt = ptAtT(t); |
76 SkDVector distU = xy - realPt; | 81 SkDVector distU = xy - realPt; |
77 double distSq = distU.fX * distU.fX + distU.fY * distU.fY; | 82 double distSq = distU.fX * distU.fX + distU.fY * distU.fY; |
78 double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq i
nstead ? | 83 double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq i
nstead ? |
79 // find the ordinal in the original line with the largest unsigned exponent | 84 // find the ordinal in the original line with the largest unsigned exponent |
80 double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX),
fPts[1].fY); | 85 double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX),
fPts[1].fY); |
81 double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX),
fPts[1].fY); | 86 double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX),
fPts[1].fY); |
82 largest = SkTMax(largest, -tiniest); | 87 largest = SkTMax(largest, -tiniest); |
83 if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS
tolerance? | 88 if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS
tolerance? |
84 return -1; | 89 return -1; |
85 } | 90 } |
(...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
130 return -1; | 135 return -1; |
131 } | 136 } |
132 if (!AlmostBetweenUlps(top, xy.fY, bottom)) { | 137 if (!AlmostBetweenUlps(top, xy.fY, bottom)) { |
133 return -1; | 138 return -1; |
134 } | 139 } |
135 double t = (xy.fY - top) / (bottom - top); | 140 double t = (xy.fY - top) / (bottom - top); |
136 t = SkPinT(t); | 141 t = SkPinT(t); |
137 SkASSERT(between(0, t, 1)); | 142 SkASSERT(between(0, t, 1)); |
138 return t; | 143 return t; |
139 } | 144 } |
OLD | NEW |