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 SkOpAngle_DEFINED
8#define SkOpAngle_DEFINED
9
10#include "SkChunkAlloc.h"
11#include "SkLineParameters.h"
12
13class SkOpSegment;
14struct SkOpSpan;
15
16// sorting angles
17// given angles of {dx dy ddx ddy dddx dddy} sort them
18class SkOpAngle {
19public:
20    enum { kStackBasedCount = 8 }; // FIXME: determine what this should be
21    enum IncludeType {
22        kUnaryWinding,
23        kUnaryXor,
24        kBinarySingle,
25        kBinaryOpp,
26    };
27
28
29    int end() const {
30        return fEnd;
31    }
32
33    const SkOpAngle* findFirst() const;
34
35    bool inLoop() const {
36        return !!fNext;
37    }
38
39    void insert(SkOpAngle* );
40    bool isHorizontal() const;
41    SkOpSpan* lastMarked() const;
42    bool loopContains(const SkOpAngle& ) const;
43    int loopCount() const;
44    void markStops();
45    bool merge(SkOpAngle* );
46
47    SkOpAngle* next() const {
48        return fNext;
49    }
50
51    SkOpAngle* previous() const;
52
53    void set(const SkOpSegment* segment, int start, int end);
54
55    void setLastMarked(SkOpSpan* marked) {
56        fLastMarked = marked;
57    }
58
59    SkOpSegment* segment() const {
60        return const_cast<SkOpSegment*>(fSegment);
61    }
62
63    int sign() const {
64        return SkSign32(fStart - fEnd);
65    }
66
67    bool small() const;
68
69    int start() const {
70        return fStart;
71    }
72
73    bool unorderable() const {
74        return fUnorderable;
75    }
76
77    // available to testing only
78#if DEBUG_SORT
79    void debugLoop() const;  // called by code during run
80#endif
81#if DEBUG_ANGLE
82    void debugSameAs(const SkOpAngle* compare) const;
83#endif
84    void dump() const;
85    void dumpLoop() const;
86    void dumpTo(const SkOpSegment* fromSeg, const SkOpAngle* ) const;
87
88#if DEBUG_ANGLE
89    int debugID() const { return fID; }
90
91    void setID(int id) {
92        fID = id;
93    }
94#else
95    int debugID() const { return 0; }
96#endif
97
98#if DEBUG_VALIDATE
99    void debugValidateLoop() const;
100#endif
101
102private:
103    bool after(const SkOpAngle* test) const;
104    int allOnOneSide(const SkOpAngle& test) const;
105    bool calcSlop(double x, double y, double rx, double ry, bool* result) const;
106    bool checkCrossesZero() const;
107    bool checkParallel(const SkOpAngle& ) const;
108    bool computeSector();
109    int convexHullOverlaps(const SkOpAngle& ) const;
110    double distEndRatio(double dist) const;
111    int findSector(SkPath::Verb verb, double x, double y) const;
112    bool endsIntersect(const SkOpAngle& ) const;
113    double midT() const;
114    bool oppositePlanes(const SkOpAngle& rh) const;
115    bool orderable(const SkOpAngle& rh) const;  // false == this < rh ; true == this > rh
116    bool overlap(const SkOpAngle& test) const;
117    void setCurveHullSweep();
118    void setSector();
119    void setSpans();
120    bool tangentsDiverge(const SkOpAngle& rh, double s0xt0) const;
121
122    SkDCubic fCurvePart; // the curve from start to end
123    double fSide;
124    SkLineParameters fTangentHalf;  // used only to sort a pair of lines or line-like sections
125    const SkOpSegment* fSegment;
126    SkOpAngle* fNext;
127    SkOpSpan* fLastMarked;
128    SkDVector fSweep[2];
129    int fStart;
130    int fEnd;
131    int fComputedEnd;
132    int fSectorMask;
133    int8_t fSectorStart;  // in 32nds of a circle
134    int8_t fSectorEnd;
135    bool fIsCurve;
136    bool fStop; // set if ordered angle is greater than the previous
137    mutable bool fUnorderable;  // this is editable by orderable()
138    bool fUnorderedSweep;  // set when a cubic's first control point between the sweep vectors
139    bool fComputeSector;
140    bool fComputedSector;
141
142#if DEBUG_ANGLE
143    int fID;
144#endif
145#if DEBUG_VALIDATE
146    void debugValidateNext() const;  // in debug builds, verify that angle loop is uncorrupted
147#else
148    void debugValidateNext() const {}
149#endif
150    void dumpOne(bool showFunc) const;  // available to testing only
151    void dumpPartials() const;  // utility to be called by user from debugger
152    friend class PathOpsAngleTester;
153};
154
155class SkOpAngleSet {
156public:
157    SkOpAngleSet();
158    ~SkOpAngleSet();
159    SkOpAngle& push_back();
160    void reset();
161private:
162    void dump() const;  // utility to be called by user from debugger
163    SkChunkAlloc* fAngles;
164#if DEBUG_ANGLE
165    int fCount;
166#endif
167};
168
169#endif
170