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 "SkIntersections.h" | 7 #include "SkIntersections.h" |
8 #include "SkPathOpsLine.h" | 8 #include "SkPathOpsLine.h" |
9 #include "SkPathOpsQuad.h" | 9 #include "SkPathOpsQuad.h" |
10 | 10 |
(...skipping 87 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
98 , fLine(l) | 98 , fLine(l) |
99 , fIntersections(i) | 99 , fIntersections(i) |
100 , fAllowNear(true) { | 100 , fAllowNear(true) { |
101 i->setMax(3); // allow short partial coincidence plus discrete intersec
tion | 101 i->setMax(3); // allow short partial coincidence plus discrete intersec
tion |
102 } | 102 } |
103 | 103 |
104 void allowNear(bool allow) { | 104 void allowNear(bool allow) { |
105 fAllowNear = allow; | 105 fAllowNear = allow; |
106 } | 106 } |
107 | 107 |
| 108 void checkCoincident() { |
| 109 int last = fIntersections->used() - 1; |
| 110 for (int index = 0; index < last; ) { |
| 111 double quadMidT = ((*fIntersections)[0][index] + (*fIntersections)[0
][index + 1]) / 2; |
| 112 SkDPoint quadMidPt = fQuad.ptAtT(quadMidT); |
| 113 double t = fLine.nearPoint(quadMidPt, NULL); |
| 114 if (t < 0) { |
| 115 ++index; |
| 116 continue; |
| 117 } |
| 118 if (fIntersections->isCoincident(index)) { |
| 119 fIntersections->removeOne(index); |
| 120 --last; |
| 121 } else if (fIntersections->isCoincident(index + 1)) { |
| 122 fIntersections->removeOne(index + 1); |
| 123 --last; |
| 124 } else { |
| 125 fIntersections->setCoincident(index++); |
| 126 } |
| 127 fIntersections->setCoincident(index); |
| 128 } |
| 129 } |
| 130 |
108 int intersectRay(double roots[2]) { | 131 int intersectRay(double roots[2]) { |
109 /* | 132 /* |
110 solve by rotating line+quad so line is horizontal, then finding the root
s | 133 solve by rotating line+quad so line is horizontal, then finding the root
s |
111 set up matrix to rotate quad to x-axis | 134 set up matrix to rotate quad to x-axis |
112 |cos(a) -sin(a)| | 135 |cos(a) -sin(a)| |
113 |sin(a) cos(a)| | 136 |sin(a) cos(a)| |
114 note that cos(a) = A(djacent) / Hypoteneuse | 137 note that cos(a) = A(djacent) / Hypoteneuse |
115 sin(a) = O(pposite) / Hypoteneuse | 138 sin(a) = O(pposite) / Hypoteneuse |
116 since we are computing Ts, we can ignore hypoteneuse, the scale factor: | 139 since we are computing Ts, we can ignore hypoteneuse, the scale factor: |
117 | A -O | | 140 | A -O | |
(...skipping 15 matching lines...) Expand all Loading... |
133 A += C - 2 * B; // A = a - 2*b + c | 156 A += C - 2 * B; // A = a - 2*b + c |
134 B -= C; // B = -(b - c) | 157 B -= C; // B = -(b - c) |
135 return SkDQuad::RootsValidT(A, 2 * B, C, roots); | 158 return SkDQuad::RootsValidT(A, 2 * B, C, roots); |
136 } | 159 } |
137 | 160 |
138 int intersect() { | 161 int intersect() { |
139 addExactEndPoints(); | 162 addExactEndPoints(); |
140 if (fAllowNear) { | 163 if (fAllowNear) { |
141 addNearEndPoints(); | 164 addNearEndPoints(); |
142 } | 165 } |
143 if (fIntersections->used() == 2) { | 166 double rootVals[2]; |
144 // FIXME : need sharable code that turns spans into coincident if mi
ddle point is on | 167 int roots = intersectRay(rootVals); |
145 } else { | 168 for (int index = 0; index < roots; ++index) { |
146 double rootVals[2]; | 169 double quadT = rootVals[index]; |
147 int roots = intersectRay(rootVals); | 170 double lineT = findLineT(quadT); |
148 for (int index = 0; index < roots; ++index) { | 171 SkDPoint pt; |
149 double quadT = rootVals[index]; | 172 if (pinTs(&quadT, &lineT, &pt, kPointUninitialized) && uniqueAnswer(
quadT, pt)) { |
150 double lineT = findLineT(quadT); | 173 fIntersections->insert(quadT, lineT, pt); |
151 SkDPoint pt; | |
152 if (pinTs(&quadT, &lineT, &pt, kPointUninitialized)) { | |
153 fIntersections->insert(quadT, lineT, pt); | |
154 } | |
155 } | 174 } |
156 } | 175 } |
| 176 checkCoincident(); |
157 return fIntersections->used(); | 177 return fIntersections->used(); |
158 } | 178 } |
159 | 179 |
160 int horizontalIntersect(double axisIntercept, double roots[2]) { | 180 int horizontalIntersect(double axisIntercept, double roots[2]) { |
161 double D = fQuad[2].fY; // f | 181 double D = fQuad[2].fY; // f |
162 double E = fQuad[1].fY; // e | 182 double E = fQuad[1].fY; // e |
163 double F = fQuad[0].fY; // d | 183 double F = fQuad[0].fY; // d |
164 D += F - 2 * E; // D = d - 2*e + f | 184 D += F - 2 * E; // D = d - 2*e + f |
165 E -= F; // E = -(d - e) | 185 E -= F; // E = -(d - e) |
166 F -= axisIntercept; | 186 F -= axisIntercept; |
167 return SkDQuad::RootsValidT(D, 2 * E, F, roots); | 187 return SkDQuad::RootsValidT(D, 2 * E, F, roots); |
168 } | 188 } |
169 | 189 |
170 int horizontalIntersect(double axisIntercept, double left, double right, boo
l flipped) { | 190 int horizontalIntersect(double axisIntercept, double left, double right, boo
l flipped) { |
171 addExactHorizontalEndPoints(left, right, axisIntercept); | 191 addExactHorizontalEndPoints(left, right, axisIntercept); |
172 if (fAllowNear) { | 192 if (fAllowNear) { |
173 addNearHorizontalEndPoints(left, right, axisIntercept); | 193 addNearHorizontalEndPoints(left, right, axisIntercept); |
174 } | 194 } |
175 double rootVals[2]; | 195 double rootVals[2]; |
176 int roots = horizontalIntersect(axisIntercept, rootVals); | 196 int roots = horizontalIntersect(axisIntercept, rootVals); |
177 for (int index = 0; index < roots; ++index) { | 197 for (int index = 0; index < roots; ++index) { |
178 double quadT = rootVals[index]; | 198 double quadT = rootVals[index]; |
179 SkDPoint pt = fQuad.ptAtT(quadT); | 199 SkDPoint pt = fQuad.ptAtT(quadT); |
180 double lineT = (pt.fX - left) / (right - left); | 200 double lineT = (pt.fX - left) / (right - left); |
181 if (pinTs(&quadT, &lineT, &pt, kPointInitialized)) { | 201 if (pinTs(&quadT, &lineT, &pt, kPointInitialized) && uniqueAnswer(qu
adT, pt)) { |
182 fIntersections->insert(quadT, lineT, pt); | 202 fIntersections->insert(quadT, lineT, pt); |
183 } | 203 } |
184 } | 204 } |
185 if (flipped) { | 205 if (flipped) { |
186 fIntersections->flip(); | 206 fIntersections->flip(); |
187 } | 207 } |
| 208 checkCoincident(); |
188 return fIntersections->used(); | 209 return fIntersections->used(); |
189 } | 210 } |
190 | 211 |
| 212 bool uniqueAnswer(double quadT, const SkDPoint& pt) { |
| 213 for (int inner = 0; inner < fIntersections->used(); ++inner) { |
| 214 if (fIntersections->pt(inner) != pt) { |
| 215 continue; |
| 216 } |
| 217 double existingQuadT = (*fIntersections)[0][inner]; |
| 218 if (quadT == existingQuadT) { |
| 219 return false; |
| 220 } |
| 221 // check if midway on quad is also same point. If so, discard this |
| 222 double quadMidT = (existingQuadT + quadT) / 2; |
| 223 SkDPoint quadMidPt = fQuad.ptAtT(quadMidT); |
| 224 if (quadMidPt.approximatelyEqual(pt)) { |
| 225 return false; |
| 226 } |
| 227 } |
| 228 #if ONE_OFF_DEBUG |
| 229 SkDPoint qPt = fQuad.ptAtT(quadT); |
| 230 SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX,
pt.fY, |
| 231 qPt.fX, qPt.fY); |
| 232 #endif |
| 233 return true; |
| 234 } |
| 235 |
191 int verticalIntersect(double axisIntercept, double roots[2]) { | 236 int verticalIntersect(double axisIntercept, double roots[2]) { |
192 double D = fQuad[2].fX; // f | 237 double D = fQuad[2].fX; // f |
193 double E = fQuad[1].fX; // e | 238 double E = fQuad[1].fX; // e |
194 double F = fQuad[0].fX; // d | 239 double F = fQuad[0].fX; // d |
195 D += F - 2 * E; // D = d - 2*e + f | 240 D += F - 2 * E; // D = d - 2*e + f |
196 E -= F; // E = -(d - e) | 241 E -= F; // E = -(d - e) |
197 F -= axisIntercept; | 242 F -= axisIntercept; |
198 return SkDQuad::RootsValidT(D, 2 * E, F, roots); | 243 return SkDQuad::RootsValidT(D, 2 * E, F, roots); |
199 } | 244 } |
200 | 245 |
201 int verticalIntersect(double axisIntercept, double top, double bottom, bool
flipped) { | 246 int verticalIntersect(double axisIntercept, double top, double bottom, bool
flipped) { |
202 addExactVerticalEndPoints(top, bottom, axisIntercept); | 247 addExactVerticalEndPoints(top, bottom, axisIntercept); |
203 if (fAllowNear) { | 248 if (fAllowNear) { |
204 addNearVerticalEndPoints(top, bottom, axisIntercept); | 249 addNearVerticalEndPoints(top, bottom, axisIntercept); |
205 } | 250 } |
206 double rootVals[2]; | 251 double rootVals[2]; |
207 int roots = verticalIntersect(axisIntercept, rootVals); | 252 int roots = verticalIntersect(axisIntercept, rootVals); |
208 for (int index = 0; index < roots; ++index) { | 253 for (int index = 0; index < roots; ++index) { |
209 double quadT = rootVals[index]; | 254 double quadT = rootVals[index]; |
210 SkDPoint pt = fQuad.ptAtT(quadT); | 255 SkDPoint pt = fQuad.ptAtT(quadT); |
211 double lineT = (pt.fY - top) / (bottom - top); | 256 double lineT = (pt.fY - top) / (bottom - top); |
212 if (pinTs(&quadT, &lineT, &pt, kPointInitialized)) { | 257 if (pinTs(&quadT, &lineT, &pt, kPointInitialized) && uniqueAnswer(qu
adT, pt)) { |
213 fIntersections->insert(quadT, lineT, pt); | 258 fIntersections->insert(quadT, lineT, pt); |
214 } | 259 } |
215 } | 260 } |
216 if (flipped) { | 261 if (flipped) { |
217 fIntersections->flip(); | 262 fIntersections->flip(); |
218 } | 263 } |
| 264 checkCoincident(); |
219 return fIntersections->used(); | 265 return fIntersections->used(); |
220 } | 266 } |
221 | 267 |
222 protected: | 268 protected: |
223 // add endpoints first to get zero and one t values exactly | 269 // add endpoints first to get zero and one t values exactly |
224 void addExactEndPoints() { | 270 void addExactEndPoints() { |
225 for (int qIndex = 0; qIndex < 3; qIndex += 2) { | 271 for (int qIndex = 0; qIndex < 3; qIndex += 2) { |
226 double lineT = fLine.exactPoint(fQuad[qIndex]); | 272 double lineT = fLine.exactPoint(fQuad[qIndex]); |
227 if (lineT < 0) { | 273 if (lineT < 0) { |
228 continue; | 274 continue; |
(...skipping 143 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
372 } | 418 } |
373 | 419 |
374 int SkIntersections::intersectRay(const SkDQuad& quad, const SkDLine& line) { | 420 int SkIntersections::intersectRay(const SkDQuad& quad, const SkDLine& line) { |
375 LineQuadraticIntersections q(quad, line, this); | 421 LineQuadraticIntersections q(quad, line, this); |
376 fUsed = q.intersectRay(fT[0]); | 422 fUsed = q.intersectRay(fT[0]); |
377 for (int index = 0; index < fUsed; ++index) { | 423 for (int index = 0; index < fUsed; ++index) { |
378 fPt[index] = quad.ptAtT(fT[0][index]); | 424 fPt[index] = quad.ptAtT(fT[0][index]); |
379 } | 425 } |
380 return fUsed; | 426 return fUsed; |
381 } | 427 } |
OLD | NEW |