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