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
|
/*
* Copyright 2014 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#ifndef SkCubicSpan_DEFINE
#define SkCubicSpan_DEFINE
#include "SkChunkAlloc.h"
#include "SkPathOpsRect.h"
#include "SkPathOpsCubic.h"
#include "SkTArray.h"
class SkIntersections;
class SkCubicCoincident {
public:
bool isCoincident() const {
return fCoincident;
}
void init() {
fCoincident = false;
SkDEBUGCODE(fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN);
SkDEBUGCODE(fPerpT = SK_ScalarNaN);
}
void markCoincident() {
if (!fCoincident) {
fPerpT = -1;
}
fCoincident = true;
}
const SkDPoint& perpPt() const {
return fPerpPt;
}
double perpT() const {
return fPerpT;
}
void setPerp(const SkDCubic& cubic1, double t, const SkDPoint& qPt, const SkDCubic& cubic2);
private:
SkDPoint fPerpPt;
double fPerpT; // perpendicular intersection on opposite Cubic
bool fCoincident;
};
class SkCubicSect; // used only by debug id
class SkCubicSpan {
public:
void init(const SkDCubic& Cubic);
void initBounds(const SkDCubic& Cubic);
bool contains(double t) const {
return !! const_cast<SkCubicSpan*>(this)->innerFind(t);
}
bool contains(const SkCubicSpan* span) const;
SkCubicSpan* find(double t) {
SkCubicSpan* result = innerFind(t);
SkASSERT(result);
return result;
}
bool intersects(const SkCubicSpan* span) const;
const SkCubicSpan* next() const {
return fNext;
}
void reset() {
fBounded.reset();
}
bool split(SkCubicSpan* work) {
return splitAt(work, (work->fStartT + work->fEndT) * 0.5);
}
bool splitAt(SkCubicSpan* work, double t);
bool tightBoundsIntersects(const SkCubicSpan* span) const;
// implementation is for testing only
void dump() const;
private:
bool hullIntersects(const SkDCubic& ) const;
SkCubicSpan* innerFind(double t);
bool linearIntersects(const SkDCubic& ) const;
// implementation is for testing only
#if DEBUG_BINARY_CUBIC
int debugID(const SkCubicSect* ) const { return fDebugID; }
#else
int debugID(const SkCubicSect* ) const;
#endif
void dump(const SkCubicSect* ) const;
void dumpID(const SkCubicSect* ) const;
#if DEBUG_BINARY_CUBIC
void validate() const;
#endif
SkDCubic fPart;
SkCubicCoincident fCoinStart;
SkCubicCoincident fCoinEnd;
SkSTArray<4, SkCubicSpan*, true> fBounded;
SkCubicSpan* fPrev;
SkCubicSpan* fNext;
SkDRect fBounds;
double fStartT;
double fEndT;
double fBoundsMax;
bool fCollapsed;
bool fHasPerp;
mutable bool fIsLinear;
#if DEBUG_BINARY_CUBIC
int fDebugID;
bool fDebugDeleted;
#endif
friend class SkCubicSect;
};
class SkCubicSect {
public:
SkCubicSect(const SkDCubic& Cubic PATH_OPS_DEBUG_PARAMS(int id));
static void BinarySearch(SkCubicSect* sect1, SkCubicSect* sect2, SkIntersections* intersections);
// for testing only
void dumpCubics() const;
private:
SkCubicSpan* addOne();
bool binarySearchCoin(const SkCubicSect& , double tStart, double tStep, double* t,
double* oppT);
SkCubicSpan* boundsMax() const;
void coincidentCheck(SkCubicSect* sect2);
bool intersects(const SkCubicSpan* span, const SkCubicSect* opp, const SkCubicSpan* oppSpan) const;
void onCurveCheck(SkCubicSect* sect2, SkCubicSpan* first, SkCubicSpan* last);
void recoverCollapsed();
void removeSpan(SkCubicSpan* span);
void removeOne(const SkCubicSpan* test, SkCubicSpan* span);
void removeSpans(SkCubicSpan* span, SkCubicSect* opp);
void setPerp(const SkDCubic& opp, SkCubicSpan* first, SkCubicSpan* last);
void trim(SkCubicSpan* span, SkCubicSect* opp);
// for testing only
void dump() const;
void dumpBoth(const SkCubicSect& opp) const;
void dumpBoth(const SkCubicSect* opp) const;
#if DEBUG_BINARY_CUBIC
int debugID() const { return fDebugID; }
void validate() const;
#else
int debugID() const { return 0; }
#endif
const SkDCubic& fCubic;
SkChunkAlloc fHeap;
SkCubicSpan* fHead;
SkCubicSpan* fDeleted;
int fActiveCount;
#if DEBUG_BINARY_CUBIC
int fDebugID;
int fDebugCount;
int fDebugAllocatedCount;
#endif
friend class SkCubicSpan; // only used by debug id
};
#endif
|
