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 "include/core/SkRect.h"
9
10 #include "include/private/SkMalloc.h"
11 #include "src/core/SkRectPriv.h"
12
intersect(const SkIRect & a,const SkIRect & b)13 bool SkIRect::intersect(const SkIRect& a, const SkIRect& b) {
14 SkIRect tmp = {
15 std::max(a.fLeft, b.fLeft),
16 std::max(a.fTop, b.fTop),
17 std::min(a.fRight, b.fRight),
18 std::min(a.fBottom, b.fBottom)
19 };
20 if (tmp.isEmpty()) {
21 return false;
22 }
23 *this = tmp;
24 return true;
25 }
26
join(const SkIRect & r)27 void SkIRect::join(const SkIRect& r) {
28 // do nothing if the params are empty
29 if (r.fLeft >= r.fRight || r.fTop >= r.fBottom) {
30 return;
31 }
32
33 // if we are empty, just assign
34 if (fLeft >= fRight || fTop >= fBottom) {
35 *this = r;
36 } else {
37 if (r.fLeft < fLeft) fLeft = r.fLeft;
38 if (r.fTop < fTop) fTop = r.fTop;
39 if (r.fRight > fRight) fRight = r.fRight;
40 if (r.fBottom > fBottom) fBottom = r.fBottom;
41 }
42 }
43
44 /////////////////////////////////////////////////////////////////////////////
45
toQuad(SkPoint quad[4]) const46 void SkRect::toQuad(SkPoint quad[4]) const {
47 SkASSERT(quad);
48
49 quad[0].set(fLeft, fTop);
50 quad[1].set(fRight, fTop);
51 quad[2].set(fRight, fBottom);
52 quad[3].set(fLeft, fBottom);
53 }
54
55 #include "include/private/SkNx.h"
56
setBoundsCheck(const SkPoint pts[],int count)57 bool SkRect::setBoundsCheck(const SkPoint pts[], int count) {
58 SkASSERT((pts && count > 0) || count == 0);
59
60 if (count <= 0) {
61 this->setEmpty();
62 return true;
63 }
64
65 Sk4s min, max;
66 if (count & 1) {
67 min = max = Sk4s(pts->fX, pts->fY,
68 pts->fX, pts->fY);
69 pts += 1;
70 count -= 1;
71 } else {
72 min = max = Sk4s::Load(pts);
73 pts += 2;
74 count -= 2;
75 }
76
77 Sk4s accum = min * 0;
78 while (count) {
79 Sk4s xy = Sk4s::Load(pts);
80 accum = accum * xy;
81 min = Sk4s::Min(min, xy);
82 max = Sk4s::Max(max, xy);
83 pts += 2;
84 count -= 2;
85 }
86
87 bool all_finite = (accum * 0 == 0).allTrue();
88 if (all_finite) {
89 this->setLTRB(std::min(min[0], min[2]), std::min(min[1], min[3]),
90 std::max(max[0], max[2]), std::max(max[1], max[3]));
91 } else {
92 this->setEmpty();
93 }
94 return all_finite;
95 }
96
setBoundsNoCheck(const SkPoint pts[],int count)97 void SkRect::setBoundsNoCheck(const SkPoint pts[], int count) {
98 if (!this->setBoundsCheck(pts, count)) {
99 this->setLTRB(SK_ScalarNaN, SK_ScalarNaN, SK_ScalarNaN, SK_ScalarNaN);
100 }
101 }
102
103 #define CHECK_INTERSECT(al, at, ar, ab, bl, bt, br, bb) \
104 SkScalar L = std::max(al, bl); \
105 SkScalar R = std::min(ar, br); \
106 SkScalar T = std::max(at, bt); \
107 SkScalar B = std::min(ab, bb); \
108 do { if (!(L < R && T < B)) return false; } while (0)
109 // do the !(opposite) check so we return false if either arg is NaN
110
intersect(const SkRect & r)111 bool SkRect::intersect(const SkRect& r) {
112 CHECK_INTERSECT(r.fLeft, r.fTop, r.fRight, r.fBottom, fLeft, fTop, fRight, fBottom);
113 this->setLTRB(L, T, R, B);
114 return true;
115 }
116
intersect(const SkRect & a,const SkRect & b)117 bool SkRect::intersect(const SkRect& a, const SkRect& b) {
118 CHECK_INTERSECT(a.fLeft, a.fTop, a.fRight, a.fBottom, b.fLeft, b.fTop, b.fRight, b.fBottom);
119 this->setLTRB(L, T, R, B);
120 return true;
121 }
122
join(const SkRect & r)123 void SkRect::join(const SkRect& r) {
124 if (r.isEmpty()) {
125 return;
126 }
127
128 if (this->isEmpty()) {
129 *this = r;
130 } else {
131 fLeft = std::min(fLeft, r.fLeft);
132 fTop = std::min(fTop, r.fTop);
133 fRight = std::max(fRight, r.fRight);
134 fBottom = std::max(fBottom, r.fBottom);
135 }
136 }
137
138 ////////////////////////////////////////////////////////////////////////////////////////////////
139
140 #include "include/core/SkString.h"
141 #include "src/core/SkStringUtils.h"
142
set_scalar(SkString * storage,SkScalar value,SkScalarAsStringType asType)143 static const char* set_scalar(SkString* storage, SkScalar value, SkScalarAsStringType asType) {
144 storage->reset();
145 SkAppendScalar(storage, value, asType);
146 return storage->c_str();
147 }
148
dump(bool asHex) const149 void SkRect::dump(bool asHex) const {
150 SkScalarAsStringType asType = asHex ? kHex_SkScalarAsStringType : kDec_SkScalarAsStringType;
151
152 SkString line;
153 if (asHex) {
154 SkString tmp;
155 line.printf( "SkRect::MakeLTRB(%s, /* %f */\n", set_scalar(&tmp, fLeft, asType), fLeft);
156 line.appendf(" %s, /* %f */\n", set_scalar(&tmp, fTop, asType), fTop);
157 line.appendf(" %s, /* %f */\n", set_scalar(&tmp, fRight, asType), fRight);
158 line.appendf(" %s /* %f */);", set_scalar(&tmp, fBottom, asType), fBottom);
159 } else {
160 SkString strL, strT, strR, strB;
161 SkAppendScalarDec(&strL, fLeft);
162 SkAppendScalarDec(&strT, fTop);
163 SkAppendScalarDec(&strR, fRight);
164 SkAppendScalarDec(&strB, fBottom);
165 line.printf("SkRect::MakeLTRB(%s, %s, %s, %s);",
166 strL.c_str(), strT.c_str(), strR.c_str(), strB.c_str());
167 }
168 SkDebugf("%s\n", line.c_str());
169 }
170
171 ////////////////////////////////////////////////////////////////////////////////////////////////
172
173 template<typename R>
subtract(const R & a,const R & b,R * out)174 static bool subtract(const R& a, const R& b, R* out) {
175 if (a.isEmpty() || b.isEmpty() || !R::Intersects(a, b)) {
176 // Either already empty, or subtracting the empty rect, or there's no intersection, so
177 // in all cases the answer is A.
178 *out = a;
179 return true;
180 }
181
182 // 4 rectangles to consider. If the edge in A is contained in B, the resulting difference can
183 // be represented exactly as a rectangle. Otherwise the difference is the largest subrectangle
184 // that is disjoint from B:
185 // 1. Left part of A: (A.left, A.top, B.left, A.bottom)
186 // 2. Right part of A: (B.right, A.top, A.right, A.bottom)
187 // 3. Top part of A: (A.left, A.top, A.right, B.top)
188 // 4. Bottom part of A: (A.left, B.bottom, A.right, A.bottom)
189 //
190 // Depending on how B intersects A, there will be 1 to 4 positive areas:
191 // - 4 occur when A contains B
192 // - 3 occur when B intersects a single edge
193 // - 2 occur when B intersects at a corner, or spans two opposing edges
194 // - 1 occurs when B spans two opposing edges and contains a 3rd, resulting in an exact rect
195 // - 0 occurs when B contains A, resulting in the empty rect
196 //
197 // Compute the relative areas of the 4 rects described above. Since each subrectangle shares
198 // either the width or height of A, we only have to divide by the other dimension, which avoids
199 // overflow on int32 types, and even if the float relative areas overflow to infinity, the
200 // comparisons work out correctly and (one of) the infinitely large subrects will be chosen.
201 float aHeight = (float) a.height();
202 float aWidth = (float) a.width();
203 float leftArea = 0.f, rightArea = 0.f, topArea = 0.f, bottomArea = 0.f;
204 int positiveCount = 0;
205 if (b.fLeft > a.fLeft) {
206 leftArea = (b.fLeft - a.fLeft) / aWidth;
207 positiveCount++;
208 }
209 if (a.fRight > b.fRight) {
210 rightArea = (a.fRight - b.fRight) / aWidth;
211 positiveCount++;
212 }
213 if (b.fTop > a.fTop) {
214 topArea = (b.fTop - a.fTop) / aHeight;
215 positiveCount++;
216 }
217 if (a.fBottom > b.fBottom) {
218 bottomArea = (a.fBottom - b.fBottom) / aHeight;
219 positiveCount++;
220 }
221
222 if (positiveCount == 0) {
223 SkASSERT(b.contains(a));
224 *out = R::MakeEmpty();
225 return true;
226 }
227
228 *out = a;
229 if (leftArea > rightArea && leftArea > topArea && leftArea > bottomArea) {
230 // Left chunk of A, so the new right edge is B's left edge
231 out->fRight = b.fLeft;
232 } else if (rightArea > topArea && rightArea > bottomArea) {
233 // Right chunk of A, so the new left edge is B's right edge
234 out->fLeft = b.fRight;
235 } else if (topArea > bottomArea) {
236 // Top chunk of A, so the new bottom edge is B's top edge
237 out->fBottom = b.fTop;
238 } else {
239 // Bottom chunk of A, so the new top edge is B's bottom edge
240 SkASSERT(bottomArea > 0.f);
241 out->fTop = b.fBottom;
242 }
243
244 // If we have 1 valid area, the disjoint shape is representable as a rectangle.
245 SkASSERT(!R::Intersects(*out, b));
246 return positiveCount == 1;
247 }
248
Subtract(const SkRect & a,const SkRect & b,SkRect * out)249 bool SkRectPriv::Subtract(const SkRect& a, const SkRect& b, SkRect* out) {
250 return subtract<SkRect>(a, b, out);
251 }
252
Subtract(const SkIRect & a,const SkIRect & b,SkIRect * out)253 bool SkRectPriv::Subtract(const SkIRect& a, const SkIRect& b, SkIRect* out) {
254 return subtract<SkIRect>(a, b, out);
255 }
256