1
2 /*
3 * Copyright 2011 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8 #include "SkEdgeBuilder.h"
9 #include "SkPath.h"
10 #include "SkEdge.h"
11 #include "SkEdgeClipper.h"
12 #include "SkLineClipper.h"
13 #include "SkGeometry.h"
14
typedAllocThrow(SkChunkAlloc & alloc)15 template <typename T> static T* typedAllocThrow(SkChunkAlloc& alloc) {
16 return static_cast<T*>(alloc.allocThrow(sizeof(T)));
17 }
18
19 ///////////////////////////////////////////////////////////////////////////////
20
SkEdgeBuilder()21 SkEdgeBuilder::SkEdgeBuilder() : fAlloc(16*1024) {
22 fEdgeList = NULL;
23 }
24
addLine(const SkPoint pts[])25 void SkEdgeBuilder::addLine(const SkPoint pts[]) {
26 SkEdge* edge = typedAllocThrow<SkEdge>(fAlloc);
27 if (edge->setLine(pts[0], pts[1], fShiftUp)) {
28 fList.push(edge);
29 } else {
30 // TODO: unallocate edge from storage...
31 }
32 }
33
addQuad(const SkPoint pts[])34 void SkEdgeBuilder::addQuad(const SkPoint pts[]) {
35 SkQuadraticEdge* edge = typedAllocThrow<SkQuadraticEdge>(fAlloc);
36 if (edge->setQuadratic(pts, fShiftUp)) {
37 fList.push(edge);
38 } else {
39 // TODO: unallocate edge from storage...
40 }
41 }
42
addCubic(const SkPoint pts[])43 void SkEdgeBuilder::addCubic(const SkPoint pts[]) {
44 SkCubicEdge* edge = typedAllocThrow<SkCubicEdge>(fAlloc);
45 if (edge->setCubic(pts, fShiftUp)) {
46 fList.push(edge);
47 } else {
48 // TODO: unallocate edge from storage...
49 }
50 }
51
addClipper(SkEdgeClipper * clipper)52 void SkEdgeBuilder::addClipper(SkEdgeClipper* clipper) {
53 SkPoint pts[4];
54 SkPath::Verb verb;
55
56 while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) {
57 switch (verb) {
58 case SkPath::kLine_Verb:
59 this->addLine(pts);
60 break;
61 case SkPath::kQuad_Verb:
62 this->addQuad(pts);
63 break;
64 case SkPath::kCubic_Verb:
65 this->addCubic(pts);
66 break;
67 default:
68 break;
69 }
70 }
71 }
72
73 ///////////////////////////////////////////////////////////////////////////////
74
setShiftedClip(SkRect * dst,const SkIRect & src,int shift)75 static void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) {
76 dst->set(SkIntToScalar(src.fLeft >> shift),
77 SkIntToScalar(src.fTop >> shift),
78 SkIntToScalar(src.fRight >> shift),
79 SkIntToScalar(src.fBottom >> shift));
80 }
81
buildPoly(const SkPath & path,const SkIRect * iclip,int shiftUp,bool canCullToTheRight)82 int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip, int shiftUp,
83 bool canCullToTheRight) {
84 SkPath::Iter iter(path, true);
85 SkPoint pts[4];
86 SkPath::Verb verb;
87
88 int maxEdgeCount = path.countPoints();
89 if (iclip) {
90 // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since
91 // we turn portions that are clipped out on the left/right into vertical
92 // segments.
93 maxEdgeCount *= SkLineClipper::kMaxClippedLineSegments;
94 }
95 size_t maxEdgeSize = maxEdgeCount * sizeof(SkEdge);
96 size_t maxEdgePtrSize = maxEdgeCount * sizeof(SkEdge*);
97
98 // lets store the edges and their pointers in the same block
99 char* storage = (char*)fAlloc.allocThrow(maxEdgeSize + maxEdgePtrSize);
100 SkEdge* edge = reinterpret_cast<SkEdge*>(storage);
101 SkEdge** edgePtr = reinterpret_cast<SkEdge**>(storage + maxEdgeSize);
102 // Record the beginning of our pointers, so we can return them to the caller
103 fEdgeList = edgePtr;
104
105 if (iclip) {
106 SkRect clip;
107 setShiftedClip(&clip, *iclip, shiftUp);
108
109 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
110 switch (verb) {
111 case SkPath::kMove_Verb:
112 case SkPath::kClose_Verb:
113 // we ignore these, and just get the whole segment from
114 // the corresponding line/quad/cubic verbs
115 break;
116 case SkPath::kLine_Verb: {
117 SkPoint lines[SkLineClipper::kMaxPoints];
118 int lineCount = SkLineClipper::ClipLine(pts, clip, lines, canCullToTheRight);
119 SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments);
120 for (int i = 0; i < lineCount; i++) {
121 if (edge->setLine(lines[i], lines[i + 1], shiftUp)) {
122 *edgePtr++ = edge++;
123 }
124 }
125 break;
126 }
127 default:
128 SkDEBUGFAIL("unexpected verb");
129 break;
130 }
131 }
132 } else {
133 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
134 switch (verb) {
135 case SkPath::kMove_Verb:
136 case SkPath::kClose_Verb:
137 // we ignore these, and just get the whole segment from
138 // the corresponding line/quad/cubic verbs
139 break;
140 case SkPath::kLine_Verb:
141 if (edge->setLine(pts[0], pts[1], shiftUp)) {
142 *edgePtr++ = edge++;
143 }
144 break;
145 default:
146 SkDEBUGFAIL("unexpected verb");
147 break;
148 }
149 }
150 }
151 SkASSERT((char*)edge <= (char*)fEdgeList);
152 SkASSERT(edgePtr - fEdgeList <= maxEdgeCount);
153 return SkToInt(edgePtr - fEdgeList);
154 }
155
handle_quad(SkEdgeBuilder * builder,const SkPoint pts[3])156 static void handle_quad(SkEdgeBuilder* builder, const SkPoint pts[3]) {
157 SkPoint monoX[5];
158 int n = SkChopQuadAtYExtrema(pts, monoX);
159 for (int i = 0; i <= n; i++) {
160 builder->addQuad(&monoX[i * 2]);
161 }
162 }
163
build(const SkPath & path,const SkIRect * iclip,int shiftUp,bool canCullToTheRight)164 int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, int shiftUp,
165 bool canCullToTheRight) {
166 fAlloc.reset();
167 fList.reset();
168 fShiftUp = shiftUp;
169
170 if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) {
171 return this->buildPoly(path, iclip, shiftUp, canCullToTheRight);
172 }
173
174 SkAutoConicToQuads quadder;
175 const SkScalar conicTol = SK_Scalar1 / 4;
176
177 SkPath::Iter iter(path, true);
178 SkPoint pts[4];
179 SkPath::Verb verb;
180
181 if (iclip) {
182 SkRect clip;
183 setShiftedClip(&clip, *iclip, shiftUp);
184 SkEdgeClipper clipper(canCullToTheRight);
185
186 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
187 switch (verb) {
188 case SkPath::kMove_Verb:
189 case SkPath::kClose_Verb:
190 // we ignore these, and just get the whole segment from
191 // the corresponding line/quad/cubic verbs
192 break;
193 case SkPath::kLine_Verb: {
194 SkPoint lines[SkLineClipper::kMaxPoints];
195 int lineCount = SkLineClipper::ClipLine(pts, clip, lines, canCullToTheRight);
196 for (int i = 0; i < lineCount; i++) {
197 this->addLine(&lines[i]);
198 }
199 break;
200 }
201 case SkPath::kQuad_Verb:
202 if (clipper.clipQuad(pts, clip)) {
203 this->addClipper(&clipper);
204 }
205 break;
206 case SkPath::kConic_Verb: {
207 const SkPoint* quadPts = quadder.computeQuads(
208 pts, iter.conicWeight(), conicTol);
209 for (int i = 0; i < quadder.countQuads(); ++i) {
210 if (clipper.clipQuad(quadPts, clip)) {
211 this->addClipper(&clipper);
212 }
213 quadPts += 2;
214 }
215 } break;
216 case SkPath::kCubic_Verb:
217 if (clipper.clipCubic(pts, clip)) {
218 this->addClipper(&clipper);
219 }
220 break;
221 default:
222 SkDEBUGFAIL("unexpected verb");
223 break;
224 }
225 }
226 } else {
227 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
228 switch (verb) {
229 case SkPath::kMove_Verb:
230 case SkPath::kClose_Verb:
231 // we ignore these, and just get the whole segment from
232 // the corresponding line/quad/cubic verbs
233 break;
234 case SkPath::kLine_Verb:
235 this->addLine(pts);
236 break;
237 case SkPath::kQuad_Verb: {
238 handle_quad(this, pts);
239 break;
240 }
241 case SkPath::kConic_Verb: {
242 const SkPoint* quadPts = quadder.computeQuads(
243 pts, iter.conicWeight(), conicTol);
244 for (int i = 0; i < quadder.countQuads(); ++i) {
245 handle_quad(this, quadPts);
246 quadPts += 2;
247 }
248 } break;
249 case SkPath::kCubic_Verb: {
250 SkPoint monoY[10];
251 int n = SkChopCubicAtYExtrema(pts, monoY);
252 for (int i = 0; i <= n; i++) {
253 this->addCubic(&monoY[i * 3]);
254 }
255 break;
256 }
257 default:
258 SkDEBUGFAIL("unexpected verb");
259 break;
260 }
261 }
262 }
263 fEdgeList = fList.begin();
264 return fList.count();
265 }
266