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