1/*
2 * Copyright 2012 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#ifndef SkIntersections_DEFINE
8#define SkIntersections_DEFINE
9
10#include "src/pathops/SkPathOpsConic.h"
11#include "src/pathops/SkPathOpsCubic.h"
12#include "src/pathops/SkPathOpsLine.h"
13#include "src/pathops/SkPathOpsPoint.h"
14#include "src/pathops/SkPathOpsQuad.h"
15
16class SkIntersections {
17public:
18 SkIntersections(SkDEBUGCODE(SkOpGlobalState* globalState = nullptr))
19 : fSwap(0)
20#ifdef SK_DEBUG
21 SkDEBUGPARAMS(fDebugGlobalState(globalState))
22 , fDepth(0)
23#endif
24 {
25 sk_bzero(fPt, sizeof(fPt));
26 sk_bzero(fPt2, sizeof(fPt2));
27 sk_bzero(fT, sizeof(fT));
28 sk_bzero(fNearlySame, sizeof(fNearlySame));
29#if DEBUG_T_SECT_LOOP_COUNT
30 sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount));
31#endif
32 reset();
33 fMax = 0; // require that the caller set the max
34 }
35
36 class TArray {
37 public:
38 explicit TArray(const double ts[10]) : fTArray(ts) {}
39 double operator[](int n) const {
40 return fTArray[n];
41 }
42 const double* fTArray;
43 };
44 TArray operator[](int n) const { return TArray(fT[n]); }
45
46 void allowNear(bool nearAllowed) {
47 fAllowNear = nearAllowed;
48 }
49
50 void clearCoincidence(int index) {
51 SkASSERT(index >= 0);
52 int bit = 1 << index;
53 fIsCoincident[0] &= ~bit;
54 fIsCoincident[1] &= ~bit;
55 }
56
57 int conicHorizontal(const SkPoint a[3], SkScalar weight, SkScalar left, SkScalar right,
58 SkScalar y, bool flipped) {
59 SkDConic conic;
60 conic.set(a, weight);
61 fMax = 2;
62 return horizontal(conic, left, right, y, flipped);
63 }
64
65 int conicVertical(const SkPoint a[3], SkScalar weight, SkScalar top, SkScalar bottom,
66 SkScalar x, bool flipped) {
67 SkDConic conic;
68 conic.set(a, weight);
69 fMax = 2;
70 return vertical(conic, top, bottom, x, flipped);
71 }
72
73 int conicLine(const SkPoint a[3], SkScalar weight, const SkPoint b[2]) {
74 SkDConic conic;
75 conic.set(a, weight);
76 SkDLine line;
77 line.set(b);
78 fMax = 3; // 2; permit small coincident segment + non-coincident intersection
79 return intersect(conic, line);
80 }
81
82 int cubicHorizontal(const SkPoint a[4], SkScalar left, SkScalar right, SkScalar y,
83 bool flipped) {
84 SkDCubic cubic;
85 cubic.set(a);
86 fMax = 3;
87 return horizontal(cubic, left, right, y, flipped);
88 }
89
90 int cubicVertical(const SkPoint a[4], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
91 SkDCubic cubic;
92 cubic.set(a);
93 fMax = 3;
94 return vertical(cubic, top, bottom, x, flipped);
95 }
96
97 int cubicLine(const SkPoint a[4], const SkPoint b[2]) {
98 SkDCubic cubic;
99 cubic.set(a);
100 SkDLine line;
101 line.set(b);
102 fMax = 3;
103 return intersect(cubic, line);
104 }
105
106#ifdef SK_DEBUG
107 SkOpGlobalState* globalState() const { return fDebugGlobalState; }
108#endif
109
110 bool hasT(double t) const {
111 SkASSERT(t == 0 || t == 1);
112 return fUsed > 0 && (t == 0 ? fT[0][0] == 0 : fT[0][fUsed - 1] == 1);
113 }
114
115 bool hasOppT(double t) const {
116 SkASSERT(t == 0 || t == 1);
117 return fUsed > 0 && (fT[1][0] == t || fT[1][fUsed - 1] == t);
118 }
119
120 int insertSwap(double one, double two, const SkDPoint& pt) {
121 if (fSwap) {
122 return insert(two, one, pt);
123 } else {
124 return insert(one, two, pt);
125 }
126 }
127
128 bool isCoincident(int index) {
129 return (fIsCoincident[0] & 1 << index) != 0;
130 }
131
132 int lineHorizontal(const SkPoint a[2], SkScalar left, SkScalar right, SkScalar y,
133 bool flipped) {
134 SkDLine line;
135 line.set(a);
136 fMax = 2;
137 return horizontal(line, left, right, y, flipped);
138 }
139
140 int lineVertical(const SkPoint a[2], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
141 SkDLine line;
142 line.set(a);
143 fMax = 2;
144 return vertical(line, top, bottom, x, flipped);
145 }
146
147 int lineLine(const SkPoint a[2], const SkPoint b[2]) {
148 SkDLine aLine, bLine;
149 aLine.set(a);
150 bLine.set(b);
151 fMax = 2;
152 return intersect(aLine, bLine);
153 }
154
155 bool nearlySame(int index) const {
156 SkASSERT(index == 0 || index == 1);
157 return fNearlySame[index];
158 }
159
160 const SkDPoint& pt(int index) const {
161 return fPt[index];
162 }
163
164 const SkDPoint& pt2(int index) const {
165 return fPt2[index];
166 }
167
168 int quadHorizontal(const SkPoint a[3], SkScalar left, SkScalar right, SkScalar y,
169 bool flipped) {
170 SkDQuad quad;
171 quad.set(a);
172 fMax = 2;
173 return horizontal(quad, left, right, y, flipped);
174 }
175
176 int quadVertical(const SkPoint a[3], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
177 SkDQuad quad;
178 quad.set(a);
179 fMax = 2;
180 return vertical(quad, top, bottom, x, flipped);
181 }
182
183 int quadLine(const SkPoint a[3], const SkPoint b[2]) {
184 SkDQuad quad;
185 quad.set(a);
186 SkDLine line;
187 line.set(b);
188 return intersect(quad, line);
189 }
190
191 // leaves swap, max alone
192 void reset() {
193 fAllowNear = true;
194 fUsed = 0;
195 sk_bzero(fIsCoincident, sizeof(fIsCoincident));
196 }
197
198 void set(bool swap, int tIndex, double t) {
199 fT[(int) swap][tIndex] = t;
200 }
201
202 void setMax(int max) {
203 SkASSERT(max <= (int) SK_ARRAY_COUNT(fPt));
204 fMax = max;
205 }
206
207 void swap() {
208 fSwap ^= true;
209 }
210
211 bool swapped() const {
212 return fSwap;
213 }
214
215 int used() const {
216 return fUsed;
217 }
218
219 void downDepth() {
220 SkASSERT(--fDepth >= 0);
221 }
222
223 bool unBumpT(int index) {
224 SkASSERT(fUsed == 1);
225 fT[0][index] = fT[0][index] * (1 + BUMP_EPSILON * 2) - BUMP_EPSILON;
226 if (!between(0, fT[0][index], 1)) {
227 fUsed = 0;
228 return false;
229 }
230 return true;
231 }
232
233 void upDepth() {
234 SkASSERT(++fDepth < 16);
235 }
236
237 void alignQuadPts(const SkPoint a[3], const SkPoint b[3]);
238 int cleanUpCoincidence();
239 int closestTo(double rangeStart, double rangeEnd, const SkDPoint& testPt, double* dist) const;
240 void cubicInsert(double one, double two, const SkDPoint& pt, const SkDCubic& c1,
241 const SkDCubic& c2);
242 void flip();
243 int horizontal(const SkDLine&, double left, double right, double y, bool flipped);
244 int horizontal(const SkDQuad&, double left, double right, double y, bool flipped);
245 int horizontal(const SkDQuad&, double left, double right, double y, double tRange[2]);
246 int horizontal(const SkDCubic&, double y, double tRange[3]);
247 int horizontal(const SkDConic&, double left, double right, double y, bool flipped);
248 int horizontal(const SkDCubic&, double left, double right, double y, bool flipped);
249 int horizontal(const SkDCubic&, double left, double right, double y, double tRange[3]);
250 static double HorizontalIntercept(const SkDLine& line, double y);
251 static int HorizontalIntercept(const SkDQuad& quad, SkScalar y, double* roots);
252 static int HorizontalIntercept(const SkDConic& conic, SkScalar y, double* roots);
253 // FIXME : does not respect swap
254 int insert(double one, double two, const SkDPoint& pt);
255 void insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2);
256 // start if index == 0 : end if index == 1
257 int insertCoincident(double one, double two, const SkDPoint& pt);
258 int intersect(const SkDLine&, const SkDLine&);
259 int intersect(const SkDQuad&, const SkDLine&);
260 int intersect(const SkDQuad&, const SkDQuad&);
261 int intersect(const SkDConic&, const SkDLine&);
262 int intersect(const SkDConic&, const SkDQuad&);
263 int intersect(const SkDConic&, const SkDConic&);
264 int intersect(const SkDCubic&, const SkDLine&);
265 int intersect(const SkDCubic&, const SkDQuad&);
266 int intersect(const SkDCubic&, const SkDConic&);
267 int intersect(const SkDCubic&, const SkDCubic&);
268 int intersectRay(const SkDLine&, const SkDLine&);
269 int intersectRay(const SkDQuad&, const SkDLine&);
270 int intersectRay(const SkDConic&, const SkDLine&);
271 int intersectRay(const SkDCubic&, const SkDLine&);
272 int intersectRay(const SkTCurve& tCurve, const SkDLine& line) {
273 return tCurve.intersectRay(this, line);
274 }
275
276 void merge(const SkIntersections& , int , const SkIntersections& , int );
277 int mostOutside(double rangeStart, double rangeEnd, const SkDPoint& origin) const;
278 void removeOne(int index);
279 void setCoincident(int index);
280 int vertical(const SkDLine&, double top, double bottom, double x, bool flipped);
281 int vertical(const SkDQuad&, double top, double bottom, double x, bool flipped);
282 int vertical(const SkDConic&, double top, double bottom, double x, bool flipped);
283 int vertical(const SkDCubic&, double top, double bottom, double x, bool flipped);
284 static double VerticalIntercept(const SkDLine& line, double x);
285 static int VerticalIntercept(const SkDQuad& quad, SkScalar x, double* roots);
286 static int VerticalIntercept(const SkDConic& conic, SkScalar x, double* roots);
287
288 int depth() const {
289#ifdef SK_DEBUG
290 return fDepth;
291#else
292 return 0;
293#endif
294 }
295
296 enum DebugLoop {
297 kIterations_DebugLoop,
298 kCoinCheck_DebugLoop,
299 kComputePerp_DebugLoop,
300 };
301
302 void debugBumpLoopCount(DebugLoop );
303 int debugCoincidentUsed() const;
304 int debugLoopCount(DebugLoop ) const;
305 void debugResetLoopCount();
306 void dump() const; // implemented for testing only
307
308private:
309 bool cubicCheckCoincidence(const SkDCubic& c1, const SkDCubic& c2);
310 bool cubicExactEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2);
311 void cubicNearEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2, const SkDRect& );
312 void cleanUpParallelLines(bool parallel);
313 void computePoints(const SkDLine& line, int used);
314
315 SkDPoint fPt[13]; // FIXME: since scans store points as SkPoint, this should also
316 SkDPoint fPt2[2]; // used by nearly same to store alternate intersection point
317 double fT[2][13];
318 uint16_t fIsCoincident[2]; // bit set for each curve's coincident T
319 bool fNearlySame[2]; // true if end points nearly match
320 unsigned char fUsed;
321 unsigned char fMax;
322 bool fAllowNear;
323 bool fSwap;
324#ifdef SK_DEBUG
325 SkOpGlobalState* fDebugGlobalState;
326 int fDepth;
327#endif
328#if DEBUG_T_SECT_LOOP_COUNT
329 int fDebugLoopCount[3];
330#endif
331};
332
333#endif
334