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
10static 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
18bool 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
47static 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
56SkCullPoints::SkCullPoints() {
57    SkIRect    r;
58    r.setEmpty();
59    this->reset(r);
60}
61
62SkCullPoints::SkCullPoints(const SkIRect& r) {
63    this->reset(r);
64}
65
66void SkCullPoints::reset(const SkIRect& r) {
67    fR = r;
68    toQuad(fR, fAsQuad);
69    fPrevPt.set(0, 0);
70    fPrevResult = kNo_Result;
71}
72
73void SkCullPoints::moveTo(int x, int y) {
74    fPrevPt.set(x, y);
75    fPrevResult = kNo_Result;   // so we trigger a movetolineto later
76}
77
78SkCullPoints::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
109SkCullPointsPath::SkCullPointsPath()
110    : fCP(), fPath(NULL) {
111}
112
113SkCullPointsPath::SkCullPointsPath(const SkIRect& r, SkPath* dst)
114    : fCP(r), fPath(dst) {
115}
116
117void SkCullPointsPath::reset(const SkIRect& r, SkPath* dst) {
118    fCP.reset(r);
119    fPath = dst;
120}
121
122void SkCullPointsPath::moveTo(int x, int y) {
123    fCP.moveTo(x, y);
124}
125
126void 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
146bool 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
206bool 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