summaryrefslogtreecommitdiff
path: root/core/math
diff options
context:
space:
mode:
Diffstat (limited to 'core/math')
-rw-r--r--core/math/a_star.cpp8
-rw-r--r--core/math/a_star.h2
-rw-r--r--core/math/color.cpp2
-rw-r--r--core/math/disjoint_set.h52
-rw-r--r--core/math/geometry_3d.cpp2
-rw-r--r--core/math/octree.h6
-rw-r--r--core/math/quick_hull.cpp36
-rw-r--r--core/math/quick_hull.h9
-rw-r--r--core/math/static_raycaster.h2
-rw-r--r--core/math/triangle_mesh.cpp6
10 files changed, 66 insertions, 59 deletions
diff --git a/core/math/a_star.cpp b/core/math/a_star.cpp
index 284b4294ea..a3ee259030 100644
--- a/core/math/a_star.cpp
+++ b/core/math/a_star.cpp
@@ -151,7 +151,7 @@ void AStar3D::connect_points(int p_id, int p_with_id, bool bidirectional) {
s.direction = Segment::BIDIRECTIONAL;
}
- Set<Segment>::Element *element = segments.find(s);
+ RBSet<Segment>::Element *element = segments.find(s);
if (element != nullptr) {
s.direction |= element->get().direction;
if (s.direction == Segment::BIDIRECTIONAL) {
@@ -177,7 +177,7 @@ void AStar3D::disconnect_points(int p_id, int p_with_id, bool bidirectional) {
Segment s(p_id, p_with_id);
int remove_direction = bidirectional ? (int)Segment::BIDIRECTIONAL : s.direction;
- Set<Segment>::Element *element = segments.find(s);
+ RBSet<Segment>::Element *element = segments.find(s);
if (element != nullptr) {
// s is the new segment
// Erase the directions to be removed
@@ -235,7 +235,7 @@ Vector<int> AStar3D::get_point_connections(int p_id) {
bool AStar3D::are_points_connected(int p_id, int p_with_id, bool bidirectional) const {
Segment s(p_id, p_with_id);
- const Set<Segment>::Element *element = segments.find(s);
+ const RBSet<Segment>::Element *element = segments.find(s);
return element != nullptr &&
(bidirectional || (element->get().direction & s.direction) == s.direction);
@@ -293,7 +293,7 @@ Vector3 AStar3D::get_closest_position_in_segment(const Vector3 &p_point) const {
real_t closest_dist = 1e20;
Vector3 closest_point;
- for (const Set<Segment>::Element *E = segments.front(); E; E = E->next()) {
+ for (const RBSet<Segment>::Element *E = segments.front(); E; E = E->next()) {
Point *from_point = nullptr, *to_point = nullptr;
points.lookup(E->get().u, from_point);
points.lookup(E->get().v, to_point);
diff --git a/core/math/a_star.h b/core/math/a_star.h
index bb7112fb09..086be839b5 100644
--- a/core/math/a_star.h
+++ b/core/math/a_star.h
@@ -112,7 +112,7 @@ class AStar3D : public RefCounted {
uint64_t pass = 1;
OAHashMap<int, Point *> points;
- Set<Segment> segments;
+ RBSet<Segment> segments;
bool _solve(Point *begin_point, Point *end_point);
diff --git a/core/math/color.cpp b/core/math/color.cpp
index e32f9147d9..74552a2894 100644
--- a/core/math/color.cpp
+++ b/core/math/color.cpp
@@ -33,7 +33,7 @@
#include "color_names.inc"
#include "core/math/math_funcs.h"
#include "core/string/print_string.h"
-#include "core/templates/map.h"
+#include "core/templates/rb_map.h"
uint32_t Color::to_argb32() const {
uint32_t c = (uint8_t)Math::round(a * 255);
diff --git a/core/math/disjoint_set.h b/core/math/disjoint_set.h
index 8657dc068e..d07c08e45e 100644
--- a/core/math/disjoint_set.h
+++ b/core/math/disjoint_set.h
@@ -31,11 +31,11 @@
#ifndef DISJOINT_SET_H
#define DISJOINT_SET_H
-#include "core/templates/map.h"
+#include "core/templates/rb_map.h"
#include "core/templates/vector.h"
/* This DisjointSet class uses Find with path compression and Union by rank */
-template <typename T, class C = Comparator<T>, class AL = DefaultAllocator>
+template <typename T, class H = HashMapHasherDefault, class C = HashMapComparatorDefault<T>, class AL = DefaultAllocator>
class DisjointSet {
struct Element {
T object;
@@ -43,7 +43,7 @@ class DisjointSet {
int rank = 0;
};
- typedef Map<T, Element *, C, AL> MapT;
+ typedef HashMap<T, Element *, H, C> MapT;
MapT elements;
@@ -65,15 +65,15 @@ public:
/* FUNCTIONS */
-template <typename T, class C, class AL>
-DisjointSet<T, C, AL>::~DisjointSet() {
- for (typename MapT::Element *itr = elements.front(); itr != nullptr; itr = itr->next()) {
- memdelete_allocator<Element, AL>(itr->value());
+template <typename T, class H, class C, class AL>
+DisjointSet<T, H, C, AL>::~DisjointSet() {
+ for (KeyValue<T, Element *> &E : elements) {
+ memdelete_allocator<Element, AL>(E.value);
}
}
-template <typename T, class C, class AL>
-typename DisjointSet<T, C, AL>::Element *DisjointSet<T, C, AL>::get_parent(Element *element) {
+template <typename T, class H, class C, class AL>
+typename DisjointSet<T, H, C, AL>::Element *DisjointSet<T, H, C, AL>::get_parent(Element *element) {
if (element->parent != element) {
element->parent = get_parent(element->parent);
}
@@ -81,11 +81,11 @@ typename DisjointSet<T, C, AL>::Element *DisjointSet<T, C, AL>::get_parent(Eleme
return element->parent;
}
-template <typename T, class C, class AL>
-typename DisjointSet<T, C, AL>::Element *DisjointSet<T, C, AL>::insert_or_get(T object) {
- typename MapT::Element *itr = elements.find(object);
+template <typename T, class H, class C, class AL>
+typename DisjointSet<T, H, C, AL>::Element *DisjointSet<T, H, C, AL>::insert_or_get(T object) {
+ typename MapT::Iterator itr = elements.find(object);
if (itr != nullptr) {
- return itr->value();
+ return itr->value;
}
Element *new_element = memnew_allocator(Element, AL);
@@ -96,8 +96,8 @@ typename DisjointSet<T, C, AL>::Element *DisjointSet<T, C, AL>::insert_or_get(T
return new_element;
}
-template <typename T, class C, class AL>
-void DisjointSet<T, C, AL>::create_union(T a, T b) {
+template <typename T, class H, class C, class AL>
+void DisjointSet<T, H, C, AL>::create_union(T a, T b) {
Element *x = insert_or_get(a);
Element *y = insert_or_get(b);
@@ -121,28 +121,28 @@ void DisjointSet<T, C, AL>::create_union(T a, T b) {
}
}
-template <typename T, class C, class AL>
-void DisjointSet<T, C, AL>::get_representatives(Vector<T> &out_representatives) {
- for (typename MapT::Element *itr = elements.front(); itr != nullptr; itr = itr->next()) {
- Element *element = itr->value();
+template <typename T, class H, class C, class AL>
+void DisjointSet<T, H, C, AL>::get_representatives(Vector<T> &out_representatives) {
+ for (KeyValue<T, Element *> &E : elements) {
+ Element *element = E.value;
if (element->parent == element) {
out_representatives.push_back(element->object);
}
}
}
-template <typename T, class C, class AL>
-void DisjointSet<T, C, AL>::get_members(Vector<T> &out_members, T representative) {
- typename MapT::Element *rep_itr = elements.find(representative);
+template <typename T, class H, class C, class AL>
+void DisjointSet<T, H, C, AL>::get_members(Vector<T> &out_members, T representative) {
+ typename MapT::Iterator rep_itr = elements.find(representative);
ERR_FAIL_COND(rep_itr == nullptr);
- Element *rep_element = rep_itr->value();
+ Element *rep_element = rep_itr->value;
ERR_FAIL_COND(rep_element->parent != rep_element);
- for (typename MapT::Element *itr = elements.front(); itr != nullptr; itr = itr->next()) {
- Element *parent = get_parent(itr->value());
+ for (KeyValue<T, Element *> &E : elements) {
+ Element *parent = get_parent(E.value);
if (parent == rep_element) {
- out_members.push_back(itr->key());
+ out_members.push_back(E.key);
}
}
}
diff --git a/core/math/geometry_3d.cpp b/core/math/geometry_3d.cpp
index f76de079e4..ec96753c79 100644
--- a/core/math/geometry_3d.cpp
+++ b/core/math/geometry_3d.cpp
@@ -36,7 +36,7 @@
#include "thirdparty/misc/polypartition.h"
void Geometry3D::MeshData::optimize_vertices() {
- Map<int, int> vtx_remap;
+ HashMap<int, int> vtx_remap;
for (int i = 0; i < faces.size(); i++) {
for (int j = 0; j < faces[i].indices.size(); j++) {
diff --git a/core/math/octree.h b/core/math/octree.h
index 65ab9e2292..8dd103f109 100644
--- a/core/math/octree.h
+++ b/core/math/octree.h
@@ -36,7 +36,7 @@
#include "core/math/vector3.h"
#include "core/string/print_string.h"
#include "core/templates/list.h"
-#include "core/templates/map.h"
+#include "core/templates/rb_map.h"
#include "core/variant/variant.h"
typedef uint32_t OctreeElementID;
@@ -151,8 +151,8 @@ private:
typename List<PairData *, AL>::Element *eA, *eB;
};
- typedef Map<OctreeElementID, Element, Comparator<OctreeElementID>, AL> ElementMap;
- typedef Map<PairKey, PairData, Comparator<PairKey>, AL> PairMap;
+ typedef HashMap<OctreeElementID, Element, Comparator<OctreeElementID>, AL> ElementMap;
+ typedef HashMap<PairKey, PairData, Comparator<PairKey>, AL> PairMap;
ElementMap element_map;
PairMap pair_map;
diff --git a/core/math/quick_hull.cpp b/core/math/quick_hull.cpp
index 3614bfadf8..43744deeb0 100644
--- a/core/math/quick_hull.cpp
+++ b/core/math/quick_hull.cpp
@@ -30,7 +30,7 @@
#include "quick_hull.h"
-#include "core/templates/map.h"
+#include "core/templates/rb_map.h"
uint32_t QuickHull::debug_stop_after = 0xFFFFFFFF;
@@ -52,7 +52,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_
Vector<bool> valid_points;
valid_points.resize(p_points.size());
- Set<Vector3> valid_cache;
+ RBSet<Vector3> valid_cache;
for (int i = 0; i < p_points.size(); i++) {
Vector3 sp = p_points[i].snapped(Vector3(0.0001, 0.0001, 0.0001));
@@ -237,7 +237,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_
//find lit faces and lit edges
List<List<Face>::Element *> lit_faces; //lit face is a death sentence
- Map<Edge, FaceConnect> lit_edges; //create this on the flight, should not be that bad for performance and simplifies code a lot
+ HashMap<Edge, FaceConnect, Edge> lit_edges; //create this on the flight, should not be that bad for performance and simplifies code a lot
for (List<Face>::Element *E = faces.front(); E; E = E->next()) {
if (E->get().plane.distance_to(v) > 0) {
@@ -248,15 +248,15 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_
uint32_t b = E->get().vertices[(i + 1) % 3];
Edge e(a, b);
- Map<Edge, FaceConnect>::Element *F = lit_edges.find(e);
+ HashMap<Edge, FaceConnect, Edge>::Iterator F = lit_edges.find(e);
if (!F) {
F = lit_edges.insert(e, FaceConnect());
}
if (e.vertices[0] == a) {
//left
- F->get().left = E;
+ F->value.left = E;
} else {
- F->get().right = E;
+ F->value.right = E;
}
}
}
@@ -333,7 +333,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_
/* CREATE MESHDATA */
//make a map of edges again
- Map<Edge, RetFaceConnect> ret_edges;
+ HashMap<Edge, RetFaceConnect, Edge> ret_edges;
List<Geometry3D::MeshData::Face> ret_faces;
for (const Face &E : faces) {
@@ -351,15 +351,15 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_
uint32_t b = E.vertices[(i + 1) % 3];
Edge e(a, b);
- Map<Edge, RetFaceConnect>::Element *G = ret_edges.find(e);
+ HashMap<Edge, RetFaceConnect, Edge>::Iterator G = ret_edges.find(e);
if (!G) {
G = ret_edges.insert(e, RetFaceConnect());
}
if (e.vertices[0] == a) {
//left
- G->get().left = F;
+ G->value.left = F;
} else {
- G->get().right = F;
+ G->value.right = F;
}
}
}
@@ -374,10 +374,10 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_
int b = E->get().indices[(i + 1) % f.indices.size()];
Edge e(a, b);
- Map<Edge, RetFaceConnect>::Element *F = ret_edges.find(e);
+ HashMap<Edge, RetFaceConnect, Edge>::Iterator F = ret_edges.find(e);
ERR_CONTINUE(!F);
- List<Geometry3D::MeshData::Face>::Element *O = F->get().left == E ? F->get().right : F->get().left;
+ List<Geometry3D::MeshData::Face>::Element *O = F->value.left == E ? F->value.right : F->value.left;
ERR_CONTINUE(O == E);
ERR_CONTINUE(O == nullptr);
@@ -401,13 +401,13 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_
}
Edge e2(idx, idxn);
- Map<Edge, RetFaceConnect>::Element *F2 = ret_edges.find(e2);
+ HashMap<Edge, RetFaceConnect, Edge>::Iterator F2 = ret_edges.find(e2);
ERR_CONTINUE(!F2);
//change faceconnect, point to this face instead
- if (F2->get().left == O) {
- F2->get().left = E;
- } else if (F2->get().right == O) {
- F2->get().right = E;
+ if (F2->value.left == O) {
+ F2->value.left = E;
+ } else if (F2->value.right == O) {
+ F2->value.right = E;
}
}
@@ -426,7 +426,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_
}
}
- ret_edges.erase(F); //remove the edge
+ ret_edges.remove(F); //remove the edge
ret_faces.erase(O); //remove the face
}
}
diff --git a/core/math/quick_hull.h b/core/math/quick_hull.h
index b8d813c979..1c354880b4 100644
--- a/core/math/quick_hull.h
+++ b/core/math/quick_hull.h
@@ -34,7 +34,7 @@
#include "core/math/aabb.h"
#include "core/math/geometry_3d.h"
#include "core/templates/list.h"
-#include "core/templates/set.h"
+#include "core/templates/rb_set.h"
class QuickHull {
public:
@@ -44,9 +44,16 @@ public:
uint64_t id = 0;
};
+ static uint32_t hash(const Edge &p_edge) {
+ return hash_one_uint64(p_edge.id);
+ }
+
bool operator<(const Edge &p_edge) const {
return id < p_edge.id;
}
+ bool operator==(const Edge &p_edge) const {
+ return id == p_edge.id;
+ }
Edge(int p_vtx_a = 0, int p_vtx_b = 0) {
if (p_vtx_a > p_vtx_b) {
diff --git a/core/math/static_raycaster.h b/core/math/static_raycaster.h
index 33254399c7..adc81906d7 100644
--- a/core/math/static_raycaster.h
+++ b/core/math/static_raycaster.h
@@ -102,7 +102,7 @@ public:
virtual void add_mesh(const PackedVector3Array &p_vertices, const PackedInt32Array &p_indices, unsigned int p_id) = 0;
virtual void commit() = 0;
- virtual void set_mesh_filter(const Set<int> &p_mesh_ids) = 0;
+ virtual void set_mesh_filter(const RBSet<int> &p_mesh_ids) = 0;
virtual void clear_mesh_filter() = 0;
static Ref<StaticRaycaster> create();
diff --git a/core/math/triangle_mesh.cpp b/core/math/triangle_mesh.cpp
index e146c4a4e3..54461bf70f 100644
--- a/core/math/triangle_mesh.cpp
+++ b/core/math/triangle_mesh.cpp
@@ -122,7 +122,7 @@ void TriangleMesh::create(const Vector<Vector3> &p_faces) {
const Vector3 *r = p_faces.ptr();
Triangle *w = triangles.ptrw();
- Map<Vector3, int> db;
+ HashMap<Vector3, int> db;
for (int i = 0; i < fc; i++) {
Triangle &f = w[i];
@@ -131,9 +131,9 @@ void TriangleMesh::create(const Vector<Vector3> &p_faces) {
for (int j = 0; j < 3; j++) {
int vidx = -1;
Vector3 vs = v[j].snapped(Vector3(0.0001, 0.0001, 0.0001));
- Map<Vector3, int>::Element *E = db.find(vs);
+ HashMap<Vector3, int>::Iterator E = db.find(vs);
if (E) {
- vidx = E->get();
+ vidx = E->value;
} else {
vidx = db.size();
db[vs] = vidx;
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-25 12:07:54 +0000