SkEdgeBuilder.cpp revision 38f1c00772539dcbeccbfa3c45d94bdc4acf3518
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 15template <typename T> static T* typedAllocThrow(SkChunkAlloc& alloc) { 16 return static_cast<T*>(alloc.allocThrow(sizeof(T))); 17} 18 19/////////////////////////////////////////////////////////////////////////////// 20 21SkEdgeBuilder::SkEdgeBuilder() : fAlloc(16*1024) { 22 fEdgeList = NULL; 23} 24 25void 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 34void 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 43void 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 52void 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 75static 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 82int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip, int shiftUp, 83 bool clipToTheRight) { 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, clipToTheRight); 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 156static 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 164int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, int shiftUp, 165 bool clipToTheRight) { 166 fAlloc.reset(); 167 fList.reset(); 168 fShiftUp = shiftUp; 169 170 if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) { 171 return this->buildPoly(path, iclip, shiftUp, clipToTheRight); 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; 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, clipToTheRight); 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