OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2012 Google Inc. | 2 * Copyright 2012 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 #include "SkGeometry.h" | 7 #include "SkGeometry.h" |
8 #include "SkOpEdgeBuilder.h" | 8 #include "SkOpEdgeBuilder.h" |
9 #include "SkReduceOrder.h" | 9 #include "SkReduceOrder.h" |
10 | 10 |
11 void SkOpEdgeBuilder::init() { | 11 void SkOpEdgeBuilder::init() { |
12 fCurrentContour = fContoursHead; | 12 fCurrentContour = fContoursHead; |
13 fOperand = false; | 13 fOperand = false; |
14 fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMas
k | 14 fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMas
k |
15 : kWinding_PathOpsMask; | 15 : kWinding_PathOpsMask; |
16 fUnparseable = false; | 16 fUnparseable = false; |
17 fSecondHalf = preFetch(); | 17 fSecondHalf = preFetch(); |
18 } | 18 } |
19 | 19 |
| 20 // very tiny points cause numerical instability : don't allow them |
| 21 static void force_small_to_zero(SkPoint* pt) { |
| 22 if (SkScalarAbs(pt->fX) < FLT_EPSILON_ORDERABLE_ERR) { |
| 23 pt->fX = 0; |
| 24 } |
| 25 if (SkScalarAbs(pt->fY) < FLT_EPSILON_ORDERABLE_ERR) { |
| 26 pt->fY = 0; |
| 27 } |
| 28 } |
| 29 |
| 30 static bool can_add_curve(SkPath::Verb verb, SkPoint* curve) { |
| 31 if (SkPath::kMove_Verb == verb) { |
| 32 return false; |
| 33 } |
| 34 for (int index = 0; index < SkPathOpsVerbToPoints(verb); ++index) { |
| 35 force_small_to_zero(&curve[index]); |
| 36 } |
| 37 return SkPath::kLine_Verb != verb || !SkDPoint::ApproximatelyEqual(curve[0],
curve[1]); |
| 38 } |
| 39 |
20 void SkOpEdgeBuilder::addOperand(const SkPath& path) { | 40 void SkOpEdgeBuilder::addOperand(const SkPath& path) { |
21 SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Ver
b); | 41 SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Ver
b); |
22 fPathVerbs.pop(); | 42 fPathVerbs.pop(); |
23 fPath = &path; | 43 fPath = &path; |
24 fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask | 44 fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask |
25 : kWinding_PathOpsMask; | 45 : kWinding_PathOpsMask; |
26 preFetch(); | 46 preFetch(); |
27 } | 47 } |
28 | 48 |
29 bool SkOpEdgeBuilder::finish() { | 49 bool SkOpEdgeBuilder::finish() { |
(...skipping 11 matching lines...) Expand all Loading... |
41 void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curve
Start) { | 61 void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curve
Start) { |
42 if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) { | 62 if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) { |
43 *fPathVerbs.append() = SkPath::kLine_Verb; | 63 *fPathVerbs.append() = SkPath::kLine_Verb; |
44 *fPathPts.append() = curveStart; | 64 *fPathPts.append() = curveStart; |
45 } else { | 65 } else { |
46 fPathPts[fPathPts.count() - 1] = curveStart; | 66 fPathPts[fPathPts.count() - 1] = curveStart; |
47 } | 67 } |
48 *fPathVerbs.append() = SkPath::kClose_Verb; | 68 *fPathVerbs.append() = SkPath::kClose_Verb; |
49 } | 69 } |
50 | 70 |
51 // very tiny points cause numerical instability : don't allow them | |
52 static void force_small_to_zero(SkPoint* pt) { | |
53 if (SkScalarAbs(pt->fX) < FLT_EPSILON_ORDERABLE_ERR) { | |
54 pt->fX = 0; | |
55 } | |
56 if (SkScalarAbs(pt->fY) < FLT_EPSILON_ORDERABLE_ERR) { | |
57 pt->fY = 0; | |
58 } | |
59 } | |
60 | |
61 int SkOpEdgeBuilder::preFetch() { | 71 int SkOpEdgeBuilder::preFetch() { |
62 if (!fPath->isFinite()) { | 72 if (!fPath->isFinite()) { |
63 fUnparseable = true; | 73 fUnparseable = true; |
64 return 0; | 74 return 0; |
65 } | 75 } |
66 SkPath::RawIter iter(*fPath); | 76 SkPath::RawIter iter(*fPath); |
67 SkPoint curveStart; | 77 SkPoint curveStart; |
68 SkPoint curve[4]; | 78 SkPoint curve[4]; |
69 SkPoint pts[4]; | 79 SkPoint pts[4]; |
70 SkPath::Verb verb; | 80 SkPath::Verb verb; |
(...skipping 29 matching lines...) Expand all Loading... |
100 verb = SkReduceOrder::Quad(curve, pts); | 110 verb = SkReduceOrder::Quad(curve, pts); |
101 if (verb == SkPath::kMove_Verb) { | 111 if (verb == SkPath::kMove_Verb) { |
102 continue; // skip degenerate points | 112 continue; // skip degenerate points |
103 } | 113 } |
104 break; | 114 break; |
105 case SkPath::kConic_Verb: | 115 case SkPath::kConic_Verb: |
106 force_small_to_zero(&pts[1]); | 116 force_small_to_zero(&pts[1]); |
107 force_small_to_zero(&pts[2]); | 117 force_small_to_zero(&pts[2]); |
108 curve[1] = pts[1]; | 118 curve[1] = pts[1]; |
109 curve[2] = pts[2]; | 119 curve[2] = pts[2]; |
110 verb = SkReduceOrder::Conic(curve, iter.conicWeight(), pts); | 120 verb = SkReduceOrder::Quad(curve, pts); |
111 if (verb == SkPath::kMove_Verb) { | 121 if (SkPath::kQuad_Verb == verb && 1 != iter.conicWeight()) { |
| 122 verb = SkPath::kConic_Verb; |
| 123 } else if (verb == SkPath::kMove_Verb) { |
112 continue; // skip degenerate points | 124 continue; // skip degenerate points |
113 } | 125 } |
114 break; | 126 break; |
115 case SkPath::kCubic_Verb: | 127 case SkPath::kCubic_Verb: |
116 force_small_to_zero(&pts[1]); | 128 force_small_to_zero(&pts[1]); |
117 force_small_to_zero(&pts[2]); | 129 force_small_to_zero(&pts[2]); |
118 force_small_to_zero(&pts[3]); | 130 force_small_to_zero(&pts[3]); |
119 curve[1] = pts[1]; | 131 curve[1] = pts[1]; |
120 curve[2] = pts[2]; | 132 curve[2] = pts[2]; |
121 curve[3] = pts[3]; | 133 curve[3] = pts[3]; |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
176 fCurrentContour = fContoursHead->appendContour(); | 188 fCurrentContour = fContoursHead->appendContour(); |
177 } | 189 } |
178 fCurrentContour->init(fGlobalState, fOperand, | 190 fCurrentContour->init(fGlobalState, fOperand, |
179 fXorMask[fOperand] == kEvenOdd_PathOpsMask); | 191 fXorMask[fOperand] == kEvenOdd_PathOpsMask); |
180 pointsPtr += 1; | 192 pointsPtr += 1; |
181 continue; | 193 continue; |
182 case SkPath::kLine_Verb: | 194 case SkPath::kLine_Verb: |
183 fCurrentContour->addLine(pointsPtr); | 195 fCurrentContour->addLine(pointsPtr); |
184 break; | 196 break; |
185 case SkPath::kQuad_Verb: | 197 case SkPath::kQuad_Verb: |
| 198 { |
| 199 SkVector v1 = pointsPtr[1] - pointsPtr[0]; |
| 200 SkVector v2 = pointsPtr[2] - pointsPtr[1]; |
| 201 if (v1.dot(v2) < 0) { |
| 202 SkPoint pair[5]; |
| 203 if (SkChopQuadAtMaxCurvature(pointsPtr, pair) == 1) { |
| 204 goto addOneQuad; |
| 205 } |
| 206 if (!SkScalarsAreFinite(&pair[0].fX, SK_ARRAY_COUNT(pair
) * 2)) { |
| 207 return false; |
| 208 } |
| 209 SkPoint cStorage[2][2]; |
| 210 SkPath::Verb v1 = SkReduceOrder::Quad(&pair[0], cStorage
[0]); |
| 211 SkPath::Verb v2 = SkReduceOrder::Quad(&pair[2], cStorage
[1]); |
| 212 SkPoint* curve1 = v1 == SkPath::kQuad_Verb ? &pair[0] :
cStorage[0]; |
| 213 SkPoint* curve2 = v2 == SkPath::kQuad_Verb ? &pair[2] :
cStorage[1]; |
| 214 if (can_add_curve(v1, curve1) && can_add_curve(v2, curve
2)) { |
| 215 fCurrentContour->addCurve(v1, curve1); |
| 216 fCurrentContour->addCurve(v2, curve2); |
| 217 break; |
| 218 } |
| 219 } |
| 220 } |
| 221 addOneQuad: |
186 fCurrentContour->addQuad(pointsPtr); | 222 fCurrentContour->addQuad(pointsPtr); |
187 break; | 223 break; |
188 case SkPath::kConic_Verb: | 224 case SkPath::kConic_Verb: { |
189 fCurrentContour->addConic(pointsPtr, *weightPtr++); | 225 SkVector v1 = pointsPtr[1] - pointsPtr[0]; |
| 226 SkVector v2 = pointsPtr[2] - pointsPtr[1]; |
| 227 SkScalar weight = *weightPtr++; |
| 228 if (v1.dot(v2) < 0) { |
| 229 // FIXME: max curvature for conics hasn't been implemented;
use placeholder |
| 230 SkScalar maxCurvature = SkFindQuadMaxCurvature(pointsPtr); |
| 231 if (maxCurvature > 0) { |
| 232 SkConic conic(pointsPtr, weight); |
| 233 SkConic pair[2]; |
| 234 conic.chopAt(maxCurvature, pair); |
| 235 SkPoint cStorage[2][3]; |
| 236 SkPath::Verb v1 = SkReduceOrder::Conic(pair[0], cStorage
[0]); |
| 237 SkPath::Verb v2 = SkReduceOrder::Conic(pair[1], cStorage
[1]); |
| 238 SkPoint* curve1 = v1 == SkPath::kConic_Verb ? pair[0].fP
ts : cStorage[0]; |
| 239 SkPoint* curve2 = v2 == SkPath::kConic_Verb ? pair[1].fP
ts : cStorage[1]; |
| 240 if (can_add_curve(v1, curve1) && can_add_curve(v2, curve
2)) { |
| 241 fCurrentContour->addCurve(v1, curve1, pair[0].fW); |
| 242 fCurrentContour->addCurve(v2, curve2, pair[1].fW); |
| 243 break; |
| 244 } |
| 245 } |
| 246 } |
| 247 fCurrentContour->addConic(pointsPtr, weight); |
| 248 } break; |
| 249 case SkPath::kCubic_Verb: |
| 250 { |
| 251 // Split complex cubics (such as self-intersecting curves or |
| 252 // ones with difficult curvature) in two before proceeding. |
| 253 // This can be required for intersection to succeed. |
| 254 SkScalar splitT; |
| 255 if (SkDCubic::ComplexBreak(pointsPtr, &splitT)) { |
| 256 SkPoint pair[7]; |
| 257 SkChopCubicAt(pointsPtr, pair, splitT); |
| 258 if (!SkScalarsAreFinite(&pair[0].fX, SK_ARRAY_COUNT(pair
) * 2)) { |
| 259 return false; |
| 260 } |
| 261 SkPoint cStorage[2][4]; |
| 262 SkPath::Verb v1 = SkReduceOrder::Cubic(&pair[0], cStorag
e[0]); |
| 263 SkPath::Verb v2 = SkReduceOrder::Cubic(&pair[3], cStorag
e[1]); |
| 264 SkPoint* curve1 = v1 == SkPath::kCubic_Verb ? &pair[0] :
cStorage[0]; |
| 265 SkPoint* curve2 = v2 == SkPath::kCubic_Verb ? &pair[3] :
cStorage[1]; |
| 266 if (can_add_curve(v1, curve1) && can_add_curve(v2, curve
2)) { |
| 267 fCurrentContour->addCurve(v1, curve1); |
| 268 fCurrentContour->addCurve(v2, curve2); |
| 269 break; |
| 270 } |
| 271 } |
| 272 } |
| 273 fCurrentContour->addCubic(pointsPtr); |
190 break; | 274 break; |
191 case SkPath::kCubic_Verb: { | |
192 // Split complex cubics (such as self-intersecting curves or | |
193 // ones with difficult curvature) in two before proceeding. | |
194 // This can be required for intersection to succeed. | |
195 SkScalar splitT; | |
196 if (SkDCubic::ComplexBreak(pointsPtr, &splitT)) { | |
197 SkPoint cubicPair[7]; | |
198 SkChopCubicAt(pointsPtr, cubicPair, splitT); | |
199 if (!SkScalarsAreFinite(&cubicPair[0].fX, SK_ARRAY_COUNT(cub
icPair) * 2)) { | |
200 return false; | |
201 } | |
202 SkPoint cStorage[2][4]; | |
203 SkPath::Verb v1 = SkReduceOrder::Cubic(&cubicPair[0], cStora
ge[0]); | |
204 SkPath::Verb v2 = SkReduceOrder::Cubic(&cubicPair[3], cStora
ge[1]); | |
205 if (v1 != SkPath::kMove_Verb && v2 != SkPath::kMove_Verb) { | |
206 SkPoint* curve1 = v1 == SkPath::kCubic_Verb ? &cubicPair
[0] : cStorage[0]; | |
207 SkPoint* curve2 = v2 == SkPath::kCubic_Verb ? &cubicPair
[3] : cStorage[1]; | |
208 for (int index = 0; index < SkPathOpsVerbToPoints(v1); +
+index) { | |
209 force_small_to_zero(&curve1[index]); | |
210 } | |
211 for (int index = 0; index < SkPathOpsVerbToPoints(v2); +
+index) { | |
212 force_small_to_zero(&curve2[index]); | |
213 } | |
214 if (SkPath::kLine_Verb != v1 || | |
215 !SkDPoint::ApproximatelyEqual(curve1[0], curve1[
1])) { | |
216 fCurrentContour->addCurve(v1, curve1); | |
217 } | |
218 if (SkPath::kLine_Verb != v2 || | |
219 !SkDPoint::ApproximatelyEqual(curve2[0], curve2[
1])) { | |
220 fCurrentContour->addCurve(v2, curve2); | |
221 } | |
222 } else { | |
223 fCurrentContour->addCubic(pointsPtr); | |
224 } | |
225 } else { | |
226 fCurrentContour->addCubic(pointsPtr); | |
227 } | |
228 } break; | |
229 case SkPath::kClose_Verb: | 275 case SkPath::kClose_Verb: |
230 SkASSERT(fCurrentContour); | 276 SkASSERT(fCurrentContour); |
231 if (!close()) { | 277 if (!close()) { |
232 return false; | 278 return false; |
233 } | 279 } |
234 continue; | 280 continue; |
235 default: | 281 default: |
236 SkDEBUGFAIL("bad verb"); | 282 SkDEBUGFAIL("bad verb"); |
237 return false; | 283 return false; |
238 } | 284 } |
239 SkASSERT(fCurrentContour); | 285 SkASSERT(fCurrentContour); |
240 fCurrentContour->debugValidate(); | 286 fCurrentContour->debugValidate(); |
241 pointsPtr += SkPathOpsVerbToPoints(verb); | 287 pointsPtr += SkPathOpsVerbToPoints(verb); |
242 } | 288 } |
243 if (fCurrentContour && fCurrentContour->count() &&!fAllowOpenContours && !clo
se()) { | 289 if (fCurrentContour && fCurrentContour->count() &&!fAllowOpenContours && !clo
se()) { |
244 return false; | 290 return false; |
245 } | 291 } |
246 return true; | 292 return true; |
247 } | 293 } |
OLD | NEW |