1/**************************************************************************/
2/* curve.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 "curve.h"
32
33#include "core/math/math_funcs.h"
34
35const char *Curve::SIGNAL_RANGE_CHANGED = "range_changed";
36
37Curve::Curve() {
38}
39
40void Curve::set_point_count(int p_count) {
41 ERR_FAIL_COND(p_count < 0);
42 int old_size = _points.size();
43 if (old_size == p_count) {
44 return;
45 }
46
47 if (old_size > p_count) {
48 _points.resize(p_count);
49 mark_dirty();
50 } else {
51 for (int i = p_count - old_size; i > 0; i--) {
52 _add_point(Vector2());
53 }
54 }
55 notify_property_list_changed();
56}
57
58int Curve::_add_point(Vector2 p_position, real_t p_left_tangent, real_t p_right_tangent, TangentMode p_left_mode, TangentMode p_right_mode) {
59 // Add a point and preserve order
60
61 // Curve bounds is in 0..1
62 if (p_position.x > MAX_X) {
63 p_position.x = MAX_X;
64 } else if (p_position.x < MIN_X) {
65 p_position.x = MIN_X;
66 }
67
68 int ret = -1;
69
70 if (_points.size() == 0) {
71 _points.push_back(Point(p_position, p_left_tangent, p_right_tangent, p_left_mode, p_right_mode));
72 ret = 0;
73
74 } else if (_points.size() == 1) {
75 // TODO Is the `else` able to handle this block already?
76
77 real_t diff = p_position.x - _points[0].position.x;
78
79 if (diff > 0) {
80 _points.push_back(Point(p_position, p_left_tangent, p_right_tangent, p_left_mode, p_right_mode));
81 ret = 1;
82 } else {
83 _points.insert(0, Point(p_position, p_left_tangent, p_right_tangent, p_left_mode, p_right_mode));
84 ret = 0;
85 }
86
87 } else {
88 int i = get_index(p_position.x);
89
90 if (i == 0 && p_position.x < _points[0].position.x) {
91 // Insert before anything else
92 _points.insert(0, Point(p_position, p_left_tangent, p_right_tangent, p_left_mode, p_right_mode));
93 ret = 0;
94 } else {
95 // Insert between i and i+1
96 ++i;
97 _points.insert(i, Point(p_position, p_left_tangent, p_right_tangent, p_left_mode, p_right_mode));
98 ret = i;
99 }
100 }
101
102 update_auto_tangents(ret);
103
104 mark_dirty();
105
106 return ret;
107}
108
109int Curve::add_point(Vector2 p_position, real_t p_left_tangent, real_t p_right_tangent, TangentMode p_left_mode, TangentMode p_right_mode) {
110 int ret = _add_point(p_position, p_left_tangent, p_right_tangent, p_left_mode, p_right_mode);
111 notify_property_list_changed();
112
113 return ret;
114}
115
116// TODO: Needed to make the curve editor function properly until https://github.com/godotengine/godot/issues/76985 is fixed.
117int Curve::add_point_no_update(Vector2 p_position, real_t p_left_tangent, real_t p_right_tangent, TangentMode p_left_mode, TangentMode p_right_mode) {
118 int ret = _add_point(p_position, p_left_tangent, p_right_tangent, p_left_mode, p_right_mode);
119
120 return ret;
121}
122
123int Curve::get_index(real_t p_offset) const {
124 // Lower-bound float binary search
125
126 int imin = 0;
127 int imax = _points.size() - 1;
128
129 while (imax - imin > 1) {
130 int m = (imin + imax) / 2;
131
132 real_t a = _points[m].position.x;
133 real_t b = _points[m + 1].position.x;
134
135 if (a < p_offset && b < p_offset) {
136 imin = m;
137
138 } else if (a > p_offset) {
139 imax = m;
140
141 } else {
142 return m;
143 }
144 }
145
146 // Will happen if the offset is out of bounds
147 if (p_offset > _points[imax].position.x) {
148 return imax;
149 }
150 return imin;
151}
152
153void Curve::clean_dupes() {
154 bool dirty = false;
155
156 for (int i = 1; i < _points.size(); ++i) {
157 real_t diff = _points[i - 1].position.x - _points[i].position.x;
158 if (diff <= CMP_EPSILON) {
159 _points.remove_at(i);
160 --i;
161 dirty = true;
162 }
163 }
164
165 if (dirty) {
166 mark_dirty();
167 }
168}
169
170void Curve::set_point_left_tangent(int p_index, real_t p_tangent) {
171 ERR_FAIL_INDEX(p_index, _points.size());
172 _points.write[p_index].left_tangent = p_tangent;
173 _points.write[p_index].left_mode = TANGENT_FREE;
174 mark_dirty();
175}
176
177void Curve::set_point_right_tangent(int p_index, real_t p_tangent) {
178 ERR_FAIL_INDEX(p_index, _points.size());
179 _points.write[p_index].right_tangent = p_tangent;
180 _points.write[p_index].right_mode = TANGENT_FREE;
181 mark_dirty();
182}
183
184void Curve::set_point_left_mode(int p_index, TangentMode p_mode) {
185 ERR_FAIL_INDEX(p_index, _points.size());
186 _points.write[p_index].left_mode = p_mode;
187 if (p_index > 0) {
188 if (p_mode == TANGENT_LINEAR) {
189 Vector2 v = (_points[p_index - 1].position - _points[p_index].position).normalized();
190 _points.write[p_index].left_tangent = v.y / v.x;
191 }
192 }
193 mark_dirty();
194}
195
196void Curve::set_point_right_mode(int p_index, TangentMode p_mode) {
197 ERR_FAIL_INDEX(p_index, _points.size());
198 _points.write[p_index].right_mode = p_mode;
199 if (p_index + 1 < _points.size()) {
200 if (p_mode == TANGENT_LINEAR) {
201 Vector2 v = (_points[p_index + 1].position - _points[p_index].position).normalized();
202 _points.write[p_index].right_tangent = v.y / v.x;
203 }
204 }
205 mark_dirty();
206}
207
208real_t Curve::get_point_left_tangent(int p_index) const {
209 ERR_FAIL_INDEX_V(p_index, _points.size(), 0);
210 return _points[p_index].left_tangent;
211}
212
213real_t Curve::get_point_right_tangent(int p_index) const {
214 ERR_FAIL_INDEX_V(p_index, _points.size(), 0);
215 return _points[p_index].right_tangent;
216}
217
218Curve::TangentMode Curve::get_point_left_mode(int p_index) const {
219 ERR_FAIL_INDEX_V(p_index, _points.size(), TANGENT_FREE);
220 return _points[p_index].left_mode;
221}
222
223Curve::TangentMode Curve::get_point_right_mode(int p_index) const {
224 ERR_FAIL_INDEX_V(p_index, _points.size(), TANGENT_FREE);
225 return _points[p_index].right_mode;
226}
227
228void Curve::_remove_point(int p_index) {
229 ERR_FAIL_INDEX(p_index, _points.size());
230 _points.remove_at(p_index);
231 mark_dirty();
232}
233
234void Curve::remove_point(int p_index) {
235 _remove_point(p_index);
236 notify_property_list_changed();
237}
238
239void Curve::clear_points() {
240 if (_points.is_empty()) {
241 return;
242 }
243
244 _points.clear();
245 mark_dirty();
246 notify_property_list_changed();
247}
248
249void Curve::set_point_value(int p_index, real_t p_position) {
250 ERR_FAIL_INDEX(p_index, _points.size());
251 _points.write[p_index].position.y = p_position;
252 update_auto_tangents(p_index);
253 mark_dirty();
254}
255
256int Curve::set_point_offset(int p_index, real_t p_offset) {
257 ERR_FAIL_INDEX_V(p_index, _points.size(), -1);
258 Point p = _points[p_index];
259 _remove_point(p_index);
260 int i = _add_point(Vector2(p_offset, p.position.y));
261 _points.write[i].left_tangent = p.left_tangent;
262 _points.write[i].right_tangent = p.right_tangent;
263 _points.write[i].left_mode = p.left_mode;
264 _points.write[i].right_mode = p.right_mode;
265 if (p_index != i) {
266 update_auto_tangents(p_index);
267 }
268 update_auto_tangents(i);
269 return i;
270}
271
272Vector2 Curve::get_point_position(int p_index) const {
273 ERR_FAIL_INDEX_V(p_index, _points.size(), Vector2(0, 0));
274 return _points[p_index].position;
275}
276
277Curve::Point Curve::get_point(int p_index) const {
278 ERR_FAIL_INDEX_V(p_index, _points.size(), Point());
279 return _points[p_index];
280}
281
282void Curve::update_auto_tangents(int p_index) {
283 Point &p = _points.write[p_index];
284
285 if (p_index > 0) {
286 if (p.left_mode == TANGENT_LINEAR) {
287 Vector2 v = (_points[p_index - 1].position - p.position).normalized();
288 p.left_tangent = v.y / v.x;
289 }
290 if (_points[p_index - 1].right_mode == TANGENT_LINEAR) {
291 Vector2 v = (_points[p_index - 1].position - p.position).normalized();
292 _points.write[p_index - 1].right_tangent = v.y / v.x;
293 }
294 }
295
296 if (p_index + 1 < _points.size()) {
297 if (p.right_mode == TANGENT_LINEAR) {
298 Vector2 v = (_points[p_index + 1].position - p.position).normalized();
299 p.right_tangent = v.y / v.x;
300 }
301 if (_points[p_index + 1].left_mode == TANGENT_LINEAR) {
302 Vector2 v = (_points[p_index + 1].position - p.position).normalized();
303 _points.write[p_index + 1].left_tangent = v.y / v.x;
304 }
305 }
306}
307
308#define MIN_Y_RANGE 0.01
309
310void Curve::set_min_value(real_t p_min) {
311 if (_minmax_set_once & 0b11 && p_min > _max_value - MIN_Y_RANGE) {
312 _min_value = _max_value - MIN_Y_RANGE;
313 } else {
314 _minmax_set_once |= 0b10; // first bit is "min set"
315 _min_value = p_min;
316 }
317 // Note: min and max are indicative values,
318 // it's still possible that existing points are out of range at this point.
319 emit_signal(SNAME(SIGNAL_RANGE_CHANGED));
320}
321
322void Curve::set_max_value(real_t p_max) {
323 if (_minmax_set_once & 0b11 && p_max < _min_value + MIN_Y_RANGE) {
324 _max_value = _min_value + MIN_Y_RANGE;
325 } else {
326 _minmax_set_once |= 0b01; // second bit is "max set"
327 _max_value = p_max;
328 }
329 emit_signal(SNAME(SIGNAL_RANGE_CHANGED));
330}
331
332real_t Curve::sample(real_t p_offset) const {
333 if (_points.size() == 0) {
334 return 0;
335 }
336 if (_points.size() == 1) {
337 return _points[0].position.y;
338 }
339
340 int i = get_index(p_offset);
341
342 if (i == _points.size() - 1) {
343 return _points[i].position.y;
344 }
345
346 real_t local = p_offset - _points[i].position.x;
347
348 if (i == 0 && local <= 0) {
349 return _points[0].position.y;
350 }
351
352 return sample_local_nocheck(i, local);
353}
354
355real_t Curve::sample_local_nocheck(int p_index, real_t p_local_offset) const {
356 const Point a = _points[p_index];
357 const Point b = _points[p_index + 1];
358
359 /* Cubic bézier
360 *
361 * ac-----bc
362 * / \
363 * / \ Here with a.right_tangent > 0
364 * / \ and b.left_tangent < 0
365 * / \
366 * a b
367 *
368 * |-d1--|-d2--|-d3--|
369 *
370 * d1 == d2 == d3 == d / 3
371 */
372
373 // Control points are chosen at equal distances
374 real_t d = b.position.x - a.position.x;
375 if (Math::is_zero_approx(d)) {
376 return b.position.y;
377 }
378 p_local_offset /= d;
379 d /= 3.0;
380 real_t yac = a.position.y + d * a.right_tangent;
381 real_t ybc = b.position.y - d * b.left_tangent;
382
383 real_t y = Math::bezier_interpolate(a.position.y, yac, ybc, b.position.y, p_local_offset);
384
385 return y;
386}
387
388void Curve::mark_dirty() {
389 _baked_cache_dirty = true;
390 emit_changed();
391}
392
393Array Curve::get_data() const {
394 Array output;
395 const unsigned int ELEMS = 5;
396 output.resize(_points.size() * ELEMS);
397
398 for (int j = 0; j < _points.size(); ++j) {
399 const Point p = _points[j];
400 int i = j * ELEMS;
401
402 output[i] = p.position;
403 output[i + 1] = p.left_tangent;
404 output[i + 2] = p.right_tangent;
405 output[i + 3] = p.left_mode;
406 output[i + 4] = p.right_mode;
407 }
408
409 return output;
410}
411
412void Curve::set_data(const Array p_input) {
413 const unsigned int ELEMS = 5;
414 ERR_FAIL_COND(p_input.size() % ELEMS != 0);
415
416 // Validate input
417 for (int i = 0; i < p_input.size(); i += ELEMS) {
418 ERR_FAIL_COND(p_input[i].get_type() != Variant::VECTOR2);
419 ERR_FAIL_COND(!p_input[i + 1].is_num());
420 ERR_FAIL_COND(p_input[i + 2].get_type() != Variant::FLOAT);
421
422 ERR_FAIL_COND(p_input[i + 3].get_type() != Variant::INT);
423 int left_mode = p_input[i + 3];
424 ERR_FAIL_COND(left_mode < 0 || left_mode >= TANGENT_MODE_COUNT);
425
426 ERR_FAIL_COND(p_input[i + 4].get_type() != Variant::INT);
427 int right_mode = p_input[i + 4];
428 ERR_FAIL_COND(right_mode < 0 || right_mode >= TANGENT_MODE_COUNT);
429 }
430 int old_size = _points.size();
431 int new_size = p_input.size() / ELEMS;
432 if (old_size != new_size) {
433 _points.resize(new_size);
434 }
435
436 for (int j = 0; j < _points.size(); ++j) {
437 Point &p = _points.write[j];
438 int i = j * ELEMS;
439
440 p.position = p_input[i];
441 p.left_tangent = p_input[i + 1];
442 p.right_tangent = p_input[i + 2];
443 int left_mode = p_input[i + 3];
444 int right_mode = p_input[i + 4];
445 p.left_mode = (TangentMode)left_mode;
446 p.right_mode = (TangentMode)right_mode;
447 }
448
449 mark_dirty();
450 if (old_size != new_size) {
451 notify_property_list_changed();
452 }
453}
454
455void Curve::bake() {
456 _baked_cache.clear();
457
458 _baked_cache.resize(_bake_resolution);
459
460 for (int i = 1; i < _bake_resolution - 1; ++i) {
461 real_t x = i / static_cast<real_t>(_bake_resolution - 1);
462 real_t y = sample(x);
463 _baked_cache.write[i] = y;
464 }
465
466 if (_points.size() != 0) {
467 _baked_cache.write[0] = _points[0].position.y;
468 _baked_cache.write[_baked_cache.size() - 1] = _points[_points.size() - 1].position.y;
469 }
470
471 _baked_cache_dirty = false;
472}
473
474void Curve::set_bake_resolution(int p_resolution) {
475 ERR_FAIL_COND(p_resolution < 1);
476 ERR_FAIL_COND(p_resolution > 1000);
477 _bake_resolution = p_resolution;
478 _baked_cache_dirty = true;
479}
480
481real_t Curve::sample_baked(real_t p_offset) const {
482 if (_baked_cache_dirty) {
483 // Last-second bake if not done already
484 const_cast<Curve *>(this)->bake();
485 }
486
487 // Special cases if the cache is too small
488 if (_baked_cache.size() == 0) {
489 if (_points.size() == 0) {
490 return 0;
491 }
492 return _points[0].position.y;
493 } else if (_baked_cache.size() == 1) {
494 return _baked_cache[0];
495 }
496
497 // Get interpolation index
498 real_t fi = p_offset * (_baked_cache.size() - 1);
499 int i = Math::floor(fi);
500 if (i < 0) {
501 i = 0;
502 fi = 0;
503 } else if (i >= _baked_cache.size()) {
504 i = _baked_cache.size() - 1;
505 fi = 0;
506 }
507
508 // Sample
509 if (i + 1 < _baked_cache.size()) {
510 real_t t = fi - i;
511 return Math::lerp(_baked_cache[i], _baked_cache[i + 1], t);
512 } else {
513 return _baked_cache[_baked_cache.size() - 1];
514 }
515}
516
517void Curve::ensure_default_setup(real_t p_min, real_t p_max) {
518 if (_points.size() == 0 && _min_value == 0 && _max_value == 1) {
519 add_point(Vector2(0, 1));
520 add_point(Vector2(1, 1));
521 set_min_value(p_min);
522 set_max_value(p_max);
523 }
524}
525
526bool Curve::_set(const StringName &p_name, const Variant &p_value) {
527 Vector<String> components = String(p_name).split("/", true, 2);
528 if (components.size() >= 2 && components[0].begins_with("point_") && components[0].trim_prefix("point_").is_valid_int()) {
529 int point_index = components[0].trim_prefix("point_").to_int();
530 String property = components[1];
531 if (property == "position") {
532 Vector2 position = p_value.operator Vector2();
533 set_point_offset(point_index, position.x);
534 set_point_value(point_index, position.y);
535 return true;
536 } else if (property == "left_tangent") {
537 set_point_left_tangent(point_index, p_value);
538 return true;
539 } else if (property == "left_mode") {
540 int mode = p_value;
541 set_point_left_mode(point_index, (TangentMode)mode);
542 return true;
543 } else if (property == "right_tangent") {
544 set_point_right_tangent(point_index, p_value);
545 return true;
546 } else if (property == "right_mode") {
547 int mode = p_value;
548 set_point_right_mode(point_index, (TangentMode)mode);
549 return true;
550 }
551 }
552 return false;
553}
554
555bool Curve::_get(const StringName &p_name, Variant &r_ret) const {
556 Vector<String> components = String(p_name).split("/", true, 2);
557 if (components.size() >= 2 && components[0].begins_with("point_") && components[0].trim_prefix("point_").is_valid_int()) {
558 int point_index = components[0].trim_prefix("point_").to_int();
559 String property = components[1];
560 if (property == "position") {
561 r_ret = get_point_position(point_index);
562 return true;
563 } else if (property == "left_tangent") {
564 r_ret = get_point_left_tangent(point_index);
565 return true;
566 } else if (property == "left_mode") {
567 r_ret = get_point_left_mode(point_index);
568 return true;
569 } else if (property == "right_tangent") {
570 r_ret = get_point_right_tangent(point_index);
571 return true;
572 } else if (property == "right_mode") {
573 r_ret = get_point_right_mode(point_index);
574 return true;
575 }
576 }
577 return false;
578}
579
580void Curve::_get_property_list(List<PropertyInfo> *p_list) const {
581 for (int i = 0; i < _points.size(); i++) {
582 PropertyInfo pi = PropertyInfo(Variant::VECTOR2, vformat("point_%d/position", i));
583 pi.usage &= ~PROPERTY_USAGE_STORAGE;
584 p_list->push_back(pi);
585
586 if (i != 0) {
587 pi = PropertyInfo(Variant::FLOAT, vformat("point_%d/left_tangent", i));
588 pi.usage &= ~PROPERTY_USAGE_STORAGE;
589 p_list->push_back(pi);
590
591 pi = PropertyInfo(Variant::INT, vformat("point_%d/left_mode", i), PROPERTY_HINT_ENUM, "Free,Linear");
592 pi.usage &= ~PROPERTY_USAGE_STORAGE;
593 p_list->push_back(pi);
594 }
595
596 if (i != _points.size() - 1) {
597 pi = PropertyInfo(Variant::FLOAT, vformat("point_%d/right_tangent", i));
598 pi.usage &= ~PROPERTY_USAGE_STORAGE;
599 p_list->push_back(pi);
600
601 pi = PropertyInfo(Variant::INT, vformat("point_%d/right_mode", i), PROPERTY_HINT_ENUM, "Free,Linear");
602 pi.usage &= ~PROPERTY_USAGE_STORAGE;
603 p_list->push_back(pi);
604 }
605 }
606}
607
608void Curve::_bind_methods() {
609 ClassDB::bind_method(D_METHOD("get_point_count"), &Curve::get_point_count);
610 ClassDB::bind_method(D_METHOD("set_point_count", "count"), &Curve::set_point_count);
611 ClassDB::bind_method(D_METHOD("add_point", "position", "left_tangent", "right_tangent", "left_mode", "right_mode"), &Curve::add_point, DEFVAL(0), DEFVAL(0), DEFVAL(TANGENT_FREE), DEFVAL(TANGENT_FREE));
612 ClassDB::bind_method(D_METHOD("remove_point", "index"), &Curve::remove_point);
613 ClassDB::bind_method(D_METHOD("clear_points"), &Curve::clear_points);
614 ClassDB::bind_method(D_METHOD("get_point_position", "index"), &Curve::get_point_position);
615 ClassDB::bind_method(D_METHOD("set_point_value", "index", "y"), &Curve::set_point_value);
616 ClassDB::bind_method(D_METHOD("set_point_offset", "index", "offset"), &Curve::set_point_offset);
617 ClassDB::bind_method(D_METHOD("sample", "offset"), &Curve::sample);
618 ClassDB::bind_method(D_METHOD("sample_baked", "offset"), &Curve::sample_baked);
619 ClassDB::bind_method(D_METHOD("get_point_left_tangent", "index"), &Curve::get_point_left_tangent);
620 ClassDB::bind_method(D_METHOD("get_point_right_tangent", "index"), &Curve::get_point_right_tangent);
621 ClassDB::bind_method(D_METHOD("get_point_left_mode", "index"), &Curve::get_point_left_mode);
622 ClassDB::bind_method(D_METHOD("get_point_right_mode", "index"), &Curve::get_point_right_mode);
623 ClassDB::bind_method(D_METHOD("set_point_left_tangent", "index", "tangent"), &Curve::set_point_left_tangent);
624 ClassDB::bind_method(D_METHOD("set_point_right_tangent", "index", "tangent"), &Curve::set_point_right_tangent);
625 ClassDB::bind_method(D_METHOD("set_point_left_mode", "index", "mode"), &Curve::set_point_left_mode);
626 ClassDB::bind_method(D_METHOD("set_point_right_mode", "index", "mode"), &Curve::set_point_right_mode);
627 ClassDB::bind_method(D_METHOD("get_min_value"), &Curve::get_min_value);
628 ClassDB::bind_method(D_METHOD("set_min_value", "min"), &Curve::set_min_value);
629 ClassDB::bind_method(D_METHOD("get_max_value"), &Curve::get_max_value);
630 ClassDB::bind_method(D_METHOD("set_max_value", "max"), &Curve::set_max_value);
631 ClassDB::bind_method(D_METHOD("clean_dupes"), &Curve::clean_dupes);
632 ClassDB::bind_method(D_METHOD("bake"), &Curve::bake);
633 ClassDB::bind_method(D_METHOD("get_bake_resolution"), &Curve::get_bake_resolution);
634 ClassDB::bind_method(D_METHOD("set_bake_resolution", "resolution"), &Curve::set_bake_resolution);
635 ClassDB::bind_method(D_METHOD("_get_data"), &Curve::get_data);
636 ClassDB::bind_method(D_METHOD("_set_data", "data"), &Curve::set_data);
637
638 ADD_PROPERTY(PropertyInfo(Variant::FLOAT, "min_value", PROPERTY_HINT_RANGE, "-1024,1024,0.01"), "set_min_value", "get_min_value");
639 ADD_PROPERTY(PropertyInfo(Variant::FLOAT, "max_value", PROPERTY_HINT_RANGE, "-1024,1024,0.01"), "set_max_value", "get_max_value");
640 ADD_PROPERTY(PropertyInfo(Variant::INT, "bake_resolution", PROPERTY_HINT_RANGE, "1,1000,1"), "set_bake_resolution", "get_bake_resolution");
641 ADD_PROPERTY(PropertyInfo(Variant::INT, "_data", PROPERTY_HINT_NONE, "", PROPERTY_USAGE_NO_EDITOR | PROPERTY_USAGE_INTERNAL), "_set_data", "_get_data");
642 ADD_ARRAY_COUNT("Points", "point_count", "set_point_count", "get_point_count", "point_");
643
644 ADD_SIGNAL(MethodInfo(SIGNAL_RANGE_CHANGED));
645
646 BIND_ENUM_CONSTANT(TANGENT_FREE);
647 BIND_ENUM_CONSTANT(TANGENT_LINEAR);
648 BIND_ENUM_CONSTANT(TANGENT_MODE_COUNT);
649}
650
651int Curve2D::get_point_count() const {
652 return points.size();
653}
654
655void Curve2D::set_point_count(int p_count) {
656 ERR_FAIL_COND(p_count < 0);
657 int old_size = points.size();
658 if (old_size == p_count) {
659 return;
660 }
661
662 if (old_size > p_count) {
663 points.resize(p_count);
664 mark_dirty();
665 } else {
666 for (int i = p_count - old_size; i > 0; i--) {
667 _add_point(Vector2());
668 }
669 }
670 notify_property_list_changed();
671}
672
673void Curve2D::_add_point(const Vector2 &p_position, const Vector2 &p_in, const Vector2 &p_out, int p_atpos) {
674 Point n;
675 n.position = p_position;
676 n.in = p_in;
677 n.out = p_out;
678 if (p_atpos >= 0 && p_atpos < points.size()) {
679 points.insert(p_atpos, n);
680 } else {
681 points.push_back(n);
682 }
683
684 mark_dirty();
685}
686
687void Curve2D::add_point(const Vector2 &p_position, const Vector2 &p_in, const Vector2 &p_out, int p_atpos) {
688 _add_point(p_position, p_in, p_out, p_atpos);
689 notify_property_list_changed();
690}
691
692void Curve2D::set_point_position(int p_index, const Vector2 &p_position) {
693 ERR_FAIL_INDEX(p_index, points.size());
694
695 points.write[p_index].position = p_position;
696 mark_dirty();
697}
698
699Vector2 Curve2D::get_point_position(int p_index) const {
700 ERR_FAIL_INDEX_V(p_index, points.size(), Vector2());
701 return points[p_index].position;
702}
703
704void Curve2D::set_point_in(int p_index, const Vector2 &p_in) {
705 ERR_FAIL_INDEX(p_index, points.size());
706
707 points.write[p_index].in = p_in;
708 mark_dirty();
709}
710
711Vector2 Curve2D::get_point_in(int p_index) const {
712 ERR_FAIL_INDEX_V(p_index, points.size(), Vector2());
713 return points[p_index].in;
714}
715
716void Curve2D::set_point_out(int p_index, const Vector2 &p_out) {
717 ERR_FAIL_INDEX(p_index, points.size());
718
719 points.write[p_index].out = p_out;
720 mark_dirty();
721}
722
723Vector2 Curve2D::get_point_out(int p_index) const {
724 ERR_FAIL_INDEX_V(p_index, points.size(), Vector2());
725 return points[p_index].out;
726}
727
728void Curve2D::_remove_point(int p_index) {
729 ERR_FAIL_INDEX(p_index, points.size());
730 points.remove_at(p_index);
731 mark_dirty();
732}
733
734void Curve2D::remove_point(int p_index) {
735 _remove_point(p_index);
736 notify_property_list_changed();
737}
738
739void Curve2D::clear_points() {
740 if (!points.is_empty()) {
741 points.clear();
742 mark_dirty();
743 notify_property_list_changed();
744 }
745}
746
747Vector2 Curve2D::sample(int p_index, const real_t p_offset) const {
748 int pc = points.size();
749 ERR_FAIL_COND_V(pc == 0, Vector2());
750
751 if (p_index >= pc - 1) {
752 return points[pc - 1].position;
753 } else if (p_index < 0) {
754 return points[0].position;
755 }
756
757 Vector2 p0 = points[p_index].position;
758 Vector2 p1 = p0 + points[p_index].out;
759 Vector2 p3 = points[p_index + 1].position;
760 Vector2 p2 = p3 + points[p_index + 1].in;
761
762 return p0.bezier_interpolate(p1, p2, p3, p_offset);
763}
764
765Vector2 Curve2D::samplef(real_t p_findex) const {
766 if (p_findex < 0) {
767 p_findex = 0;
768 } else if (p_findex >= points.size()) {
769 p_findex = points.size();
770 }
771
772 return sample((int)p_findex, Math::fmod(p_findex, (real_t)1.0));
773}
774
775void Curve2D::mark_dirty() {
776 baked_cache_dirty = true;
777 emit_changed();
778}
779
780void Curve2D::_bake_segment2d(RBMap<real_t, Vector2> &r_bake, real_t p_begin, real_t p_end, const Vector2 &p_a, const Vector2 &p_out, const Vector2 &p_b, const Vector2 &p_in, int p_depth, int p_max_depth, real_t p_tol) const {
781 real_t mp = p_begin + (p_end - p_begin) * 0.5;
782 Vector2 beg = p_a.bezier_interpolate(p_a + p_out, p_b + p_in, p_b, p_begin);
783 Vector2 mid = p_a.bezier_interpolate(p_a + p_out, p_b + p_in, p_b, mp);
784 Vector2 end = p_a.bezier_interpolate(p_a + p_out, p_b + p_in, p_b, p_end);
785
786 Vector2 na = (mid - beg).normalized();
787 Vector2 nb = (end - mid).normalized();
788 real_t dp = na.dot(nb);
789
790 if (dp < Math::cos(Math::deg_to_rad(p_tol))) {
791 r_bake[mp] = mid;
792 }
793
794 if (p_depth < p_max_depth) {
795 _bake_segment2d(r_bake, p_begin, mp, p_a, p_out, p_b, p_in, p_depth + 1, p_max_depth, p_tol);
796 _bake_segment2d(r_bake, mp, p_end, p_a, p_out, p_b, p_in, p_depth + 1, p_max_depth, p_tol);
797 }
798}
799
800void Curve2D::_bake_segment2d_even_length(RBMap<real_t, Vector2> &r_bake, real_t p_begin, real_t p_end, const Vector2 &p_a, const Vector2 &p_out, const Vector2 &p_b, const Vector2 &p_in, int p_depth, int p_max_depth, real_t p_length) const {
801 Vector2 beg = p_a.bezier_interpolate(p_a + p_out, p_b + p_in, p_b, p_begin);
802 Vector2 end = p_a.bezier_interpolate(p_a + p_out, p_b + p_in, p_b, p_end);
803
804 real_t length = beg.distance_to(end);
805
806 if (length > p_length && p_depth < p_max_depth) {
807 real_t mp = (p_begin + p_end) * 0.5;
808 Vector2 mid = p_a.bezier_interpolate(p_a + p_out, p_b + p_in, p_b, mp);
809 r_bake[mp] = mid;
810
811 _bake_segment2d_even_length(r_bake, p_begin, mp, p_a, p_out, p_b, p_in, p_depth + 1, p_max_depth, p_length);
812 _bake_segment2d_even_length(r_bake, mp, p_end, p_a, p_out, p_b, p_in, p_depth + 1, p_max_depth, p_length);
813 }
814}
815
816Vector2 Curve2D::_calculate_tangent(const Vector2 &p_begin, const Vector2 &p_control_1, const Vector2 &p_control_2, const Vector2 &p_end, const real_t p_t) {
817 // Handle corner cases.
818 if (Math::is_zero_approx(p_t - 0.0f) && p_control_1.is_equal_approx(p_begin)) {
819 return (p_end - p_begin).normalized();
820 }
821
822 if (Math::is_zero_approx(p_t - 1.0f) && p_control_2.is_equal_approx(p_end)) {
823 return (p_end - p_begin).normalized();
824 }
825
826 return p_begin.bezier_derivative(p_control_1, p_control_2, p_end, p_t).normalized();
827}
828
829void Curve2D::_bake() const {
830 if (!baked_cache_dirty) {
831 return;
832 }
833
834 baked_max_ofs = 0;
835 baked_cache_dirty = false;
836
837 if (points.size() == 0) {
838 baked_point_cache.clear();
839 baked_dist_cache.clear();
840 baked_forward_vector_cache.clear();
841 return;
842 }
843
844 if (points.size() == 1) {
845 baked_point_cache.resize(1);
846 baked_point_cache.set(0, points[0].position);
847 baked_dist_cache.resize(1);
848 baked_dist_cache.set(0, 0.0);
849 baked_forward_vector_cache.resize(1);
850 baked_forward_vector_cache.set(0, Vector2(0.0, 0.1));
851
852 return;
853 }
854
855 // Tessellate curve to (almost) even length segments
856 {
857 Vector<RBMap<real_t, Vector2>> midpoints = _tessellate_even_length(10, bake_interval);
858
859 int pc = 1;
860 for (int i = 0; i < points.size() - 1; i++) {
861 pc++;
862 pc += midpoints[i].size();
863 }
864
865 baked_point_cache.resize(pc);
866 baked_dist_cache.resize(pc);
867 baked_forward_vector_cache.resize(pc);
868
869 Vector2 *bpw = baked_point_cache.ptrw();
870 Vector2 *bfw = baked_forward_vector_cache.ptrw();
871
872 // Collect positions and sample tilts and tangents for each baked points.
873 bpw[0] = points[0].position;
874 bfw[0] = _calculate_tangent(points[0].position, points[0].position + points[0].out, points[1].position + points[1].in, points[1].position, 0.0);
875 int pidx = 0;
876
877 for (int i = 0; i < points.size() - 1; i++) {
878 for (const KeyValue<real_t, Vector2> &E : midpoints[i]) {
879 pidx++;
880 bpw[pidx] = E.value;
881 bfw[pidx] = _calculate_tangent(points[i].position, points[i].position + points[i].out, points[i + 1].position + points[i + 1].in, points[i + 1].position, E.key);
882 }
883
884 pidx++;
885 bpw[pidx] = points[i + 1].position;
886 bfw[pidx] = _calculate_tangent(points[i].position, points[i].position + points[i].out, points[i + 1].position + points[i + 1].in, points[i + 1].position, 1.0);
887 }
888
889 // Recalculate the baked distances.
890 real_t *bdw = baked_dist_cache.ptrw();
891 bdw[0] = 0.0;
892 for (int i = 0; i < pc - 1; i++) {
893 bdw[i + 1] = bdw[i] + bpw[i].distance_to(bpw[i + 1]);
894 }
895 baked_max_ofs = bdw[pc - 1];
896 }
897}
898
899real_t Curve2D::get_baked_length() const {
900 if (baked_cache_dirty) {
901 _bake();
902 }
903
904 return baked_max_ofs;
905}
906
907Curve2D::Interval Curve2D::_find_interval(real_t p_offset) const {
908 Interval interval = {
909 -1,
910 0.0
911 };
912 ERR_FAIL_COND_V_MSG(baked_cache_dirty, interval, "Backed cache is dirty");
913
914 int pc = baked_point_cache.size();
915 ERR_FAIL_COND_V_MSG(pc < 2, interval, "Less than two points in cache");
916
917 int start = 0;
918 int end = pc;
919 int idx = (end + start) / 2;
920 // Binary search to find baked points.
921 while (start < idx) {
922 real_t offset = baked_dist_cache[idx];
923 if (p_offset <= offset) {
924 end = idx;
925 } else {
926 start = idx;
927 }
928 idx = (end + start) / 2;
929 }
930
931 real_t offset_begin = baked_dist_cache[idx];
932 real_t offset_end = baked_dist_cache[idx + 1];
933
934 real_t idx_interval = offset_end - offset_begin;
935 ERR_FAIL_COND_V_MSG(p_offset < offset_begin || p_offset > offset_end, interval, "Offset out of range.");
936
937 interval.idx = idx;
938 if (idx_interval < FLT_EPSILON) {
939 interval.frac = 0.5; // For a very short interval, 0.5 is a reasonable choice.
940 ERR_FAIL_V_MSG(interval, "Zero length interval.");
941 }
942
943 interval.frac = (p_offset - offset_begin) / idx_interval;
944 return interval;
945}
946
947Vector2 Curve2D::_sample_baked(Interval p_interval, bool p_cubic) const {
948 // Assuming p_interval is valid.
949 ERR_FAIL_INDEX_V_MSG(p_interval.idx, baked_point_cache.size(), Vector2(), "Invalid interval");
950
951 int idx = p_interval.idx;
952 real_t frac = p_interval.frac;
953
954 const Vector2 *r = baked_point_cache.ptr();
955 int pc = baked_point_cache.size();
956
957 if (p_cubic) {
958 Vector2 pre = idx > 0 ? r[idx - 1] : r[idx];
959 Vector2 post = (idx < (pc - 2)) ? r[idx + 2] : r[idx + 1];
960 return r[idx].cubic_interpolate(r[idx + 1], pre, post, frac);
961 } else {
962 return r[idx].lerp(r[idx + 1], frac);
963 }
964}
965
966Transform2D Curve2D::_sample_posture(Interval p_interval) const {
967 // Assuming that p_interval is valid.
968 ERR_FAIL_INDEX_V_MSG(p_interval.idx, baked_point_cache.size(), Transform2D(), "Invalid interval");
969
970 int idx = p_interval.idx;
971 real_t frac = p_interval.frac;
972
973 Vector2 forward_begin = baked_forward_vector_cache[idx];
974 Vector2 forward_end = baked_forward_vector_cache[idx + 1];
975
976 // Build frames at both ends of the interval, then interpolate.
977 const Vector2 forward = forward_begin.slerp(forward_end, frac).normalized();
978 const Vector2 side = Vector2(-forward.y, forward.x);
979
980 return Transform2D(side, forward, Vector2(0.0, 0.0));
981}
982
983Vector2 Curve2D::sample_baked(real_t p_offset, bool p_cubic) const {
984 if (baked_cache_dirty) {
985 _bake();
986 }
987
988 // Validate: Curve may not have baked points.
989 int pc = baked_point_cache.size();
990 ERR_FAIL_COND_V_MSG(pc == 0, Vector2(), "No points in Curve2D.");
991
992 if (pc == 1) {
993 return baked_point_cache[0];
994 }
995
996 p_offset = CLAMP(p_offset, 0.0, get_baked_length()); // PathFollower implement wrapping logic.
997
998 Curve2D::Interval interval = _find_interval(p_offset);
999 return _sample_baked(interval, p_cubic);
1000}
1001
1002Transform2D Curve2D::sample_baked_with_rotation(real_t p_offset, bool p_cubic) const {
1003 if (baked_cache_dirty) {
1004 _bake();
1005 }
1006
1007 // Validate: Curve may not have baked points.
1008 const int point_count = baked_point_cache.size();
1009 ERR_FAIL_COND_V_MSG(point_count == 0, Transform2D(), "No points in Curve3D.");
1010
1011 if (point_count == 1) {
1012 Transform2D t;
1013 t.set_origin(baked_point_cache.get(0));
1014 ERR_FAIL_V_MSG(t, "Only 1 point in Curve2D.");
1015 }
1016
1017 p_offset = CLAMP(p_offset, 0.0, get_baked_length()); // PathFollower implement wrapping logic.
1018
1019 // 0. Find interval for all sampling steps.
1020 Curve2D::Interval interval = _find_interval(p_offset);
1021
1022 // 1. Sample position.
1023 Vector2 pos = _sample_baked(interval, p_cubic);
1024
1025 // 2. Sample rotation frame.
1026 Transform2D frame = _sample_posture(interval);
1027 frame.set_origin(pos);
1028
1029 return frame;
1030}
1031
1032PackedVector2Array Curve2D::get_baked_points() const {
1033 if (baked_cache_dirty) {
1034 _bake();
1035 }
1036
1037 return baked_point_cache;
1038}
1039
1040void Curve2D::set_bake_interval(real_t p_tolerance) {
1041 bake_interval = p_tolerance;
1042 mark_dirty();
1043}
1044
1045real_t Curve2D::get_bake_interval() const {
1046 return bake_interval;
1047}
1048
1049Vector2 Curve2D::get_closest_point(const Vector2 &p_to_point) const {
1050 // Brute force method.
1051
1052 if (baked_cache_dirty) {
1053 _bake();
1054 }
1055
1056 // Validate: Curve may not have baked points.
1057 int pc = baked_point_cache.size();
1058 ERR_FAIL_COND_V_MSG(pc == 0, Vector2(), "No points in Curve2D.");
1059
1060 if (pc == 1) {
1061 return baked_point_cache.get(0);
1062 }
1063
1064 const Vector2 *r = baked_point_cache.ptr();
1065
1066 Vector2 nearest;
1067 real_t nearest_dist = -1.0f;
1068
1069 for (int i = 0; i < pc - 1; i++) {
1070 const real_t interval = baked_dist_cache[i + 1] - baked_dist_cache[i];
1071 Vector2 origin = r[i];
1072 Vector2 direction = (r[i + 1] - origin) / interval;
1073
1074 real_t d = CLAMP((p_to_point - origin).dot(direction), 0.0f, interval);
1075 Vector2 proj = origin + direction * d;
1076
1077 real_t dist = proj.distance_squared_to(p_to_point);
1078
1079 if (nearest_dist < 0.0f || dist < nearest_dist) {
1080 nearest = proj;
1081 nearest_dist = dist;
1082 }
1083 }
1084
1085 return nearest;
1086}
1087
1088real_t Curve2D::get_closest_offset(const Vector2 &p_to_point) const {
1089 // Brute force method.
1090
1091 if (baked_cache_dirty) {
1092 _bake();
1093 }
1094
1095 // Validate: Curve may not have baked points.
1096 int pc = baked_point_cache.size();
1097 ERR_FAIL_COND_V_MSG(pc == 0, 0.0f, "No points in Curve2D.");
1098
1099 if (pc == 1) {
1100 return 0.0f;
1101 }
1102
1103 const Vector2 *r = baked_point_cache.ptr();
1104
1105 real_t nearest = 0.0f;
1106 real_t nearest_dist = -1.0f;
1107 real_t offset = 0.0f;
1108
1109 for (int i = 0; i < pc - 1; i++) {
1110 offset = baked_dist_cache[i];
1111
1112 const real_t interval = baked_dist_cache[i + 1] - baked_dist_cache[i];
1113 Vector2 origin = r[i];
1114 Vector2 direction = (r[i + 1] - origin) / interval;
1115
1116 real_t d = CLAMP((p_to_point - origin).dot(direction), 0.0f, interval);
1117 Vector2 proj = origin + direction * d;
1118
1119 real_t dist = proj.distance_squared_to(p_to_point);
1120
1121 if (nearest_dist < 0.0f || dist < nearest_dist) {
1122 nearest = offset + d;
1123 nearest_dist = dist;
1124 }
1125 }
1126
1127 return nearest;
1128}
1129
1130Dictionary Curve2D::_get_data() const {
1131 Dictionary dc;
1132
1133 PackedVector2Array d;
1134 d.resize(points.size() * 3);
1135 Vector2 *w = d.ptrw();
1136
1137 for (int i = 0; i < points.size(); i++) {
1138 w[i * 3 + 0] = points[i].in;
1139 w[i * 3 + 1] = points[i].out;
1140 w[i * 3 + 2] = points[i].position;
1141 }
1142
1143 dc["points"] = d;
1144
1145 return dc;
1146}
1147
1148void Curve2D::_set_data(const Dictionary &p_data) {
1149 ERR_FAIL_COND(!p_data.has("points"));
1150
1151 PackedVector2Array rp = p_data["points"];
1152 int pc = rp.size();
1153 ERR_FAIL_COND(pc % 3 != 0);
1154 int old_size = points.size();
1155 int new_size = pc / 3;
1156 if (old_size != new_size) {
1157 points.resize(new_size);
1158 }
1159 const Vector2 *r = rp.ptr();
1160
1161 for (int i = 0; i < points.size(); i++) {
1162 points.write[i].in = r[i * 3 + 0];
1163 points.write[i].out = r[i * 3 + 1];
1164 points.write[i].position = r[i * 3 + 2];
1165 }
1166
1167 mark_dirty();
1168 if (old_size != new_size) {
1169 notify_property_list_changed();
1170 }
1171}
1172
1173PackedVector2Array Curve2D::tessellate(int p_max_stages, real_t p_tolerance) const {
1174 PackedVector2Array tess;
1175
1176 if (points.size() == 0) {
1177 return tess;
1178 }
1179
1180 // The current implementation requires a sorted map.
1181 Vector<RBMap<real_t, Vector2>> midpoints;
1182
1183 midpoints.resize(points.size() - 1);
1184
1185 int pc = 1;
1186 for (int i = 0; i < points.size() - 1; i++) {
1187 _bake_segment2d(midpoints.write[i], 0, 1, points[i].position, points[i].out, points[i + 1].position, points[i + 1].in, 0, p_max_stages, p_tolerance);
1188 pc++;
1189 pc += midpoints[i].size();
1190 }
1191
1192 tess.resize(pc);
1193 Vector2 *bpw = tess.ptrw();
1194 bpw[0] = points[0].position;
1195 int pidx = 0;
1196
1197 for (int i = 0; i < points.size() - 1; i++) {
1198 for (const KeyValue<real_t, Vector2> &E : midpoints[i]) {
1199 pidx++;
1200 bpw[pidx] = E.value;
1201 }
1202
1203 pidx++;
1204 bpw[pidx] = points[i + 1].position;
1205 }
1206
1207 return tess;
1208}
1209
1210Vector<RBMap<real_t, Vector2>> Curve2D::_tessellate_even_length(int p_max_stages, real_t p_length) const {
1211 Vector<RBMap<real_t, Vector2>> midpoints;
1212 ERR_FAIL_COND_V_MSG(points.size() < 2, midpoints, "Curve must have at least 2 control point");
1213
1214 midpoints.resize(points.size() - 1);
1215
1216 for (int i = 0; i < points.size() - 1; i++) {
1217 _bake_segment2d_even_length(midpoints.write[i], 0, 1, points[i].position, points[i].out, points[i + 1].position, points[i + 1].in, 0, p_max_stages, p_length);
1218 }
1219 return midpoints;
1220}
1221
1222PackedVector2Array Curve2D::tessellate_even_length(int p_max_stages, real_t p_length) const {
1223 PackedVector2Array tess;
1224
1225 Vector<RBMap<real_t, Vector2>> midpoints = _tessellate_even_length(p_max_stages, p_length);
1226 if (midpoints.size() == 0) {
1227 return tess;
1228 }
1229
1230 int pc = 1;
1231 for (int i = 0; i < points.size() - 1; i++) {
1232 pc++;
1233 pc += midpoints[i].size();
1234 }
1235
1236 tess.resize(pc);
1237 Vector2 *bpw = tess.ptrw();
1238 bpw[0] = points[0].position;
1239 int pidx = 0;
1240
1241 for (int i = 0; i < points.size() - 1; i++) {
1242 for (const KeyValue<real_t, Vector2> &E : midpoints[i]) {
1243 pidx++;
1244 bpw[pidx] = E.value;
1245 }
1246
1247 pidx++;
1248 bpw[pidx] = points[i + 1].position;
1249 }
1250
1251 return tess;
1252}
1253
1254bool Curve2D::_set(const StringName &p_name, const Variant &p_value) {
1255 Vector<String> components = String(p_name).split("/", true, 2);
1256 if (components.size() >= 2 && components[0].begins_with("point_") && components[0].trim_prefix("point_").is_valid_int()) {
1257 int point_index = components[0].trim_prefix("point_").to_int();
1258 String property = components[1];
1259 if (property == "position") {
1260 set_point_position(point_index, p_value);
1261 return true;
1262 } else if (property == "in") {
1263 set_point_in(point_index, p_value);
1264 return true;
1265 } else if (property == "out") {
1266 set_point_out(point_index, p_value);
1267 return true;
1268 }
1269 }
1270 return false;
1271}
1272
1273bool Curve2D::_get(const StringName &p_name, Variant &r_ret) const {
1274 Vector<String> components = String(p_name).split("/", true, 2);
1275 if (components.size() >= 2 && components[0].begins_with("point_") && components[0].trim_prefix("point_").is_valid_int()) {
1276 int point_index = components[0].trim_prefix("point_").to_int();
1277 String property = components[1];
1278 if (property == "position") {
1279 r_ret = get_point_position(point_index);
1280 return true;
1281 } else if (property == "in") {
1282 r_ret = get_point_in(point_index);
1283 return true;
1284 } else if (property == "out") {
1285 r_ret = get_point_out(point_index);
1286 return true;
1287 }
1288 }
1289 return false;
1290}
1291
1292void Curve2D::_get_property_list(List<PropertyInfo> *p_list) const {
1293 for (int i = 0; i < points.size(); i++) {
1294 PropertyInfo pi = PropertyInfo(Variant::VECTOR2, vformat("point_%d/position", i));
1295 pi.usage &= ~PROPERTY_USAGE_STORAGE;
1296 p_list->push_back(pi);
1297
1298 if (i != 0) {
1299 pi = PropertyInfo(Variant::VECTOR2, vformat("point_%d/in", i));
1300 pi.usage &= ~PROPERTY_USAGE_STORAGE;
1301 p_list->push_back(pi);
1302 }
1303
1304 if (i != points.size() - 1) {
1305 pi = PropertyInfo(Variant::VECTOR2, vformat("point_%d/out", i));
1306 pi.usage &= ~PROPERTY_USAGE_STORAGE;
1307 p_list->push_back(pi);
1308 }
1309 }
1310}
1311
1312void Curve2D::_bind_methods() {
1313 ClassDB::bind_method(D_METHOD("get_point_count"), &Curve2D::get_point_count);
1314 ClassDB::bind_method(D_METHOD("set_point_count", "count"), &Curve2D::set_point_count);
1315 ClassDB::bind_method(D_METHOD("add_point", "position", "in", "out", "index"), &Curve2D::add_point, DEFVAL(Vector2()), DEFVAL(Vector2()), DEFVAL(-1));
1316 ClassDB::bind_method(D_METHOD("set_point_position", "idx", "position"), &Curve2D::set_point_position);
1317 ClassDB::bind_method(D_METHOD("get_point_position", "idx"), &Curve2D::get_point_position);
1318 ClassDB::bind_method(D_METHOD("set_point_in", "idx", "position"), &Curve2D::set_point_in);
1319 ClassDB::bind_method(D_METHOD("get_point_in", "idx"), &Curve2D::get_point_in);
1320 ClassDB::bind_method(D_METHOD("set_point_out", "idx", "position"), &Curve2D::set_point_out);
1321 ClassDB::bind_method(D_METHOD("get_point_out", "idx"), &Curve2D::get_point_out);
1322 ClassDB::bind_method(D_METHOD("remove_point", "idx"), &Curve2D::remove_point);
1323 ClassDB::bind_method(D_METHOD("clear_points"), &Curve2D::clear_points);
1324 ClassDB::bind_method(D_METHOD("sample", "idx", "t"), &Curve2D::sample);
1325 ClassDB::bind_method(D_METHOD("samplef", "fofs"), &Curve2D::samplef);
1326 //ClassDB::bind_method(D_METHOD("bake","subdivs"),&Curve2D::bake,DEFVAL(10));
1327 ClassDB::bind_method(D_METHOD("set_bake_interval", "distance"), &Curve2D::set_bake_interval);
1328 ClassDB::bind_method(D_METHOD("get_bake_interval"), &Curve2D::get_bake_interval);
1329
1330 ClassDB::bind_method(D_METHOD("get_baked_length"), &Curve2D::get_baked_length);
1331 ClassDB::bind_method(D_METHOD("sample_baked", "offset", "cubic"), &Curve2D::sample_baked, DEFVAL(0.0), DEFVAL(false));
1332 ClassDB::bind_method(D_METHOD("sample_baked_with_rotation", "offset", "cubic"), &Curve2D::sample_baked_with_rotation, DEFVAL(0.0), DEFVAL(false));
1333 ClassDB::bind_method(D_METHOD("get_baked_points"), &Curve2D::get_baked_points);
1334 ClassDB::bind_method(D_METHOD("get_closest_point", "to_point"), &Curve2D::get_closest_point);
1335 ClassDB::bind_method(D_METHOD("get_closest_offset", "to_point"), &Curve2D::get_closest_offset);
1336 ClassDB::bind_method(D_METHOD("tessellate", "max_stages", "tolerance_degrees"), &Curve2D::tessellate, DEFVAL(5), DEFVAL(4));
1337 ClassDB::bind_method(D_METHOD("tessellate_even_length", "max_stages", "tolerance_length"), &Curve2D::tessellate_even_length, DEFVAL(5), DEFVAL(20.0));
1338
1339 ClassDB::bind_method(D_METHOD("_get_data"), &Curve2D::_get_data);
1340 ClassDB::bind_method(D_METHOD("_set_data", "data"), &Curve2D::_set_data);
1341
1342 ADD_PROPERTY(PropertyInfo(Variant::FLOAT, "bake_interval", PROPERTY_HINT_RANGE, "0.01,512,0.01"), "set_bake_interval", "get_bake_interval");
1343 ADD_PROPERTY(PropertyInfo(Variant::INT, "_data", PROPERTY_HINT_NONE, "", PROPERTY_USAGE_NO_EDITOR | PROPERTY_USAGE_INTERNAL), "_set_data", "_get_data");
1344 ADD_ARRAY_COUNT("Points", "point_count", "set_point_count", "get_point_count", "point_");
1345}
1346
1347Curve2D::Curve2D() {}
1348
1349/***********************************************************************************/
1350/***********************************************************************************/
1351/***********************************************************************************/
1352/***********************************************************************************/
1353/***********************************************************************************/
1354/***********************************************************************************/
1355
1356int Curve3D::get_point_count() const {
1357 return points.size();
1358}
1359
1360void Curve3D::set_point_count(int p_count) {
1361 ERR_FAIL_COND(p_count < 0);
1362 int old_size = points.size();
1363 if (old_size == p_count) {
1364 return;
1365 }
1366
1367 if (old_size > p_count) {
1368 points.resize(p_count);
1369 mark_dirty();
1370 } else {
1371 for (int i = p_count - old_size; i > 0; i--) {
1372 _add_point(Vector3());
1373 }
1374 }
1375 notify_property_list_changed();
1376}
1377
1378void Curve3D::_add_point(const Vector3 &p_position, const Vector3 &p_in, const Vector3 &p_out, int p_atpos) {
1379 Point n;
1380 n.position = p_position;
1381 n.in = p_in;
1382 n.out = p_out;
1383 if (p_atpos >= 0 && p_atpos < points.size()) {
1384 points.insert(p_atpos, n);
1385 } else {
1386 points.push_back(n);
1387 }
1388
1389 mark_dirty();
1390}
1391
1392void Curve3D::add_point(const Vector3 &p_position, const Vector3 &p_in, const Vector3 &p_out, int p_atpos) {
1393 _add_point(p_position, p_in, p_out, p_atpos);
1394 notify_property_list_changed();
1395}
1396
1397void Curve3D::set_point_position(int p_index, const Vector3 &p_position) {
1398 ERR_FAIL_INDEX(p_index, points.size());
1399
1400 points.write[p_index].position = p_position;
1401 mark_dirty();
1402}
1403
1404Vector3 Curve3D::get_point_position(int p_index) const {
1405 ERR_FAIL_INDEX_V(p_index, points.size(), Vector3());
1406 return points[p_index].position;
1407}
1408
1409void Curve3D::set_point_tilt(int p_index, real_t p_tilt) {
1410 ERR_FAIL_INDEX(p_index, points.size());
1411
1412 points.write[p_index].tilt = p_tilt;
1413 mark_dirty();
1414}
1415
1416real_t Curve3D::get_point_tilt(int p_index) const {
1417 ERR_FAIL_INDEX_V(p_index, points.size(), 0);
1418 return points[p_index].tilt;
1419}
1420
1421void Curve3D::set_point_in(int p_index, const Vector3 &p_in) {
1422 ERR_FAIL_INDEX(p_index, points.size());
1423
1424 points.write[p_index].in = p_in;
1425 mark_dirty();
1426}
1427
1428Vector3 Curve3D::get_point_in(int p_index) const {
1429 ERR_FAIL_INDEX_V(p_index, points.size(), Vector3());
1430 return points[p_index].in;
1431}
1432
1433void Curve3D::set_point_out(int p_index, const Vector3 &p_out) {
1434 ERR_FAIL_INDEX(p_index, points.size());
1435
1436 points.write[p_index].out = p_out;
1437 mark_dirty();
1438}
1439
1440Vector3 Curve3D::get_point_out(int p_index) const {
1441 ERR_FAIL_INDEX_V(p_index, points.size(), Vector3());
1442 return points[p_index].out;
1443}
1444
1445void Curve3D::_remove_point(int p_index) {
1446 ERR_FAIL_INDEX(p_index, points.size());
1447 points.remove_at(p_index);
1448 mark_dirty();
1449}
1450
1451void Curve3D::remove_point(int p_index) {
1452 _remove_point(p_index);
1453 notify_property_list_changed();
1454}
1455
1456void Curve3D::clear_points() {
1457 if (!points.is_empty()) {
1458 points.clear();
1459 mark_dirty();
1460 notify_property_list_changed();
1461 }
1462}
1463
1464Vector3 Curve3D::sample(int p_index, real_t p_offset) const {
1465 int pc = points.size();
1466 ERR_FAIL_COND_V(pc == 0, Vector3());
1467
1468 if (p_index >= pc - 1) {
1469 return points[pc - 1].position;
1470 } else if (p_index < 0) {
1471 return points[0].position;
1472 }
1473
1474 Vector3 p0 = points[p_index].position;
1475 Vector3 p1 = p0 + points[p_index].out;
1476 Vector3 p3 = points[p_index + 1].position;
1477 Vector3 p2 = p3 + points[p_index + 1].in;
1478
1479 return p0.bezier_interpolate(p1, p2, p3, p_offset);
1480}
1481
1482Vector3 Curve3D::samplef(real_t p_findex) const {
1483 if (p_findex < 0) {
1484 p_findex = 0;
1485 } else if (p_findex >= points.size()) {
1486 p_findex = points.size();
1487 }
1488
1489 return sample((int)p_findex, Math::fmod(p_findex, (real_t)1.0));
1490}
1491
1492void Curve3D::mark_dirty() {
1493 baked_cache_dirty = true;
1494 emit_changed();
1495}
1496
1497void Curve3D::_bake_segment3d(RBMap<real_t, Vector3> &r_bake, real_t p_begin, real_t p_end, const Vector3 &p_a, const Vector3 &p_out, const Vector3 &p_b, const Vector3 &p_in, int p_depth, int p_max_depth, real_t p_tol) const {
1498 real_t mp = p_begin + (p_end - p_begin) * 0.5;
1499 Vector3 beg = p_a.bezier_interpolate(p_a + p_out, p_b + p_in, p_b, p_begin);
1500 Vector3 mid = p_a.bezier_interpolate(p_a + p_out, p_b + p_in, p_b, mp);
1501 Vector3 end = p_a.bezier_interpolate(p_a + p_out, p_b + p_in, p_b, p_end);
1502
1503 Vector3 na = (mid - beg).normalized();
1504 Vector3 nb = (end - mid).normalized();
1505 real_t dp = na.dot(nb);
1506
1507 if (dp < Math::cos(Math::deg_to_rad(p_tol))) {
1508 r_bake[mp] = mid;
1509 }
1510 if (p_depth < p_max_depth) {
1511 _bake_segment3d(r_bake, p_begin, mp, p_a, p_out, p_b, p_in, p_depth + 1, p_max_depth, p_tol);
1512 _bake_segment3d(r_bake, mp, p_end, p_a, p_out, p_b, p_in, p_depth + 1, p_max_depth, p_tol);
1513 }
1514}
1515
1516void Curve3D::_bake_segment3d_even_length(RBMap<real_t, Vector3> &r_bake, real_t p_begin, real_t p_end, const Vector3 &p_a, const Vector3 &p_out, const Vector3 &p_b, const Vector3 &p_in, int p_depth, int p_max_depth, real_t p_length) const {
1517 Vector3 beg = p_a.bezier_interpolate(p_a + p_out, p_b + p_in, p_b, p_begin);
1518 Vector3 end = p_a.bezier_interpolate(p_a + p_out, p_b + p_in, p_b, p_end);
1519
1520 real_t length = beg.distance_to(end);
1521
1522 if (length > p_length && p_depth < p_max_depth) {
1523 real_t mp = (p_begin + p_end) * 0.5;
1524 Vector3 mid = p_a.bezier_interpolate(p_a + p_out, p_b + p_in, p_b, mp);
1525 r_bake[mp] = mid;
1526
1527 _bake_segment3d_even_length(r_bake, p_begin, mp, p_a, p_out, p_b, p_in, p_depth + 1, p_max_depth, p_length);
1528 _bake_segment3d_even_length(r_bake, mp, p_end, p_a, p_out, p_b, p_in, p_depth + 1, p_max_depth, p_length);
1529 }
1530}
1531
1532Vector3 Curve3D::_calculate_tangent(const Vector3 &p_begin, const Vector3 &p_control_1, const Vector3 &p_control_2, const Vector3 &p_end, const real_t p_t) {
1533 // Handle corner cases.
1534 if (Math::is_zero_approx(p_t - 0.0f) && p_control_1.is_equal_approx(p_begin)) {
1535 return (p_end - p_begin).normalized();
1536 }
1537
1538 if (Math::is_zero_approx(p_t - 1.0f) && p_control_2.is_equal_approx(p_end)) {
1539 return (p_end - p_begin).normalized();
1540 }
1541
1542 return p_begin.bezier_derivative(p_control_1, p_control_2, p_end, p_t).normalized();
1543}
1544
1545void Curve3D::_bake() const {
1546 if (!baked_cache_dirty) {
1547 return;
1548 }
1549
1550 baked_max_ofs = 0;
1551 baked_cache_dirty = false;
1552
1553 if (points.size() == 0) {
1554#ifdef TOOLS_ENABLED
1555 points_in_cache.clear();
1556#endif
1557 baked_point_cache.clear();
1558 baked_tilt_cache.clear();
1559 baked_dist_cache.clear();
1560
1561 baked_forward_vector_cache.clear();
1562 baked_up_vector_cache.clear();
1563 return;
1564 }
1565
1566 if (points.size() == 1) {
1567#ifdef TOOLS_ENABLED
1568 points_in_cache.resize(1);
1569 points_in_cache.set(0, 0);
1570#endif
1571
1572 baked_point_cache.resize(1);
1573 baked_point_cache.set(0, points[0].position);
1574 baked_tilt_cache.resize(1);
1575 baked_tilt_cache.set(0, points[0].tilt);
1576 baked_dist_cache.resize(1);
1577 baked_dist_cache.set(0, 0.0);
1578 baked_forward_vector_cache.resize(1);
1579 baked_forward_vector_cache.set(0, Vector3(0.0, 0.0, 1.0));
1580
1581 if (up_vector_enabled) {
1582 baked_up_vector_cache.resize(1);
1583 baked_up_vector_cache.set(0, Vector3(0.0, 1.0, 0.0));
1584 } else {
1585 baked_up_vector_cache.clear();
1586 }
1587
1588 return;
1589 }
1590
1591 // Step 1: Tessellate curve to (almost) even length segments
1592 {
1593 Vector<RBMap<real_t, Vector3>> midpoints = _tessellate_even_length(10, bake_interval);
1594
1595#ifdef TOOLS_ENABLED
1596 points_in_cache.resize(points.size());
1597 points_in_cache.set(0, 0);
1598#endif
1599
1600 int pc = 1;
1601 for (int i = 0; i < points.size() - 1; i++) {
1602 pc++;
1603 pc += midpoints[i].size();
1604#ifdef TOOLS_ENABLED
1605 points_in_cache.set(i + 1, pc - 1);
1606#endif
1607 }
1608
1609 baked_point_cache.resize(pc);
1610 baked_tilt_cache.resize(pc);
1611 baked_dist_cache.resize(pc);
1612 baked_forward_vector_cache.resize(pc);
1613
1614 Vector3 *bpw = baked_point_cache.ptrw();
1615 real_t *btw = baked_tilt_cache.ptrw();
1616 Vector3 *bfw = baked_forward_vector_cache.ptrw();
1617
1618 // Collect positions and sample tilts and tangents for each baked points.
1619 bpw[0] = points[0].position;
1620 bfw[0] = _calculate_tangent(points[0].position, points[0].position + points[0].out, points[1].position + points[1].in, points[1].position, 0.0);
1621 btw[0] = points[0].tilt;
1622 int pidx = 0;
1623
1624 for (int i = 0; i < points.size() - 1; i++) {
1625 for (const KeyValue<real_t, Vector3> &E : midpoints[i]) {
1626 pidx++;
1627 bpw[pidx] = E.value;
1628 bfw[pidx] = _calculate_tangent(points[i].position, points[i].position + points[i].out, points[i + 1].position + points[i + 1].in, points[i + 1].position, E.key);
1629 btw[pidx] = Math::lerp(points[i].tilt, points[i + 1].tilt, E.key);
1630 }
1631
1632 pidx++;
1633 bpw[pidx] = points[i + 1].position;
1634 bfw[pidx] = _calculate_tangent(points[i].position, points[i].position + points[i].out, points[i + 1].position + points[i + 1].in, points[i + 1].position, 1.0);
1635 btw[pidx] = points[i + 1].tilt;
1636 }
1637
1638 // Recalculate the baked distances.
1639 real_t *bdw = baked_dist_cache.ptrw();
1640 bdw[0] = 0.0;
1641 for (int i = 0; i < pc - 1; i++) {
1642 bdw[i + 1] = bdw[i] + bpw[i].distance_to(bpw[i + 1]);
1643 }
1644 baked_max_ofs = bdw[pc - 1];
1645 }
1646
1647 if (!up_vector_enabled) {
1648 baked_up_vector_cache.resize(0);
1649 return;
1650 }
1651
1652 // Step 2: Calculate the up vectors and the whole local reference frame
1653 //
1654 // See Dougan, Carl. "The parallel transport frame." Game Programming Gems 2 (2001): 215-219.
1655 // for an example discussing about why not the Frenet frame.
1656 {
1657 int point_count = baked_point_cache.size();
1658
1659 baked_up_vector_cache.resize(point_count);
1660 Vector3 *up_write = baked_up_vector_cache.ptrw();
1661
1662 const Vector3 *forward_ptr = baked_forward_vector_cache.ptr();
1663 const Vector3 *points_ptr = baked_point_cache.ptr();
1664
1665 Basis frame; // X-right, Y-up, Z-forward.
1666 Basis frame_prev;
1667
1668 // Set the initial frame based on Y-up rule.
1669 {
1670 Vector3 forward = forward_ptr[0];
1671
1672 if (abs(forward.dot(Vector3(0, 1, 0))) > 1.0 - UNIT_EPSILON) {
1673 frame_prev = Basis::looking_at(forward, Vector3(1, 0, 0));
1674 } else {
1675 frame_prev = Basis::looking_at(forward, Vector3(0, 1, 0));
1676 }
1677
1678 up_write[0] = frame_prev.get_column(1);
1679 }
1680
1681 // Calculate the Parallel Transport Frame.
1682 for (int idx = 1; idx < point_count; idx++) {
1683 Vector3 forward = forward_ptr[idx];
1684
1685 Basis rotate;
1686 rotate.rotate_to_align(frame_prev.get_column(2), forward);
1687 frame = rotate * frame_prev;
1688 frame.orthonormalize(); // guard against float error accumulation
1689
1690 up_write[idx] = frame.get_column(1);
1691 frame_prev = frame;
1692 }
1693
1694 bool is_loop = true;
1695 // Loop smoothing only applies when the curve is a loop, which means two ends meet, and share forward directions.
1696 {
1697 if (!points_ptr[0].is_equal_approx(points_ptr[point_count - 1])) {
1698 is_loop = false;
1699 }
1700
1701 real_t dot = forward_ptr[0].dot(forward_ptr[point_count - 1]);
1702 if (dot < 1.0 - UNIT_EPSILON) { // Alignment should not be too tight, or it doesn't work for coarse bake interval.
1703 is_loop = false;
1704 }
1705 }
1706
1707 // Twist up vectors, so that they align at two ends of the curve.
1708 if (is_loop) {
1709 const Vector3 up_start = up_write[0];
1710 const Vector3 up_end = up_write[point_count - 1];
1711
1712 real_t sign = SIGN(up_end.cross(up_start).dot(forward_ptr[0]));
1713 real_t full_angle = Quaternion(up_end, up_start).get_angle();
1714
1715 if (abs(full_angle) < CMP_EPSILON) {
1716 return;
1717 } else {
1718 const real_t *dists = baked_dist_cache.ptr();
1719 for (int idx = 1; idx < point_count; idx++) {
1720 const real_t frac = dists[idx] / baked_max_ofs;
1721 const real_t angle = Math::lerp((real_t)0.0, full_angle, frac);
1722 Basis twist(forward_ptr[idx] * sign, angle);
1723
1724 up_write[idx] = twist.xform(up_write[idx]);
1725 }
1726 }
1727 }
1728 }
1729}
1730
1731real_t Curve3D::get_baked_length() const {
1732 if (baked_cache_dirty) {
1733 _bake();
1734 }
1735
1736 return baked_max_ofs;
1737}
1738
1739Curve3D::Interval Curve3D::_find_interval(real_t p_offset) const {
1740 Interval interval = {
1741 -1,
1742 0.0
1743 };
1744 ERR_FAIL_COND_V_MSG(baked_cache_dirty, interval, "Backed cache is dirty");
1745
1746 int pc = baked_point_cache.size();
1747 ERR_FAIL_COND_V_MSG(pc < 2, interval, "Less than two points in cache");
1748
1749 int start = 0;
1750 int end = pc;
1751 int idx = (end + start) / 2;
1752 // Binary search to find baked points.
1753 while (start < idx) {
1754 real_t offset = baked_dist_cache[idx];
1755 if (p_offset <= offset) {
1756 end = idx;
1757 } else {
1758 start = idx;
1759 }
1760 idx = (end + start) / 2;
1761 }
1762
1763 real_t offset_begin = baked_dist_cache[idx];
1764 real_t offset_end = baked_dist_cache[idx + 1];
1765
1766 real_t idx_interval = offset_end - offset_begin;
1767 ERR_FAIL_COND_V_MSG(p_offset < offset_begin || p_offset > offset_end, interval, "Offset out of range.");
1768
1769 interval.idx = idx;
1770 if (idx_interval < FLT_EPSILON) {
1771 interval.frac = 0.5; // For a very short interval, 0.5 is a reasonable choice.
1772 ERR_FAIL_V_MSG(interval, "Zero length interval.");
1773 }
1774
1775 interval.frac = (p_offset - offset_begin) / idx_interval;
1776 return interval;
1777}
1778
1779Vector3 Curve3D::_sample_baked(Interval p_interval, bool p_cubic) const {
1780 // Assuming p_interval is valid.
1781 ERR_FAIL_INDEX_V_MSG(p_interval.idx, baked_point_cache.size(), Vector3(), "Invalid interval");
1782
1783 int idx = p_interval.idx;
1784 real_t frac = p_interval.frac;
1785
1786 const Vector3 *r = baked_point_cache.ptr();
1787 int pc = baked_point_cache.size();
1788
1789 if (p_cubic) {
1790 Vector3 pre = idx > 0 ? r[idx - 1] : r[idx];
1791 Vector3 post = (idx < (pc - 2)) ? r[idx + 2] : r[idx + 1];
1792 return r[idx].cubic_interpolate(r[idx + 1], pre, post, frac);
1793 } else {
1794 return r[idx].lerp(r[idx + 1], frac);
1795 }
1796}
1797
1798real_t Curve3D::_sample_baked_tilt(Interval p_interval) const {
1799 // Assuming that p_interval is valid.
1800 ERR_FAIL_INDEX_V_MSG(p_interval.idx, baked_tilt_cache.size(), 0.0, "Invalid interval");
1801
1802 int idx = p_interval.idx;
1803 real_t frac = p_interval.frac;
1804
1805 const real_t *r = baked_tilt_cache.ptr();
1806
1807 return Math::lerp(r[idx], r[idx + 1], frac);
1808}
1809
1810// Internal method for getting posture at a baked point. Assuming caller
1811// make all sanity checks.
1812Basis Curve3D::_compose_posture(int p_index) const {
1813 Vector3 forward = baked_forward_vector_cache[p_index];
1814
1815 Vector3 up;
1816 if (up_vector_enabled) {
1817 up = baked_up_vector_cache[p_index];
1818 } else {
1819 up = Vector3(0.0, 1.0, 0.0);
1820 }
1821
1822 const Basis frame = Basis::looking_at(forward, up);
1823 return frame;
1824}
1825
1826Basis Curve3D::_sample_posture(Interval p_interval, bool p_apply_tilt) const {
1827 // Assuming that p_interval is valid.
1828 ERR_FAIL_INDEX_V_MSG(p_interval.idx, baked_point_cache.size(), Basis(), "Invalid interval");
1829 if (up_vector_enabled) {
1830 ERR_FAIL_INDEX_V_MSG(p_interval.idx, baked_up_vector_cache.size(), Basis(), "Invalid interval");
1831 }
1832
1833 int idx = p_interval.idx;
1834 real_t frac = p_interval.frac;
1835
1836 // Get frames at both ends of the interval, then interpolate.
1837 const Basis frame_begin = _compose_posture(idx);
1838 const Basis frame_end = _compose_posture(idx + 1);
1839 const Basis frame = frame_begin.slerp(frame_end, frac).orthonormalized();
1840
1841 if (!p_apply_tilt) {
1842 return frame;
1843 }
1844
1845 // Applying tilt.
1846 const real_t tilt = _sample_baked_tilt(p_interval);
1847 Vector3 tangent = -frame.get_column(2);
1848
1849 const Basis twist(tangent, tilt);
1850 return twist * frame;
1851}
1852
1853#ifdef TOOLS_ENABLED
1854// Get posture at a control point. Needed for Gizmo implementation.
1855Basis Curve3D::get_point_baked_posture(int p_index, bool p_apply_tilt) const {
1856 if (baked_cache_dirty) {
1857 _bake();
1858 }
1859
1860 // Assuming that p_idx is valid.
1861 ERR_FAIL_INDEX_V_MSG(p_index, points_in_cache.size(), Basis(), "Invalid control point index");
1862
1863 int baked_idx = points_in_cache[p_index];
1864 Basis frame = _compose_posture(baked_idx);
1865
1866 if (!p_apply_tilt) {
1867 return frame;
1868 }
1869
1870 // Applying tilt.
1871 const real_t tilt = points[p_index].tilt;
1872 Vector3 tangent = -frame.get_column(2);
1873 const Basis twist(tangent, tilt);
1874
1875 return twist * frame;
1876}
1877#endif
1878
1879Vector3 Curve3D::sample_baked(real_t p_offset, bool p_cubic) const {
1880 if (baked_cache_dirty) {
1881 _bake();
1882 }
1883
1884 // Validate: Curve may not have baked points.
1885 int pc = baked_point_cache.size();
1886 ERR_FAIL_COND_V_MSG(pc == 0, Vector3(), "No points in Curve3D.");
1887
1888 if (pc == 1) {
1889 return baked_point_cache[0];
1890 }
1891
1892 p_offset = CLAMP(p_offset, 0.0, get_baked_length()); // PathFollower implement wrapping logic.
1893
1894 Curve3D::Interval interval = _find_interval(p_offset);
1895 return _sample_baked(interval, p_cubic);
1896}
1897
1898Transform3D Curve3D::sample_baked_with_rotation(real_t p_offset, bool p_cubic, bool p_apply_tilt) const {
1899 if (baked_cache_dirty) {
1900 _bake();
1901 }
1902
1903 // Validate: Curve may not have baked points.
1904 const int point_count = baked_point_cache.size();
1905 ERR_FAIL_COND_V_MSG(point_count == 0, Transform3D(), "No points in Curve3D.");
1906
1907 if (point_count == 1) {
1908 Transform3D t;
1909 t.origin = baked_point_cache.get(0);
1910 ERR_FAIL_V_MSG(t, "Only 1 point in Curve3D.");
1911 }
1912
1913 p_offset = CLAMP(p_offset, 0.0, get_baked_length()); // PathFollower implement wrapping logic.
1914
1915 // 0. Find interval for all sampling steps.
1916 Curve3D::Interval interval = _find_interval(p_offset);
1917
1918 // 1. Sample position.
1919 Vector3 pos = _sample_baked(interval, p_cubic);
1920
1921 // 2. Sample rotation frame.
1922 Basis frame = _sample_posture(interval, p_apply_tilt);
1923
1924 return Transform3D(frame, pos);
1925}
1926
1927real_t Curve3D::sample_baked_tilt(real_t p_offset) const {
1928 if (baked_cache_dirty) {
1929 _bake();
1930 }
1931
1932 // Validate: Curve may not have baked tilts.
1933 int pc = baked_tilt_cache.size();
1934 ERR_FAIL_COND_V_MSG(pc == 0, 0, "No tilts in Curve3D.");
1935
1936 if (pc == 1) {
1937 return baked_tilt_cache.get(0);
1938 }
1939
1940 p_offset = CLAMP(p_offset, 0.0, get_baked_length()); // PathFollower implement wrapping logic
1941
1942 Curve3D::Interval interval = _find_interval(p_offset);
1943 return _sample_baked_tilt(interval);
1944}
1945
1946Vector3 Curve3D::sample_baked_up_vector(real_t p_offset, bool p_apply_tilt) const {
1947 if (baked_cache_dirty) {
1948 _bake();
1949 }
1950
1951 // Validate: Curve may not have baked up vectors.
1952 ERR_FAIL_COND_V_MSG(!up_vector_enabled, Vector3(0, 1, 0), "No up vectors in Curve3D.");
1953
1954 int count = baked_up_vector_cache.size();
1955 if (count == 1) {
1956 return baked_up_vector_cache.get(0);
1957 }
1958
1959 p_offset = CLAMP(p_offset, 0.0, get_baked_length()); // PathFollower implement wrapping logic.
1960
1961 Curve3D::Interval interval = _find_interval(p_offset);
1962 return _sample_posture(interval, p_apply_tilt).get_column(1);
1963}
1964
1965PackedVector3Array Curve3D::get_baked_points() const {
1966 if (baked_cache_dirty) {
1967 _bake();
1968 }
1969
1970 return baked_point_cache;
1971}
1972
1973Vector<real_t> Curve3D::get_baked_tilts() const {
1974 if (baked_cache_dirty) {
1975 _bake();
1976 }
1977
1978 return baked_tilt_cache;
1979}
1980
1981PackedVector3Array Curve3D::get_baked_up_vectors() const {
1982 if (baked_cache_dirty) {
1983 _bake();
1984 }
1985
1986 return baked_up_vector_cache;
1987}
1988
1989Vector3 Curve3D::get_closest_point(const Vector3 &p_to_point) const {
1990 // Brute force method.
1991
1992 if (baked_cache_dirty) {
1993 _bake();
1994 }
1995
1996 // Validate: Curve may not have baked points.
1997 int pc = baked_point_cache.size();
1998 ERR_FAIL_COND_V_MSG(pc == 0, Vector3(), "No points in Curve3D.");
1999
2000 if (pc == 1) {
2001 return baked_point_cache.get(0);
2002 }
2003
2004 const Vector3 *r = baked_point_cache.ptr();
2005
2006 Vector3 nearest;
2007 real_t nearest_dist = -1.0f;
2008
2009 for (int i = 0; i < pc - 1; i++) {
2010 const real_t interval = baked_dist_cache[i + 1] - baked_dist_cache[i];
2011 Vector3 origin = r[i];
2012 Vector3 direction = (r[i + 1] - origin) / interval;
2013
2014 real_t d = CLAMP((p_to_point - origin).dot(direction), 0.0f, interval);
2015 Vector3 proj = origin + direction * d;
2016
2017 real_t dist = proj.distance_squared_to(p_to_point);
2018
2019 if (nearest_dist < 0.0f || dist < nearest_dist) {
2020 nearest = proj;
2021 nearest_dist = dist;
2022 }
2023 }
2024
2025 return nearest;
2026}
2027
2028real_t Curve3D::get_closest_offset(const Vector3 &p_to_point) const {
2029 // Brute force method.
2030
2031 if (baked_cache_dirty) {
2032 _bake();
2033 }
2034
2035 // Validate: Curve may not have baked points.
2036 int pc = baked_point_cache.size();
2037 ERR_FAIL_COND_V_MSG(pc == 0, 0.0f, "No points in Curve3D.");
2038
2039 if (pc == 1) {
2040 return 0.0f;
2041 }
2042
2043 const Vector3 *r = baked_point_cache.ptr();
2044
2045 real_t nearest = 0.0f;
2046 real_t nearest_dist = -1.0f;
2047 real_t offset;
2048
2049 for (int i = 0; i < pc - 1; i++) {
2050 offset = baked_dist_cache[i];
2051
2052 const real_t interval = baked_dist_cache[i + 1] - baked_dist_cache[i];
2053 Vector3 origin = r[i];
2054 Vector3 direction = (r[i + 1] - origin) / interval;
2055
2056 real_t d = CLAMP((p_to_point - origin).dot(direction), 0.0f, interval);
2057 Vector3 proj = origin + direction * d;
2058
2059 real_t dist = proj.distance_squared_to(p_to_point);
2060
2061 if (nearest_dist < 0.0f || dist < nearest_dist) {
2062 nearest = offset + d;
2063 nearest_dist = dist;
2064 }
2065 }
2066
2067 return nearest;
2068}
2069
2070void Curve3D::set_bake_interval(real_t p_tolerance) {
2071 bake_interval = p_tolerance;
2072 mark_dirty();
2073}
2074
2075real_t Curve3D::get_bake_interval() const {
2076 return bake_interval;
2077}
2078
2079void Curve3D::set_up_vector_enabled(bool p_enable) {
2080 up_vector_enabled = p_enable;
2081 mark_dirty();
2082}
2083
2084bool Curve3D::is_up_vector_enabled() const {
2085 return up_vector_enabled;
2086}
2087
2088Dictionary Curve3D::_get_data() const {
2089 Dictionary dc;
2090
2091 PackedVector3Array d;
2092 d.resize(points.size() * 3);
2093 Vector3 *w = d.ptrw();
2094 Vector<real_t> t;
2095 t.resize(points.size());
2096 real_t *wt = t.ptrw();
2097
2098 for (int i = 0; i < points.size(); i++) {
2099 w[i * 3 + 0] = points[i].in;
2100 w[i * 3 + 1] = points[i].out;
2101 w[i * 3 + 2] = points[i].position;
2102 wt[i] = points[i].tilt;
2103 }
2104
2105 dc["points"] = d;
2106 dc["tilts"] = t;
2107
2108 return dc;
2109}
2110
2111void Curve3D::_set_data(const Dictionary &p_data) {
2112 ERR_FAIL_COND(!p_data.has("points"));
2113 ERR_FAIL_COND(!p_data.has("tilts"));
2114
2115 PackedVector3Array rp = p_data["points"];
2116 int pc = rp.size();
2117 ERR_FAIL_COND(pc % 3 != 0);
2118 int old_size = points.size();
2119 int new_size = pc / 3;
2120 if (old_size != new_size) {
2121 points.resize(new_size);
2122 }
2123 const Vector3 *r = rp.ptr();
2124 Vector<real_t> rtl = p_data["tilts"];
2125 const real_t *rt = rtl.ptr();
2126
2127 for (int i = 0; i < points.size(); i++) {
2128 points.write[i].in = r[i * 3 + 0];
2129 points.write[i].out = r[i * 3 + 1];
2130 points.write[i].position = r[i * 3 + 2];
2131 points.write[i].tilt = rt[i];
2132 }
2133
2134 mark_dirty();
2135 if (old_size != new_size) {
2136 notify_property_list_changed();
2137 }
2138}
2139
2140PackedVector3Array Curve3D::tessellate(int p_max_stages, real_t p_tolerance) const {
2141 PackedVector3Array tess;
2142
2143 if (points.size() == 0) {
2144 return tess;
2145 }
2146 Vector<RBMap<real_t, Vector3>> midpoints;
2147
2148 midpoints.resize(points.size() - 1);
2149
2150 int pc = 1;
2151 for (int i = 0; i < points.size() - 1; i++) {
2152 _bake_segment3d(midpoints.write[i], 0, 1, points[i].position, points[i].out, points[i + 1].position, points[i + 1].in, 0, p_max_stages, p_tolerance);
2153 pc++;
2154 pc += midpoints[i].size();
2155 }
2156
2157 tess.resize(pc);
2158 Vector3 *bpw = tess.ptrw();
2159 bpw[0] = points[0].position;
2160 int pidx = 0;
2161
2162 for (int i = 0; i < points.size() - 1; i++) {
2163 for (const KeyValue<real_t, Vector3> &E : midpoints[i]) {
2164 pidx++;
2165 bpw[pidx] = E.value;
2166 }
2167
2168 pidx++;
2169 bpw[pidx] = points[i + 1].position;
2170 }
2171
2172 return tess;
2173}
2174
2175Vector<RBMap<real_t, Vector3>> Curve3D::_tessellate_even_length(int p_max_stages, real_t p_length) const {
2176 Vector<RBMap<real_t, Vector3>> midpoints;
2177 ERR_FAIL_COND_V_MSG(points.size() < 2, midpoints, "Curve must have at least 2 control point");
2178
2179 midpoints.resize(points.size() - 1);
2180
2181 for (int i = 0; i < points.size() - 1; i++) {
2182 _bake_segment3d_even_length(midpoints.write[i], 0, 1, points[i].position, points[i].out, points[i + 1].position, points[i + 1].in, 0, p_max_stages, p_length);
2183 }
2184 return midpoints;
2185}
2186
2187PackedVector3Array Curve3D::tessellate_even_length(int p_max_stages, real_t p_length) const {
2188 PackedVector3Array tess;
2189
2190 Vector<RBMap<real_t, Vector3>> midpoints = _tessellate_even_length(p_max_stages, p_length);
2191 if (midpoints.size() == 0) {
2192 return tess;
2193 }
2194
2195 int pc = 1;
2196 for (int i = 0; i < points.size() - 1; i++) {
2197 pc++;
2198 pc += midpoints[i].size();
2199 }
2200
2201 tess.resize(pc);
2202 Vector3 *bpw = tess.ptrw();
2203 bpw[0] = points[0].position;
2204 int pidx = 0;
2205
2206 for (int i = 0; i < points.size() - 1; i++) {
2207 for (const KeyValue<real_t, Vector3> &E : midpoints[i]) {
2208 pidx++;
2209 bpw[pidx] = E.value;
2210 }
2211
2212 pidx++;
2213 bpw[pidx] = points[i + 1].position;
2214 }
2215
2216 return tess;
2217}
2218
2219bool Curve3D::_set(const StringName &p_name, const Variant &p_value) {
2220 Vector<String> components = String(p_name).split("/", true, 2);
2221 if (components.size() >= 2 && components[0].begins_with("point_") && components[0].trim_prefix("point_").is_valid_int()) {
2222 int point_index = components[0].trim_prefix("point_").to_int();
2223 String property = components[1];
2224 if (property == "position") {
2225 set_point_position(point_index, p_value);
2226 return true;
2227 } else if (property == "in") {
2228 set_point_in(point_index, p_value);
2229 return true;
2230 } else if (property == "out") {
2231 set_point_out(point_index, p_value);
2232 return true;
2233 } else if (property == "tilt") {
2234 set_point_tilt(point_index, p_value);
2235 return true;
2236 }
2237 }
2238 return false;
2239}
2240
2241bool Curve3D::_get(const StringName &p_name, Variant &r_ret) const {
2242 Vector<String> components = String(p_name).split("/", true, 2);
2243 if (components.size() >= 2 && components[0].begins_with("point_") && components[0].trim_prefix("point_").is_valid_int()) {
2244 int point_index = components[0].trim_prefix("point_").to_int();
2245 String property = components[1];
2246 if (property == "position") {
2247 r_ret = get_point_position(point_index);
2248 return true;
2249 } else if (property == "in") {
2250 r_ret = get_point_in(point_index);
2251 return true;
2252 } else if (property == "out") {
2253 r_ret = get_point_out(point_index);
2254 return true;
2255 } else if (property == "tilt") {
2256 r_ret = get_point_tilt(point_index);
2257 return true;
2258 }
2259 }
2260 return false;
2261}
2262
2263void Curve3D::_get_property_list(List<PropertyInfo> *p_list) const {
2264 for (int i = 0; i < points.size(); i++) {
2265 PropertyInfo pi = PropertyInfo(Variant::VECTOR3, vformat("point_%d/position", i));
2266 pi.usage &= ~PROPERTY_USAGE_STORAGE;
2267 p_list->push_back(pi);
2268
2269 if (i != 0) {
2270 pi = PropertyInfo(Variant::VECTOR3, vformat("point_%d/in", i));
2271 pi.usage &= ~PROPERTY_USAGE_STORAGE;
2272 p_list->push_back(pi);
2273 }
2274
2275 if (i != points.size() - 1) {
2276 pi = PropertyInfo(Variant::VECTOR3, vformat("point_%d/out", i));
2277 pi.usage &= ~PROPERTY_USAGE_STORAGE;
2278 p_list->push_back(pi);
2279 }
2280
2281 pi = PropertyInfo(Variant::FLOAT, vformat("point_%d/tilt", i));
2282 pi.usage &= ~PROPERTY_USAGE_STORAGE;
2283 p_list->push_back(pi);
2284 }
2285}
2286
2287void Curve3D::_bind_methods() {
2288 ClassDB::bind_method(D_METHOD("get_point_count"), &Curve3D::get_point_count);
2289 ClassDB::bind_method(D_METHOD("set_point_count", "count"), &Curve3D::set_point_count);
2290 ClassDB::bind_method(D_METHOD("add_point", "position", "in", "out", "index"), &Curve3D::add_point, DEFVAL(Vector3()), DEFVAL(Vector3()), DEFVAL(-1));
2291 ClassDB::bind_method(D_METHOD("set_point_position", "idx", "position"), &Curve3D::set_point_position);
2292 ClassDB::bind_method(D_METHOD("get_point_position", "idx"), &Curve3D::get_point_position);
2293 ClassDB::bind_method(D_METHOD("set_point_tilt", "idx", "tilt"), &Curve3D::set_point_tilt);
2294 ClassDB::bind_method(D_METHOD("get_point_tilt", "idx"), &Curve3D::get_point_tilt);
2295 ClassDB::bind_method(D_METHOD("set_point_in", "idx", "position"), &Curve3D::set_point_in);
2296 ClassDB::bind_method(D_METHOD("get_point_in", "idx"), &Curve3D::get_point_in);
2297 ClassDB::bind_method(D_METHOD("set_point_out", "idx", "position"), &Curve3D::set_point_out);
2298 ClassDB::bind_method(D_METHOD("get_point_out", "idx"), &Curve3D::get_point_out);
2299 ClassDB::bind_method(D_METHOD("remove_point", "idx"), &Curve3D::remove_point);
2300 ClassDB::bind_method(D_METHOD("clear_points"), &Curve3D::clear_points);
2301 ClassDB::bind_method(D_METHOD("sample", "idx", "t"), &Curve3D::sample);
2302 ClassDB::bind_method(D_METHOD("samplef", "fofs"), &Curve3D::samplef);
2303 //ClassDB::bind_method(D_METHOD("bake","subdivs"),&Curve3D::bake,DEFVAL(10));
2304 ClassDB::bind_method(D_METHOD("set_bake_interval", "distance"), &Curve3D::set_bake_interval);
2305 ClassDB::bind_method(D_METHOD("get_bake_interval"), &Curve3D::get_bake_interval);
2306 ClassDB::bind_method(D_METHOD("set_up_vector_enabled", "enable"), &Curve3D::set_up_vector_enabled);
2307 ClassDB::bind_method(D_METHOD("is_up_vector_enabled"), &Curve3D::is_up_vector_enabled);
2308
2309 ClassDB::bind_method(D_METHOD("get_baked_length"), &Curve3D::get_baked_length);
2310 ClassDB::bind_method(D_METHOD("sample_baked", "offset", "cubic"), &Curve3D::sample_baked, DEFVAL(0.0), DEFVAL(false));
2311 ClassDB::bind_method(D_METHOD("sample_baked_with_rotation", "offset", "cubic", "apply_tilt"), &Curve3D::sample_baked_with_rotation, DEFVAL(0.0), DEFVAL(false), DEFVAL(false));
2312 ClassDB::bind_method(D_METHOD("sample_baked_up_vector", "offset", "apply_tilt"), &Curve3D::sample_baked_up_vector, DEFVAL(false));
2313 ClassDB::bind_method(D_METHOD("get_baked_points"), &Curve3D::get_baked_points);
2314 ClassDB::bind_method(D_METHOD("get_baked_tilts"), &Curve3D::get_baked_tilts);
2315 ClassDB::bind_method(D_METHOD("get_baked_up_vectors"), &Curve3D::get_baked_up_vectors);
2316 ClassDB::bind_method(D_METHOD("get_closest_point", "to_point"), &Curve3D::get_closest_point);
2317 ClassDB::bind_method(D_METHOD("get_closest_offset", "to_point"), &Curve3D::get_closest_offset);
2318 ClassDB::bind_method(D_METHOD("tessellate", "max_stages", "tolerance_degrees"), &Curve3D::tessellate, DEFVAL(5), DEFVAL(4));
2319 ClassDB::bind_method(D_METHOD("tessellate_even_length", "max_stages", "tolerance_length"), &Curve3D::tessellate_even_length, DEFVAL(5), DEFVAL(0.2));
2320
2321 ClassDB::bind_method(D_METHOD("_get_data"), &Curve3D::_get_data);
2322 ClassDB::bind_method(D_METHOD("_set_data", "data"), &Curve3D::_set_data);
2323
2324 ADD_PROPERTY(PropertyInfo(Variant::FLOAT, "bake_interval", PROPERTY_HINT_RANGE, "0.01,512,0.01"), "set_bake_interval", "get_bake_interval");
2325 ADD_PROPERTY(PropertyInfo(Variant::INT, "_data", PROPERTY_HINT_NONE, "", PROPERTY_USAGE_NO_EDITOR | PROPERTY_USAGE_INTERNAL), "_set_data", "_get_data");
2326 ADD_ARRAY_COUNT("Points", "point_count", "set_point_count", "get_point_count", "point_");
2327
2328 ADD_GROUP("Up Vector", "up_vector_");
2329 ADD_PROPERTY(PropertyInfo(Variant::BOOL, "up_vector_enabled"), "set_up_vector_enabled", "is_up_vector_enabled");
2330}
2331
2332Curve3D::Curve3D() {}
2333