Line data Source code
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 "SkGeometry.h"
8 : #include "SkOpEdgeBuilder.h"
9 : #include "SkReduceOrder.h"
10 :
11 0 : void SkOpEdgeBuilder::init() {
12 0 : fOperand = false;
13 0 : fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
14 : : kWinding_PathOpsMask;
15 0 : fUnparseable = false;
16 0 : fSecondHalf = preFetch();
17 0 : }
18 :
19 : // very tiny points cause numerical instability : don't allow them
20 0 : static void force_small_to_zero(SkPoint* pt) {
21 0 : if (SkScalarAbs(pt->fX) < FLT_EPSILON_ORDERABLE_ERR) {
22 0 : pt->fX = 0;
23 : }
24 0 : if (SkScalarAbs(pt->fY) < FLT_EPSILON_ORDERABLE_ERR) {
25 0 : pt->fY = 0;
26 : }
27 0 : }
28 :
29 0 : static bool can_add_curve(SkPath::Verb verb, SkPoint* curve) {
30 0 : if (SkPath::kMove_Verb == verb) {
31 0 : return false;
32 : }
33 0 : for (int index = 0; index <= SkPathOpsVerbToPoints(verb); ++index) {
34 0 : force_small_to_zero(&curve[index]);
35 : }
36 0 : return SkPath::kLine_Verb != verb || !SkDPoint::ApproximatelyEqual(curve[0], curve[1]);
37 : }
38 :
39 0 : void SkOpEdgeBuilder::addOperand(const SkPath& path) {
40 0 : SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb);
41 0 : fPathVerbs.pop();
42 0 : fPath = &path;
43 0 : fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
44 : : kWinding_PathOpsMask;
45 0 : preFetch();
46 0 : }
47 :
48 0 : bool SkOpEdgeBuilder::finish() {
49 0 : fOperand = false;
50 0 : if (fUnparseable || !walk()) {
51 0 : return false;
52 : }
53 0 : complete();
54 0 : SkOpContour* contour = fContourBuilder.contour();
55 0 : if (contour && !contour->count()) {
56 0 : fContoursHead->remove(contour);
57 : }
58 0 : return true;
59 : }
60 :
61 0 : void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) {
62 0 : if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) {
63 0 : *fPathVerbs.append() = SkPath::kLine_Verb;
64 0 : *fPathPts.append() = curveStart;
65 : } else {
66 0 : int verbCount = fPathVerbs.count();
67 0 : int ptsCount = fPathPts.count();
68 0 : if (SkPath::kLine_Verb == fPathVerbs[verbCount - 1]
69 0 : && fPathPts[ptsCount - 2] == curveStart) {
70 0 : fPathVerbs.pop();
71 0 : fPathPts.pop();
72 : } else {
73 0 : fPathPts[ptsCount - 1] = curveStart;
74 : }
75 : }
76 0 : *fPathVerbs.append() = SkPath::kClose_Verb;
77 0 : }
78 :
79 0 : int SkOpEdgeBuilder::preFetch() {
80 0 : if (!fPath->isFinite()) {
81 0 : fUnparseable = true;
82 0 : return 0;
83 : }
84 0 : SkPath::RawIter iter(*fPath);
85 : SkPoint curveStart;
86 : SkPoint curve[4];
87 : SkPoint pts[4];
88 : SkPath::Verb verb;
89 0 : bool lastCurve = false;
90 0 : do {
91 0 : verb = iter.next(pts);
92 0 : switch (verb) {
93 : case SkPath::kMove_Verb:
94 0 : if (!fAllowOpenContours && lastCurve) {
95 0 : closeContour(curve[0], curveStart);
96 : }
97 0 : *fPathVerbs.append() = verb;
98 0 : force_small_to_zero(&pts[0]);
99 0 : *fPathPts.append() = pts[0];
100 0 : curveStart = curve[0] = pts[0];
101 0 : lastCurve = false;
102 0 : continue;
103 : case SkPath::kLine_Verb:
104 0 : force_small_to_zero(&pts[1]);
105 0 : if (SkDPoint::ApproximatelyEqual(curve[0], pts[1])) {
106 0 : uint8_t lastVerb = fPathVerbs.top();
107 0 : if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) {
108 0 : fPathPts.top() = curve[0] = pts[1];
109 : }
110 0 : continue; // skip degenerate points
111 : }
112 0 : break;
113 : case SkPath::kQuad_Verb:
114 0 : force_small_to_zero(&pts[1]);
115 0 : force_small_to_zero(&pts[2]);
116 0 : curve[1] = pts[1];
117 0 : curve[2] = pts[2];
118 0 : verb = SkReduceOrder::Quad(curve, pts);
119 0 : if (verb == SkPath::kMove_Verb) {
120 0 : continue; // skip degenerate points
121 : }
122 0 : break;
123 : case SkPath::kConic_Verb:
124 0 : force_small_to_zero(&pts[1]);
125 0 : force_small_to_zero(&pts[2]);
126 0 : curve[1] = pts[1];
127 0 : curve[2] = pts[2];
128 0 : verb = SkReduceOrder::Quad(curve, pts);
129 0 : if (SkPath::kQuad_Verb == verb && 1 != iter.conicWeight()) {
130 0 : verb = SkPath::kConic_Verb;
131 0 : } else if (verb == SkPath::kMove_Verb) {
132 0 : continue; // skip degenerate points
133 : }
134 0 : break;
135 : case SkPath::kCubic_Verb:
136 0 : force_small_to_zero(&pts[1]);
137 0 : force_small_to_zero(&pts[2]);
138 0 : force_small_to_zero(&pts[3]);
139 0 : curve[1] = pts[1];
140 0 : curve[2] = pts[2];
141 0 : curve[3] = pts[3];
142 0 : verb = SkReduceOrder::Cubic(curve, pts);
143 0 : if (verb == SkPath::kMove_Verb) {
144 0 : continue; // skip degenerate points
145 : }
146 0 : break;
147 : case SkPath::kClose_Verb:
148 0 : closeContour(curve[0], curveStart);
149 0 : lastCurve = false;
150 0 : continue;
151 : case SkPath::kDone_Verb:
152 0 : continue;
153 : }
154 0 : *fPathVerbs.append() = verb;
155 0 : int ptCount = SkPathOpsVerbToPoints(verb);
156 0 : fPathPts.append(ptCount, &pts[1]);
157 0 : if (verb == SkPath::kConic_Verb) {
158 0 : *fWeights.append() = iter.conicWeight();
159 : }
160 0 : curve[0] = pts[ptCount];
161 0 : lastCurve = true;
162 0 : } while (verb != SkPath::kDone_Verb);
163 0 : if (!fAllowOpenContours && lastCurve) {
164 0 : closeContour(curve[0], curveStart);
165 : }
166 0 : *fPathVerbs.append() = SkPath::kDone_Verb;
167 0 : return fPathVerbs.count() - 1;
168 : }
169 :
170 0 : bool SkOpEdgeBuilder::close() {
171 0 : complete();
172 0 : return true;
173 : }
174 :
175 0 : bool SkOpEdgeBuilder::walk() {
176 0 : uint8_t* verbPtr = fPathVerbs.begin();
177 0 : uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
178 0 : SkPoint* pointsPtr = fPathPts.begin() - 1;
179 0 : SkScalar* weightPtr = fWeights.begin();
180 : SkPath::Verb verb;
181 0 : SkOpContour* contour = fContourBuilder.contour();
182 0 : while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) {
183 0 : if (verbPtr == endOfFirstHalf) {
184 0 : fOperand = true;
185 : }
186 0 : verbPtr++;
187 0 : switch (verb) {
188 : case SkPath::kMove_Verb:
189 0 : if (contour && contour->count()) {
190 0 : if (fAllowOpenContours) {
191 0 : complete();
192 0 : } else if (!close()) {
193 0 : return false;
194 : }
195 : }
196 0 : if (!contour) {
197 0 : fContourBuilder.setContour(contour = fContoursHead->appendContour());
198 : }
199 0 : contour->init(fGlobalState, fOperand,
200 0 : fXorMask[fOperand] == kEvenOdd_PathOpsMask);
201 0 : pointsPtr += 1;
202 0 : continue;
203 : case SkPath::kLine_Verb:
204 0 : fContourBuilder.addLine(pointsPtr);
205 0 : break;
206 : case SkPath::kQuad_Verb:
207 : {
208 0 : SkVector v1 = pointsPtr[1] - pointsPtr[0];
209 0 : SkVector v2 = pointsPtr[2] - pointsPtr[1];
210 0 : if (v1.dot(v2) < 0) {
211 : SkPoint pair[5];
212 0 : if (SkChopQuadAtMaxCurvature(pointsPtr, pair) == 1) {
213 0 : goto addOneQuad;
214 : }
215 0 : if (!SkScalarsAreFinite(&pair[0].fX, SK_ARRAY_COUNT(pair) * 2)) {
216 0 : return false;
217 : }
218 : SkPoint cStorage[2][2];
219 0 : SkPath::Verb v1 = SkReduceOrder::Quad(&pair[0], cStorage[0]);
220 0 : SkPath::Verb v2 = SkReduceOrder::Quad(&pair[2], cStorage[1]);
221 0 : SkPoint* curve1 = v1 != SkPath::kLine_Verb ? &pair[0] : cStorage[0];
222 0 : SkPoint* curve2 = v2 != SkPath::kLine_Verb ? &pair[2] : cStorage[1];
223 0 : if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
224 0 : fContourBuilder.addCurve(v1, curve1);
225 0 : fContourBuilder.addCurve(v2, curve2);
226 0 : break;
227 : }
228 : }
229 : }
230 : addOneQuad:
231 0 : fContourBuilder.addQuad(pointsPtr);
232 0 : break;
233 : case SkPath::kConic_Verb: {
234 0 : SkVector v1 = pointsPtr[1] - pointsPtr[0];
235 0 : SkVector v2 = pointsPtr[2] - pointsPtr[1];
236 0 : SkScalar weight = *weightPtr++;
237 0 : if (v1.dot(v2) < 0) {
238 : // FIXME: max curvature for conics hasn't been implemented; use placeholder
239 0 : SkScalar maxCurvature = SkFindQuadMaxCurvature(pointsPtr);
240 0 : if (maxCurvature > 0) {
241 0 : SkConic conic(pointsPtr, weight);
242 0 : SkConic pair[2];
243 0 : if (!conic.chopAt(maxCurvature, pair)) {
244 : // if result can't be computed, use original
245 0 : fContourBuilder.addConic(pointsPtr, weight);
246 0 : break;
247 : }
248 : SkPoint cStorage[2][3];
249 0 : SkPath::Verb v1 = SkReduceOrder::Conic(pair[0], cStorage[0]);
250 0 : SkPath::Verb v2 = SkReduceOrder::Conic(pair[1], cStorage[1]);
251 0 : SkPoint* curve1 = v1 != SkPath::kLine_Verb ? pair[0].fPts : cStorage[0];
252 0 : SkPoint* curve2 = v2 != SkPath::kLine_Verb ? pair[1].fPts : cStorage[1];
253 0 : if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
254 0 : fContourBuilder.addCurve(v1, curve1, pair[0].fW);
255 0 : fContourBuilder.addCurve(v2, curve2, pair[1].fW);
256 0 : break;
257 : }
258 : }
259 : }
260 0 : fContourBuilder.addConic(pointsPtr, weight);
261 0 : } break;
262 : case SkPath::kCubic_Verb:
263 : {
264 : // Split complex cubics (such as self-intersecting curves or
265 : // ones with difficult curvature) in two before proceeding.
266 : // This can be required for intersection to succeed.
267 : SkScalar splitT[3];
268 0 : int breaks = SkDCubic::ComplexBreak(pointsPtr, splitT);
269 0 : if (!breaks) {
270 0 : fContourBuilder.addCubic(pointsPtr);
271 0 : break;
272 : }
273 0 : SkASSERT(breaks <= (int) SK_ARRAY_COUNT(splitT));
274 : struct Splitsville {
275 : double fT[2];
276 : SkPoint fPts[4];
277 : SkPoint fReduced[4];
278 : SkPath::Verb fVerb;
279 : bool fCanAdd;
280 : } splits[4];
281 : SkASSERT(SK_ARRAY_COUNT(splits) == SK_ARRAY_COUNT(splitT) + 1);
282 0 : SkTQSort(splitT, &splitT[breaks - 1]);
283 0 : for (int index = 0; index <= breaks; ++index) {
284 0 : Splitsville* split = &splits[index];
285 0 : split->fT[0] = index ? splitT[index - 1] : 0;
286 0 : split->fT[1] = index < breaks ? splitT[index] : 1;
287 0 : SkDCubic part = SkDCubic::SubDivide(pointsPtr, split->fT[0], split->fT[1]);
288 0 : if (!part.toFloatPoints(split->fPts)) {
289 0 : return false;
290 : }
291 0 : split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced);
292 : SkPoint* curve = SkPath::kCubic_Verb == verb
293 0 : ? split->fPts : split->fReduced;
294 0 : split->fCanAdd = can_add_curve(split->fVerb, curve);
295 : }
296 0 : for (int index = 0; index <= breaks; ++index) {
297 0 : Splitsville* split = &splits[index];
298 0 : if (!split->fCanAdd) {
299 0 : continue;
300 : }
301 0 : int prior = index;
302 0 : while (prior > 0 && !splits[prior - 1].fCanAdd) {
303 0 : --prior;
304 : }
305 0 : if (prior < index) {
306 0 : split->fT[0] = splits[prior].fT[0];
307 : }
308 0 : int next = index;
309 0 : while (next < breaks && !splits[next + 1].fCanAdd) {
310 0 : ++next;
311 : }
312 0 : if (next > index) {
313 0 : split->fT[1] = splits[next].fT[1];
314 : }
315 0 : if (prior < index || next > index) {
316 0 : if (0 == split->fT[0] && 1 == split->fT[1]) {
317 0 : fContourBuilder.addCubic(pointsPtr);
318 0 : break;
319 : }
320 : SkDCubic part = SkDCubic::SubDivide(pointsPtr, split->fT[0],
321 0 : split->fT[1]);
322 0 : if (!part.toFloatPoints(split->fPts)) {
323 0 : return false;
324 : }
325 0 : split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced);
326 : }
327 0 : SkPoint* curve = SkPath::kCubic_Verb == split->fVerb
328 0 : ? split->fPts : split->fReduced;
329 0 : SkAssertResult(can_add_curve(split->fVerb, curve));
330 0 : fContourBuilder.addCurve(split->fVerb, curve);
331 : }
332 : }
333 0 : break;
334 : case SkPath::kClose_Verb:
335 0 : SkASSERT(contour);
336 0 : if (!close()) {
337 0 : return false;
338 : }
339 0 : contour = nullptr;
340 0 : continue;
341 : default:
342 0 : SkDEBUGFAIL("bad verb");
343 0 : return false;
344 : }
345 0 : SkASSERT(contour);
346 0 : if (contour->count()) {
347 0 : contour->debugValidate();
348 : }
349 0 : pointsPtr += SkPathOpsVerbToPoints(verb);
350 : }
351 0 : fContourBuilder.flush();
352 0 : if (contour && contour->count() &&!fAllowOpenContours && !close()) {
353 0 : return false;
354 : }
355 0 : return true;
356 : }
|
