OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2011 Google Inc. | 2 * Copyright 2011 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 #include "SkEdgeBuilder.h" | 7 #include "SkEdgeBuilder.h" |
8 #include "SkPath.h" | 8 #include "SkPath.h" |
9 #include "SkEdge.h" | 9 #include "SkEdge.h" |
| 10 #include "SkAnalyticEdge.h" |
10 #include "SkEdgeClipper.h" | 11 #include "SkEdgeClipper.h" |
11 #include "SkLineClipper.h" | 12 #include "SkLineClipper.h" |
12 #include "SkGeometry.h" | 13 #include "SkGeometry.h" |
13 | 14 |
14 template <typename T> static T* typedAllocThrow(SkChunkAlloc& alloc) { | 15 template <typename T> static T* typedAllocThrow(SkChunkAlloc& alloc) { |
15 return static_cast<T*>(alloc.allocThrow(sizeof(T))); | 16 return static_cast<T*>(alloc.allocThrow(sizeof(T))); |
16 } | 17 } |
17 | 18 |
18 /////////////////////////////////////////////////////////////////////////////// | 19 /////////////////////////////////////////////////////////////////////////////// |
19 | 20 |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
55 return kPartial_Combine; | 56 return kPartial_Combine; |
56 } | 57 } |
57 last->fLastY = last->fFirstY - 1; | 58 last->fLastY = last->fFirstY - 1; |
58 last->fFirstY = edge->fFirstY; | 59 last->fFirstY = edge->fFirstY; |
59 last->fWinding = edge->fWinding; | 60 last->fWinding = edge->fWinding; |
60 return kPartial_Combine; | 61 return kPartial_Combine; |
61 } | 62 } |
62 return kNo_Combine; | 63 return kNo_Combine; |
63 } | 64 } |
64 | 65 |
65 static bool vertical_line(const SkEdge* edge) { | 66 SkEdgeBuilder::Combine SkEdgeBuilder::CombineVertical( |
| 67 const SkAnalyticEdge* edge, SkAnalyticEdge* last) { |
| 68 SkASSERT(fAnalyticAA); |
| 69 if (last->fCurveCount || last->fDX || edge->fX != last->fX) { |
| 70 return kNo_Combine; |
| 71 } |
| 72 if (edge->fWinding == last->fWinding) { |
| 73 if (edge->fLowerY == last->fUpperY) { |
| 74 last->fUpperY = edge->fUpperY; |
| 75 last->fY = last->fUpperY; |
| 76 return kPartial_Combine; |
| 77 } |
| 78 if (edge->fUpperY == last->fLowerY) { |
| 79 last->fLowerY = edge->fLowerY; |
| 80 return kPartial_Combine; |
| 81 } |
| 82 return kNo_Combine; |
| 83 } |
| 84 if (edge->fUpperY == last->fUpperY) { |
| 85 if (edge->fLowerY == last->fLowerY) { |
| 86 return kTotal_Combine; |
| 87 } |
| 88 if (edge->fLowerY < last->fLowerY) { |
| 89 last->fUpperY = edge->fLowerY; |
| 90 last->fY = last->fUpperY; |
| 91 return kPartial_Combine; |
| 92 } |
| 93 last->fUpperY = last->fLowerY; |
| 94 last->fY = last->fUpperY; |
| 95 last->fLowerY = edge->fLowerY; |
| 96 last->fWinding = edge->fWinding; |
| 97 return kPartial_Combine; |
| 98 } |
| 99 if (edge->fLowerY == last->fLowerY) { |
| 100 if (edge->fUpperY > last->fUpperY) { |
| 101 last->fLowerY = edge->fUpperY; |
| 102 return kPartial_Combine; |
| 103 } |
| 104 last->fLowerY = last->fUpperY; |
| 105 last->fUpperY = edge->fUpperY; |
| 106 last->fY = last->fUpperY; |
| 107 last->fWinding = edge->fWinding; |
| 108 return kPartial_Combine; |
| 109 } |
| 110 return kNo_Combine; |
| 111 } |
| 112 |
| 113 bool SkEdgeBuilder::vertical_line(const SkEdge* edge) { |
| 114 return !edge->fDX && !edge->fCurveCount; |
| 115 } |
| 116 |
| 117 bool SkEdgeBuilder::vertical_line(const SkAnalyticEdge* edge) { |
| 118 SkASSERT(fAnalyticAA); |
66 return !edge->fDX && !edge->fCurveCount; | 119 return !edge->fDX && !edge->fCurveCount; |
67 } | 120 } |
68 | 121 |
69 void SkEdgeBuilder::addLine(const SkPoint pts[]) { | 122 void SkEdgeBuilder::addLine(const SkPoint pts[]) { |
70 SkEdge* edge = typedAllocThrow<SkEdge>(fAlloc); | 123 if (fAnalyticAA) { |
71 if (edge->setLine(pts[0], pts[1], fShiftUp)) { | 124 SkAnalyticEdge* edge = typedAllocThrow<SkAnalyticEdge>(fAlloc); |
72 if (vertical_line(edge) && fList.count()) { | 125 if (edge->setLine(pts[0], pts[1])) { |
73 Combine combine = CombineVertical(edge, *(fList.end() - 1)); | 126 if (vertical_line(edge) && fList.count()) { |
74 if (kNo_Combine != combine) { | 127 Combine combine = CombineVertical(edge, (SkAnalyticEdge*)*(fList
.end() - 1)); |
75 if (kTotal_Combine == combine) { | 128 if (kNo_Combine != combine) { |
76 fList.pop(); | 129 if (kTotal_Combine == combine) { |
| 130 fList.pop(); |
| 131 } |
| 132 goto unallocate_analytic_edge; |
77 } | 133 } |
78 goto unallocate_edge; | |
79 } | 134 } |
| 135 fList.push(edge); |
| 136 } else { |
| 137 unallocate_analytic_edge: |
| 138 ; |
| 139 // TODO: unallocate edge from storage... |
80 } | 140 } |
81 fList.push(edge); | |
82 } else { | 141 } else { |
| 142 SkEdge* edge = typedAllocThrow<SkEdge>(fAlloc); |
| 143 if (edge->setLine(pts[0], pts[1], fShiftUp)) { |
| 144 if (vertical_line(edge) && fList.count()) { |
| 145 Combine combine = CombineVertical(edge, (SkEdge*)*(fList.end() -
1)); |
| 146 if (kNo_Combine != combine) { |
| 147 if (kTotal_Combine == combine) { |
| 148 fList.pop(); |
| 149 } |
| 150 goto unallocate_edge; |
| 151 } |
| 152 } |
| 153 fList.push(edge); |
| 154 } else { |
83 unallocate_edge: | 155 unallocate_edge: |
84 ; | 156 ; |
85 // TODO: unallocate edge from storage... | 157 // TODO: unallocate edge from storage... |
| 158 } |
86 } | 159 } |
87 } | 160 } |
88 | 161 |
89 void SkEdgeBuilder::addQuad(const SkPoint pts[]) { | 162 void SkEdgeBuilder::addQuad(const SkPoint pts[]) { |
90 SkQuadraticEdge* edge = typedAllocThrow<SkQuadraticEdge>(fAlloc); | 163 if (fAnalyticAA) { |
91 if (edge->setQuadratic(pts, fShiftUp)) { | 164 SkAnalyticQuadraticEdge* edge = typedAllocThrow<SkAnalyticQuadraticEdge>
(fAlloc); |
92 fList.push(edge); | 165 if (edge->setQuadratic(pts)) { |
| 166 fList.push(edge); |
| 167 } else { |
| 168 // TODO: unallocate edge from storage... |
| 169 } |
93 } else { | 170 } else { |
94 // TODO: unallocate edge from storage... | 171 SkQuadraticEdge* edge = typedAllocThrow<SkQuadraticEdge>(fAlloc); |
| 172 if (edge->setQuadratic(pts, fShiftUp)) { |
| 173 fList.push(edge); |
| 174 } else { |
| 175 // TODO: unallocate edge from storage... |
| 176 } |
95 } | 177 } |
96 } | 178 } |
97 | 179 |
98 void SkEdgeBuilder::addCubic(const SkPoint pts[]) { | 180 void SkEdgeBuilder::addCubic(const SkPoint pts[]) { |
99 SkCubicEdge* edge = typedAllocThrow<SkCubicEdge>(fAlloc); | 181 if (fAnalyticAA) { |
100 if (edge->setCubic(pts, fShiftUp)) { | 182 SkAnalyticCubicEdge* edge = typedAllocThrow<SkAnalyticCubicEdge>(fAlloc)
; |
101 fList.push(edge); | 183 if (edge->setCubic(pts)) { |
| 184 fList.push(edge); |
| 185 } else { |
| 186 // TODO: unallocate edge from storage... |
| 187 } |
102 } else { | 188 } else { |
103 // TODO: unallocate edge from storage... | 189 SkCubicEdge* edge = typedAllocThrow<SkCubicEdge>(fAlloc); |
| 190 if (edge->setCubic(pts, fShiftUp)) { |
| 191 fList.push(edge); |
| 192 } else { |
| 193 // TODO: unallocate edge from storage... |
| 194 } |
104 } | 195 } |
105 } | 196 } |
106 | 197 |
107 void SkEdgeBuilder::addClipper(SkEdgeClipper* clipper) { | 198 void SkEdgeBuilder::addClipper(SkEdgeClipper* clipper) { |
108 SkPoint pts[4]; | 199 SkPoint pts[4]; |
109 SkPath::Verb verb; | 200 SkPath::Verb verb; |
110 | 201 |
111 while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) { | 202 while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) { |
112 switch (verb) { | 203 switch (verb) { |
113 case SkPath::kLine_Verb: | 204 case SkPath::kLine_Verb: |
(...skipping 14 matching lines...) Expand all Loading... |
128 /////////////////////////////////////////////////////////////////////////////// | 219 /////////////////////////////////////////////////////////////////////////////// |
129 | 220 |
130 static void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) { | 221 static void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) { |
131 dst->set(SkIntToScalar(src.fLeft >> shift), | 222 dst->set(SkIntToScalar(src.fLeft >> shift), |
132 SkIntToScalar(src.fTop >> shift), | 223 SkIntToScalar(src.fTop >> shift), |
133 SkIntToScalar(src.fRight >> shift), | 224 SkIntToScalar(src.fRight >> shift), |
134 SkIntToScalar(src.fBottom >> shift)); | 225 SkIntToScalar(src.fBottom >> shift)); |
135 } | 226 } |
136 | 227 |
137 SkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkEdge* edge, SkEdge**
edgePtr) { | 228 SkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkEdge* edge, SkEdge**
edgePtr) { |
138 return !vertical_line(edge) || edgePtr <= fEdgeList ? kNo_Combine : | 229 return !vertical_line(edge) || edgePtr <= (SkEdge**)fEdgeList ? kNo_Combine
: |
139 CombineVertical(edge, edgePtr[-1]); | 230 CombineVertical(edge, edgePtr[-1]); |
140 } | 231 } |
141 | 232 |
| 233 SkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkAnalyticEdge* edge, |
| 234 SkAnalyticEdge** edgePtr) { |
| 235 SkASSERT(fAnalyticAA); |
| 236 return !vertical_line(edge) || edgePtr <= (SkAnalyticEdge**)fEdgeList ? kNo_
Combine : |
| 237 CombineVertical(edge, edgePtr[-1]); |
| 238 } |
| 239 |
142 int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip, int shift
Up, | 240 int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip, int shift
Up, |
143 bool canCullToTheRight) { | 241 bool canCullToTheRight) { |
144 SkPath::Iter iter(path, true); | 242 SkPath::Iter iter(path, true); |
145 SkPoint pts[4]; | 243 SkPoint pts[4]; |
146 SkPath::Verb verb; | 244 SkPath::Verb verb; |
147 | 245 |
148 int maxEdgeCount = path.countPoints(); | 246 int maxEdgeCount = path.countPoints(); |
149 if (iclip) { | 247 if (iclip) { |
150 // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since | 248 // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since |
151 // we turn portions that are clipped out on the left/right into vertical | 249 // we turn portions that are clipped out on the left/right into vertical |
152 // segments. | 250 // segments. |
153 maxEdgeCount *= SkLineClipper::kMaxClippedLineSegments; | 251 maxEdgeCount *= SkLineClipper::kMaxClippedLineSegments; |
154 } | 252 } |
155 size_t maxEdgeSize = maxEdgeCount * sizeof(SkEdge); | 253 size_t edgeSize = fAnalyticAA ? sizeof(SkAnalyticEdge) : sizeof(SkEdge); |
156 size_t maxEdgePtrSize = maxEdgeCount * sizeof(SkEdge*); | 254 size_t maxEdgeSize = maxEdgeCount * edgeSize; |
| 255 size_t maxEdgePtrSize = maxEdgeCount * sizeof(char*); |
157 | 256 |
158 // lets store the edges and their pointers in the same block | 257 // lets store the edges and their pointers in the same block |
159 char* storage = (char*)fAlloc.allocThrow(maxEdgeSize + maxEdgePtrSize); | 258 char* storage = (char*)fAlloc.allocThrow(maxEdgeSize + maxEdgePtrSize); |
160 SkEdge* edge = reinterpret_cast<SkEdge*>(storage); | 259 char* edge = (char*)storage; |
161 SkEdge** edgePtr = reinterpret_cast<SkEdge**>(storage + maxEdgeSize); | 260 char** edgePtr = (char**)(storage + maxEdgeSize); |
162 // Record the beginning of our pointers, so we can return them to the caller | 261 // Record the beginning of our pointers, so we can return them to the caller |
163 fEdgeList = edgePtr; | 262 fEdgeList = (void**)edgePtr; |
164 | 263 |
165 if (iclip) { | 264 if (iclip) { |
166 SkRect clip; | 265 SkRect clip; |
167 setShiftedClip(&clip, *iclip, shiftUp); | 266 setShiftedClip(&clip, *iclip, shiftUp); |
168 | 267 |
169 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { | 268 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { |
170 switch (verb) { | 269 switch (verb) { |
171 case SkPath::kMove_Verb: | 270 case SkPath::kMove_Verb: |
172 case SkPath::kClose_Verb: | 271 case SkPath::kClose_Verb: |
173 // we ignore these, and just get the whole segment from | 272 // we ignore these, and just get the whole segment from |
174 // the corresponding line/quad/cubic verbs | 273 // the corresponding line/quad/cubic verbs |
175 break; | 274 break; |
176 case SkPath::kLine_Verb: { | 275 case SkPath::kLine_Verb: { |
177 SkPoint lines[SkLineClipper::kMaxPoints]; | 276 SkPoint lines[SkLineClipper::kMaxPoints]; |
178 int lineCount = SkLineClipper::ClipLine(pts, clip, lines, ca
nCullToTheRight); | 277 int lineCount = SkLineClipper::ClipLine(pts, clip, lines, ca
nCullToTheRight); |
179 SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments
); | 278 SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments
); |
180 for (int i = 0; i < lineCount; i++) { | 279 for (int i = 0; i < lineCount; i++) { |
181 if (edge->setLine(lines[i], lines[i + 1], shiftUp)) { | 280 bool setLineResult = fAnalyticAA ? |
182 Combine combine = checkVertical(edge, edgePtr); | 281 ((SkAnalyticEdge*)edge)->setLine(lines[i], lines
[i + 1]) : |
| 282 ((SkEdge*)edge)->setLine(lines[i], lines[i + 1],
shiftUp); |
| 283 if (setLineResult) { |
| 284 Combine combine = fAnalyticAA ? |
| 285 checkVertical((SkAnalyticEdge*)edge, (SkAnal
yticEdge**)edgePtr) : |
| 286 checkVertical((SkEdge*)edge, (SkEdge**)edgeP
tr); |
183 if (kNo_Combine == combine) { | 287 if (kNo_Combine == combine) { |
184 *edgePtr++ = edge++; | 288 *edgePtr++ = edge; |
| 289 edge += edgeSize; |
185 } else if (kTotal_Combine == combine) { | 290 } else if (kTotal_Combine == combine) { |
186 --edgePtr; | 291 --edgePtr; |
187 } | 292 } |
188 } | 293 } |
189 } | 294 } |
190 break; | 295 break; |
191 } | 296 } |
192 default: | 297 default: |
193 SkDEBUGFAIL("unexpected verb"); | 298 SkDEBUGFAIL("unexpected verb"); |
194 break; | 299 break; |
195 } | 300 } |
196 } | 301 } |
197 } else { | 302 } else { |
198 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { | 303 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { |
199 switch (verb) { | 304 switch (verb) { |
200 case SkPath::kMove_Verb: | 305 case SkPath::kMove_Verb: |
201 case SkPath::kClose_Verb: | 306 case SkPath::kClose_Verb: |
202 // we ignore these, and just get the whole segment from | 307 // we ignore these, and just get the whole segment from |
203 // the corresponding line/quad/cubic verbs | 308 // the corresponding line/quad/cubic verbs |
204 break; | 309 break; |
205 case SkPath::kLine_Verb: | 310 case SkPath::kLine_Verb: { |
206 if (edge->setLine(pts[0], pts[1], shiftUp)) { | 311 bool setLineResult = fAnalyticAA ? |
207 Combine combine = checkVertical(edge, edgePtr); | 312 ((SkAnalyticEdge*)edge)->setLine(pts[0], pts[1]) : |
| 313 ((SkEdge*)edge)->setLine(pts[0], pts[1], shiftUp); |
| 314 if (setLineResult) { |
| 315 Combine combine = fAnalyticAA ? |
| 316 checkVertical((SkAnalyticEdge*)edge, (SkAnalytic
Edge**)edgePtr) : |
| 317 checkVertical((SkEdge*)edge, (SkEdge**)edgePtr); |
208 if (kNo_Combine == combine) { | 318 if (kNo_Combine == combine) { |
209 *edgePtr++ = edge++; | 319 *edgePtr++ = edge; |
| 320 edge += edgeSize; |
210 } else if (kTotal_Combine == combine) { | 321 } else if (kTotal_Combine == combine) { |
211 --edgePtr; | 322 --edgePtr; |
212 } | 323 } |
213 } | 324 } |
214 break; | 325 break; |
| 326 } |
215 default: | 327 default: |
216 SkDEBUGFAIL("unexpected verb"); | 328 SkDEBUGFAIL("unexpected verb"); |
217 break; | 329 break; |
218 } | 330 } |
219 } | 331 } |
220 } | 332 } |
221 SkASSERT((char*)edge <= (char*)fEdgeList); | 333 SkASSERT((char*)edge <= (char*)fEdgeList); |
222 SkASSERT(edgePtr - fEdgeList <= maxEdgeCount); | 334 SkASSERT(edgePtr - (char**)fEdgeList <= maxEdgeCount); |
223 return SkToInt(edgePtr - fEdgeList); | 335 return SkToInt(edgePtr - (char**)fEdgeList); |
224 } | 336 } |
225 | 337 |
226 static void handle_quad(SkEdgeBuilder* builder, const SkPoint pts[3]) { | 338 static void handle_quad(SkEdgeBuilder* builder, const SkPoint pts[3]) { |
227 SkPoint monoX[5]; | 339 SkPoint monoX[5]; |
228 int n = SkChopQuadAtYExtrema(pts, monoX); | 340 int n = SkChopQuadAtYExtrema(pts, monoX); |
229 for (int i = 0; i <= n; i++) { | 341 for (int i = 0; i <= n; i++) { |
230 builder->addQuad(&monoX[i * 2]); | 342 builder->addQuad(&monoX[i * 2]); |
231 } | 343 } |
232 } | 344 } |
233 | 345 |
234 int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, int shiftUp, | 346 int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, int shiftUp, |
235 bool canCullToTheRight) { | 347 bool canCullToTheRight, bool analyticAA) { |
236 fAlloc.reset(); | 348 fAlloc.reset(); |
237 fList.reset(); | 349 fList.reset(); |
238 fShiftUp = shiftUp; | 350 fShiftUp = shiftUp; |
| 351 fAnalyticAA = analyticAA; |
239 | 352 |
240 if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) { | 353 if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) { |
241 return this->buildPoly(path, iclip, shiftUp, canCullToTheRight); | 354 return this->buildPoly(path, iclip, shiftUp, canCullToTheRight); |
242 } | 355 } |
243 | 356 |
244 SkAutoConicToQuads quadder; | 357 SkAutoConicToQuads quadder; |
245 const SkScalar conicTol = SK_Scalar1 / 4; | 358 const SkScalar conicTol = SK_Scalar1 / 4; |
246 | 359 |
247 SkPath::Iter iter(path, true); | 360 SkPath::Iter iter(path, true); |
248 SkPoint pts[4]; | 361 SkPoint pts[4]; |
(...skipping 77 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
326 } | 439 } |
327 default: | 440 default: |
328 SkDEBUGFAIL("unexpected verb"); | 441 SkDEBUGFAIL("unexpected verb"); |
329 break; | 442 break; |
330 } | 443 } |
331 } | 444 } |
332 } | 445 } |
333 fEdgeList = fList.begin(); | 446 fEdgeList = fList.begin(); |
334 return fList.count(); | 447 return fList.count(); |
335 } | 448 } |
OLD | NEW |