The Tor Browser / file comparison

comparison: gfx/skia/trunk/src/pathops/SkPathOpsOp.cpp

gfx/skia/trunk/src/pathops/SkPathOpsOp.cpp

branch
TOR_BUG_3246
changeset 7
129ffea94266
equal deleted inserted replaced
-1:000000000000 0:cbc9eba1402c
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 "SkOpEdgeBuilder.h"
9 #include "SkPathOpsCommon.h"
10 #include "SkPathWriter.h"
11
12 // FIXME: this and find chase should be merge together, along with
13 // other code that walks winding in angles
14 // OPTIMIZATION: Probably, the walked winding should be rolled into the angle structure
15 // so it isn't duplicated by walkers like this one
16 static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int& nextEnd) {
17 while (chase.count()) {
18 SkOpSpan* span;
19 chase.pop(&span);
20 const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex);
21 SkOpSegment* segment = backPtr.fOther;
22 nextStart = backPtr.fOtherIndex;
23 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
24 int done = 0;
25 if (segment->activeAngle(nextStart, &done, &angles)) {
26 SkOpAngle* last = angles.end() - 1;
27 nextStart = last->start();
28 nextEnd = last->end();
29 #if TRY_ROTATE
30 *chase.insert(0) = span;
31 #else
32 *chase.append() = span;
33 #endif
34 return last->segment();
35 }
36 if (done == angles.count()) {
37 continue;
38 }
39 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
40 bool sortable = SkOpSegment::SortAngles(angles, &sorted,
41 SkOpSegment::kMayBeUnordered_SortAngleKind);
42 int angleCount = sorted.count();
43 #if DEBUG_SORT
44 sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, sortable);
45 #endif
46 if (!sortable) {
47 continue;
48 }
49 // find first angle, initialize winding to computed fWindSum
50 int firstIndex = -1;
51 const SkOpAngle* angle;
52 bool foundAngle = true;
53 do {
54 ++firstIndex;
55 if (firstIndex >= angleCount) {
56 foundAngle = false;
57 break;
58 }
59 angle = sorted[firstIndex];
60 segment = angle->segment();
61 } while (segment->windSum(angle) == SK_MinS32);
62 if (!foundAngle) {
63 continue;
64 }
65 #if DEBUG_SORT
66 segment->debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
67 #endif
68 int sumMiWinding = segment->updateWindingReverse(angle);
69 int sumSuWinding = segment->updateOppWindingReverse(angle);
70 if (segment->operand()) {
71 SkTSwap<int>(sumMiWinding, sumSuWinding);
72 }
73 int nextIndex = firstIndex + 1;
74 int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
75 SkOpSegment* first = NULL;
76 do {
77 SkASSERT(nextIndex != firstIndex);
78 if (nextIndex == angleCount) {
79 nextIndex = 0;
80 }
81 angle = sorted[nextIndex];
82 segment = angle->segment();
83 int start = angle->start();
84 int end = angle->end();
85 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
86 segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding,
87 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
88 if (!segment->done(angle)) {
89 if (!first) {
90 first = segment;
91 nextStart = start;
92 nextEnd = end;
93 }
94 (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
95 oppSumWinding, angle);
96 }
97 } while (++nextIndex != lastIndex);
98 if (first) {
99 #if TRY_ROTATE
100 *chase.insert(0) = span;
101 #else
102 *chase.append() = span;
103 #endif
104 return first;
105 }
106 }
107 return NULL;
108 }
109
110 /*
111 static bool windingIsActive(int winding, int oppWinding, int spanWinding, int oppSpanWinding,
112 bool windingIsOp, PathOp op) {
113 bool active = windingIsActive(winding, spanWinding);
114 if (!active) {
115 return false;
116 }
117 if (oppSpanWinding && windingIsActive(oppWinding, oppSpanWinding)) {
118 switch (op) {
119 case kIntersect_Op:
120 case kUnion_Op:
121 return true;
122 case kDifference_Op: {
123 int absSpan = abs(spanWinding);
124 int absOpp = abs(oppSpanWinding);
125 return windingIsOp ? absSpan < absOpp : absSpan > absOpp;
126 }
127 case kXor_Op:
128 return spanWinding != oppSpanWinding;
129 default:
130 SkASSERT(0);
131 }
132 }
133 bool opActive = oppWinding != 0;
134 return gOpLookup[op][opActive][windingIsOp];
135 }
136 */
137
138 static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp op,
139 const int xorMask, const int xorOpMask, SkPathWriter* simple) {
140 bool firstContour = true;
141 bool unsortable = false;
142 bool topUnsortable = false;
143 SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
144 do {
145 int index, endIndex;
146 bool done;
147 SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kBinarySingle, &firstContour,
148 &index, &endIndex, &topLeft, &topUnsortable, &done);
149 if (!current) {
150 if (topUnsortable || !done) {
151 topUnsortable = false;
152 SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
153 topLeft.fX = topLeft.fY = SK_ScalarMin;
154 continue;
155 }
156 break;
157 }
158 SkTDArray<SkOpSpan*> chaseArray;
159 do {
160 if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) {
161 do {
162 if (!unsortable && current->done()) {
163 #if DEBUG_ACTIVE_SPANS
164 DebugShowActiveSpans(contourList);
165 #endif
166 if (simple->isEmpty()) {
167 simple->init();
168 }
169 break;
170 }
171 SkASSERT(unsortable || !current->done());
172 int nextStart = index;
173 int nextEnd = endIndex;
174 SkOpSegment* next = current->findNextOp(&chaseArray, &nextStart, &nextEnd,
175 &unsortable, op, xorMask, xorOpMask);
176 if (!next) {
177 if (!unsortable && simple->hasMove()
178 && current->verb() != SkPath::kLine_Verb
179 && !simple->isClosed()) {
180 current->addCurveTo(index, endIndex, simple, true);
181 SkASSERT(simple->isClosed());
182 }
183 break;
184 }
185 #if DEBUG_FLOW
186 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
187 current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
188 current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
189 #endif
190 current->addCurveTo(index, endIndex, simple, true);
191 current = next;
192 index = nextStart;
193 endIndex = nextEnd;
194 } while (!simple->isClosed() && (!unsortable
195 || !current->done(SkMin32(index, endIndex))));
196 if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
197 // FIXME : add to simplify, xor cpaths
198 int min = SkMin32(index, endIndex);
199 if (!unsortable && !simple->isEmpty()) {
200 unsortable = current->checkSmall(min);
201 }
202 SkASSERT(unsortable || simple->isEmpty());
203 if (!current->done(min)) {
204 current->addCurveTo(index, endIndex, simple, true);
205 current->markDoneBinary(min);
206 }
207 }
208 simple->close();
209 } else {
210 SkOpSpan* last = current->markAndChaseDoneBinary(index, endIndex);
211 if (last && !last->fLoop) {
212 *chaseArray.append() = last;
213 }
214 }
215 current = findChaseOp(chaseArray, index, endIndex);
216 #if DEBUG_ACTIVE_SPANS
217 DebugShowActiveSpans(contourList);
218 #endif
219 if (!current) {
220 break;
221 }
222 } while (true);
223 } while (true);
224 return simple->someAssemblyRequired();
225 }
226
227 // pretty picture:
228 // https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing
229 static const SkPathOp gOpInverse[kReverseDifference_PathOp + 1][2][2] = {
230 // inside minuend outside minuend
231 // inside subtrahend outside subtrahend inside subtrahend outside subtrahend
232 {{ kDifference_PathOp, kIntersect_PathOp }, { kUnion_PathOp, kReverseDifference_PathOp }},
233 {{ kIntersect_PathOp, kDifference_PathOp }, { kReverseDifference_PathOp, kUnion_PathOp }},
234 {{ kUnion_PathOp, kReverseDifference_PathOp }, { kDifference_PathOp, kIntersect_PathOp }},
235 {{ kXOR_PathOp, kXOR_PathOp }, { kXOR_PathOp, kXOR_PathOp }},
236 {{ kReverseDifference_PathOp, kUnion_PathOp }, { kIntersect_PathOp, kDifference_PathOp }},
237 };
238
239 static const bool gOutInverse[kReverseDifference_PathOp + 1][2][2] = {
240 {{ false, false }, { true, false }}, // diff
241 {{ false, false }, { false, true }}, // sect
242 {{ false, true }, { true, true }}, // union
243 {{ false, true }, { true, false }}, // xor
244 {{ false, true }, { false, false }}, // rev diff
245 };
246
247 bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
248 #if DEBUG_SHOW_TEST_NAME
249 char* debugName = DEBUG_FILENAME_STRING;
250 if (debugName && debugName[0]) {
251 SkPathOpsDebug::BumpTestName(debugName);
252 SkPathOpsDebug::ShowPath(one, two, op, debugName);
253 }
254 #endif
255 op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
256 SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()]
257 ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType;
258 const SkPath* minuend = &one;
259 const SkPath* subtrahend = &two;
260 if (op == kReverseDifference_PathOp) {
261 minuend = &two;
262 subtrahend = &one;
263 op = kDifference_PathOp;
264 }
265 #if DEBUG_SORT || DEBUG_SWAP_TOP
266 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
267 #endif
268 // turn path into list of segments
269 SkTArray<SkOpContour> contours;
270 // FIXME: add self-intersecting cubics' T values to segment
271 SkOpEdgeBuilder builder(*minuend, contours);
272 const int xorMask = builder.xorMask();
273 builder.addOperand(*subtrahend);
274 if (!builder.finish()) {
275 return false;
276 }
277 result->reset();
278 result->setFillType(fillType);
279 const int xorOpMask = builder.xorMask();
280 SkTArray<SkOpContour*, true> contourList;
281 MakeContourList(contours, contourList, xorMask == kEvenOdd_PathOpsMask,
282 xorOpMask == kEvenOdd_PathOpsMask);
283 SkOpContour** currentPtr = contourList.begin();
284 if (!currentPtr) {
285 return true;
286 }
287 SkOpContour** listEnd = contourList.end();
288 // find all intersections between segments
289 do {
290 SkOpContour** nextPtr = currentPtr;
291 SkOpContour* current = *currentPtr++;
292 if (current->containsCubics()) {
293 AddSelfIntersectTs(current);
294 }
295 SkOpContour* next;
296 do {
297 next = *nextPtr++;
298 } while (AddIntersectTs(current, next) && nextPtr != listEnd);
299 } while (currentPtr != listEnd);
300 // eat through coincident edges
301
302 int total = 0;
303 int index;
304 for (index = 0; index < contourList.count(); ++index) {
305 total += contourList[index]->segments().count();
306 }
307 HandleCoincidence(&contourList, total);
308 // construct closed contours
309 SkPathWriter wrapper(*result);
310 bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper);
311 { // if some edges could not be resolved, assemble remaining fragments
312 SkPath temp;
313 temp.setFillType(fillType);
314 SkPathWriter assembled(temp);
315 Assemble(wrapper, &assembled);
316 *result = *assembled.nativePath();
317 result->setFillType(fillType);
318 }
319 return true;
320 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial