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