1 /*************************************************************************/
2 /* navigation_polygon.cpp */
3 /*************************************************************************/
4 /* This file is part of: */
5 /* GODOT ENGINE */
6 /* https://godotengine.org */
7 /*************************************************************************/
8 /* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */
9 /* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */
10 /* */
11 /* Permission is hereby granted, free of charge, to any person obtaining */
12 /* a copy of this software and associated documentation files (the */
13 /* "Software"), to deal in the Software without restriction, including */
14 /* without limitation the rights to use, copy, modify, merge, publish, */
15 /* distribute, sublicense, and/or sell copies of the Software, and to */
16 /* permit persons to whom the Software is furnished to do so, subject to */
17 /* the following conditions: */
18 /* */
19 /* The above copyright notice and this permission notice shall be */
20 /* included in all copies or substantial portions of the Software. */
21 /* */
22 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24 /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
25 /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26 /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27 /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28 /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29 /*************************************************************************/
30 #include "navigation_polygon.h"
31
32 #include "core_string_names.h"
33 #include "navigation2d.h"
34
35 #include "thirdparty/misc/triangulator.h"
36
set_vertices(const DVector<Vector2> & p_vertices)37 void NavigationPolygon::set_vertices(const DVector<Vector2> &p_vertices) {
38
39 vertices = p_vertices;
40 }
41
get_vertices() const42 DVector<Vector2> NavigationPolygon::get_vertices() const {
43
44 return vertices;
45 }
46
_set_polygons(const Array & p_array)47 void NavigationPolygon::_set_polygons(const Array &p_array) {
48
49 polygons.resize(p_array.size());
50 for (int i = 0; i < p_array.size(); i++) {
51 polygons[i].indices = p_array[i];
52 }
53 }
54
_get_polygons() const55 Array NavigationPolygon::_get_polygons() const {
56
57 Array ret;
58 ret.resize(polygons.size());
59 for (int i = 0; i < ret.size(); i++) {
60 ret[i] = polygons[i].indices;
61 }
62
63 return ret;
64 }
65
_set_outlines(const Array & p_array)66 void NavigationPolygon::_set_outlines(const Array &p_array) {
67
68 outlines.resize(p_array.size());
69 for (int i = 0; i < p_array.size(); i++) {
70 outlines[i] = p_array[i];
71 }
72 }
73
_get_outlines() const74 Array NavigationPolygon::_get_outlines() const {
75
76 Array ret;
77 ret.resize(outlines.size());
78 for (int i = 0; i < ret.size(); i++) {
79 ret[i] = outlines[i];
80 }
81
82 return ret;
83 }
84
add_polygon(const Vector<int> & p_polygon)85 void NavigationPolygon::add_polygon(const Vector<int> &p_polygon) {
86
87 Polygon polygon;
88 polygon.indices = p_polygon;
89 polygons.push_back(polygon);
90 }
91
add_outline_at_index(const DVector<Vector2> & p_outline,int p_index)92 void NavigationPolygon::add_outline_at_index(const DVector<Vector2> &p_outline, int p_index) {
93
94 outlines.insert(p_index, p_outline);
95 }
96
get_polygon_count() const97 int NavigationPolygon::get_polygon_count() const {
98
99 return polygons.size();
100 }
get_polygon(int p_idx)101 Vector<int> NavigationPolygon::get_polygon(int p_idx) {
102
103 ERR_FAIL_INDEX_V(p_idx, polygons.size(), Vector<int>());
104 return polygons[p_idx].indices;
105 }
clear_polygons()106 void NavigationPolygon::clear_polygons() {
107
108 polygons.clear();
109 }
110
add_outline(const DVector<Vector2> & p_outline)111 void NavigationPolygon::add_outline(const DVector<Vector2> &p_outline) {
112
113 outlines.push_back(p_outline);
114 }
115
get_outline_count() const116 int NavigationPolygon::get_outline_count() const {
117
118 return outlines.size();
119 }
120
set_outline(int p_idx,const DVector<Vector2> & p_outline)121 void NavigationPolygon::set_outline(int p_idx, const DVector<Vector2> &p_outline) {
122 ERR_FAIL_INDEX(p_idx, outlines.size());
123 outlines[p_idx] = p_outline;
124 }
125
remove_outline(int p_idx)126 void NavigationPolygon::remove_outline(int p_idx) {
127
128 ERR_FAIL_INDEX(p_idx, outlines.size());
129 outlines.remove(p_idx);
130 }
131
get_outline(int p_idx) const132 DVector<Vector2> NavigationPolygon::get_outline(int p_idx) const {
133 ERR_FAIL_INDEX_V(p_idx, outlines.size(), DVector<Vector2>());
134 return outlines[p_idx];
135 }
136
clear_outlines()137 void NavigationPolygon::clear_outlines() {
138
139 outlines.clear();
140 }
make_polygons_from_outlines()141 void NavigationPolygon::make_polygons_from_outlines() {
142
143 List<TriangulatorPoly> in_poly, out_poly;
144
145 Vector2 outside_point(-1e10, -1e10);
146
147 for (int i = 0; i < outlines.size(); i++) {
148
149 DVector<Vector2> ol = outlines[i];
150 int olsize = ol.size();
151 if (olsize < 3)
152 continue;
153 DVector<Vector2>::Read r = ol.read();
154 for (int j = 0; j < olsize; j++) {
155 outside_point.x = MAX(r[j].x, outside_point.x);
156 outside_point.y = MAX(r[j].y, outside_point.y);
157 }
158 }
159
160 outside_point += Vector2(0.7239784, 0.819238); //avoid precision issues
161
162 for (int i = 0; i < outlines.size(); i++) {
163
164 DVector<Vector2> ol = outlines[i];
165 int olsize = ol.size();
166 if (olsize < 3)
167 continue;
168 DVector<Vector2>::Read r = ol.read();
169
170 int interscount = 0;
171 //test if this is an outer outline
172 for (int k = 0; k < outlines.size(); k++) {
173
174 if (i == k)
175 continue; //no self intersect
176
177 DVector<Vector2> ol2 = outlines[k];
178 int olsize2 = ol2.size();
179 if (olsize2 < 3)
180 continue;
181 DVector<Vector2>::Read r2 = ol2.read();
182
183 for (int l = 0; l < olsize2; l++) {
184
185 if (Geometry::segment_intersects_segment_2d(r[0], outside_point, r2[l], r2[(l + 1) % olsize2], NULL)) {
186 interscount++;
187 }
188 }
189 }
190
191 bool outer = (interscount % 2) == 0;
192
193 TriangulatorPoly tp;
194 tp.Init(olsize);
195 for (int j = 0; j < olsize; j++) {
196 tp[j] = r[j];
197 }
198
199 if (outer)
200 tp.SetOrientation(TRIANGULATOR_CCW);
201 else {
202 tp.SetOrientation(TRIANGULATOR_CW);
203 tp.SetHole(true);
204 }
205
206 in_poly.push_back(tp);
207 }
208
209 TriangulatorPartition tpart;
210 if (tpart.ConvexPartition_HM(&in_poly, &out_poly) == 0) { //failed!
211 print_line("convex partition failed!");
212 return;
213 }
214
215 polygons.clear();
216 vertices.resize(0);
217
218 Map<Vector2, int> points;
219 for (List<TriangulatorPoly>::Element *I = out_poly.front(); I; I = I->next()) {
220
221 TriangulatorPoly &tp = I->get();
222
223 struct Polygon p;
224
225 for (int i = 0; i < tp.GetNumPoints(); i++) {
226
227 Map<Vector2, int>::Element *E = points.find(tp[i]);
228 if (!E) {
229 E = points.insert(tp[i], vertices.size());
230 vertices.push_back(tp[i]);
231 }
232 p.indices.push_back(E->get());
233 }
234
235 polygons.push_back(p);
236 }
237
238 emit_signal(CoreStringNames::get_singleton()->changed);
239 }
240
_bind_methods()241 void NavigationPolygon::_bind_methods() {
242
243 ObjectTypeDB::bind_method(_MD("set_vertices", "vertices"), &NavigationPolygon::set_vertices);
244 ObjectTypeDB::bind_method(_MD("get_vertices"), &NavigationPolygon::get_vertices);
245
246 ObjectTypeDB::bind_method(_MD("add_polygon", "polygon"), &NavigationPolygon::add_polygon);
247 ObjectTypeDB::bind_method(_MD("get_polygon_count"), &NavigationPolygon::get_polygon_count);
248 ObjectTypeDB::bind_method(_MD("get_polygon", "idx"), &NavigationPolygon::get_polygon);
249 ObjectTypeDB::bind_method(_MD("clear_polygons"), &NavigationPolygon::clear_polygons);
250
251 ObjectTypeDB::bind_method(_MD("add_outline", "outline"), &NavigationPolygon::add_outline);
252 ObjectTypeDB::bind_method(_MD("add_outline_at_index", "outline", "index"), &NavigationPolygon::add_outline_at_index);
253 ObjectTypeDB::bind_method(_MD("get_outline_count"), &NavigationPolygon::get_outline_count);
254 ObjectTypeDB::bind_method(_MD("set_outline", "idx", "outline"), &NavigationPolygon::set_outline);
255 ObjectTypeDB::bind_method(_MD("get_outline", "idx"), &NavigationPolygon::get_outline);
256 ObjectTypeDB::bind_method(_MD("remove_outline", "idx"), &NavigationPolygon::remove_outline);
257 ObjectTypeDB::bind_method(_MD("clear_outlines"), &NavigationPolygon::clear_outlines);
258 ObjectTypeDB::bind_method(_MD("make_polygons_from_outlines"), &NavigationPolygon::make_polygons_from_outlines);
259
260 ObjectTypeDB::bind_method(_MD("_set_polygons", "polygons"), &NavigationPolygon::_set_polygons);
261 ObjectTypeDB::bind_method(_MD("_get_polygons"), &NavigationPolygon::_get_polygons);
262
263 ObjectTypeDB::bind_method(_MD("_set_outlines", "outlines"), &NavigationPolygon::_set_outlines);
264 ObjectTypeDB::bind_method(_MD("_get_outlines"), &NavigationPolygon::_get_outlines);
265
266 ADD_PROPERTY(PropertyInfo(Variant::VECTOR3_ARRAY, "vertices", PROPERTY_HINT_NONE, "", PROPERTY_USAGE_NOEDITOR), _SCS("set_vertices"), _SCS("get_vertices"));
267 ADD_PROPERTY(PropertyInfo(Variant::ARRAY, "polygons", PROPERTY_HINT_NONE, "", PROPERTY_USAGE_NOEDITOR), _SCS("_set_polygons"), _SCS("_get_polygons"));
268 ADD_PROPERTY(PropertyInfo(Variant::ARRAY, "outlines", PROPERTY_HINT_NONE, "", PROPERTY_USAGE_NOEDITOR), _SCS("_set_outlines"), _SCS("_get_outlines"));
269 }
270
NavigationPolygon()271 NavigationPolygon::NavigationPolygon() {
272 }
273
set_enabled(bool p_enabled)274 void NavigationPolygonInstance::set_enabled(bool p_enabled) {
275
276 if (enabled == p_enabled)
277 return;
278 enabled = p_enabled;
279
280 if (!is_inside_tree())
281 return;
282
283 if (!enabled) {
284
285 if (nav_id != -1) {
286 navigation->navpoly_remove(nav_id);
287 nav_id = -1;
288 }
289 } else {
290
291 if (navigation) {
292
293 if (navpoly.is_valid()) {
294
295 nav_id = navigation->navpoly_create(navpoly, get_relative_transform_to_parent(navigation), this);
296 }
297 }
298 }
299
300 if (get_tree()->is_editor_hint() || get_tree()->is_debugging_navigation_hint())
301 update();
302
303 // update_gizmo();
304 }
305
is_enabled() const306 bool NavigationPolygonInstance::is_enabled() const {
307
308 return enabled;
309 }
310
311 /////////////////////////////
312
_notification(int p_what)313 void NavigationPolygonInstance::_notification(int p_what) {
314
315 switch (p_what) {
316 case NOTIFICATION_ENTER_TREE: {
317
318 Node2D *c = this;
319 while (c) {
320
321 navigation = c->cast_to<Navigation2D>();
322 if (navigation) {
323
324 if (enabled && navpoly.is_valid()) {
325
326 nav_id = navigation->navpoly_create(navpoly, get_relative_transform_to_parent(navigation), this);
327 }
328 break;
329 }
330
331 c = c->get_parent()->cast_to<Node2D>();
332 }
333
334 } break;
335 case NOTIFICATION_TRANSFORM_CHANGED: {
336
337 if (navigation && nav_id != -1) {
338 navigation->navpoly_set_transform(nav_id, get_relative_transform_to_parent(navigation));
339 }
340
341 } break;
342 case NOTIFICATION_EXIT_TREE: {
343
344 if (navigation) {
345
346 if (nav_id != -1) {
347 navigation->navpoly_remove(nav_id);
348 nav_id = -1;
349 }
350 }
351 navigation = NULL;
352 } break;
353 case NOTIFICATION_DRAW: {
354
355 if (is_inside_tree() && (get_tree()->is_editor_hint() || get_tree()->is_debugging_navigation_hint()) && navpoly.is_valid()) {
356
357 DVector<Vector2> verts = navpoly->get_vertices();
358 int vsize = verts.size();
359 if (vsize < 3)
360 return;
361
362 Color color;
363 if (enabled) {
364 color = get_tree()->get_debug_navigation_color();
365 } else {
366 color = get_tree()->get_debug_navigation_disabled_color();
367 }
368 Vector<Color> colors;
369 Vector<Vector2> vertices;
370 vertices.resize(vsize);
371 colors.resize(vsize);
372 {
373 DVector<Vector2>::Read vr = verts.read();
374 for (int i = 0; i < vsize; i++) {
375 vertices[i] = vr[i];
376 colors[i] = color;
377 }
378 }
379
380 Vector<int> indices;
381
382 for (int i = 0; i < navpoly->get_polygon_count(); i++) {
383 Vector<int> polygon = navpoly->get_polygon(i);
384
385 for (int j = 2; j < polygon.size(); j++) {
386
387 int kofs[3] = { 0, j - 1, j };
388 for (int k = 0; k < 3; k++) {
389
390 int idx = polygon[kofs[k]];
391 ERR_FAIL_INDEX(idx, vsize);
392 indices.push_back(idx);
393 }
394 }
395 }
396 VS::get_singleton()->canvas_item_add_triangle_array(get_canvas_item(), indices, vertices, colors);
397 }
398 } break;
399 }
400 }
401
set_navigation_polygon(const Ref<NavigationPolygon> & p_navpoly)402 void NavigationPolygonInstance::set_navigation_polygon(const Ref<NavigationPolygon> &p_navpoly) {
403
404 if (p_navpoly == navpoly)
405 return;
406
407 if (navigation && nav_id != -1) {
408 navigation->navpoly_remove(nav_id);
409 nav_id = -1;
410 }
411 if (navpoly.is_valid()) {
412 navpoly->disconnect(CoreStringNames::get_singleton()->changed, this, "_navpoly_changed");
413 }
414 navpoly = p_navpoly;
415
416 if (navpoly.is_valid()) {
417 navpoly->connect(CoreStringNames::get_singleton()->changed, this, "_navpoly_changed");
418 }
419
420 if (navigation && navpoly.is_valid() && enabled) {
421 nav_id = navigation->navpoly_create(navpoly, get_relative_transform_to_parent(navigation), this);
422 }
423 //update_gizmo();
424 _change_notify("navpoly");
425 update_configuration_warning();
426 }
427
get_navigation_polygon() const428 Ref<NavigationPolygon> NavigationPolygonInstance::get_navigation_polygon() const {
429
430 return navpoly;
431 }
432
_navpoly_changed()433 void NavigationPolygonInstance::_navpoly_changed() {
434
435 if (is_inside_tree() && (get_tree()->is_editor_hint() || get_tree()->is_debugging_navigation_hint()))
436 update();
437 }
438
get_configuration_warning() const439 String NavigationPolygonInstance::get_configuration_warning() const {
440
441 if (!is_visible() || !is_inside_tree())
442 return String();
443
444 if (!navpoly.is_valid()) {
445 return TTR("A NavigationPolygon resource must be set or created for this node to work. Please set a property or draw a polygon.");
446 }
447 const Node2D *c = this;
448 while (c) {
449
450 if (c->cast_to<Navigation2D>()) {
451 return String();
452 }
453
454 c = c->get_parent()->cast_to<Node2D>();
455 }
456
457 return TTR("NavigationPolygonInstance must be a child or grandchild to a Navigation2D node. It only provides navigation data.");
458 }
459
_bind_methods()460 void NavigationPolygonInstance::_bind_methods() {
461
462 ObjectTypeDB::bind_method(_MD("set_navigation_polygon", "navpoly:NavigationPolygon"), &NavigationPolygonInstance::set_navigation_polygon);
463 ObjectTypeDB::bind_method(_MD("get_navigation_polygon:NavigationPolygon"), &NavigationPolygonInstance::get_navigation_polygon);
464
465 ObjectTypeDB::bind_method(_MD("set_enabled", "enabled"), &NavigationPolygonInstance::set_enabled);
466 ObjectTypeDB::bind_method(_MD("is_enabled"), &NavigationPolygonInstance::is_enabled);
467
468 ObjectTypeDB::bind_method(_MD("_navpoly_changed"), &NavigationPolygonInstance::_navpoly_changed);
469
470 ADD_PROPERTY(PropertyInfo(Variant::OBJECT, "navpoly", PROPERTY_HINT_RESOURCE_TYPE, "NavigationPolygon"), _SCS("set_navigation_polygon"), _SCS("get_navigation_polygon"));
471 ADD_PROPERTY(PropertyInfo(Variant::BOOL, "enabled"), _SCS("set_enabled"), _SCS("is_enabled"));
472 }
473
NavigationPolygonInstance()474 NavigationPolygonInstance::NavigationPolygonInstance() {
475
476 navigation = NULL;
477 nav_id = -1;
478 enabled = true;
479 }
480