Added auto triangle generation in blend space, using Delaunay.

7 files changed, 342 insertions, 13 deletions

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<Vector2> &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<Vector2> &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<Triangle> triangulate(const Vector<Vector2> &p_points) {
+
+		Vector<Vector2> points = p_points;
+		Vector<Triangle> 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<Edge> 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 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<svg
+   xmlns:dc="http://purl.org/dc/elements/1.1/"
+   xmlns:cc="http://creativecommons.org/ns#"
+   xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
+   xmlns:svg="http://www.w3.org/2000/svg"
+   xmlns="http://www.w3.org/2000/svg"
+   xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
+   xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
+   width="16"
+   height="16"
+   version="1.1"
+   viewBox="0 0 16 16"
+   id="svg8"
+   sodipodi:docname="icon_auto_triangle.svg"
+   inkscape:version="0.92.3 (2405546, 2018-03-11)">
+  <metadata
+     id="metadata14">
+    <rdf:RDF>
+      <cc:Work
+         rdf:about="">
+        <dc:format>image/svg+xml</dc:format>
+        <dc:type
+           rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
+        <dc:title></dc:title>
+      </cc:Work>
+    </rdf:RDF>
+  </metadata>
+  <defs
+     id="defs12" />
+  <sodipodi:namedview
+     pagecolor="#ffffff"
+     bordercolor="#666666"
+     borderopacity="1"
+     objecttolerance="10"
+     gridtolerance="10"
+     guidetolerance="10"
+     inkscape:pageopacity="0"
+     inkscape:pageshadow="2"
+     inkscape:window-width="1853"
+     inkscape:window-height="1016"
+     id="namedview10"
+     showgrid="false"
+     inkscape:zoom="29.5"
+     inkscape:cx="17.168167"
+     inkscape:cy="5.5708575"
+     inkscape:window-x="67"
+     inkscape:window-y="27"
+     inkscape:window-maximized="1"
+     inkscape:current-layer="g4" />
+  <g
+     transform="translate(0 -1036.4)"
+     id="g6">
+    <g
+       transform="translate(-26.001 -9.8683)"
+       id="g4">
+      <path
+         style="fill:#e0e0e0;fill-opacity:1;stroke:none;stroke-width:1.87616086;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
+         d="M 8.2324219 0.67773438 L 0.64453125 15.289062 L 15.355469 15.289062 L 8.2324219 0.67773438 z M 6.9414062 5.4433594 L 9.2109375 5.4433594 C 9.5561128 6.0670927 9.8954447 6.7088542 10.230469 7.3671875 C 10.565492 8.0167875 10.901304 8.703974 11.236328 9.4316406 C 11.581503 10.159241 11.931781 10.934946 12.287109 11.757812 C 12.642437 12.580746 13.018126 13.477066 13.414062 14.447266 L 10.871094 14.447266 C 10.75942 14.135399 10.632366 13.815528 10.490234 13.486328 C 10.358255 13.157195 10.225729 12.827247 10.09375 12.498047 L 5.9824219 12.498047 C 5.8504432 12.827247 5.7143976 13.157195 5.5722656 13.486328 C 5.440287 13.815528 5.3167521 14.135399 5.2050781 14.447266 L 2.7382812 14.447266 C 3.1342186 13.477066 3.5099064 12.580746 3.8652344 11.757812 C 4.2205624 10.934946 4.5673204 10.159241 4.9023438 9.4316406 C 5.2475197 8.703974 5.5813793 8.0167875 5.90625 7.3671875 C 6.2412733 6.7088542 6.5860782 6.0670927 6.9414062 5.4433594 z M 8.0234375 7.4824219 C 7.9726708 7.6123552 7.8964385 7.790425 7.7949219 8.015625 C 7.6933999 8.240825 7.5772912 8.5003885 7.4453125 8.7949219 C 7.3133332 9.0894552 7.1643891 9.4143979 7.0019531 9.7695312 C 6.8496698 10.124665 6.6936847 10.496919 6.53125 10.886719 L 9.53125 10.886719 C 9.368814 10.496919 9.2108764 10.124665 9.0585938 9.7695312 C 8.9063104 9.4143979 8.7593188 9.0894552 8.6171875 8.7949219 C 8.4852082 8.5003885 8.3691001 8.240825 8.2675781 8.015625 C 8.1660555 7.790425 8.0843508 7.6123552 8.0234375 7.4824219 z "
+         transform="translate(26.001,1046.2683)"
+         id="path821" />
+    </g>
+  </g>
+</svg>
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<InputEvent>
 		}
 
 		//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<Vector2> 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<Vector2> 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<Vector2> points;
+		for (int i = 0; i < blend_space->get_blend_point_count(); i++) {
+			points.push_back(blend_space->get_blend_point_position(i));
+		}
+		Vector<Delaunay2D::Triangle> 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<AnimationRootNode> &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<AnimationRootNode> &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<AnimationRootNode> &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<AnimationR
 
 void AnimationNodeBlendSpace::_set_triangles(const Vector<int> &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<int> &p_triangles) {
 Vector<int> AnimationNodeBlendSpace::_get_triangles() const {
 
 	Vector<int> 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<int> 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<Vector2> points;
+	points.resize(blend_points_used);
+	for (int i = 0; i < blend_points_used; i++) {
+		points[i] = blend_points[i].position;
+	}
+
+	Vector<Delaunay2D::Triangle> 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();
 };