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