From 2365fe472b0999100e76078d7b9f5e8f7fe2f9d5 Mon Sep 17 00:00:00 2001 From: Juan Linietsky Date: Thu, 21 Jun 2018 22:48:47 -0300 Subject: Added auto triangle generation in blend space, using Delaunay. --- core/math/delaunay.cpp | 1 + core/math/delaunay.h | 145 ++++++++++++++++++++++++ editor/icons/icon_auto_triangle.svg | 64 +++++++++++ editor/plugins/animation_blend_space_editor.cpp | 70 +++++++++--- editor/plugins/animation_blend_space_editor.h | 4 + scene/animation/animation_blend_space.cpp | 63 ++++++++++ scene/animation/animation_blend_space.h | 8 ++ 7 files changed, 342 insertions(+), 13 deletions(-) create mode 100644 core/math/delaunay.cpp create mode 100644 core/math/delaunay.h create mode 100644 editor/icons/icon_auto_triangle.svg diff --git a/core/math/delaunay.cpp b/core/math/delaunay.cpp new file mode 100644 index 0000000000..8cae92b7c0 --- /dev/null +++ b/core/math/delaunay.cpp @@ -0,0 +1 @@ +#include "delaunay.h" diff --git a/core/math/delaunay.h b/core/math/delaunay.h new file mode 100644 index 0000000000..09aebc773f --- /dev/null +++ b/core/math/delaunay.h @@ -0,0 +1,145 @@ +#ifndef DELAUNAY_H +#define DELAUNAY_H + +#include "math_2d.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]].distance_to(p_vertices[p_b.edge[0]]) < CMP_EPSILON && p_vertices[p_a.edge[1]].distance_to(p_vertices[p_b.edge[1]]) < CMP_EPSILON) { + return true; + } + + if (p_vertices[p_a.edge[0]].distance_to(p_vertices[p_b.edge[1]]) < CMP_EPSILON && p_vertices[p_a.edge[1]].distance_to(p_vertices[p_b.edge[0]]) < CMP_EPSILON) { + 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++) { + //std::cout << "Traitement du point " << *p << std::endl; + //std::cout << "_triangles contains " << _triangles.size() << " elements" << std::endl; + + Vector polygon; + + for (int j = 0; j < triangles.size(); j++) { + if (circum_circle_contains(points, triangles[j], i)) { + triangles[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[j].bad = true; + polygon[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/editor/icons/icon_auto_triangle.svg b/editor/icons/icon_auto_triangle.svg new file mode 100644 index 0000000000..631f259452 --- /dev/null +++ b/editor/icons/icon_auto_triangle.svg @@ -0,0 +1,64 @@ + + + + + + image/svg+xml + + + + + + + + + + + + + diff --git a/editor/plugins/animation_blend_space_editor.cpp b/editor/plugins/animation_blend_space_editor.cpp index f2a68296cf..9118211bf2 100644 --- a/editor/plugins/animation_blend_space_editor.cpp +++ b/editor/plugins/animation_blend_space_editor.cpp @@ -2,6 +2,7 @@ #include "core/io/resource_loader.h" #include "core/project_settings.h" +#include "math/delaunay.h" #include "os/input.h" #include "os/keyboard.h" #include "scene/animation/animation_blend_tree.h" @@ -113,20 +114,21 @@ void AnimationNodeBlendSpaceEditor::_blend_space_gui_input(const Ref } //then try to see if a triangle can be selected + if (!blend_space->get_auto_triangles()) { //if autotriangles use, disable this + for (int i = 0; i < blend_space->get_triangle_count(); i++) { + Vector triangle; + + for (int j = 0; j < 3; j++) { + int idx = blend_space->get_triangle_point(i, j); + ERR_FAIL_INDEX(idx, points.size()); + triangle.push_back(points[idx]); + } - for (int i = 0; i < blend_space->get_triangle_count(); i++) { - Vector triangle; - - for (int j = 0; j < 3; j++) { - int idx = blend_space->get_triangle_point(i, j); - ERR_FAIL_INDEX(idx, points.size()); - triangle.push_back(points[idx]); - } - - if (Geometry::is_point_in_triangle(mb->get_position(), triangle[0], triangle[1], triangle[2])) { - selected_triangle = i; - _update_tool_erase(); - return; + if (Geometry::is_point_in_triangle(mb->get_position(), triangle[0], triangle[1], triangle[2])) { + selected_triangle = i; + _update_tool_erase(); + return; + } } } } @@ -300,6 +302,18 @@ void AnimationNodeBlendSpaceEditor::_update_tool_erase() { void AnimationNodeBlendSpaceEditor::_tool_switch(int p_tool) { making_triangle.clear(); + if (p_tool == 2) { + Vector points; + for (int i = 0; i < blend_space->get_blend_point_count(); i++) { + points.push_back(blend_space->get_blend_point_position(i)); + } + Vector tr = Delaunay2D::triangulate(points); + print_line("triangleS: " + itos(tr.size())); + for (int i = 0; i < tr.size(); i++) { + blend_space->add_triangle(tr[i].points[0], tr[i].points[1], tr[i].points[2]); + } + } + if (p_tool == 0) { tool_erase->show(); tool_erase_sep->show(); @@ -518,6 +532,15 @@ void AnimationNodeBlendSpaceEditor::_update_space() { } else { goto_parent_hb->hide(); } + + if (blend_space->get_auto_triangles()) { + tool_triangle->hide(); + } else { + tool_triangle->show(); + } + + auto_triangles->set_pressed(blend_space->get_auto_triangles()); + max_x_value->set_value(blend_space->get_max_space().x); max_y_value->set_value(blend_space->get_max_space().y); @@ -663,6 +686,7 @@ void AnimationNodeBlendSpaceEditor::_notification(int p_what) { snap->set_icon(get_icon("SnapGrid", "EditorIcons")); open_editor->set_icon(get_icon("Edit", "EditorIcons")); goto_parent->set_icon(get_icon("MoveUp", "EditorIcons")); + auto_triangles->set_icon(get_icon("AutoTriangle", "EditorIcons")); } if (p_what == NOTIFICATION_PROCESS) { @@ -708,6 +732,16 @@ void AnimationNodeBlendSpaceEditor::_removed_from_graph() { EditorNode::get_singleton()->edit_item(NULL); } +void AnimationNodeBlendSpaceEditor::_auto_triangles_toggled() { + + undo_redo->create_action("Toggle Auto Triangles"); + undo_redo->add_do_method(blend_space.ptr(), "set_auto_triangles", auto_triangles->is_pressed()); + undo_redo->add_undo_method(blend_space.ptr(), "set_auto_triangles", blend_space->get_auto_triangles()); + undo_redo->add_do_method(this, "_update_space"); + undo_redo->add_undo_method(this, "_update_space"); + undo_redo->commit_action(); +} + void AnimationNodeBlendSpaceEditor::_bind_methods() { ClassDB::bind_method("_blend_space_gui_input", &AnimationNodeBlendSpaceEditor::_blend_space_gui_input); @@ -730,6 +764,8 @@ void AnimationNodeBlendSpaceEditor::_bind_methods() { ClassDB::bind_method("_goto_parent", &AnimationNodeBlendSpaceEditor::_goto_parent); ClassDB::bind_method("_removed_from_graph", &AnimationNodeBlendSpaceEditor::_removed_from_graph); + + ClassDB::bind_method("_auto_triangles_toggled", &AnimationNodeBlendSpaceEditor::_auto_triangles_toggled); } AnimationNodeBlendSpaceEditor *AnimationNodeBlendSpaceEditor::singleton = NULL; @@ -792,6 +828,14 @@ AnimationNodeBlendSpaceEditor::AnimationNodeBlendSpaceEditor() { top_hb->add_child(memnew(VSeparator)); + auto_triangles = memnew(ToolButton); + top_hb->add_child(auto_triangles); + auto_triangles->connect("pressed", this, "_auto_triangles_toggled"); + auto_triangles->set_toggle_mode(true); + auto_triangles->set_tooltip(TTR("Generate blend triangles automatically (instead of manually)")); + + top_hb->add_child(memnew(VSeparator)); + snap = memnew(ToolButton); snap->set_toggle_mode(true); top_hb->add_child(snap); diff --git a/editor/plugins/animation_blend_space_editor.h b/editor/plugins/animation_blend_space_editor.h index 4514ecc430..66d2ec6cae 100644 --- a/editor/plugins/animation_blend_space_editor.h +++ b/editor/plugins/animation_blend_space_editor.h @@ -33,6 +33,8 @@ class AnimationNodeBlendSpaceEditor : public VBoxContainer { SpinBox *snap_x; SpinBox *snap_y; + ToolButton *auto_triangles; + LineEdit *label_x; LineEdit *label_y; SpinBox *max_x_value; @@ -95,6 +97,8 @@ class AnimationNodeBlendSpaceEditor : public VBoxContainer { void _removed_from_graph(); + void _auto_triangles_toggled(); + protected: void _notification(int p_what); static void _bind_methods(); diff --git a/scene/animation/animation_blend_space.cpp b/scene/animation/animation_blend_space.cpp index 9faf9aadfd..44b2d980e2 100644 --- a/scene/animation/animation_blend_space.cpp +++ b/scene/animation/animation_blend_space.cpp @@ -1,4 +1,5 @@ #include "animation_blend_space.h" +#include "math/delaunay.h" void AnimationNodeBlendSpace::add_blend_point(const Ref &p_node, const Vector2 &p_position, int p_at_index) { ERR_FAIL_COND(blend_points_used >= MAX_BLEND_POINTS); @@ -26,11 +27,18 @@ void AnimationNodeBlendSpace::add_blend_point(const Ref &p_no blend_points[p_at_index].node->set_parent(this); blend_points[p_at_index].node->set_graph_player(get_graph_player()); blend_points_used++; + + if (auto_triangles) { + trianges_dirty = true; + } } void AnimationNodeBlendSpace::set_blend_point_position(int p_point, const Vector2 &p_position) { ERR_FAIL_INDEX(p_point, blend_points_used); blend_points[p_point].position = p_position; + if (auto_triangles) { + trianges_dirty = true; + } } void AnimationNodeBlendSpace::set_blend_point_node(int p_point, const Ref &p_node) { ERR_FAIL_INDEX(p_point, blend_points_used); @@ -121,6 +129,8 @@ void AnimationNodeBlendSpace::add_triangle(int p_x, int p_y, int p_z, int p_at_i ERR_FAIL_INDEX(p_y, blend_points_used); ERR_FAIL_INDEX(p_z, blend_points_used); + _update_triangles(); + BlendTriangle t; t.points[0] = p_x; t.points[1] = p_y; @@ -147,6 +157,9 @@ void AnimationNodeBlendSpace::add_triangle(int p_x, int p_y, int p_z, int p_at_i } } int AnimationNodeBlendSpace::get_triangle_point(int p_triangle, int p_point) { + + _update_triangles(); + ERR_FAIL_INDEX_V(p_point, 3, -1); ERR_FAIL_INDEX_V(p_triangle, triangles.size(), -1); return triangles[p_triangle].points[p_point]; @@ -227,6 +240,8 @@ void AnimationNodeBlendSpace::_add_blend_point(int p_index, const Ref &p_triangles) { + if (auto_triangles) + return; ERR_FAIL_COND(p_triangles.size() % 3 != 0); for (int i = 0; i < p_triangles.size(); i += 3) { add_triangle(p_triangles[i + 0], p_triangles[i + 1], p_triangles[i + 2]); @@ -236,6 +251,9 @@ void AnimationNodeBlendSpace::_set_triangles(const Vector &p_triangles) { Vector AnimationNodeBlendSpace::_get_triangles() const { Vector t; + if (auto_triangles && trianges_dirty) + return t; + t.resize(triangles.size() * 3); for (int i = 0; i < triangles.size(); i++) { t[i * 3 + 0] = triangles[i].points[0]; @@ -245,8 +263,33 @@ Vector AnimationNodeBlendSpace::_get_triangles() const { return t; } +void AnimationNodeBlendSpace::_update_triangles() { + + if (!auto_triangles || !trianges_dirty) + return; + + trianges_dirty = false; + triangles.clear(); + if (blend_points_used < 3) + return; + + Vector points; + points.resize(blend_points_used); + for (int i = 0; i < blend_points_used; i++) { + points[i] = blend_points[i].position; + } + + Vector triangles = Delaunay2D::triangulate(points); + + for (int i = 0; i < triangles.size(); i++) { + add_triangle(triangles[i].points[0], triangles[i].points[1], triangles[i].points[2]); + } +} + Vector2 AnimationNodeBlendSpace::get_closest_point(const Vector2 &p_point) { + _update_triangles(); + if (triangles.size() == 0) return Vector2(); @@ -328,6 +371,8 @@ void AnimationNodeBlendSpace::_blend_triangle(const Vector2 &p_pos, const Vector float AnimationNodeBlendSpace::process(float p_time, bool p_seek) { + _update_triangles(); + if (triangles.size() == 0) return 0; @@ -423,6 +468,17 @@ void AnimationNodeBlendSpace::_validate_property(PropertyInfo &property) const { AnimationRootNode::_validate_property(property); } +void AnimationNodeBlendSpace::set_auto_triangles(bool p_enable) { + auto_triangles = p_enable; + if (auto_triangles) { + trianges_dirty = true; + } +} + +bool AnimationNodeBlendSpace::get_auto_triangles() const { + return auto_triangles; +} + void AnimationNodeBlendSpace::_bind_methods() { ClassDB::bind_method(D_METHOD("add_blend_point", "node", "pos", "at_index"), &AnimationNodeBlendSpace::add_blend_point, DEFVAL(-1)); @@ -461,6 +517,11 @@ void AnimationNodeBlendSpace::_bind_methods() { ClassDB::bind_method(D_METHOD("_set_triangles", "triangles"), &AnimationNodeBlendSpace::_set_triangles); ClassDB::bind_method(D_METHOD("_get_triangles"), &AnimationNodeBlendSpace::_get_triangles); + ClassDB::bind_method(D_METHOD("set_auto_triangles", "enable"), &AnimationNodeBlendSpace::set_auto_triangles); + ClassDB::bind_method(D_METHOD("get_auto_triangles"), &AnimationNodeBlendSpace::get_auto_triangles); + + ADD_PROPERTY(PropertyInfo(Variant::BOOL, "auto_triangles", PROPERTY_HINT_NONE, "", PROPERTY_USAGE_NOEDITOR), "set_auto_triangles", "get_auto_triangles"); + for (int i = 0; i < MAX_BLEND_POINTS; i++) { ADD_PROPERTYI(PropertyInfo(Variant::OBJECT, "blend_point_" + itos(i) + "/node", PROPERTY_HINT_RESOURCE_TYPE, "AnimationRootNode", PROPERTY_USAGE_NOEDITOR | PROPERTY_USAGE_INTERNAL | PROPERTY_USAGE_DO_NOT_SHARE_ON_DUPLICATE), "_add_blend_point", "get_blend_point_node", i); ADD_PROPERTYI(PropertyInfo(Variant::VECTOR2, "blend_point_" + itos(i) + "/pos", PROPERTY_HINT_NONE, "", PROPERTY_USAGE_NOEDITOR | PROPERTY_USAGE_INTERNAL), "set_blend_point_position", "get_blend_point_position", i); @@ -478,12 +539,14 @@ void AnimationNodeBlendSpace::_bind_methods() { AnimationNodeBlendSpace::AnimationNodeBlendSpace() { + auto_triangles = true; blend_points_used = 0; max_space = Vector2(1, 1); min_space = Vector2(-1, -1); snap = Vector2(0.1, 0.1); x_label = "x"; y_label = "y"; + trianges_dirty = false; } AnimationNodeBlendSpace::~AnimationNodeBlendSpace() { diff --git a/scene/animation/animation_blend_space.h b/scene/animation/animation_blend_space.h index 2f7a17e399..3eda3d2d39 100644 --- a/scene/animation/animation_blend_space.h +++ b/scene/animation/animation_blend_space.h @@ -37,6 +37,11 @@ class AnimationNodeBlendSpace : public AnimationRootNode { void _blend_triangle(const Vector2 &p_pos, const Vector2 *p_points, float *r_weights); + bool auto_triangles; + bool trianges_dirty; + + void _update_triangles(); + protected: virtual void _validate_property(PropertyInfo &property) const; static void _bind_methods(); @@ -79,6 +84,9 @@ public: Vector2 get_closest_point(const Vector2 &p_point); + void set_auto_triangles(bool p_enable); + bool get_auto_triangles() const; + AnimationNodeBlendSpace(); ~AnimationNodeBlendSpace(); }; -- cgit v1.2.3