Home | History | Annotate | Download | only in utils 
      1 /*
      2  * Copyright 2006 The Android Open Source Project
      3  *
      4  * Use of this source code is governed by a BSD-style license that can be
      5  * found in the LICENSE file.
      6  */
      7 
      8 #include "SkCullPoints.h"
      9 
     10 static bool cross_product_is_neg(const SkIPoint& v, int dx, int dy) {
     11 #if 0
     12     return v.fX * dy - v.fY * dx < 0;
     13 #else
     14     return sk_64_mul(v.fX, dy) < sk_64_mul(dx, v.fY);
     15 #endif
     16 }
     17 
     18 bool SkCullPoints::sect_test(int x0, int y0, int x1, int y1) const {
     19     const SkIRect& r = fR;
     20 
     21     if ((x0 < r.fLeft    && x1 < r.fLeft) ||
     22         (x0 > r.fRight   && x1 > r.fRight) ||
     23         (y0 < r.fTop     && y1 < r.fTop) ||
     24         (y0 > r.fBottom  && y1 > r.fBottom)) {
     25         return false;
     26     }
     27 
     28     // since the crossprod test is a little expensive, check for easy-in cases first
     29     if (r.contains(x0, y0) || r.contains(x1, y1)) {
     30         return true;
     31     }
     32 
     33     // At this point we're not sure, so we do a crossprod test
     34     SkIPoint           vec;
     35     const SkIPoint*    rAsQuad = fAsQuad;
     36 
     37     vec.set(x1 - x0, y1 - y0);
     38     bool isNeg = cross_product_is_neg(vec, x0 - rAsQuad[0].fX, y0 - rAsQuad[0].fY);
     39     for (int i = 1; i < 4; i++) {
     40         if (cross_product_is_neg(vec, x0 - rAsQuad[i].fX, y0 - rAsQuad[i].fY) != isNeg) {
     41             return true;
     42         }
     43     }
     44     return false;   // we didn't intersect
     45 }
     46 
     47 static void toQuad(const SkIRect& r, SkIPoint quad[4]) {
     48     SkASSERT(quad);
     49 
     50     quad[0].set(r.fLeft, r.fTop);
     51     quad[1].set(r.fRight, r.fTop);
     52     quad[2].set(r.fRight, r.fBottom);
     53     quad[3].set(r.fLeft, r.fBottom);
     54 }
     55 
     56 SkCullPoints::SkCullPoints() {
     57     SkIRect    r;
     58     r.setEmpty();
     59     this->reset(r);
     60 }
     61 
     62 SkCullPoints::SkCullPoints(const SkIRect& r) {
     63     this->reset(r);
     64 }
     65 
     66 void SkCullPoints::reset(const SkIRect& r) {
     67     fR = r;
     68     toQuad(fR, fAsQuad);
     69     fPrevPt.set(0, 0);
     70     fPrevResult = kNo_Result;
     71 }
     72 
     73 void SkCullPoints::moveTo(int x, int y) {
     74     fPrevPt.set(x, y);
     75     fPrevResult = kNo_Result;   // so we trigger a movetolineto later
     76 }
     77 
     78 SkCullPoints::LineToResult SkCullPoints::lineTo(int x, int y, SkIPoint line[]) {
     79     SkASSERT(line != NULL);
     80 
     81     LineToResult result = kNo_Result;
     82     int x0 = fPrevPt.fX;
     83     int y0 = fPrevPt.fY;
     84 
     85     // need to upgrade sect_test to chop the result
     86     // and to correctly return kLineTo_Result when the result is connected
     87     // to the previous call-out
     88     if (this->sect_test(x0, y0, x, y)) {
     89         line[0].set(x0, y0);
     90         line[1].set(x, y);
     91 
     92         if (fPrevResult != kNo_Result && fPrevPt.equals(x0, y0)) {
     93             result = kLineTo_Result;
     94         } else {
     95             result = kMoveToLineTo_Result;
     96         }
     97     }
     98 
     99     fPrevPt.set(x, y);
    100     fPrevResult = result;
    101 
    102     return result;
    103 }
    104 
    105 /////////////////////////////////////////////////////////////////////////////////////////////////
    106 
    107 #include "SkPath.h"
    108 
    109 SkCullPointsPath::SkCullPointsPath()
    110     : fCP(), fPath(NULL) {
    111 }
    112 
    113 SkCullPointsPath::SkCullPointsPath(const SkIRect& r, SkPath* dst)
    114     : fCP(r), fPath(dst) {
    115 }
    116 
    117 void SkCullPointsPath::reset(const SkIRect& r, SkPath* dst) {
    118     fCP.reset(r);
    119     fPath = dst;
    120 }
    121 
    122 void SkCullPointsPath::moveTo(int x, int y) {
    123     fCP.moveTo(x, y);
    124 }
    125 
    126 void SkCullPointsPath::lineTo(int x, int y) {
    127     SkIPoint   pts[2];
    128 
    129     switch (fCP.lineTo(x, y, pts)) {
    130     case SkCullPoints::kMoveToLineTo_Result:
    131         fPath->moveTo(SkIntToScalar(pts[0].fX), SkIntToScalar(pts[0].fY));
    132         // fall through to the lineto case
    133     case SkCullPoints::kLineTo_Result:
    134         fPath->lineTo(SkIntToScalar(pts[1].fX), SkIntToScalar(pts[1].fY));
    135         break;
    136     default:
    137         break;
    138     }
    139 }
    140 
    141 ///////////////////////////////////////////////////////////////////////////////
    142 
    143 #include "SkMatrix.h"
    144 #include "SkRegion.h"
    145 
    146 bool SkHitTestPath(const SkPath& path, SkRect& target, bool hires) {
    147     if (target.isEmpty()) {
    148         return false;
    149     }
    150 
    151     bool isInverse = path.isInverseFillType();
    152     if (path.isEmpty()) {
    153         return isInverse;
    154     }
    155 
    156     SkRect bounds = path.getBounds();
    157 
    158     bool sects = SkRect::Intersects(target, bounds);
    159     if (isInverse) {
    160         if (!sects) {
    161             return true;
    162         }
    163     } else {
    164         if (!sects) {
    165             return false;
    166         }
    167         if (target.contains(bounds)) {
    168             return true;
    169         }
    170     }
    171 
    172     SkPath devPath;
    173     const SkPath* pathPtr;
    174     SkRect        devTarget;
    175 
    176     if (hires) {
    177         const SkScalar coordLimit = SkIntToScalar(16384);
    178         const SkRect limit = { 0, 0, coordLimit, coordLimit };
    179 
    180         SkMatrix matrix;
    181         matrix.setRectToRect(bounds, limit, SkMatrix::kFill_ScaleToFit);
    182 
    183         path.transform(matrix, &devPath);
    184         matrix.mapRect(&devTarget, target);
    185 
    186         pathPtr = &devPath;
    187     } else {
    188         devTarget = target;
    189         pathPtr = &path;
    190     }
    191 
    192     SkIRect iTarget;
    193     devTarget.round(&iTarget);
    194     if (iTarget.isEmpty()) {
    195         iTarget.fLeft = SkScalarFloorToInt(devTarget.fLeft);
    196         iTarget.fTop = SkScalarFloorToInt(devTarget.fTop);
    197         iTarget.fRight = iTarget.fLeft + 1;
    198         iTarget.fBottom = iTarget.fTop + 1;
    199     }
    200 
    201     SkRegion clip(iTarget);
    202     SkRegion rgn;
    203     return rgn.setPath(*pathPtr, clip) ^ isInverse;
    204 }
    205 
    206 bool SkHitTestPath(const SkPath& path, SkScalar x, SkScalar y, bool hires) {
    207     const SkScalar half = SK_ScalarHalf;
    208     const SkScalar one = SK_Scalar1;
    209     SkRect r = SkRect::MakeXYWH(x - half, y - half, one, one);
    210     return SkHitTestPath(path, r, hires);
    211 }
    212