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
16class SkIntersections {
17public:
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:
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
42    void allowNear(bool nearAllowed) {
43        fAllowNear = nearAllowed;
44    }
45
46    void clearCoincidence(int index) {
47        SkASSERT(index >= 0);
48        int bit = 1 << index;
49        fIsCoincident[0] &= ~bit;
50        fIsCoincident[1] &= ~bit;
51    }
52
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
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
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
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
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
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
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
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
115    bool isCoincident(int index) {
116        return (fIsCoincident[0] & 1 << index) != 0;
117    }
118
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
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
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
142    bool nearlySame(int index) const {
143        SkASSERT(index == 0 || index == 1);
144        return fNearlySame[index];
145    }
146
147    const SkDPoint& pt(int index) const {
148        return fPt[index];
149    }
150
151    const SkDPoint& pt2(int index) const {
152        return fPt2[index];
153    }
154
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
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
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
180    void reset() {
181        fAllowNear = true;
182        fUsed = 0;
183        sk_bzero(fIsCoincident, sizeof(fIsCoincident));
184    }
185
186    void set(bool swap, int tIndex, double t) {
187        fT[(int) swap][tIndex] = t;
188    }
189
190    void setMax(int max) {
191        fMax = max;
192    }
193
194    void swap() {
195        fSwap ^= true;
196    }
197
198    bool swapped() const {
199        return fSwap;
200    }
201
202    int used() const {
203        return fUsed;
204    }
205
206    void downDepth() {
207        SkASSERT(--fDepth >= 0);
208    }
209
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
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
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
282private:
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