gfx/skia/trunk/src/pathops/SkPathOpsSimplify.cpp@6474c204b198
gfx/skia/trunk/src/pathops/SkPathOpsSimplify.cpp
Wed, 31 Dec 2014 06:09:35 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Wed, 31 Dec 2014 06:09:35 +0100
- changeset 0
- 6474c204b198
- permissions
- -rw-r--r--
Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.
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"
12 static bool bridgeWinding(SkTArray<SkOpContour*, true>& contourList, SkPathWriter* simple) {
13 bool firstContour = true;
14 bool unsortable = false;
15 bool topUnsortable = false;
16 SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
17 do {
18 int index, endIndex;
19 bool topDone;
20 SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kUnaryWinding, &firstContour,
21 &index, &endIndex, &topLeft, &topUnsortable, &topDone);
22 if (!current) {
23 if (topUnsortable || !topDone) {
24 topUnsortable = false;
25 SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
26 topLeft.fX = topLeft.fY = SK_ScalarMin;
27 continue;
28 }
29 break;
30 }
31 SkTDArray<SkOpSpan*> chaseArray;
32 do {
33 if (current->activeWinding(index, endIndex)) {
34 do {
35 if (!unsortable && current->done()) {
36 #if DEBUG_ACTIVE_SPANS
37 DebugShowActiveSpans(contourList);
38 #endif
39 if (simple->isEmpty()) {
40 simple->init();
41 break;
42 }
43 }
44 SkASSERT(unsortable || !current->done());
45 int nextStart = index;
46 int nextEnd = endIndex;
47 SkOpSegment* next = current->findNextWinding(&chaseArray, &nextStart, &nextEnd,
48 &unsortable);
49 if (!next) {
50 if (!unsortable && simple->hasMove()
51 && current->verb() != SkPath::kLine_Verb
52 && !simple->isClosed()) {
53 current->addCurveTo(index, endIndex, simple, true);
54 SkASSERT(simple->isClosed());
55 }
56 break;
57 }
58 #if DEBUG_FLOW
59 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
60 current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
61 current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
62 #endif
63 current->addCurveTo(index, endIndex, simple, true);
64 current = next;
65 index = nextStart;
66 endIndex = nextEnd;
67 } while (!simple->isClosed() && (!unsortable
68 || !current->done(SkMin32(index, endIndex))));
69 if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
70 SkASSERT(unsortable || simple->isEmpty());
71 int min = SkMin32(index, endIndex);
72 if (!current->done(min)) {
73 current->addCurveTo(index, endIndex, simple, true);
74 current->markDoneUnary(min);
75 }
76 }
77 simple->close();
78 } else {
79 SkOpSpan* last = current->markAndChaseDoneUnary(index, endIndex);
80 if (last && !last->fLoop) {
81 *chaseArray.append() = last;
82 }
83 }
84 current = FindChase(chaseArray, index, endIndex);
85 #if DEBUG_ACTIVE_SPANS
86 DebugShowActiveSpans(contourList);
87 #endif
88 if (!current) {
89 break;
90 }
91 } while (true);
92 } while (true);
93 return simple->someAssemblyRequired();
94 }
96 // returns true if all edges were processed
97 static bool bridgeXor(SkTArray<SkOpContour*, true>& contourList, SkPathWriter* simple) {
98 SkOpSegment* current;
99 int start, 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 int nextStart = start;
111 int 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 SkASSERT(simple->isClosed());
119 }
120 break;
121 }
122 #if DEBUG_FLOW
123 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
124 current->debugID(), current->xyAtT(start).fX, current->xyAtT(start).fY,
125 current->xyAtT(end).fX, current->xyAtT(end).fY);
126 #endif
127 current->addCurveTo(start, end, simple, true);
128 current = next;
129 start = nextStart;
130 end = nextEnd;
131 } while (!simple->isClosed() && (!unsortable || !current->done(SkMin32(start, end))));
132 if (!simple->isClosed()) {
133 SkASSERT(unsortable);
134 int min = SkMin32(start, end);
135 if (!current->done(min)) {
136 current->addCurveTo(start, end, simple, true);
137 current->markDone(min, 1);
138 }
139 closable = false;
140 }
141 simple->close();
142 #if DEBUG_ACTIVE_SPANS
143 DebugShowActiveSpans(contourList);
144 #endif
145 }
146 return closable;
147 }
149 // FIXME : add this as a member of SkPath
150 bool Simplify(const SkPath& path, SkPath* result) {
151 #if DEBUG_SORT || DEBUG_SWAP_TOP
152 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
153 #endif
154 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
155 SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenOdd_FillType
156 : SkPath::kEvenOdd_FillType;
158 // turn path into list of segments
159 SkTArray<SkOpContour> contours;
160 SkOpEdgeBuilder builder(path, contours);
161 if (!builder.finish()) {
162 return false;
163 }
164 SkTArray<SkOpContour*, true> contourList;
165 MakeContourList(contours, contourList, false, false);
166 SkOpContour** currentPtr = contourList.begin();
167 result->reset();
168 result->setFillType(fillType);
169 if (!currentPtr) {
170 return true;
171 }
172 SkOpContour** listEnd = contourList.end();
173 // find all intersections between segments
174 do {
175 SkOpContour** nextPtr = currentPtr;
176 SkOpContour* current = *currentPtr++;
177 if (current->containsCubics()) {
178 AddSelfIntersectTs(current);
179 }
180 SkOpContour* next;
181 do {
182 next = *nextPtr++;
183 } while (AddIntersectTs(current, next) && nextPtr != listEnd);
184 } while (currentPtr != listEnd);
185 HandleCoincidence(&contourList, 0);
186 // construct closed contours
187 SkPathWriter simple(*result);
188 if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &simple)
189 : !bridgeXor(contourList, &simple))
190 { // if some edges could not be resolved, assemble remaining fragments
191 SkPath temp;
192 temp.setFillType(fillType);
193 SkPathWriter assembled(temp);
194 Assemble(simple, &assembled);
195 *result = *assembled.nativePath();
196 result->setFillType(fillType);
197 }
198 return true;
199 }
