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
cross_product_is_neg(const SkIPoint & v,int dx,int dy)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
sect_test(int x0,int y0,int x1,int y1) const26 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
toQuad(const SkIRect & r,SkIPoint quad[4])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
SkCullPoints()64 SkCullPoints::SkCullPoints() {
65 SkIRect r;
66 r.setEmpty();
67 this->reset(r);
68 }
69
SkCullPoints(const SkIRect & r)70 SkCullPoints::SkCullPoints(const SkIRect& r) {
71 this->reset(r);
72 }
73
reset(const SkIRect & r)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
moveTo(int x,int y)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
lineTo(int x,int y,SkIPoint line[])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
SkCullPointsPath()117 SkCullPointsPath::SkCullPointsPath()
118 : fCP(), fPath(NULL) {
119 }
120
SkCullPointsPath(const SkIRect & r,SkPath * dst)121 SkCullPointsPath::SkCullPointsPath(const SkIRect& r, SkPath* dst)
122 : fCP(r), fPath(dst) {
123 }
124
reset(const SkIRect & r,SkPath * dst)125 void SkCullPointsPath::reset(const SkIRect& r, SkPath* dst) {
126 fCP.reset(r);
127 fPath = dst;
128 }
129
moveTo(int x,int y)130 void SkCullPointsPath::moveTo(int x, int y) {
131 fCP.moveTo(x, y);
132 }
133
lineTo(int x,int y)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