The Tor Browser / file comparison

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

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

branch
TOR_BUG_3246
changeset 7
129ffea94266
equal deleted inserted replaced
-1:000000000000 0:a9d247db7b86
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 #include "SkIntersections.h"
8 #include "SkOpContour.h"
9 #include "SkPathWriter.h"
10 #include "SkTSort.h"
11
12 bool SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex,
13 const SkIntersections& ts, bool swap) {
14 SkPoint pt0 = ts.pt(0).asSkPoint();
15 SkPoint pt1 = ts.pt(1).asSkPoint();
16 if (pt0 == pt1) {
17 // FIXME: one could imagine a case where it would be incorrect to ignore this
18 // suppose two self-intersecting cubics overlap to be coincident --
19 // this needs to check that by some measure the t values are far enough apart
20 // or needs to check to see if the self-intersection bit was set on the cubic segment
21 return false;
22 }
23 SkCoincidence& coincidence = fCoincidences.push_back();
24 coincidence.fOther = other;
25 coincidence.fSegments[0] = index;
26 coincidence.fSegments[1] = otherIndex;
27 coincidence.fTs[swap][0] = ts[0][0];
28 coincidence.fTs[swap][1] = ts[0][1];
29 coincidence.fTs[!swap][0] = ts[1][0];
30 coincidence.fTs[!swap][1] = ts[1][1];
31 coincidence.fPts[0] = pt0;
32 coincidence.fPts[1] = pt1;
33 return true;
34 }
35
36 SkOpSegment* SkOpContour::nonVerticalSegment(int* start, int* end) {
37 int segmentCount = fSortedSegments.count();
38 SkASSERT(segmentCount > 0);
39 for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) {
40 SkOpSegment* testSegment = fSortedSegments[sortedIndex];
41 if (testSegment->done()) {
42 continue;
43 }
44 *start = *end = 0;
45 while (testSegment->nextCandidate(start, end)) {
46 if (!testSegment->isVertical(*start, *end)) {
47 return testSegment;
48 }
49 }
50 }
51 return NULL;
52 }
53
54 // first pass, add missing T values
55 // second pass, determine winding values of overlaps
56 void SkOpContour::addCoincidentPoints() {
57 int count = fCoincidences.count();
58 for (int index = 0; index < count; ++index) {
59 SkCoincidence& coincidence = fCoincidences[index];
60 int thisIndex = coincidence.fSegments[0];
61 SkOpSegment& thisOne = fSegments[thisIndex];
62 SkOpContour* otherContour = coincidence.fOther;
63 int otherIndex = coincidence.fSegments[1];
64 SkOpSegment& other = otherContour->fSegments[otherIndex];
65 if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
66 // OPTIMIZATION: remove from array
67 continue;
68 }
69 #if DEBUG_CONCIDENT
70 thisOne.debugShowTs("-");
71 other.debugShowTs("o");
72 #endif
73 double startT = coincidence.fTs[0][0];
74 double endT = coincidence.fTs[0][1];
75 bool startSwapped, oStartSwapped, cancelers;
76 if ((cancelers = startSwapped = startT > endT)) {
77 SkTSwap(startT, endT);
78 }
79 if (startT == endT) { // if one is very large the smaller may have collapsed to nothing
80 if (endT <= 1 - FLT_EPSILON) {
81 endT += FLT_EPSILON;
82 SkASSERT(endT <= 1);
83 } else {
84 startT -= FLT_EPSILON;
85 SkASSERT(startT >= 0);
86 }
87 }
88 SkASSERT(!approximately_negative(endT - startT));
89 double oStartT = coincidence.fTs[1][0];
90 double oEndT = coincidence.fTs[1][1];
91 if ((oStartSwapped = oStartT > oEndT)) {
92 SkTSwap(oStartT, oEndT);
93 cancelers ^= true;
94 }
95 SkASSERT(!approximately_negative(oEndT - oStartT));
96 if (cancelers) {
97 // make sure startT and endT have t entries
98 const SkPoint& startPt = coincidence.fPts[startSwapped];
99 if (startT > 0 || oEndT < 1
100 || thisOne.isMissing(startT, startPt) || other.isMissing(oEndT, startPt)) {
101 thisOne.addTPair(startT, &other, oEndT, true, startPt);
102 }
103 const SkPoint& oStartPt = coincidence.fPts[oStartSwapped];
104 if (oStartT > 0 || endT < 1
105 || thisOne.isMissing(endT, oStartPt) || other.isMissing(oStartT, oStartPt)) {
106 other.addTPair(oStartT, &thisOne, endT, true, oStartPt);
107 }
108 } else {
109 const SkPoint& startPt = coincidence.fPts[startSwapped];
110 if (startT > 0 || oStartT > 0
111 || thisOne.isMissing(startT, startPt) || other.isMissing(oStartT, startPt)) {
112 thisOne.addTPair(startT, &other, oStartT, true, startPt);
113 }
114 const SkPoint& oEndPt = coincidence.fPts[!oStartSwapped];
115 if (endT < 1 || oEndT < 1
116 || thisOne.isMissing(endT, oEndPt) || other.isMissing(oEndT, oEndPt)) {
117 other.addTPair(oEndT, &thisOne, endT, true, oEndPt);
118 }
119 }
120 #if DEBUG_CONCIDENT
121 thisOne.debugShowTs("+");
122 other.debugShowTs("o");
123 #endif
124 }
125 }
126
127 bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex,
128 const SkIntersections& ts, int ptIndex, bool swap) {
129 SkPoint pt0 = ts.pt(ptIndex).asSkPoint();
130 SkPoint pt1 = ts.pt(ptIndex + 1).asSkPoint();
131 if (SkDPoint::ApproximatelyEqual(pt0, pt1)) {
132 // FIXME: one could imagine a case where it would be incorrect to ignore this
133 // suppose two self-intersecting cubics overlap to form a partial coincidence --
134 // although it isn't clear why the regular coincidence could wouldn't pick this up
135 // this is exceptional enough to ignore for now
136 return false;
137 }
138 SkCoincidence& coincidence = fPartialCoincidences.push_back();
139 coincidence.fOther = other;
140 coincidence.fSegments[0] = index;
141 coincidence.fSegments[1] = otherIndex;
142 coincidence.fTs[swap][0] = ts[0][ptIndex];
143 coincidence.fTs[swap][1] = ts[0][ptIndex + 1];
144 coincidence.fTs[!swap][0] = ts[1][ptIndex];
145 coincidence.fTs[!swap][1] = ts[1][ptIndex + 1];
146 coincidence.fPts[0] = pt0;
147 coincidence.fPts[1] = pt1;
148 return true;
149 }
150
151 void SkOpContour::calcCoincidentWinding() {
152 int count = fCoincidences.count();
153 #if DEBUG_CONCIDENT
154 if (count > 0) {
155 SkDebugf("%s count=%d\n", __FUNCTION__, count);
156 }
157 #endif
158 for (int index = 0; index < count; ++index) {
159 SkCoincidence& coincidence = fCoincidences[index];
160 calcCommonCoincidentWinding(coincidence);
161 }
162 }
163
164 void SkOpContour::calcPartialCoincidentWinding() {
165 int count = fPartialCoincidences.count();
166 #if DEBUG_CONCIDENT
167 if (count > 0) {
168 SkDebugf("%s count=%d\n", __FUNCTION__, count);
169 }
170 #endif
171 for (int index = 0; index < count; ++index) {
172 SkCoincidence& coincidence = fPartialCoincidences[index];
173 calcCommonCoincidentWinding(coincidence);
174 }
175 }
176
177 void SkOpContour::joinCoincidence(const SkTArray<SkCoincidence, true>& coincidences, bool partial) {
178 int count = coincidences.count();
179 #if DEBUG_CONCIDENT
180 if (count > 0) {
181 SkDebugf("%s count=%d\n", __FUNCTION__, count);
182 }
183 #endif
184 // look for a lineup where the partial implies another adjoining coincidence
185 for (int index = 0; index < count; ++index) {
186 const SkCoincidence& coincidence = coincidences[index];
187 int thisIndex = coincidence.fSegments[0];
188 SkOpSegment& thisOne = fSegments[thisIndex];
189 SkOpContour* otherContour = coincidence.fOther;
190 int otherIndex = coincidence.fSegments[1];
191 SkOpSegment& other = otherContour->fSegments[otherIndex];
192 double startT = coincidence.fTs[0][0];
193 double endT = coincidence.fTs[0][1];
194 if (startT == endT) { // this can happen in very large compares
195 continue;
196 }
197 double oStartT = coincidence.fTs[1][0];
198 double oEndT = coincidence.fTs[1][1];
199 if (oStartT == oEndT) {
200 continue;
201 }
202 bool swapStart = startT > endT;
203 bool swapOther = oStartT > oEndT;
204 if (swapStart) {
205 SkTSwap<double>(startT, endT);
206 SkTSwap<double>(oStartT, oEndT);
207 }
208 bool cancel = swapOther != swapStart;
209 int step = swapStart ? -1 : 1;
210 int oStep = swapOther ? -1 : 1;
211 double oMatchStart = cancel ? oEndT : oStartT;
212 if (partial ? startT != 0 || oMatchStart != 0 : (startT == 0) != (oMatchStart == 0)) {
213 bool added = false;
214 if (oMatchStart != 0) {
215 added = thisOne.joinCoincidence(&other, oMatchStart, oStep, cancel);
216 }
217 if (!cancel && startT != 0 && !added) {
218 (void) other.joinCoincidence(&thisOne, startT, step, cancel);
219 }
220 }
221 double oMatchEnd = cancel ? oStartT : oEndT;
222 if (partial ? endT != 1 || oMatchEnd != 1 : (endT == 1) != (oMatchEnd == 1)) {
223 bool added = false;
224 if (cancel && endT != 1 && !added) {
225 (void) other.joinCoincidence(&thisOne, endT, -step, cancel);
226 }
227 }
228 }
229 }
230
231 void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) {
232 int thisIndex = coincidence.fSegments[0];
233 SkOpSegment& thisOne = fSegments[thisIndex];
234 if (thisOne.done()) {
235 return;
236 }
237 SkOpContour* otherContour = coincidence.fOther;
238 int otherIndex = coincidence.fSegments[1];
239 SkOpSegment& other = otherContour->fSegments[otherIndex];
240 if (other.done()) {
241 return;
242 }
243 double startT = coincidence.fTs[0][0];
244 double endT = coincidence.fTs[0][1];
245 const SkPoint* startPt = &coincidence.fPts[0];
246 const SkPoint* endPt = &coincidence.fPts[1];
247 bool cancelers;
248 if ((cancelers = startT > endT)) {
249 SkTSwap<double>(startT, endT);
250 SkTSwap<const SkPoint*>(startPt, endPt);
251 }
252 if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing
253 if (endT <= 1 - FLT_EPSILON) {
254 endT += FLT_EPSILON;
255 SkASSERT(endT <= 1);
256 } else {
257 startT -= FLT_EPSILON;
258 SkASSERT(startT >= 0);
259 }
260 }
261 SkASSERT(!approximately_negative(endT - startT));
262 double oStartT = coincidence.fTs[1][0];
263 double oEndT = coincidence.fTs[1][1];
264 if (oStartT > oEndT) {
265 SkTSwap<double>(oStartT, oEndT);
266 cancelers ^= true;
267 }
268 SkASSERT(!approximately_negative(oEndT - oStartT));
269 if (cancelers) {
270 thisOne.addTCancel(*startPt, *endPt, &other);
271 } else {
272 thisOne.addTCoincident(*startPt, *endPt, endT, &other);
273 }
274 #if DEBUG_CONCIDENT
275 thisOne.debugShowTs("p");
276 other.debugShowTs("o");
277 #endif
278 }
279
280 void SkOpContour::sortSegments() {
281 int segmentCount = fSegments.count();
282 fSortedSegments.push_back_n(segmentCount);
283 for (int test = 0; test < segmentCount; ++test) {
284 fSortedSegments[test] = &fSegments[test];
285 }
286 SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
287 fFirstSorted = 0;
288 }
289
290 void SkOpContour::toPath(SkPathWriter* path) const {
291 int segmentCount = fSegments.count();
292 const SkPoint& pt = fSegments.front().pts()[0];
293 path->deferredMove(pt);
294 for (int test = 0; test < segmentCount; ++test) {
295 fSegments[test].addCurveTo(0, 1, path, true);
296 }
297 path->close();
298 }
299
300 void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY,
301 SkOpSegment** topStart) {
302 int segmentCount = fSortedSegments.count();
303 SkASSERT(segmentCount > 0);
304 int sortedIndex = fFirstSorted;
305 fDone = true; // may be cleared below
306 for ( ; sortedIndex < segmentCount; ++sortedIndex) {
307 SkOpSegment* testSegment = fSortedSegments[sortedIndex];
308 if (testSegment->done()) {
309 if (sortedIndex == fFirstSorted) {
310 ++fFirstSorted;
311 }
312 continue;
313 }
314 fDone = false;
315 SkPoint testXY = testSegment->activeLeftTop(true, NULL);
316 if (*topStart) {
317 if (testXY.fY < topLeft.fY) {
318 continue;
319 }
320 if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) {
321 continue;
322 }
323 if (bestXY->fY < testXY.fY) {
324 continue;
325 }
326 if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) {
327 continue;
328 }
329 }
330 *topStart = testSegment;
331 *bestXY = testXY;
332 }
333 }
334
335 SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) {
336 int segmentCount = fSegments.count();
337 for (int test = 0; test < segmentCount; ++test) {
338 SkOpSegment* testSegment = &fSegments[test];
339 if (testSegment->done()) {
340 continue;
341 }
342 testSegment->undoneSpan(start, end);
343 return testSegment;
344 }
345 return NULL;
346 }
347
348 #if DEBUG_SHOW_WINDING
349 int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) {
350 int count = fSegments.count();
351 int sum = 0;
352 for (int index = 0; index < count; ++index) {
353 sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest);
354 }
355 // SkDebugf("%s sum=%d\n", __FUNCTION__, sum);
356 return sum;
357 }
358
359 void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) {
360 // int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13;
361 // int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16;
362 int ofInterest = 1 << 5 | 1 << 8;
363 int total = 0;
364 int index;
365 for (index = 0; index < contourList.count(); ++index) {
366 total += contourList[index]->segments().count();
367 }
368 int sum = 0;
369 for (index = 0; index < contourList.count(); ++index) {
370 sum += contourList[index]->debugShowWindingValues(total, ofInterest);
371 }
372 // SkDebugf("%s total=%d\n", __FUNCTION__, sum);
373 }
374 #endif
375
376 void SkOpContour::setBounds() {
377 int count = fSegments.count();
378 if (count == 0) {
379 SkDebugf("%s empty contour\n", __FUNCTION__);
380 SkASSERT(0);
381 // FIXME: delete empty contour?
382 return;
383 }
384 fBounds = fSegments.front().bounds();
385 for (int index = 1; index < count; ++index) {
386 fBounds.add(fSegments[index].bounds());
387 }
388 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial