1 /* libs/graphics/effects/SkCullPoints.cpp
2 **
3 ** Copyright 2006, The Android Open Source Project
4 **
5 ** Licensed under the Apache License, Version 2.0 (the "License");
6 ** you may not use this file except in compliance with the License.
7 ** You may obtain a copy of the License at
8 **
9 ** http://www.apache.org/licenses/LICENSE-2.0
10 **
11 ** Unless required by applicable law or agreed to in writing, software
12 ** distributed under the License is distributed on an "AS IS" BASIS,
13 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 ** See the License for the specific language governing permissions and
15 ** limitations under the License.
16 */
17
18 #include "SkCullPoints.h"
19 #include "Sk64.h"
20
cross_product_is_neg(const SkIPoint & v,int dx,int dy)21 static bool cross_product_is_neg(const SkIPoint& v, int dx, int dy)
22 {
23 #if 0
24 return v.fX * dy - v.fY * dx < 0;
25 #else
26 Sk64 tmp0, tmp1;
27
28 tmp0.setMul(v.fX, dy);
29 tmp1.setMul(dx, v.fY);
30 tmp0.sub(tmp1);
31 return tmp0.isNeg();
32 #endif
33 }
34
sect_test(int x0,int y0,int x1,int y1) const35 bool SkCullPoints::sect_test(int x0, int y0, int x1, int y1) const
36 {
37 const SkIRect& r = fR;
38
39 if (x0 < r.fLeft && x1 < r.fLeft ||
40 x0 > r.fRight && x1 > r.fRight ||
41 y0 < r.fTop && y1 < r.fTop ||
42 y0 > r.fBottom && y1 > r.fBottom)
43 return false;
44
45 // since the crossprod test is a little expensive, check for easy-in cases first
46 if (r.contains(x0, y0) || r.contains(x1, y1))
47 return true;
48
49 // At this point we're not sure, so we do a crossprod test
50 SkIPoint vec;
51 const SkIPoint* rAsQuad = fAsQuad;
52
53 vec.set(x1 - x0, y1 - y0);
54 bool isNeg = cross_product_is_neg(vec, x0 - rAsQuad[0].fX, y0 - rAsQuad[0].fY);
55 for (int i = 1; i < 4; i++) {
56 if (cross_product_is_neg(vec, x0 - rAsQuad[i].fX, y0 - rAsQuad[i].fY) != isNeg)
57 {
58 return true;
59 }
60 }
61 return false; // we didn't intersect
62 }
63
toQuad(const SkIRect & r,SkIPoint quad[4])64 static void toQuad(const SkIRect& r, SkIPoint quad[4])
65 {
66 SkASSERT(quad);
67
68 quad[0].set(r.fLeft, r.fTop);
69 quad[1].set(r.fRight, r.fTop);
70 quad[2].set(r.fRight, r.fBottom);
71 quad[3].set(r.fLeft, r.fBottom);
72 }
73
SkCullPoints()74 SkCullPoints::SkCullPoints()
75 {
76 SkIRect r;
77 r.setEmpty();
78 this->reset(r);
79 }
80
SkCullPoints(const SkIRect & r)81 SkCullPoints::SkCullPoints(const SkIRect& r)
82 {
83 this->reset(r);
84 }
85
reset(const SkIRect & r)86 void SkCullPoints::reset(const SkIRect& r)
87 {
88 fR = r;
89 toQuad(fR, fAsQuad);
90 fPrevPt.set(0, 0);
91 fPrevResult = kNo_Result;
92 }
93
moveTo(int x,int y)94 void SkCullPoints::moveTo(int x, int y)
95 {
96 fPrevPt.set(x, y);
97 fPrevResult = kNo_Result; // so we trigger a movetolineto later
98 }
99
lineTo(int x,int y,SkIPoint line[])100 SkCullPoints::LineToResult SkCullPoints::lineTo(int x, int y, SkIPoint line[])
101 {
102 SkASSERT(line != NULL);
103
104 LineToResult result = kNo_Result;
105 int x0 = fPrevPt.fX;
106 int y0 = fPrevPt.fY;
107
108 // need to upgrade sect_test to chop the result
109 // and to correctly return kLineTo_Result when the result is connected
110 // to the previous call-out
111 if (this->sect_test(x0, y0, x, y))
112 {
113 line[0].set(x0, y0);
114 line[1].set(x, y);
115
116 if (fPrevResult != kNo_Result && fPrevPt.equals(x0, y0))
117 result = kLineTo_Result;
118 else
119 result = kMoveToLineTo_Result;
120 }
121
122 fPrevPt.set(x, y);
123 fPrevResult = result;
124
125 return result;
126 }
127
128 /////////////////////////////////////////////////////////////////////////////////////////////////
129
130 #include "SkPath.h"
131
SkCullPointsPath()132 SkCullPointsPath::SkCullPointsPath()
133 : fCP(), fPath(NULL)
134 {
135 }
136
SkCullPointsPath(const SkIRect & r,SkPath * dst)137 SkCullPointsPath::SkCullPointsPath(const SkIRect& r, SkPath* dst)
138 : fCP(r), fPath(dst)
139 {
140 }
141
reset(const SkIRect & r,SkPath * dst)142 void SkCullPointsPath::reset(const SkIRect& r, SkPath* dst)
143 {
144 fCP.reset(r);
145 fPath = dst;
146 }
147
moveTo(int x,int y)148 void SkCullPointsPath::moveTo(int x, int y)
149 {
150 fCP.moveTo(x, y);
151 }
152
lineTo(int x,int y)153 void SkCullPointsPath::lineTo(int x, int y)
154 {
155 SkIPoint pts[2];
156
157 switch (fCP.lineTo(x, y, pts)) {
158 case SkCullPoints::kMoveToLineTo_Result:
159 fPath->moveTo(SkIntToScalar(pts[0].fX), SkIntToScalar(pts[0].fY));
160 // fall through to the lineto case
161 case SkCullPoints::kLineTo_Result:
162 fPath->lineTo(SkIntToScalar(pts[1].fX), SkIntToScalar(pts[1].fY));
163 break;
164 default:
165 break;
166 }
167 }
168
169