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