diff options
Diffstat (limited to 'core')
30 files changed, 1592 insertions, 96 deletions
diff --git a/core/SCsub b/core/SCsub index 45918fb520..c9f84a9a00 100644 --- a/core/SCsub +++ b/core/SCsub @@ -38,6 +38,9 @@ with open("script_encryption_key.gen.cpp", "w") as f: # Add required thirdparty code. + +thirdparty_obj = [] + env_thirdparty = env.Clone() env_thirdparty.disable_warnings() @@ -55,7 +58,7 @@ thirdparty_misc_sources = [ "clipper.cpp", ] thirdparty_misc_sources = [thirdparty_misc_dir + file for file in thirdparty_misc_sources] -env_thirdparty.add_source_files(env.core_sources, thirdparty_misc_sources) +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_misc_sources) # Zlib library, can be unbundled if env["builtin_zlib"]: @@ -81,14 +84,14 @@ if env["builtin_zlib"]: if env["target"] == "debug": env_thirdparty.Append(CPPDEFINES=["ZLIB_DEBUG"]) - env_thirdparty.add_source_files(env.core_sources, thirdparty_zlib_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_zlib_sources) # Minizip library, could be unbundled in theory # However, our version has some custom modifications, so it won't compile with the system one thirdparty_minizip_dir = "#thirdparty/minizip/" thirdparty_minizip_sources = ["ioapi.c", "unzip.c", "zip.c"] thirdparty_minizip_sources = [thirdparty_minizip_dir + file for file in thirdparty_minizip_sources] -env_thirdparty.add_source_files(env.core_sources, thirdparty_minizip_sources) +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_minizip_sources) # Zstd library, can be unbundled in theory # though we currently use some private symbols @@ -130,10 +133,14 @@ if env["builtin_zstd"]: # Also needed in main env includes will trigger warnings env.Append(CPPDEFINES=["ZSTD_STATIC_LINKING_ONLY"]) - env_thirdparty.add_source_files(env.core_sources, thirdparty_zstd_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_zstd_sources) + +env.core_sources += thirdparty_obj + + +# Godot source files -# Godot's own sources env.add_source_files(env.core_sources, "*.cpp") # Certificates @@ -185,3 +192,6 @@ SConscript("error/SCsub") # Build it all as a library lib = env.add_library("core", env.core_sources) env.Prepend(LIBS=[lib]) + +# Needed to force rebuilding the core files when the thirdparty code is updated. +env.Depends(lib, thirdparty_obj) diff --git a/core/core_constants.cpp b/core/core_constants.cpp index 02055012ad..555908ea79 100644 --- a/core/core_constants.cpp +++ b/core/core_constants.cpp @@ -112,10 +112,10 @@ VARIANT_ENUM_CAST(JoyAxisList); VARIANT_ENUM_CAST(MidiMessageList); void register_global_constants() { - BIND_CORE_ENUM_CONSTANT(MARGIN_LEFT); - BIND_CORE_ENUM_CONSTANT(MARGIN_TOP); - BIND_CORE_ENUM_CONSTANT(MARGIN_RIGHT); - BIND_CORE_ENUM_CONSTANT(MARGIN_BOTTOM); + BIND_CORE_ENUM_CONSTANT(SIDE_LEFT); + BIND_CORE_ENUM_CONSTANT(SIDE_TOP); + BIND_CORE_ENUM_CONSTANT(SIDE_RIGHT); + BIND_CORE_ENUM_CONSTANT(SIDE_BOTTOM); BIND_CORE_ENUM_CONSTANT(CORNER_TOP_LEFT); BIND_CORE_ENUM_CONSTANT(CORNER_TOP_RIGHT); @@ -525,6 +525,7 @@ void register_global_constants() { BIND_CORE_ENUM_CONSTANT(PROPERTY_HINT_COLOR_NO_ALPHA); BIND_CORE_ENUM_CONSTANT(PROPERTY_HINT_IMAGE_COMPRESS_LOSSY); BIND_CORE_ENUM_CONSTANT(PROPERTY_HINT_IMAGE_COMPRESS_LOSSLESS); + BIND_CORE_ENUM_CONSTANT(PROPERTY_HINT_TYPE_STRING); BIND_CORE_ENUM_CONSTANT(PROPERTY_USAGE_STORAGE); BIND_CORE_ENUM_CONSTANT(PROPERTY_USAGE_EDITOR); diff --git a/core/crypto/SCsub b/core/crypto/SCsub index da4a9c9381..4f3104d84b 100644 --- a/core/crypto/SCsub +++ b/core/crypto/SCsub @@ -6,6 +6,7 @@ env_crypto = env.Clone() is_builtin = env["builtin_mbedtls"] has_module = env["module_mbedtls_enabled"] +thirdparty_obj = [] if is_builtin or not has_module: # Use our headers for builtin or if the module is not going to be compiled. @@ -35,6 +36,16 @@ if not has_module: "godot_core_mbedtls_platform.c", ] thirdparty_mbedtls_sources = [thirdparty_mbedtls_dir + file for file in thirdparty_mbedtls_sources] - env_thirdparty.add_source_files(env.core_sources, thirdparty_mbedtls_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_mbedtls_sources) + env.core_sources += thirdparty_obj -env_crypto.add_source_files(env.core_sources, "*.cpp") + +# Godot source files + +core_obj = [] + +env_crypto.add_source_files(core_obj, "*.cpp") +env.core_sources += core_obj + +# Needed to force rebuilding the core files when the thirdparty library is updated. +env.Depends(core_obj, thirdparty_obj) diff --git a/core/io/image.cpp b/core/io/image.cpp index 7c32c02701..56d84325b5 100644 --- a/core/io/image.cpp +++ b/core/io/image.cpp @@ -993,7 +993,7 @@ bool Image::is_size_po2() const { return uint32_t(width) == next_power_of_2(width) && uint32_t(height) == next_power_of_2(height); } -void Image::resize_to_po2(bool p_square) { +void Image::resize_to_po2(bool p_square, Interpolation p_interpolation) { ERR_FAIL_COND_MSG(!_can_modify(format), "Cannot resize in compressed or custom image formats."); int w = next_power_of_2(width); @@ -1008,7 +1008,7 @@ void Image::resize_to_po2(bool p_square) { } } - resize(w, h); + resize(w, h, p_interpolation); } void Image::resize(int p_width, int p_height, Interpolation p_interpolation) { @@ -2480,7 +2480,7 @@ void Image::blit_rect(const Ref<Image> &p_src, const Rect2 &p_src_rect, const Po ERR_FAIL_COND(format != p_src->format); ERR_FAIL_COND_MSG(!_can_modify(format), "Cannot blit_rect in compressed or custom image formats."); - Rect2i clipped_src_rect = Rect2i(0, 0, p_src->width, p_src->height).clip(p_src_rect); + Rect2i clipped_src_rect = Rect2i(0, 0, p_src->width, p_src->height).intersection(p_src_rect); if (p_dest.x < 0) { clipped_src_rect.position.x = ABS(p_dest.x); @@ -2494,7 +2494,7 @@ void Image::blit_rect(const Ref<Image> &p_src, const Rect2 &p_src_rect, const Po } Point2 src_underscan = Point2(MIN(0, p_src_rect.position.x), MIN(0, p_src_rect.position.y)); - Rect2i dest_rect = Rect2i(0, 0, width, height).clip(Rect2i(p_dest - src_underscan, clipped_src_rect.size)); + Rect2i dest_rect = Rect2i(0, 0, width, height).intersection(Rect2i(p_dest - src_underscan, clipped_src_rect.size)); uint8_t *wp = data.ptrw(); uint8_t *dst_data_ptr = wp; @@ -2535,7 +2535,7 @@ void Image::blit_rect_mask(const Ref<Image> &p_src, const Ref<Image> &p_mask, co ERR_FAIL_COND_MSG(p_src->height != p_mask->height, "Source image height is different from mask height."); ERR_FAIL_COND(format != p_src->format); - Rect2i clipped_src_rect = Rect2i(0, 0, p_src->width, p_src->height).clip(p_src_rect); + Rect2i clipped_src_rect = Rect2i(0, 0, p_src->width, p_src->height).intersection(p_src_rect); if (p_dest.x < 0) { clipped_src_rect.position.x = ABS(p_dest.x); @@ -2549,7 +2549,7 @@ void Image::blit_rect_mask(const Ref<Image> &p_src, const Ref<Image> &p_mask, co } Point2 src_underscan = Point2(MIN(0, p_src_rect.position.x), MIN(0, p_src_rect.position.y)); - Rect2i dest_rect = Rect2i(0, 0, width, height).clip(Rect2i(p_dest - src_underscan, clipped_src_rect.size)); + Rect2i dest_rect = Rect2i(0, 0, width, height).intersection(Rect2i(p_dest - src_underscan, clipped_src_rect.size)); uint8_t *wp = data.ptrw(); uint8_t *dst_data_ptr = wp; @@ -2589,7 +2589,7 @@ void Image::blend_rect(const Ref<Image> &p_src, const Rect2 &p_src_rect, const P ERR_FAIL_COND(srcdsize == 0); ERR_FAIL_COND(format != p_src->format); - Rect2i clipped_src_rect = Rect2i(0, 0, p_src->width, p_src->height).clip(p_src_rect); + Rect2i clipped_src_rect = Rect2i(0, 0, p_src->width, p_src->height).intersection(p_src_rect); if (p_dest.x < 0) { clipped_src_rect.position.x = ABS(p_dest.x); @@ -2603,7 +2603,7 @@ void Image::blend_rect(const Ref<Image> &p_src, const Rect2 &p_src_rect, const P } Point2 src_underscan = Point2(MIN(0, p_src_rect.position.x), MIN(0, p_src_rect.position.y)); - Rect2i dest_rect = Rect2i(0, 0, width, height).clip(Rect2i(p_dest - src_underscan, clipped_src_rect.size)); + Rect2i dest_rect = Rect2i(0, 0, width, height).intersection(Rect2i(p_dest - src_underscan, clipped_src_rect.size)); Ref<Image> img = p_src; @@ -2638,7 +2638,7 @@ void Image::blend_rect_mask(const Ref<Image> &p_src, const Ref<Image> &p_mask, c ERR_FAIL_COND_MSG(p_src->height != p_mask->height, "Source image height is different from mask height."); ERR_FAIL_COND(format != p_src->format); - Rect2i clipped_src_rect = Rect2i(0, 0, p_src->width, p_src->height).clip(p_src_rect); + Rect2i clipped_src_rect = Rect2i(0, 0, p_src->width, p_src->height).intersection(p_src_rect); if (p_dest.x < 0) { clipped_src_rect.position.x = ABS(p_dest.x); @@ -2652,7 +2652,7 @@ void Image::blend_rect_mask(const Ref<Image> &p_src, const Ref<Image> &p_mask, c } Point2 src_underscan = Point2(MIN(0, p_src_rect.position.x), MIN(0, p_src_rect.position.y)); - Rect2i dest_rect = Rect2i(0, 0, width, height).clip(Rect2i(p_dest - src_underscan, clipped_src_rect.size)); + Rect2i dest_rect = Rect2i(0, 0, width, height).intersection(Rect2i(p_dest - src_underscan, clipped_src_rect.size)); Ref<Image> img = p_src; Ref<Image> msk = p_mask; @@ -3077,7 +3077,7 @@ void Image::_bind_methods() { ClassDB::bind_method(D_METHOD("get_mipmap_offset", "mipmap"), &Image::get_mipmap_offset); - ClassDB::bind_method(D_METHOD("resize_to_po2", "square"), &Image::resize_to_po2, DEFVAL(false)); + ClassDB::bind_method(D_METHOD("resize_to_po2", "square", "interpolation"), &Image::resize_to_po2, DEFVAL(false), DEFVAL(INTERPOLATE_BILINEAR)); ClassDB::bind_method(D_METHOD("resize", "width", "height", "interpolation"), &Image::resize, DEFVAL(INTERPOLATE_BILINEAR)); ClassDB::bind_method(D_METHOD("shrink_x2"), &Image::shrink_x2); diff --git a/core/io/image.h b/core/io/image.h index 0151df0cf9..6b4488bd66 100644 --- a/core/io/image.h +++ b/core/io/image.h @@ -244,7 +244,7 @@ public: /** * Resize the image, using the preferred interpolation method. */ - void resize_to_po2(bool p_square = false); + void resize_to_po2(bool p_square = false, Interpolation p_interpolation = INTERPOLATE_BILINEAR); void resize(int p_width, int p_height, Interpolation p_interpolation = INTERPOLATE_BILINEAR); void shrink_x2(); bool is_size_po2() const; diff --git a/core/io/logger.cpp b/core/io/logger.cpp index f5cea00f28..241c72d310 100644 --- a/core/io/logger.cpp +++ b/core/io/logger.cpp @@ -30,6 +30,7 @@ #include "logger.h" +#include "core/config/project_settings.h" #include "core/os/dir_access.h" #include "core/os/os.h" #include "core/string/print_string.h" @@ -201,15 +202,14 @@ void RotatedFileLogger::logv(const char *p_format, va_list p_list, bool p_err) { } va_end(list_copy); file->store_buffer((uint8_t *)buf, len); + if (len >= static_buf_size) { Memory::free_static(buf); } -#ifdef DEBUG_ENABLED - const bool need_flush = true; -#else - bool need_flush = p_err; -#endif - if (need_flush) { + + if (p_err || GLOBAL_GET("application/run/flush_stdout_on_print")) { + // Don't always flush when printing stdout to avoid performance + // issues when `print()` is spammed in release builds. file->flush(); } } @@ -228,9 +228,11 @@ void StdLogger::logv(const char *p_format, va_list p_list, bool p_err) { vfprintf(stderr, p_format, p_list); } else { vprintf(p_format, p_list); -#ifdef DEBUG_ENABLED - fflush(stdout); -#endif + if (GLOBAL_GET("application/run/flush_stdout_on_print")) { + // Don't always flush when printing stdout to avoid performance + // issues when `print()` is spammed in release builds. + fflush(stdout); + } } } diff --git a/core/math/aabb.h b/core/math/aabb.h index 45dcbc7f7f..24908ae59d 100644 --- a/core/math/aabb.h +++ b/core/math/aabb.h @@ -107,6 +107,9 @@ public: Variant intersects_segment_bind(const Vector3 &p_from, const Vector3 &p_to) const; Variant intersects_ray_bind(const Vector3 &p_from, const Vector3 &p_dir) const; + _FORCE_INLINE_ void quantize(float p_unit); + _FORCE_INLINE_ AABB quantized(float p_unit) const; + _FORCE_INLINE_ void set_end(const Vector3 &p_end) { size = p_end - position; } @@ -190,9 +193,9 @@ Vector3 AABB::get_support(const Vector3 &p_normal) const { Vector3 ofs = position + half_extents; return Vector3( - (p_normal.x > 0) ? -half_extents.x : half_extents.x, - (p_normal.y > 0) ? -half_extents.y : half_extents.y, - (p_normal.z > 0) ? -half_extents.z : half_extents.z) + + (p_normal.x > 0) ? half_extents.x : -half_extents.x, + (p_normal.y > 0) ? half_extents.y : -half_extents.y, + (p_normal.z > 0) ? half_extents.z : -half_extents.z) + ofs; } @@ -427,4 +430,28 @@ void AABB::grow_by(real_t p_amount) { size.z += 2.0 * p_amount; } +void AABB::quantize(float p_unit) { + size += position; + + position.x -= Math::fposmodp(position.x, p_unit); + position.y -= Math::fposmodp(position.y, p_unit); + position.z -= Math::fposmodp(position.z, p_unit); + + size.x -= Math::fposmodp(size.x, p_unit); + size.y -= Math::fposmodp(size.y, p_unit); + size.z -= Math::fposmodp(size.z, p_unit); + + size.x += p_unit; + size.y += p_unit; + size.z += p_unit; + + size -= position; +} + +AABB AABB::quantized(float p_unit) const { + AABB ret = *this; + ret.quantize(p_unit); + return ret; +} + #endif // AABB_H diff --git a/core/math/camera_matrix.cpp b/core/math/camera_matrix.cpp index 5e5efb6356..f29cb7a269 100644 --- a/core/math/camera_matrix.cpp +++ b/core/math/camera_matrix.cpp @@ -655,6 +655,17 @@ real_t CameraMatrix::get_fov() const { } } +float CameraMatrix::get_lod_multiplier() const { + if (is_orthogonal()) { + return get_viewport_half_extents().x; + } else { + float zn = get_z_near(); + float width = get_viewport_half_extents().x * 2.0; + return 1.0 / (zn / width); + } + + //usage is lod_size / (lod_distance * multiplier) < threshold +} void CameraMatrix::make_scale(const Vector3 &p_scale) { set_identity(); matrix[0][0] = p_scale.x; diff --git a/core/math/camera_matrix.h b/core/math/camera_matrix.h index c5cdd98377..f856a7b1bf 100644 --- a/core/math/camera_matrix.h +++ b/core/math/camera_matrix.h @@ -108,6 +108,8 @@ struct CameraMatrix { return !(*this == p_cam); } + float get_lod_multiplier() const; + CameraMatrix(); CameraMatrix(const Transform &p_transform); ~CameraMatrix(); diff --git a/core/math/dynamic_bvh.cpp b/core/math/dynamic_bvh.cpp new file mode 100644 index 0000000000..23e713dd2d --- /dev/null +++ b/core/math/dynamic_bvh.cpp @@ -0,0 +1,431 @@ +/*************************************************************************/ +/* dynamic_bvh.cpp */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#include "dynamic_bvh.h" + +void DynamicBVH::_delete_node(Node *p_node) { + node_allocator.free(p_node); +} + +void DynamicBVH::_recurse_delete_node(Node *p_node) { + if (!p_node->is_leaf()) { + _recurse_delete_node(p_node->childs[0]); + _recurse_delete_node(p_node->childs[1]); + } + if (p_node == bvh_root) { + bvh_root = nullptr; + } + _delete_node(p_node); +} + +DynamicBVH::Node *DynamicBVH::_create_node(Node *p_parent, void *p_data) { + Node *node = node_allocator.alloc(); + node->parent = p_parent; + node->data = p_data; + return (node); +} + +DynamicBVH::Node *DynamicBVH::_create_node_with_volume(Node *p_parent, const Volume &p_volume, void *p_data) { + Node *node = _create_node(p_parent, p_data); + node->volume = p_volume; + return node; +} + +void DynamicBVH::_insert_leaf(Node *p_root, Node *p_leaf) { + if (!bvh_root) { + bvh_root = p_leaf; + p_leaf->parent = 0; + } else { + if (!p_root->is_leaf()) { + do { + p_root = p_root->childs[p_leaf->volume.select_by_proximity( + p_root->childs[0]->volume, + p_root->childs[1]->volume)]; + } while (!p_root->is_leaf()); + } + Node *prev = p_root->parent; + Node *node = _create_node_with_volume(prev, p_leaf->volume.merge(p_root->volume), 0); + if (prev) { + prev->childs[p_root->get_index_in_parent()] = node; + node->childs[0] = p_root; + p_root->parent = node; + node->childs[1] = p_leaf; + p_leaf->parent = node; + do { + if (!prev->volume.contains(node->volume)) { + prev->volume = prev->childs[0]->volume.merge(prev->childs[1]->volume); + } else { + break; + } + node = prev; + } while (0 != (prev = node->parent)); + } else { + node->childs[0] = p_root; + p_root->parent = node; + node->childs[1] = p_leaf; + p_leaf->parent = node; + bvh_root = node; + } + } +} + +DynamicBVH::Node *DynamicBVH::_remove_leaf(Node *leaf) { + if (leaf == bvh_root) { + bvh_root = 0; + return (0); + } else { + Node *parent = leaf->parent; + Node *prev = parent->parent; + Node *sibling = parent->childs[1 - leaf->get_index_in_parent()]; + if (prev) { + prev->childs[parent->get_index_in_parent()] = sibling; + sibling->parent = prev; + _delete_node(parent); + while (prev) { + const Volume pb = prev->volume; + prev->volume = prev->childs[0]->volume.merge(prev->childs[1]->volume); + if (pb.is_not_equal_to(prev->volume)) { + prev = prev->parent; + } else + break; + } + return (prev ? prev : bvh_root); + } else { + bvh_root = sibling; + sibling->parent = 0; + _delete_node(parent); + return (bvh_root); + } + } +} + +void DynamicBVH::_fetch_leaves(Node *p_root, LocalVector<Node *> &r_leaves, int p_depth) { + if (p_root->is_internal() && p_depth) { + _fetch_leaves(p_root->childs[0], r_leaves, p_depth - 1); + _fetch_leaves(p_root->childs[1], r_leaves, p_depth - 1); + _delete_node(p_root); + } else { + r_leaves.push_back(p_root); + } +} + +// Partitions leaves such that leaves[0, n) are on the +// left of axis, and leaves[n, count) are on the right +// of axis. returns N. +int DynamicBVH::_split(Node **leaves, int p_count, const Vector3 &p_org, const Vector3 &p_axis) { + int begin = 0; + int end = p_count; + for (;;) { + while (begin != end && leaves[begin]->is_left_of_axis(p_org, p_axis)) { + ++begin; + } + + if (begin == end) { + break; + } + + while (begin != end && !leaves[end - 1]->is_left_of_axis(p_org, p_axis)) { + --end; + } + + if (begin == end) { + break; + } + + // swap out of place nodes + --end; + Node *temp = leaves[begin]; + leaves[begin] = leaves[end]; + leaves[end] = temp; + ++begin; + } + + return begin; +} + +DynamicBVH::Volume DynamicBVH::_bounds(Node **leaves, int p_count) { + Volume volume = leaves[0]->volume; + for (int i = 1, ni = p_count; i < ni; ++i) { + volume = volume.merge(leaves[i]->volume); + } + return (volume); +} + +void DynamicBVH::_bottom_up(Node **leaves, int p_count) { + while (p_count > 1) { + real_t minsize = Math_INF; + int minidx[2] = { -1, -1 }; + for (int i = 0; i < p_count; ++i) { + for (int j = i + 1; j < p_count; ++j) { + const real_t sz = leaves[i]->volume.merge(leaves[j]->volume).get_size(); + if (sz < minsize) { + minsize = sz; + minidx[0] = i; + minidx[1] = j; + } + } + } + Node *n[] = { leaves[minidx[0]], leaves[minidx[1]] }; + Node *p = _create_node_with_volume(nullptr, n[0]->volume.merge(n[1]->volume), nullptr); + p->childs[0] = n[0]; + p->childs[1] = n[1]; + n[0]->parent = p; + n[1]->parent = p; + leaves[minidx[0]] = p; + leaves[minidx[1]] = leaves[p_count - 1]; + --p_count; + } +} + +DynamicBVH::Node *DynamicBVH::_top_down(Node **leaves, int p_count, int p_bu_threshold) { + static const Vector3 axis[] = { Vector3(1, 0, 0), Vector3(0, 1, 0), Vector3(0, 0, 1) }; + + ERR_FAIL_COND_V(p_bu_threshold <= 1, nullptr); + if (p_count > 1) { + if (p_count > p_bu_threshold) { + const Volume vol = _bounds(leaves, p_count); + const Vector3 org = vol.get_center(); + int partition; + int bestaxis = -1; + int bestmidp = p_count; + int splitcount[3][2] = { { 0, 0 }, { 0, 0 }, { 0, 0 } }; + int i; + for (i = 0; i < p_count; ++i) { + const Vector3 x = leaves[i]->volume.get_center() - org; + for (int j = 0; j < 3; ++j) { + ++splitcount[j][x.dot(axis[j]) > 0 ? 1 : 0]; + } + } + for (i = 0; i < 3; ++i) { + if ((splitcount[i][0] > 0) && (splitcount[i][1] > 0)) { + const int midp = (int)Math::abs(real_t(splitcount[i][0] - splitcount[i][1])); + if (midp < bestmidp) { + bestaxis = i; + bestmidp = midp; + } + } + } + if (bestaxis >= 0) { + partition = _split(leaves, p_count, org, axis[bestaxis]); + ERR_FAIL_COND_V(partition == 0 || partition == p_count, nullptr); + } else { + partition = p_count / 2 + 1; + } + + Node *node = _create_node_with_volume(nullptr, vol, nullptr); + node->childs[0] = _top_down(&leaves[0], partition, p_bu_threshold); + node->childs[1] = _top_down(&leaves[partition], p_count - partition, p_bu_threshold); + node->childs[0]->parent = node; + node->childs[1]->parent = node; + return (node); + } else { + _bottom_up(leaves, p_count); + return (leaves[0]); + } + } + return (leaves[0]); +} + +DynamicBVH::Node *DynamicBVH::_node_sort(Node *n, Node *&r) { + Node *p = n->parent; + ERR_FAIL_COND_V(!n->is_internal(), nullptr); + if (p > n) { + const int i = n->get_index_in_parent(); + const int j = 1 - i; + Node *s = p->childs[j]; + Node *q = p->parent; + ERR_FAIL_COND_V(n != p->childs[i], nullptr); + if (q) + q->childs[p->get_index_in_parent()] = n; + else + r = n; + s->parent = n; + p->parent = n; + n->parent = q; + p->childs[0] = n->childs[0]; + p->childs[1] = n->childs[1]; + n->childs[0]->parent = p; + n->childs[1]->parent = p; + n->childs[i] = p; + n->childs[j] = s; + SWAP(p->volume, n->volume); + return (p); + } + return (n); +} + +void DynamicBVH::clear() { + if (bvh_root) { + _recurse_delete_node(bvh_root); + } + lkhd = -1; + opath = 0; +} + +void DynamicBVH::optimize_bottom_up() { + if (bvh_root) { + LocalVector<Node *> leaves; + _fetch_leaves(bvh_root, leaves); + _bottom_up(&leaves[0], leaves.size()); + bvh_root = leaves[0]; + } +} + +void DynamicBVH::optimize_top_down(int bu_threshold) { + if (bvh_root) { + LocalVector<Node *> leaves; + _fetch_leaves(bvh_root, leaves); + bvh_root = _top_down(&leaves[0], leaves.size(), bu_threshold); + } +} + +void DynamicBVH::optimize_incremental(int passes) { + if (passes < 0) + passes = total_leaves; + if (bvh_root && (passes > 0)) { + do { + Node *node = bvh_root; + unsigned bit = 0; + while (node->is_internal()) { + node = _node_sort(node, bvh_root)->childs[(opath >> bit) & 1]; + bit = (bit + 1) & (sizeof(unsigned) * 8 - 1); + } + _update(node); + ++opath; + } while (--passes); + } +} + +DynamicBVH::ID DynamicBVH::insert(const AABB &p_box, void *p_userdata) { + Volume volume; + volume.min = p_box.position; + volume.max = p_box.position + p_box.size; + + Node *leaf = _create_node_with_volume(nullptr, volume, p_userdata); + _insert_leaf(bvh_root, leaf); + ++total_leaves; + + ID id; + id.node = leaf; + + return id; +} + +void DynamicBVH::_update(Node *leaf, int lookahead) { + Node *root = _remove_leaf(leaf); + if (root) { + if (lookahead >= 0) { + for (int i = 0; (i < lookahead) && root->parent; ++i) { + root = root->parent; + } + } else + root = bvh_root; + } + _insert_leaf(root, leaf); +} + +bool DynamicBVH::update(const ID &p_id, const AABB &p_box) { + ERR_FAIL_COND_V(!p_id.is_valid(), false); + Node *leaf = p_id.node; + + Volume volume; + volume.min = p_box.position; + volume.max = p_box.position + p_box.size; + + if (leaf->volume.min.is_equal_approx(volume.min) && leaf->volume.max.is_equal_approx(volume.max)) { + // noop + return false; + } + + Node *base = _remove_leaf(leaf); + if (base) { + if (lkhd >= 0) { + for (int i = 0; (i < lkhd) && base->parent; ++i) { + base = base->parent; + } + } else + base = bvh_root; + } + leaf->volume = volume; + _insert_leaf(base, leaf); + return true; +} + +void DynamicBVH::remove(const ID &p_id) { + ERR_FAIL_COND(!p_id.is_valid()); + Node *leaf = p_id.node; + _remove_leaf(leaf); + _delete_node(leaf); + --total_leaves; +} + +void DynamicBVH::_extract_leaves(Node *p_node, List<ID> *r_elements) { + if (p_node->is_internal()) { + _extract_leaves(p_node->childs[0], r_elements); + _extract_leaves(p_node->childs[1], r_elements); + } else { + ID id; + id.node = p_node; + r_elements->push_back(id); + } +} + +void DynamicBVH::set_index(uint32_t p_index) { + ERR_FAIL_COND(bvh_root != nullptr); + index = p_index; +} + +uint32_t DynamicBVH::get_index() const { + return index; +} + +void DynamicBVH::get_elements(List<ID> *r_elements) { + if (bvh_root) { + _extract_leaves(bvh_root, r_elements); + } +} + +int DynamicBVH::get_leaf_count() const { + return total_leaves; +} +int DynamicBVH::get_max_depth() const { + if (bvh_root) { + int depth = 1; + int max_depth = 0; + bvh_root->get_max_depth(depth, max_depth); + return max_depth; + } else { + return 0; + } +} + +DynamicBVH::~DynamicBVH() { + clear(); +} diff --git a/core/math/dynamic_bvh.h b/core/math/dynamic_bvh.h new file mode 100644 index 0000000000..ecf2feb3d8 --- /dev/null +++ b/core/math/dynamic_bvh.h @@ -0,0 +1,468 @@ +/*************************************************************************/ +/* dynamic_bvh.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef DYNAMICBVH_H +#define DYNAMICBVH_H + +#include "core/math/aabb.h" +#include "core/templates/list.h" +#include "core/templates/local_vector.h" +#include "core/templates/paged_allocator.h" +#include "core/typedefs.h" + +// Based on bullet Dbvh + +/* +Bullet Continuous Collision Detection and Physics Library +Copyright (c) 2003-2013 Erwin Coumans http://bulletphysics.org + +This software is provided 'as-is', without any express or implied warranty. +In no event will the authors be held liable for any damages arising from the use of this software. +Permission is granted to anyone to use this software for any purpose, +including commercial applications, and to alter it and redistribute it freely, +subject to the following restrictions: + +1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required. +2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software. +3. This notice may not be removed or altered from any source distribution. +*/ + +///DynamicBVH implementation by Nathanael Presson +// The DynamicBVH class implements a fast dynamic bounding volume tree based on axis aligned bounding boxes (aabb tree). + +class DynamicBVH { + struct Node; + +public: + struct ID { + Node *node = nullptr; + + public: + _FORCE_INLINE_ bool is_valid() const { return node != nullptr; } + }; + +private: + struct Volume { + Vector3 min, max; + + _FORCE_INLINE_ Vector3 get_center() const { return ((min + max) / 2); } + _FORCE_INLINE_ Vector3 get_length() const { return (max - min); } + + _FORCE_INLINE_ bool contains(const Volume &a) const { + return ((min.x <= a.min.x) && + (min.y <= a.min.y) && + (min.z <= a.min.z) && + (max.x >= a.max.x) && + (max.y >= a.max.y) && + (max.z >= a.max.z)); + } + + _FORCE_INLINE_ Volume merge(const Volume &b) const { + Volume r; + for (int i = 0; i < 3; ++i) { + if (min[i] < b.min[i]) + r.min[i] = min[i]; + else + r.min[i] = b.min[i]; + if (max[i] > b.max[i]) + r.max[i] = max[i]; + else + r.max[i] = b.max[i]; + } + return r; + } + + _FORCE_INLINE_ real_t get_size() const { + const Vector3 edges = get_length(); + return (edges.x * edges.y * edges.z + + edges.x + edges.y + edges.z); + } + + _FORCE_INLINE_ bool is_not_equal_to(const Volume &b) const { + return ((min.x != b.min.x) || + (min.y != b.min.y) || + (min.z != b.min.z) || + (max.x != b.max.x) || + (max.y != b.max.y) || + (max.z != b.max.z)); + } + + _FORCE_INLINE_ real_t get_proximity_to(const Volume &b) const { + const Vector3 d = (min + max) - (b.min + b.max); + return (Math::abs(d.x) + Math::abs(d.y) + Math::abs(d.z)); + } + + _FORCE_INLINE_ int select_by_proximity(const Volume &a, const Volume &b) const { + return (get_proximity_to(a) < get_proximity_to(b) ? 0 : 1); + } + + // + _FORCE_INLINE_ bool intersects(const Volume &b) const { + return ((min.x <= b.max.x) && + (max.x >= b.min.x) && + (min.y <= b.max.y) && + (max.y >= b.min.y) && + (min.z <= b.max.z) && + (max.z >= b.min.z)); + } + + _FORCE_INLINE_ bool intersects_convex(const Plane *p_planes, int p_plane_count, const Vector3 *p_points, int p_point_count) const { + Vector3 half_extents = (max - min) * 0.5; + Vector3 ofs = min + half_extents; + + for (int i = 0; i < p_plane_count; i++) { + const Plane &p = p_planes[i]; + Vector3 point( + (p.normal.x > 0) ? -half_extents.x : half_extents.x, + (p.normal.y > 0) ? -half_extents.y : half_extents.y, + (p.normal.z > 0) ? -half_extents.z : half_extents.z); + point += ofs; + if (p.is_point_over(point)) { + return false; + } + } + + // Make sure all points in the shape aren't fully separated from the AABB on + // each axis. + int bad_point_counts_positive[3] = { 0 }; + int bad_point_counts_negative[3] = { 0 }; + + for (int k = 0; k < 3; k++) { + for (int i = 0; i < p_point_count; i++) { + if (p_points[i].coord[k] > ofs.coord[k] + half_extents.coord[k]) { + bad_point_counts_positive[k]++; + } + if (p_points[i].coord[k] < ofs.coord[k] - half_extents.coord[k]) { + bad_point_counts_negative[k]++; + } + } + + if (bad_point_counts_negative[k] == p_point_count) { + return false; + } + if (bad_point_counts_positive[k] == p_point_count) { + return false; + } + } + + return true; + } + }; + + struct Node { + Volume volume; + Node *parent = nullptr; + union { + Node *childs[2]; + void *data; + }; + + _FORCE_INLINE_ bool is_leaf() const { return childs[1] == nullptr; } + _FORCE_INLINE_ bool is_internal() const { return (!is_leaf()); } + + _FORCE_INLINE_ int get_index_in_parent() const { + ERR_FAIL_COND_V(!parent, 0); + return (parent->childs[1] == this) ? 1 : 0; + } + void get_max_depth(int depth, int &maxdepth) { + if (is_internal()) { + childs[0]->get_max_depth(depth + 1, maxdepth); + childs[1]->get_max_depth(depth + 1, maxdepth); + } else { + maxdepth = MAX(maxdepth, depth); + } + } + + // + int count_leaves() const { + if (is_internal()) + return childs[0]->count_leaves() + childs[1]->count_leaves(); + else + return (1); + } + + bool is_left_of_axis(const Vector3 &org, const Vector3 &axis) const { + return axis.dot(volume.get_center() - org) <= 0; + } + + Node() { + childs[0] = nullptr; + childs[1] = nullptr; + } + }; + + PagedAllocator<Node> node_allocator; + // Fields + Node *bvh_root = nullptr; + int lkhd = -1; + int total_leaves = 0; + uint32_t opath = 0; + uint32_t index = 0; + + enum { + ALLOCA_STACK_SIZE = 128 + }; + + _FORCE_INLINE_ void _delete_node(Node *p_node); + void _recurse_delete_node(Node *p_node); + _FORCE_INLINE_ Node *_create_node(Node *p_parent, void *p_data); + _FORCE_INLINE_ DynamicBVH::Node *_create_node_with_volume(Node *p_parent, const Volume &p_volume, void *p_data); + _FORCE_INLINE_ void _insert_leaf(Node *p_root, Node *p_leaf); + _FORCE_INLINE_ Node *_remove_leaf(Node *leaf); + void _fetch_leaves(Node *p_root, LocalVector<Node *> &r_leaves, int p_depth = -1); + static int _split(Node **leaves, int p_count, const Vector3 &p_org, const Vector3 &p_axis); + static Volume _bounds(Node **leaves, int p_count); + void _bottom_up(Node **leaves, int p_count); + Node *_top_down(Node **leaves, int p_count, int p_bu_threshold); + Node *_node_sort(Node *n, Node *&r); + + _FORCE_INLINE_ void _update(Node *leaf, int lookahead = -1); + + void _extract_leaves(Node *p_node, List<ID> *r_elements); + + _FORCE_INLINE_ bool _ray_aabb(const Vector3 &rayFrom, const Vector3 &rayInvDirection, const unsigned int raySign[3], const Vector3 bounds[2], real_t &tmin, real_t lambda_min, real_t lambda_max) { + real_t tmax, tymin, tymax, tzmin, tzmax; + tmin = (bounds[raySign[0]].x - rayFrom.x) * rayInvDirection.x; + tmax = (bounds[1 - raySign[0]].x - rayFrom.x) * rayInvDirection.x; + tymin = (bounds[raySign[1]].y - rayFrom.y) * rayInvDirection.y; + tymax = (bounds[1 - raySign[1]].y - rayFrom.y) * rayInvDirection.y; + + if ((tmin > tymax) || (tymin > tmax)) + return false; + + if (tymin > tmin) + tmin = tymin; + + if (tymax < tmax) + tmax = tymax; + + tzmin = (bounds[raySign[2]].z - rayFrom.z) * rayInvDirection.z; + tzmax = (bounds[1 - raySign[2]].z - rayFrom.z) * rayInvDirection.z; + + if ((tmin > tzmax) || (tzmin > tmax)) + return false; + if (tzmin > tmin) + tmin = tzmin; + if (tzmax < tmax) + tmax = tzmax; + return ((tmin < lambda_max) && (tmax > lambda_min)); + } + +public: + // Methods + void clear(); + bool empty() const { return (0 == bvh_root); } + void optimize_bottom_up(); + void optimize_top_down(int bu_threshold = 128); + void optimize_incremental(int passes); + ID insert(const AABB &p_box, void *p_userdata); + bool update(const ID &p_id, const AABB &p_box); + void remove(const ID &p_id); + void get_elements(List<ID> *r_elements); + + int get_leaf_count() const; + int get_max_depth() const; + + /* Discouraged, but works as a reference on how it must be used */ + struct DefaultQueryResult { + virtual bool operator()(void *p_data) = 0; //return true whether you want to continue the query + virtual ~DefaultQueryResult() {} + }; + + template <class QueryResult> + _FORCE_INLINE_ void aabb_query(const AABB &p_aabb, QueryResult &r_result); + template <class QueryResult> + _FORCE_INLINE_ void convex_query(const Plane *p_planes, int p_plane_count, const Vector3 *p_points, int p_point_count, QueryResult &r_result); + template <class QueryResult> + _FORCE_INLINE_ void ray_query(const Vector3 &p_from, const Vector3 &p_to, QueryResult &r_result); + + void set_index(uint32_t p_index); + uint32_t get_index() const; + + ~DynamicBVH(); +}; + +template <class QueryResult> +void DynamicBVH::aabb_query(const AABB &p_box, QueryResult &r_result) { + if (!bvh_root) { + return; + } + + Volume volume; + volume.min = p_box.position; + volume.max = p_box.position + p_box.size; + + const Node **stack = (const Node **)alloca(ALLOCA_STACK_SIZE * sizeof(const Node *)); + stack[0] = bvh_root; + int32_t depth = 1; + int32_t threshold = ALLOCA_STACK_SIZE - 2; + + LocalVector<const Node *> aux_stack; //only used in rare occasions when you run out of alloca memory because tree is too unbalanced. Should correct itself over time. + + do { + depth--; + const Node *n = stack[depth]; + if (n->volume.intersects(volume)) { + if (n->is_internal()) { + if (depth > threshold) { + if (aux_stack.empty()) { + aux_stack.resize(ALLOCA_STACK_SIZE * 2); + copymem(aux_stack.ptr(), stack, ALLOCA_STACK_SIZE * sizeof(const Node *)); + } else { + aux_stack.resize(aux_stack.size() * 2); + } + stack = aux_stack.ptr(); + threshold = aux_stack.size() - 2; + } + stack[depth++] = n->childs[0]; + stack[depth++] = n->childs[1]; + } else { + if (r_result(n->data)) { + return; + } + } + } + } while (depth > 0); +} + +template <class QueryResult> +void DynamicBVH::convex_query(const Plane *p_planes, int p_plane_count, const Vector3 *p_points, int p_point_count, QueryResult &r_result) { + if (!bvh_root) { + return; + } + + //generate a volume anyway to improve pre-testing + Volume volume; + for (int i = 0; i < p_point_count; i++) { + if (i == 0) { + volume.min = p_points[0]; + volume.max = p_points[0]; + } else { + volume.min.x = MIN(volume.min.x, p_points[i].x); + volume.min.y = MIN(volume.min.y, p_points[i].y); + volume.min.z = MIN(volume.min.z, p_points[i].z); + + volume.max.x = MAX(volume.max.x, p_points[i].x); + volume.max.y = MAX(volume.max.y, p_points[i].y); + volume.max.z = MAX(volume.max.z, p_points[i].z); + } + } + + const Node **stack = (const Node **)alloca(ALLOCA_STACK_SIZE * sizeof(const Node *)); + stack[0] = bvh_root; + int32_t depth = 1; + int32_t threshold = ALLOCA_STACK_SIZE - 2; + + LocalVector<const Node *> aux_stack; //only used in rare occasions when you run out of alloca memory because tree is too unbalanced. Should correct itself over time. + + do { + depth--; + const Node *n = stack[depth]; + if (n->volume.intersects(volume) && n->volume.intersects_convex(p_planes, p_plane_count, p_points, p_point_count)) { + if (n->is_internal()) { + if (depth > threshold) { + if (aux_stack.empty()) { + aux_stack.resize(ALLOCA_STACK_SIZE * 2); + copymem(aux_stack.ptr(), stack, ALLOCA_STACK_SIZE * sizeof(const Node *)); + } else { + aux_stack.resize(aux_stack.size() * 2); + } + stack = aux_stack.ptr(); + threshold = aux_stack.size() - 2; + } + stack[depth++] = n->childs[0]; + stack[depth++] = n->childs[1]; + } else { + if (r_result(n->data)) { + return; + } + } + } + } while (depth > 0); +} +template <class QueryResult> +void DynamicBVH::ray_query(const Vector3 &p_from, const Vector3 &p_to, QueryResult &r_result) { + if (!bvh_root) { + return; + } + + Vector3 ray_dir = (p_to - p_from); + ray_dir.normalize(); + + ///what about division by zero? --> just set rayDirection[i] to INF/B3_LARGE_FLOAT + Vector3 inv_dir; + inv_dir[0] = ray_dir[0] == real_t(0.0) ? real_t(1e20) : real_t(1.0) / ray_dir[0]; + inv_dir[1] = ray_dir[1] == real_t(0.0) ? real_t(1e20) : real_t(1.0) / ray_dir[1]; + inv_dir[2] = ray_dir[2] == real_t(0.0) ? real_t(1e20) : real_t(1.0) / ray_dir[2]; + unsigned int signs[3] = { inv_dir[0] < 0.0, inv_dir[1] < 0.0, inv_dir[2] < 0.0 }; + + real_t lambda_max = ray_dir.dot(p_to - p_from); + + Vector3 bounds[2]; + + const Node **stack = (const Node **)alloca(ALLOCA_STACK_SIZE * sizeof(const Node *)); + stack[0] = bvh_root; + int32_t depth = 1; + int32_t threshold = ALLOCA_STACK_SIZE - 2; + + LocalVector<const Node *> aux_stack; //only used in rare occasions when you run out of alloca memory because tree is too unbalanced. Should correct itself over time. + + do { + depth--; + const Node *node = stack[depth]; + bounds[0] = node->volume.min; + bounds[1] = node->volume.max; + real_t tmin = 1.f, lambda_min = 0.f; + unsigned int result1 = false; + result1 = _ray_aabb(p_from, inv_dir, signs, bounds, tmin, lambda_min, lambda_max); + if (result1) { + if (node->is_internal()) { + if (depth > threshold) { + if (aux_stack.empty()) { + aux_stack.resize(ALLOCA_STACK_SIZE * 2); + copymem(aux_stack.ptr(), stack, ALLOCA_STACK_SIZE * sizeof(const Node *)); + } else { + aux_stack.resize(aux_stack.size() * 2); + } + stack = aux_stack.ptr(); + threshold = aux_stack.size() - 2; + } + stack[depth++] = node->childs[0]; + stack[depth++] = node->childs[1]; + } else { + if (r_result(node->data)) { + return; + } + } + } + } while (depth > 0); +} + +#endif // DYNAMICBVH_H diff --git a/core/math/math_defs.h b/core/math/math_defs.h index 4d97f72ebf..0478de732a 100644 --- a/core/math/math_defs.h +++ b/core/math/math_defs.h @@ -83,11 +83,11 @@ enum VAlign { VALIGN_BOTTOM }; -enum Margin { - MARGIN_LEFT, - MARGIN_TOP, - MARGIN_RIGHT, - MARGIN_BOTTOM +enum Side { + SIDE_LEFT, + SIDE_TOP, + SIDE_RIGHT, + SIDE_BOTTOM }; enum Corner { diff --git a/core/math/math_funcs.h b/core/math/math_funcs.h index 827637bf2b..471aa58996 100644 --- a/core/math/math_funcs.h +++ b/core/math/math_funcs.h @@ -198,6 +198,23 @@ public: value += 0.0; return value; } + static _ALWAYS_INLINE_ float fposmodp(float p_x, float p_y) { + float value = Math::fmod(p_x, p_y); + if (value < 0) { + value += p_y; + } + value += 0.0; + return value; + } + static _ALWAYS_INLINE_ double fposmodp(double p_x, double p_y) { + double value = Math::fmod(p_x, p_y); + if (value < 0) { + value += p_y; + } + value += 0.0; + return value; + } + static _ALWAYS_INLINE_ int posmod(int p_x, int p_y) { int value = p_x % p_y; if ((value < 0 && p_y > 0) || (value > 0 && p_y < 0)) { diff --git a/core/math/random_pcg.cpp b/core/math/random_pcg.cpp index e0768b9403..c39037747a 100644 --- a/core/math/random_pcg.cpp +++ b/core/math/random_pcg.cpp @@ -51,16 +51,8 @@ float RandomPCG::random(float p_from, float p_to) { } int RandomPCG::random(int p_from, int p_to) { - int range; - int min; - if (p_to > p_from) { - range = p_to - p_from + 1; - min = p_from; - } else if (p_to < p_from) { - range = p_from - p_to + 1; - min = p_to; - } else { // from == to + if (p_from == p_to) { return p_from; } - return rand(range) + min; + return rand(abs(p_from - p_to) + 1) + MIN(p_from, p_to); } diff --git a/core/math/rect2.h b/core/math/rect2.h index b1fe865ba5..aecba9e88c 100644 --- a/core/math/rect2.h +++ b/core/math/rect2.h @@ -123,8 +123,9 @@ struct Rect2 { _FORCE_INLINE_ bool has_no_area() const { return (size.x <= 0 || size.y <= 0); } - inline Rect2 clip(const Rect2 &p_rect) const { /// return a clipped rect + // Returns the instersection between two Rect2s or an empty Rect2 if there is no intersection + inline Rect2 intersection(const Rect2 &p_rect) const { Rect2 new_rect = p_rect; if (!intersects(new_rect)) { @@ -188,17 +189,17 @@ struct Rect2 { return g; } - inline Rect2 grow_margin(Margin p_margin, real_t p_amount) const { + inline Rect2 grow_margin(Side p_side, real_t p_amount) const { Rect2 g = *this; - g = g.grow_individual((MARGIN_LEFT == p_margin) ? p_amount : 0, - (MARGIN_TOP == p_margin) ? p_amount : 0, - (MARGIN_RIGHT == p_margin) ? p_amount : 0, - (MARGIN_BOTTOM == p_margin) ? p_amount : 0); + g = g.grow_individual((SIDE_LEFT == p_side) ? p_amount : 0, + (SIDE_TOP == p_side) ? p_amount : 0, + (SIDE_RIGHT == p_side) ? p_amount : 0, + (SIDE_BOTTOM == p_side) ? p_amount : 0); return g; } - inline Rect2 grow_margin_bind(uint32_t p_margin, real_t p_amount) const { - return grow_margin(Margin(p_margin), p_amount); + inline Rect2 grow_margin_bind(uint32_t p_side, real_t p_amount) const { + return grow_margin(Side(p_side), p_amount); } inline Rect2 grow_individual(real_t p_left, real_t p_top, real_t p_right, real_t p_bottom) const { @@ -365,8 +366,9 @@ struct Rect2i { _FORCE_INLINE_ bool has_no_area() const { return (size.x <= 0 || size.y <= 0); } - inline Rect2i clip(const Rect2i &p_rect) const { /// return a clipped rect + // Returns the instersection between two Rect2is or an empty Rect2i if there is no intersection + inline Rect2i intersection(const Rect2i &p_rect) const { Rect2i new_rect = p_rect; if (!intersects(new_rect)) { @@ -429,17 +431,17 @@ struct Rect2i { return g; } - inline Rect2i grow_margin(Margin p_margin, int p_amount) const { + inline Rect2i grow_margin(Side p_side, int p_amount) const { Rect2i g = *this; - g = g.grow_individual((MARGIN_LEFT == p_margin) ? p_amount : 0, - (MARGIN_TOP == p_margin) ? p_amount : 0, - (MARGIN_RIGHT == p_margin) ? p_amount : 0, - (MARGIN_BOTTOM == p_margin) ? p_amount : 0); + g = g.grow_individual((SIDE_LEFT == p_side) ? p_amount : 0, + (SIDE_TOP == p_side) ? p_amount : 0, + (SIDE_RIGHT == p_side) ? p_amount : 0, + (SIDE_BOTTOM == p_side) ? p_amount : 0); return g; } - inline Rect2i grow_margin_bind(uint32_t p_margin, int p_amount) const { - return grow_margin(Margin(p_margin), p_amount); + inline Rect2i grow_margin_bind(uint32_t p_side, int p_amount) const { + return grow_margin(Side(p_side), p_amount); } inline Rect2i grow_individual(int p_left, int p_top, int p_right, int p_bottom) const { diff --git a/core/object/object.h b/core/object/object.h index dc004f38a9..6e2328848b 100644 --- a/core/object/object.h +++ b/core/object/object.h @@ -482,8 +482,6 @@ private: void _set_indexed_bind(const NodePath &p_name, const Variant &p_value); Variant _get_indexed_bind(const NodePath &p_name) const; - void property_list_changed_notify(); - _FORCE_INLINE_ void _construct_object(bool p_reference); friend class Reference; @@ -525,6 +523,7 @@ protected: static void get_valid_parents_static(List<String> *p_parents); static void _get_valid_parents_static(List<String> *p_parents); + void property_list_changed_notify(); virtual void _changed_callback(Object *p_changed, const char *p_prop); //Variant _call_bind(const StringName& p_name, const Variant& p_arg1 = Variant(), const Variant& p_arg2 = Variant(), const Variant& p_arg3 = Variant(), const Variant& p_arg4 = Variant()); diff --git a/core/object/undo_redo.cpp b/core/object/undo_redo.cpp index 1dcbb0cd6b..65bae6f6e8 100644 --- a/core/object/undo_redo.cpp +++ b/core/object/undo_redo.cpp @@ -30,6 +30,7 @@ #include "undo_redo.h" +#include "core/io/resource.h" #include "core/os/os.h" void UndoRedo::_discard_redo() { @@ -104,8 +105,8 @@ void UndoRedo::add_do_method(Object *p_object, const StringName &p_method, VARIA ERR_FAIL_COND((current_action + 1) >= actions.size()); Operation do_op; do_op.object = p_object->get_instance_id(); - if (Object::cast_to<Resource>(p_object)) { - do_op.resref = Ref<Resource>(Object::cast_to<Resource>(p_object)); + if (Object::cast_to<Reference>(p_object)) { + do_op.ref = Ref<Reference>(Object::cast_to<Reference>(p_object)); } do_op.type = Operation::TYPE_METHOD; @@ -130,8 +131,8 @@ void UndoRedo::add_undo_method(Object *p_object, const StringName &p_method, VAR Operation undo_op; undo_op.object = p_object->get_instance_id(); - if (Object::cast_to<Resource>(p_object)) { - undo_op.resref = Ref<Resource>(Object::cast_to<Resource>(p_object)); + if (Object::cast_to<Reference>(p_object)) { + undo_op.ref = Ref<Reference>(Object::cast_to<Reference>(p_object)); } undo_op.type = Operation::TYPE_METHOD; @@ -149,8 +150,8 @@ void UndoRedo::add_do_property(Object *p_object, const StringName &p_property, c ERR_FAIL_COND((current_action + 1) >= actions.size()); Operation do_op; do_op.object = p_object->get_instance_id(); - if (Object::cast_to<Resource>(p_object)) { - do_op.resref = Ref<Resource>(Object::cast_to<Resource>(p_object)); + if (Object::cast_to<Reference>(p_object)) { + do_op.ref = Ref<Reference>(Object::cast_to<Reference>(p_object)); } do_op.type = Operation::TYPE_PROPERTY; @@ -171,8 +172,8 @@ void UndoRedo::add_undo_property(Object *p_object, const StringName &p_property, Operation undo_op; undo_op.object = p_object->get_instance_id(); - if (Object::cast_to<Resource>(p_object)) { - undo_op.resref = Ref<Resource>(Object::cast_to<Resource>(p_object)); + if (Object::cast_to<Reference>(p_object)) { + undo_op.ref = Ref<Reference>(Object::cast_to<Reference>(p_object)); } undo_op.type = Operation::TYPE_PROPERTY; @@ -187,8 +188,8 @@ void UndoRedo::add_do_reference(Object *p_object) { ERR_FAIL_COND((current_action + 1) >= actions.size()); Operation do_op; do_op.object = p_object->get_instance_id(); - if (Object::cast_to<Resource>(p_object)) { - do_op.resref = Ref<Resource>(Object::cast_to<Resource>(p_object)); + if (Object::cast_to<Reference>(p_object)) { + do_op.ref = Ref<Reference>(Object::cast_to<Reference>(p_object)); } do_op.type = Operation::TYPE_REFERENCE; @@ -207,8 +208,8 @@ void UndoRedo::add_undo_reference(Object *p_object) { Operation undo_op; undo_op.object = p_object->get_instance_id(); - if (Object::cast_to<Resource>(p_object)) { - undo_op.resref = Ref<Resource>(Object::cast_to<Resource>(p_object)); + if (Object::cast_to<Reference>(p_object)) { + undo_op.ref = Ref<Reference>(Object::cast_to<Reference>(p_object)); } undo_op.type = Operation::TYPE_REFERENCE; diff --git a/core/object/undo_redo.h b/core/object/undo_redo.h index 68d78e0d7d..06c2759a65 100644 --- a/core/object/undo_redo.h +++ b/core/object/undo_redo.h @@ -31,8 +31,8 @@ #ifndef UNDO_REDO_H #define UNDO_REDO_H -#include "core/io/resource.h" #include "core/object/class_db.h" +#include "core/object/reference.h" class UndoRedo : public Object { GDCLASS(UndoRedo, Object); @@ -61,7 +61,7 @@ private: }; Type type; - Ref<Resource> resref; + Ref<Reference> ref; ObjectID object; StringName name; Variant args[VARIANT_ARG_MAX]; diff --git a/core/string/ustring.cpp b/core/string/ustring.cpp index d630e987ea..fee168993b 100644 --- a/core/string/ustring.cpp +++ b/core/string/ustring.cpp @@ -4285,7 +4285,10 @@ bool String::is_rel_path() const { } String String::get_base_dir() const { - int basepos = find("://"); + int basepos = find(":/"); + if (basepos == -1) { + basepos = find(":\\"); + } String rs; String base; if (basepos != -1) { diff --git a/core/templates/paged_allocator.h b/core/templates/paged_allocator.h new file mode 100644 index 0000000000..ab9945dd3b --- /dev/null +++ b/core/templates/paged_allocator.h @@ -0,0 +1,129 @@ +/*************************************************************************/ +/* paged_allocator.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef PAGED_ALLOCATOR_H +#define PAGED_ALLOCATOR_H + +#include "core/os/memory.h" +#include "core/os/spin_lock.h" +#include "core/typedefs.h" + +template <class T, bool thread_safe = false> +class PagedAllocator { + T **page_pool = nullptr; + T ***available_pool = nullptr; + uint32_t pages_allocated = 0; + uint32_t allocs_available = 0; + + uint32_t page_shift = 0; + uint32_t page_mask = 0; + uint32_t page_size = 0; + SpinLock spin_lock; + +public: + T *alloc() { + if (thread_safe) { + spin_lock.lock(); + } + if (unlikely(allocs_available == 0)) { + uint32_t pages_used = pages_allocated; + + pages_allocated++; + page_pool = (T **)memrealloc(page_pool, sizeof(T *) * pages_allocated); + available_pool = (T ***)memrealloc(available_pool, sizeof(T **) * pages_allocated); + + page_pool[pages_used] = (T *)memalloc(sizeof(T) * page_size); + available_pool[pages_used] = (T **)memalloc(sizeof(T *) * page_size); + + for (uint32_t i = 0; i < page_size; i++) { + available_pool[0][i] = &page_pool[pages_used][i]; + } + allocs_available += page_size; + } + + allocs_available--; + T *alloc = available_pool[allocs_available >> page_shift][allocs_available & page_mask]; + if (thread_safe) { + spin_lock.unlock(); + } + memnew_placement(alloc, T); + return alloc; + } + + void free(T *p_mem) { + if (thread_safe) { + spin_lock.lock(); + } + p_mem->~T(); + available_pool[allocs_available >> page_shift][allocs_available & page_mask] = p_mem; + if (thread_safe) { + spin_lock.unlock(); + } + allocs_available++; + } + + void reset() { + ERR_FAIL_COND(allocs_available < pages_allocated * page_size); + if (pages_allocated) { + for (uint32_t i = 0; i < pages_allocated; i++) { + memfree(page_pool[i]); + memfree(available_pool[i]); + } + memfree(page_pool); + memfree(available_pool); + page_pool = nullptr; + available_pool = nullptr; + pages_allocated = 0; + allocs_available = 0; + } + } + bool is_configured() const { + return page_size > 0; + } + + void configure(uint32_t p_page_size) { + ERR_FAIL_COND(page_pool != nullptr); //sanity check + ERR_FAIL_COND(p_page_size == 0); + page_size = nearest_power_of_2_templated(p_page_size); + page_mask = page_size - 1; + page_shift = get_shift_from_power_of_2(page_size); + } + + PagedAllocator(uint32_t p_page_size = 4096) { // power of 2 recommended because of alignment with OS page sizes. Even if element is bigger, its still a multiple and get rounded amount of pages + configure(p_page_size); + } + + ~PagedAllocator() { + ERR_FAIL_COND_MSG(allocs_available < pages_allocated * page_size, "Pages in use exist at exit in PagedAllocator"); + reset(); + } +}; + +#endif // PAGED_ALLOCATOR_H diff --git a/core/templates/paged_array.h b/core/templates/paged_array.h new file mode 100644 index 0000000000..aaf3893715 --- /dev/null +++ b/core/templates/paged_array.h @@ -0,0 +1,349 @@ +/*************************************************************************/ +/* paged_array.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef PAGED_ARRAY_H +#define PAGED_ARRAY_H + +#include "core/os/memory.h" +#include "core/os/spin_lock.h" +#include "core/typedefs.h" + +// PagedArray is used mainly for filling a very large array from multiple threads efficiently and without causing major fragmentation + +// PageArrayPool manages central page allocation in a thread safe matter + +template <class T> +class PagedArrayPool { + T **page_pool = nullptr; + uint32_t pages_allocated = 0; + + uint32_t *available_page_pool = nullptr; + uint32_t pages_available = 0; + + uint32_t page_size = 0; + SpinLock spin_lock; + +public: + uint32_t alloc_page() { + spin_lock.lock(); + if (unlikely(pages_available == 0)) { + uint32_t pages_used = pages_allocated; + + pages_allocated++; + page_pool = (T **)memrealloc(page_pool, sizeof(T *) * pages_allocated); + available_page_pool = (uint32_t *)memrealloc(available_page_pool, sizeof(uint32_t) * pages_allocated); + + page_pool[pages_used] = (T *)memalloc(sizeof(T) * page_size); + available_page_pool[0] = pages_used; + + pages_available++; + } + + pages_available--; + uint32_t page = available_page_pool[pages_available]; + spin_lock.unlock(); + + return page; + } + T *get_page(uint32_t p_page_id) { + return page_pool[p_page_id]; + } + + void free_page(uint32_t p_page_id) { + spin_lock.lock(); + available_page_pool[pages_available] = p_page_id; + pages_available++; + spin_lock.unlock(); + } + + uint32_t get_page_size_shift() const { + return get_shift_from_power_of_2(page_size); + } + + uint32_t get_page_size_mask() const { + return page_size - 1; + } + + void reset() { + ERR_FAIL_COND(pages_available < pages_allocated); + if (pages_allocated) { + for (uint32_t i = 0; i < pages_allocated; i++) { + memfree(page_pool[i]); + } + memfree(page_pool); + memfree(available_page_pool); + page_pool = nullptr; + available_page_pool = nullptr; + pages_allocated = 0; + pages_available = 0; + } + } + bool is_configured() const { + return page_size > 0; + } + + void configure(uint32_t p_page_size) { + ERR_FAIL_COND(page_pool != nullptr); //sanity check + ERR_FAIL_COND(p_page_size == 0); + page_size = nearest_power_of_2_templated(p_page_size); + } + + PagedArrayPool(uint32_t p_page_size = 4096) { // power of 2 recommended because of alignment with OS page sizes. Even if element is bigger, its still a multiple and get rounded amount of pages + configure(p_page_size); + } + + ~PagedArrayPool() { + ERR_FAIL_COND_MSG(pages_available < pages_allocated, "Pages in use exist at exit in PagedArrayPool"); + reset(); + } +}; + +// PageArray is a local array that is optimized to grow in place, then be cleared often. +// It does so by allocating pages from a PagedArrayPool. +// It is safe to use multiple PagedArrays from different threads, sharing a single PagedArrayPool + +template <class T> +class PagedArray { + PagedArrayPool<T> *page_pool = nullptr; + + T **page_data = nullptr; + uint32_t *page_ids = nullptr; + uint32_t max_pages_used = 0; + uint32_t page_size_shift = 0; + uint32_t page_size_mask = 0; + uint64_t count = 0; + + _FORCE_INLINE_ uint32_t _get_pages_in_use() const { + if (count == 0) { + return 0; + } else { + return ((count - 1) >> page_size_shift) + 1; + } + } + + void _grow_page_array() { + //no more room in the page array to put the new page, make room + if (max_pages_used == 0) { + max_pages_used = 1; + } else { + max_pages_used *= 2; // increase in powers of 2 to keep allocations to minimum + } + page_data = (T **)memrealloc(page_data, sizeof(T *) * max_pages_used); + page_ids = (uint32_t *)memrealloc(page_ids, sizeof(uint32_t) * max_pages_used); + } + +public: + _FORCE_INLINE_ const T &operator[](uint64_t p_index) const { + CRASH_BAD_UNSIGNED_INDEX(p_index, count); + uint32_t page = p_index >> page_size_shift; + uint32_t offset = p_index & page_size_mask; + + return page_data[page][offset]; + } + _FORCE_INLINE_ T &operator[](uint64_t p_index) { + CRASH_BAD_UNSIGNED_INDEX(p_index, count); + uint32_t page = p_index >> page_size_shift; + uint32_t offset = p_index & page_size_mask; + + return page_data[page][offset]; + } + + _FORCE_INLINE_ void push_back(const T &p_value) { + uint32_t remainder = count & page_size_mask; + if (unlikely(remainder == 0)) { + // at 0, so time to request a new page + uint32_t page_count = _get_pages_in_use(); + uint32_t new_page_count = page_count + 1; + + if (unlikely(new_page_count > max_pages_used)) { + ERR_FAIL_COND(page_pool == nullptr); //sanity check + + _grow_page_array(); //keep out of inline + } + + uint32_t page_id = page_pool->alloc_page(); + page_data[page_count] = page_pool->get_page(page_id); + page_ids[page_count] = page_id; + } + + // place the new value + uint32_t page = count >> page_size_shift; + uint32_t offset = count & page_size_mask; + + if (!__has_trivial_constructor(T)) { + memnew_placement(&page_data[page][offset], T(p_value)); + } else { + page_data[page][offset] = p_value; + } + + count++; + } + + void clear() { + //destruct if needed + if (!__has_trivial_destructor(T)) { + for (uint64_t i = 0; i < count; i++) { + uint32_t page = i >> page_size_shift; + uint32_t offset = i & page_size_mask; + page_data[page][offset].~T(); + } + } + + //return the pages to the pagepool, so they can be used by another array eventually + uint32_t pages_used = _get_pages_in_use(); + for (uint32_t i = 0; i < pages_used; i++) { + page_pool->free_page(page_ids[i]); + } + + count = 0; + + //note we leave page_data and page_indices intact for next use. If you really want to clear them call reset() + } + + void reset() { + clear(); + if (page_data) { + memfree(page_data); + memfree(page_ids); + page_data = nullptr; + page_ids = nullptr; + max_pages_used = 0; + } + } + + // This takes the pages from a source array and merges them to this one + // resulting order is undefined, but content is merged very efficiently, + // making it ideal to fill content on several threads to later join it. + + void merge_unordered(PagedArray<T> &p_array) { + ERR_FAIL_COND(page_pool != p_array.page_pool); + + uint32_t remainder = count & page_size_mask; + + T *remainder_page = nullptr; + uint32_t remainder_page_id; + + if (remainder > 0) { + uint32_t last_page = _get_pages_in_use() - 1; + remainder_page = page_data[last_page]; + remainder_page_id = page_ids[last_page]; + } + + count -= remainder; + + uint32_t src_pages = p_array._get_pages_in_use(); + uint32_t page_size = page_size_mask + 1; + + for (uint32_t i = 0; i < src_pages; i++) { + uint32_t page_count = _get_pages_in_use(); + uint32_t new_page_count = page_count + 1; + + if (unlikely(new_page_count > max_pages_used)) { + _grow_page_array(); //keep out of inline + } + + page_data[page_count] = p_array.page_data[i]; + page_ids[page_count] = p_array.page_ids[i]; + if (i == src_pages - 1) { + //last page, only increment with remainder + count += p_array.count & page_size_mask; + } else { + count += page_size; + } + } + p_array.count = 0; //take away the other array pages + + //handle the remainder page if exists + if (remainder_page) { + uint32_t new_remainder = count & page_size_mask; + + if (new_remainder > 0) { + //must merge old remainder with new remainder + + T *dst_page = page_data[_get_pages_in_use() - 1]; + uint32_t to_copy = MIN(page_size - new_remainder, remainder); + + for (uint32_t i = 0; i < to_copy; i++) { + if (!__has_trivial_constructor(T)) { + memnew_placement(&dst_page[i + new_remainder], T(remainder_page[i + remainder - to_copy])); + } else { + dst_page[i + new_remainder] = remainder_page[i + remainder - to_copy]; + } + + if (!__has_trivial_destructor(T)) { + remainder_page[i + remainder - to_copy].~T(); + } + } + + remainder -= to_copy; //subtract what was copied from remainder + count += to_copy; //add what was copied to the count + + if (remainder == 0) { + //entire remainder copied, let go of remainder page + page_pool->free_page(remainder_page_id); + remainder_page = nullptr; + } + } + + if (remainder > 0) { + //there is still remainder, append it + uint32_t page_count = _get_pages_in_use(); + uint32_t new_page_count = page_count + 1; + + if (unlikely(new_page_count > max_pages_used)) { + _grow_page_array(); //keep out of inline + } + + page_data[page_count] = remainder_page; + page_ids[page_count] = remainder_page_id; + + count += remainder; + } + } + } + + _FORCE_INLINE_ uint64_t size() const { + return count; + } + + void set_page_pool(PagedArrayPool<T> *p_page_pool) { + ERR_FAIL_COND(max_pages_used > 0); //sanity check + + page_pool = p_page_pool; + page_size_mask = page_pool->get_page_size_mask(); + page_size_shift = page_pool->get_page_size_shift(); + } + + ~PagedArray() { + reset(); + } +}; + +#endif // PAGED_ARRAY_H diff --git a/core/templates/rid_owner.h b/core/templates/rid_owner.h index d1bcb92010..7de4e43648 100644 --- a/core/templates/rid_owner.h +++ b/core/templates/rid_owner.h @@ -346,6 +346,18 @@ public: alloc.free(p_rid); } + _FORCE_INLINE_ uint32_t get_rid_count() const { + return alloc.get_rid_count(); + } + + _FORCE_INLINE_ RID get_rid_by_index(uint32_t p_index) { + return alloc.get_rid_by_index(p_index); + } + + _FORCE_INLINE_ T *get_ptr_by_index(uint32_t p_index) { + return *alloc.get_ptr_by_index(p_index); + } + _FORCE_INLINE_ void get_owned_list(List<RID> *p_owned) { return alloc.get_owned_list(p_owned); } @@ -353,6 +365,7 @@ public: void set_description(const char *p_descrption) { alloc.set_description(p_descrption); } + RID_PtrOwner(uint32_t p_target_chunk_byte_size = 4096) : alloc(p_target_chunk_byte_size) {} }; diff --git a/core/templates/vector.h b/core/templates/vector.h index 9d45f7c30a..7420384bf7 100644 --- a/core/templates/vector.h +++ b/core/templates/vector.h @@ -112,6 +112,10 @@ public: sort_custom<_DefaultComparator<T>>(); } + Vector<T> duplicate() { + return *this; + } + void ordered_insert(const T &p_val) { int i; for (i = 0; i < _cowdata.size(); i++) { diff --git a/core/variant/binder_common.h b/core/variant/binder_common.h index e950709526..95113c89ba 100644 --- a/core/variant/binder_common.h +++ b/core/variant/binder_common.h @@ -87,7 +87,7 @@ VARIANT_ENUM_CAST(Object::ConnectFlags); VARIANT_ENUM_CAST(Vector3::Axis); VARIANT_ENUM_CAST(Error); -VARIANT_ENUM_CAST(Margin); +VARIANT_ENUM_CAST(Side); VARIANT_ENUM_CAST(Corner); VARIANT_ENUM_CAST(Orientation); VARIANT_ENUM_CAST(HAlign); diff --git a/core/variant/variant.cpp b/core/variant/variant.cpp index 741d05c139..9eb512f71d 100644 --- a/core/variant/variant.cpp +++ b/core/variant/variant.cpp @@ -2338,8 +2338,8 @@ Variant::operator Vector<StringName>() const { return to; } -Variant::operator Margin() const { - return (Margin) operator int(); +Variant::operator Side() const { + return (Side) operator int(); } Variant::operator Orientation() const { diff --git a/core/variant/variant.h b/core/variant/variant.h index 76c936a7bd..b22488a877 100644 --- a/core/variant/variant.h +++ b/core/variant/variant.h @@ -356,7 +356,7 @@ public: operator Vector<Vector2>() const; // some core type enums to convert to - operator Margin() const; + operator Side() const; operator Orientation() const; operator IP_Address() const; diff --git a/core/variant/variant_call.cpp b/core/variant/variant_call.cpp index d588c83809..afe4f2702e 100644 --- a/core/variant/variant_call.cpp +++ b/core/variant/variant_call.cpp @@ -1021,7 +1021,7 @@ static void _register_variant_builtin_methods() { bind_method(Rect2, is_equal_approx, sarray("rect"), varray()); bind_method(Rect2, intersects, sarray("b", "include_borders"), varray(false)); bind_method(Rect2, encloses, sarray("b"), varray()); - bind_method(Rect2, clip, sarray("b"), varray()); + bind_method(Rect2, intersection, sarray("b"), varray()); bind_method(Rect2, merge, sarray("b"), varray()); bind_method(Rect2, expand, sarray("to"), varray()); bind_method(Rect2, grow, sarray("by"), varray()); @@ -1036,7 +1036,7 @@ static void _register_variant_builtin_methods() { bind_method(Rect2i, has_point, sarray("point"), varray()); bind_method(Rect2i, intersects, sarray("b"), varray()); bind_method(Rect2i, encloses, sarray("b"), varray()); - bind_method(Rect2i, clip, sarray("b"), varray()); + bind_method(Rect2i, intersection, sarray("b"), varray()); bind_method(Rect2i, merge, sarray("b"), varray()); bind_method(Rect2i, expand, sarray("to"), varray()); bind_method(Rect2i, grow, sarray("by"), varray()); @@ -1316,6 +1316,7 @@ static void _register_variant_builtin_methods() { bind_method(PackedByteArray, invert, sarray(), varray()); bind_method(PackedByteArray, subarray, sarray("from", "to"), varray()); bind_method(PackedByteArray, sort, sarray(), varray()); + bind_method(PackedByteArray, duplicate, sarray(), varray()); bind_function(PackedByteArray, get_string_from_ascii, _VariantCall::func_PackedByteArray_get_string_from_ascii, sarray(), varray()); bind_function(PackedByteArray, get_string_from_utf8, _VariantCall::func_PackedByteArray_get_string_from_utf8, sarray(), varray()); @@ -1342,6 +1343,7 @@ static void _register_variant_builtin_methods() { bind_method(PackedInt32Array, subarray, sarray("from", "to"), varray()); bind_method(PackedInt32Array, to_byte_array, sarray(), varray()); bind_method(PackedInt32Array, sort, sarray(), varray()); + bind_method(PackedInt32Array, duplicate, sarray(), varray()); /* Int64 Array */ @@ -1359,6 +1361,7 @@ static void _register_variant_builtin_methods() { bind_method(PackedInt64Array, subarray, sarray("from", "to"), varray()); bind_method(PackedInt64Array, to_byte_array, sarray(), varray()); bind_method(PackedInt64Array, sort, sarray(), varray()); + bind_method(PackedInt64Array, duplicate, sarray(), varray()); /* Float32 Array */ @@ -1376,6 +1379,7 @@ static void _register_variant_builtin_methods() { bind_method(PackedFloat32Array, subarray, sarray("from", "to"), varray()); bind_method(PackedFloat32Array, to_byte_array, sarray(), varray()); bind_method(PackedFloat32Array, sort, sarray(), varray()); + bind_method(PackedFloat32Array, duplicate, sarray(), varray()); /* Float64 Array */ @@ -1393,6 +1397,7 @@ static void _register_variant_builtin_methods() { bind_method(PackedFloat64Array, subarray, sarray("from", "to"), varray()); bind_method(PackedFloat64Array, to_byte_array, sarray(), varray()); bind_method(PackedFloat64Array, sort, sarray(), varray()); + bind_method(PackedFloat64Array, duplicate, sarray(), varray()); /* String Array */ @@ -1410,6 +1415,7 @@ static void _register_variant_builtin_methods() { bind_method(PackedStringArray, subarray, sarray("from", "to"), varray()); bind_method(PackedStringArray, to_byte_array, sarray(), varray()); bind_method(PackedStringArray, sort, sarray(), varray()); + bind_method(PackedStringArray, duplicate, sarray(), varray()); /* Vector2 Array */ @@ -1427,6 +1433,7 @@ static void _register_variant_builtin_methods() { bind_method(PackedVector2Array, subarray, sarray("from", "to"), varray()); bind_method(PackedVector2Array, to_byte_array, sarray(), varray()); bind_method(PackedVector2Array, sort, sarray(), varray()); + bind_method(PackedVector2Array, duplicate, sarray(), varray()); /* Vector3 Array */ @@ -1444,6 +1451,7 @@ static void _register_variant_builtin_methods() { bind_method(PackedVector3Array, subarray, sarray("from", "to"), varray()); bind_method(PackedVector3Array, to_byte_array, sarray(), varray()); bind_method(PackedVector3Array, sort, sarray(), varray()); + bind_method(PackedVector3Array, duplicate, sarray(), varray()); /* Color Array */ @@ -1461,6 +1469,7 @@ static void _register_variant_builtin_methods() { bind_method(PackedColorArray, subarray, sarray("from", "to"), varray()); bind_method(PackedColorArray, to_byte_array, sarray(), varray()); bind_method(PackedColorArray, sort, sarray(), varray()); + bind_method(PackedColorArray, duplicate, sarray(), varray()); /* Register constants */ diff --git a/core/variant/variant_internal.h b/core/variant/variant_internal.h index 804abf8fbc..57e8f8813f 100644 --- a/core/variant/variant_internal.h +++ b/core/variant/variant_internal.h @@ -743,7 +743,7 @@ VARIANT_ACCESSOR_NUMBER(int64_t) VARIANT_ACCESSOR_NUMBER(uint64_t) VARIANT_ACCESSOR_NUMBER(char32_t) VARIANT_ACCESSOR_NUMBER(Error) -VARIANT_ACCESSOR_NUMBER(Margin) +VARIANT_ACCESSOR_NUMBER(Side) template <> struct VariantInternalAccessor<ObjectID> { diff --git a/core/variant/variant_parser.cpp b/core/variant/variant_parser.cpp index 5a0bbf041b..00d81f597a 100644 --- a/core/variant/variant_parser.cpp +++ b/core/variant/variant_parser.cpp @@ -743,6 +743,8 @@ Error VariantParser::parse_value(Token &token, Variant &value, Stream *p_stream, return ERR_PARSE_ERROR; } + REF ref = REF(Object::cast_to<Reference>(obj)); + get_token(p_stream, token, line, r_err_str); if (token.type != TK_COMMA) { r_err_str = "Expected ',' after object type"; @@ -767,12 +769,7 @@ Error VariantParser::parse_value(Token &token, Variant &value, Stream *p_stream, } if (token2.type == TK_PARENTHESIS_CLOSE) { - Reference *reference = Object::cast_to<Reference>(obj); - if (reference) { - value = REF(reference); - } else { - value = obj; - } + value = ref.is_valid() ? Variant(ref) : Variant(obj); return OK; } diff --git a/core/variant/variant_setget.cpp b/core/variant/variant_setget.cpp index cee7465205..28cf8ef967 100644 --- a/core/variant/variant_setget.cpp +++ b/core/variant/variant_setget.cpp @@ -2023,6 +2023,24 @@ Variant Variant::duplicate(bool deep) const { return operator Dictionary().duplicate(deep); case ARRAY: return operator Array().duplicate(deep); + case PACKED_BYTE_ARRAY: + return operator Vector<uint8_t>().duplicate(); + case PACKED_INT32_ARRAY: + return operator Vector<int32_t>().duplicate(); + case PACKED_INT64_ARRAY: + return operator Vector<int64_t>().duplicate(); + case PACKED_FLOAT32_ARRAY: + return operator Vector<float>().duplicate(); + case PACKED_FLOAT64_ARRAY: + return operator Vector<double>().duplicate(); + case PACKED_STRING_ARRAY: + return operator Vector<String>().duplicate(); + case PACKED_VECTOR2_ARRAY: + return operator Vector<Vector2>().duplicate(); + case PACKED_VECTOR3_ARRAY: + return operator Vector<Vector3>().duplicate(); + case PACKED_COLOR_ARRAY: + return operator Vector<Color>().duplicate(); default: return *this; } |