1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkEdgeBuilder.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,280 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2011 Google Inc.
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +#include "SkEdgeBuilder.h"
1.12 +#include "SkPath.h"
1.13 +#include "SkEdge.h"
1.14 +#include "SkEdgeClipper.h"
1.15 +#include "SkLineClipper.h"
1.16 +#include "SkGeometry.h"
1.17 +
1.18 +template <typename T> static T* typedAllocThrow(SkChunkAlloc& alloc) {
1.19 + return static_cast<T*>(alloc.allocThrow(sizeof(T)));
1.20 +}
1.21 +
1.22 +///////////////////////////////////////////////////////////////////////////////
1.23 +
1.24 +SkEdgeBuilder::SkEdgeBuilder() : fAlloc(16*1024) {
1.25 + fEdgeList = NULL;
1.26 +}
1.27 +
1.28 +void SkEdgeBuilder::addLine(const SkPoint pts[]) {
1.29 + SkEdge* edge = typedAllocThrow<SkEdge>(fAlloc);
1.30 + if (edge->setLine(pts[0], pts[1], fShiftUp)) {
1.31 + fList.push(edge);
1.32 + } else {
1.33 + // TODO: unallocate edge from storage...
1.34 + }
1.35 +}
1.36 +
1.37 +void SkEdgeBuilder::addQuad(const SkPoint pts[]) {
1.38 + SkQuadraticEdge* edge = typedAllocThrow<SkQuadraticEdge>(fAlloc);
1.39 + if (edge->setQuadratic(pts, fShiftUp)) {
1.40 + fList.push(edge);
1.41 + } else {
1.42 + // TODO: unallocate edge from storage...
1.43 + }
1.44 +}
1.45 +
1.46 +void SkEdgeBuilder::addCubic(const SkPoint pts[]) {
1.47 + SkCubicEdge* edge = typedAllocThrow<SkCubicEdge>(fAlloc);
1.48 + if (edge->setCubic(pts, NULL, fShiftUp)) {
1.49 + fList.push(edge);
1.50 + } else {
1.51 + // TODO: unallocate edge from storage...
1.52 + }
1.53 +}
1.54 +
1.55 +void SkEdgeBuilder::addClipper(SkEdgeClipper* clipper) {
1.56 + SkPoint pts[4];
1.57 + SkPath::Verb verb;
1.58 +
1.59 + while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) {
1.60 + switch (verb) {
1.61 + case SkPath::kLine_Verb:
1.62 + this->addLine(pts);
1.63 + break;
1.64 + case SkPath::kQuad_Verb:
1.65 + this->addQuad(pts);
1.66 + break;
1.67 + case SkPath::kCubic_Verb:
1.68 + this->addCubic(pts);
1.69 + break;
1.70 + default:
1.71 + break;
1.72 + }
1.73 + }
1.74 +}
1.75 +
1.76 +///////////////////////////////////////////////////////////////////////////////
1.77 +
1.78 +static void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) {
1.79 + dst->set(SkIntToScalar(src.fLeft >> shift),
1.80 + SkIntToScalar(src.fTop >> shift),
1.81 + SkIntToScalar(src.fRight >> shift),
1.82 + SkIntToScalar(src.fBottom >> shift));
1.83 +}
1.84 +
1.85 +int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip,
1.86 + int shiftUp) {
1.87 + SkPath::Iter iter(path, true);
1.88 + SkPoint pts[4];
1.89 + SkPath::Verb verb;
1.90 +
1.91 + int maxEdgeCount = path.countPoints();
1.92 + if (iclip) {
1.93 + // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since
1.94 + // we turn portions that are clipped out on the left/right into vertical
1.95 + // segments.
1.96 + maxEdgeCount *= SkLineClipper::kMaxClippedLineSegments;
1.97 + }
1.98 + size_t maxEdgeSize = maxEdgeCount * sizeof(SkEdge);
1.99 + size_t maxEdgePtrSize = maxEdgeCount * sizeof(SkEdge*);
1.100 +
1.101 + // lets store the edges and their pointers in the same block
1.102 + char* storage = (char*)fAlloc.allocThrow(maxEdgeSize + maxEdgePtrSize);
1.103 + SkEdge* edge = reinterpret_cast<SkEdge*>(storage);
1.104 + SkEdge** edgePtr = reinterpret_cast<SkEdge**>(storage + maxEdgeSize);
1.105 + // Record the beginning of our pointers, so we can return them to the caller
1.106 + fEdgeList = edgePtr;
1.107 +
1.108 + if (iclip) {
1.109 + SkRect clip;
1.110 + setShiftedClip(&clip, *iclip, shiftUp);
1.111 +
1.112 + while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
1.113 + switch (verb) {
1.114 + case SkPath::kMove_Verb:
1.115 + case SkPath::kClose_Verb:
1.116 + // we ignore these, and just get the whole segment from
1.117 + // the corresponding line/quad/cubic verbs
1.118 + break;
1.119 + case SkPath::kLine_Verb: {
1.120 + SkPoint lines[SkLineClipper::kMaxPoints];
1.121 + int lineCount = SkLineClipper::ClipLine(pts, clip, lines);
1.122 + SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments);
1.123 + for (int i = 0; i < lineCount; i++) {
1.124 + if (edge->setLine(lines[i], lines[i + 1], shiftUp)) {
1.125 + *edgePtr++ = edge++;
1.126 + }
1.127 + }
1.128 + break;
1.129 + }
1.130 + default:
1.131 + SkDEBUGFAIL("unexpected verb");
1.132 + break;
1.133 + }
1.134 + }
1.135 + } else {
1.136 + while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
1.137 + switch (verb) {
1.138 + case SkPath::kMove_Verb:
1.139 + case SkPath::kClose_Verb:
1.140 + // we ignore these, and just get the whole segment from
1.141 + // the corresponding line/quad/cubic verbs
1.142 + break;
1.143 + case SkPath::kLine_Verb:
1.144 + if (edge->setLine(pts[0], pts[1], shiftUp)) {
1.145 + *edgePtr++ = edge++;
1.146 + }
1.147 + break;
1.148 + default:
1.149 + SkDEBUGFAIL("unexpected verb");
1.150 + break;
1.151 + }
1.152 + }
1.153 + }
1.154 + SkASSERT((char*)edge <= (char*)fEdgeList);
1.155 + SkASSERT(edgePtr - fEdgeList <= maxEdgeCount);
1.156 + return SkToInt(edgePtr - fEdgeList);
1.157 +}
1.158 +
1.159 +static void handle_quad(SkEdgeBuilder* builder, const SkPoint pts[3]) {
1.160 + SkPoint monoX[5];
1.161 + int n = SkChopQuadAtYExtrema(pts, monoX);
1.162 + for (int i = 0; i <= n; i++) {
1.163 + builder->addQuad(&monoX[i * 2]);
1.164 + }
1.165 +}
1.166 +
1.167 +int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip,
1.168 + int shiftUp) {
1.169 + fAlloc.reset();
1.170 + fList.reset();
1.171 + fShiftUp = shiftUp;
1.172 +
1.173 + SkScalar conicTol = SK_ScalarHalf * (1 << shiftUp);
1.174 +
1.175 + if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) {
1.176 + return this->buildPoly(path, iclip, shiftUp);
1.177 + }
1.178 +
1.179 + SkPath::Iter iter(path, true);
1.180 + SkPoint pts[4];
1.181 + SkPath::Verb verb;
1.182 +
1.183 + if (iclip) {
1.184 + SkRect clip;
1.185 + setShiftedClip(&clip, *iclip, shiftUp);
1.186 + SkEdgeClipper clipper;
1.187 +
1.188 + while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
1.189 + switch (verb) {
1.190 + case SkPath::kMove_Verb:
1.191 + case SkPath::kClose_Verb:
1.192 + // we ignore these, and just get the whole segment from
1.193 + // the corresponding line/quad/cubic verbs
1.194 + break;
1.195 + case SkPath::kLine_Verb: {
1.196 + SkPoint lines[SkLineClipper::kMaxPoints];
1.197 + int lineCount = SkLineClipper::ClipLine(pts, clip, lines);
1.198 + for (int i = 0; i < lineCount; i++) {
1.199 + this->addLine(&lines[i]);
1.200 + }
1.201 + break;
1.202 + }
1.203 + case SkPath::kQuad_Verb:
1.204 + if (clipper.clipQuad(pts, clip)) {
1.205 + this->addClipper(&clipper);
1.206 + }
1.207 + break;
1.208 + case SkPath::kConic_Verb: {
1.209 + const int MAX_POW2 = 4;
1.210 + const int MAX_QUADS = 1 << MAX_POW2;
1.211 + const int MAX_QUAD_PTS = 1 + 2 * MAX_QUADS;
1.212 + SkPoint storage[MAX_QUAD_PTS];
1.213 +
1.214 + SkConic conic;
1.215 + conic.set(pts, iter.conicWeight());
1.216 + int pow2 = conic.computeQuadPOW2(conicTol);
1.217 + pow2 = SkMin32(pow2, MAX_POW2);
1.218 + int quadCount = conic.chopIntoQuadsPOW2(storage, pow2);
1.219 + SkASSERT(quadCount <= MAX_QUADS);
1.220 + for (int i = 0; i < quadCount; ++i) {
1.221 + if (clipper.clipQuad(&storage[i * 2], clip)) {
1.222 + this->addClipper(&clipper);
1.223 + }
1.224 + }
1.225 + } break;
1.226 + case SkPath::kCubic_Verb:
1.227 + if (clipper.clipCubic(pts, clip)) {
1.228 + this->addClipper(&clipper);
1.229 + }
1.230 + break;
1.231 + default:
1.232 + SkDEBUGFAIL("unexpected verb");
1.233 + break;
1.234 + }
1.235 + }
1.236 + } else {
1.237 + while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
1.238 + switch (verb) {
1.239 + case SkPath::kMove_Verb:
1.240 + case SkPath::kClose_Verb:
1.241 + // we ignore these, and just get the whole segment from
1.242 + // the corresponding line/quad/cubic verbs
1.243 + break;
1.244 + case SkPath::kLine_Verb:
1.245 + this->addLine(pts);
1.246 + break;
1.247 + case SkPath::kQuad_Verb: {
1.248 + handle_quad(this, pts);
1.249 + break;
1.250 + }
1.251 + case SkPath::kConic_Verb: {
1.252 + const int MAX_POW2 = 4;
1.253 + const int MAX_QUADS = 1 << MAX_POW2;
1.254 + const int MAX_QUAD_PTS = 1 + 2 * MAX_QUADS;
1.255 + SkPoint storage[MAX_QUAD_PTS];
1.256 +
1.257 + SkConic conic;
1.258 + conic.set(pts, iter.conicWeight());
1.259 + int pow2 = conic.computeQuadPOW2(conicTol);
1.260 + pow2 = SkMin32(pow2, MAX_POW2);
1.261 + int quadCount = conic.chopIntoQuadsPOW2(storage, pow2);
1.262 + SkASSERT(quadCount <= MAX_QUADS);
1.263 + for (int i = 0; i < quadCount; ++i) {
1.264 + handle_quad(this, &storage[i * 2]);
1.265 + }
1.266 + } break;
1.267 + case SkPath::kCubic_Verb: {
1.268 + SkPoint monoY[10];
1.269 + int n = SkChopCubicAtYExtrema(pts, monoY);
1.270 + for (int i = 0; i <= n; i++) {
1.271 + this->addCubic(&monoY[i * 3]);
1.272 + }
1.273 + break;
1.274 + }
1.275 + default:
1.276 + SkDEBUGFAIL("unexpected verb");
1.277 + break;
1.278 + }
1.279 + }
1.280 + }
1.281 + fEdgeList = fList.begin();
1.282 + return fList.count();
1.283 +}
