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 #include "SkAddIntersections.h"
8 #include "SkOpCoincidence.h"
9 #include "SkOpEdgeBuilder.h"
10 #include "SkPathOpsCommon.h"
11 #include "SkPathWriter.h"
12
bridgeWinding(SkOpContourHead * contourList,SkPathWriter * simple,SkChunkAlloc * allocator)13 static bool bridgeWinding(SkOpContourHead* contourList, SkPathWriter* simple,
14 SkChunkAlloc* allocator) {
15 bool unsortable = false;
16 do {
17 SkOpSpan* span = FindSortableTop(contourList);
18 if (!span) {
19 break;
20 }
21 SkOpSegment* current = span->segment();
22 SkOpSpanBase* start = span->next();
23 SkOpSpanBase* end = span;
24 SkTDArray<SkOpSpanBase*> chase;
25 do {
26 if (current->activeWinding(start, end)) {
27 do {
28 if (!unsortable && current->done()) {
29 break;
30 }
31 SkASSERT(unsortable || !current->done());
32 SkOpSpanBase* nextStart = start;
33 SkOpSpanBase* nextEnd = end;
34 SkOpSegment* next = current->findNextWinding(&chase, &nextStart, &nextEnd,
35 &unsortable);
36 if (!next) {
37 if (!unsortable && simple->hasMove()
38 && current->verb() != SkPath::kLine_Verb
39 && !simple->isClosed()) {
40 current->addCurveTo(start, end, simple, true);
41 #if DEBUG_ACTIVE_SPANS
42 if (!simple->isClosed()) {
43 DebugShowActiveSpans(contourList);
44 }
45 #endif
46 }
47 break;
48 }
49 #if DEBUG_FLOW
50 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
51 current->debugID(), start->pt().fX, start->pt().fY,
52 end->pt().fX, end->pt().fY);
53 #endif
54 current->addCurveTo(start, end, simple, true);
55 current = next;
56 start = nextStart;
57 end = nextEnd;
58 } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done()));
59 if (current->activeWinding(start, end) && !simple->isClosed()) {
60 SkOpSpan* spanStart = start->starter(end);
61 if (!spanStart->done()) {
62 current->addCurveTo(start, end, simple, true);
63 current->markDone(spanStart);
64 }
65 }
66 simple->close();
67 } else {
68 SkOpSpanBase* last = current->markAndChaseDone(start, end);
69 if (last && !last->chased()) {
70 last->setChased(true);
71 SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
72 *chase.append() = last;
73 #if DEBUG_WINDING
74 SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID());
75 if (!last->final()) {
76 SkDebugf(" windSum=%d", last->upCast()->windSum());
77 }
78 SkDebugf("\n");
79 #endif
80 }
81 }
82 current = FindChase(&chase, &start, &end);
83 #if DEBUG_ACTIVE_SPANS
84 DebugShowActiveSpans(contourList);
85 #endif
86 if (!current) {
87 break;
88 }
89 } while (true);
90 } while (true);
91 return simple->someAssemblyRequired();
92 }
93
94 // returns true if all edges were processed
bridgeXor(SkOpContourHead * contourList,SkPathWriter * simple,SkChunkAlloc * allocator)95 static bool bridgeXor(SkOpContourHead* contourList, SkPathWriter* simple,
96 SkChunkAlloc* allocator) {
97 SkOpSegment* current;
98 SkOpSpanBase* start;
99 SkOpSpanBase* end;
100 bool unsortable = false;
101 bool closable = true;
102 while ((current = FindUndone(contourList, &start, &end))) {
103 do {
104 #if DEBUG_ACTIVE_SPANS
105 if (!unsortable && current->done()) {
106 DebugShowActiveSpans(contourList);
107 }
108 #endif
109 SkASSERT(unsortable || !current->done());
110 SkOpSpanBase* nextStart = start;
111 SkOpSpanBase* nextEnd = end;
112 SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd, &unsortable);
113 if (!next) {
114 if (!unsortable && simple->hasMove()
115 && current->verb() != SkPath::kLine_Verb
116 && !simple->isClosed()) {
117 current->addCurveTo(start, end, simple, true);
118 #if DEBUG_ACTIVE_SPANS
119 if (!simple->isClosed()) {
120 DebugShowActiveSpans(contourList);
121 }
122 #endif
123 }
124 break;
125 }
126 #if DEBUG_FLOW
127 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
128 current->debugID(), start->pt().fX, start->pt().fY,
129 end->pt().fX, end->pt().fY);
130 #endif
131 current->addCurveTo(start, end, simple, true);
132 current = next;
133 start = nextStart;
134 end = nextEnd;
135 } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done()));
136 if (!simple->isClosed()) {
137 SkASSERT(unsortable);
138 SkOpSpan* spanStart = start->starter(end);
139 if (!spanStart->done()) {
140 current->addCurveTo(start, end, simple, true);
141 current->markDone(spanStart);
142 }
143 closable = false;
144 }
145 simple->close();
146 #if DEBUG_ACTIVE_SPANS
147 DebugShowActiveSpans(contourList);
148 #endif
149 }
150 return closable;
151 }
152
153 // FIXME : add this as a member of SkPath
Simplify(const SkPath & path,SkPath * result)154 bool Simplify(const SkPath& path, SkPath* result) {
155 SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune
156 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
157 SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenOdd_FillType
158 : SkPath::kEvenOdd_FillType;
159 if (path.isConvex()) {
160 if (result != &path) {
161 *result = path;
162 }
163 result->setFillType(fillType);
164 return true;
165 }
166 // turn path into list of segments
167 SkOpCoincidence coincidence;
168 SkOpContour contour;
169 SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
170 SkOpGlobalState globalState(&coincidence, contourList);
171 #if DEBUG_SORT
172 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
173 #endif
174 SkOpEdgeBuilder builder(path, &contour, &allocator, &globalState);
175 if (!builder.finish(&allocator)) {
176 return false;
177 }
178 #if DEBUG_DUMP_SEGMENTS
179 contour.dumpSegments((SkPathOp) -1);
180 #endif
181 if (!SortContourList(&contourList, false, false)) {
182 result->reset();
183 result->setFillType(fillType);
184 return true;
185 }
186 // find all intersections between segments
187 SkOpContour* current = contourList;
188 do {
189 SkOpContour* next = current;
190 while (AddIntersectTs(current, next, &coincidence, &allocator)
191 && (next = next->next()));
192 } while ((current = current->next()));
193 #if DEBUG_VALIDATE
194 globalState.setPhase(SkOpGlobalState::kWalking);
195 #endif
196 if (!HandleCoincidence(contourList, &coincidence, &allocator)) {
197 return false;
198 }
199 // construct closed contours
200 result->reset();
201 result->setFillType(fillType);
202 SkPathWriter wrapper(*result);
203 if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &wrapper, &allocator)
204 : !bridgeXor(contourList, &wrapper, &allocator))
205 { // if some edges could not be resolved, assemble remaining fragments
206 SkPath temp;
207 temp.setFillType(fillType);
208 SkPathWriter assembled(temp);
209 Assemble(wrapper, &assembled);
210 *result = *assembled.nativePath();
211 result->setFillType(fillType);
212 }
213 return true;
214 }
215