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 "SkPathOpsCubic.h" | 7 #include "SkPathOpsCubic.h" |
8 #include "SkPathOpsLine.h" | 8 #include "SkPathOpsLine.h" |
9 #include "SkPathOpsQuad.h" | 9 #include "SkPathOpsQuad.h" |
10 | 10 |
11 // Sources | 11 // Sources |
12 // computer-aided design - volume 22 number 9 november 1990 pp 538 - 549 | 12 // computer-aided design - volume 22 number 9 november 1990 pp 538 - 549 |
13 // online at http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf | 13 // online at http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf |
14 | 14 |
15 // This turns a line segment into a parameterized line, of the form | 15 // This turns a line segment into a parameterized line, of the form |
16 // ax + by + c = 0 | 16 // ax + by + c = 0 |
17 // When a^2 + b^2 == 1, the line is normalized. | 17 // When a^2 + b^2 == 1, the line is normalized. |
18 // The distance to the line for (x, y) is d(x,y) = ax + by + c | 18 // The distance to the line for (x, y) is d(x,y) = ax + by + c |
19 // | 19 // |
20 // Note that the distances below are not necessarily normalized. To get the true | 20 // Note that the distances below are not necessarily normalized. To get the true |
21 // distance, it's necessary to either call normalize() after xxxEndPoints(), or | 21 // distance, it's necessary to either call normalize() after xxxEndPoints(), or |
22 // divide the result of xxxDistance() by sqrt(normalSquared()) | 22 // divide the result of xxxDistance() by sqrt(normalSquared()) |
23 | 23 |
24 class SkLineParameters { | 24 class SkLineParameters { |
25 public: | 25 public: |
| 26 |
26 void cubicEndPoints(const SkDCubic& pts) { | 27 void cubicEndPoints(const SkDCubic& pts) { |
27 cubicEndPoints(pts, 0, 1); | 28 int endIndex = 1; |
28 if (dx() == 0 && dy() == 0) { | 29 cubicEndPoints(pts, 0, endIndex); |
29 cubicEndPoints(pts, 0, 2); | 30 if (dy() != 0) { |
30 if (dx() == 0 && dy() == 0) { | 31 return; |
31 cubicEndPoints(pts, 0, 3); | 32 } |
| 33 if (dx() == 0) { |
| 34 cubicEndPoints(pts, 0, ++endIndex); |
| 35 SkASSERT(endIndex == 2); |
| 36 if (dy() != 0) { |
| 37 return; |
32 } | 38 } |
| 39 if (dx() == 0) { |
| 40 cubicEndPoints(pts, 0, ++endIndex); // line |
| 41 SkASSERT(endIndex == 3); |
| 42 return; |
| 43 } |
| 44 } |
| 45 if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie |
| 46 return; |
| 47 } |
| 48 // if cubic tangent is on x axis, look at next control point to break ti
e |
| 49 // control point may be approximate, so it must move significantly to ac
count for error |
| 50 if (NotAlmostEqualUlps(pts[0].fY, pts[++endIndex].fY)) { |
| 51 if (pts[0].fY > pts[endIndex].fY) { |
| 52 a = DBL_EPSILON; // push it from 0 to slightly negative (y() ret
urns -a) |
| 53 } |
| 54 return; |
| 55 } |
| 56 if (endIndex == 3) { |
| 57 return; |
| 58 } |
| 59 SkASSERT(endIndex == 2); |
| 60 if (pts[0].fY > pts[3].fY) { |
| 61 a = DBL_EPSILON; // push it from 0 to slightly negative (y() returns
-a) |
33 } | 62 } |
34 } | 63 } |
35 | 64 |
36 void cubicEndPoints(const SkDCubic& pts, int s, int e) { | 65 void cubicEndPoints(const SkDCubic& pts, int s, int e) { |
37 a = pts[s].fY - pts[e].fY; | 66 a = pts[s].fY - pts[e].fY; |
38 b = pts[e].fX - pts[s].fX; | 67 b = pts[e].fX - pts[s].fX; |
39 c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; | 68 c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; |
40 } | 69 } |
41 | 70 |
42 double cubicPart(const SkDCubic& part) { | 71 double cubicPart(const SkDCubic& part) { |
43 cubicEndPoints(part); | 72 cubicEndPoints(part); |
44 if (part[0] == part[1] || ((const SkDLine& ) part[0]).nearRay(part[2]))
{ | 73 if (part[0] == part[1] || ((const SkDLine& ) part[0]).nearRay(part[2]))
{ |
45 return pointDistance(part[3]); | 74 return pointDistance(part[3]); |
46 } | 75 } |
47 return pointDistance(part[2]); | 76 return pointDistance(part[2]); |
48 } | 77 } |
49 | 78 |
50 void lineEndPoints(const SkDLine& pts) { | 79 void lineEndPoints(const SkDLine& pts) { |
51 a = pts[0].fY - pts[1].fY; | 80 a = pts[0].fY - pts[1].fY; |
52 b = pts[1].fX - pts[0].fX; | 81 b = pts[1].fX - pts[0].fX; |
53 c = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY; | 82 c = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY; |
54 } | 83 } |
55 | 84 |
56 void quadEndPoints(const SkDQuad& pts) { | 85 void quadEndPoints(const SkDQuad& pts) { |
57 quadEndPoints(pts, 0, 1); | 86 quadEndPoints(pts, 0, 1); |
58 if (dx() == 0 && dy() == 0) { | 87 if (dy() != 0) { |
| 88 return; |
| 89 } |
| 90 if (dx() == 0) { |
59 quadEndPoints(pts, 0, 2); | 91 quadEndPoints(pts, 0, 2); |
| 92 return; |
| 93 } |
| 94 if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie |
| 95 return; |
| 96 } |
| 97 if (pts[0].fY > pts[2].fY) { |
| 98 a = DBL_EPSILON; |
60 } | 99 } |
61 } | 100 } |
62 | 101 |
63 void quadEndPoints(const SkDQuad& pts, int s, int e) { | 102 void quadEndPoints(const SkDQuad& pts, int s, int e) { |
64 a = pts[s].fY - pts[e].fY; | 103 a = pts[s].fY - pts[e].fY; |
65 b = pts[e].fX - pts[s].fX; | 104 b = pts[e].fX - pts[s].fX; |
66 c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; | 105 c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; |
67 } | 106 } |
68 | 107 |
69 double quadPart(const SkDQuad& part) { | 108 double quadPart(const SkDQuad& part) { |
(...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
123 | 162 |
124 double dy() const { | 163 double dy() const { |
125 return -a; | 164 return -a; |
126 } | 165 } |
127 | 166 |
128 private: | 167 private: |
129 double a; | 168 double a; |
130 double b; | 169 double b; |
131 double c; | 170 double c; |
132 }; | 171 }; |
OLD | NEW |