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