1 /*
2 * Copyright 2015 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 "include/core/SkPath.h"
8 #include "include/core/SkPoint.h"
9 #include "include/core/SkScalar.h"
10 #include "include/core/SkTypes.h"
11 #include "include/private/base/SkDebug.h"
12 #include "src/pathops/SkIntersections.h"
13 #include "src/pathops/SkPathOpsConic.h"
14 #include "src/pathops/SkPathOpsCurve.h"
15 #include "src/pathops/SkPathOpsDebug.h"
16 #include "src/pathops/SkPathOpsLine.h"
17 #include "src/pathops/SkPathOpsPoint.h"
18 #include "src/pathops/SkPathOpsQuad.h"
19 #include "src/pathops/SkPathOpsTypes.h"
20
21 #include <algorithm>
22 #include <cmath>
23
24 class LineConicIntersections {
25 public:
26 enum PinTPoint {
27 kPointUninitialized,
28 kPointInitialized
29 };
30
LineConicIntersections(const SkDConic & c,const SkDLine & l,SkIntersections * i)31 LineConicIntersections(const SkDConic& c, const SkDLine& l, SkIntersections* i)
32 : fConic(c)
33 , fLine(&l)
34 , fIntersections(i)
35 , fAllowNear(true) {
36 i->setMax(4); // allow short partial coincidence plus discrete intersection
37 }
38
LineConicIntersections(const SkDConic & c)39 LineConicIntersections(const SkDConic& c)
40 : fConic(c)
41 SkDEBUGPARAMS(fLine(nullptr))
42 SkDEBUGPARAMS(fIntersections(nullptr))
43 SkDEBUGPARAMS(fAllowNear(false)) {
44 }
45
allowNear(bool allow)46 void allowNear(bool allow) {
47 fAllowNear = allow;
48 }
49
checkCoincident()50 void checkCoincident() {
51 int last = fIntersections->used() - 1;
52 for (int index = 0; index < last; ) {
53 double conicMidT = ((*fIntersections)[0][index] + (*fIntersections)[0][index + 1]) / 2;
54 SkDPoint conicMidPt = fConic.ptAtT(conicMidT);
55 double t = fLine->nearPoint(conicMidPt, nullptr);
56 if (t < 0) {
57 ++index;
58 continue;
59 }
60 if (fIntersections->isCoincident(index)) {
61 fIntersections->removeOne(index);
62 --last;
63 } else if (fIntersections->isCoincident(index + 1)) {
64 fIntersections->removeOne(index + 1);
65 --last;
66 } else {
67 fIntersections->setCoincident(index++);
68 }
69 fIntersections->setCoincident(index);
70 }
71 }
72
73 #ifdef SK_DEBUG
close_to(double a,double b,const double c[3])74 static bool close_to(double a, double b, const double c[3]) {
75 double max = std::max(-std::min(std::min(c[0], c[1]), c[2]), std::max(std::max(c[0], c[1]), c[2]));
76 return approximately_zero_when_compared_to(a - b, max);
77 }
78 #endif
horizontalIntersect(double axisIntercept,double roots[2])79 int horizontalIntersect(double axisIntercept, double roots[2]) {
80 double conicVals[] = { fConic[0].fY, fConic[1].fY, fConic[2].fY };
81 return this->validT(conicVals, axisIntercept, roots);
82 }
83
horizontalIntersect(double axisIntercept,double left,double right,bool flipped)84 int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) {
85 this->addExactHorizontalEndPoints(left, right, axisIntercept);
86 if (fAllowNear) {
87 this->addNearHorizontalEndPoints(left, right, axisIntercept);
88 }
89 double roots[2];
90 int count = this->horizontalIntersect(axisIntercept, roots);
91 for (int index = 0; index < count; ++index) {
92 double conicT = roots[index];
93 SkDPoint pt = fConic.ptAtT(conicT);
94 SkDEBUGCODE(double conicVals[] = { fConic[0].fY, fConic[1].fY, fConic[2].fY });
95 SkOPOBJASSERT(fIntersections, close_to(pt.fY, axisIntercept, conicVals));
96 double lineT = (pt.fX - left) / (right - left);
97 if (this->pinTs(&conicT, &lineT, &pt, kPointInitialized)
98 && this->uniqueAnswer(conicT, pt)) {
99 fIntersections->insert(conicT, lineT, pt);
100 }
101 }
102 if (flipped) {
103 fIntersections->flip();
104 }
105 this->checkCoincident();
106 return fIntersections->used();
107 }
108
intersect()109 int intersect() {
110 this->addExactEndPoints();
111 if (fAllowNear) {
112 this->addNearEndPoints();
113 }
114 double rootVals[2];
115 int roots = this->intersectRay(rootVals);
116 for (int index = 0; index < roots; ++index) {
117 double conicT = rootVals[index];
118 double lineT = this->findLineT(conicT);
119 #ifdef SK_DEBUG
120 if (!fIntersections->globalState()
121 || !fIntersections->globalState()->debugSkipAssert()) {
122 SkDEBUGCODE(SkDPoint conicPt = fConic.ptAtT(conicT));
123 SkDEBUGCODE(SkDPoint linePt = fLine->ptAtT(lineT));
124 SkASSERT(conicPt.approximatelyDEqual(linePt));
125 }
126 #endif
127 SkDPoint pt;
128 if (this->pinTs(&conicT, &lineT, &pt, kPointUninitialized)
129 && this->uniqueAnswer(conicT, pt)) {
130 fIntersections->insert(conicT, lineT, pt);
131 }
132 }
133 this->checkCoincident();
134 return fIntersections->used();
135 }
136
intersectRay(double roots[2])137 int intersectRay(double roots[2]) {
138 double adj = (*fLine)[1].fX - (*fLine)[0].fX;
139 double opp = (*fLine)[1].fY - (*fLine)[0].fY;
140 double r[3];
141 for (int n = 0; n < 3; ++n) {
142 r[n] = (fConic[n].fY - (*fLine)[0].fY) * adj - (fConic[n].fX - (*fLine)[0].fX) * opp;
143 }
144 return this->validT(r, 0, roots);
145 }
146
validT(double r[3],double axisIntercept,double roots[2])147 int validT(double r[3], double axisIntercept, double roots[2]) {
148 double A = r[2];
149 double B = r[1] * fConic.fWeight - axisIntercept * fConic.fWeight + axisIntercept;
150 double C = r[0];
151 A += C - 2 * B; // A = a + c - 2*(b*w - xCept*w + xCept)
152 B -= C; // B = b*w - w * xCept + xCept - a
153 C -= axisIntercept;
154 return SkDQuad::RootsValidT(A, 2 * B, C, roots);
155 }
156
verticalIntersect(double axisIntercept,double roots[2])157 int verticalIntersect(double axisIntercept, double roots[2]) {
158 double conicVals[] = { fConic[0].fX, fConic[1].fX, fConic[2].fX };
159 return this->validT(conicVals, axisIntercept, roots);
160 }
161
verticalIntersect(double axisIntercept,double top,double bottom,bool flipped)162 int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) {
163 this->addExactVerticalEndPoints(top, bottom, axisIntercept);
164 if (fAllowNear) {
165 this->addNearVerticalEndPoints(top, bottom, axisIntercept);
166 }
167 double roots[2];
168 int count = this->verticalIntersect(axisIntercept, roots);
169 for (int index = 0; index < count; ++index) {
170 double conicT = roots[index];
171 SkDPoint pt = fConic.ptAtT(conicT);
172 SkDEBUGCODE(double conicVals[] = { fConic[0].fX, fConic[1].fX, fConic[2].fX });
173 SkOPOBJASSERT(fIntersections, close_to(pt.fX, axisIntercept, conicVals));
174 double lineT = (pt.fY - top) / (bottom - top);
175 if (this->pinTs(&conicT, &lineT, &pt, kPointInitialized)
176 && this->uniqueAnswer(conicT, pt)) {
177 fIntersections->insert(conicT, lineT, pt);
178 }
179 }
180 if (flipped) {
181 fIntersections->flip();
182 }
183 this->checkCoincident();
184 return fIntersections->used();
185 }
186
187 protected:
188 // OPTIMIZE: Functions of the form add .. points are indentical to the conic routines.
189 // add endpoints first to get zero and one t values exactly
addExactEndPoints()190 void addExactEndPoints() {
191 for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
192 double lineT = fLine->exactPoint(fConic[cIndex]);
193 if (lineT < 0) {
194 continue;
195 }
196 double conicT = (double) (cIndex >> 1);
197 fIntersections->insert(conicT, lineT, fConic[cIndex]);
198 }
199 }
200
addNearEndPoints()201 void addNearEndPoints() {
202 for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
203 double conicT = (double) (cIndex >> 1);
204 if (fIntersections->hasT(conicT)) {
205 continue;
206 }
207 double lineT = fLine->nearPoint(fConic[cIndex], nullptr);
208 if (lineT < 0) {
209 continue;
210 }
211 fIntersections->insert(conicT, lineT, fConic[cIndex]);
212 }
213 this->addLineNearEndPoints();
214 }
215
addLineNearEndPoints()216 void addLineNearEndPoints() {
217 for (int lIndex = 0; lIndex < 2; ++lIndex) {
218 double lineT = (double) lIndex;
219 if (fIntersections->hasOppT(lineT)) {
220 continue;
221 }
222 double conicT = ((const SkDCurve*) &fConic)->nearPoint(SkPath::kConic_Verb,
223 (*fLine)[lIndex], (*fLine)[!lIndex]);
224 if (conicT < 0) {
225 continue;
226 }
227 fIntersections->insert(conicT, lineT, (*fLine)[lIndex]);
228 }
229 }
230
addExactHorizontalEndPoints(double left,double right,double y)231 void addExactHorizontalEndPoints(double left, double right, double y) {
232 for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
233 double lineT = SkDLine::ExactPointH(fConic[cIndex], left, right, y);
234 if (lineT < 0) {
235 continue;
236 }
237 double conicT = (double) (cIndex >> 1);
238 fIntersections->insert(conicT, lineT, fConic[cIndex]);
239 }
240 }
241
addNearHorizontalEndPoints(double left,double right,double y)242 void addNearHorizontalEndPoints(double left, double right, double y) {
243 for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
244 double conicT = (double) (cIndex >> 1);
245 if (fIntersections->hasT(conicT)) {
246 continue;
247 }
248 double lineT = SkDLine::NearPointH(fConic[cIndex], left, right, y);
249 if (lineT < 0) {
250 continue;
251 }
252 fIntersections->insert(conicT, lineT, fConic[cIndex]);
253 }
254 this->addLineNearEndPoints();
255 }
256
addExactVerticalEndPoints(double top,double bottom,double x)257 void addExactVerticalEndPoints(double top, double bottom, double x) {
258 for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
259 double lineT = SkDLine::ExactPointV(fConic[cIndex], top, bottom, x);
260 if (lineT < 0) {
261 continue;
262 }
263 double conicT = (double) (cIndex >> 1);
264 fIntersections->insert(conicT, lineT, fConic[cIndex]);
265 }
266 }
267
addNearVerticalEndPoints(double top,double bottom,double x)268 void addNearVerticalEndPoints(double top, double bottom, double x) {
269 for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
270 double conicT = (double) (cIndex >> 1);
271 if (fIntersections->hasT(conicT)) {
272 continue;
273 }
274 double lineT = SkDLine::NearPointV(fConic[cIndex], top, bottom, x);
275 if (lineT < 0) {
276 continue;
277 }
278 fIntersections->insert(conicT, lineT, fConic[cIndex]);
279 }
280 this->addLineNearEndPoints();
281 }
282
findLineT(double t)283 double findLineT(double t) {
284 SkDPoint xy = fConic.ptAtT(t);
285 double dx = (*fLine)[1].fX - (*fLine)[0].fX;
286 double dy = (*fLine)[1].fY - (*fLine)[0].fY;
287 if (fabs(dx) > fabs(dy)) {
288 return (xy.fX - (*fLine)[0].fX) / dx;
289 }
290 return (xy.fY - (*fLine)[0].fY) / dy;
291 }
292
pinTs(double * conicT,double * lineT,SkDPoint * pt,PinTPoint ptSet)293 bool pinTs(double* conicT, double* lineT, SkDPoint* pt, PinTPoint ptSet) {
294 if (!approximately_one_or_less_double(*lineT)) {
295 return false;
296 }
297 if (!approximately_zero_or_more_double(*lineT)) {
298 return false;
299 }
300 double qT = *conicT = SkPinT(*conicT);
301 double lT = *lineT = SkPinT(*lineT);
302 if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && qT != 0 && qT != 1)) {
303 *pt = (*fLine).ptAtT(lT);
304 } else if (ptSet == kPointUninitialized) {
305 *pt = fConic.ptAtT(qT);
306 }
307 SkPoint gridPt = pt->asSkPoint();
308 if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[0].asSkPoint())) {
309 *pt = (*fLine)[0];
310 *lineT = 0;
311 } else if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[1].asSkPoint())) {
312 *pt = (*fLine)[1];
313 *lineT = 1;
314 }
315 if (fIntersections->used() > 0 && approximately_equal((*fIntersections)[1][0], *lineT)) {
316 return false;
317 }
318 if (gridPt == fConic[0].asSkPoint()) {
319 *pt = fConic[0];
320 *conicT = 0;
321 } else if (gridPt == fConic[2].asSkPoint()) {
322 *pt = fConic[2];
323 *conicT = 1;
324 }
325 return true;
326 }
327
uniqueAnswer(double conicT,const SkDPoint & pt)328 bool uniqueAnswer(double conicT, const SkDPoint& pt) {
329 for (int inner = 0; inner < fIntersections->used(); ++inner) {
330 if (fIntersections->pt(inner) != pt) {
331 continue;
332 }
333 double existingConicT = (*fIntersections)[0][inner];
334 if (conicT == existingConicT) {
335 return false;
336 }
337 // check if midway on conic is also same point. If so, discard this
338 double conicMidT = (existingConicT + conicT) / 2;
339 SkDPoint conicMidPt = fConic.ptAtT(conicMidT);
340 if (conicMidPt.approximatelyEqual(pt)) {
341 return false;
342 }
343 }
344 #if ONE_OFF_DEBUG
345 SkDPoint qPt = fConic.ptAtT(conicT);
346 SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY,
347 qPt.fX, qPt.fY);
348 #endif
349 return true;
350 }
351
352 private:
353 const SkDConic& fConic;
354 const SkDLine* fLine;
355 SkIntersections* fIntersections;
356 bool fAllowNear;
357 };
358
horizontal(const SkDConic & conic,double left,double right,double y,bool flipped)359 int SkIntersections::horizontal(const SkDConic& conic, double left, double right, double y,
360 bool flipped) {
361 SkDLine line = {{{ left, y }, { right, y }}};
362 LineConicIntersections c(conic, line, this);
363 return c.horizontalIntersect(y, left, right, flipped);
364 }
365
vertical(const SkDConic & conic,double top,double bottom,double x,bool flipped)366 int SkIntersections::vertical(const SkDConic& conic, double top, double bottom, double x,
367 bool flipped) {
368 SkDLine line = {{{ x, top }, { x, bottom }}};
369 LineConicIntersections c(conic, line, this);
370 return c.verticalIntersect(x, top, bottom, flipped);
371 }
372
intersect(const SkDConic & conic,const SkDLine & line)373 int SkIntersections::intersect(const SkDConic& conic, const SkDLine& line) {
374 LineConicIntersections c(conic, line, this);
375 c.allowNear(fAllowNear);
376 return c.intersect();
377 }
378
intersectRay(const SkDConic & conic,const SkDLine & line)379 int SkIntersections::intersectRay(const SkDConic& conic, const SkDLine& line) {
380 LineConicIntersections c(conic, line, this);
381 fUsed = c.intersectRay(fT[0]);
382 for (int index = 0; index < fUsed; ++index) {
383 fPt[index] = conic.ptAtT(fT[0][index]);
384 }
385 return fUsed;
386 }
387
HorizontalIntercept(const SkDConic & conic,SkScalar y,double * roots)388 int SkIntersections::HorizontalIntercept(const SkDConic& conic, SkScalar y, double* roots) {
389 LineConicIntersections c(conic);
390 return c.horizontalIntersect(y, roots);
391 }
392
VerticalIntercept(const SkDConic & conic,SkScalar x,double * roots)393 int SkIntersections::VerticalIntercept(const SkDConic& conic, SkScalar x, double* roots) {
394 LineConicIntersections c(conic);
395 return c.verticalIntersect(x, roots);
396 }
397