1/**************************************************************************/
2/* navigation_polygon.cpp */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
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
31#include "navigation_polygon.h"
32
33#include "core/math/geometry_2d.h"
34#include "core/os/mutex.h"
35
36#include "thirdparty/misc/polypartition.h"
37
38#ifdef TOOLS_ENABLED
39Rect2 NavigationPolygon::_edit_get_rect() const {
40 if (rect_cache_dirty) {
41 item_rect = Rect2();
42 bool first = true;
43
44 for (int i = 0; i < outlines.size(); i++) {
45 const Vector<Vector2> &outline = outlines[i];
46 const int outline_size = outline.size();
47 if (outline_size < 3) {
48 continue;
49 }
50 const Vector2 *p = outline.ptr();
51 for (int j = 0; j < outline_size; j++) {
52 if (first) {
53 item_rect = Rect2(p[j], Vector2(0, 0));
54 first = false;
55 } else {
56 item_rect.expand_to(p[j]);
57 }
58 }
59 }
60
61 rect_cache_dirty = false;
62 }
63 return item_rect;
64}
65
66bool NavigationPolygon::_edit_is_selected_on_click(const Point2 &p_point, double p_tolerance) const {
67 for (int i = 0; i < outlines.size(); i++) {
68 const Vector<Vector2> &outline = outlines[i];
69 const int outline_size = outline.size();
70 if (outline_size < 3) {
71 continue;
72 }
73 if (Geometry2D::is_point_in_polygon(p_point, Variant(outline))) {
74 return true;
75 }
76 }
77 return false;
78}
79#endif
80
81void NavigationPolygon::set_vertices(const Vector<Vector2> &p_vertices) {
82 {
83 MutexLock lock(navigation_mesh_generation);
84 navigation_mesh.unref();
85 }
86 vertices = p_vertices;
87 rect_cache_dirty = true;
88}
89
90Vector<Vector2> NavigationPolygon::get_vertices() const {
91 return vertices;
92}
93
94void NavigationPolygon::_set_polygons(const TypedArray<Vector<int32_t>> &p_array) {
95 {
96 MutexLock lock(navigation_mesh_generation);
97 navigation_mesh.unref();
98 }
99 polygons.resize(p_array.size());
100 for (int i = 0; i < p_array.size(); i++) {
101 polygons.write[i].indices = p_array[i];
102 }
103}
104
105TypedArray<Vector<int32_t>> NavigationPolygon::_get_polygons() const {
106 TypedArray<Vector<int32_t>> ret;
107 ret.resize(polygons.size());
108 for (int i = 0; i < ret.size(); i++) {
109 ret[i] = polygons[i].indices;
110 }
111
112 return ret;
113}
114
115void NavigationPolygon::_set_outlines(const TypedArray<Vector<Vector2>> &p_array) {
116 outlines.resize(p_array.size());
117 for (int i = 0; i < p_array.size(); i++) {
118 outlines.write[i] = p_array[i];
119 }
120 rect_cache_dirty = true;
121}
122
123TypedArray<Vector<Vector2>> NavigationPolygon::_get_outlines() const {
124 TypedArray<Vector<Vector2>> ret;
125 ret.resize(outlines.size());
126 for (int i = 0; i < ret.size(); i++) {
127 ret[i] = outlines[i];
128 }
129
130 return ret;
131}
132
133void NavigationPolygon::add_polygon(const Vector<int> &p_polygon) {
134 Polygon polygon;
135 polygon.indices = p_polygon;
136 polygons.push_back(polygon);
137 {
138 MutexLock lock(navigation_mesh_generation);
139 navigation_mesh.unref();
140 }
141}
142
143void NavigationPolygon::add_outline_at_index(const Vector<Vector2> &p_outline, int p_index) {
144 outlines.insert(p_index, p_outline);
145 rect_cache_dirty = true;
146}
147
148int NavigationPolygon::get_polygon_count() const {
149 return polygons.size();
150}
151
152Vector<int> NavigationPolygon::get_polygon(int p_idx) {
153 ERR_FAIL_INDEX_V(p_idx, polygons.size(), Vector<int>());
154 return polygons[p_idx].indices;
155}
156
157void NavigationPolygon::clear_polygons() {
158 polygons.clear();
159 {
160 MutexLock lock(navigation_mesh_generation);
161 navigation_mesh.unref();
162 }
163}
164
165void NavigationPolygon::clear() {
166 polygons.clear();
167 vertices.clear();
168 {
169 MutexLock lock(navigation_mesh_generation);
170 navigation_mesh.unref();
171 }
172}
173
174Ref<NavigationMesh> NavigationPolygon::get_navigation_mesh() {
175 MutexLock lock(navigation_mesh_generation);
176
177 if (navigation_mesh.is_null()) {
178 navigation_mesh.instantiate();
179 Vector<Vector3> verts;
180 {
181 verts.resize(get_vertices().size());
182 Vector3 *w = verts.ptrw();
183
184 const Vector2 *r = get_vertices().ptr();
185
186 for (int i(0); i < get_vertices().size(); i++) {
187 w[i] = Vector3(r[i].x, 0.0, r[i].y);
188 }
189 }
190 navigation_mesh->set_vertices(verts);
191
192 for (int i(0); i < get_polygon_count(); i++) {
193 navigation_mesh->add_polygon(get_polygon(i));
194 }
195 navigation_mesh->set_cell_size(cell_size); // Needed to not fail the cell size check on the server
196 }
197
198 return navigation_mesh;
199}
200
201void NavigationPolygon::add_outline(const Vector<Vector2> &p_outline) {
202 outlines.push_back(p_outline);
203 rect_cache_dirty = true;
204}
205
206int NavigationPolygon::get_outline_count() const {
207 return outlines.size();
208}
209
210void NavigationPolygon::set_outline(int p_idx, const Vector<Vector2> &p_outline) {
211 ERR_FAIL_INDEX(p_idx, outlines.size());
212 outlines.write[p_idx] = p_outline;
213 rect_cache_dirty = true;
214}
215
216void NavigationPolygon::remove_outline(int p_idx) {
217 ERR_FAIL_INDEX(p_idx, outlines.size());
218 outlines.remove_at(p_idx);
219 rect_cache_dirty = true;
220}
221
222Vector<Vector2> NavigationPolygon::get_outline(int p_idx) const {
223 ERR_FAIL_INDEX_V(p_idx, outlines.size(), Vector<Vector2>());
224 return outlines[p_idx];
225}
226
227void NavigationPolygon::clear_outlines() {
228 outlines.clear();
229 rect_cache_dirty = true;
230}
231
232void NavigationPolygon::make_polygons_from_outlines() {
233 {
234 MutexLock lock(navigation_mesh_generation);
235 navigation_mesh.unref();
236 }
237 List<TPPLPoly> in_poly, out_poly;
238
239 Vector2 outside_point(-1e10, -1e10);
240
241 for (int i = 0; i < outlines.size(); i++) {
242 Vector<Vector2> ol = outlines[i];
243 int olsize = ol.size();
244 if (olsize < 3) {
245 continue;
246 }
247 const Vector2 *r = ol.ptr();
248 for (int j = 0; j < olsize; j++) {
249 outside_point.x = MAX(r[j].x, outside_point.x);
250 outside_point.y = MAX(r[j].y, outside_point.y);
251 }
252 }
253
254 outside_point += Vector2(0.7239784, 0.819238); //avoid precision issues
255
256 for (int i = 0; i < outlines.size(); i++) {
257 Vector<Vector2> ol = outlines[i];
258 int olsize = ol.size();
259 if (olsize < 3) {
260 continue;
261 }
262 const Vector2 *r = ol.ptr();
263
264 int interscount = 0;
265 //test if this is an outer outline
266 for (int k = 0; k < outlines.size(); k++) {
267 if (i == k) {
268 continue; //no self intersect
269 }
270
271 Vector<Vector2> ol2 = outlines[k];
272 int olsize2 = ol2.size();
273 if (olsize2 < 3) {
274 continue;
275 }
276 const Vector2 *r2 = ol2.ptr();
277
278 for (int l = 0; l < olsize2; l++) {
279 if (Geometry2D::segment_intersects_segment(r[0], outside_point, r2[l], r2[(l + 1) % olsize2], nullptr)) {
280 interscount++;
281 }
282 }
283 }
284
285 bool outer = (interscount % 2) == 0;
286
287 TPPLPoly tp;
288 tp.Init(olsize);
289 for (int j = 0; j < olsize; j++) {
290 tp[j] = r[j];
291 }
292
293 if (outer) {
294 tp.SetOrientation(TPPL_ORIENTATION_CCW);
295 } else {
296 tp.SetOrientation(TPPL_ORIENTATION_CW);
297 tp.SetHole(true);
298 }
299
300 in_poly.push_back(tp);
301 }
302
303 TPPLPartition tpart;
304 if (tpart.ConvexPartition_HM(&in_poly, &out_poly) == 0) { //failed!
305 ERR_PRINT("NavigationPolygon: Convex partition failed! Failed to convert outlines to a valid NavigationMesh."
306 "\nNavigationPolygon outlines can not overlap vertices or edges inside same outline or with other outlines or have any intersections."
307 "\nAdd the outmost and largest outline first. To add holes inside this outline add the smaller outlines with same winding order.");
308 return;
309 }
310
311 polygons.clear();
312 vertices.clear();
313
314 HashMap<Vector2, int> points;
315 for (List<TPPLPoly>::Element *I = out_poly.front(); I; I = I->next()) {
316 TPPLPoly &tp = I->get();
317
318 struct Polygon p;
319
320 for (int64_t i = 0; i < tp.GetNumPoints(); i++) {
321 HashMap<Vector2, int>::Iterator E = points.find(tp[i]);
322 if (!E) {
323 E = points.insert(tp[i], vertices.size());
324 vertices.push_back(tp[i]);
325 }
326 p.indices.push_back(E->value);
327 }
328
329 polygons.push_back(p);
330 }
331
332 emit_changed();
333}
334
335void NavigationPolygon::set_cell_size(real_t p_cell_size) {
336 cell_size = p_cell_size;
337 get_navigation_mesh()->set_cell_size(cell_size);
338}
339
340real_t NavigationPolygon::get_cell_size() const {
341 return cell_size;
342}
343
344void NavigationPolygon::_bind_methods() {
345 ClassDB::bind_method(D_METHOD("set_vertices", "vertices"), &NavigationPolygon::set_vertices);
346 ClassDB::bind_method(D_METHOD("get_vertices"), &NavigationPolygon::get_vertices);
347
348 ClassDB::bind_method(D_METHOD("add_polygon", "polygon"), &NavigationPolygon::add_polygon);
349 ClassDB::bind_method(D_METHOD("get_polygon_count"), &NavigationPolygon::get_polygon_count);
350 ClassDB::bind_method(D_METHOD("get_polygon", "idx"), &NavigationPolygon::get_polygon);
351 ClassDB::bind_method(D_METHOD("clear_polygons"), &NavigationPolygon::clear_polygons);
352 ClassDB::bind_method(D_METHOD("get_navigation_mesh"), &NavigationPolygon::get_navigation_mesh);
353
354 ClassDB::bind_method(D_METHOD("add_outline", "outline"), &NavigationPolygon::add_outline);
355 ClassDB::bind_method(D_METHOD("add_outline_at_index", "outline", "index"), &NavigationPolygon::add_outline_at_index);
356 ClassDB::bind_method(D_METHOD("get_outline_count"), &NavigationPolygon::get_outline_count);
357 ClassDB::bind_method(D_METHOD("set_outline", "idx", "outline"), &NavigationPolygon::set_outline);
358 ClassDB::bind_method(D_METHOD("get_outline", "idx"), &NavigationPolygon::get_outline);
359 ClassDB::bind_method(D_METHOD("remove_outline", "idx"), &NavigationPolygon::remove_outline);
360 ClassDB::bind_method(D_METHOD("clear_outlines"), &NavigationPolygon::clear_outlines);
361 ClassDB::bind_method(D_METHOD("make_polygons_from_outlines"), &NavigationPolygon::make_polygons_from_outlines);
362
363 ClassDB::bind_method(D_METHOD("_set_polygons", "polygons"), &NavigationPolygon::_set_polygons);
364 ClassDB::bind_method(D_METHOD("_get_polygons"), &NavigationPolygon::_get_polygons);
365
366 ClassDB::bind_method(D_METHOD("_set_outlines", "outlines"), &NavigationPolygon::_set_outlines);
367 ClassDB::bind_method(D_METHOD("_get_outlines"), &NavigationPolygon::_get_outlines);
368
369 ClassDB::bind_method(D_METHOD("set_cell_size", "cell_size"), &NavigationPolygon::set_cell_size);
370 ClassDB::bind_method(D_METHOD("get_cell_size"), &NavigationPolygon::get_cell_size);
371
372 ClassDB::bind_method(D_METHOD("clear"), &NavigationPolygon::clear);
373
374 ADD_PROPERTY(PropertyInfo(Variant::PACKED_VECTOR2_ARRAY, "vertices", PROPERTY_HINT_NONE, "", PROPERTY_USAGE_NO_EDITOR | PROPERTY_USAGE_INTERNAL), "set_vertices", "get_vertices");
375 ADD_PROPERTY(PropertyInfo(Variant::ARRAY, "polygons", PROPERTY_HINT_NONE, "", PROPERTY_USAGE_NO_EDITOR | PROPERTY_USAGE_INTERNAL), "_set_polygons", "_get_polygons");
376 ADD_PROPERTY(PropertyInfo(Variant::ARRAY, "outlines", PROPERTY_HINT_NONE, "", PROPERTY_USAGE_NO_EDITOR | PROPERTY_USAGE_INTERNAL), "_set_outlines", "_get_outlines");
377 ADD_PROPERTY(PropertyInfo(Variant::FLOAT, "cell_size", PROPERTY_HINT_RANGE, "0.01,500.0,0.01,or_greater,suffix:px"), "set_cell_size", "get_cell_size");
378}
379