Fixed Timestep Interpolation (2D)

Adds fixed timestep interpolation to the rendering server (2D only).
Switchable on and off with a project setting (default is off).

Co-authored-by: lawnjelly <lawnjelly@gmail.com>

4 files changed, 139 insertions, 0 deletions

diff --git a/core/math/transform_interpolator.cpp b/core/math/transform_interpolator.cpp
new file mode 100644
index 0000000000..7cfe880b5a
--- /dev/null
+++ b/core/math/transform_interpolator.cpp
@@ -0,0 +1,76 @@
+/**************************************************************************/
+/*  transform_interpolator.cpp                                            */
+/**************************************************************************/
+/*                         This file is part of:                          */
+/*                             GODOT ENGINE                               */
+/*                        https://godotengine.org                         */
+/**************************************************************************/
+/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
+/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur.                  */
+/*                                                                        */
+/* Permission is hereby granted, free of charge, to any person obtaining  */
+/* a copy of this software and associated documentation files (the        */
+/* "Software"), to deal in the Software without restriction, including    */
+/* without limitation the rights to use, copy, modify, merge, publish,    */
+/* distribute, sublicense, and/or sell copies of the Software, and to     */
+/* permit persons to whom the Software is furnished to do so, subject to  */
+/* the following conditions:                                              */
+/*                                                                        */
+/* The above copyright notice and this permission notice shall be         */
+/* included in all copies or substantial portions of the Software.        */
+/*                                                                        */
+/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,        */
+/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF     */
+/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
+/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY   */
+/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,   */
+/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE      */
+/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                 */
+/**************************************************************************/
+
+#include "transform_interpolator.h"
+
+#include "core/math/transform_2d.h"
+
+void TransformInterpolator::interpolate_transform_2d(const Transform2D &p_prev, const Transform2D &p_curr, Transform2D &r_result, real_t p_fraction) {
+	// Extract parameters.
+	Vector2 p1 = p_prev.get_origin();
+	Vector2 p2 = p_curr.get_origin();
+
+	// Special case for physics interpolation, if flipping, don't interpolate basis.
+	// If the determinant polarity changes, the handedness of the coordinate system changes.
+	if (_sign(p_prev.determinant()) != _sign(p_curr.determinant())) {
+		r_result.columns[0] = p_curr.columns[0];
+		r_result.columns[1] = p_curr.columns[1];
+		r_result.set_origin(p1.lerp(p2, p_fraction));
+		return;
+	}
+
+	real_t r1 = p_prev.get_rotation();
+	real_t r2 = p_curr.get_rotation();
+
+	Size2 s1 = p_prev.get_scale();
+	Size2 s2 = p_curr.get_scale();
+
+	// Slerp rotation.
+	Vector2 v1(Math::cos(r1), Math::sin(r1));
+	Vector2 v2(Math::cos(r2), Math::sin(r2));
+
+	real_t dot = v1.dot(v2);
+
+	dot = CLAMP(dot, -1, 1);
+
+	Vector2 v;
+
+	if (dot > 0.9995f) {
+		v = v1.lerp(v2, p_fraction).normalized(); // Linearly interpolate to avoid numerical precision issues.
+	} else {
+		real_t angle = p_fraction * Math::acos(dot);
+		Vector2 v3 = (v2 - v1 * dot).normalized();
+		v = v1 * Math::cos(angle) + v3 * Math::sin(angle);
+	}
+
+	// Construct matrix.
+	r_result = Transform2D(Math::atan2(v.y, v.x), p1.lerp(p2, p_fraction));
+	r_result.scale_basis(s1.lerp(s2, p_fraction));
+}
diff --git a/core/math/transform_interpolator.h b/core/math/transform_interpolator.h
new file mode 100644
index 0000000000..a9bce2bd7f
--- /dev/null
+++ b/core/math/transform_interpolator.h
@@ -0,0 +1,46 @@
+/**************************************************************************/
+/*  transform_interpolator.h                                              */
+/**************************************************************************/
+/*                         This file is part of:                          */
+/*                             GODOT ENGINE                               */
+/*                        https://godotengine.org                         */
+/**************************************************************************/
+/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
+/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur.                  */
+/*                                                                        */
+/* Permission is hereby granted, free of charge, to any person obtaining  */
+/* a copy of this software and associated documentation files (the        */
+/* "Software"), to deal in the Software without restriction, including    */
+/* without limitation the rights to use, copy, modify, merge, publish,    */
+/* distribute, sublicense, and/or sell copies of the Software, and to     */
+/* permit persons to whom the Software is furnished to do so, subject to  */
+/* the following conditions:                                              */
+/*                                                                        */
+/* The above copyright notice and this permission notice shall be         */
+/* included in all copies or substantial portions of the Software.        */
+/*                                                                        */
+/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,        */
+/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF     */
+/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
+/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY   */
+/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,   */
+/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE      */
+/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                 */
+/**************************************************************************/
+
+#ifndef TRANSFORM_INTERPOLATOR_H
+#define TRANSFORM_INTERPOLATOR_H
+
+#include "core/math/math_defs.h"
+
+struct Transform2D;
+
+class TransformInterpolator {
+private:
+	static bool _sign(real_t p_val) { return p_val >= 0; }
+
+public:
+	static void interpolate_transform_2d(const Transform2D &p_prev, const Transform2D &p_curr, Transform2D &r_result, real_t p_fraction);
+};
+
+#endif // TRANSFORM_INTERPOLATOR_H
diff --git a/core/os/main_loop.h b/core/os/main_loop.h
index b45eb38aeb..e48541d074 100644
--- a/core/os/main_loop.h
+++ b/core/os/main_loop.h
@@ -62,6 +62,7 @@ public:
 	};
 
 	virtual void initialize();
+	virtual void iteration_prepare() {}
 	virtual bool physics_process(double p_time);
 	virtual bool process(double p_time);
 	virtual void finalize();
diff --git a/core/templates/local_vector.h b/core/templates/local_vector.h
index 6478297fd1..e0047e0782 100644
--- a/core/templates/local_vector.h
+++ b/core/templates/local_vector.h
@@ -104,6 +104,22 @@ public:
 		return false;
 	}
 
+	U erase_multiple_unordered(const T &p_val) {
+		U from = 0;
+		U occurrences = 0;
+		while (true) {
+			int64_t idx = find(p_val, from);
+
+			if (idx == -1) {
+				break;
+			}
+			remove_at_unordered(idx);
+			from = idx;
+			occurrences++;
+		}
+		return occurrences;
+	}
+
 	void invert() {
 		for (U i = 0; i < count / 2; i++) {
 			SWAP(data[i], data[count - i - 1]);