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 15 template <typename T> static T* typedAllocThrow(SkChunkAlloc& alloc) { 16 return static_cast<T*>(alloc.allocThrow(sizeof(T))); 17 } 18 19 /////////////////////////////////////////////////////////////////////////////// 20 21 SkEdgeBuilder::SkEdgeBuilder() : fAlloc(16*1024) { 22 fEdgeList = NULL; 23 } 24 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 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 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 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 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 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 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 164 int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, 165 int shiftUp) { 166 fAlloc.reset(); 167 fList.reset(); 168 fShiftUp = shiftUp; 169 170 SkScalar conicTol = SK_ScalarHalf * (1 << shiftUp); 171 172 if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) { 173 return this->buildPoly(path, iclip, shiftUp); 174 } 175 176 SkPath::Iter iter(path, true); 177 SkPoint pts[4]; 178 SkPath::Verb verb; 179 180 if (iclip) { 181 SkRect clip; 182 setShiftedClip(&clip, *iclip, shiftUp); 183 SkEdgeClipper clipper; 184 185 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 186 switch (verb) { 187 case SkPath::kMove_Verb: 188 case SkPath::kClose_Verb: 189 // we ignore these, and just get the whole segment from 190 // the corresponding line/quad/cubic verbs 191 break; 192 case SkPath::kLine_Verb: { 193 SkPoint lines[SkLineClipper::kMaxPoints]; 194 int lineCount = SkLineClipper::ClipLine(pts, clip, lines); 195 for (int i = 0; i < lineCount; i++) { 196 this->addLine(&lines[i]); 197 } 198 break; 199 } 200 case SkPath::kQuad_Verb: 201 if (clipper.clipQuad(pts, clip)) { 202 this->addClipper(&clipper); 203 } 204 break; 205 case SkPath::kConic_Verb: { 206 const int MAX_POW2 = 4; 207 const int MAX_QUADS = 1 << MAX_POW2; 208 const int MAX_QUAD_PTS = 1 + 2 * MAX_QUADS; 209 SkPoint storage[MAX_QUAD_PTS]; 210 211 SkConic conic; 212 conic.set(pts, iter.conicWeight()); 213 int pow2 = conic.computeQuadPOW2(conicTol); 214 pow2 = SkMin32(pow2, MAX_POW2); 215 int quadCount = conic.chopIntoQuadsPOW2(storage, pow2); 216 SkASSERT(quadCount <= MAX_QUADS); 217 for (int i = 0; i < quadCount; ++i) { 218 if (clipper.clipQuad(&storage[i * 2], clip)) { 219 this->addClipper(&clipper); 220 } 221 } 222 } break; 223 case SkPath::kCubic_Verb: 224 if (clipper.clipCubic(pts, clip)) { 225 this->addClipper(&clipper); 226 } 227 break; 228 default: 229 SkDEBUGFAIL("unexpected verb"); 230 break; 231 } 232 } 233 } else { 234 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 235 switch (verb) { 236 case SkPath::kMove_Verb: 237 case SkPath::kClose_Verb: 238 // we ignore these, and just get the whole segment from 239 // the corresponding line/quad/cubic verbs 240 break; 241 case SkPath::kLine_Verb: 242 this->addLine(pts); 243 break; 244 case SkPath::kQuad_Verb: { 245 handle_quad(this, pts); 246 break; 247 } 248 case SkPath::kConic_Verb: { 249 const int MAX_POW2 = 4; 250 const int MAX_QUADS = 1 << MAX_POW2; 251 const int MAX_QUAD_PTS = 1 + 2 * MAX_QUADS; 252 SkPoint storage[MAX_QUAD_PTS]; 253 254 SkConic conic; 255 conic.set(pts, iter.conicWeight()); 256 int pow2 = conic.computeQuadPOW2(conicTol); 257 pow2 = SkMin32(pow2, MAX_POW2); 258 int quadCount = conic.chopIntoQuadsPOW2(storage, pow2); 259 SkASSERT(quadCount <= MAX_QUADS); 260 for (int i = 0; i < quadCount; ++i) { 261 handle_quad(this, &storage[i * 2]); 262 } 263 } break; 264 case SkPath::kCubic_Verb: { 265 SkPoint monoY[10]; 266 int n = SkChopCubicAtYExtrema(pts, monoY); 267 for (int i = 0; i <= n; i++) { 268 this->addCubic(&monoY[i * 3]); 269 } 270 break; 271 } 272 default: 273 SkDEBUGFAIL("unexpected verb"); 274 break; 275 } 276 } 277 } 278 fEdgeList = fList.begin(); 279 return fList.count(); 280 } 281
