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 #if 0
23 return v.fX * dy - v.fY * dx < 0;
24 #else
25 Sk64 tmp0, tmp1;
26
27 tmp0.setMul(v.fX, dy);
28 tmp1.setMul(dx, v.fY);
29 tmp0.sub(tmp1);
30 return tmp0.isNeg() != 0;
31 #endif
32 }
33
sect_test(int x0,int y0,int x1,int y1) const34 bool SkCullPoints::sect_test(int x0, int y0, int x1, int y1) const {
35 const SkIRect& r = fR;
36
37 if ((x0 < r.fLeft && x1 < r.fLeft) ||
38 (x0 > r.fRight && x1 > r.fRight) ||
39 (y0 < r.fTop && y1 < r.fTop) ||
40 (y0 > r.fBottom && y1 > r.fBottom)) {
41 return false;
42 }
43
44 // since the crossprod test is a little expensive, check for easy-in cases first
45 if (r.contains(x0, y0) || r.contains(x1, y1)) {
46 return true;
47 }
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 return true;
58 }
59 }
60 return false; // we didn't intersect
61 }
62
toQuad(const SkIRect & r,SkIPoint quad[4])63 static void toQuad(const SkIRect& r, SkIPoint quad[4]) {
64 SkASSERT(quad);
65
66 quad[0].set(r.fLeft, r.fTop);
67 quad[1].set(r.fRight, r.fTop);
68 quad[2].set(r.fRight, r.fBottom);
69 quad[3].set(r.fLeft, r.fBottom);
70 }
71
SkCullPoints()72 SkCullPoints::SkCullPoints() {
73 SkIRect r;
74 r.setEmpty();
75 this->reset(r);
76 }
77
SkCullPoints(const SkIRect & r)78 SkCullPoints::SkCullPoints(const SkIRect& r) {
79 this->reset(r);
80 }
81
reset(const SkIRect & r)82 void SkCullPoints::reset(const SkIRect& r) {
83 fR = r;
84 toQuad(fR, fAsQuad);
85 fPrevPt.set(0, 0);
86 fPrevResult = kNo_Result;
87 }
88
moveTo(int x,int y)89 void SkCullPoints::moveTo(int x, int y) {
90 fPrevPt.set(x, y);
91 fPrevResult = kNo_Result; // so we trigger a movetolineto later
92 }
93
lineTo(int x,int y,SkIPoint line[])94 SkCullPoints::LineToResult SkCullPoints::lineTo(int x, int y, SkIPoint line[]) {
95 SkASSERT(line != NULL);
96
97 LineToResult result = kNo_Result;
98 int x0 = fPrevPt.fX;
99 int y0 = fPrevPt.fY;
100
101 // need to upgrade sect_test to chop the result
102 // and to correctly return kLineTo_Result when the result is connected
103 // to the previous call-out
104 if (this->sect_test(x0, y0, x, y)) {
105 line[0].set(x0, y0);
106 line[1].set(x, y);
107
108 if (fPrevResult != kNo_Result && fPrevPt.equals(x0, y0)) {
109 result = kLineTo_Result;
110 } else {
111 result = kMoveToLineTo_Result;
112 }
113 }
114
115 fPrevPt.set(x, y);
116 fPrevResult = result;
117
118 return result;
119 }
120
121 /////////////////////////////////////////////////////////////////////////////////////////////////
122
123 #include "SkPath.h"
124
SkCullPointsPath()125 SkCullPointsPath::SkCullPointsPath()
126 : fCP(), fPath(NULL) {
127 }
128
SkCullPointsPath(const SkIRect & r,SkPath * dst)129 SkCullPointsPath::SkCullPointsPath(const SkIRect& r, SkPath* dst)
130 : fCP(r), fPath(dst) {
131 }
132
reset(const SkIRect & r,SkPath * dst)133 void SkCullPointsPath::reset(const SkIRect& r, SkPath* dst) {
134 fCP.reset(r);
135 fPath = dst;
136 }
137
moveTo(int x,int y)138 void SkCullPointsPath::moveTo(int x, int y) {
139 fCP.moveTo(x, y);
140 }
141
lineTo(int x,int y)142 void SkCullPointsPath::lineTo(int x, int y) {
143 SkIPoint pts[2];
144
145 switch (fCP.lineTo(x, y, pts)) {
146 case SkCullPoints::kMoveToLineTo_Result:
147 fPath->moveTo(SkIntToScalar(pts[0].fX), SkIntToScalar(pts[0].fY));
148 // fall through to the lineto case
149 case SkCullPoints::kLineTo_Result:
150 fPath->lineTo(SkIntToScalar(pts[1].fX), SkIntToScalar(pts[1].fY));
151 break;
152 default:
153 break;
154 }
155 }
156
157