1/**************************************************************************/
2/* godot_shape_3d.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 GODOT_SHAPE_3D_H
32#define GODOT_SHAPE_3D_H
33
34#include "core/math/geometry_3d.h"
35#include "core/templates/local_vector.h"
36#include "servers/physics_server_3d.h"
37
38class GodotShape3D;
39
40class GodotShapeOwner3D {
41public:
42 virtual void _shape_changed() = 0;
43 virtual void remove_shape(GodotShape3D *p_shape) = 0;
44
45 virtual ~GodotShapeOwner3D() {}
46};
47
48class GodotShape3D {
49 RID self;
50 AABB aabb;
51 bool configured = false;
52 real_t custom_bias = 0.0;
53
54 HashMap<GodotShapeOwner3D *, int> owners;
55
56protected:
57 void configure(const AABB &p_aabb);
58
59public:
60 enum FeatureType {
61 FEATURE_POINT,
62 FEATURE_EDGE,
63 FEATURE_FACE,
64 FEATURE_CIRCLE,
65 };
66
67 virtual real_t get_volume() const { return aabb.get_volume(); }
68
69 _FORCE_INLINE_ void set_self(const RID &p_self) { self = p_self; }
70 _FORCE_INLINE_ RID get_self() const { return self; }
71
72 virtual PhysicsServer3D::ShapeType get_type() const = 0;
73
74 _FORCE_INLINE_ const AABB &get_aabb() const { return aabb; }
75 _FORCE_INLINE_ bool is_configured() const { return configured; }
76
77 virtual bool is_concave() const { return false; }
78
79 virtual void project_range(const Vector3 &p_normal, const Transform3D &p_transform, real_t &r_min, real_t &r_max) const = 0;
80 virtual Vector3 get_support(const Vector3 &p_normal) const;
81 virtual void get_supports(const Vector3 &p_normal, int p_max, Vector3 *r_supports, int &r_amount, FeatureType &r_type) const = 0;
82 virtual Vector3 get_closest_point_to(const Vector3 &p_point) const = 0;
83 virtual bool intersect_segment(const Vector3 &p_begin, const Vector3 &p_end, Vector3 &r_point, Vector3 &r_normal, int &r_face_index, bool p_hit_back_faces) const = 0;
84 virtual bool intersect_point(const Vector3 &p_point) const = 0;
85 virtual Vector3 get_moment_of_inertia(real_t p_mass) const = 0;
86
87 virtual void set_data(const Variant &p_data) = 0;
88 virtual Variant get_data() const = 0;
89
90 _FORCE_INLINE_ void set_custom_bias(real_t p_bias) { custom_bias = p_bias; }
91 _FORCE_INLINE_ real_t get_custom_bias() const { return custom_bias; }
92
93 void add_owner(GodotShapeOwner3D *p_owner);
94 void remove_owner(GodotShapeOwner3D *p_owner);
95 bool is_owner(GodotShapeOwner3D *p_owner) const;
96 const HashMap<GodotShapeOwner3D *, int> &get_owners() const;
97
98 GodotShape3D() {}
99 virtual ~GodotShape3D();
100};
101
102class GodotConcaveShape3D : public GodotShape3D {
103public:
104 virtual bool is_concave() const override { return true; }
105 virtual void get_supports(const Vector3 &p_normal, int p_max, Vector3 *r_supports, int &r_amount, FeatureType &r_type) const override { r_amount = 0; }
106
107 // Returns true to stop the query.
108 typedef bool (*QueryCallback)(void *p_userdata, GodotShape3D *p_convex);
109
110 virtual void cull(const AABB &p_local_aabb, QueryCallback p_callback, void *p_userdata, bool p_invert_backface_collision) const = 0;
111
112 GodotConcaveShape3D() {}
113};
114
115class GodotWorldBoundaryShape3D : public GodotShape3D {
116 Plane plane;
117
118 void _setup(const Plane &p_plane);
119
120public:
121 Plane get_plane() const;
122
123 virtual real_t get_volume() const override { return INFINITY; }
124 virtual PhysicsServer3D::ShapeType get_type() const override { return PhysicsServer3D::SHAPE_WORLD_BOUNDARY; }
125 virtual void project_range(const Vector3 &p_normal, const Transform3D &p_transform, real_t &r_min, real_t &r_max) const override;
126 virtual Vector3 get_support(const Vector3 &p_normal) const override;
127 virtual void get_supports(const Vector3 &p_normal, int p_max, Vector3 *r_supports, int &r_amount, FeatureType &r_type) const override { r_amount = 0; }
128
129 virtual bool intersect_segment(const Vector3 &p_begin, const Vector3 &p_end, Vector3 &r_result, Vector3 &r_normal, int &r_face_index, bool p_hit_back_faces) const override;
130 virtual bool intersect_point(const Vector3 &p_point) const override;
131 virtual Vector3 get_closest_point_to(const Vector3 &p_point) const override;
132 virtual Vector3 get_moment_of_inertia(real_t p_mass) const override;
133
134 virtual void set_data(const Variant &p_data) override;
135 virtual Variant get_data() const override;
136
137 GodotWorldBoundaryShape3D();
138};
139
140class GodotSeparationRayShape3D : public GodotShape3D {
141 real_t length = 1.0;
142 bool slide_on_slope = false;
143
144 void _setup(real_t p_length, bool p_slide_on_slope);
145
146public:
147 real_t get_length() const;
148 bool get_slide_on_slope() const;
149
150 virtual real_t get_volume() const override { return 0.0; }
151 virtual PhysicsServer3D::ShapeType get_type() const override { return PhysicsServer3D::SHAPE_SEPARATION_RAY; }
152 virtual void project_range(const Vector3 &p_normal, const Transform3D &p_transform, real_t &r_min, real_t &r_max) const override;
153 virtual Vector3 get_support(const Vector3 &p_normal) const override;
154 virtual void get_supports(const Vector3 &p_normal, int p_max, Vector3 *r_supports, int &r_amount, FeatureType &r_type) const override;
155
156 virtual bool intersect_segment(const Vector3 &p_begin, const Vector3 &p_end, Vector3 &r_result, Vector3 &r_normal, int &r_face_index, bool p_hit_back_faces) const override;
157 virtual bool intersect_point(const Vector3 &p_point) const override;
158 virtual Vector3 get_closest_point_to(const Vector3 &p_point) const override;
159
160 virtual Vector3 get_moment_of_inertia(real_t p_mass) const override;
161
162 virtual void set_data(const Variant &p_data) override;
163 virtual Variant get_data() const override;
164
165 GodotSeparationRayShape3D();
166};
167
168class GodotSphereShape3D : public GodotShape3D {
169 real_t radius = 0.0;
170
171 void _setup(real_t p_radius);
172
173public:
174 real_t get_radius() const;
175
176 virtual real_t get_volume() const override { return 4.0 / 3.0 * Math_PI * radius * radius * radius; }
177
178 virtual PhysicsServer3D::ShapeType get_type() const override { return PhysicsServer3D::SHAPE_SPHERE; }
179
180 virtual void project_range(const Vector3 &p_normal, const Transform3D &p_transform, real_t &r_min, real_t &r_max) const override;
181 virtual Vector3 get_support(const Vector3 &p_normal) const override;
182 virtual void get_supports(const Vector3 &p_normal, int p_max, Vector3 *r_supports, int &r_amount, FeatureType &r_type) const override;
183 virtual bool intersect_segment(const Vector3 &p_begin, const Vector3 &p_end, Vector3 &r_result, Vector3 &r_normal, int &r_face_index, bool p_hit_back_faces) const override;
184 virtual bool intersect_point(const Vector3 &p_point) const override;
185 virtual Vector3 get_closest_point_to(const Vector3 &p_point) const override;
186
187 virtual Vector3 get_moment_of_inertia(real_t p_mass) const override;
188
189 virtual void set_data(const Variant &p_data) override;
190 virtual Variant get_data() const override;
191
192 GodotSphereShape3D();
193};
194
195class GodotBoxShape3D : public GodotShape3D {
196 Vector3 half_extents;
197 void _setup(const Vector3 &p_half_extents);
198
199public:
200 _FORCE_INLINE_ Vector3 get_half_extents() const { return half_extents; }
201 virtual real_t get_volume() const override { return 8 * half_extents.x * half_extents.y * half_extents.z; }
202
203 virtual PhysicsServer3D::ShapeType get_type() const override { return PhysicsServer3D::SHAPE_BOX; }
204
205 virtual void project_range(const Vector3 &p_normal, const Transform3D &p_transform, real_t &r_min, real_t &r_max) const override;
206 virtual Vector3 get_support(const Vector3 &p_normal) const override;
207 virtual void get_supports(const Vector3 &p_normal, int p_max, Vector3 *r_supports, int &r_amount, FeatureType &r_type) const override;
208 virtual bool intersect_segment(const Vector3 &p_begin, const Vector3 &p_end, Vector3 &r_result, Vector3 &r_normal, int &r_face_index, bool p_hit_back_faces) const override;
209 virtual bool intersect_point(const Vector3 &p_point) const override;
210 virtual Vector3 get_closest_point_to(const Vector3 &p_point) const override;
211
212 virtual Vector3 get_moment_of_inertia(real_t p_mass) const override;
213
214 virtual void set_data(const Variant &p_data) override;
215 virtual Variant get_data() const override;
216
217 GodotBoxShape3D();
218};
219
220class GodotCapsuleShape3D : public GodotShape3D {
221 real_t height = 0.0;
222 real_t radius = 0.0;
223
224 void _setup(real_t p_height, real_t p_radius);
225
226public:
227 _FORCE_INLINE_ real_t get_height() const { return height; }
228 _FORCE_INLINE_ real_t get_radius() const { return radius; }
229
230 virtual real_t get_volume() const override { return 4.0 / 3.0 * Math_PI * radius * radius * radius + (height - radius * 2.0) * Math_PI * radius * radius; }
231
232 virtual PhysicsServer3D::ShapeType get_type() const override { return PhysicsServer3D::SHAPE_CAPSULE; }
233
234 virtual void project_range(const Vector3 &p_normal, const Transform3D &p_transform, real_t &r_min, real_t &r_max) const override;
235 virtual Vector3 get_support(const Vector3 &p_normal) const override;
236 virtual void get_supports(const Vector3 &p_normal, int p_max, Vector3 *r_supports, int &r_amount, FeatureType &r_type) const override;
237 virtual bool intersect_segment(const Vector3 &p_begin, const Vector3 &p_end, Vector3 &r_result, Vector3 &r_normal, int &r_face_index, bool p_hit_back_faces) const override;
238 virtual bool intersect_point(const Vector3 &p_point) const override;
239 virtual Vector3 get_closest_point_to(const Vector3 &p_point) const override;
240
241 virtual Vector3 get_moment_of_inertia(real_t p_mass) const override;
242
243 virtual void set_data(const Variant &p_data) override;
244 virtual Variant get_data() const override;
245
246 GodotCapsuleShape3D();
247};
248
249class GodotCylinderShape3D : public GodotShape3D {
250 real_t height = 0.0;
251 real_t radius = 0.0;
252
253 void _setup(real_t p_height, real_t p_radius);
254
255public:
256 _FORCE_INLINE_ real_t get_height() const { return height; }
257 _FORCE_INLINE_ real_t get_radius() const { return radius; }
258
259 virtual real_t get_volume() const override { return height * Math_PI * radius * radius; }
260
261 virtual PhysicsServer3D::ShapeType get_type() const override { return PhysicsServer3D::SHAPE_CYLINDER; }
262
263 virtual void project_range(const Vector3 &p_normal, const Transform3D &p_transform, real_t &r_min, real_t &r_max) const override;
264 virtual Vector3 get_support(const Vector3 &p_normal) const override;
265 virtual void get_supports(const Vector3 &p_normal, int p_max, Vector3 *r_supports, int &r_amount, FeatureType &r_type) const override;
266 virtual bool intersect_segment(const Vector3 &p_begin, const Vector3 &p_end, Vector3 &r_result, Vector3 &r_normal, int &r_face_index, bool p_hit_back_faces) const override;
267 virtual bool intersect_point(const Vector3 &p_point) const override;
268 virtual Vector3 get_closest_point_to(const Vector3 &p_point) const override;
269
270 virtual Vector3 get_moment_of_inertia(real_t p_mass) const override;
271
272 virtual void set_data(const Variant &p_data) override;
273 virtual Variant get_data() const override;
274
275 GodotCylinderShape3D();
276};
277
278struct GodotConvexPolygonShape3D : public GodotShape3D {
279 Geometry3D::MeshData mesh;
280 LocalVector<int> extreme_vertices;
281 LocalVector<LocalVector<int>> vertex_neighbors;
282
283 void _setup(const Vector<Vector3> &p_vertices);
284
285public:
286 const Geometry3D::MeshData &get_mesh() const { return mesh; }
287
288 virtual PhysicsServer3D::ShapeType get_type() const override { return PhysicsServer3D::SHAPE_CONVEX_POLYGON; }
289
290 virtual void project_range(const Vector3 &p_normal, const Transform3D &p_transform, real_t &r_min, real_t &r_max) const override;
291 virtual Vector3 get_support(const Vector3 &p_normal) const override;
292 virtual void get_supports(const Vector3 &p_normal, int p_max, Vector3 *r_supports, int &r_amount, FeatureType &r_type) const override;
293 virtual bool intersect_segment(const Vector3 &p_begin, const Vector3 &p_end, Vector3 &r_result, Vector3 &r_normal, int &r_face_index, bool p_hit_back_faces) const override;
294 virtual bool intersect_point(const Vector3 &p_point) const override;
295 virtual Vector3 get_closest_point_to(const Vector3 &p_point) const override;
296
297 virtual Vector3 get_moment_of_inertia(real_t p_mass) const override;
298
299 virtual void set_data(const Variant &p_data) override;
300 virtual Variant get_data() const override;
301
302 GodotConvexPolygonShape3D();
303};
304
305struct _Volume_BVH;
306struct GodotFaceShape3D;
307
308struct GodotConcavePolygonShape3D : public GodotConcaveShape3D {
309 // always a trimesh
310
311 struct Face {
312 Vector3 normal;
313 int indices[3] = {};
314 };
315
316 Vector<Face> faces;
317 Vector<Vector3> vertices;
318
319 struct BVH {
320 AABB aabb;
321 int left = 0;
322 int right = 0;
323
324 int face_index = 0;
325 };
326
327 Vector<BVH> bvh;
328
329 struct _CullParams {
330 AABB aabb;
331 QueryCallback callback = nullptr;
332 void *userdata = nullptr;
333 const Face *faces = nullptr;
334 const Vector3 *vertices = nullptr;
335 const BVH *bvh = nullptr;
336 GodotFaceShape3D *face = nullptr;
337 };
338
339 struct _SegmentCullParams {
340 Vector3 from;
341 Vector3 to;
342 Vector3 dir;
343 const Face *faces = nullptr;
344 const Vector3 *vertices = nullptr;
345 const BVH *bvh = nullptr;
346 GodotFaceShape3D *face = nullptr;
347
348 Vector3 result;
349 Vector3 normal;
350 int face_index = -1;
351 real_t min_d = 1e20;
352 int collisions = 0;
353 };
354
355 bool backface_collision = false;
356
357 void _cull_segment(int p_idx, _SegmentCullParams *p_params) const;
358 bool _cull(int p_idx, _CullParams *p_params) const;
359
360 void _fill_bvh(_Volume_BVH *p_bvh_tree, BVH *p_bvh_array, int &p_idx);
361
362 void _setup(const Vector<Vector3> &p_faces, bool p_backface_collision);
363
364public:
365 Vector<Vector3> get_faces() const;
366
367 virtual PhysicsServer3D::ShapeType get_type() const override { return PhysicsServer3D::SHAPE_CONCAVE_POLYGON; }
368
369 virtual void project_range(const Vector3 &p_normal, const Transform3D &p_transform, real_t &r_min, real_t &r_max) const override;
370 virtual Vector3 get_support(const Vector3 &p_normal) const override;
371
372 virtual bool intersect_segment(const Vector3 &p_begin, const Vector3 &p_end, Vector3 &r_result, Vector3 &r_normal, int &r_face_index, bool p_hit_back_faces) const override;
373 virtual bool intersect_point(const Vector3 &p_point) const override;
374 virtual Vector3 get_closest_point_to(const Vector3 &p_point) const override;
375
376 virtual void cull(const AABB &p_local_aabb, QueryCallback p_callback, void *p_userdata, bool p_invert_backface_collision) const override;
377
378 virtual Vector3 get_moment_of_inertia(real_t p_mass) const override;
379
380 virtual void set_data(const Variant &p_data) override;
381 virtual Variant get_data() const override;
382
383 GodotConcavePolygonShape3D();
384};
385
386struct GodotHeightMapShape3D : public GodotConcaveShape3D {
387 Vector<real_t> heights;
388 int width = 0;
389 int depth = 0;
390 Vector3 local_origin;
391
392 // Accelerator.
393 struct Range {
394 real_t min = 0.0;
395 real_t max = 0.0;
396 };
397 LocalVector<Range> bounds_grid;
398 int bounds_grid_width = 0;
399 int bounds_grid_depth = 0;
400
401 static const int BOUNDS_CHUNK_SIZE = 16;
402
403 _FORCE_INLINE_ const Range &_get_bounds_chunk(int p_x, int p_z) const {
404 return bounds_grid[(p_z * bounds_grid_width) + p_x];
405 }
406
407 _FORCE_INLINE_ real_t _get_height(int p_x, int p_z) const {
408 return heights[(p_z * width) + p_x];
409 }
410
411 _FORCE_INLINE_ void _get_point(int p_x, int p_z, Vector3 &r_point) const {
412 r_point.x = p_x - 0.5 * (width - 1.0);
413 r_point.y = _get_height(p_x, p_z);
414 r_point.z = p_z - 0.5 * (depth - 1.0);
415 }
416
417 void _get_cell(const Vector3 &p_point, int &r_x, int &r_y, int &r_z) const;
418
419 void _build_accelerator();
420
421 template <typename ProcessFunction>
422 bool _intersect_grid_segment(ProcessFunction &p_process, const Vector3 &p_begin, const Vector3 &p_end, int p_width, int p_depth, const Vector3 &offset, Vector3 &r_point, Vector3 &r_normal) const;
423
424 void _setup(const Vector<real_t> &p_heights, int p_width, int p_depth, real_t p_min_height, real_t p_max_height);
425
426public:
427 Vector<real_t> get_heights() const;
428 int get_width() const;
429 int get_depth() const;
430
431 virtual PhysicsServer3D::ShapeType get_type() const override { return PhysicsServer3D::SHAPE_HEIGHTMAP; }
432
433 virtual void project_range(const Vector3 &p_normal, const Transform3D &p_transform, real_t &r_min, real_t &r_max) const override;
434 virtual Vector3 get_support(const Vector3 &p_normal) const override;
435 virtual bool intersect_segment(const Vector3 &p_begin, const Vector3 &p_end, Vector3 &r_point, Vector3 &r_normal, int &r_face_index, bool p_hit_back_faces) const override;
436 virtual bool intersect_point(const Vector3 &p_point) const override;
437
438 virtual Vector3 get_closest_point_to(const Vector3 &p_point) const override;
439 virtual void cull(const AABB &p_local_aabb, QueryCallback p_callback, void *p_userdata, bool p_invert_backface_collision) const override;
440
441 virtual Vector3 get_moment_of_inertia(real_t p_mass) const override;
442
443 virtual void set_data(const Variant &p_data) override;
444 virtual Variant get_data() const override;
445
446 GodotHeightMapShape3D();
447};
448
449//used internally
450struct GodotFaceShape3D : public GodotShape3D {
451 Vector3 normal; //cache
452 Vector3 vertex[3];
453 bool backface_collision = false;
454 bool invert_backface_collision = false;
455
456 virtual PhysicsServer3D::ShapeType get_type() const override { return PhysicsServer3D::SHAPE_CONCAVE_POLYGON; }
457
458 const Vector3 &get_vertex(int p_idx) const { return vertex[p_idx]; }
459
460 virtual void project_range(const Vector3 &p_normal, const Transform3D &p_transform, real_t &r_min, real_t &r_max) const override;
461 virtual Vector3 get_support(const Vector3 &p_normal) const override;
462 virtual void get_supports(const Vector3 &p_normal, int p_max, Vector3 *r_supports, int &r_amount, FeatureType &r_type) const override;
463 virtual bool intersect_segment(const Vector3 &p_begin, const Vector3 &p_end, Vector3 &r_result, Vector3 &r_normal, int &r_face_index, bool p_hit_back_faces) const override;
464 virtual bool intersect_point(const Vector3 &p_point) const override;
465 virtual Vector3 get_closest_point_to(const Vector3 &p_point) const override;
466
467 virtual Vector3 get_moment_of_inertia(real_t p_mass) const override;
468
469 virtual void set_data(const Variant &p_data) override {}
470 virtual Variant get_data() const override { return Variant(); }
471
472 GodotFaceShape3D();
473};
474
475struct GodotMotionShape3D : public GodotShape3D {
476 GodotShape3D *shape = nullptr;
477 Vector3 motion;
478
479 virtual PhysicsServer3D::ShapeType get_type() const override { return PhysicsServer3D::SHAPE_CONVEX_POLYGON; }
480
481 virtual void project_range(const Vector3 &p_normal, const Transform3D &p_transform, real_t &r_min, real_t &r_max) const override {
482 Vector3 cast = p_transform.basis.xform(motion);
483 real_t mina, maxa;
484 real_t minb, maxb;
485 Transform3D ofsb = p_transform;
486 ofsb.origin += cast;
487 shape->project_range(p_normal, p_transform, mina, maxa);
488 shape->project_range(p_normal, ofsb, minb, maxb);
489 r_min = MIN(mina, minb);
490 r_max = MAX(maxa, maxb);
491 }
492
493 virtual Vector3 get_support(const Vector3 &p_normal) const override {
494 Vector3 support = shape->get_support(p_normal);
495 if (p_normal.dot(motion) > 0) {
496 support += motion;
497 }
498 return support;
499 }
500
501 virtual void get_supports(const Vector3 &p_normal, int p_max, Vector3 *r_supports, int &r_amount, FeatureType &r_type) const override { r_amount = 0; }
502 virtual bool intersect_segment(const Vector3 &p_begin, const Vector3 &p_end, Vector3 &r_result, Vector3 &r_normal, int &r_face_index, bool p_hit_back_faces) const override { return false; }
503 virtual bool intersect_point(const Vector3 &p_point) const override { return false; }
504 virtual Vector3 get_closest_point_to(const Vector3 &p_point) const override { return p_point; }
505
506 virtual Vector3 get_moment_of_inertia(real_t p_mass) const override { return Vector3(); }
507
508 virtual void set_data(const Variant &p_data) override {}
509 virtual Variant get_data() const override { return Variant(); }
510
511 GodotMotionShape3D() { configure(AABB()); }
512};
513
514#endif // GODOT_SHAPE_3D_H
515