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