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