michael@0: 
michael@0: /*
michael@0:  * Copyright 2011 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: #include "SkEdgeBuilder.h"
michael@0: #include "SkPath.h"
michael@0: #include "SkEdge.h"
michael@0: #include "SkEdgeClipper.h"
michael@0: #include "SkLineClipper.h"
michael@0: #include "SkGeometry.h"
michael@0: 
michael@0: template <typename T> static T* typedAllocThrow(SkChunkAlloc& alloc) {
michael@0:     return static_cast<T*>(alloc.allocThrow(sizeof(T)));
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: SkEdgeBuilder::SkEdgeBuilder() : fAlloc(16*1024) {
michael@0:     fEdgeList = NULL;
michael@0: }
michael@0: 
michael@0: void SkEdgeBuilder::addLine(const SkPoint pts[]) {
michael@0:     SkEdge* edge = typedAllocThrow<SkEdge>(fAlloc);
michael@0:     if (edge->setLine(pts[0], pts[1], fShiftUp)) {
michael@0:         fList.push(edge);
michael@0:     } else {
michael@0:         // TODO: unallocate edge from storage...
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkEdgeBuilder::addQuad(const SkPoint pts[]) {
michael@0:     SkQuadraticEdge* edge = typedAllocThrow<SkQuadraticEdge>(fAlloc);
michael@0:     if (edge->setQuadratic(pts, fShiftUp)) {
michael@0:         fList.push(edge);
michael@0:     } else {
michael@0:         // TODO: unallocate edge from storage...
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkEdgeBuilder::addCubic(const SkPoint pts[]) {
michael@0:     SkCubicEdge* edge = typedAllocThrow<SkCubicEdge>(fAlloc);
michael@0:     if (edge->setCubic(pts, NULL, fShiftUp)) {
michael@0:         fList.push(edge);
michael@0:     } else {
michael@0:         // TODO: unallocate edge from storage...
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkEdgeBuilder::addClipper(SkEdgeClipper* clipper) {
michael@0:     SkPoint      pts[4];
michael@0:     SkPath::Verb verb;
michael@0: 
michael@0:     while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) {
michael@0:         switch (verb) {
michael@0:             case SkPath::kLine_Verb:
michael@0:                 this->addLine(pts);
michael@0:                 break;
michael@0:             case SkPath::kQuad_Verb:
michael@0:                 this->addQuad(pts);
michael@0:                 break;
michael@0:             case SkPath::kCubic_Verb:
michael@0:                 this->addCubic(pts);
michael@0:                 break;
michael@0:             default:
michael@0:                 break;
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: static void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) {
michael@0:     dst->set(SkIntToScalar(src.fLeft >> shift),
michael@0:              SkIntToScalar(src.fTop >> shift),
michael@0:              SkIntToScalar(src.fRight >> shift),
michael@0:              SkIntToScalar(src.fBottom >> shift));
michael@0: }
michael@0: 
michael@0: int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip,
michael@0:                              int shiftUp) {
michael@0:     SkPath::Iter    iter(path, true);
michael@0:     SkPoint         pts[4];
michael@0:     SkPath::Verb    verb;
michael@0: 
michael@0:     int maxEdgeCount = path.countPoints();
michael@0:     if (iclip) {
michael@0:         // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since
michael@0:         // we turn portions that are clipped out on the left/right into vertical
michael@0:         // segments.
michael@0:         maxEdgeCount *= SkLineClipper::kMaxClippedLineSegments;
michael@0:     }
michael@0:     size_t maxEdgeSize = maxEdgeCount * sizeof(SkEdge);
michael@0:     size_t maxEdgePtrSize = maxEdgeCount * sizeof(SkEdge*);
michael@0: 
michael@0:     // lets store the edges and their pointers in the same block
michael@0:     char* storage = (char*)fAlloc.allocThrow(maxEdgeSize + maxEdgePtrSize);
michael@0:     SkEdge* edge = reinterpret_cast<SkEdge*>(storage);
michael@0:     SkEdge** edgePtr = reinterpret_cast<SkEdge**>(storage + maxEdgeSize);
michael@0:     // Record the beginning of our pointers, so we can return them to the caller
michael@0:     fEdgeList = edgePtr;
michael@0: 
michael@0:     if (iclip) {
michael@0:         SkRect clip;
michael@0:         setShiftedClip(&clip, *iclip, shiftUp);
michael@0: 
michael@0:         while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
michael@0:             switch (verb) {
michael@0:                 case SkPath::kMove_Verb:
michael@0:                 case SkPath::kClose_Verb:
michael@0:                     // we ignore these, and just get the whole segment from
michael@0:                     // the corresponding line/quad/cubic verbs
michael@0:                     break;
michael@0:                 case SkPath::kLine_Verb: {
michael@0:                     SkPoint lines[SkLineClipper::kMaxPoints];
michael@0:                     int lineCount = SkLineClipper::ClipLine(pts, clip, lines);
michael@0:                     SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments);
michael@0:                     for (int i = 0; i < lineCount; i++) {
michael@0:                         if (edge->setLine(lines[i], lines[i + 1], shiftUp)) {
michael@0:                             *edgePtr++ = edge++;
michael@0:                         }
michael@0:                     }
michael@0:                     break;
michael@0:                 }
michael@0:                 default:
michael@0:                     SkDEBUGFAIL("unexpected verb");
michael@0:                     break;
michael@0:             }
michael@0:         }
michael@0:     } else {
michael@0:         while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
michael@0:             switch (verb) {
michael@0:                 case SkPath::kMove_Verb:
michael@0:                 case SkPath::kClose_Verb:
michael@0:                     // we ignore these, and just get the whole segment from
michael@0:                     // the corresponding line/quad/cubic verbs
michael@0:                     break;
michael@0:                 case SkPath::kLine_Verb:
michael@0:                     if (edge->setLine(pts[0], pts[1], shiftUp)) {
michael@0:                         *edgePtr++ = edge++;
michael@0:                     }
michael@0:                     break;
michael@0:                 default:
michael@0:                     SkDEBUGFAIL("unexpected verb");
michael@0:                     break;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     SkASSERT((char*)edge <= (char*)fEdgeList);
michael@0:     SkASSERT(edgePtr - fEdgeList <= maxEdgeCount);
michael@0:     return SkToInt(edgePtr - fEdgeList);
michael@0: }
michael@0: 
michael@0: static void handle_quad(SkEdgeBuilder* builder, const SkPoint pts[3]) {
michael@0:     SkPoint monoX[5];
michael@0:     int n = SkChopQuadAtYExtrema(pts, monoX);
michael@0:     for (int i = 0; i <= n; i++) {
michael@0:         builder->addQuad(&monoX[i * 2]);
michael@0:     }
michael@0: }
michael@0: 
michael@0: int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip,
michael@0:                          int shiftUp) {
michael@0:     fAlloc.reset();
michael@0:     fList.reset();
michael@0:     fShiftUp = shiftUp;
michael@0: 
michael@0:     SkScalar conicTol = SK_ScalarHalf * (1 << shiftUp);
michael@0: 
michael@0:     if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) {
michael@0:         return this->buildPoly(path, iclip, shiftUp);
michael@0:     }
michael@0: 
michael@0:     SkPath::Iter    iter(path, true);
michael@0:     SkPoint         pts[4];
michael@0:     SkPath::Verb    verb;
michael@0: 
michael@0:     if (iclip) {
michael@0:         SkRect clip;
michael@0:         setShiftedClip(&clip, *iclip, shiftUp);
michael@0:         SkEdgeClipper clipper;
michael@0: 
michael@0:         while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
michael@0:             switch (verb) {
michael@0:                 case SkPath::kMove_Verb:
michael@0:                 case SkPath::kClose_Verb:
michael@0:                     // we ignore these, and just get the whole segment from
michael@0:                     // the corresponding line/quad/cubic verbs
michael@0:                     break;
michael@0:                 case SkPath::kLine_Verb: {
michael@0:                     SkPoint lines[SkLineClipper::kMaxPoints];
michael@0:                     int lineCount = SkLineClipper::ClipLine(pts, clip, lines);
michael@0:                     for (int i = 0; i < lineCount; i++) {
michael@0:                         this->addLine(&lines[i]);
michael@0:                     }
michael@0:                     break;
michael@0:                 }
michael@0:                 case SkPath::kQuad_Verb:
michael@0:                     if (clipper.clipQuad(pts, clip)) {
michael@0:                         this->addClipper(&clipper);
michael@0:                     }
michael@0:                     break;
michael@0:                 case SkPath::kConic_Verb: {
michael@0:                     const int MAX_POW2 = 4;
michael@0:                     const int MAX_QUADS = 1 << MAX_POW2;
michael@0:                     const int MAX_QUAD_PTS = 1 + 2 * MAX_QUADS;
michael@0:                     SkPoint storage[MAX_QUAD_PTS];
michael@0: 
michael@0:                     SkConic conic;
michael@0:                     conic.set(pts, iter.conicWeight());
michael@0:                     int pow2 = conic.computeQuadPOW2(conicTol);
michael@0:                     pow2 = SkMin32(pow2, MAX_POW2);
michael@0:                     int quadCount = conic.chopIntoQuadsPOW2(storage, pow2);
michael@0:                     SkASSERT(quadCount <= MAX_QUADS);
michael@0:                     for (int i = 0; i < quadCount; ++i) {
michael@0:                         if (clipper.clipQuad(&storage[i * 2], clip)) {
michael@0:                             this->addClipper(&clipper);
michael@0:                         }
michael@0:                     }
michael@0:                 } break;
michael@0:                 case SkPath::kCubic_Verb:
michael@0:                     if (clipper.clipCubic(pts, clip)) {
michael@0:                         this->addClipper(&clipper);
michael@0:                     }
michael@0:                     break;
michael@0:                 default:
michael@0:                     SkDEBUGFAIL("unexpected verb");
michael@0:                     break;
michael@0:             }
michael@0:         }
michael@0:     } else {
michael@0:         while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
michael@0:             switch (verb) {
michael@0:                 case SkPath::kMove_Verb:
michael@0:                 case SkPath::kClose_Verb:
michael@0:                     // we ignore these, and just get the whole segment from
michael@0:                     // the corresponding line/quad/cubic verbs
michael@0:                     break;
michael@0:                 case SkPath::kLine_Verb:
michael@0:                     this->addLine(pts);
michael@0:                     break;
michael@0:                 case SkPath::kQuad_Verb: {
michael@0:                     handle_quad(this, pts);
michael@0:                     break;
michael@0:                 }
michael@0:                 case SkPath::kConic_Verb: {
michael@0:                     const int MAX_POW2 = 4;
michael@0:                     const int MAX_QUADS = 1 << MAX_POW2;
michael@0:                     const int MAX_QUAD_PTS = 1 + 2 * MAX_QUADS;
michael@0:                     SkPoint storage[MAX_QUAD_PTS];
michael@0: 
michael@0:                     SkConic conic;
michael@0:                     conic.set(pts, iter.conicWeight());
michael@0:                     int pow2 = conic.computeQuadPOW2(conicTol);
michael@0:                     pow2 = SkMin32(pow2, MAX_POW2);
michael@0:                     int quadCount = conic.chopIntoQuadsPOW2(storage, pow2);
michael@0:                     SkASSERT(quadCount <= MAX_QUADS);
michael@0:                     for (int i = 0; i < quadCount; ++i) {
michael@0:                         handle_quad(this, &storage[i * 2]);
michael@0:                     }
michael@0:                 } break;
michael@0:                 case SkPath::kCubic_Verb: {
michael@0:                     SkPoint monoY[10];
michael@0:                     int n = SkChopCubicAtYExtrema(pts, monoY);
michael@0:                     for (int i = 0; i <= n; i++) {
michael@0:                         this->addCubic(&monoY[i * 3]);
michael@0:                     }
michael@0:                     break;
michael@0:                 }
michael@0:                 default:
michael@0:                     SkDEBUGFAIL("unexpected verb");
michael@0:                     break;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     fEdgeList = fList.begin();
michael@0:     return fList.count();
michael@0: }