From 83b630b8c27fc3307eba36fa2b6193690bd18e4c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?R=C3=A9mi=20Verschelde?= Date: Mon, 11 May 2020 14:36:46 +0200 Subject: thirdparty: Cleanup after #38386, document provenance and copyright Also renamed `delaunay.h` to `delaunay_2d.h` to match the class name. --- core/math/delaunay.h | 173 ------------------------------------------------ core/math/delaunay_2d.h | 173 ++++++++++++++++++++++++++++++++++++++++++++++++ core/math/delaunay_3d.h | 3 +- core/math/geometry.cpp | 3 +- core/math/geometry.h | 3 +- core/math/r128.cpp | 2 - 6 files changed, 178 insertions(+), 179 deletions(-) delete mode 100644 core/math/delaunay.h create mode 100644 core/math/delaunay_2d.h delete mode 100644 core/math/r128.cpp (limited to 'core/math') diff --git a/core/math/delaunay.h b/core/math/delaunay.h deleted file mode 100644 index 6f19f3e58a..0000000000 --- a/core/math/delaunay.h +++ /dev/null @@ -1,173 +0,0 @@ -/*************************************************************************/ -/* delaunay.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 DELAUNAY_H -#define DELAUNAY_H - -#include "core/math/rect2.h" - -class Delaunay2D { -public: - struct Triangle { - - int points[3]; - bool bad; - Triangle() { bad = false; } - Triangle(int p_a, int p_b, int p_c) { - points[0] = p_a; - points[1] = p_b; - points[2] = p_c; - bad = false; - } - }; - - struct Edge { - int edge[2]; - bool bad; - Edge() { bad = false; } - Edge(int p_a, int p_b) { - bad = false; - edge[0] = p_a; - edge[1] = p_b; - } - }; - - static bool circum_circle_contains(const Vector &p_vertices, const Triangle &p_triangle, int p_vertex) { - - Vector2 p1 = p_vertices[p_triangle.points[0]]; - Vector2 p2 = p_vertices[p_triangle.points[1]]; - Vector2 p3 = p_vertices[p_triangle.points[2]]; - - real_t ab = p1.x * p1.x + p1.y * p1.y; - real_t cd = p2.x * p2.x + p2.y * p2.y; - real_t ef = p3.x * p3.x + p3.y * p3.y; - - Vector2 circum( - (ab * (p3.y - p2.y) + cd * (p1.y - p3.y) + ef * (p2.y - p1.y)) / (p1.x * (p3.y - p2.y) + p2.x * (p1.y - p3.y) + p3.x * (p2.y - p1.y)), - (ab * (p3.x - p2.x) + cd * (p1.x - p3.x) + ef * (p2.x - p1.x)) / (p1.y * (p3.x - p2.x) + p2.y * (p1.x - p3.x) + p3.y * (p2.x - p1.x))); - - circum *= 0.5; - float r = p1.distance_squared_to(circum); - float d = p_vertices[p_vertex].distance_squared_to(circum); - return d <= r; - } - - static bool edge_compare(const Vector &p_vertices, const Edge &p_a, const Edge &p_b) { - if (p_vertices[p_a.edge[0]].is_equal_approx(p_vertices[p_b.edge[0]]) && p_vertices[p_a.edge[1]].is_equal_approx(p_vertices[p_b.edge[1]])) { - return true; - } - - if (p_vertices[p_a.edge[0]].is_equal_approx(p_vertices[p_b.edge[1]]) && p_vertices[p_a.edge[1]].is_equal_approx(p_vertices[p_b.edge[0]])) { - return true; - } - - return false; - } - - static Vector triangulate(const Vector &p_points) { - - Vector points = p_points; - Vector triangles; - - Rect2 rect; - for (int i = 0; i < p_points.size(); i++) { - if (i == 0) { - rect.position = p_points[i]; - } else { - rect.expand_to(p_points[i]); - } - } - - float delta_max = MAX(rect.size.width, rect.size.height); - Vector2 center = rect.position + rect.size * 0.5; - - points.push_back(Vector2(center.x - 20 * delta_max, center.y - delta_max)); - points.push_back(Vector2(center.x, center.y + 20 * delta_max)); - points.push_back(Vector2(center.x + 20 * delta_max, center.y - delta_max)); - - triangles.push_back(Triangle(p_points.size() + 0, p_points.size() + 1, p_points.size() + 2)); - - for (int i = 0; i < p_points.size(); i++) { - - Vector polygon; - - for (int j = 0; j < triangles.size(); j++) { - if (circum_circle_contains(points, triangles[j], i)) { - triangles.write[j].bad = true; - polygon.push_back(Edge(triangles[j].points[0], triangles[j].points[1])); - polygon.push_back(Edge(triangles[j].points[1], triangles[j].points[2])); - polygon.push_back(Edge(triangles[j].points[2], triangles[j].points[0])); - } - } - - for (int j = 0; j < triangles.size(); j++) { - if (triangles[j].bad) { - triangles.remove(j); - j--; - } - } - - for (int j = 0; j < polygon.size(); j++) { - for (int k = j + 1; k < polygon.size(); k++) { - if (edge_compare(points, polygon[j], polygon[k])) { - polygon.write[j].bad = true; - polygon.write[k].bad = true; - } - } - } - - for (int j = 0; j < polygon.size(); j++) { - - if (polygon[j].bad) { - continue; - } - triangles.push_back(Triangle(polygon[j].edge[0], polygon[j].edge[1], i)); - } - } - - for (int i = 0; i < triangles.size(); i++) { - bool invalid = false; - for (int j = 0; j < 3; j++) { - if (triangles[i].points[j] >= p_points.size()) { - invalid = true; - break; - } - } - if (invalid) { - triangles.remove(i); - i--; - } - } - - return triangles; - } -}; - -#endif // DELAUNAY_H diff --git a/core/math/delaunay_2d.h b/core/math/delaunay_2d.h new file mode 100644 index 0000000000..b8252e9d16 --- /dev/null +++ b/core/math/delaunay_2d.h @@ -0,0 +1,173 @@ +/*************************************************************************/ +/* delaunay_2d.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 DELAUNAY_2D_H +#define DELAUNAY_2D_H + +#include "core/math/rect2.h" + +class Delaunay2D { +public: + struct Triangle { + + int points[3]; + bool bad; + Triangle() { bad = false; } + Triangle(int p_a, int p_b, int p_c) { + points[0] = p_a; + points[1] = p_b; + points[2] = p_c; + bad = false; + } + }; + + struct Edge { + int edge[2]; + bool bad; + Edge() { bad = false; } + Edge(int p_a, int p_b) { + bad = false; + edge[0] = p_a; + edge[1] = p_b; + } + }; + + static bool circum_circle_contains(const Vector &p_vertices, const Triangle &p_triangle, int p_vertex) { + + Vector2 p1 = p_vertices[p_triangle.points[0]]; + Vector2 p2 = p_vertices[p_triangle.points[1]]; + Vector2 p3 = p_vertices[p_triangle.points[2]]; + + real_t ab = p1.x * p1.x + p1.y * p1.y; + real_t cd = p2.x * p2.x + p2.y * p2.y; + real_t ef = p3.x * p3.x + p3.y * p3.y; + + Vector2 circum( + (ab * (p3.y - p2.y) + cd * (p1.y - p3.y) + ef * (p2.y - p1.y)) / (p1.x * (p3.y - p2.y) + p2.x * (p1.y - p3.y) + p3.x * (p2.y - p1.y)), + (ab * (p3.x - p2.x) + cd * (p1.x - p3.x) + ef * (p2.x - p1.x)) / (p1.y * (p3.x - p2.x) + p2.y * (p1.x - p3.x) + p3.y * (p2.x - p1.x))); + + circum *= 0.5; + float r = p1.distance_squared_to(circum); + float d = p_vertices[p_vertex].distance_squared_to(circum); + return d <= r; + } + + static bool edge_compare(const Vector &p_vertices, const Edge &p_a, const Edge &p_b) { + if (p_vertices[p_a.edge[0]].is_equal_approx(p_vertices[p_b.edge[0]]) && p_vertices[p_a.edge[1]].is_equal_approx(p_vertices[p_b.edge[1]])) { + return true; + } + + if (p_vertices[p_a.edge[0]].is_equal_approx(p_vertices[p_b.edge[1]]) && p_vertices[p_a.edge[1]].is_equal_approx(p_vertices[p_b.edge[0]])) { + return true; + } + + return false; + } + + static Vector triangulate(const Vector &p_points) { + + Vector points = p_points; + Vector triangles; + + Rect2 rect; + for (int i = 0; i < p_points.size(); i++) { + if (i == 0) { + rect.position = p_points[i]; + } else { + rect.expand_to(p_points[i]); + } + } + + float delta_max = MAX(rect.size.width, rect.size.height); + Vector2 center = rect.position + rect.size * 0.5; + + points.push_back(Vector2(center.x - 20 * delta_max, center.y - delta_max)); + points.push_back(Vector2(center.x, center.y + 20 * delta_max)); + points.push_back(Vector2(center.x + 20 * delta_max, center.y - delta_max)); + + triangles.push_back(Triangle(p_points.size() + 0, p_points.size() + 1, p_points.size() + 2)); + + for (int i = 0; i < p_points.size(); i++) { + + Vector polygon; + + for (int j = 0; j < triangles.size(); j++) { + if (circum_circle_contains(points, triangles[j], i)) { + triangles.write[j].bad = true; + polygon.push_back(Edge(triangles[j].points[0], triangles[j].points[1])); + polygon.push_back(Edge(triangles[j].points[1], triangles[j].points[2])); + polygon.push_back(Edge(triangles[j].points[2], triangles[j].points[0])); + } + } + + for (int j = 0; j < triangles.size(); j++) { + if (triangles[j].bad) { + triangles.remove(j); + j--; + } + } + + for (int j = 0; j < polygon.size(); j++) { + for (int k = j + 1; k < polygon.size(); k++) { + if (edge_compare(points, polygon[j], polygon[k])) { + polygon.write[j].bad = true; + polygon.write[k].bad = true; + } + } + } + + for (int j = 0; j < polygon.size(); j++) { + + if (polygon[j].bad) { + continue; + } + triangles.push_back(Triangle(polygon[j].edge[0], polygon[j].edge[1], i)); + } + } + + for (int i = 0; i < triangles.size(); i++) { + bool invalid = false; + for (int j = 0; j < 3; j++) { + if (triangles[i].points[j] >= p_points.size()) { + invalid = true; + break; + } + } + if (invalid) { + triangles.remove(i); + i--; + } + } + + return triangles; + } +}; + +#endif // DELAUNAY_2D_H diff --git a/core/math/delaunay_3d.h b/core/math/delaunay_3d.h index 6280ec8071..57f3a78d35 100644 --- a/core/math/delaunay_3d.h +++ b/core/math/delaunay_3d.h @@ -10,7 +10,8 @@ #include "core/print_string.h" #include "core/variant.h" #include "core/vector.h" -#include "thirdparty/r128/r128.h" + +#include "thirdparty/misc/r128.h" class Delaunay3D { struct Simplex; diff --git a/core/math/geometry.cpp b/core/math/geometry.cpp index 65b80856cc..b0a46036f9 100644 --- a/core/math/geometry.cpp +++ b/core/math/geometry.cpp @@ -31,10 +31,11 @@ #include "geometry.h" #include "core/print_string.h" + #include "thirdparty/misc/clipper.hpp" #include "thirdparty/misc/triangulator.h" #define STB_RECT_PACK_IMPLEMENTATION -#include "thirdparty/stb_rect_pack/stb_rect_pack.h" +#include "thirdparty/misc/stb_rect_pack.h" #define SCALE_FACTOR 100000.0 // Based on CMP_EPSILON. diff --git a/core/math/geometry.h b/core/math/geometry.h index 5a8e21d02b..45c8558fac 100644 --- a/core/math/geometry.h +++ b/core/math/geometry.h @@ -31,13 +31,12 @@ #ifndef GEOMETRY_H #define GEOMETRY_H -#include "core/math/delaunay.h" +#include "core/math/delaunay_2d.h" #include "core/math/face3.h" #include "core/math/rect2.h" #include "core/math/triangulate.h" #include "core/math/vector3.h" #include "core/object.h" - #include "core/print_string.h" #include "core/vector.h" diff --git a/core/math/r128.cpp b/core/math/r128.cpp deleted file mode 100644 index fb1e4733ee..0000000000 --- a/core/math/r128.cpp +++ /dev/null @@ -1,2 +0,0 @@ -#define R128_IMPLEMENTATION -#include "thirdparty/r128/r128.h" -- cgit v1.2.3