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 fCurrentContour = NULL;
13 fOperand = false;
14 fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
15 : kWinding_PathOpsMask;
16 fUnparseable = false;
17 fSecondHalf = preFetch();
18 }
19
addOperand(const SkPath & path)20 void SkOpEdgeBuilder::addOperand(const SkPath& path) {
21 SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb);
22 fPathVerbs.pop_back();
23 fPath = &path;
24 fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
25 : kWinding_PathOpsMask;
26 preFetch();
27 }
28
finish()29 bool SkOpEdgeBuilder::finish() {
30 if (fUnparseable || !walk()) {
31 return false;
32 }
33 complete();
34 if (fCurrentContour && !fCurrentContour->segments().count()) {
35 fContours.pop_back();
36 }
37 return true;
38 }
39
closeContour(const SkPoint & curveEnd,const SkPoint & curveStart)40 void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) {
41 if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) {
42 fPathVerbs.push_back(SkPath::kLine_Verb);
43 fPathPts.push_back_n(1, &curveStart);
44 } else {
45 fPathPts[fPathPts.count() - 1] = curveStart;
46 }
47 fPathVerbs.push_back(SkPath::kClose_Verb);
48 }
49
50 // very tiny points cause numerical instability : don't allow them
force_small_to_zero(SkPoint * pt)51 static void force_small_to_zero(SkPoint* pt) {
52 if (SkScalarAbs(pt->fX) < FLT_EPSILON_ORDERABLE_ERR) {
53 pt->fX = 0;
54 }
55 if (SkScalarAbs(pt->fY) < FLT_EPSILON_ORDERABLE_ERR) {
56 pt->fY = 0;
57 }
58 }
59
60
preFetch()61 int SkOpEdgeBuilder::preFetch() {
62 if (!fPath->isFinite()) {
63 fUnparseable = true;
64 return 0;
65 }
66 SkAutoConicToQuads quadder;
67 const SkScalar quadderTol = SK_Scalar1 / 16;
68 SkPath::RawIter iter(*fPath);
69 SkPoint curveStart;
70 SkPoint curve[4];
71 SkPoint pts[4];
72 SkPath::Verb verb;
73 bool lastCurve = false;
74 do {
75 verb = iter.next(pts);
76 switch (verb) {
77 case SkPath::kMove_Verb:
78 if (!fAllowOpenContours && lastCurve) {
79 closeContour(curve[0], curveStart);
80 }
81 fPathVerbs.push_back(verb);
82 force_small_to_zero(&pts[0]);
83 fPathPts.push_back(pts[0]);
84 curveStart = curve[0] = pts[0];
85 lastCurve = false;
86 continue;
87 case SkPath::kLine_Verb:
88 force_small_to_zero(&pts[1]);
89 if (SkDPoint::ApproximatelyEqual(curve[0], pts[1])) {
90 uint8_t lastVerb = fPathVerbs.back();
91 if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) {
92 fPathPts.back() = pts[1];
93 }
94 continue; // skip degenerate points
95 }
96 break;
97 case SkPath::kQuad_Verb:
98 force_small_to_zero(&pts[1]);
99 force_small_to_zero(&pts[2]);
100 curve[1] = pts[1];
101 curve[2] = pts[2];
102 verb = SkReduceOrder::Quad(curve, pts);
103 if (verb == SkPath::kMove_Verb) {
104 continue; // skip degenerate points
105 }
106 break;
107 case SkPath::kConic_Verb: {
108 const SkPoint* quadPts = quadder.computeQuads(pts, iter.conicWeight(),
109 quadderTol);
110 const int nQuads = quadder.countQuads();
111 for (int i = 0; i < nQuads; ++i) {
112 fPathVerbs.push_back(SkPath::kQuad_Verb);
113 }
114 fPathPts.push_back_n(nQuads * 2, quadPts);
115 curve[0] = quadPts[nQuads * 2 - 1];
116 lastCurve = true;
117 }
118 continue;
119 case SkPath::kCubic_Verb:
120 force_small_to_zero(&pts[1]);
121 force_small_to_zero(&pts[2]);
122 force_small_to_zero(&pts[3]);
123 curve[1] = pts[1];
124 curve[2] = pts[2];
125 curve[3] = pts[3];
126 verb = SkReduceOrder::Cubic(curve, pts);
127 if (verb == SkPath::kMove_Verb) {
128 continue; // skip degenerate points
129 }
130 break;
131 case SkPath::kClose_Verb:
132 closeContour(curve[0], curveStart);
133 lastCurve = false;
134 continue;
135 case SkPath::kDone_Verb:
136 continue;
137 }
138 fPathVerbs.push_back(verb);
139 int ptCount = SkPathOpsVerbToPoints(verb);
140 fPathPts.push_back_n(ptCount, &pts[1]);
141 curve[0] = pts[ptCount];
142 lastCurve = true;
143 } while (verb != SkPath::kDone_Verb);
144 if (!fAllowOpenContours && lastCurve) {
145 closeContour(curve[0], curveStart);
146 }
147 fPathVerbs.push_back(SkPath::kDone_Verb);
148 return fPathVerbs.count() - 1;
149 }
150
close()151 bool SkOpEdgeBuilder::close() {
152 complete();
153 return true;
154 }
155
walk()156 bool SkOpEdgeBuilder::walk() {
157 uint8_t* verbPtr = fPathVerbs.begin();
158 uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
159 const SkPoint* pointsPtr = fPathPts.begin() - 1;
160 SkPath::Verb verb;
161 while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) {
162 if (verbPtr == endOfFirstHalf) {
163 fOperand = true;
164 }
165 verbPtr++;
166 switch (verb) {
167 case SkPath::kMove_Verb:
168 if (fCurrentContour) {
169 if (fAllowOpenContours) {
170 complete();
171 } else if (!close()) {
172 return false;
173 }
174 }
175 if (!fCurrentContour) {
176 fCurrentContour = fContours.push_back_n(1);
177 fCurrentContour->setOperand(fOperand);
178 fCurrentContour->setXor(fXorMask[fOperand] == kEvenOdd_PathOpsMask);
179 }
180 pointsPtr += 1;
181 continue;
182 case SkPath::kLine_Verb:
183 fCurrentContour->addLine(pointsPtr);
184 break;
185 case SkPath::kQuad_Verb:
186 fCurrentContour->addQuad(pointsPtr);
187 break;
188 case SkPath::kCubic_Verb:
189 fCurrentContour->addCubic(pointsPtr);
190 break;
191 case SkPath::kClose_Verb:
192 SkASSERT(fCurrentContour);
193 if (!close()) {
194 return false;
195 }
196 continue;
197 default:
198 SkDEBUGFAIL("bad verb");
199 return false;
200 }
201 pointsPtr += SkPathOpsVerbToPoints(verb);
202 SkASSERT(fCurrentContour);
203 }
204 if (fCurrentContour && !fAllowOpenContours && !close()) {
205 return false;
206 }
207 return true;
208 }
209