Home | History | Annotate | Download | only in core
      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