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 void SkOpEdgeBuilder::init() { 12 fCurrentContour = fContoursHead; 13 fOperand = false; 14 fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask 15 : kWinding_PathOpsMask; 16 fUnparseable = false; 17 fSecondHalf = preFetch(); 18 } 19 20 void SkOpEdgeBuilder::addOperand(const SkPath& path) { 21 SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb); 22 fPathVerbs.pop(); 23 fPath = &path; 24 fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask 25 : kWinding_PathOpsMask; 26 preFetch(); 27 } 28 29 int SkOpEdgeBuilder::count() const { 30 SkOpContour* contour = fContoursHead; 31 int count = 0; 32 while (contour) { 33 count += contour->count() > 0; 34 contour = contour->next(); 35 } 36 return count; 37 } 38 39 bool SkOpEdgeBuilder::finish(SkChunkAlloc* allocator) { 40 fOperand = false; 41 if (fUnparseable || !walk(allocator)) { 42 return false; 43 } 44 complete(); 45 if (fCurrentContour && !fCurrentContour->count()) { 46 fContoursHead->remove(fCurrentContour); 47 } 48 return true; 49 } 50 51 void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) { 52 if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) { 53 *fPathVerbs.append() = SkPath::kLine_Verb; 54 *fPathPts.append() = curveStart; 55 } else { 56 fPathPts[fPathPts.count() - 1] = curveStart; 57 } 58 *fPathVerbs.append() = SkPath::kClose_Verb; 59 } 60 61 // very tiny points cause numerical instability : don't allow them 62 static void force_small_to_zero(SkPoint* pt) { 63 if (SkScalarAbs(pt->fX) < FLT_EPSILON_ORDERABLE_ERR) { 64 pt->fX = 0; 65 } 66 if (SkScalarAbs(pt->fY) < FLT_EPSILON_ORDERABLE_ERR) { 67 pt->fY = 0; 68 } 69 } 70 71 int SkOpEdgeBuilder::preFetch() { 72 if (!fPath->isFinite()) { 73 fUnparseable = true; 74 return 0; 75 } 76 SkPath::RawIter iter(*fPath); 77 SkPoint curveStart; 78 SkPoint curve[4]; 79 SkPoint pts[4]; 80 SkPath::Verb verb; 81 bool lastCurve = false; 82 do { 83 verb = iter.next(pts); 84 switch (verb) { 85 case SkPath::kMove_Verb: 86 if (!fAllowOpenContours && lastCurve) { 87 closeContour(curve[0], curveStart); 88 } 89 *fPathVerbs.append() = verb; 90 force_small_to_zero(&pts[0]); 91 *fPathPts.append() = pts[0]; 92 curveStart = curve[0] = pts[0]; 93 lastCurve = false; 94 continue; 95 case SkPath::kLine_Verb: 96 force_small_to_zero(&pts[1]); 97 if (SkDPoint::ApproximatelyEqual(curve[0], pts[1])) { 98 uint8_t lastVerb = fPathVerbs.top(); 99 if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) { 100 fPathPts.top() = pts[1]; 101 } 102 continue; // skip degenerate points 103 } 104 break; 105 case SkPath::kQuad_Verb: 106 force_small_to_zero(&pts[1]); 107 force_small_to_zero(&pts[2]); 108 curve[1] = pts[1]; 109 curve[2] = pts[2]; 110 verb = SkReduceOrder::Quad(curve, pts); 111 if (verb == SkPath::kMove_Verb) { 112 continue; // skip degenerate points 113 } 114 break; 115 case SkPath::kConic_Verb: 116 force_small_to_zero(&pts[1]); 117 force_small_to_zero(&pts[2]); 118 curve[1] = pts[1]; 119 curve[2] = pts[2]; 120 verb = SkReduceOrder::Conic(curve, iter.conicWeight(), pts); 121 if (verb == SkPath::kMove_Verb) { 122 continue; // skip degenerate points 123 } 124 break; 125 case SkPath::kCubic_Verb: 126 force_small_to_zero(&pts[1]); 127 force_small_to_zero(&pts[2]); 128 force_small_to_zero(&pts[3]); 129 curve[1] = pts[1]; 130 curve[2] = pts[2]; 131 curve[3] = pts[3]; 132 verb = SkReduceOrder::Cubic(curve, pts); 133 if (verb == SkPath::kMove_Verb) { 134 continue; // skip degenerate points 135 } 136 break; 137 case SkPath::kClose_Verb: 138 closeContour(curve[0], curveStart); 139 lastCurve = false; 140 continue; 141 case SkPath::kDone_Verb: 142 continue; 143 } 144 *fPathVerbs.append() = verb; 145 int ptCount = SkPathOpsVerbToPoints(verb); 146 fPathPts.append(ptCount, &pts[1]); 147 if (verb == SkPath::kConic_Verb) { 148 *fWeights.append() = iter.conicWeight(); 149 } 150 curve[0] = pts[ptCount]; 151 lastCurve = true; 152 } while (verb != SkPath::kDone_Verb); 153 if (!fAllowOpenContours && lastCurve) { 154 closeContour(curve[0], curveStart); 155 } 156 *fPathVerbs.append() = SkPath::kDone_Verb; 157 return fPathVerbs.count() - 1; 158 } 159 160 bool SkOpEdgeBuilder::close() { 161 complete(); 162 return true; 163 } 164 165 bool SkOpEdgeBuilder::walk(SkChunkAlloc* allocator) { 166 uint8_t* verbPtr = fPathVerbs.begin(); 167 uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf]; 168 SkPoint* pointsPtr = fPathPts.begin() - 1; 169 SkScalar* weightPtr = fWeights.begin(); 170 SkPath::Verb verb; 171 while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) { 172 if (verbPtr == endOfFirstHalf) { 173 fOperand = true; 174 } 175 verbPtr++; 176 switch (verb) { 177 case SkPath::kMove_Verb: 178 if (fCurrentContour && fCurrentContour->count()) { 179 if (fAllowOpenContours) { 180 complete(); 181 } else if (!close()) { 182 return false; 183 } 184 } 185 if (!fCurrentContour) { 186 fCurrentContour = fContoursHead->appendContour(allocator); 187 } 188 fCurrentContour->init(fGlobalState, fOperand, 189 fXorMask[fOperand] == kEvenOdd_PathOpsMask); 190 pointsPtr += 1; 191 continue; 192 case SkPath::kLine_Verb: 193 fCurrentContour->addLine(pointsPtr, fAllocator); 194 break; 195 case SkPath::kQuad_Verb: 196 fCurrentContour->addQuad(pointsPtr, fAllocator); 197 break; 198 case SkPath::kConic_Verb: 199 fCurrentContour->addConic(pointsPtr, *weightPtr++, fAllocator); 200 break; 201 case SkPath::kCubic_Verb: { 202 // split self-intersecting cubics in two before proceeding 203 // if the cubic is convex, it doesn't self intersect. 204 SkScalar loopT; 205 if (SkDCubic::ComplexBreak(pointsPtr, &loopT)) { 206 SkPoint cubicPair[7]; 207 SkChopCubicAt(pointsPtr, cubicPair, loopT); 208 if (!SkScalarsAreFinite(&cubicPair[0].fX, SK_ARRAY_COUNT(cubicPair) * 2)) { 209 return false; 210 } 211 SkPoint cStorage[2][4]; 212 SkPath::Verb v1 = SkReduceOrder::Cubic(&cubicPair[0], cStorage[0]); 213 SkPath::Verb v2 = SkReduceOrder::Cubic(&cubicPair[3], cStorage[1]); 214 if (v1 != SkPath::kMove_Verb && v2 != SkPath::kMove_Verb) { 215 SkPoint* curve1 = v1 == SkPath::kCubic_Verb ? &cubicPair[0] : cStorage[0]; 216 SkPoint* curve2 = v2 == SkPath::kCubic_Verb ? &cubicPair[3] : cStorage[1]; 217 for (int index = 0; index < SkPathOpsVerbToPoints(v1); ++index) { 218 force_small_to_zero(&curve1[index]); 219 } 220 for (int index = 0; index < SkPathOpsVerbToPoints(v2); ++index) { 221 force_small_to_zero(&curve2[index]); 222 } 223 fCurrentContour->addCurve(v1, curve1, fAllocator); 224 fCurrentContour->addCurve(v2, curve2, fAllocator); 225 } else { 226 fCurrentContour->addCubic(pointsPtr, fAllocator); 227 } 228 } else { 229 fCurrentContour->addCubic(pointsPtr, fAllocator); 230 } 231 } break; 232 case SkPath::kClose_Verb: 233 SkASSERT(fCurrentContour); 234 if (!close()) { 235 return false; 236 } 237 continue; 238 default: 239 SkDEBUGFAIL("bad verb"); 240 return false; 241 } 242 SkASSERT(fCurrentContour); 243 fCurrentContour->debugValidate(); 244 pointsPtr += SkPathOpsVerbToPoints(verb); 245 } 246 if (fCurrentContour && fCurrentContour->count() &&!fAllowOpenContours && !close()) { 247 return false; 248 } 249 return true; 250 } 251
