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