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
|
/*
* 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 {
const SkDCubic& first() const { return (const SkDCubic&) pts[0]; }
const SkDCubic& second() const { return (const SkDCubic&) pts[3]; }
SkDPoint pts[7];
};
struct SkDCubic {
static const int kPointCount = 4;
static const int kPointLast = kPointCount - 1;
static const int kMaxIntersections = 9;
enum SearchAxis {
kXAxis,
kYAxis
};
enum CubicType {
kUnsplit_SkDCubicType,
kSplitAtLoop_SkDCubicType,
kSplitAtInflection_SkDCubicType,
kSplitAtMaxCurvature_SkDCubicType,
};
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 IsCubic() { return true; }
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 bool ComplexBreak(const SkPoint pts[4], SkScalar* t, CubicType* cubicType);
int convexHull(char order[kPointCount]) const;
void debugInit() {
sk_bzero(fPts, sizeof(fPts));
}
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;
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;
/**
* 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;
const SkDCubic& set(const SkPoint pts[kPointCount]) {
fPts[0] = pts[0];
fPts[1] = pts[1];
fPts[2] = pts[2];
fPts[3] = pts[3];
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];
};
/* 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;
}
#endif
|
