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 = 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 
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();
23     fPath = &path;
24     fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
25             : kWinding_PathOpsMask;
26     preFetch();
27 }
28 
count() const29 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 
finish(SkChunkAlloc * allocator)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 
closeContour(const SkPoint & curveEnd,const SkPoint & curveStart)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
force_small_to_zero(SkPoint * pt)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 
preFetch()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 
close()160 bool SkOpEdgeBuilder::close() {
161     complete();
162     return true;
163 }
164 
walk(SkChunkAlloc * allocator)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