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