Refactor baking code for Curve2D

The main change is to caculate tangent directly from bezier curve, without going
through discretized polyline, avoiding pitfalls of discretization. A similar refacor
had been applied to Curve3D.

The test cases for Curve2D is updated, comparing floating point with is_equal_approxmiate()
instead of `==`, in order to avoid float precision problem.

3 files changed, 200 insertions, 126 deletions

diff --git a/scene/2d/path_2d.cpp b/scene/2d/path_2d.cpp
index b5945a4562..b68a8fb031 100644
--- a/scene/2d/path_2d.cpp
+++ b/scene/2d/path_2d.cpp
@@ -177,7 +177,7 @@ void PathFollow2D::_update_transform() {
 	}
 
 	if (rotates) {
-		Transform2D xform = c->sample_baked_with_rotation(progress, cubic, loop, lookahead);
+		Transform2D xform = c->sample_baked_with_rotation(progress, cubic);
 		xform.translate_local(v_offset, h_offset);
 		set_rotation(xform[1].angle());
 		set_position(xform[2]);
diff --git a/scene/resources/curve.cpp b/scene/resources/curve.cpp
index 93c3d4f851..fa7a1f3dbf 100644
--- a/scene/resources/curve.cpp
+++ b/scene/resources/curve.cpp
@@ -341,7 +341,7 @@ real_t Curve::sample_local_nocheck(int p_index, real_t p_local_offset) const {
 	const Point a = _points[p_index];
 	const Point b = _points[p_index + 1];
 
-	/* Cubic bezier
+	/* Cubic bézier
 	 *
 	 *       ac-----bc
 	 *      /         \
@@ -774,6 +774,22 @@ void Curve2D::_bake_segment2d(RBMap<real_t, Vector2> &r_bake, real_t p_begin, re
 	}
 }
 
+void 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 {
+	Vector2 beg = p_a.bezier_interpolate(p_a + p_out, p_b + p_in, p_b, p_begin);
+	Vector2 end = p_a.bezier_interpolate(p_a + p_out, p_b + p_in, p_b, p_end);
+
+	real_t length = beg.distance_to(end);
+
+	if (length > p_length && p_depth < p_max_depth) {
+		real_t mp = (p_begin + p_end) * 0.5;
+		Vector2 mid = p_a.bezier_interpolate(p_a + p_out, p_b + p_in, p_b, mp);
+		r_bake[mp] = mid;
+
+		_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);
+		_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);
+	}
+}
+
 void Curve2D::_bake() const {
 	if (!baked_cache_dirty) {
 		return;
@@ -785,94 +801,62 @@ void Curve2D::_bake() const {
 	if (points.size() == 0) {
 		baked_point_cache.clear();
 		baked_dist_cache.clear();
+		baked_forward_vector_cache.clear();
 		return;
 	}
 
 	if (points.size() == 1) {
 		baked_point_cache.resize(1);
 		baked_point_cache.set(0, points[0].position);
-
 		baked_dist_cache.resize(1);
 		baked_dist_cache.set(0, 0.0);
+		baked_forward_vector_cache.resize(1);
+		baked_forward_vector_cache.set(0, Vector2(0.0, 0.1));
+
 		return;
 	}
 
-	Vector2 position = points[0].position;
-	real_t dist = 0.0;
-
-	List<Vector2> pointlist;
-	List<real_t> distlist;
-
-	// Start always from origin.
-	pointlist.push_back(position);
-	distlist.push_back(0.0);
-
-	for (int i = 0; i < points.size() - 1; i++) {
-		real_t step = 0.1; // at least 10 substeps ought to be enough?
-		real_t p = 0.0;
-
-		while (p < 1.0) {
-			real_t np = p + step;
-			if (np > 1.0) {
-				np = 1.0;
-			}
-
-			Vector2 npp = points[i].position.bezier_interpolate(points[i].position + points[i].out, points[i + 1].position + points[i + 1].in, points[i + 1].position, np);
-			real_t d = position.distance_to(npp);
-
-			if (d > bake_interval) {
-				// OK! between P and NP there _has_ to be Something, let's go searching!
-
-				int iterations = 10; //lots of detail!
-
-				real_t low = p;
-				real_t hi = np;
-				real_t mid = low + (hi - low) * 0.5;
-
-				for (int j = 0; j < iterations; j++) {
-					npp = points[i].position.bezier_interpolate(points[i].position + points[i].out, points[i + 1].position + points[i + 1].in, points[i + 1].position, mid);
-					d = position.distance_to(npp);
-
-					if (bake_interval < d) {
-						hi = mid;
-					} else {
-						low = mid;
-					}
-					mid = low + (hi - low) * 0.5;
-				}
-
-				position = npp;
-				p = mid;
-				dist += d;
+	// Tesselate curve to (almost) even length segments
+	{
+		Vector<RBMap<real_t, Vector2>> midpoints = _tessellate_even_length(10, bake_interval);
 
-				pointlist.push_back(position);
-				distlist.push_back(dist);
-			} else {
-				p = np;
-			}
+		int pc = 1;
+		for (int i = 0; i < points.size() - 1; i++) {
+			pc++;
+			pc += midpoints[i].size();
 		}
 
-		Vector2 npp = points[i + 1].position;
-		real_t d = position.distance_to(npp);
+		baked_point_cache.resize(pc);
+		baked_dist_cache.resize(pc);
+		baked_forward_vector_cache.resize(pc);
 
-		position = npp;
-		dist += d;
+		Vector2 *bpw = baked_point_cache.ptrw();
+		Vector2 *bfw = baked_forward_vector_cache.ptrw();
 
-		pointlist.push_back(position);
-		distlist.push_back(dist);
-	}
-
-	baked_max_ofs = dist;
+		// Collect positions and sample tilts and tangents for each baked points.
+		bpw[0] = points[0].position;
+		bfw[0] = points[0].position.bezier_derivative(points[0].position + points[0].out, points[1].position + points[1].in, points[1].position, 0.0).normalized();
+		int pidx = 0;
 
-	baked_point_cache.resize(pointlist.size());
-	baked_dist_cache.resize(distlist.size());
+		for (int i = 0; i < points.size() - 1; i++) {
+			for (const KeyValue<real_t, Vector2> &E : midpoints[i]) {
+				pidx++;
+				bpw[pidx] = E.value;
+				bfw[pidx] = points[i].position.bezier_derivative(points[i].position + points[i].out, points[i + 1].position + points[i + 1].in, points[i + 1].position, E.key).normalized();
+			}
 
-	Vector2 *w = baked_point_cache.ptrw();
-	real_t *wd = baked_dist_cache.ptrw();
+			pidx++;
+			bpw[pidx] = points[i + 1].position;
+			bfw[pidx] = points[i].position.bezier_derivative(points[i].position + points[i].out, points[i + 1].position + points[i + 1].in, points[i + 1].position, 1.0).normalized();
+		}
 
-	for (int i = 0; i < pointlist.size(); i++) {
-		w[i] = pointlist[i];
-		wd[i] = distlist[i];
+		// Recalculate the baked distances.
+		real_t *bdw = baked_dist_cache.ptrw();
+		bdw[0] = 0.0;
+		for (int i = 0; i < pc - 1; i++) {
+			bdw[i + 1] = bdw[i] + bpw[i].distance_to(bpw[i + 1]);
+		}
+		baked_max_ofs = bdw[pc - 1];
 	}
 }
 
@@ -884,27 +868,15 @@ real_t Curve2D::get_baked_length() const {
 	return baked_max_ofs;
 }
 
-Vector2 Curve2D::sample_baked(real_t p_offset, bool p_cubic) const {
-	if (baked_cache_dirty) {
-		_bake();
-	}
+Curve2D::Interval Curve2D::_find_interval(real_t p_offset) const {
+	Interval interval = {
+		-1,
+		0.0
+	};
+	ERR_FAIL_COND_V_MSG(baked_cache_dirty, interval, "Backed cache is dirty");
 
-	// Validate: Curve may not have baked points.
 	int pc = baked_point_cache.size();
-	ERR_FAIL_COND_V_MSG(pc == 0, Vector2(), "No points in Curve2D.");
-
-	if (pc == 1) {
-		return baked_point_cache.get(0);
-	}
-
-	const Vector2 *r = baked_point_cache.ptr();
-
-	if (p_offset < 0) {
-		return r[0];
-	}
-	if (p_offset >= baked_max_ofs) {
-		return r[pc - 1];
-	}
+	ERR_FAIL_COND_V_MSG(pc < 2, interval, "Less than two points in cache");
 
 	int start = 0;
 	int end = pc;
@@ -924,9 +896,27 @@ Vector2 Curve2D::sample_baked(real_t p_offset, bool p_cubic) const {
 	real_t offset_end = baked_dist_cache[idx + 1];
 
 	real_t idx_interval = offset_end - offset_begin;
-	ERR_FAIL_COND_V_MSG(p_offset < offset_begin || p_offset > offset_end, Vector2(), "Couldn't find baked segment.");
+	ERR_FAIL_COND_V_MSG(p_offset < offset_begin || p_offset > offset_end, interval, "Offset out of range.");
 
-	real_t frac = (p_offset - offset_begin) / idx_interval;
+	interval.idx = idx;
+	if (idx_interval < FLT_EPSILON) {
+		interval.frac = 0.5; // For a very short interval, 0.5 is a reasonable choice.
+		ERR_FAIL_V_MSG(interval, "Zero length interval.");
+	}
+
+	interval.frac = (p_offset - offset_begin) / idx_interval;
+	return interval;
+}
+
+Vector2 Curve2D::_sample_baked(Interval p_interval, bool p_cubic) const {
+	// Assuming p_interval is valid.
+	ERR_FAIL_INDEX_V_MSG(p_interval.idx, baked_point_cache.size(), Vector2(), "Invalid interval");
+
+	int idx = p_interval.idx;
+	real_t frac = p_interval.frac;
+
+	const Vector2 *r = baked_point_cache.ptr();
+	int pc = baked_point_cache.size();
 
 	if (p_cubic) {
 		Vector2 pre = idx > 0 ? r[idx - 1] : r[idx];
@@ -937,44 +927,70 @@ Vector2 Curve2D::sample_baked(real_t p_offset, bool p_cubic) const {
 	}
 }
 
-Transform2D Curve2D::sample_baked_with_rotation(real_t p_offset, bool p_cubic, bool p_loop, real_t p_lookahead) const {
-	real_t path_length = get_baked_length(); // Ensure baked.
-	ERR_FAIL_COND_V_MSG(path_length == 0, Transform2D(), "Length of Curve2D is 0.");
+Transform2D Curve2D::_sample_posture(Interval p_interval) const {
+	// Assuming that p_interval is valid.
+	ERR_FAIL_INDEX_V_MSG(p_interval.idx, baked_point_cache.size(), Transform2D(), "Invalid interval");
 
-	Vector2 pos = sample_baked(p_offset, p_cubic);
+	int idx = p_interval.idx;
+	real_t frac = p_interval.frac;
 
-	real_t ahead = p_offset + p_lookahead;
+	Vector2 forward_begin = baked_forward_vector_cache[idx];
+	Vector2 forward_end = baked_forward_vector_cache[idx + 1];
 
-	if (p_loop && ahead >= path_length) {
-		// If our lookahead will loop, we need to check if the path is closed.
-		int point_count = get_point_count();
-		if (point_count > 0) {
-			Vector2 start_point = get_point_position(0);
-			Vector2 end_point = get_point_position(point_count - 1);
-			if (start_point == end_point) {
-				// Since the path is closed we want to 'smooth off'
-				// the corner at the start/end.
-				// So we wrap the lookahead back round.
-				ahead = Math::fmod(ahead, path_length);
-			}
-		}
+	// Build frames at both ends of the interval, then interpolate.
+	const Vector2 forward = forward_begin.slerp(forward_end, frac).normalized();
+	const Vector2 side = Vector2(-forward.y, forward.x);
+
+	return Transform2D(forward, side, Vector2(0.0, 0.0));
+}
+
+Vector2 Curve2D::sample_baked(real_t p_offset, bool p_cubic) const {
+	if (baked_cache_dirty) {
+		_bake();
 	}
 
-	Vector2 ahead_pos = sample_baked(ahead, p_cubic);
+	// Validate: Curve may not have baked points.
+	int pc = baked_point_cache.size();
+	ERR_FAIL_COND_V_MSG(pc == 0, Vector2(), "No points in Curve2D.");
 
-	Vector2 tangent_to_curve;
-	if (ahead_pos == pos) {
-		// This will happen at the end of non-looping or non-closed paths.
-		// We'll try a look behind instead, in order to get a meaningful angle.
-		tangent_to_curve =
-				(pos - sample_baked(p_offset - p_lookahead, p_cubic)).normalized();
-	} else {
-		tangent_to_curve = (ahead_pos - pos).normalized();
+	if (pc == 1) {
+		return baked_point_cache[0];
+	}
+
+	p_offset = CLAMP(p_offset, 0.0, get_baked_length()); // PathFollower implement wrapping logic.
+
+	Curve2D::Interval interval = _find_interval(p_offset);
+	return _sample_baked(interval, p_cubic);
+}
+
+Transform2D Curve2D::sample_baked_with_rotation(real_t p_offset, bool p_cubic) const {
+	if (baked_cache_dirty) {
+		_bake();
 	}
 
-	Vector2 normal_of_curve = -tangent_to_curve.orthogonal();
+	// Validate: Curve may not have baked points.
+	const int point_count = baked_point_cache.size();
+	ERR_FAIL_COND_V_MSG(point_count == 0, Transform2D(), "No points in Curve3D.");
+
+	if (point_count == 1) {
+		Transform2D t;
+		t.set_origin(baked_point_cache.get(0));
+		ERR_FAIL_V_MSG(t, "Only 1 point in Curve2D.");
+	}
+
+	p_offset = CLAMP(p_offset, 0.0, get_baked_length()); // PathFollower implement wrapping logic.
+
+	// 0. Find interval for all sampling steps.
+	Curve2D::Interval interval = _find_interval(p_offset);
+
+	// 1. Sample position.
+	Vector2 pos = _sample_baked(interval, p_cubic);
 
-	return Transform2D(normal_of_curve, tangent_to_curve, pos);
+	// 2. Sample rotation frame.
+	Transform2D frame = _sample_posture(interval);
+	frame.set_origin(pos);
+
+	return frame;
 }
 
 PackedVector2Array Curve2D::get_baked_points() const {
@@ -1147,6 +1163,50 @@ PackedVector2Array Curve2D::tessellate(int p_max_stages, real_t p_tolerance) con
 	return tess;
 }
 
+Vector<RBMap<real_t, Vector2>> Curve2D::_tessellate_even_length(int p_max_stages, real_t p_length) const {
+	Vector<RBMap<real_t, Vector2>> midpoints;
+	ERR_FAIL_COND_V_MSG(points.size() < 2, midpoints, "Curve must have at least 2 control point");
+
+	midpoints.resize(points.size() - 1);
+
+	for (int i = 0; i < points.size() - 1; i++) {
+		_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);
+	}
+	return midpoints;
+}
+
+PackedVector2Array Curve2D::tessellate_even_length(int p_max_stages, real_t p_length) const {
+	PackedVector2Array tess;
+
+	Vector<RBMap<real_t, Vector2>> midpoints = _tessellate_even_length(p_max_stages, p_length);
+	if (midpoints.size() == 0) {
+		return tess;
+	}
+
+	int pc = 1;
+	for (int i = 0; i < points.size() - 1; i++) {
+		pc++;
+		pc += midpoints[i].size();
+	}
+
+	tess.resize(pc);
+	Vector2 *bpw = tess.ptrw();
+	bpw[0] = points[0].position;
+	int pidx = 0;
+
+	for (int i = 0; i < points.size() - 1; i++) {
+		for (const KeyValue<real_t, Vector2> &E : midpoints[i]) {
+			pidx++;
+			bpw[pidx] = E.value;
+		}
+
+		pidx++;
+		bpw[pidx] = points[i + 1].position;
+	}
+
+	return tess;
+}
+
 bool Curve2D::_set(const StringName &p_name, const Variant &p_value) {
 	Vector<String> components = String(p_name).split("/", true, 2);
 	if (components.size() >= 2 && components[0].begins_with("point_") && components[0].trim_prefix("point_").is_valid_int()) {
@@ -1224,12 +1284,13 @@ void Curve2D::_bind_methods() {
 	ClassDB::bind_method(D_METHOD("get_bake_interval"), &Curve2D::get_bake_interval);
 
 	ClassDB::bind_method(D_METHOD("get_baked_length"), &Curve2D::get_baked_length);
-	ClassDB::bind_method(D_METHOD("sample_baked", "offset", "cubic"), &Curve2D::sample_baked, DEFVAL(false));
-	ClassDB::bind_method(D_METHOD("sample_baked_with_rotation", "offset", "cubic", "loop", "lookahead"), &Curve2D::sample_baked_with_rotation, DEFVAL(false), DEFVAL(true), DEFVAL(4.0));
+	ClassDB::bind_method(D_METHOD("sample_baked", "offset", "cubic"), &Curve2D::sample_baked, DEFVAL(0.0), DEFVAL(false));
+	ClassDB::bind_method(D_METHOD("sample_baked_with_rotation", "offset", "cubic"), &Curve2D::sample_baked_with_rotation, DEFVAL(0.0), DEFVAL(false));
 	ClassDB::bind_method(D_METHOD("get_baked_points"), &Curve2D::get_baked_points);
 	ClassDB::bind_method(D_METHOD("get_closest_point", "to_point"), &Curve2D::get_closest_point);
 	ClassDB::bind_method(D_METHOD("get_closest_offset", "to_point"), &Curve2D::get_closest_offset);
 	ClassDB::bind_method(D_METHOD("tessellate", "max_stages", "tolerance_degrees"), &Curve2D::tessellate, DEFVAL(5), DEFVAL(4));
+	ClassDB::bind_method(D_METHOD("tessellate_even_length", "max_stages", "tolerance_length"), &Curve2D::tessellate_even_length, DEFVAL(5), DEFVAL(20.0));
 
 	ClassDB::bind_method(D_METHOD("_get_data"), &Curve2D::_get_data);
 	ClassDB::bind_method(D_METHOD("_set_data", "data"), &Curve2D::_set_data);
@@ -2133,8 +2194,8 @@ void Curve3D::_bind_methods() {
 	ClassDB::bind_method(D_METHOD("is_up_vector_enabled"), &Curve3D::is_up_vector_enabled);
 
 	ClassDB::bind_method(D_METHOD("get_baked_length"), &Curve3D::get_baked_length);
-	ClassDB::bind_method(D_METHOD("sample_baked", "offset", "cubic"), &Curve3D::sample_baked, DEFVAL(false));
-	ClassDB::bind_method(D_METHOD("sample_baked_with_rotation", "offset", "cubic", "apply_tilt"), &Curve3D::sample_baked_with_rotation, DEFVAL(false), DEFVAL(false));
+	ClassDB::bind_method(D_METHOD("sample_baked", "offset", "cubic"), &Curve3D::sample_baked, DEFVAL(0.0), DEFVAL(false));
+	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));
 	ClassDB::bind_method(D_METHOD("sample_baked_up_vector", "offset", "apply_tilt"), &Curve3D::sample_baked_up_vector, DEFVAL(false));
 	ClassDB::bind_method(D_METHOD("get_baked_points"), &Curve3D::get_baked_points);
 	ClassDB::bind_method(D_METHOD("get_baked_tilts"), &Curve3D::get_baked_tilts);
diff --git a/scene/resources/curve.h b/scene/resources/curve.h
index 88c3cf3ae6..ea3ceabb14 100644
--- a/scene/resources/curve.h
+++ b/scene/resources/curve.h
@@ -172,6 +172,7 @@ class Curve2D : public Resource {
 
 	mutable bool baked_cache_dirty = false;
 	mutable PackedVector2Array baked_point_cache;
+	mutable PackedVector2Array baked_forward_vector_cache;
 	mutable Vector<real_t> baked_dist_cache;
 	mutable real_t baked_max_ofs = 0.0;
 
@@ -181,7 +182,16 @@ class Curve2D : public Resource {
 
 	real_t bake_interval = 5.0;
 
+	struct Interval {
+		int idx;
+		real_t frac;
+	};
+	Interval _find_interval(real_t p_offset) const;
+	Vector2 _sample_baked(Interval p_interval, bool p_cubic) const;
+	Transform2D _sample_posture(Interval p_interval) const;
+
 	void _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;
+	void _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;
 	Dictionary _get_data() const;
 	void _set_data(const Dictionary &p_data);
 
@@ -192,6 +202,8 @@ class Curve2D : public Resource {
 	void _add_point(const Vector2 &p_position, const Vector2 &p_in = Vector2(), const Vector2 &p_out = Vector2(), int p_atpos = -1);
 	void _remove_point(int p_index);
 
+	Vector<RBMap<real_t, Vector2>> _tessellate_even_length(int p_max_stages = 5, real_t p_length = 0.2) const;
+
 protected:
 	static void _bind_methods();
 
@@ -216,12 +228,13 @@ public:
 
 	real_t get_baked_length() const;
 	Vector2 sample_baked(real_t p_offset, bool p_cubic = false) const;
-	Transform2D sample_baked_with_rotation(real_t p_offset, bool p_cubic = false, bool p_loop = true, real_t p_lookahead = 4.0) const;
+	Transform2D sample_baked_with_rotation(real_t p_offset, bool p_cubic = false) const;
 	PackedVector2Array get_baked_points() const; //useful for going through
 	Vector2 get_closest_point(const Vector2 &p_to_point) const;
 	real_t get_closest_offset(const Vector2 &p_to_point) const;
 
 	PackedVector2Array tessellate(int p_max_stages = 5, real_t p_tolerance = 4) const; //useful for display
+	PackedVector2Array tessellate_even_length(int p_max_stages = 5, real_t p_length = 20.0) const; // Useful for baking.
 
 	Curve2D();
 };