diff options
Diffstat (limited to 'core')
-rw-r--r-- | core/math/dynamic_bvh.cpp | 25 | ||||
-rw-r--r-- | core/math/dynamic_bvh.h | 125 | ||||
-rw-r--r-- | core/templates/paged_allocator.h | 129 | ||||
-rw-r--r-- | core/templates/paged_array.h | 2 | ||||
-rw-r--r-- | core/templates/rid_owner.h | 13 |
5 files changed, 283 insertions, 11 deletions
diff --git a/core/math/dynamic_bvh.cpp b/core/math/dynamic_bvh.cpp index 8486415c81..5f87f75b61 100644 --- a/core/math/dynamic_bvh.cpp +++ b/core/math/dynamic_bvh.cpp @@ -49,7 +49,6 @@ DynamicBVH::Node *DynamicBVH::_create_node(Node *p_parent, void *p_data) { Node *node = memnew(Node); node->parent = p_parent; node->data = p_data; - node->childs[1] = 0; return (node); } @@ -335,6 +334,7 @@ DynamicBVH::ID DynamicBVH::insert(const AABB &p_box, void *p_userdata) { ID id; id.node = leaf; + return id; } @@ -389,12 +389,35 @@ void DynamicBVH::_extract_leaves(Node *p_node, List<ID> *r_elements) { } } +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 index 81d70d7469..cdea51c674 100644 --- a/core/math/dynamic_bvh.h +++ b/core/math/dynamic_bvh.h @@ -61,13 +61,10 @@ class DynamicBVH { public: struct ID { - Node *node; + Node *node = nullptr; public: _FORCE_INLINE_ bool is_valid() const { return node != nullptr; } - _FORCE_INLINE_ ID() { - node = nullptr; - } }; private: @@ -134,6 +131,48 @@ private: (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 { @@ -144,14 +183,14 @@ private: void *data; }; - _FORCE_INLINE_ bool is_leaf() const { return data != nullptr; } + _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; } - _FORCE_INLINE_ void get_max_depth(int depth, int &maxdepth) { + 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); @@ -183,6 +222,7 @@ private: int lkhd = -1; int total_leaves = 0; uint32_t opath = 0; + uint32_t index = 0; enum { ALLOCA_STACK_SIZE = 128 @@ -245,6 +285,9 @@ public: 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 @@ -254,9 +297,13 @@ public: 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); - DynamicBVH(); + void set_index(uint32_t p_index); + uint32_t get_index() const; + ~DynamicBVH(); }; @@ -278,8 +325,8 @@ void DynamicBVH::aabb_query(const AABB &p_box, QueryResult &r_result) { 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 { - const Node *n = stack[depth - 1]; depth--; + const Node *n = stack[depth]; if (n->volume.intersects(volume)) { if (n->is_internal()) { if (depth > threshold) { @@ -304,7 +351,66 @@ void DynamicBVH::aabb_query(const AABB &p_box, QueryResult &r_result) { } 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(); @@ -327,7 +433,8 @@ void DynamicBVH::ray_query(const Vector3 &p_from, const Vector3 &p_to, QueryResu 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 { - const Node *node = stack[--depth]; + 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; diff --git a/core/templates/paged_allocator.h b/core/templates/paged_allocator.h new file mode 100644 index 0000000000..8bd1eecdeb --- /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, bool p_thread_safe) { + 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, bool p_thread_safe = false) { // 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, false); + } + + ~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 index 71183c4ad8..aaf3893715 100644 --- a/core/templates/paged_array.h +++ b/core/templates/paged_array.h @@ -329,7 +329,7 @@ public: } } - uint64_t size() const { + _FORCE_INLINE_ uint64_t size() const { return count; } 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) {} }; |