epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2011 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 | */ |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 7 | #include "SkEdgeBuilder.h" |
| 8 | #include "SkPath.h" |
| 9 | #include "SkEdge.h" |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 10 | #include "SkAnalyticEdge.h" |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 11 | #include "SkEdgeClipper.h" |
| 12 | #include "SkLineClipper.h" |
| 13 | #include "SkGeometry.h" |
| 14 | |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 15 | /////////////////////////////////////////////////////////////////////////////// |
| 16 | |
Cary Clark | cd0a61e | 2017-04-14 14:29:33 -0400 | [diff] [blame] | 17 | SkEdgeBuilder::SkEdgeBuilder() { |
Mike Klein | 2b46f3e | 2017-03-02 22:04:55 +0000 | [diff] [blame] | 18 | fEdgeList = nullptr; |
| 19 | } |
reed@google.com | c8d640b | 2012-08-02 14:26:43 +0000 | [diff] [blame] | 20 | |
caryclark | afd25f7 | 2016-01-30 14:07:20 -0800 | [diff] [blame] | 21 | SkEdgeBuilder::Combine SkEdgeBuilder::CombineVertical(const SkEdge* edge, SkEdge* last) { |
| 22 | if (last->fCurveCount || last->fDX || edge->fX != last->fX) { |
| 23 | return kNo_Combine; |
| 24 | } |
| 25 | if (edge->fWinding == last->fWinding) { |
| 26 | if (edge->fLastY + 1 == last->fFirstY) { |
| 27 | last->fFirstY = edge->fFirstY; |
| 28 | return kPartial_Combine; |
| 29 | } |
| 30 | if (edge->fFirstY == last->fLastY + 1) { |
| 31 | last->fLastY = edge->fLastY; |
| 32 | return kPartial_Combine; |
| 33 | } |
| 34 | return kNo_Combine; |
| 35 | } |
| 36 | if (edge->fFirstY == last->fFirstY) { |
| 37 | if (edge->fLastY == last->fLastY) { |
| 38 | return kTotal_Combine; |
| 39 | } |
| 40 | if (edge->fLastY < last->fLastY) { |
| 41 | last->fFirstY = edge->fLastY + 1; |
| 42 | return kPartial_Combine; |
| 43 | } |
| 44 | last->fFirstY = last->fLastY + 1; |
| 45 | last->fLastY = edge->fLastY; |
| 46 | last->fWinding = edge->fWinding; |
| 47 | return kPartial_Combine; |
| 48 | } |
| 49 | if (edge->fLastY == last->fLastY) { |
| 50 | if (edge->fFirstY > last->fFirstY) { |
| 51 | last->fLastY = edge->fFirstY - 1; |
| 52 | return kPartial_Combine; |
| 53 | } |
| 54 | last->fLastY = last->fFirstY - 1; |
| 55 | last->fFirstY = edge->fFirstY; |
| 56 | last->fWinding = edge->fWinding; |
| 57 | return kPartial_Combine; |
| 58 | } |
| 59 | return kNo_Combine; |
| 60 | } |
| 61 | |
liyuqian | 451ceba | 2016-11-07 08:10:44 -0800 | [diff] [blame] | 62 | static inline bool approximatelyEqual(SkFixed a, SkFixed b) { |
| 63 | return SkAbs32(a - b) < 0x100; |
| 64 | } |
| 65 | |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 66 | SkEdgeBuilder::Combine SkEdgeBuilder::CombineVertical( |
| 67 | const SkAnalyticEdge* edge, SkAnalyticEdge* last) { |
Yuqian Li | df60e36 | 2017-07-25 11:26:31 -0400 | [diff] [blame] | 68 | SkASSERT(fEdgeType == kAnalyticEdge); |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 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 | } |
liyuqian | 451ceba | 2016-11-07 08:10:44 -0800 | [diff] [blame] | 78 | if (approximatelyEqual(edge->fUpperY, last->fLowerY)) { |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 79 | last->fLowerY = edge->fLowerY; |
| 80 | return kPartial_Combine; |
| 81 | } |
| 82 | return kNo_Combine; |
| 83 | } |
liyuqian | 451ceba | 2016-11-07 08:10:44 -0800 | [diff] [blame] | 84 | if (approximatelyEqual(edge->fUpperY, last->fUpperY)) { |
| 85 | if (approximatelyEqual(edge->fLowerY, last->fLowerY)) { |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 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 | } |
liyuqian | 451ceba | 2016-11-07 08:10:44 -0800 | [diff] [blame] | 99 | if (approximatelyEqual(edge->fLowerY, last->fLowerY)) { |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 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) { |
Yuqian Li | df60e36 | 2017-07-25 11:26:31 -0400 | [diff] [blame] | 118 | SkASSERT(fEdgeType == kAnalyticEdge); |
caryclark | afd25f7 | 2016-01-30 14:07:20 -0800 | [diff] [blame] | 119 | return !edge->fDX && !edge->fCurveCount; |
| 120 | } |
| 121 | |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 122 | void SkEdgeBuilder::addLine(const SkPoint pts[]) { |
Yuqian Li | df60e36 | 2017-07-25 11:26:31 -0400 | [diff] [blame] | 123 | if (fEdgeType == kBezier) { |
| 124 | SkLine* line = fAlloc.make<SkLine>(); |
| 125 | if (line->set(pts)) { |
| 126 | fList.push(line); |
| 127 | } |
| 128 | } else if (fEdgeType == kAnalyticEdge) { |
Herb Derby | 4b1b04d | 2017-03-01 13:44:39 -0500 | [diff] [blame] | 129 | SkAnalyticEdge* edge = fAlloc.make<SkAnalyticEdge>(); |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 130 | if (edge->setLine(pts[0], pts[1])) { |
| 131 | if (vertical_line(edge) && fList.count()) { |
| 132 | Combine combine = CombineVertical(edge, (SkAnalyticEdge*)*(fList.end() - 1)); |
| 133 | if (kNo_Combine != combine) { |
| 134 | if (kTotal_Combine == combine) { |
| 135 | fList.pop(); |
| 136 | } |
| 137 | goto unallocate_analytic_edge; |
caryclark | afd25f7 | 2016-01-30 14:07:20 -0800 | [diff] [blame] | 138 | } |
caryclark | afd25f7 | 2016-01-30 14:07:20 -0800 | [diff] [blame] | 139 | } |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 140 | fList.push(edge); |
| 141 | } else { |
| 142 | unallocate_analytic_edge: |
| 143 | ; |
| 144 | // TODO: unallocate edge from storage... |
caryclark | afd25f7 | 2016-01-30 14:07:20 -0800 | [diff] [blame] | 145 | } |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 146 | } else { |
Herb Derby | 4b1b04d | 2017-03-01 13:44:39 -0500 | [diff] [blame] | 147 | SkEdge* edge = fAlloc.make<SkEdge>(); |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 148 | if (edge->setLine(pts[0], pts[1], fShiftUp)) { |
| 149 | if (vertical_line(edge) && fList.count()) { |
| 150 | Combine combine = CombineVertical(edge, (SkEdge*)*(fList.end() - 1)); |
| 151 | if (kNo_Combine != combine) { |
| 152 | if (kTotal_Combine == combine) { |
| 153 | fList.pop(); |
| 154 | } |
| 155 | goto unallocate_edge; |
| 156 | } |
| 157 | } |
| 158 | fList.push(edge); |
| 159 | } else { |
caryclark | afd25f7 | 2016-01-30 14:07:20 -0800 | [diff] [blame] | 160 | unallocate_edge: |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 161 | ; |
| 162 | // TODO: unallocate edge from storage... |
| 163 | } |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 164 | } |
| 165 | } |
| 166 | |
| 167 | void SkEdgeBuilder::addQuad(const SkPoint pts[]) { |
Yuqian Li | df60e36 | 2017-07-25 11:26:31 -0400 | [diff] [blame] | 168 | if (fEdgeType == kBezier) { |
| 169 | SkQuad* quad = fAlloc.make<SkQuad>(); |
| 170 | if (quad->set(pts)) { |
| 171 | fList.push(quad); |
| 172 | } |
| 173 | } else if (fEdgeType == kAnalyticEdge) { |
Herb Derby | 4b1b04d | 2017-03-01 13:44:39 -0500 | [diff] [blame] | 174 | SkAnalyticQuadraticEdge* edge = fAlloc.make<SkAnalyticQuadraticEdge>(); |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 175 | if (edge->setQuadratic(pts)) { |
| 176 | fList.push(edge); |
| 177 | } else { |
| 178 | // TODO: unallocate edge from storage... |
| 179 | } |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 180 | } else { |
Herb Derby | 4b1b04d | 2017-03-01 13:44:39 -0500 | [diff] [blame] | 181 | SkQuadraticEdge* edge = fAlloc.make<SkQuadraticEdge>(); |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 182 | if (edge->setQuadratic(pts, fShiftUp)) { |
| 183 | fList.push(edge); |
| 184 | } else { |
| 185 | // TODO: unallocate edge from storage... |
| 186 | } |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 187 | } |
| 188 | } |
| 189 | |
| 190 | void SkEdgeBuilder::addCubic(const SkPoint pts[]) { |
Yuqian Li | df60e36 | 2017-07-25 11:26:31 -0400 | [diff] [blame] | 191 | if (fEdgeType == kBezier) { |
| 192 | SkCubic* cubic = fAlloc.make<SkCubic>(); |
| 193 | if (cubic->set(pts)) { |
| 194 | fList.push(cubic); |
| 195 | } |
| 196 | } else if (fEdgeType == kAnalyticEdge) { |
Herb Derby | 4b1b04d | 2017-03-01 13:44:39 -0500 | [diff] [blame] | 197 | SkAnalyticCubicEdge* edge = fAlloc.make<SkAnalyticCubicEdge>(); |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 198 | if (edge->setCubic(pts)) { |
| 199 | fList.push(edge); |
| 200 | } else { |
| 201 | // TODO: unallocate edge from storage... |
| 202 | } |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 203 | } else { |
Herb Derby | 4b1b04d | 2017-03-01 13:44:39 -0500 | [diff] [blame] | 204 | SkCubicEdge* edge = fAlloc.make<SkCubicEdge>(); |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 205 | if (edge->setCubic(pts, fShiftUp)) { |
| 206 | fList.push(edge); |
| 207 | } else { |
| 208 | // TODO: unallocate edge from storage... |
| 209 | } |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 210 | } |
| 211 | } |
| 212 | |
| 213 | void SkEdgeBuilder::addClipper(SkEdgeClipper* clipper) { |
| 214 | SkPoint pts[4]; |
| 215 | SkPath::Verb verb; |
| 216 | |
| 217 | while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) { |
| 218 | switch (verb) { |
| 219 | case SkPath::kLine_Verb: |
| 220 | this->addLine(pts); |
| 221 | break; |
| 222 | case SkPath::kQuad_Verb: |
| 223 | this->addQuad(pts); |
| 224 | break; |
| 225 | case SkPath::kCubic_Verb: |
| 226 | this->addCubic(pts); |
| 227 | break; |
| 228 | default: |
| 229 | break; |
| 230 | } |
| 231 | } |
| 232 | } |
| 233 | |
| 234 | /////////////////////////////////////////////////////////////////////////////// |
| 235 | |
| 236 | static void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) { |
| 237 | dst->set(SkIntToScalar(src.fLeft >> shift), |
| 238 | SkIntToScalar(src.fTop >> shift), |
| 239 | SkIntToScalar(src.fRight >> shift), |
| 240 | SkIntToScalar(src.fBottom >> shift)); |
| 241 | } |
| 242 | |
caryclark | afd25f7 | 2016-01-30 14:07:20 -0800 | [diff] [blame] | 243 | SkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkEdge* edge, SkEdge** edgePtr) { |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 244 | return !vertical_line(edge) || edgePtr <= (SkEdge**)fEdgeList ? kNo_Combine : |
| 245 | CombineVertical(edge, edgePtr[-1]); |
| 246 | } |
| 247 | |
| 248 | SkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkAnalyticEdge* edge, |
| 249 | SkAnalyticEdge** edgePtr) { |
Yuqian Li | df60e36 | 2017-07-25 11:26:31 -0400 | [diff] [blame] | 250 | SkASSERT(fEdgeType == kAnalyticEdge); |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 251 | return !vertical_line(edge) || edgePtr <= (SkAnalyticEdge**)fEdgeList ? kNo_Combine : |
caryclark | afd25f7 | 2016-01-30 14:07:20 -0800 | [diff] [blame] | 252 | CombineVertical(edge, edgePtr[-1]); |
| 253 | } |
| 254 | |
reed | 01d3319 | 2015-02-07 12:18:41 -0800 | [diff] [blame] | 255 | int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip, int shiftUp, |
reed | 31223e0 | 2015-02-09 08:33:07 -0800 | [diff] [blame] | 256 | bool canCullToTheRight) { |
reed@google.com | c8d640b | 2012-08-02 14:26:43 +0000 | [diff] [blame] | 257 | SkPath::Iter iter(path, true); |
| 258 | SkPoint pts[4]; |
| 259 | SkPath::Verb verb; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 260 | |
reed@google.com | c8d640b | 2012-08-02 14:26:43 +0000 | [diff] [blame] | 261 | int maxEdgeCount = path.countPoints(); |
| 262 | if (iclip) { |
| 263 | // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since |
| 264 | // we turn portions that are clipped out on the left/right into vertical |
| 265 | // segments. |
| 266 | maxEdgeCount *= SkLineClipper::kMaxClippedLineSegments; |
| 267 | } |
reed@google.com | c8d640b | 2012-08-02 14:26:43 +0000 | [diff] [blame] | 268 | |
Yuqian Li | df60e36 | 2017-07-25 11:26:31 -0400 | [diff] [blame] | 269 | size_t edgeSize; |
| 270 | char* edge; |
| 271 | switch (fEdgeType) { |
| 272 | case kEdge: |
| 273 | edgeSize = sizeof(SkEdge); |
| 274 | edge = (char*)fAlloc.makeArrayDefault<SkEdge>(maxEdgeCount); |
| 275 | break; |
| 276 | case kAnalyticEdge: |
| 277 | edgeSize = sizeof(SkAnalyticEdge); |
| 278 | edge = (char*)fAlloc.makeArrayDefault<SkAnalyticEdge>(maxEdgeCount); |
| 279 | break; |
| 280 | case kBezier: |
| 281 | edgeSize = sizeof(SkLine); |
| 282 | edge = (char*)fAlloc.makeArrayDefault<SkLine>(maxEdgeCount); |
| 283 | break; |
| 284 | } |
Herb Derby | 4b1b04d | 2017-03-01 13:44:39 -0500 | [diff] [blame] | 285 | |
| 286 | SkDEBUGCODE(char* edgeStart = edge); |
| 287 | char** edgePtr = fAlloc.makeArrayDefault<char*>(maxEdgeCount); |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 288 | fEdgeList = (void**)edgePtr; |
reed@google.com | c8d640b | 2012-08-02 14:26:43 +0000 | [diff] [blame] | 289 | |
| 290 | if (iclip) { |
| 291 | SkRect clip; |
| 292 | setShiftedClip(&clip, *iclip, shiftUp); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 293 | |
reed@google.com | c8d640b | 2012-08-02 14:26:43 +0000 | [diff] [blame] | 294 | while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { |
| 295 | switch (verb) { |
| 296 | case SkPath::kMove_Verb: |
| 297 | case SkPath::kClose_Verb: |
| 298 | // we ignore these, and just get the whole segment from |
| 299 | // the corresponding line/quad/cubic verbs |
| 300 | break; |
| 301 | case SkPath::kLine_Verb: { |
| 302 | SkPoint lines[SkLineClipper::kMaxPoints]; |
reed | 31223e0 | 2015-02-09 08:33:07 -0800 | [diff] [blame] | 303 | int lineCount = SkLineClipper::ClipLine(pts, clip, lines, canCullToTheRight); |
reed@google.com | c8d640b | 2012-08-02 14:26:43 +0000 | [diff] [blame] | 304 | SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments); |
| 305 | for (int i = 0; i < lineCount; i++) { |
Yuqian Li | df60e36 | 2017-07-25 11:26:31 -0400 | [diff] [blame] | 306 | this->addPolyLine(lines + i, edge, edgeSize, edgePtr, shiftUp); |
reed@google.com | c8d640b | 2012-08-02 14:26:43 +0000 | [diff] [blame] | 307 | } |
| 308 | break; |
| 309 | } |
| 310 | default: |
| 311 | SkDEBUGFAIL("unexpected verb"); |
| 312 | break; |
| 313 | } |
| 314 | } |
| 315 | } else { |
| 316 | while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { |
| 317 | switch (verb) { |
| 318 | case SkPath::kMove_Verb: |
| 319 | case SkPath::kClose_Verb: |
| 320 | // we ignore these, and just get the whole segment from |
| 321 | // the corresponding line/quad/cubic verbs |
| 322 | break; |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 323 | case SkPath::kLine_Verb: { |
Yuqian Li | df60e36 | 2017-07-25 11:26:31 -0400 | [diff] [blame] | 324 | this->addPolyLine(pts, edge, edgeSize, edgePtr, shiftUp); |
reed@google.com | c8d640b | 2012-08-02 14:26:43 +0000 | [diff] [blame] | 325 | break; |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 326 | } |
reed@google.com | c8d640b | 2012-08-02 14:26:43 +0000 | [diff] [blame] | 327 | default: |
| 328 | SkDEBUGFAIL("unexpected verb"); |
| 329 | break; |
| 330 | } |
| 331 | } |
| 332 | } |
Herb Derby | 4b1b04d | 2017-03-01 13:44:39 -0500 | [diff] [blame] | 333 | SkASSERT((size_t)(edge - edgeStart) <= maxEdgeCount * edgeSize); |
liyuqian | 38911a7 | 2016-10-04 11:23:22 -0700 | [diff] [blame] | 334 | SkASSERT(edgePtr - (char**)fEdgeList <= maxEdgeCount); |
| 335 | return SkToInt(edgePtr - (char**)fEdgeList); |
reed@google.com | c8d640b | 2012-08-02 14:26:43 +0000 | [diff] [blame] | 336 | } |
| 337 | |
reed@google.com | 277c3f8 | 2013-05-31 15:17:50 +0000 | [diff] [blame] | 338 | static void handle_quad(SkEdgeBuilder* builder, const SkPoint pts[3]) { |
| 339 | SkPoint monoX[5]; |
| 340 | int n = SkChopQuadAtYExtrema(pts, monoX); |
| 341 | for (int i = 0; i <= n; i++) { |
| 342 | builder->addQuad(&monoX[i * 2]); |
| 343 | } |
| 344 | } |
| 345 | |
reed | 01d3319 | 2015-02-07 12:18:41 -0800 | [diff] [blame] | 346 | int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, int shiftUp, |
Yuqian Li | df60e36 | 2017-07-25 11:26:31 -0400 | [diff] [blame] | 347 | bool canCullToTheRight, EdgeType edgeType) { |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 348 | fAlloc.reset(); |
| 349 | fList.reset(); |
| 350 | fShiftUp = shiftUp; |
Yuqian Li | df60e36 | 2017-07-25 11:26:31 -0400 | [diff] [blame] | 351 | fEdgeType = edgeType; |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 352 | |
reed@google.com | c8d640b | 2012-08-02 14:26:43 +0000 | [diff] [blame] | 353 | if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) { |
reed | 31223e0 | 2015-02-09 08:33:07 -0800 | [diff] [blame] | 354 | return this->buildPoly(path, iclip, shiftUp, canCullToTheRight); |
reed@google.com | c8d640b | 2012-08-02 14:26:43 +0000 | [diff] [blame] | 355 | } |
| 356 | |
reed | 220f926 | 2014-12-17 08:21:04 -0800 | [diff] [blame] | 357 | SkAutoConicToQuads quadder; |
reed | 3f4e045 | 2015-01-06 07:44:21 -0800 | [diff] [blame] | 358 | const SkScalar conicTol = SK_Scalar1 / 4; |
reed | 220f926 | 2014-12-17 08:21:04 -0800 | [diff] [blame] | 359 | |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 360 | SkPath::Iter iter(path, true); |
| 361 | SkPoint pts[4]; |
| 362 | SkPath::Verb verb; |
| 363 | |
| 364 | if (iclip) { |
| 365 | SkRect clip; |
| 366 | setShiftedClip(&clip, *iclip, shiftUp); |
reed | 31223e0 | 2015-02-09 08:33:07 -0800 | [diff] [blame] | 367 | SkEdgeClipper clipper(canCullToTheRight); |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 368 | |
reed@google.com | 4a3b714 | 2012-05-16 17:16:46 +0000 | [diff] [blame] | 369 | while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 370 | switch (verb) { |
| 371 | case SkPath::kMove_Verb: |
| 372 | case SkPath::kClose_Verb: |
| 373 | // we ignore these, and just get the whole segment from |
| 374 | // the corresponding line/quad/cubic verbs |
| 375 | break; |
Mike Reed | 5baafa8 | 2017-01-26 14:21:26 -0500 | [diff] [blame] | 376 | case SkPath::kLine_Verb: |
| 377 | if (clipper.clipLine(pts[0], pts[1], clip)) { |
| 378 | this->addClipper(&clipper); |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 379 | } |
| 380 | break; |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 381 | case SkPath::kQuad_Verb: |
| 382 | if (clipper.clipQuad(pts, clip)) { |
| 383 | this->addClipper(&clipper); |
| 384 | } |
| 385 | break; |
reed@google.com | 277c3f8 | 2013-05-31 15:17:50 +0000 | [diff] [blame] | 386 | case SkPath::kConic_Verb: { |
reed | 220f926 | 2014-12-17 08:21:04 -0800 | [diff] [blame] | 387 | const SkPoint* quadPts = quadder.computeQuads( |
| 388 | pts, iter.conicWeight(), conicTol); |
| 389 | for (int i = 0; i < quadder.countQuads(); ++i) { |
| 390 | if (clipper.clipQuad(quadPts, clip)) { |
reed@google.com | 277c3f8 | 2013-05-31 15:17:50 +0000 | [diff] [blame] | 391 | this->addClipper(&clipper); |
| 392 | } |
reed | 220f926 | 2014-12-17 08:21:04 -0800 | [diff] [blame] | 393 | quadPts += 2; |
reed@google.com | 277c3f8 | 2013-05-31 15:17:50 +0000 | [diff] [blame] | 394 | } |
| 395 | } break; |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 396 | case SkPath::kCubic_Verb: |
| 397 | if (clipper.clipCubic(pts, clip)) { |
| 398 | this->addClipper(&clipper); |
| 399 | } |
| 400 | break; |
| 401 | default: |
tomhudson@google.com | 0c00f21 | 2011-12-28 14:59:50 +0000 | [diff] [blame] | 402 | SkDEBUGFAIL("unexpected verb"); |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 403 | break; |
| 404 | } |
| 405 | } |
| 406 | } else { |
reed@google.com | 4a3b714 | 2012-05-16 17:16:46 +0000 | [diff] [blame] | 407 | while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 408 | switch (verb) { |
| 409 | case SkPath::kMove_Verb: |
| 410 | case SkPath::kClose_Verb: |
| 411 | // we ignore these, and just get the whole segment from |
| 412 | // the corresponding line/quad/cubic verbs |
| 413 | break; |
| 414 | case SkPath::kLine_Verb: |
| 415 | this->addLine(pts); |
| 416 | break; |
| 417 | case SkPath::kQuad_Verb: { |
reed@google.com | 277c3f8 | 2013-05-31 15:17:50 +0000 | [diff] [blame] | 418 | handle_quad(this, pts); |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 419 | break; |
| 420 | } |
reed@google.com | 277c3f8 | 2013-05-31 15:17:50 +0000 | [diff] [blame] | 421 | case SkPath::kConic_Verb: { |
reed | 220f926 | 2014-12-17 08:21:04 -0800 | [diff] [blame] | 422 | const SkPoint* quadPts = quadder.computeQuads( |
| 423 | pts, iter.conicWeight(), conicTol); |
| 424 | for (int i = 0; i < quadder.countQuads(); ++i) { |
| 425 | handle_quad(this, quadPts); |
| 426 | quadPts += 2; |
reed@google.com | 277c3f8 | 2013-05-31 15:17:50 +0000 | [diff] [blame] | 427 | } |
| 428 | } break; |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 429 | case SkPath::kCubic_Verb: { |
Yuqian Li | 5eb8fc5 | 2017-08-08 14:00:52 -0400 | [diff] [blame] | 430 | if (fEdgeType == kBezier) { |
| 431 | this->addCubic(pts); |
| 432 | break; |
| 433 | } |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 434 | SkPoint monoY[10]; |
| 435 | int n = SkChopCubicAtYExtrema(pts, monoY); |
| 436 | for (int i = 0; i <= n; i++) { |
| 437 | this->addCubic(&monoY[i * 3]); |
| 438 | } |
| 439 | break; |
| 440 | } |
| 441 | default: |
tomhudson@google.com | 0c00f21 | 2011-12-28 14:59:50 +0000 | [diff] [blame] | 442 | SkDEBUGFAIL("unexpected verb"); |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 443 | break; |
| 444 | } |
| 445 | } |
| 446 | } |
reed@google.com | c8d640b | 2012-08-02 14:26:43 +0000 | [diff] [blame] | 447 | fEdgeList = fList.begin(); |
reed@android.com | 909994f | 2009-11-18 16:09:51 +0000 | [diff] [blame] | 448 | return fList.count(); |
| 449 | } |
Yuqian Li | 1c84088 | 2017-05-26 14:50:35 -0400 | [diff] [blame] | 450 | |
| 451 | int SkEdgeBuilder::build_edges(const SkPath& path, const SkIRect* shiftedClip, |
Yuqian Li | df60e36 | 2017-07-25 11:26:31 -0400 | [diff] [blame] | 452 | int shiftEdgesUp, bool pathContainedInClip, EdgeType edgeType) { |
Yuqian Li | 1c84088 | 2017-05-26 14:50:35 -0400 | [diff] [blame] | 453 | // If we're convex, then we need both edges, even the right edge is past the clip |
| 454 | const bool canCullToTheRight = !path.isConvex(); |
| 455 | |
| 456 | const SkIRect* builderClip = pathContainedInClip ? nullptr : shiftedClip; |
Yuqian Li | df60e36 | 2017-07-25 11:26:31 -0400 | [diff] [blame] | 457 | int count = this->build(path, builderClip, shiftEdgesUp, canCullToTheRight, edgeType); |
Yuqian Li | 1c84088 | 2017-05-26 14:50:35 -0400 | [diff] [blame] | 458 | SkASSERT(count >= 0); |
| 459 | |
Yuqian Li | a81b626 | 2017-09-06 17:10:05 -0400 | [diff] [blame] | 460 | // canCullToRight == false should imply count != 1 if edgeType != kBezier. |
| 461 | // If edgeType == kBezier (DAA), we don't chop edges at y extrema so count == 1 is valid. |
| 462 | // For example, a single cubic edge with a valley shape \_/ is fine for DAA. |
| 463 | SkASSERT(edgeType == kBezier || canCullToTheRight || count != 1); |
Yuqian Li | 1c84088 | 2017-05-26 14:50:35 -0400 | [diff] [blame] | 464 | |
| 465 | return count; |
| 466 | } |