Line data Source code
1 : /*
2 : * Copyright 2013 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 : #ifndef SkOpContour_DEFINED
8 : #define SkOpContour_DEFINED
9 :
10 : #include "SkOpSegment.h"
11 : #include "SkTDArray.h"
12 : #include "SkTSort.h"
13 :
14 : enum class SkOpRayDir;
15 : struct SkOpRayHit;
16 : class SkPathWriter;
17 :
18 : class SkOpContour {
19 : public:
20 0 : SkOpContour() {
21 0 : reset();
22 0 : }
23 :
24 0 : bool operator<(const SkOpContour& rh) const {
25 0 : return fBounds.fTop == rh.fBounds.fTop
26 0 : ? fBounds.fLeft < rh.fBounds.fLeft
27 0 : : fBounds.fTop < rh.fBounds.fTop;
28 : }
29 :
30 0 : void addConic(SkPoint pts[3], SkScalar weight) {
31 0 : appendSegment().addConic(pts, weight, this);
32 0 : }
33 :
34 0 : void addCubic(SkPoint pts[4]) {
35 0 : appendSegment().addCubic(pts, this);
36 0 : }
37 :
38 0 : SkOpSegment* addLine(SkPoint pts[2]) {
39 0 : SkASSERT(pts[0] != pts[1]);
40 0 : return appendSegment().addLine(pts, this);
41 : }
42 :
43 0 : void addQuad(SkPoint pts[3]) {
44 0 : appendSegment().addQuad(pts, this);
45 0 : }
46 :
47 0 : SkOpSegment& appendSegment() {
48 0 : SkOpSegment* result = fCount++
49 0 : ? SkOpTAllocator<SkOpSegment>::Allocate(this->globalState()->allocator()) : &fHead;
50 0 : result->setPrev(fTail);
51 0 : if (fTail) {
52 0 : fTail->setNext(result);
53 : }
54 0 : fTail = result;
55 0 : return *result;
56 : }
57 :
58 0 : const SkPathOpsBounds& bounds() const {
59 0 : return fBounds;
60 : }
61 :
62 0 : void calcAngles() {
63 0 : SkASSERT(fCount > 0);
64 0 : SkOpSegment* segment = &fHead;
65 0 : do {
66 0 : segment->calcAngles();
67 : } while ((segment = segment->next()));
68 0 : }
69 :
70 0 : void complete() {
71 0 : setBounds();
72 0 : }
73 :
74 0 : int count() const {
75 0 : return fCount;
76 : }
77 :
78 : int debugID() const {
79 : return SkDEBUGRELEASE(fID, -1);
80 : }
81 :
82 : int debugIndent() const {
83 : return SkDEBUGRELEASE(fDebugIndent, 0);
84 : }
85 :
86 :
87 : const SkOpAngle* debugAngle(int id) const {
88 : return SkDEBUGRELEASE(this->globalState()->debugAngle(id), nullptr);
89 : }
90 :
91 : const SkOpCoincidence* debugCoincidence() const {
92 : return this->globalState()->coincidence();
93 : }
94 :
95 : #if DEBUG_COIN
96 : void debugCheckHealth(SkPathOpsDebug::GlitchLog* ) const;
97 : #endif
98 :
99 : SkOpContour* debugContour(int id) const {
100 : return SkDEBUGRELEASE(this->globalState()->debugContour(id), nullptr);
101 : }
102 :
103 : #if DEBUG_COIN
104 : void debugMissingCoincidence(SkPathOpsDebug::GlitchLog* log) const;
105 : void debugMoveMultiples(SkPathOpsDebug::GlitchLog* ) const;
106 : void debugMoveNearby(SkPathOpsDebug::GlitchLog* log) const;
107 : #endif
108 :
109 : const SkOpPtT* debugPtT(int id) const {
110 : return SkDEBUGRELEASE(this->globalState()->debugPtT(id), nullptr);
111 : }
112 :
113 : const SkOpSegment* debugSegment(int id) const {
114 : return SkDEBUGRELEASE(this->globalState()->debugSegment(id), nullptr);
115 : }
116 :
117 : #if DEBUG_ACTIVE_SPANS
118 : void debugShowActiveSpans(SkString* str) {
119 : SkOpSegment* segment = &fHead;
120 : do {
121 : segment->debugShowActiveSpans(str);
122 : } while ((segment = segment->next()));
123 : }
124 : #endif
125 :
126 : const SkOpSpanBase* debugSpan(int id) const {
127 : return SkDEBUGRELEASE(this->globalState()->debugSpan(id), nullptr);
128 : }
129 :
130 0 : SkOpGlobalState* globalState() const {
131 0 : return fState;
132 : }
133 :
134 0 : void debugValidate() const {
135 : #if DEBUG_VALIDATE
136 : const SkOpSegment* segment = &fHead;
137 : const SkOpSegment* prior = nullptr;
138 : do {
139 : segment->debugValidate();
140 : SkASSERT(segment->prev() == prior);
141 : prior = segment;
142 : } while ((segment = segment->next()));
143 : SkASSERT(prior == fTail);
144 : #endif
145 0 : }
146 :
147 0 : bool done() const {
148 0 : return fDone;
149 : }
150 :
151 : void dump() const;
152 : void dumpAll() const;
153 : void dumpAngles() const;
154 : void dumpContours() const;
155 : void dumpContoursAll() const;
156 : void dumpContoursAngles() const;
157 : void dumpContoursPts() const;
158 : void dumpContoursPt(int segmentID) const;
159 : void dumpContoursSegment(int segmentID) const;
160 : void dumpContoursSpan(int segmentID) const;
161 : void dumpContoursSpans() const;
162 : void dumpPt(int ) const;
163 : void dumpPts(const char* prefix = "seg") const;
164 : void dumpPtsX(const char* prefix) const;
165 : void dumpSegment(int ) const;
166 : void dumpSegments(const char* prefix = "seg", SkPathOp op = (SkPathOp) -1) const;
167 : void dumpSpan(int ) const;
168 : void dumpSpans() const;
169 :
170 : const SkPoint& end() const {
171 : return fTail->pts()[SkPathOpsVerbToPoints(fTail->verb())];
172 : }
173 :
174 : SkOpSpan* findSortableTop(SkOpContour* );
175 :
176 0 : SkOpSegment* first() {
177 0 : SkASSERT(fCount > 0);
178 0 : return &fHead;
179 : }
180 :
181 : const SkOpSegment* first() const {
182 : SkASSERT(fCount > 0);
183 : return &fHead;
184 : }
185 :
186 : void indentDump() const {
187 : SkDEBUGCODE(fDebugIndent += 2);
188 : }
189 :
190 0 : void init(SkOpGlobalState* globalState, bool operand, bool isXor) {
191 0 : fState = globalState;
192 0 : fOperand = operand;
193 0 : fXor = isXor;
194 0 : SkDEBUGCODE(fID = globalState->nextContourID());
195 0 : }
196 :
197 0 : int isCcw() const {
198 0 : return fCcw;
199 : }
200 :
201 0 : bool isXor() const {
202 0 : return fXor;
203 : }
204 :
205 0 : void joinSegments() {
206 0 : SkOpSegment* segment = &fHead;
207 : SkOpSegment* next;
208 0 : do {
209 0 : next = segment->next();
210 0 : segment->joinEnds(next ? next : &fHead);
211 0 : } while ((segment = next));
212 0 : }
213 :
214 0 : void markAllDone() {
215 0 : SkOpSegment* segment = &fHead;
216 0 : do {
217 0 : segment->markAllDone();
218 : } while ((segment = segment->next()));
219 0 : }
220 :
221 : // Please keep this aligned with debugMissingCoincidence()
222 0 : bool missingCoincidence() {
223 0 : SkASSERT(fCount > 0);
224 0 : SkOpSegment* segment = &fHead;
225 0 : bool result = false;
226 0 : do {
227 0 : if (segment->missingCoincidence()) {
228 0 : result = true;
229 : }
230 0 : segment = segment->next();
231 0 : } while (segment);
232 0 : return result;
233 : }
234 :
235 0 : bool moveMultiples() {
236 0 : SkASSERT(fCount > 0);
237 0 : SkOpSegment* segment = &fHead;
238 0 : do {
239 0 : if (!segment->moveMultiples()) {
240 0 : return false;
241 : }
242 : } while ((segment = segment->next()));
243 0 : return true;
244 : }
245 :
246 0 : bool moveNearby() {
247 0 : SkASSERT(fCount > 0);
248 0 : SkOpSegment* segment = &fHead;
249 0 : do {
250 0 : if (!segment->moveNearby()) {
251 0 : return false;
252 : }
253 : } while ((segment = segment->next()));
254 0 : return true;
255 : }
256 :
257 0 : SkOpContour* next() {
258 0 : return fNext;
259 : }
260 :
261 : const SkOpContour* next() const {
262 : return fNext;
263 : }
264 :
265 0 : bool operand() const {
266 0 : return fOperand;
267 : }
268 :
269 0 : bool oppXor() const {
270 0 : return fOppXor;
271 : }
272 :
273 : void outdentDump() const {
274 : SkDEBUGCODE(fDebugIndent -= 2);
275 : }
276 :
277 : void rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, SkArenaAlloc*);
278 :
279 0 : void reset() {
280 0 : fTail = nullptr;
281 0 : fNext = nullptr;
282 0 : fCount = 0;
283 0 : fDone = false;
284 0 : SkDEBUGCODE(fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMin, SK_ScalarMin));
285 0 : SkDEBUGCODE(fFirstSorted = -1);
286 0 : SkDEBUGCODE(fDebugIndent = 0);
287 0 : }
288 :
289 0 : void resetReverse() {
290 0 : SkOpContour* next = this;
291 0 : do {
292 0 : if (!next->count()) {
293 0 : continue;
294 : }
295 0 : next->fCcw = -1;
296 0 : next->fReverse = false;
297 : } while ((next = next->next()));
298 0 : }
299 :
300 0 : bool reversed() const {
301 0 : return fReverse;
302 : }
303 :
304 0 : void setBounds() {
305 0 : SkASSERT(fCount > 0);
306 0 : const SkOpSegment* segment = &fHead;
307 0 : fBounds = segment->bounds();
308 0 : while ((segment = segment->next())) {
309 0 : fBounds.add(segment->bounds());
310 : }
311 0 : }
312 :
313 0 : void setCcw(int ccw) {
314 0 : fCcw = ccw;
315 0 : }
316 :
317 : void setGlobalState(SkOpGlobalState* state) {
318 : fState = state;
319 : }
320 :
321 0 : void setNext(SkOpContour* contour) {
322 : // SkASSERT(!fNext == !!contour);
323 0 : fNext = contour;
324 0 : }
325 :
326 : void setOperand(bool isOp) {
327 : fOperand = isOp;
328 : }
329 :
330 0 : void setOppXor(bool isOppXor) {
331 0 : fOppXor = isOppXor;
332 0 : }
333 :
334 0 : void setReverse() {
335 0 : fReverse = true;
336 0 : }
337 :
338 : void setXor(bool isXor) {
339 : fXor = isXor;
340 : }
341 :
342 0 : bool sortAngles() {
343 0 : SkASSERT(fCount > 0);
344 0 : SkOpSegment* segment = &fHead;
345 0 : do {
346 0 : FAIL_IF(!segment->sortAngles());
347 : } while ((segment = segment->next()));
348 0 : return true;
349 : }
350 :
351 : const SkPoint& start() const {
352 : return fHead.pts()[0];
353 : }
354 :
355 : void toPartialBackward(SkPathWriter* path) const {
356 : const SkOpSegment* segment = fTail;
357 : do {
358 : SkAssertResult(segment->addCurveTo(segment->tail(), segment->head(), path));
359 : } while ((segment = segment->prev()));
360 : }
361 :
362 : void toPartialForward(SkPathWriter* path) const {
363 : const SkOpSegment* segment = &fHead;
364 : do {
365 : SkAssertResult(segment->addCurveTo(segment->head(), segment->tail(), path));
366 : } while ((segment = segment->next()));
367 : }
368 :
369 : void toReversePath(SkPathWriter* path) const;
370 : void toPath(SkPathWriter* path) const;
371 : SkOpSpan* undoneSpan();
372 :
373 : protected:
374 : SkOpGlobalState* fState;
375 : SkOpSegment fHead;
376 : SkOpSegment* fTail;
377 : SkOpContour* fNext;
378 : SkPathOpsBounds fBounds;
379 : int fCcw;
380 : int fCount;
381 : int fFirstSorted;
382 : bool fDone; // set by find top segment
383 : bool fOperand; // true for the second argument to a binary operator
384 : bool fReverse; // true if contour should be reverse written to path (used only by fix winding)
385 : bool fXor; // set if original path had even-odd fill
386 : bool fOppXor; // set if opposite path had even-odd fill
387 : SkDEBUGCODE(int fID);
388 : SkDEBUGCODE(mutable int fDebugIndent);
389 : };
390 :
391 0 : class SkOpContourHead : public SkOpContour {
392 : public:
393 0 : SkOpContour* appendContour() {
394 0 : SkOpContour* contour = SkOpTAllocator<SkOpContour>::New(this->globalState()->allocator());
395 0 : contour->setNext(nullptr);
396 0 : SkOpContour* prev = this;
397 : SkOpContour* next;
398 0 : while ((next = prev->next())) {
399 0 : prev = next;
400 : }
401 0 : prev->setNext(contour);
402 0 : return contour;
403 : }
404 :
405 0 : void joinAllSegments() {
406 0 : SkOpContour* next = this;
407 0 : do {
408 0 : if (!next->count()) {
409 0 : continue;
410 : }
411 0 : next->joinSegments();
412 : } while ((next = next->next()));
413 0 : }
414 :
415 0 : void remove(SkOpContour* contour) {
416 0 : if (contour == this) {
417 0 : SkASSERT(this->count() == 0);
418 0 : return;
419 : }
420 0 : SkASSERT(contour->next() == nullptr);
421 0 : SkOpContour* prev = this;
422 : SkOpContour* next;
423 0 : while ((next = prev->next()) != contour) {
424 0 : SkASSERT(next);
425 0 : prev = next;
426 : }
427 0 : SkASSERT(prev);
428 0 : prev->setNext(nullptr);
429 : }
430 :
431 : };
432 :
433 : class SkOpContourBuilder {
434 : public:
435 0 : SkOpContourBuilder(SkOpContour* contour)
436 0 : : fContour(contour)
437 0 : , fLastIsLine(false) {
438 0 : }
439 :
440 : void addConic(SkPoint pts[3], SkScalar weight);
441 : void addCubic(SkPoint pts[4]);
442 : void addCurve(SkPath::Verb verb, const SkPoint pts[4], SkScalar weight = 1);
443 : void addLine(const SkPoint pts[2]);
444 : void addQuad(SkPoint pts[3]);
445 : void flush();
446 0 : SkOpContour* contour() { return fContour; }
447 0 : void setContour(SkOpContour* contour) { flush(); fContour = contour; }
448 : protected:
449 : SkOpContour* fContour;
450 : SkPoint fLastLine[2];
451 : bool fLastIsLine;
452 : };
453 :
454 : #endif
|