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