1/**************************************************************************/
2/* godot_collision_solver_3d.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 "godot_collision_solver_3d.h"
32
33#include "godot_collision_solver_3d_sat.h"
34#include "godot_soft_body_3d.h"
35
36#include "gjk_epa.h"
37
38#define collision_solver sat_calculate_penetration
39//#define collision_solver gjk_epa_calculate_penetration
40
41bool GodotCollisionSolver3D::solve_static_world_boundary(const GodotShape3D *p_shape_A, const Transform3D &p_transform_A, const GodotShape3D *p_shape_B, const Transform3D &p_transform_B, CallbackResult p_result_callback, void *p_userdata, bool p_swap_result, real_t p_margin) {
42 const GodotWorldBoundaryShape3D *world_boundary = static_cast<const GodotWorldBoundaryShape3D *>(p_shape_A);
43 if (p_shape_B->get_type() == PhysicsServer3D::SHAPE_WORLD_BOUNDARY) {
44 return false;
45 }
46 Plane p = p_transform_A.xform(world_boundary->get_plane());
47
48 static const int max_supports = 16;
49 Vector3 supports[max_supports];
50 int support_count;
51 GodotShape3D::FeatureType support_type = GodotShape3D::FeatureType::FEATURE_POINT;
52 p_shape_B->get_supports(p_transform_B.basis.xform_inv(-p.normal).normalized(), max_supports, supports, support_count, support_type);
53
54 if (support_type == GodotShape3D::FEATURE_CIRCLE) {
55 ERR_FAIL_COND_V(support_count != 3, false);
56
57 Vector3 circle_pos = supports[0];
58 Vector3 circle_axis_1 = supports[1] - circle_pos;
59 Vector3 circle_axis_2 = supports[2] - circle_pos;
60
61 // Use 3 equidistant points on the circle.
62 for (int i = 0; i < 3; ++i) {
63 Vector3 vertex_pos = circle_pos;
64 vertex_pos += circle_axis_1 * Math::cos(2.0 * Math_PI * i / 3.0);
65 vertex_pos += circle_axis_2 * Math::sin(2.0 * Math_PI * i / 3.0);
66 supports[i] = vertex_pos;
67 }
68 }
69
70 bool found = false;
71
72 for (int i = 0; i < support_count; i++) {
73 supports[i] += p_margin * supports[i].normalized();
74 supports[i] = p_transform_B.xform(supports[i]);
75 if (p.distance_to(supports[i]) >= 0) {
76 continue;
77 }
78 found = true;
79
80 Vector3 support_A = p.project(supports[i]);
81
82 if (p_result_callback) {
83 if (p_swap_result) {
84 Vector3 normal = (support_A - supports[i]).normalized();
85 p_result_callback(supports[i], 0, support_A, 0, normal, p_userdata);
86 } else {
87 Vector3 normal = (supports[i] - support_A).normalized();
88 p_result_callback(support_A, 0, supports[i], 0, normal, p_userdata);
89 }
90 }
91 }
92
93 return found;
94}
95
96bool GodotCollisionSolver3D::solve_separation_ray(const GodotShape3D *p_shape_A, const Transform3D &p_transform_A, const GodotShape3D *p_shape_B, const Transform3D &p_transform_B, CallbackResult p_result_callback, void *p_userdata, bool p_swap_result, real_t p_margin) {
97 const GodotSeparationRayShape3D *ray = static_cast<const GodotSeparationRayShape3D *>(p_shape_A);
98
99 Vector3 from = p_transform_A.origin;
100 Vector3 to = from + p_transform_A.basis.get_column(2) * (ray->get_length() + p_margin);
101 Vector3 support_A = to;
102
103 Transform3D ai = p_transform_B.affine_inverse();
104
105 from = ai.xform(from);
106 to = ai.xform(to);
107
108 Vector3 p, n;
109 int fi = -1;
110 if (!p_shape_B->intersect_segment(from, to, p, n, fi, true)) {
111 return false;
112 }
113
114 // Discard contacts when the ray is fully contained inside the shape.
115 if (n == Vector3()) {
116 return false;
117 }
118
119 // Discard contacts in the wrong direction.
120 if (n.dot(from - to) < CMP_EPSILON) {
121 return false;
122 }
123
124 Vector3 support_B = p_transform_B.xform(p);
125 if (ray->get_slide_on_slope()) {
126 Vector3 global_n = ai.basis.xform_inv(n).normalized();
127 support_B = support_A + (support_B - support_A).length() * global_n;
128 }
129
130 if (p_result_callback) {
131 Vector3 normal = (support_B - support_A).normalized();
132 if (p_swap_result) {
133 p_result_callback(support_B, 0, support_A, 0, -normal, p_userdata);
134 } else {
135 p_result_callback(support_A, 0, support_B, 0, normal, p_userdata);
136 }
137 }
138 return true;
139}
140
141struct _SoftBodyContactCollisionInfo {
142 int node_index = 0;
143 GodotCollisionSolver3D::CallbackResult result_callback = nullptr;
144 void *userdata = nullptr;
145 bool swap_result = false;
146 int contact_count = 0;
147};
148
149void GodotCollisionSolver3D::soft_body_contact_callback(const Vector3 &p_point_A, int p_index_A, const Vector3 &p_point_B, int p_index_B, const Vector3 &normal, void *p_userdata) {
150 _SoftBodyContactCollisionInfo &cinfo = *(static_cast<_SoftBodyContactCollisionInfo *>(p_userdata));
151
152 ++cinfo.contact_count;
153
154 if (!cinfo.result_callback) {
155 return;
156 }
157
158 if (cinfo.swap_result) {
159 cinfo.result_callback(p_point_B, cinfo.node_index, p_point_A, p_index_A, -normal, cinfo.userdata);
160 } else {
161 cinfo.result_callback(p_point_A, p_index_A, p_point_B, cinfo.node_index, normal, cinfo.userdata);
162 }
163}
164
165struct _SoftBodyQueryInfo {
166 GodotSoftBody3D *soft_body = nullptr;
167 const GodotShape3D *shape_A = nullptr;
168 const GodotShape3D *shape_B = nullptr;
169 Transform3D transform_A;
170 Transform3D node_transform;
171 _SoftBodyContactCollisionInfo contact_info;
172#ifdef DEBUG_ENABLED
173 int node_query_count = 0;
174 int convex_query_count = 0;
175#endif
176};
177
178bool GodotCollisionSolver3D::soft_body_query_callback(uint32_t p_node_index, void *p_userdata) {
179 _SoftBodyQueryInfo &query_cinfo = *(static_cast<_SoftBodyQueryInfo *>(p_userdata));
180
181 Vector3 node_position = query_cinfo.soft_body->get_node_position(p_node_index);
182
183 Transform3D transform_B;
184 transform_B.origin = query_cinfo.node_transform.xform(node_position);
185
186 query_cinfo.contact_info.node_index = p_node_index;
187 bool collided = solve_static(query_cinfo.shape_A, query_cinfo.transform_A, query_cinfo.shape_B, transform_B, soft_body_contact_callback, &query_cinfo.contact_info);
188
189#ifdef DEBUG_ENABLED
190 ++query_cinfo.node_query_count;
191#endif
192
193 // Stop at first collision if contacts are not needed.
194 return (collided && !query_cinfo.contact_info.result_callback);
195}
196
197bool GodotCollisionSolver3D::soft_body_concave_callback(void *p_userdata, GodotShape3D *p_convex) {
198 _SoftBodyQueryInfo &query_cinfo = *(static_cast<_SoftBodyQueryInfo *>(p_userdata));
199
200 query_cinfo.shape_A = p_convex;
201
202 // Calculate AABB for internal soft body query (in world space).
203 AABB shape_aabb;
204 for (int i = 0; i < 3; i++) {
205 Vector3 axis;
206 axis[i] = 1.0;
207
208 real_t smin, smax;
209 p_convex->project_range(axis, query_cinfo.transform_A, smin, smax);
210
211 shape_aabb.position[i] = smin;
212 shape_aabb.size[i] = smax - smin;
213 }
214
215 shape_aabb.grow_by(query_cinfo.soft_body->get_collision_margin());
216
217 query_cinfo.soft_body->query_aabb(shape_aabb, soft_body_query_callback, &query_cinfo);
218
219 bool collided = (query_cinfo.contact_info.contact_count > 0);
220
221#ifdef DEBUG_ENABLED
222 ++query_cinfo.convex_query_count;
223#endif
224
225 // Stop at first collision if contacts are not needed.
226 return (collided && !query_cinfo.contact_info.result_callback);
227}
228
229bool GodotCollisionSolver3D::solve_soft_body(const GodotShape3D *p_shape_A, const Transform3D &p_transform_A, const GodotShape3D *p_shape_B, const Transform3D &p_transform_B, CallbackResult p_result_callback, void *p_userdata, bool p_swap_result) {
230 const GodotSoftBodyShape3D *soft_body_shape_B = static_cast<const GodotSoftBodyShape3D *>(p_shape_B);
231
232 GodotSoftBody3D *soft_body = soft_body_shape_B->get_soft_body();
233 const Transform3D &world_to_local = soft_body->get_inv_transform();
234
235 const real_t collision_margin = soft_body->get_collision_margin();
236
237 GodotSphereShape3D sphere_shape;
238 sphere_shape.set_data(collision_margin);
239
240 _SoftBodyQueryInfo query_cinfo;
241 query_cinfo.contact_info.result_callback = p_result_callback;
242 query_cinfo.contact_info.userdata = p_userdata;
243 query_cinfo.contact_info.swap_result = p_swap_result;
244 query_cinfo.soft_body = soft_body;
245 query_cinfo.node_transform = p_transform_B * world_to_local;
246 query_cinfo.shape_A = p_shape_A;
247 query_cinfo.transform_A = p_transform_A;
248 query_cinfo.shape_B = &sphere_shape;
249
250 if (p_shape_A->is_concave()) {
251 // In case of concave shape, query convex shapes first.
252 const GodotConcaveShape3D *concave_shape_A = static_cast<const GodotConcaveShape3D *>(p_shape_A);
253
254 AABB soft_body_aabb = soft_body->get_bounds();
255 soft_body_aabb.grow_by(collision_margin);
256
257 // Calculate AABB for internal concave shape query (in local space).
258 AABB local_aabb;
259 for (int i = 0; i < 3; i++) {
260 Vector3 axis(p_transform_A.basis.get_column(i));
261 real_t axis_scale = 1.0 / axis.length();
262
263 real_t smin = soft_body_aabb.position[i];
264 real_t smax = smin + soft_body_aabb.size[i];
265
266 smin *= axis_scale;
267 smax *= axis_scale;
268
269 local_aabb.position[i] = smin;
270 local_aabb.size[i] = smax - smin;
271 }
272
273 concave_shape_A->cull(local_aabb, soft_body_concave_callback, &query_cinfo, true);
274 } else {
275 AABB shape_aabb = p_transform_A.xform(p_shape_A->get_aabb());
276 shape_aabb.grow_by(collision_margin);
277
278 soft_body->query_aabb(shape_aabb, soft_body_query_callback, &query_cinfo);
279 }
280
281 return (query_cinfo.contact_info.contact_count > 0);
282}
283
284struct _ConcaveCollisionInfo {
285 const Transform3D *transform_A = nullptr;
286 const GodotShape3D *shape_A = nullptr;
287 const Transform3D *transform_B = nullptr;
288 GodotCollisionSolver3D::CallbackResult result_callback = nullptr;
289 void *userdata = nullptr;
290 bool swap_result = false;
291 bool collided = false;
292 int aabb_tests = 0;
293 int collisions = 0;
294 bool tested = false;
295 real_t margin_A = 0.0f;
296 real_t margin_B = 0.0f;
297 Vector3 close_A;
298 Vector3 close_B;
299};
300
301bool GodotCollisionSolver3D::concave_callback(void *p_userdata, GodotShape3D *p_convex) {
302 _ConcaveCollisionInfo &cinfo = *(static_cast<_ConcaveCollisionInfo *>(p_userdata));
303 cinfo.aabb_tests++;
304
305 bool collided = collision_solver(cinfo.shape_A, *cinfo.transform_A, p_convex, *cinfo.transform_B, cinfo.result_callback, cinfo.userdata, cinfo.swap_result, nullptr, cinfo.margin_A, cinfo.margin_B);
306 if (!collided) {
307 return false;
308 }
309
310 cinfo.collided = true;
311 cinfo.collisions++;
312
313 // Stop at first collision if contacts are not needed.
314 return !cinfo.result_callback;
315}
316
317bool GodotCollisionSolver3D::solve_concave(const GodotShape3D *p_shape_A, const Transform3D &p_transform_A, const GodotShape3D *p_shape_B, const Transform3D &p_transform_B, CallbackResult p_result_callback, void *p_userdata, bool p_swap_result, real_t p_margin_A, real_t p_margin_B) {
318 const GodotConcaveShape3D *concave_B = static_cast<const GodotConcaveShape3D *>(p_shape_B);
319
320 _ConcaveCollisionInfo cinfo;
321 cinfo.transform_A = &p_transform_A;
322 cinfo.shape_A = p_shape_A;
323 cinfo.transform_B = &p_transform_B;
324 cinfo.result_callback = p_result_callback;
325 cinfo.userdata = p_userdata;
326 cinfo.swap_result = p_swap_result;
327 cinfo.collided = false;
328 cinfo.collisions = 0;
329 cinfo.margin_A = p_margin_A;
330 cinfo.margin_B = p_margin_B;
331
332 cinfo.aabb_tests = 0;
333
334 Transform3D rel_transform = p_transform_A;
335 rel_transform.origin -= p_transform_B.origin;
336
337 //quickly compute a local AABB
338
339 AABB local_aabb;
340 for (int i = 0; i < 3; i++) {
341 Vector3 axis(p_transform_B.basis.get_column(i));
342 real_t axis_scale = 1.0 / axis.length();
343 axis *= axis_scale;
344
345 real_t smin = 0.0, smax = 0.0;
346 p_shape_A->project_range(axis, rel_transform, smin, smax);
347 smin -= p_margin_A;
348 smax += p_margin_A;
349 smin *= axis_scale;
350 smax *= axis_scale;
351
352 local_aabb.position[i] = smin;
353 local_aabb.size[i] = smax - smin;
354 }
355
356 concave_B->cull(local_aabb, concave_callback, &cinfo, false);
357
358 return cinfo.collided;
359}
360
361bool GodotCollisionSolver3D::solve_static(const GodotShape3D *p_shape_A, const Transform3D &p_transform_A, const GodotShape3D *p_shape_B, const Transform3D &p_transform_B, CallbackResult p_result_callback, void *p_userdata, Vector3 *r_sep_axis, real_t p_margin_A, real_t p_margin_B) {
362 PhysicsServer3D::ShapeType type_A = p_shape_A->get_type();
363 PhysicsServer3D::ShapeType type_B = p_shape_B->get_type();
364 bool concave_A = p_shape_A->is_concave();
365 bool concave_B = p_shape_B->is_concave();
366
367 bool swap = false;
368
369 if (type_A > type_B) {
370 SWAP(type_A, type_B);
371 SWAP(concave_A, concave_B);
372 swap = true;
373 }
374
375 if (type_A == PhysicsServer3D::SHAPE_WORLD_BOUNDARY) {
376 if (type_B == PhysicsServer3D::SHAPE_WORLD_BOUNDARY) {
377 WARN_PRINT_ONCE("Collisions between world boundaries are not supported.");
378 return false;
379 }
380 if (type_B == PhysicsServer3D::SHAPE_SEPARATION_RAY) {
381 WARN_PRINT_ONCE("Collisions between world boundaries and rays are not supported.");
382 return false;
383 }
384 if (type_B == PhysicsServer3D::SHAPE_SOFT_BODY) {
385 WARN_PRINT_ONCE("Collisions between world boundaries and soft bodies are not supported.");
386 return false;
387 }
388
389 if (swap) {
390 return solve_static_world_boundary(p_shape_B, p_transform_B, p_shape_A, p_transform_A, p_result_callback, p_userdata, true, p_margin_A);
391 } else {
392 return solve_static_world_boundary(p_shape_A, p_transform_A, p_shape_B, p_transform_B, p_result_callback, p_userdata, false, p_margin_B);
393 }
394
395 } else if (type_A == PhysicsServer3D::SHAPE_SEPARATION_RAY) {
396 if (type_B == PhysicsServer3D::SHAPE_SEPARATION_RAY) {
397 WARN_PRINT_ONCE("Collisions between rays are not supported.");
398 return false;
399 }
400
401 if (swap) {
402 return solve_separation_ray(p_shape_B, p_transform_B, p_shape_A, p_transform_A, p_result_callback, p_userdata, true, p_margin_B);
403 } else {
404 return solve_separation_ray(p_shape_A, p_transform_A, p_shape_B, p_transform_B, p_result_callback, p_userdata, false, p_margin_A);
405 }
406
407 } else if (type_B == PhysicsServer3D::SHAPE_SOFT_BODY) {
408 if (type_A == PhysicsServer3D::SHAPE_SOFT_BODY) {
409 WARN_PRINT_ONCE("Collisions between soft bodies are not supported.");
410 return false;
411 }
412
413 if (swap) {
414 return solve_soft_body(p_shape_B, p_transform_B, p_shape_A, p_transform_A, p_result_callback, p_userdata, true);
415 } else {
416 return solve_soft_body(p_shape_A, p_transform_A, p_shape_B, p_transform_B, p_result_callback, p_userdata, false);
417 }
418
419 } else if (concave_B) {
420 if (concave_A) {
421 WARN_PRINT_ONCE("Collisions between two concave shapes are not supported.");
422 return false;
423 }
424
425 if (!swap) {
426 return solve_concave(p_shape_A, p_transform_A, p_shape_B, p_transform_B, p_result_callback, p_userdata, false, p_margin_A, p_margin_B);
427 } else {
428 return solve_concave(p_shape_B, p_transform_B, p_shape_A, p_transform_A, p_result_callback, p_userdata, true, p_margin_A, p_margin_B);
429 }
430
431 } else {
432 return collision_solver(p_shape_A, p_transform_A, p_shape_B, p_transform_B, p_result_callback, p_userdata, false, r_sep_axis, p_margin_A, p_margin_B);
433 }
434}
435
436bool GodotCollisionSolver3D::concave_distance_callback(void *p_userdata, GodotShape3D *p_convex) {
437 _ConcaveCollisionInfo &cinfo = *(static_cast<_ConcaveCollisionInfo *>(p_userdata));
438 cinfo.aabb_tests++;
439
440 Vector3 close_A, close_B;
441 cinfo.collided = !gjk_epa_calculate_distance(cinfo.shape_A, *cinfo.transform_A, p_convex, *cinfo.transform_B, close_A, close_B);
442
443 if (cinfo.collided) {
444 // No need to process any more result.
445 return true;
446 }
447
448 if (!cinfo.tested || close_A.distance_squared_to(close_B) < cinfo.close_A.distance_squared_to(cinfo.close_B)) {
449 cinfo.close_A = close_A;
450 cinfo.close_B = close_B;
451 cinfo.tested = true;
452 }
453
454 cinfo.collisions++;
455 return false;
456}
457
458bool GodotCollisionSolver3D::solve_distance_world_boundary(const GodotShape3D *p_shape_A, const Transform3D &p_transform_A, const GodotShape3D *p_shape_B, const Transform3D &p_transform_B, Vector3 &r_point_A, Vector3 &r_point_B) {
459 const GodotWorldBoundaryShape3D *world_boundary = static_cast<const GodotWorldBoundaryShape3D *>(p_shape_A);
460 if (p_shape_B->get_type() == PhysicsServer3D::SHAPE_WORLD_BOUNDARY) {
461 return false;
462 }
463 Plane p = p_transform_A.xform(world_boundary->get_plane());
464
465 static const int max_supports = 16;
466 Vector3 supports[max_supports];
467 int support_count;
468 GodotShape3D::FeatureType support_type;
469 Vector3 support_direction = p_transform_B.basis.xform_inv(-p.normal).normalized();
470
471 p_shape_B->get_supports(support_direction, max_supports, supports, support_count, support_type);
472
473 if (support_count == 0) { // This is a poor man's way to detect shapes that don't implement get_supports, such as GodotMotionShape3D.
474 Vector3 support_B = p_transform_B.xform(p_shape_B->get_support(support_direction));
475 r_point_A = p.project(support_B);
476 r_point_B = support_B;
477 bool collided = p.distance_to(support_B) <= 0;
478 return collided;
479 }
480
481 if (support_type == GodotShape3D::FEATURE_CIRCLE) {
482 ERR_FAIL_COND_V(support_count != 3, false);
483
484 Vector3 circle_pos = supports[0];
485 Vector3 circle_axis_1 = supports[1] - circle_pos;
486 Vector3 circle_axis_2 = supports[2] - circle_pos;
487
488 // Use 3 equidistant points on the circle.
489 for (int i = 0; i < 3; ++i) {
490 Vector3 vertex_pos = circle_pos;
491 vertex_pos += circle_axis_1 * Math::cos(2.0 * Math_PI * i / 3.0);
492 vertex_pos += circle_axis_2 * Math::sin(2.0 * Math_PI * i / 3.0);
493 supports[i] = vertex_pos;
494 }
495 }
496
497 bool collided = false;
498 Vector3 closest;
499 real_t closest_d = 0;
500
501 for (int i = 0; i < support_count; i++) {
502 supports[i] = p_transform_B.xform(supports[i]);
503 real_t d = p.distance_to(supports[i]);
504 if (i == 0 || d < closest_d) {
505 closest = supports[i];
506 closest_d = d;
507 if (d <= 0) {
508 collided = true;
509 }
510 }
511 }
512
513 r_point_A = p.project(closest);
514 r_point_B = closest;
515
516 return collided;
517}
518
519bool GodotCollisionSolver3D::solve_distance(const GodotShape3D *p_shape_A, const Transform3D &p_transform_A, const GodotShape3D *p_shape_B, const Transform3D &p_transform_B, Vector3 &r_point_A, Vector3 &r_point_B, const AABB &p_concave_hint, Vector3 *r_sep_axis) {
520 if (p_shape_B->get_type() == PhysicsServer3D::SHAPE_WORLD_BOUNDARY) {
521 Vector3 a, b;
522 bool col = solve_distance_world_boundary(p_shape_B, p_transform_B, p_shape_A, p_transform_A, a, b);
523 r_point_A = b;
524 r_point_B = a;
525 return !col;
526
527 } else if (p_shape_B->is_concave()) {
528 if (p_shape_A->is_concave()) {
529 return false;
530 }
531
532 const GodotConcaveShape3D *concave_B = static_cast<const GodotConcaveShape3D *>(p_shape_B);
533
534 _ConcaveCollisionInfo cinfo;
535 cinfo.transform_A = &p_transform_A;
536 cinfo.shape_A = p_shape_A;
537 cinfo.transform_B = &p_transform_B;
538 cinfo.result_callback = nullptr;
539 cinfo.userdata = nullptr;
540 cinfo.swap_result = false;
541 cinfo.collided = false;
542 cinfo.collisions = 0;
543 cinfo.aabb_tests = 0;
544 cinfo.tested = false;
545
546 Transform3D rel_transform = p_transform_A;
547 rel_transform.origin -= p_transform_B.origin;
548
549 //quickly compute a local AABB
550
551 bool use_cc_hint = p_concave_hint != AABB();
552 AABB cc_hint_aabb;
553 if (use_cc_hint) {
554 cc_hint_aabb = p_concave_hint;
555 cc_hint_aabb.position -= p_transform_B.origin;
556 }
557
558 AABB local_aabb;
559 for (int i = 0; i < 3; i++) {
560 Vector3 axis(p_transform_B.basis.get_column(i));
561 real_t axis_scale = ((real_t)1.0) / axis.length();
562 axis *= axis_scale;
563
564 real_t smin, smax;
565
566 if (use_cc_hint) {
567 cc_hint_aabb.project_range_in_plane(Plane(axis), smin, smax);
568 } else {
569 p_shape_A->project_range(axis, rel_transform, smin, smax);
570 }
571
572 smin *= axis_scale;
573 smax *= axis_scale;
574
575 local_aabb.position[i] = smin;
576 local_aabb.size[i] = smax - smin;
577 }
578
579 concave_B->cull(local_aabb, concave_distance_callback, &cinfo, false);
580 if (!cinfo.collided) {
581 r_point_A = cinfo.close_A;
582 r_point_B = cinfo.close_B;
583 }
584
585 return !cinfo.collided;
586 } else {
587 return gjk_epa_calculate_distance(p_shape_A, p_transform_A, p_shape_B, p_transform_B, r_point_A, r_point_B); //should pass sepaxis..
588 }
589}
590