caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 | */ |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 7 | #include "SkGeometry.h" |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 8 | #include "SkOpEdgeBuilder.h" |
| 9 | #include "SkReduceOrder.h" |
| 10 | |
| 11 | void SkOpEdgeBuilder::init() { |
| 12 | fCurrentContour = NULL; |
| 13 | fOperand = false; |
| 14 | fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask |
| 15 | : kWinding_PathOpsMask; |
commit-bot@chromium.org | 8cb1daa | 2014-04-25 12:59:11 +0000 | [diff] [blame^] | 16 | #if defined(SK_DEBUG) || !FORCE_RELEASE |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 17 | SkPathOpsDebug::gContourID = 0; |
| 18 | SkPathOpsDebug::gSegmentID = 0; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 19 | #endif |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 20 | fUnparseable = false; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 21 | fSecondHalf = preFetch(); |
| 22 | } |
| 23 | |
| 24 | void SkOpEdgeBuilder::addOperand(const SkPath& path) { |
| 25 | SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb); |
caryclark@google.com | d892bd8 | 2013-06-17 14:10:36 +0000 | [diff] [blame] | 26 | fPathVerbs.pop_back(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 27 | fPath = &path; |
| 28 | fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask |
| 29 | : kWinding_PathOpsMask; |
| 30 | preFetch(); |
| 31 | } |
| 32 | |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 33 | bool SkOpEdgeBuilder::finish() { |
| 34 | if (fUnparseable || !walk()) { |
| 35 | return false; |
| 36 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 37 | complete(); |
| 38 | if (fCurrentContour && !fCurrentContour->segments().count()) { |
| 39 | fContours.pop_back(); |
| 40 | } |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 41 | return true; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 42 | } |
| 43 | |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 44 | void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) { |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 45 | if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) { |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 46 | fPathVerbs.push_back(SkPath::kLine_Verb); |
skia.committer@gmail.com | a4aced4 | 2013-07-09 07:00:56 +0000 | [diff] [blame] | 47 | fPathPts.push_back_n(1, &curveStart); |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 48 | } else { |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 49 | fPathPts[fPathPts.count() - 1] = curveStart; |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 50 | } |
| 51 | fPathVerbs.push_back(SkPath::kClose_Verb); |
| 52 | } |
| 53 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 54 | int SkOpEdgeBuilder::preFetch() { |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 55 | if (!fPath->isFinite()) { |
| 56 | fUnparseable = true; |
| 57 | return 0; |
| 58 | } |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 59 | SkAutoConicToQuads quadder; |
| 60 | const SkScalar quadderTol = SK_Scalar1 / 16; |
caryclark@google.com | 6dc7df6 | 2013-04-25 11:51:54 +0000 | [diff] [blame] | 61 | SkPath::RawIter iter(*fPath); |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 62 | SkPoint curveStart; |
| 63 | SkPoint curve[4]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 64 | SkPoint pts[4]; |
| 65 | SkPath::Verb verb; |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 66 | bool lastCurve = false; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 67 | do { |
| 68 | verb = iter.next(pts); |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 69 | switch (verb) { |
| 70 | case SkPath::kMove_Verb: |
| 71 | if (!fAllowOpenContours && lastCurve) { |
| 72 | closeContour(curve[0], curveStart); |
| 73 | } |
| 74 | fPathVerbs.push_back(verb); |
| 75 | fPathPts.push_back(pts[0]); |
| 76 | curveStart = curve[0] = pts[0]; |
| 77 | lastCurve = false; |
| 78 | continue; |
| 79 | case SkPath::kLine_Verb: |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 80 | if (SkDPoint::ApproximatelyEqual(curve[0], pts[1])) { |
| 81 | uint8_t lastVerb = fPathVerbs.back(); |
| 82 | if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) { |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 83 | fPathPts.back() = pts[1]; |
| 84 | } |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 85 | continue; // skip degenerate points |
| 86 | } |
| 87 | break; |
| 88 | case SkPath::kQuad_Verb: |
| 89 | curve[1] = pts[1]; |
| 90 | curve[2] = pts[2]; |
| 91 | verb = SkReduceOrder::Quad(curve, pts); |
| 92 | if (verb == SkPath::kMove_Verb) { |
| 93 | continue; // skip degenerate points |
| 94 | } |
| 95 | break; |
| 96 | case SkPath::kConic_Verb: { |
| 97 | const SkPoint* quadPts = quadder.computeQuads(pts, iter.conicWeight(), |
| 98 | quadderTol); |
| 99 | const int nQuads = quadder.countQuads(); |
| 100 | for (int i = 0; i < nQuads; ++i) { |
| 101 | fPathVerbs.push_back(SkPath::kQuad_Verb); |
| 102 | } |
| 103 | fPathPts.push_back_n(nQuads * 2, quadPts); |
| 104 | curve[0] = quadPts[nQuads * 2 - 1]; |
| 105 | lastCurve = true; |
| 106 | } |
| 107 | continue; |
| 108 | case SkPath::kCubic_Verb: |
| 109 | curve[1] = pts[1]; |
| 110 | curve[2] = pts[2]; |
| 111 | curve[3] = pts[3]; |
| 112 | verb = SkReduceOrder::Cubic(curve, pts); |
| 113 | if (verb == SkPath::kMove_Verb) { |
| 114 | continue; // skip degenerate points |
| 115 | } |
| 116 | break; |
| 117 | case SkPath::kClose_Verb: |
| 118 | closeContour(curve[0], curveStart); |
| 119 | lastCurve = false; |
| 120 | continue; |
| 121 | case SkPath::kDone_Verb: |
| 122 | continue; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 123 | } |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 124 | fPathVerbs.push_back(verb); |
| 125 | int ptCount = SkPathOpsVerbToPoints(verb); |
| 126 | fPathPts.push_back_n(ptCount, &pts[1]); |
| 127 | curve[0] = pts[ptCount]; |
| 128 | lastCurve = true; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 129 | } while (verb != SkPath::kDone_Verb); |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 130 | if (!fAllowOpenContours && lastCurve) { |
| 131 | closeContour(curve[0], curveStart); |
| 132 | } |
| 133 | fPathVerbs.push_back(SkPath::kDone_Verb); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 134 | return fPathVerbs.count() - 1; |
| 135 | } |
| 136 | |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 137 | bool SkOpEdgeBuilder::close() { |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 138 | complete(); |
| 139 | return true; |
| 140 | } |
| 141 | |
| 142 | bool SkOpEdgeBuilder::walk() { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 143 | uint8_t* verbPtr = fPathVerbs.begin(); |
| 144 | uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf]; |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 145 | const SkPoint* pointsPtr = fPathPts.begin() - 1; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 146 | SkPath::Verb verb; |
caryclark@google.com | 6dc7df6 | 2013-04-25 11:51:54 +0000 | [diff] [blame] | 147 | while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) { |
| 148 | if (verbPtr == endOfFirstHalf) { |
| 149 | fOperand = true; |
| 150 | } |
| 151 | verbPtr++; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 152 | switch (verb) { |
| 153 | case SkPath::kMove_Verb: |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 154 | if (fCurrentContour) { |
| 155 | if (fAllowOpenContours) { |
| 156 | complete(); |
| 157 | } else if (!close()) { |
| 158 | return false; |
| 159 | } |
| 160 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 161 | if (!fCurrentContour) { |
| 162 | fCurrentContour = fContours.push_back_n(1); |
| 163 | fCurrentContour->setOperand(fOperand); |
| 164 | fCurrentContour->setXor(fXorMask[fOperand] == kEvenOdd_PathOpsMask); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 165 | } |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 166 | pointsPtr += 1; |
caryclark@google.com | 6dc7df6 | 2013-04-25 11:51:54 +0000 | [diff] [blame] | 167 | continue; |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 168 | case SkPath::kLine_Verb: |
| 169 | fCurrentContour->addLine(pointsPtr); |
| 170 | break; |
| 171 | case SkPath::kQuad_Verb: |
| 172 | fCurrentContour->addQuad(pointsPtr); |
| 173 | break; |
| 174 | case SkPath::kCubic_Verb: |
| 175 | fCurrentContour->addCubic(pointsPtr); |
| 176 | break; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 177 | case SkPath::kClose_Verb: |
| 178 | SkASSERT(fCurrentContour); |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 179 | if (!close()) { |
| 180 | return false; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 181 | } |
caryclark@google.com | 6dc7df6 | 2013-04-25 11:51:54 +0000 | [diff] [blame] | 182 | continue; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 183 | default: |
| 184 | SkDEBUGFAIL("bad verb"); |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 185 | return false; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 186 | } |
reed@google.com | 277c3f8 | 2013-05-31 15:17:50 +0000 | [diff] [blame] | 187 | pointsPtr += SkPathOpsVerbToPoints(verb); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 188 | SkASSERT(fCurrentContour); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 189 | } |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 190 | if (fCurrentContour && !fAllowOpenContours && !close()) { |
| 191 | return false; |
| 192 | } |
| 193 | return true; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 194 | } |