1/**************************************************************************/
2/* aabb.h */
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#ifndef AABB_H
32#define AABB_H
33
34#include "core/math/plane.h"
35#include "core/math/vector3.h"
36
37/**
38 * AABB (Axis Aligned Bounding Box)
39 * This is implemented by a point (position) and the box size.
40 */
41
42class Variant;
43
44struct _NO_DISCARD_ AABB {
45 Vector3 position;
46 Vector3 size;
47
48 real_t get_volume() const;
49 _FORCE_INLINE_ bool has_volume() const {
50 return size.x > 0.0f && size.y > 0.0f && size.z > 0.0f;
51 }
52
53 _FORCE_INLINE_ bool has_surface() const {
54 return size.x > 0.0f || size.y > 0.0f || size.z > 0.0f;
55 }
56
57 const Vector3 &get_position() const { return position; }
58 void set_position(const Vector3 &p_pos) { position = p_pos; }
59 const Vector3 &get_size() const { return size; }
60 void set_size(const Vector3 &p_size) { size = p_size; }
61
62 bool operator==(const AABB &p_rval) const;
63 bool operator!=(const AABB &p_rval) const;
64
65 bool is_equal_approx(const AABB &p_aabb) const;
66 bool is_finite() const;
67 _FORCE_INLINE_ bool intersects(const AABB &p_aabb) const; /// Both AABBs overlap
68 _FORCE_INLINE_ bool intersects_inclusive(const AABB &p_aabb) const; /// Both AABBs (or their faces) overlap
69 _FORCE_INLINE_ bool encloses(const AABB &p_aabb) const; /// p_aabb is completely inside this
70
71 AABB merge(const AABB &p_with) const;
72 void merge_with(const AABB &p_aabb); ///merge with another AABB
73 AABB intersection(const AABB &p_aabb) const; ///get box where two intersect, empty if no intersection occurs
74 bool intersects_segment(const Vector3 &p_from, const Vector3 &p_to, Vector3 *r_clip = nullptr, Vector3 *r_normal = nullptr) const;
75 bool intersects_ray(const Vector3 &p_from, const Vector3 &p_dir, Vector3 *r_clip = nullptr, Vector3 *r_normal = nullptr) const;
76 _FORCE_INLINE_ bool smits_intersect_ray(const Vector3 &p_from, const Vector3 &p_dir, real_t t0, real_t t1) const;
77
78 _FORCE_INLINE_ bool intersects_convex_shape(const Plane *p_planes, int p_plane_count, const Vector3 *p_points, int p_point_count) const;
79 _FORCE_INLINE_ bool inside_convex_shape(const Plane *p_planes, int p_plane_count) const;
80 bool intersects_plane(const Plane &p_plane) const;
81
82 _FORCE_INLINE_ bool has_point(const Vector3 &p_point) const;
83 _FORCE_INLINE_ Vector3 get_support(const Vector3 &p_normal) const;
84
85 Vector3 get_longest_axis() const;
86 int get_longest_axis_index() const;
87 _FORCE_INLINE_ real_t get_longest_axis_size() const;
88
89 Vector3 get_shortest_axis() const;
90 int get_shortest_axis_index() const;
91 _FORCE_INLINE_ real_t get_shortest_axis_size() const;
92
93 AABB grow(real_t p_by) const;
94 _FORCE_INLINE_ void grow_by(real_t p_amount);
95
96 void get_edge(int p_edge, Vector3 &r_from, Vector3 &r_to) const;
97 _FORCE_INLINE_ Vector3 get_endpoint(int p_point) const;
98
99 AABB expand(const Vector3 &p_vector) const;
100 _FORCE_INLINE_ void project_range_in_plane(const Plane &p_plane, real_t &r_min, real_t &r_max) const;
101 _FORCE_INLINE_ void expand_to(const Vector3 &p_vector); /** expand to contain a point if necessary */
102
103 _FORCE_INLINE_ AABB abs() const {
104 return AABB(Vector3(position.x + MIN(size.x, (real_t)0), position.y + MIN(size.y, (real_t)0), position.z + MIN(size.z, (real_t)0)), size.abs());
105 }
106
107 Variant intersects_segment_bind(const Vector3 &p_from, const Vector3 &p_to) const;
108 Variant intersects_ray_bind(const Vector3 &p_from, const Vector3 &p_dir) const;
109
110 _FORCE_INLINE_ void quantize(real_t p_unit);
111 _FORCE_INLINE_ AABB quantized(real_t p_unit) const;
112
113 _FORCE_INLINE_ void set_end(const Vector3 &p_end) {
114 size = p_end - position;
115 }
116
117 _FORCE_INLINE_ Vector3 get_end() const {
118 return position + size;
119 }
120
121 _FORCE_INLINE_ Vector3 get_center() const {
122 return position + (size * 0.5f);
123 }
124
125 operator String() const;
126
127 _FORCE_INLINE_ AABB() {}
128 inline AABB(const Vector3 &p_pos, const Vector3 &p_size) :
129 position(p_pos),
130 size(p_size) {
131 }
132};
133
134inline bool AABB::intersects(const AABB &p_aabb) const {
135#ifdef MATH_CHECKS
136 if (unlikely(size.x < 0 || size.y < 0 || size.z < 0 || p_aabb.size.x < 0 || p_aabb.size.y < 0 || p_aabb.size.z < 0)) {
137 ERR_PRINT("AABB size is negative, this is not supported. Use AABB.abs() to get an AABB with a positive size.");
138 }
139#endif
140 if (position.x >= (p_aabb.position.x + p_aabb.size.x)) {
141 return false;
142 }
143 if ((position.x + size.x) <= p_aabb.position.x) {
144 return false;
145 }
146 if (position.y >= (p_aabb.position.y + p_aabb.size.y)) {
147 return false;
148 }
149 if ((position.y + size.y) <= p_aabb.position.y) {
150 return false;
151 }
152 if (position.z >= (p_aabb.position.z + p_aabb.size.z)) {
153 return false;
154 }
155 if ((position.z + size.z) <= p_aabb.position.z) {
156 return false;
157 }
158
159 return true;
160}
161
162inline bool AABB::intersects_inclusive(const AABB &p_aabb) const {
163#ifdef MATH_CHECKS
164 if (unlikely(size.x < 0 || size.y < 0 || size.z < 0 || p_aabb.size.x < 0 || p_aabb.size.y < 0 || p_aabb.size.z < 0)) {
165 ERR_PRINT("AABB size is negative, this is not supported. Use AABB.abs() to get an AABB with a positive size.");
166 }
167#endif
168 if (position.x > (p_aabb.position.x + p_aabb.size.x)) {
169 return false;
170 }
171 if ((position.x + size.x) < p_aabb.position.x) {
172 return false;
173 }
174 if (position.y > (p_aabb.position.y + p_aabb.size.y)) {
175 return false;
176 }
177 if ((position.y + size.y) < p_aabb.position.y) {
178 return false;
179 }
180 if (position.z > (p_aabb.position.z + p_aabb.size.z)) {
181 return false;
182 }
183 if ((position.z + size.z) < p_aabb.position.z) {
184 return false;
185 }
186
187 return true;
188}
189
190inline bool AABB::encloses(const AABB &p_aabb) const {
191#ifdef MATH_CHECKS
192 if (unlikely(size.x < 0 || size.y < 0 || size.z < 0 || p_aabb.size.x < 0 || p_aabb.size.y < 0 || p_aabb.size.z < 0)) {
193 ERR_PRINT("AABB size is negative, this is not supported. Use AABB.abs() to get an AABB with a positive size.");
194 }
195#endif
196 Vector3 src_min = position;
197 Vector3 src_max = position + size;
198 Vector3 dst_min = p_aabb.position;
199 Vector3 dst_max = p_aabb.position + p_aabb.size;
200
201 return (
202 (src_min.x <= dst_min.x) &&
203 (src_max.x > dst_max.x) &&
204 (src_min.y <= dst_min.y) &&
205 (src_max.y > dst_max.y) &&
206 (src_min.z <= dst_min.z) &&
207 (src_max.z > dst_max.z));
208}
209
210Vector3 AABB::get_support(const Vector3 &p_normal) const {
211 Vector3 half_extents = size * 0.5f;
212 Vector3 ofs = position + half_extents;
213
214 return Vector3(
215 (p_normal.x > 0) ? half_extents.x : -half_extents.x,
216 (p_normal.y > 0) ? half_extents.y : -half_extents.y,
217 (p_normal.z > 0) ? half_extents.z : -half_extents.z) +
218 ofs;
219}
220
221Vector3 AABB::get_endpoint(int p_point) const {
222 switch (p_point) {
223 case 0:
224 return Vector3(position.x, position.y, position.z);
225 case 1:
226 return Vector3(position.x, position.y, position.z + size.z);
227 case 2:
228 return Vector3(position.x, position.y + size.y, position.z);
229 case 3:
230 return Vector3(position.x, position.y + size.y, position.z + size.z);
231 case 4:
232 return Vector3(position.x + size.x, position.y, position.z);
233 case 5:
234 return Vector3(position.x + size.x, position.y, position.z + size.z);
235 case 6:
236 return Vector3(position.x + size.x, position.y + size.y, position.z);
237 case 7:
238 return Vector3(position.x + size.x, position.y + size.y, position.z + size.z);
239 }
240
241 ERR_FAIL_V(Vector3());
242}
243
244bool AABB::intersects_convex_shape(const Plane *p_planes, int p_plane_count, const Vector3 *p_points, int p_point_count) const {
245 Vector3 half_extents = size * 0.5f;
246 Vector3 ofs = position + half_extents;
247
248 for (int i = 0; i < p_plane_count; i++) {
249 const Plane &p = p_planes[i];
250 Vector3 point(
251 (p.normal.x > 0) ? -half_extents.x : half_extents.x,
252 (p.normal.y > 0) ? -half_extents.y : half_extents.y,
253 (p.normal.z > 0) ? -half_extents.z : half_extents.z);
254 point += ofs;
255 if (p.is_point_over(point)) {
256 return false;
257 }
258 }
259
260 // Make sure all points in the shape aren't fully separated from the AABB on
261 // each axis.
262 int bad_point_counts_positive[3] = { 0 };
263 int bad_point_counts_negative[3] = { 0 };
264
265 for (int k = 0; k < 3; k++) {
266 for (int i = 0; i < p_point_count; i++) {
267 if (p_points[i].coord[k] > ofs.coord[k] + half_extents.coord[k]) {
268 bad_point_counts_positive[k]++;
269 }
270 if (p_points[i].coord[k] < ofs.coord[k] - half_extents.coord[k]) {
271 bad_point_counts_negative[k]++;
272 }
273 }
274
275 if (bad_point_counts_negative[k] == p_point_count) {
276 return false;
277 }
278 if (bad_point_counts_positive[k] == p_point_count) {
279 return false;
280 }
281 }
282
283 return true;
284}
285
286bool AABB::inside_convex_shape(const Plane *p_planes, int p_plane_count) const {
287 Vector3 half_extents = size * 0.5f;
288 Vector3 ofs = position + half_extents;
289
290 for (int i = 0; i < p_plane_count; i++) {
291 const Plane &p = p_planes[i];
292 Vector3 point(
293 (p.normal.x < 0) ? -half_extents.x : half_extents.x,
294 (p.normal.y < 0) ? -half_extents.y : half_extents.y,
295 (p.normal.z < 0) ? -half_extents.z : half_extents.z);
296 point += ofs;
297 if (p.is_point_over(point)) {
298 return false;
299 }
300 }
301
302 return true;
303}
304
305bool AABB::has_point(const Vector3 &p_point) const {
306#ifdef MATH_CHECKS
307 if (unlikely(size.x < 0 || size.y < 0 || size.z < 0)) {
308 ERR_PRINT("AABB size is negative, this is not supported. Use AABB.abs() to get an AABB with a positive size.");
309 }
310#endif
311 if (p_point.x < position.x) {
312 return false;
313 }
314 if (p_point.y < position.y) {
315 return false;
316 }
317 if (p_point.z < position.z) {
318 return false;
319 }
320 if (p_point.x > position.x + size.x) {
321 return false;
322 }
323 if (p_point.y > position.y + size.y) {
324 return false;
325 }
326 if (p_point.z > position.z + size.z) {
327 return false;
328 }
329
330 return true;
331}
332
333inline void AABB::expand_to(const Vector3 &p_vector) {
334#ifdef MATH_CHECKS
335 if (unlikely(size.x < 0 || size.y < 0 || size.z < 0)) {
336 ERR_PRINT("AABB size is negative, this is not supported. Use AABB.abs() to get an AABB with a positive size.");
337 }
338#endif
339 Vector3 begin = position;
340 Vector3 end = position + size;
341
342 if (p_vector.x < begin.x) {
343 begin.x = p_vector.x;
344 }
345 if (p_vector.y < begin.y) {
346 begin.y = p_vector.y;
347 }
348 if (p_vector.z < begin.z) {
349 begin.z = p_vector.z;
350 }
351
352 if (p_vector.x > end.x) {
353 end.x = p_vector.x;
354 }
355 if (p_vector.y > end.y) {
356 end.y = p_vector.y;
357 }
358 if (p_vector.z > end.z) {
359 end.z = p_vector.z;
360 }
361
362 position = begin;
363 size = end - begin;
364}
365
366void AABB::project_range_in_plane(const Plane &p_plane, real_t &r_min, real_t &r_max) const {
367 Vector3 half_extents(size.x * 0.5f, size.y * 0.5f, size.z * 0.5f);
368 Vector3 center(position.x + half_extents.x, position.y + half_extents.y, position.z + half_extents.z);
369
370 real_t length = p_plane.normal.abs().dot(half_extents);
371 real_t distance = p_plane.distance_to(center);
372 r_min = distance - length;
373 r_max = distance + length;
374}
375
376inline real_t AABB::get_longest_axis_size() const {
377 real_t max_size = size.x;
378
379 if (size.y > max_size) {
380 max_size = size.y;
381 }
382
383 if (size.z > max_size) {
384 max_size = size.z;
385 }
386
387 return max_size;
388}
389
390inline real_t AABB::get_shortest_axis_size() const {
391 real_t max_size = size.x;
392
393 if (size.y < max_size) {
394 max_size = size.y;
395 }
396
397 if (size.z < max_size) {
398 max_size = size.z;
399 }
400
401 return max_size;
402}
403
404bool AABB::smits_intersect_ray(const Vector3 &p_from, const Vector3 &p_dir, real_t t0, real_t t1) const {
405#ifdef MATH_CHECKS
406 if (unlikely(size.x < 0 || size.y < 0 || size.z < 0)) {
407 ERR_PRINT("AABB size is negative, this is not supported. Use AABB.abs() to get an AABB with a positive size.");
408 }
409#endif
410 real_t divx = 1.0f / p_dir.x;
411 real_t divy = 1.0f / p_dir.y;
412 real_t divz = 1.0f / p_dir.z;
413
414 Vector3 upbound = position + size;
415 real_t tmin, tmax, tymin, tymax, tzmin, tzmax;
416 if (p_dir.x >= 0) {
417 tmin = (position.x - p_from.x) * divx;
418 tmax = (upbound.x - p_from.x) * divx;
419 } else {
420 tmin = (upbound.x - p_from.x) * divx;
421 tmax = (position.x - p_from.x) * divx;
422 }
423 if (p_dir.y >= 0) {
424 tymin = (position.y - p_from.y) * divy;
425 tymax = (upbound.y - p_from.y) * divy;
426 } else {
427 tymin = (upbound.y - p_from.y) * divy;
428 tymax = (position.y - p_from.y) * divy;
429 }
430 if ((tmin > tymax) || (tymin > tmax)) {
431 return false;
432 }
433 if (tymin > tmin) {
434 tmin = tymin;
435 }
436 if (tymax < tmax) {
437 tmax = tymax;
438 }
439 if (p_dir.z >= 0) {
440 tzmin = (position.z - p_from.z) * divz;
441 tzmax = (upbound.z - p_from.z) * divz;
442 } else {
443 tzmin = (upbound.z - p_from.z) * divz;
444 tzmax = (position.z - p_from.z) * divz;
445 }
446 if ((tmin > tzmax) || (tzmin > tmax)) {
447 return false;
448 }
449 if (tzmin > tmin) {
450 tmin = tzmin;
451 }
452 if (tzmax < tmax) {
453 tmax = tzmax;
454 }
455 return ((tmin < t1) && (tmax > t0));
456}
457
458void AABB::grow_by(real_t p_amount) {
459 position.x -= p_amount;
460 position.y -= p_amount;
461 position.z -= p_amount;
462 size.x += 2.0f * p_amount;
463 size.y += 2.0f * p_amount;
464 size.z += 2.0f * p_amount;
465}
466
467void AABB::quantize(real_t p_unit) {
468 size += position;
469
470 position.x -= Math::fposmodp(position.x, p_unit);
471 position.y -= Math::fposmodp(position.y, p_unit);
472 position.z -= Math::fposmodp(position.z, p_unit);
473
474 size.x -= Math::fposmodp(size.x, p_unit);
475 size.y -= Math::fposmodp(size.y, p_unit);
476 size.z -= Math::fposmodp(size.z, p_unit);
477
478 size.x += p_unit;
479 size.y += p_unit;
480 size.z += p_unit;
481
482 size -= position;
483}
484
485AABB AABB::quantized(real_t p_unit) const {
486 AABB ret = *this;
487 ret.quantize(p_unit);
488 return ret;
489}
490
491#endif // AABB_H
492