summaryrefslogtreecommitdiff
path: root/core/math
diff options
context:
space:
mode:
Diffstat (limited to 'core/math')
-rw-r--r--core/math/disjoint_set.cpp31
-rw-r--r--core/math/disjoint_set.h155
-rw-r--r--core/math/geometry.cpp2
-rw-r--r--core/math/math_funcs.h10
-rw-r--r--core/math/transform.h39
5 files changed, 220 insertions, 17 deletions
diff --git a/core/math/disjoint_set.cpp b/core/math/disjoint_set.cpp
new file mode 100644
index 0000000000..c9d47aa0ae
--- /dev/null
+++ b/core/math/disjoint_set.cpp
@@ -0,0 +1,31 @@
+/*************************************************************************/
+/* disjoint_set.cpp */
+/*************************************************************************/
+/* This file is part of: */
+/* GODOT ENGINE */
+/* https://godotengine.org */
+/*************************************************************************/
+/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */
+/* Copyright (c) 2014-2019 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 "disjoint_set.h"
diff --git a/core/math/disjoint_set.h b/core/math/disjoint_set.h
new file mode 100644
index 0000000000..c9b3d0b65d
--- /dev/null
+++ b/core/math/disjoint_set.h
@@ -0,0 +1,155 @@
+/*************************************************************************/
+/* disjoint_set.h */
+/*************************************************************************/
+/* This file is part of: */
+/* GODOT ENGINE */
+/* https://godotengine.org */
+/*************************************************************************/
+/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */
+/* Copyright (c) 2014-2019 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 DISJOINT_SET_H
+#define DISJOINT_SET_H
+
+#include "core/map.h"
+#include "core/vector.h"
+
+/**
+ @author Marios Staikopoulos <marios@staik.net>
+*/
+
+/* This DisjointSet class uses Find with path compression and Union by rank */
+template <typename T, class C = Comparator<T>, class AL = DefaultAllocator>
+class DisjointSet {
+
+ struct Element {
+ T object;
+ Element *parent = nullptr;
+ int rank = 0;
+ };
+
+ typedef Map<T, Element *, C, AL> MapT;
+
+ MapT elements;
+
+ Element *get_parent(Element *element);
+
+ _FORCE_INLINE_ Element *insert_or_get(T object);
+
+public:
+ ~DisjointSet();
+
+ _FORCE_INLINE_ void insert(T object) { (void)insert_or_get(object); }
+
+ void create_union(T a, T b);
+
+ void get_representatives(Vector<T> &out_roots);
+
+ void get_members(Vector<T> &out_members, T representative);
+};
+
+/* 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 C, class AL>
+typename DisjointSet<T, C, AL>::Element *DisjointSet<T, C, AL>::get_parent(Element *element) {
+ if (element->parent != element) {
+ element->parent = get_parent(element->parent);
+ }
+
+ 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);
+ if (itr != nullptr) {
+ return itr->value();
+ }
+
+ Element *new_element = memnew_allocator(Element, AL);
+ new_element->object = object;
+ new_element->parent = new_element;
+ elements.insert(object, new_element);
+
+ return new_element;
+}
+
+template <typename T, class C, class AL>
+void DisjointSet<T, C, AL>::create_union(T a, T b) {
+
+ Element *x = insert_or_get(a);
+ Element *y = insert_or_get(b);
+
+ Element *x_root = get_parent(x);
+ Element *y_root = get_parent(y);
+
+ // Already in the same set
+ if (x_root == y_root)
+ return;
+
+ // Not in the same set, merge
+ if (x_root->rank < y_root->rank) {
+ SWAP(x_root, y_root);
+ }
+
+ // Merge y_root into x_root
+ y_root->parent = x_root;
+ if (x_root->rank == y_root->rank) {
+ ++x_root->rank;
+ }
+}
+
+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();
+ 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);
+ ERR_FAIL_COND(rep_itr == nullptr);
+
+ 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());
+ if (parent == rep_element) {
+ out_members.push_back(itr->key());
+ }
+ }
+}
+
+#endif
diff --git a/core/math/geometry.cpp b/core/math/geometry.cpp
index f37db90929..77383e2839 100644
--- a/core/math/geometry.cpp
+++ b/core/math/geometry.cpp
@@ -715,7 +715,7 @@ Vector<Vector<Vector2> > Geometry::decompose_polygon_in_convex(Vector<Point2> po
decomp.write[idx].resize(tp.GetNumPoints());
- for (int i = 0; i < tp.GetNumPoints(); i++) {
+ for (int64_t i = 0; i < tp.GetNumPoints(); i++) {
decomp.write[idx].write[i] = tp.GetPoint(i);
}
diff --git a/core/math/math_funcs.h b/core/math/math_funcs.h
index af845ca01e..9078abea68 100644
--- a/core/math/math_funcs.h
+++ b/core/math/math_funcs.h
@@ -300,6 +300,11 @@ public:
}
static _ALWAYS_INLINE_ bool is_equal_approx(real_t a, real_t b) {
+ // Check for exact equality first, required to handle "infinity" values.
+ if (a == b) {
+ return true;
+ }
+ // Then check for approximate equality.
real_t tolerance = CMP_EPSILON * abs(a);
if (tolerance < CMP_EPSILON) {
tolerance = CMP_EPSILON;
@@ -308,6 +313,11 @@ public:
}
static _ALWAYS_INLINE_ bool is_equal_approx(real_t a, real_t b, real_t tolerance) {
+ // Check for exact equality first, required to handle "infinity" values.
+ if (a == b) {
+ return true;
+ }
+ // Then check for approximate equality.
return abs(a - b) < tolerance;
}
diff --git a/core/math/transform.h b/core/math/transform.h
index 1fdc6398a1..90e2b07583 100644
--- a/core/math/transform.h
+++ b/core/math/transform.h
@@ -158,22 +158,29 @@ _FORCE_INLINE_ Plane Transform::xform_inv(const Plane &p_plane) const {
}
_FORCE_INLINE_ AABB Transform::xform(const AABB &p_aabb) const {
- /* define vertices */
- Vector3 x = basis.get_axis(0) * p_aabb.size.x;
- Vector3 y = basis.get_axis(1) * p_aabb.size.y;
- Vector3 z = basis.get_axis(2) * p_aabb.size.z;
- Vector3 pos = xform(p_aabb.position);
- //could be even further optimized
- AABB new_aabb;
- new_aabb.position = pos;
- new_aabb.expand_to(pos + x);
- new_aabb.expand_to(pos + y);
- new_aabb.expand_to(pos + z);
- new_aabb.expand_to(pos + x + y);
- new_aabb.expand_to(pos + x + z);
- new_aabb.expand_to(pos + y + z);
- new_aabb.expand_to(pos + x + y + z);
- return new_aabb;
+
+ /* http://dev.theomader.com/transform-bounding-boxes/ */
+ Vector3 min = p_aabb.position;
+ Vector3 max = p_aabb.position + p_aabb.size;
+ Vector3 tmin, tmax;
+ for (int i = 0; i < 3; i++) {
+ tmin[i] = tmax[i] = origin[i];
+ for (int j = 0; j < 3; j++) {
+ real_t e = basis[i][j] * min[j];
+ real_t f = basis[i][j] * max[j];
+ if (e < f) {
+ tmin[i] += e;
+ tmax[i] += f;
+ } else {
+ tmin[i] += f;
+ tmax[i] += e;
+ }
+ }
+ }
+ AABB r_aabb;
+ r_aabb.position = tmin;
+ r_aabb.size = tmax - tmin;
+ return r_aabb;
}
_FORCE_INLINE_ AABB Transform::xform_inv(const AABB &p_aabb) const {
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-28 20:27:42 +0000