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
13static 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
26bool 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
55static 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
64SkCullPoints::SkCullPoints() {
65    SkIRect    r;
66    r.setEmpty();
67    this->reset(r);
68}
69
70SkCullPoints::SkCullPoints(const SkIRect& r) {
71    this->reset(r);
72}
73
74void SkCullPoints::reset(const SkIRect& r) {
75    fR = r;
76    toQuad(fR, fAsQuad);
77    fPrevPt.set(0, 0);
78    fPrevResult = kNo_Result;
79}
80
81void SkCullPoints::moveTo(int x, int y) {
82    fPrevPt.set(x, y);
83    fPrevResult = kNo_Result;   // so we trigger a movetolineto later
84}
85
86SkCullPoints::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
117SkCullPointsPath::SkCullPointsPath()
118    : fCP(), fPath(NULL) {
119}
120
121SkCullPointsPath::SkCullPointsPath(const SkIRect& r, SkPath* dst)
122    : fCP(r), fPath(dst) {
123}
124
125void SkCullPointsPath::reset(const SkIRect& r, SkPath* dst) {
126    fCP.reset(r);
127    fPath = dst;
128}
129
130void SkCullPointsPath::moveTo(int x, int y) {
131    fCP.moveTo(x, y);
132}
133
134void 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
154bool 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
214bool 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