1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/utils/SkCullPoints.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,211 @@
1.4 +/*
1.5 + * Copyright 2006 The Android Open Source Project
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +
1.11 +#include "SkCullPoints.h"
1.12 +
1.13 +static bool cross_product_is_neg(const SkIPoint& v, int dx, int dy) {
1.14 +#if 0
1.15 + return v.fX * dy - v.fY * dx < 0;
1.16 +#else
1.17 + return sk_64_mul(v.fX, dy) < sk_64_mul(dx, v.fY);
1.18 +#endif
1.19 +}
1.20 +
1.21 +bool SkCullPoints::sect_test(int x0, int y0, int x1, int y1) const {
1.22 + const SkIRect& r = fR;
1.23 +
1.24 + if ((x0 < r.fLeft && x1 < r.fLeft) ||
1.25 + (x0 > r.fRight && x1 > r.fRight) ||
1.26 + (y0 < r.fTop && y1 < r.fTop) ||
1.27 + (y0 > r.fBottom && y1 > r.fBottom)) {
1.28 + return false;
1.29 + }
1.30 +
1.31 + // since the crossprod test is a little expensive, check for easy-in cases first
1.32 + if (r.contains(x0, y0) || r.contains(x1, y1)) {
1.33 + return true;
1.34 + }
1.35 +
1.36 + // At this point we're not sure, so we do a crossprod test
1.37 + SkIPoint vec;
1.38 + const SkIPoint* rAsQuad = fAsQuad;
1.39 +
1.40 + vec.set(x1 - x0, y1 - y0);
1.41 + bool isNeg = cross_product_is_neg(vec, x0 - rAsQuad[0].fX, y0 - rAsQuad[0].fY);
1.42 + for (int i = 1; i < 4; i++) {
1.43 + if (cross_product_is_neg(vec, x0 - rAsQuad[i].fX, y0 - rAsQuad[i].fY) != isNeg) {
1.44 + return true;
1.45 + }
1.46 + }
1.47 + return false; // we didn't intersect
1.48 +}
1.49 +
1.50 +static void toQuad(const SkIRect& r, SkIPoint quad[4]) {
1.51 + SkASSERT(quad);
1.52 +
1.53 + quad[0].set(r.fLeft, r.fTop);
1.54 + quad[1].set(r.fRight, r.fTop);
1.55 + quad[2].set(r.fRight, r.fBottom);
1.56 + quad[3].set(r.fLeft, r.fBottom);
1.57 +}
1.58 +
1.59 +SkCullPoints::SkCullPoints() {
1.60 + SkIRect r;
1.61 + r.setEmpty();
1.62 + this->reset(r);
1.63 +}
1.64 +
1.65 +SkCullPoints::SkCullPoints(const SkIRect& r) {
1.66 + this->reset(r);
1.67 +}
1.68 +
1.69 +void SkCullPoints::reset(const SkIRect& r) {
1.70 + fR = r;
1.71 + toQuad(fR, fAsQuad);
1.72 + fPrevPt.set(0, 0);
1.73 + fPrevResult = kNo_Result;
1.74 +}
1.75 +
1.76 +void SkCullPoints::moveTo(int x, int y) {
1.77 + fPrevPt.set(x, y);
1.78 + fPrevResult = kNo_Result; // so we trigger a movetolineto later
1.79 +}
1.80 +
1.81 +SkCullPoints::LineToResult SkCullPoints::lineTo(int x, int y, SkIPoint line[]) {
1.82 + SkASSERT(line != NULL);
1.83 +
1.84 + LineToResult result = kNo_Result;
1.85 + int x0 = fPrevPt.fX;
1.86 + int y0 = fPrevPt.fY;
1.87 +
1.88 + // need to upgrade sect_test to chop the result
1.89 + // and to correctly return kLineTo_Result when the result is connected
1.90 + // to the previous call-out
1.91 + if (this->sect_test(x0, y0, x, y)) {
1.92 + line[0].set(x0, y0);
1.93 + line[1].set(x, y);
1.94 +
1.95 + if (fPrevResult != kNo_Result && fPrevPt.equals(x0, y0)) {
1.96 + result = kLineTo_Result;
1.97 + } else {
1.98 + result = kMoveToLineTo_Result;
1.99 + }
1.100 + }
1.101 +
1.102 + fPrevPt.set(x, y);
1.103 + fPrevResult = result;
1.104 +
1.105 + return result;
1.106 +}
1.107 +
1.108 +/////////////////////////////////////////////////////////////////////////////////////////////////
1.109 +
1.110 +#include "SkPath.h"
1.111 +
1.112 +SkCullPointsPath::SkCullPointsPath()
1.113 + : fCP(), fPath(NULL) {
1.114 +}
1.115 +
1.116 +SkCullPointsPath::SkCullPointsPath(const SkIRect& r, SkPath* dst)
1.117 + : fCP(r), fPath(dst) {
1.118 +}
1.119 +
1.120 +void SkCullPointsPath::reset(const SkIRect& r, SkPath* dst) {
1.121 + fCP.reset(r);
1.122 + fPath = dst;
1.123 +}
1.124 +
1.125 +void SkCullPointsPath::moveTo(int x, int y) {
1.126 + fCP.moveTo(x, y);
1.127 +}
1.128 +
1.129 +void SkCullPointsPath::lineTo(int x, int y) {
1.130 + SkIPoint pts[2];
1.131 +
1.132 + switch (fCP.lineTo(x, y, pts)) {
1.133 + case SkCullPoints::kMoveToLineTo_Result:
1.134 + fPath->moveTo(SkIntToScalar(pts[0].fX), SkIntToScalar(pts[0].fY));
1.135 + // fall through to the lineto case
1.136 + case SkCullPoints::kLineTo_Result:
1.137 + fPath->lineTo(SkIntToScalar(pts[1].fX), SkIntToScalar(pts[1].fY));
1.138 + break;
1.139 + default:
1.140 + break;
1.141 + }
1.142 +}
1.143 +
1.144 +///////////////////////////////////////////////////////////////////////////////
1.145 +
1.146 +#include "SkMatrix.h"
1.147 +#include "SkRegion.h"
1.148 +
1.149 +bool SkHitTestPath(const SkPath& path, SkRect& target, bool hires) {
1.150 + if (target.isEmpty()) {
1.151 + return false;
1.152 + }
1.153 +
1.154 + bool isInverse = path.isInverseFillType();
1.155 + if (path.isEmpty()) {
1.156 + return isInverse;
1.157 + }
1.158 +
1.159 + SkRect bounds = path.getBounds();
1.160 +
1.161 + bool sects = SkRect::Intersects(target, bounds);
1.162 + if (isInverse) {
1.163 + if (!sects) {
1.164 + return true;
1.165 + }
1.166 + } else {
1.167 + if (!sects) {
1.168 + return false;
1.169 + }
1.170 + if (target.contains(bounds)) {
1.171 + return true;
1.172 + }
1.173 + }
1.174 +
1.175 + SkPath devPath;
1.176 + const SkPath* pathPtr;
1.177 + SkRect devTarget;
1.178 +
1.179 + if (hires) {
1.180 + const SkScalar coordLimit = SkIntToScalar(16384);
1.181 + const SkRect limit = { 0, 0, coordLimit, coordLimit };
1.182 +
1.183 + SkMatrix matrix;
1.184 + matrix.setRectToRect(bounds, limit, SkMatrix::kFill_ScaleToFit);
1.185 +
1.186 + path.transform(matrix, &devPath);
1.187 + matrix.mapRect(&devTarget, target);
1.188 +
1.189 + pathPtr = &devPath;
1.190 + } else {
1.191 + devTarget = target;
1.192 + pathPtr = &path;
1.193 + }
1.194 +
1.195 + SkIRect iTarget;
1.196 + devTarget.round(&iTarget);
1.197 + if (iTarget.isEmpty()) {
1.198 + iTarget.fLeft = SkScalarFloorToInt(devTarget.fLeft);
1.199 + iTarget.fTop = SkScalarFloorToInt(devTarget.fTop);
1.200 + iTarget.fRight = iTarget.fLeft + 1;
1.201 + iTarget.fBottom = iTarget.fTop + 1;
1.202 + }
1.203 +
1.204 + SkRegion clip(iTarget);
1.205 + SkRegion rgn;
1.206 + return rgn.setPath(*pathPtr, clip) ^ isInverse;
1.207 +}
1.208 +
1.209 +bool SkHitTestPath(const SkPath& path, SkScalar x, SkScalar y, bool hires) {
1.210 + const SkScalar half = SK_ScalarHalf;
1.211 + const SkScalar one = SK_Scalar1;
1.212 + SkRect r = SkRect::MakeXYWH(x - half, y - half, one, one);
1.213 + return SkHitTestPath(path, r, hires);
1.214 +}
