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
8#ifndef SkPathOpsCubic_DEFINED
9#define SkPathOpsCubic_DEFINED
10
11#include "SkPath.h"
12#include "SkPathOpsPoint.h"
13
14struct SkDCubicPair;
15
16struct SkDCubic {
17    static const int kPointCount = 4;
18    static const int kPointLast = kPointCount - 1;
19    static const int kMaxIntersections = 9;
20
21    enum SearchAxis {
22        kXAxis,
23        kYAxis
24    };
25
26    bool collapsed() const {
27        return fPts[0].approximatelyEqual(fPts[1]) && fPts[0].approximatelyEqual(fPts[2])
28                && fPts[0].approximatelyEqual(fPts[3]);
29    }
30
31    bool controlsInside() const {
32        SkDVector v01 = fPts[0] - fPts[1];
33        SkDVector v02 = fPts[0] - fPts[2];
34        SkDVector v03 = fPts[0] - fPts[3];
35        SkDVector v13 = fPts[1] - fPts[3];
36        SkDVector v23 = fPts[2] - fPts[3];
37        return v03.dot(v01) > 0 && v03.dot(v02) > 0 && v03.dot(v13) > 0 && v03.dot(v23) > 0;
38    }
39
40    static bool IsConic() { return false; }
41
42    const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; }
43    SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; }
44
45    void align(int endIndex, int ctrlIndex, SkDPoint* dstPt) const;
46    double binarySearch(double min, double max, double axisIntercept, SearchAxis xAxis) const;
47    double calcPrecision() const;
48    SkDCubicPair chopAt(double t) const;
49    static void Coefficients(const double* cubic, double* A, double* B, double* C, double* D);
50    static int ComplexBreak(const SkPoint pts[4], SkScalar* t);
51    int convexHull(char order[kPointCount]) const;
52
53    void debugInit() {
54        sk_bzero(fPts, sizeof(fPts));
55    }
56
57    void debugSet(const SkDPoint* pts);
58
59    void dump() const;  // callable from the debugger when the implementation code is linked in
60    void dumpID(int id) const;
61    void dumpInner() const;
62    SkDVector dxdyAtT(double t) const;
63    bool endsAreExtremaInXOrY() const;
64    static int FindExtrema(const double src[], double tValue[2]);
65    int findInflections(double tValues[2]) const;
66
67    static int FindInflections(const SkPoint a[kPointCount], double tValues[2]) {
68        SkDCubic cubic;
69        return cubic.set(a).findInflections(tValues);
70    }
71
72    int findMaxCurvature(double tValues[]) const;
73
74#ifdef SK_DEBUG
75    SkOpGlobalState* globalState() const { return fDebugGlobalState; }
76#endif
77
78    bool hullIntersects(const SkDCubic& c2, bool* isLinear) const;
79    bool hullIntersects(const SkDConic& c, bool* isLinear) const;
80    bool hullIntersects(const SkDQuad& c2, bool* isLinear) const;
81    bool hullIntersects(const SkDPoint* pts, int ptCount, bool* isLinear) const;
82    bool isLinear(int startIndex, int endIndex) const;
83    bool monotonicInX() const;
84    bool monotonicInY() const;
85    void otherPts(int index, const SkDPoint* o1Pts[kPointCount - 1]) const;
86    SkDPoint ptAtT(double t) const;
87    static int RootsReal(double A, double B, double C, double D, double t[3]);
88    static int RootsValidT(const double A, const double B, const double C, double D, double s[3]);
89
90    int searchRoots(double extremes[6], int extrema, double axisIntercept,
91                    SearchAxis xAxis, double* validRoots) const;
92
93    bool toFloatPoints(SkPoint* ) const;
94    /**
95     *  Return the number of valid roots (0 < root < 1) for this cubic intersecting the
96     *  specified horizontal line.
97     */
98    int horizontalIntersect(double yIntercept, double roots[3]) const;
99    /**
100     *  Return the number of valid roots (0 < root < 1) for this cubic intersecting the
101     *  specified vertical line.
102     */
103    int verticalIntersect(double xIntercept, double roots[3]) const;
104
105// add debug only global pointer so asserts can be skipped by fuzzers
106    const SkDCubic& set(const SkPoint pts[kPointCount]
107            SkDEBUGPARAMS(SkOpGlobalState* state = nullptr)) {
108        fPts[0] = pts[0];
109        fPts[1] = pts[1];
110        fPts[2] = pts[2];
111        fPts[3] = pts[3];
112        SkDEBUGCODE(fDebugGlobalState = state);
113        return *this;
114    }
115
116    SkDCubic subDivide(double t1, double t2) const;
117
118    static SkDCubic SubDivide(const SkPoint a[kPointCount], double t1, double t2) {
119        SkDCubic cubic;
120        return cubic.set(a).subDivide(t1, t2);
121    }
122
123    void subDivide(const SkDPoint& a, const SkDPoint& d, double t1, double t2, SkDPoint p[2]) const;
124
125    static void SubDivide(const SkPoint pts[kPointCount], const SkDPoint& a, const SkDPoint& d, double t1,
126                          double t2, SkDPoint p[2]) {
127        SkDCubic cubic;
128        cubic.set(pts).subDivide(a, d, t1, t2, p);
129    }
130
131    double top(const SkDCubic& dCurve, double startT, double endT, SkDPoint*topPt) const;
132    SkDQuad toQuad() const;
133
134    static const int gPrecisionUnit;
135    SkDPoint fPts[kPointCount];
136    SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState);
137};
138
139/* Given the set [0, 1, 2, 3], and two of the four members, compute an XOR mask
140   that computes the other two. Note that:
141
142   one ^ two == 3 for (0, 3), (1, 2)
143   one ^ two <  3 for (0, 1), (0, 2), (1, 3), (2, 3)
144   3 - (one ^ two) is either 0, 1, or 2
145   1 >> (3 - (one ^ two)) is either 0 or 1
146thus:
147   returned == 2 for (0, 3), (1, 2)
148   returned == 3 for (0, 1), (0, 2), (1, 3), (2, 3)
149given that:
150   (0, 3) ^ 2 -> (2, 1)  (1, 2) ^ 2 -> (3, 0)
151   (0, 1) ^ 3 -> (3, 2)  (0, 2) ^ 3 -> (3, 1)  (1, 3) ^ 3 -> (2, 0)  (2, 3) ^ 3 -> (1, 0)
152*/
153inline int other_two(int one, int two) {
154    return 1 >> (3 - (one ^ two)) ^ 3;
155}
156
157struct SkDCubicPair {
158    const SkDCubic first() const {
159#ifdef SK_DEBUG
160        SkDCubic result;
161        result.debugSet(&pts[0]);
162        return result;
163#else
164        return (const SkDCubic&) pts[0];
165#endif
166    }
167    const SkDCubic second() const {
168#ifdef SK_DEBUG
169        SkDCubic result;
170        result.debugSet(&pts[3]);
171        return result;
172#else
173        return (const SkDCubic&) pts[3];
174#endif
175    }
176    SkDPoint pts[7];
177};
178
179#endif
180