michael@0: /*
michael@0:  * Copyright 2006 The Android Open Source Project
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: 
michael@0: #include "SkCullPoints.h"
michael@0: 
michael@0: static bool cross_product_is_neg(const SkIPoint& v, int dx, int dy) {
michael@0: #if 0
michael@0:     return v.fX * dy - v.fY * dx < 0;
michael@0: #else
michael@0:     return sk_64_mul(v.fX, dy) < sk_64_mul(dx, v.fY);
michael@0: #endif
michael@0: }
michael@0: 
michael@0: bool SkCullPoints::sect_test(int x0, int y0, int x1, int y1) const {
michael@0:     const SkIRect& r = fR;
michael@0: 
michael@0:     if ((x0 < r.fLeft    && x1 < r.fLeft) ||
michael@0:         (x0 > r.fRight   && x1 > r.fRight) ||
michael@0:         (y0 < r.fTop     && y1 < r.fTop) ||
michael@0:         (y0 > r.fBottom  && y1 > r.fBottom)) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     // since the crossprod test is a little expensive, check for easy-in cases first
michael@0:     if (r.contains(x0, y0) || r.contains(x1, y1)) {
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     // At this point we're not sure, so we do a crossprod test
michael@0:     SkIPoint           vec;
michael@0:     const SkIPoint*    rAsQuad = fAsQuad;
michael@0: 
michael@0:     vec.set(x1 - x0, y1 - y0);
michael@0:     bool isNeg = cross_product_is_neg(vec, x0 - rAsQuad[0].fX, y0 - rAsQuad[0].fY);
michael@0:     for (int i = 1; i < 4; i++) {
michael@0:         if (cross_product_is_neg(vec, x0 - rAsQuad[i].fX, y0 - rAsQuad[i].fY) != isNeg) {
michael@0:             return true;
michael@0:         }
michael@0:     }
michael@0:     return false;   // we didn't intersect
michael@0: }
michael@0: 
michael@0: static void toQuad(const SkIRect& r, SkIPoint quad[4]) {
michael@0:     SkASSERT(quad);
michael@0: 
michael@0:     quad[0].set(r.fLeft, r.fTop);
michael@0:     quad[1].set(r.fRight, r.fTop);
michael@0:     quad[2].set(r.fRight, r.fBottom);
michael@0:     quad[3].set(r.fLeft, r.fBottom);
michael@0: }
michael@0: 
michael@0: SkCullPoints::SkCullPoints() {
michael@0:     SkIRect    r;
michael@0:     r.setEmpty();
michael@0:     this->reset(r);
michael@0: }
michael@0: 
michael@0: SkCullPoints::SkCullPoints(const SkIRect& r) {
michael@0:     this->reset(r);
michael@0: }
michael@0: 
michael@0: void SkCullPoints::reset(const SkIRect& r) {
michael@0:     fR = r;
michael@0:     toQuad(fR, fAsQuad);
michael@0:     fPrevPt.set(0, 0);
michael@0:     fPrevResult = kNo_Result;
michael@0: }
michael@0: 
michael@0: void SkCullPoints::moveTo(int x, int y) {
michael@0:     fPrevPt.set(x, y);
michael@0:     fPrevResult = kNo_Result;   // so we trigger a movetolineto later
michael@0: }
michael@0: 
michael@0: SkCullPoints::LineToResult SkCullPoints::lineTo(int x, int y, SkIPoint line[]) {
michael@0:     SkASSERT(line != NULL);
michael@0: 
michael@0:     LineToResult result = kNo_Result;
michael@0:     int x0 = fPrevPt.fX;
michael@0:     int y0 = fPrevPt.fY;
michael@0: 
michael@0:     // need to upgrade sect_test to chop the result
michael@0:     // and to correctly return kLineTo_Result when the result is connected
michael@0:     // to the previous call-out
michael@0:     if (this->sect_test(x0, y0, x, y)) {
michael@0:         line[0].set(x0, y0);
michael@0:         line[1].set(x, y);
michael@0: 
michael@0:         if (fPrevResult != kNo_Result && fPrevPt.equals(x0, y0)) {
michael@0:             result = kLineTo_Result;
michael@0:         } else {
michael@0:             result = kMoveToLineTo_Result;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     fPrevPt.set(x, y);
michael@0:     fPrevResult = result;
michael@0: 
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: /////////////////////////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: #include "SkPath.h"
michael@0: 
michael@0: SkCullPointsPath::SkCullPointsPath()
michael@0:     : fCP(), fPath(NULL) {
michael@0: }
michael@0: 
michael@0: SkCullPointsPath::SkCullPointsPath(const SkIRect& r, SkPath* dst)
michael@0:     : fCP(r), fPath(dst) {
michael@0: }
michael@0: 
michael@0: void SkCullPointsPath::reset(const SkIRect& r, SkPath* dst) {
michael@0:     fCP.reset(r);
michael@0:     fPath = dst;
michael@0: }
michael@0: 
michael@0: void SkCullPointsPath::moveTo(int x, int y) {
michael@0:     fCP.moveTo(x, y);
michael@0: }
michael@0: 
michael@0: void SkCullPointsPath::lineTo(int x, int y) {
michael@0:     SkIPoint   pts[2];
michael@0: 
michael@0:     switch (fCP.lineTo(x, y, pts)) {
michael@0:     case SkCullPoints::kMoveToLineTo_Result:
michael@0:         fPath->moveTo(SkIntToScalar(pts[0].fX), SkIntToScalar(pts[0].fY));
michael@0:         // fall through to the lineto case
michael@0:     case SkCullPoints::kLineTo_Result:
michael@0:         fPath->lineTo(SkIntToScalar(pts[1].fX), SkIntToScalar(pts[1].fY));
michael@0:         break;
michael@0:     default:
michael@0:         break;
michael@0:     }
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: #include "SkMatrix.h"
michael@0: #include "SkRegion.h"
michael@0: 
michael@0: bool SkHitTestPath(const SkPath& path, SkRect& target, bool hires) {
michael@0:     if (target.isEmpty()) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     bool isInverse = path.isInverseFillType();
michael@0:     if (path.isEmpty()) {
michael@0:         return isInverse;
michael@0:     }
michael@0: 
michael@0:     SkRect bounds = path.getBounds();
michael@0: 
michael@0:     bool sects = SkRect::Intersects(target, bounds);
michael@0:     if (isInverse) {
michael@0:         if (!sects) {
michael@0:             return true;
michael@0:         }
michael@0:     } else {
michael@0:         if (!sects) {
michael@0:             return false;
michael@0:         }
michael@0:         if (target.contains(bounds)) {
michael@0:             return true;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     SkPath devPath;
michael@0:     const SkPath* pathPtr;
michael@0:     SkRect        devTarget;
michael@0: 
michael@0:     if (hires) {
michael@0:         const SkScalar coordLimit = SkIntToScalar(16384);
michael@0:         const SkRect limit = { 0, 0, coordLimit, coordLimit };
michael@0: 
michael@0:         SkMatrix matrix;
michael@0:         matrix.setRectToRect(bounds, limit, SkMatrix::kFill_ScaleToFit);
michael@0: 
michael@0:         path.transform(matrix, &devPath);
michael@0:         matrix.mapRect(&devTarget, target);
michael@0: 
michael@0:         pathPtr = &devPath;
michael@0:     } else {
michael@0:         devTarget = target;
michael@0:         pathPtr = &path;
michael@0:     }
michael@0: 
michael@0:     SkIRect iTarget;
michael@0:     devTarget.round(&iTarget);
michael@0:     if (iTarget.isEmpty()) {
michael@0:         iTarget.fLeft = SkScalarFloorToInt(devTarget.fLeft);
michael@0:         iTarget.fTop = SkScalarFloorToInt(devTarget.fTop);
michael@0:         iTarget.fRight = iTarget.fLeft + 1;
michael@0:         iTarget.fBottom = iTarget.fTop + 1;
michael@0:     }
michael@0: 
michael@0:     SkRegion clip(iTarget);
michael@0:     SkRegion rgn;
michael@0:     return rgn.setPath(*pathPtr, clip) ^ isInverse;
michael@0: }
michael@0: 
michael@0: bool SkHitTestPath(const SkPath& path, SkScalar x, SkScalar y, bool hires) {
michael@0:     const SkScalar half = SK_ScalarHalf;
michael@0:     const SkScalar one = SK_Scalar1;
michael@0:     SkRect r = SkRect::MakeXYWH(x - half, y - half, one, one);
michael@0:     return SkHitTestPath(path, r, hires);
michael@0: }