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