Line data Source code
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 :
14 : struct SkDCubicPair;
15 :
16 : struct 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 0 : bool collapsed() const {
27 0 : return fPts[0].approximatelyEqual(fPts[1]) && fPts[0].approximatelyEqual(fPts[2])
28 0 : && fPts[0].approximatelyEqual(fPts[3]);
29 : }
30 :
31 0 : bool controlsInside() const {
32 0 : SkDVector v01 = fPts[0] - fPts[1];
33 0 : SkDVector v02 = fPts[0] - fPts[2];
34 0 : SkDVector v03 = fPts[0] - fPts[3];
35 0 : SkDVector v13 = fPts[1] - fPts[3];
36 0 : SkDVector v23 = fPts[2] - fPts[3];
37 0 : return v03.dot(v01) > 0 && v03.dot(v02) > 0 && v03.dot(v13) > 0 && v03.dot(v23) > 0;
38 : }
39 :
40 0 : static bool IsConic() { return false; }
41 :
42 33 : const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; }
43 0 : 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 0 : void debugInit() {
54 0 : sk_bzero(fPts, sizeof(fPts));
55 0 : }
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 0 : static int FindInflections(const SkPoint a[kPointCount], double tValues[2]) {
68 : SkDCubic cubic;
69 0 : return cubic.set(a).findInflections(tValues);
70 : }
71 :
72 : int findMaxCurvature(double tValues[]) const;
73 :
74 : #ifdef SK_DEBUG
75 0 : 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 33 : const SkDCubic& set(const SkPoint pts[kPointCount]
107 : SkDEBUGPARAMS(SkOpGlobalState* state = nullptr)) {
108 33 : fPts[0] = pts[0];
109 33 : fPts[1] = pts[1];
110 33 : fPts[2] = pts[2];
111 33 : fPts[3] = pts[3];
112 33 : SkDEBUGCODE(fDebugGlobalState = state);
113 33 : return *this;
114 : }
115 :
116 : SkDCubic subDivide(double t1, double t2) const;
117 :
118 0 : static SkDCubic SubDivide(const SkPoint a[kPointCount], double t1, double t2) {
119 : SkDCubic cubic;
120 0 : 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 0 : 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 0 : cubic.set(pts).subDivide(a, d, t1, t2, p);
129 0 : }
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
146 : thus:
147 : returned == 2 for (0, 3), (1, 2)
148 : returned == 3 for (0, 1), (0, 2), (1, 3), (2, 3)
149 : given 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 : */
153 0 : inline int other_two(int one, int two) {
154 0 : return 1 >> (3 - (one ^ two)) ^ 3;
155 : }
156 :
157 : struct SkDCubicPair {
158 0 : const SkDCubic first() const {
159 : #ifdef SK_DEBUG
160 : SkDCubic result;
161 0 : result.debugSet(&pts[0]);
162 0 : return result;
163 : #else
164 : return (const SkDCubic&) pts[0];
165 : #endif
166 : }
167 0 : const SkDCubic second() const {
168 : #ifdef SK_DEBUG
169 : SkDCubic result;
170 0 : result.debugSet(&pts[3]);
171 0 : return result;
172 : #else
173 : return (const SkDCubic&) pts[3];
174 : #endif
175 : }
176 : SkDPoint pts[7];
177 : };
178 :
179 : #endif
|
