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, NULL, 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)82 int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip,
83 int shiftUp) {
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);
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 edgePtr - fEdgeList;
154 }
155
build(const SkPath & path,const SkIRect * iclip,int shiftUp)156 int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip,
157 int shiftUp) {
158 fAlloc.reset();
159 fList.reset();
160 fShiftUp = shiftUp;
161
162 if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) {
163 return this->buildPoly(path, iclip, shiftUp);
164 }
165
166 SkPath::Iter iter(path, true);
167 SkPoint pts[4];
168 SkPath::Verb verb;
169
170 if (iclip) {
171 SkRect clip;
172 setShiftedClip(&clip, *iclip, shiftUp);
173 SkEdgeClipper clipper;
174
175 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
176 switch (verb) {
177 case SkPath::kMove_Verb:
178 case SkPath::kClose_Verb:
179 // we ignore these, and just get the whole segment from
180 // the corresponding line/quad/cubic verbs
181 break;
182 case SkPath::kLine_Verb: {
183 SkPoint lines[SkLineClipper::kMaxPoints];
184 int lineCount = SkLineClipper::ClipLine(pts, clip, lines);
185 for (int i = 0; i < lineCount; i++) {
186 this->addLine(&lines[i]);
187 }
188 break;
189 }
190 case SkPath::kQuad_Verb:
191 if (clipper.clipQuad(pts, clip)) {
192 this->addClipper(&clipper);
193 }
194 break;
195 case SkPath::kCubic_Verb:
196 if (clipper.clipCubic(pts, clip)) {
197 this->addClipper(&clipper);
198 }
199 break;
200 default:
201 SkDEBUGFAIL("unexpected verb");
202 break;
203 }
204 }
205 } else {
206 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
207 switch (verb) {
208 case SkPath::kMove_Verb:
209 case SkPath::kClose_Verb:
210 // we ignore these, and just get the whole segment from
211 // the corresponding line/quad/cubic verbs
212 break;
213 case SkPath::kLine_Verb:
214 this->addLine(pts);
215 break;
216 case SkPath::kQuad_Verb: {
217 SkPoint monoX[5];
218 int n = SkChopQuadAtYExtrema(pts, monoX);
219 for (int i = 0; i <= n; i++) {
220 this->addQuad(&monoX[i * 2]);
221 }
222 break;
223 }
224 case SkPath::kCubic_Verb: {
225 SkPoint monoY[10];
226 int n = SkChopCubicAtYExtrema(pts, monoY);
227 for (int i = 0; i <= n; i++) {
228 this->addCubic(&monoY[i * 3]);
229 }
230 break;
231 }
232 default:
233 SkDEBUGFAIL("unexpected verb");
234 break;
235 }
236 }
237 }
238 fEdgeList = fList.begin();
239 return fList.count();
240 }
241