summaryrefslogtreecommitdiff
path: root/core
diff options
context:
space:
mode:
Diffstat (limited to 'core')
-rw-r--r--core/math/dynamic_bvh.cpp25
-rw-r--r--core/math/dynamic_bvh.h125
-rw-r--r--core/templates/paged_allocator.h129
-rw-r--r--core/templates/paged_array.h2
-rw-r--r--core/templates/rid_owner.h13
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) {}
};
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 13:19:03 +0000