1/**************************************************************************/
2/* rect2.cpp */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
10/* */
11/* Permission is hereby granted, free of charge, to any person obtaining */
12/* a copy of this software and associated documentation files (the */
13/* "Software"), to deal in the Software without restriction, including */
14/* without limitation the rights to use, copy, modify, merge, publish, */
15/* distribute, sublicense, and/or sell copies of the Software, and to */
16/* permit persons to whom the Software is furnished to do so, subject to */
17/* the following conditions: */
18/* */
19/* The above copyright notice and this permission notice shall be */
20/* included in all copies or substantial portions of the Software. */
21/* */
22/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
25/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29/**************************************************************************/
30
31#include "rect2.h"
32
33#include "core/math/rect2i.h"
34#include "core/math/transform_2d.h"
35#include "core/string/ustring.h"
36
37bool Rect2::is_equal_approx(const Rect2 &p_rect) const {
38 return position.is_equal_approx(p_rect.position) && size.is_equal_approx(p_rect.size);
39}
40
41bool Rect2::is_finite() const {
42 return position.is_finite() && size.is_finite();
43}
44
45bool Rect2::intersects_segment(const Point2 &p_from, const Point2 &p_to, Point2 *r_pos, Point2 *r_normal) const {
46#ifdef MATH_CHECKS
47 if (unlikely(size.x < 0 || size.y < 0)) {
48 ERR_PRINT("Rect2 size is negative, this is not supported. Use Rect2.abs() to get a Rect2 with a positive size.");
49 }
50#endif
51 real_t min = 0, max = 1;
52 int axis = 0;
53 real_t sign = 0;
54
55 for (int i = 0; i < 2; i++) {
56 real_t seg_from = p_from[i];
57 real_t seg_to = p_to[i];
58 real_t box_begin = position[i];
59 real_t box_end = box_begin + size[i];
60 real_t cmin, cmax;
61 real_t csign;
62
63 if (seg_from < seg_to) {
64 if (seg_from > box_end || seg_to < box_begin) {
65 return false;
66 }
67 real_t length = seg_to - seg_from;
68 cmin = (seg_from < box_begin) ? ((box_begin - seg_from) / length) : 0;
69 cmax = (seg_to > box_end) ? ((box_end - seg_from) / length) : 1;
70 csign = -1.0;
71
72 } else {
73 if (seg_to > box_end || seg_from < box_begin) {
74 return false;
75 }
76 real_t length = seg_to - seg_from;
77 cmin = (seg_from > box_end) ? (box_end - seg_from) / length : 0;
78 cmax = (seg_to < box_begin) ? (box_begin - seg_from) / length : 1;
79 csign = 1.0;
80 }
81
82 if (cmin > min) {
83 min = cmin;
84 axis = i;
85 sign = csign;
86 }
87 if (cmax < max) {
88 max = cmax;
89 }
90 if (max < min) {
91 return false;
92 }
93 }
94
95 Vector2 rel = p_to - p_from;
96
97 if (r_normal) {
98 Vector2 normal;
99 normal[axis] = sign;
100 *r_normal = normal;
101 }
102
103 if (r_pos) {
104 *r_pos = p_from + rel * min;
105 }
106
107 return true;
108}
109
110bool Rect2::intersects_transformed(const Transform2D &p_xform, const Rect2 &p_rect) const {
111#ifdef MATH_CHECKS
112 if (unlikely(size.x < 0 || size.y < 0 || p_rect.size.x < 0 || p_rect.size.y < 0)) {
113 ERR_PRINT("Rect2 size is negative, this is not supported. Use Rect2.abs() to get a Rect2 with a positive size.");
114 }
115#endif
116 //SAT intersection between local and transformed rect2
117
118 Vector2 xf_points[4] = {
119 p_xform.xform(p_rect.position),
120 p_xform.xform(Vector2(p_rect.position.x + p_rect.size.x, p_rect.position.y)),
121 p_xform.xform(Vector2(p_rect.position.x, p_rect.position.y + p_rect.size.y)),
122 p_xform.xform(Vector2(p_rect.position.x + p_rect.size.x, p_rect.position.y + p_rect.size.y)),
123 };
124
125 real_t low_limit;
126
127 //base rect2 first (faster)
128
129 if (xf_points[0].y > position.y) {
130 goto next1;
131 }
132 if (xf_points[1].y > position.y) {
133 goto next1;
134 }
135 if (xf_points[2].y > position.y) {
136 goto next1;
137 }
138 if (xf_points[3].y > position.y) {
139 goto next1;
140 }
141
142 return false;
143
144next1:
145
146 low_limit = position.y + size.y;
147
148 if (xf_points[0].y < low_limit) {
149 goto next2;
150 }
151 if (xf_points[1].y < low_limit) {
152 goto next2;
153 }
154 if (xf_points[2].y < low_limit) {
155 goto next2;
156 }
157 if (xf_points[3].y < low_limit) {
158 goto next2;
159 }
160
161 return false;
162
163next2:
164
165 if (xf_points[0].x > position.x) {
166 goto next3;
167 }
168 if (xf_points[1].x > position.x) {
169 goto next3;
170 }
171 if (xf_points[2].x > position.x) {
172 goto next3;
173 }
174 if (xf_points[3].x > position.x) {
175 goto next3;
176 }
177
178 return false;
179
180next3:
181
182 low_limit = position.x + size.x;
183
184 if (xf_points[0].x < low_limit) {
185 goto next4;
186 }
187 if (xf_points[1].x < low_limit) {
188 goto next4;
189 }
190 if (xf_points[2].x < low_limit) {
191 goto next4;
192 }
193 if (xf_points[3].x < low_limit) {
194 goto next4;
195 }
196
197 return false;
198
199next4:
200
201 Vector2 xf_points2[4] = {
202 position,
203 Vector2(position.x + size.x, position.y),
204 Vector2(position.x, position.y + size.y),
205 Vector2(position.x + size.x, position.y + size.y),
206 };
207
208 real_t maxa = p_xform.columns[0].dot(xf_points2[0]);
209 real_t mina = maxa;
210
211 real_t dp = p_xform.columns[0].dot(xf_points2[1]);
212 maxa = MAX(dp, maxa);
213 mina = MIN(dp, mina);
214
215 dp = p_xform.columns[0].dot(xf_points2[2]);
216 maxa = MAX(dp, maxa);
217 mina = MIN(dp, mina);
218
219 dp = p_xform.columns[0].dot(xf_points2[3]);
220 maxa = MAX(dp, maxa);
221 mina = MIN(dp, mina);
222
223 real_t maxb = p_xform.columns[0].dot(xf_points[0]);
224 real_t minb = maxb;
225
226 dp = p_xform.columns[0].dot(xf_points[1]);
227 maxb = MAX(dp, maxb);
228 minb = MIN(dp, minb);
229
230 dp = p_xform.columns[0].dot(xf_points[2]);
231 maxb = MAX(dp, maxb);
232 minb = MIN(dp, minb);
233
234 dp = p_xform.columns[0].dot(xf_points[3]);
235 maxb = MAX(dp, maxb);
236 minb = MIN(dp, minb);
237
238 if (mina > maxb) {
239 return false;
240 }
241 if (minb > maxa) {
242 return false;
243 }
244
245 maxa = p_xform.columns[1].dot(xf_points2[0]);
246 mina = maxa;
247
248 dp = p_xform.columns[1].dot(xf_points2[1]);
249 maxa = MAX(dp, maxa);
250 mina = MIN(dp, mina);
251
252 dp = p_xform.columns[1].dot(xf_points2[2]);
253 maxa = MAX(dp, maxa);
254 mina = MIN(dp, mina);
255
256 dp = p_xform.columns[1].dot(xf_points2[3]);
257 maxa = MAX(dp, maxa);
258 mina = MIN(dp, mina);
259
260 maxb = p_xform.columns[1].dot(xf_points[0]);
261 minb = maxb;
262
263 dp = p_xform.columns[1].dot(xf_points[1]);
264 maxb = MAX(dp, maxb);
265 minb = MIN(dp, minb);
266
267 dp = p_xform.columns[1].dot(xf_points[2]);
268 maxb = MAX(dp, maxb);
269 minb = MIN(dp, minb);
270
271 dp = p_xform.columns[1].dot(xf_points[3]);
272 maxb = MAX(dp, maxb);
273 minb = MIN(dp, minb);
274
275 if (mina > maxb) {
276 return false;
277 }
278 if (minb > maxa) {
279 return false;
280 }
281
282 return true;
283}
284
285Rect2::operator String() const {
286 return "[P: " + position.operator String() + ", S: " + size + "]";
287}
288
289Rect2::operator Rect2i() const {
290 return Rect2i(position, size);
291}
292