1 /** 2 Axis-Aligned Bounding Box. 3 4 Copyright: 5 Copyright (c) 2007 Juan Linietsky, Ariel Manzur. 6 Copyright (c) 2014 Godot Engine contributors (cf. AUTHORS.md) 7 Copyright (c) 2017 Godot-D contributors 8 Copyright (c) 2022 Godot-DLang contributors 9 10 License: $(LINK2 https://opensource.org/licenses/MIT, MIT License) 11 12 13 */ 14 module godot.aabb; 15 16 import godot.api.types; 17 import godot.vector3; 18 import godot.plane; 19 20 import std.algorithm.mutation : swap; 21 22 /** 23 AABB consists of a position, a size, and several utility functions. It is typically used for fast overlap tests. 24 */ 25 struct AABB { 26 @nogc nothrow: 27 28 Vector3 position; 29 Vector3 size; 30 31 deprecated("pos has been renamed to position, please use position instead") 32 alias pos = position; 33 34 bool hasNoArea() const { 35 return (size.x <= CMP_EPSILON || size.y <= CMP_EPSILON || size.z <= CMP_EPSILON); 36 } 37 38 bool hasNoSurface() const { 39 return (size.x <= CMP_EPSILON && size.y <= CMP_EPSILON && size.z <= CMP_EPSILON); 40 } 41 42 bool intersects(in AABB p_aabb) const { 43 if (position.x >= (p_aabb.position.x + p_aabb.size.x)) 44 return false; 45 if ((position.x + size.x) <= p_aabb.position.x) 46 return false; 47 if (position.y >= (p_aabb.position.y + p_aabb.size.y)) 48 return false; 49 if ((position.y + size.y) <= p_aabb.position.y) 50 return false; 51 if (position.z >= (p_aabb.position.z + p_aabb.size.z)) 52 return false; 53 if ((position.z + size.z) <= p_aabb.position.z) 54 return false; 55 return true; 56 } 57 58 bool intersectsInclusive(in AABB p_aabb) const { 59 if (position.x > (p_aabb.position.x + p_aabb.size.x)) 60 return false; 61 if ((position.x + size.x) < p_aabb.position.x) 62 return false; 63 if (position.y > (p_aabb.position.y + p_aabb.size.y)) 64 return false; 65 if ((position.y + size.y) < p_aabb.position.y) 66 return false; 67 if (position.z > (p_aabb.position.z + p_aabb.size.z)) 68 return false; 69 if ((position.z + size.z) < p_aabb.position.z) 70 return false; 71 return true; 72 } 73 74 bool encloses(in AABB p_aabb) const { 75 Vector3 src_min = position; 76 Vector3 src_max = position + size; 77 Vector3 dst_min = p_aabb.position; 78 Vector3 dst_max = p_aabb.position + p_aabb.size; 79 80 return ( 81 (src_min.x <= dst_min.x) && 82 (src_max.x > dst_max.x) && 83 (src_min.y <= dst_min.y) && 84 (src_max.y > dst_max.y) && 85 (src_min.z <= dst_min.z) && 86 (src_max.z > dst_max.z)); 87 88 } 89 90 Vector3 getSupport(in Vector3 p_normal) const { 91 Vector3 half_extents = size * 0.5; 92 Vector3 ofs = position + half_extents; 93 94 return Vector3( 95 (p_normal.x > 0) ? -half_extents.x : half_extents.x, 96 (p_normal.y > 0) ? -half_extents.y : half_extents.y, 97 (p_normal.z > 0) ? -half_extents.z : half_extents.z 98 ) + ofs; 99 } 100 101 Vector3 getEndpoint(int p_point) const { 102 switch (p_point) { 103 case 0: 104 return Vector3(position.x, position.y, position.z); 105 case 1: 106 return Vector3(position.x, position.y, position.z + size.z); 107 case 2: 108 return Vector3(position.x, position.y + size.y, position.z); 109 case 3: 110 return Vector3(position.x, position.y + size.y, position.z + size.z); 111 case 4: 112 return Vector3(position.x + size.x, position.y, position.z); 113 case 5: 114 return Vector3(position.x + size.x, position.y, position.z + size.z); 115 case 6: 116 return Vector3(position.x + size.x, position.y + size.y, position.z); 117 case 7: 118 return Vector3(position.x + size.x, position.y + size.y, position.z + size.z); 119 default: 120 assert(0); ///ERR_FAIL_V(Vector3()) 121 } 122 } 123 124 bool intersectsConvexShape(in Plane[] p_planes) const { 125 Vector3 half_extents = size * 0.5; 126 Vector3 ofs = position + half_extents; 127 128 foreach (const ref p; p_planes) { 129 Vector3 point = Vector3( 130 (p.normal.x > 0) ? -half_extents.x 131 : half_extents.x, 132 (p.normal.y > 0) ? -half_extents.y 133 : half_extents.y, 134 (p.normal.z > 0) ? -half_extents.z : half_extents.z 135 ); 136 point += ofs; 137 if (p.isPointOver(point)) 138 return false; 139 } 140 141 return true; 142 } 143 144 bool hasPoint(in Vector3 p_point) const { 145 if (p_point.x < position.x) 146 return false; 147 if (p_point.y < position.y) 148 return false; 149 if (p_point.z < position.z) 150 return false; 151 if (p_point.x > position.x + size.x) 152 return false; 153 if (p_point.y > position.y + size.y) 154 return false; 155 if (p_point.z > position.z + size.z) 156 return false; 157 158 return true; 159 } 160 161 void expandTo(in Vector3 p_vector) { 162 Vector3 begin = position; 163 Vector3 end = position + size; 164 165 if (p_vector.x < begin.x) 166 begin.x = p_vector.x; 167 if (p_vector.y < begin.y) 168 begin.y = p_vector.y; 169 if (p_vector.z < begin.z) 170 begin.z = p_vector.z; 171 172 if (p_vector.x > end.x) 173 end.x = p_vector.x; 174 if (p_vector.y > end.y) 175 end.y = p_vector.y; 176 if (p_vector.z > end.z) 177 end.z = p_vector.z; 178 179 position = begin; 180 size = end - begin; 181 } 182 183 void projectRangeInPlane(in Plane p_plane, out real_t r_min, out real_t r_max) const { 184 Vector3 half_extents = Vector3(size.x * 0.5, size.y * 0.5, size.z * 0.5); 185 Vector3 center = Vector3(position.x + half_extents.x, position.y + half_extents.y, position.z + half_extents 186 .z); 187 188 real_t length = p_plane.normal.abs().dot(half_extents); 189 real_t distance = p_plane.distanceTo(center); 190 r_min = distance - length; 191 r_max = distance + length; 192 } 193 194 real_t getLongestAxisSize() const { 195 real_t max_size = size.x; 196 197 if (size.y > max_size) { 198 max_size = size.y; 199 } 200 201 if (size.z > max_size) { 202 max_size = size.z; 203 } 204 205 return max_size; 206 } 207 208 real_t getShortestAxisSize() const { 209 real_t max_size = size.x; 210 211 if (size.y < max_size) { 212 max_size = size.y; 213 } 214 215 if (size.z < max_size) { 216 max_size = size.z; 217 } 218 219 return max_size; 220 } 221 222 bool smitsIntersectRay(in Vector3 from, in Vector3 dir, real_t t0, real_t t1) const { 223 real_t divx = 1.0 / dir.x; 224 real_t divy = 1.0 / dir.y; 225 real_t divz = 1.0 / dir.z; 226 227 Vector3 upbound = position + size; 228 real_t tmin, tmax, tymin, tymax, tzmin, tzmax; 229 if (dir.x >= 0) { 230 tmin = (position.x - from.x) * divx; 231 tmax = (upbound.x - from.x) * divx; 232 } else { 233 tmin = (upbound.x - from.x) * divx; 234 tmax = (position.x - from.x) * divx; 235 } 236 if (dir.y >= 0) { 237 tymin = (position.y - from.y) * divy; 238 tymax = (upbound.y - from.y) * divy; 239 } else { 240 tymin = (upbound.y - from.y) * divy; 241 tymax = (position.y - from.y) * divy; 242 } 243 if ((tmin > tymax) || (tymin > tmax)) 244 return false; 245 if (tymin > tmin) 246 tmin = tymin; 247 if (tymax < tmax) 248 tmax = tymax; 249 if (dir.z >= 0) { 250 tzmin = (position.z - from.z) * divz; 251 tzmax = (upbound.z - from.z) * divz; 252 } else { 253 tzmin = (upbound.z - from.z) * divz; 254 tzmax = (position.z - from.z) * divz; 255 } 256 if ((tmin > tzmax) || (tzmin > tmax)) 257 return false; 258 if (tzmin > tmin) 259 tmin = tzmin; 260 if (tzmax < tmax) 261 tmax = tzmax; 262 return ((tmin < t1) && (tmax > t0)); 263 } 264 265 void growBy(real_t p_amount) { 266 position.x -= p_amount; 267 position.y -= p_amount; 268 position.z -= p_amount; 269 size.x += 2.0 * p_amount; 270 size.y += 2.0 * p_amount; 271 size.z += 2.0 * p_amount; 272 } 273 274 real_t getArea() const { 275 return size.x * size.y * size.z; 276 } 277 278 void mergeWith(in AABB p_aabb) { 279 Vector3 beg_1, beg_2; 280 Vector3 end_1, end_2; 281 Vector3 min, max; 282 283 beg_1 = position; 284 beg_2 = p_aabb.position; 285 end_1 = Vector3(size.x, size.y, size.z) + beg_1; 286 end_2 = Vector3(p_aabb.size.x, p_aabb.size.y, p_aabb.size.z) + beg_2; 287 288 min.x = (beg_1.x < beg_2.x) ? beg_1.x : beg_2.x; 289 min.y = (beg_1.y < beg_2.y) ? beg_1.y : beg_2.y; 290 min.z = (beg_1.z < beg_2.z) ? beg_1.z : beg_2.z; 291 292 max.x = (end_1.x > end_2.x) ? end_1.x : end_2.x; 293 max.y = (end_1.y > end_2.y) ? end_1.y : end_2.y; 294 max.z = (end_1.z > end_2.z) ? end_1.z : end_2.z; 295 296 position = min; 297 size = max - min; 298 } 299 300 AABB intersection(in AABB p_aabb) const { 301 Vector3 src_min = position; 302 Vector3 src_max = position + size; 303 Vector3 dst_min = p_aabb.position; 304 Vector3 dst_max = p_aabb.position + p_aabb.size; 305 306 Vector3 min, max; 307 308 if (src_min.x > dst_max.x || src_max.x < dst_min.x) 309 return AABB(); 310 else { 311 min.x = (src_min.x > dst_min.x) ? src_min.x : dst_min.x; 312 max.x = (src_max.x < dst_max.x) ? src_max.x : dst_max.x; 313 } 314 315 if (src_min.y > dst_max.y || src_max.y < dst_min.y) 316 return AABB(); 317 else { 318 min.y = (src_min.y > dst_min.y) ? src_min.y : dst_min.y; 319 max.y = (src_max.y < dst_max.y) ? src_max.y : dst_max.y; 320 } 321 322 if (src_min.z > dst_max.z || src_max.z < dst_min.z) 323 return AABB(); 324 else { 325 min.z = (src_min.z > dst_min.z) ? src_min.z : dst_min.z; 326 max.z = (src_max.z < dst_max.z) ? src_max.z : dst_max.z; 327 } 328 329 return AABB(min, max - min); 330 } 331 332 bool intersectsRay(in Vector3 p_from, in Vector3 p_dir, Vector3* r_clip = null, Vector3* r_normal = null) const { 333 Vector3 c1, c2; 334 Vector3 end = position + size; 335 real_t near = -1e20; 336 real_t far = 1e20; 337 int axis = 0; 338 339 for (int i = 0; i < 3; i++) { 340 if (p_dir[i] == 0) { 341 if ((p_from[i] < position[i]) || (p_from[i] > end[i])) { 342 return false; 343 } 344 } else { // ray not parallel to planes in this direction 345 c1[i] = (position[i] - p_from[i]) / p_dir[i]; 346 c2[i] = (end[i] - p_from[i]) / p_dir[i]; 347 348 if (c1[i] > c2[i]) { 349 swap(c1, c2); 350 } 351 if (c1[i] > near) { 352 near = c1[i]; 353 axis = i; 354 } 355 if (c2[i] < far) { 356 far = c2[i]; 357 } 358 if ((near > far) || (far < 0)) { 359 return false; 360 } 361 } 362 } 363 if (r_clip) 364 *r_clip = c1; 365 if (r_normal) { 366 *r_normal = Vector3(); 367 (*r_normal)[axis] = p_dir[axis] ? -1 : 1; 368 } 369 return true; 370 } 371 372 bool intersectsSegment(in Vector3 p_from, in Vector3 p_to, Vector3* r_clip = null, Vector3* r_normal = null) const { 373 real_t min = 0, max = 1; 374 int axis = 0; 375 real_t sign = 0; 376 377 for (int i = 0; i < 3; i++) { 378 real_t seg_from = p_from[i]; 379 real_t seg_to = p_to[i]; 380 real_t box_begin = position[i]; 381 real_t box_end = box_begin + size[i]; 382 real_t cmin, cmax; 383 real_t csign; 384 385 if (seg_from < seg_to) { 386 if (seg_from > box_end || seg_to < box_begin) 387 return false; 388 real_t length = seg_to - seg_from; 389 cmin = (seg_from < box_begin) ? ((box_begin - seg_from) / length) : 0; 390 cmax = (seg_to > box_end) ? ((box_end - seg_from) / length) : 1; 391 csign = -1.0; 392 } else { 393 if (seg_to > box_end || seg_from < box_begin) 394 return false; 395 real_t length = seg_to - seg_from; 396 cmin = (seg_from > box_end) ? (box_end - seg_from) / length : 0; 397 cmax = (seg_to < box_begin) ? (box_begin - seg_from) / length : 1; 398 csign = 1.0; 399 } 400 401 if (cmin > min) { 402 min = cmin; 403 axis = i; 404 sign = csign; 405 } 406 if (cmax < max) 407 max = cmax; 408 if (max < min) 409 return false; 410 } 411 412 Vector3 rel = p_to - p_from; 413 414 if (r_normal) { 415 Vector3 normal; 416 normal[axis] = sign; 417 *r_normal = normal; 418 } 419 420 if (r_clip) 421 *r_clip = p_from + rel * min; 422 423 return true; 424 } 425 426 bool intersectsPlane(in Plane p_plane) const { 427 Vector3[8] points = [ 428 Vector3(position.x, position.y, position.z), 429 Vector3(position.x, position.y, position.z + size.z), 430 Vector3(position.x, position.y + size.y, position.z), 431 Vector3(position.x, position.y + size.y, position.z + size.z), 432 Vector3(position.x + size.x, position.y, position.z), 433 Vector3(position.x + size.x, position.y, position.z + size.z), 434 Vector3(position.x + size.x, position.y + size.y, position.z), 435 Vector3(position.x + size.x, position.y + size.y, position.z + size.z), 436 ]; 437 438 bool over = false; 439 bool under = false; 440 441 for (int i = 0; i < 8; i++) { 442 if (p_plane.distanceTo(points[i]) > 0) 443 over = true; 444 else 445 under = true; 446 } 447 return under && over; 448 } 449 450 Vector3 getLongestAxis() const { 451 Vector3 axis = Vector3(1, 0, 0); 452 real_t max_size = size.x; 453 454 if (size.y > max_size) { 455 axis = Vector3(0, 1, 0); 456 max_size = size.y; 457 } 458 459 if (size.z > max_size) { 460 axis = Vector3(0, 0, 1); 461 max_size = size.z; 462 } 463 464 return axis; 465 } 466 467 int getLongestAxisIndex() const { 468 int axis = 0; 469 real_t max_size = size.x; 470 471 if (size.y > max_size) { 472 axis = 1; 473 max_size = size.y; 474 } 475 476 if (size.z > max_size) { 477 axis = 2; 478 max_size = size.z; 479 } 480 481 return axis; 482 } 483 484 Vector3 getShortestAxis() const { 485 Vector3 axis = Vector3(1, 0, 0); 486 real_t max_size = size.x; 487 488 if (size.y < max_size) { 489 axis = Vector3(0, 1, 0); 490 max_size = size.y; 491 } 492 493 if (size.z < max_size) { 494 axis = Vector3(0, 0, 1); 495 max_size = size.z; 496 } 497 498 return axis; 499 } 500 501 int getShortestAxisIndex() const { 502 int axis = 0; 503 real_t max_size = size.x; 504 505 if (size.y < max_size) { 506 axis = 1; 507 max_size = size.y; 508 } 509 510 if (size.z < max_size) { 511 axis = 2; 512 max_size = size.z; 513 } 514 515 return axis; 516 } 517 518 AABB merge(in AABB p_with) const { 519 AABB aabb = this; 520 aabb.mergeWith(p_with); 521 return aabb; 522 } 523 524 AABB expand(in Vector3 p_vector) const { 525 AABB aabb = this; 526 aabb.expandTo(p_vector); 527 return aabb; 528 529 } 530 531 AABB grow(real_t p_by) const { 532 AABB aabb = this; 533 aabb.growBy(p_by); 534 return aabb; 535 } 536 537 void getEdge(int p_edge, out Vector3 r_from, out Vector3 r_to) const { 538 ///ERR_FAIL_INDEX(p_edge,12); 539 switch (p_edge) { 540 case 0: { 541 r_from = Vector3(position.x + size.x, position.y, position.z); 542 r_to = Vector3(position.x, position.y, position.z); 543 } 544 break; 545 case 1: { 546 r_from = Vector3(position.x + size.x, position.y, position.z + size.z); 547 r_to = Vector3(position.x + size.x, position.y, position.z); 548 } 549 break; 550 case 2: { 551 r_from = Vector3(position.x, position.y, position.z + size.z); 552 r_to = Vector3(position.x + size.x, position.y, position.z + size.z); 553 } 554 break; 555 case 3: { 556 r_from = Vector3(position.x, position.y, position.z); 557 r_to = Vector3(position.x, position.y, position.z + size.z); 558 } 559 break; 560 case 4: { 561 r_from = Vector3(position.x, position.y + size.y, position.z); 562 r_to = Vector3(position.x + size.x, position.y + size.y, position.z); 563 } 564 break; 565 case 5: { 566 r_from = Vector3(position.x + size.x, position.y + size.y, position.z); 567 r_to = Vector3(position.x + size.x, position.y + size.y, position.z + size.z); 568 } 569 break; 570 case 6: { 571 r_from = Vector3(position.x + size.x, position.y + size.y, position.z + size.z); 572 r_to = Vector3(position.x, position.y + size.y, position.z + size.z); 573 } 574 break; 575 case 7: { 576 r_from = Vector3(position.x, position.y + size.y, position.z + size.z); 577 r_to = Vector3(position.x, position.y + size.y, position.z); 578 } 579 break; 580 case 8: { 581 r_from = Vector3(position.x, position.y, position.z + size.z); 582 r_to = Vector3(position.x, position.y + size.y, position.z + size.z); 583 } 584 break; 585 case 9: { 586 r_from = Vector3(position.x, position.y, position.z); 587 r_to = Vector3(position.x, position.y + size.y, position.z); 588 } 589 break; 590 case 10: { 591 r_from = Vector3(position.x + size.x, position.y, position.z); 592 r_to = Vector3(position.x + size.x, position.y + size.y, position.z); 593 } 594 break; 595 case 11: { 596 r_from = Vector3(position.x + size.x, position.y, position.z + size.z); 597 r_to = Vector3(position.x + size.x, position.y + size.y, position.z + size.z); 598 } 599 break; 600 default: 601 assert(0); 602 } 603 } 604 }