Merge pull request #93025 from kleonc/y-sort-physics-interpolation

Account for physics interpolation and transform snapping when Y-sorting

2 files changed, 96 insertions, 61 deletions

diff --git a/servers/rendering/renderer_canvas_cull.cpp b/servers/rendering/renderer_canvas_cull.cpp
index 0ec161d8cf..b5873528f7 100644
--- a/servers/rendering/renderer_canvas_cull.cpp
+++ b/servers/rendering/renderer_canvas_cull.cpp
@@ -51,7 +51,7 @@ void RendererCanvasCull::_render_canvas_item_tree(RID p_to_render_target, Canvas
 	memset(z_last_list, 0, z_range * sizeof(RendererCanvasRender::Item *));
 
 	for (int i = 0; i < p_child_item_count; i++) {
-		_cull_canvas_item(p_child_items[i].item, p_transform, p_clip_rect, Color(1, 1, 1, 1), 0, z_list, z_last_list, nullptr, nullptr, true, p_canvas_cull_mask, Point2(), 1, nullptr);
+		_cull_canvas_item(p_child_items[i].item, p_transform, p_clip_rect, Color(1, 1, 1, 1), 0, z_list, z_last_list, nullptr, nullptr, false, p_canvas_cull_mask, Point2(), 1, nullptr);
 	}
 
 	RendererCanvasRender::Item *list = nullptr;
@@ -79,45 +79,71 @@ void RendererCanvasCull::_render_canvas_item_tree(RID p_to_render_target, Canvas
 	}
 }
 
-void _collect_ysort_children(RendererCanvasCull::Item *p_canvas_item, const Transform2D &p_transform, RendererCanvasCull::Item *p_material_owner, const Color &p_modulate, RendererCanvasCull::Item **r_items, int &r_index, int p_z) {
+void RendererCanvasCull::_collect_ysort_children(RendererCanvasCull::Item *p_canvas_item, RendererCanvasCull::Item *p_material_owner, const Color &p_modulate, RendererCanvasCull::Item **r_items, int &r_index, int p_z) {
 	int child_item_count = p_canvas_item->child_items.size();
 	RendererCanvasCull::Item **child_items = p_canvas_item->child_items.ptrw();
 	for (int i = 0; i < child_item_count; i++) {
-		int abs_z = 0;
 		if (child_items[i]->visible) {
-			if (r_items) {
-				r_items[r_index] = child_items[i];
-				child_items[i]->ysort_xform = p_transform;
-				child_items[i]->ysort_pos = p_transform.xform(child_items[i]->xform_curr.columns[2]);
-				child_items[i]->material_owner = child_items[i]->use_parent_material ? p_material_owner : nullptr;
-				child_items[i]->ysort_modulate = p_modulate;
-				child_items[i]->ysort_index = r_index;
-				child_items[i]->ysort_parent_abs_z_index = p_z;
-
-				if (!child_items[i]->repeat_source) {
-					child_items[i]->repeat_size = p_canvas_item->repeat_size;
-					child_items[i]->repeat_times = p_canvas_item->repeat_times;
-					child_items[i]->repeat_source_item = p_canvas_item->repeat_source_item;
-				}
+			// To y-sort according to the item's final position, physics interpolation
+			// and transform snapping need to be applied before y-sorting.
+			Transform2D child_xform;
+			if (!_interpolation_data.interpolation_enabled || !child_items[i]->interpolated) {
+				child_xform = child_items[i]->xform_curr;
+			} else {
+				real_t f = Engine::get_singleton()->get_physics_interpolation_fraction();
+				TransformInterpolator::interpolate_transform_2d(child_items[i]->xform_prev, child_items[i]->xform_curr, child_xform, f);
+			}
 
-				// Y sorted canvas items are flattened into r_items. Calculate their absolute z index to use when rendering r_items.
-				if (child_items[i]->z_relative) {
-					abs_z = CLAMP(p_z + child_items[i]->z_index, RS::CANVAS_ITEM_Z_MIN, RS::CANVAS_ITEM_Z_MAX);
-				} else {
-					abs_z = child_items[i]->z_index;
-				}
+			if (snapping_2d_transforms_to_pixel) {
+				child_xform.columns[2] = child_xform.columns[2].round();
+			}
+
+			r_items[r_index] = child_items[i];
+			child_items[i]->ysort_xform = p_canvas_item->ysort_xform * child_xform;
+			child_items[i]->material_owner = child_items[i]->use_parent_material ? p_material_owner : nullptr;
+			child_items[i]->ysort_modulate = p_modulate;
+			child_items[i]->ysort_index = r_index;
+			child_items[i]->ysort_parent_abs_z_index = p_z;
+
+			if (!child_items[i]->repeat_source) {
+				child_items[i]->repeat_size = p_canvas_item->repeat_size;
+				child_items[i]->repeat_times = p_canvas_item->repeat_times;
+				child_items[i]->repeat_source_item = p_canvas_item->repeat_source_item;
+			}
+
+			// Y sorted canvas items are flattened into r_items. Calculate their absolute z index to use when rendering r_items.
+			int abs_z = 0;
+			if (child_items[i]->z_relative) {
+				abs_z = CLAMP(p_z + child_items[i]->z_index, RS::CANVAS_ITEM_Z_MIN, RS::CANVAS_ITEM_Z_MAX);
+			} else {
+				abs_z = child_items[i]->z_index;
 			}
 
 			r_index++;
 
 			if (child_items[i]->sort_y) {
-				_collect_ysort_children(child_items[i], p_transform * child_items[i]->xform_curr, child_items[i]->use_parent_material ? p_material_owner : child_items[i], p_modulate * child_items[i]->modulate, r_items, r_index, abs_z);
+				_collect_ysort_children(child_items[i], child_items[i]->use_parent_material ? p_material_owner : child_items[i], p_modulate * child_items[i]->modulate, r_items, r_index, abs_z);
 			}
 		}
 	}
 }
 
-void _mark_ysort_dirty(RendererCanvasCull::Item *ysort_owner, RID_Owner<RendererCanvasCull::Item, true> &canvas_item_owner) {
+int RendererCanvasCull::_count_ysort_children(RendererCanvasCull::Item *p_canvas_item) {
+	int ysort_children_count = 0;
+	int child_item_count = p_canvas_item->child_items.size();
+	RendererCanvasCull::Item *const *child_items = p_canvas_item->child_items.ptr();
+	for (int i = 0; i < child_item_count; i++) {
+		if (child_items[i]->visible) {
+			ysort_children_count++;
+			if (child_items[i]->sort_y) {
+				ysort_children_count += _count_ysort_children(child_items[i]);
+			}
+		}
+	}
+	return ysort_children_count;
+}
+
+void RendererCanvasCull::_mark_ysort_dirty(RendererCanvasCull::Item *ysort_owner) {
 	do {
 		ysort_owner->ysort_children_count = -1;
 		ysort_owner = canvas_item_owner.owns(ysort_owner->parent) ? canvas_item_owner.get_or_null(ysort_owner->parent) : nullptr;
@@ -236,7 +262,7 @@ void RendererCanvasCull::_attach_canvas_item_for_draw(RendererCanvasCull::Item *
 	}
 }
 
-void RendererCanvasCull::_cull_canvas_item(Item *p_canvas_item, const Transform2D &p_parent_xform, const Rect2 &p_clip_rect, const Color &p_modulate, int p_z, RendererCanvasRender::Item **r_z_list, RendererCanvasRender::Item **r_z_last_list, Item *p_canvas_clip, Item *p_material_owner, bool p_allow_y_sort, uint32_t p_canvas_cull_mask, const Point2 &p_repeat_size, int p_repeat_times, RendererCanvasRender::Item *p_repeat_source_item) {
+void RendererCanvasCull::_cull_canvas_item(Item *p_canvas_item, const Transform2D &p_parent_xform, const Rect2 &p_clip_rect, const Color &p_modulate, int p_z, RendererCanvasRender::Item **r_z_list, RendererCanvasRender::Item **r_z_last_list, Item *p_canvas_clip, Item *p_material_owner, bool p_is_already_y_sorted, uint32_t p_canvas_cull_mask, const Point2 &p_repeat_size, int p_repeat_times, RendererCanvasRender::Item *p_repeat_source_item) {
 	Item *ci = p_canvas_item;
 
 	if (!ci->visible) {
@@ -260,15 +286,29 @@ void RendererCanvasCull::_cull_canvas_item(Item *p_canvas_item, const Transform2
 		}
 	}
 
+	Transform2D self_xform;
 	Transform2D final_xform;
-	if (!_interpolation_data.interpolation_enabled || !ci->interpolated) {
-		final_xform = ci->xform_curr;
+	if (p_is_already_y_sorted) {
+		// Y-sorted item's final transform is calculated before y-sorting,
+		// and is passed as `p_parent_xform` afterwards. No need to recalculate.
+		final_xform = p_parent_xform;
 	} else {
-		real_t f = Engine::get_singleton()->get_physics_interpolation_fraction();
-		TransformInterpolator::interpolate_transform_2d(ci->xform_prev, ci->xform_curr, final_xform, f);
-	}
+		if (!_interpolation_data.interpolation_enabled || !ci->interpolated) {
+			self_xform = ci->xform_curr;
+		} else {
+			real_t f = Engine::get_singleton()->get_physics_interpolation_fraction();
+			TransformInterpolator::interpolate_transform_2d(ci->xform_prev, ci->xform_curr, self_xform, f);
+		}
 
-	Transform2D parent_xform = p_parent_xform;
+		Transform2D parent_xform = p_parent_xform;
+
+		if (snapping_2d_transforms_to_pixel) {
+			self_xform.columns[2] = self_xform.columns[2].round();
+			parent_xform.columns[2] = parent_xform.columns[2].round();
+		}
+
+		final_xform = parent_xform * self_xform;
+	}
 
 	Point2 repeat_size = p_repeat_size;
 	int repeat_times = p_repeat_times;
@@ -284,13 +324,6 @@ void RendererCanvasCull::_cull_canvas_item(Item *p_canvas_item, const Transform2
 		ci->repeat_source_item = repeat_source_item;
 	}
 
-	if (snapping_2d_transforms_to_pixel) {
-		final_xform.columns[2] = (final_xform.columns[2] + Point2(0.5, 0.5)).floor();
-		parent_xform.columns[2] = (parent_xform.columns[2] + Point2(0.5, 0.5)).floor();
-	}
-
-	final_xform = parent_xform * final_xform;
-
 	Rect2 global_rect = final_xform.xform(rect);
 	if (repeat_source_item && (repeat_size.x || repeat_size.y)) {
 		// Top-left repeated rect.
@@ -355,29 +388,27 @@ void RendererCanvasCull::_cull_canvas_item(Item *p_canvas_item, const Transform2
 	}
 
 	if (ci->sort_y) {
-		if (p_allow_y_sort) {
+		if (!p_is_already_y_sorted) {
 			if (ci->ysort_children_count == -1) {
-				ci->ysort_children_count = 0;
-				_collect_ysort_children(ci, Transform2D(), p_material_owner, Color(1, 1, 1, 1), nullptr, ci->ysort_children_count, p_z);
+				ci->ysort_children_count = _count_ysort_children(ci);
 			}
 
 			child_item_count = ci->ysort_children_count + 1;
 			child_items = (Item **)alloca(child_item_count * sizeof(Item *));
 
-			ci->ysort_xform = ci->xform_curr.affine_inverse();
-			ci->ysort_pos = Vector2();
+			ci->ysort_xform = Transform2D();
 			ci->ysort_modulate = Color(1, 1, 1, 1);
 			ci->ysort_index = 0;
 			ci->ysort_parent_abs_z_index = parent_z;
 			child_items[0] = ci;
 			int i = 1;
-			_collect_ysort_children(ci, Transform2D(), p_material_owner, Color(1, 1, 1, 1), child_items, i, p_z);
+			_collect_ysort_children(ci, p_material_owner, Color(1, 1, 1, 1), child_items, i, p_z);
 
-			SortArray<Item *, ItemPtrSort> sorter;
+			SortArray<Item *, ItemYSort> sorter;
 			sorter.sort(child_items, child_item_count);
 
 			for (i = 0; i < child_item_count; i++) {
-				_cull_canvas_item(child_items[i], final_xform * child_items[i]->ysort_xform, p_clip_rect, modulate * child_items[i]->ysort_modulate, child_items[i]->ysort_parent_abs_z_index, r_z_list, r_z_last_list, (Item *)ci->final_clip_owner, (Item *)child_items[i]->material_owner, false, p_canvas_cull_mask, child_items[i]->repeat_size, child_items[i]->repeat_times, child_items[i]->repeat_source_item);
+				_cull_canvas_item(child_items[i], final_xform * child_items[i]->ysort_xform, p_clip_rect, modulate * child_items[i]->ysort_modulate, child_items[i]->ysort_parent_abs_z_index, r_z_list, r_z_last_list, (Item *)ci->final_clip_owner, (Item *)child_items[i]->material_owner, true, p_canvas_cull_mask, child_items[i]->repeat_size, child_items[i]->repeat_times, child_items[i]->repeat_source_item);
 			}
 		} else {
 			RendererCanvasRender::Item *canvas_group_from = nullptr;
@@ -401,14 +432,14 @@ void RendererCanvasCull::_cull_canvas_item(Item *p_canvas_item, const Transform2
 			if (!child_items[i]->behind && !use_canvas_group) {
 				continue;
 			}
-			_cull_canvas_item(child_items[i], final_xform, p_clip_rect, modulate, p_z, r_z_list, r_z_last_list, (Item *)ci->final_clip_owner, p_material_owner, true, p_canvas_cull_mask, repeat_size, repeat_times, repeat_source_item);
+			_cull_canvas_item(child_items[i], final_xform, p_clip_rect, modulate, p_z, r_z_list, r_z_last_list, (Item *)ci->final_clip_owner, p_material_owner, false, p_canvas_cull_mask, repeat_size, repeat_times, repeat_source_item);
 		}
 		_attach_canvas_item_for_draw(ci, p_canvas_clip, r_z_list, r_z_last_list, final_xform, p_clip_rect, global_rect, modulate, p_z, p_material_owner, use_canvas_group, canvas_group_from);
 		for (int i = 0; i < child_item_count; i++) {
 			if (child_items[i]->behind || use_canvas_group) {
 				continue;
 			}
-			_cull_canvas_item(child_items[i], final_xform, p_clip_rect, modulate, p_z, r_z_list, r_z_last_list, (Item *)ci->final_clip_owner, p_material_owner, true, p_canvas_cull_mask, repeat_size, repeat_times, repeat_source_item);
+			_cull_canvas_item(child_items[i], final_xform, p_clip_rect, modulate, p_z, r_z_list, r_z_last_list, (Item *)ci->final_clip_owner, p_material_owner, false, p_canvas_cull_mask, repeat_size, repeat_times, repeat_source_item);
 		}
 	}
 }
@@ -509,7 +540,7 @@ void RendererCanvasCull::canvas_item_set_parent(RID p_item, RID p_parent) {
 			item_owner->child_items.erase(canvas_item);
 
 			if (item_owner->sort_y) {
-				_mark_ysort_dirty(item_owner, canvas_item_owner);
+				_mark_ysort_dirty(item_owner);
 			}
 		}
 
@@ -529,7 +560,7 @@ void RendererCanvasCull::canvas_item_set_parent(RID p_item, RID p_parent) {
 			item_owner->children_order_dirty = true;
 
 			if (item_owner->sort_y) {
-				_mark_ysort_dirty(item_owner, canvas_item_owner);
+				_mark_ysort_dirty(item_owner);
 			}
 
 		} else {
@@ -546,7 +577,7 @@ void RendererCanvasCull::canvas_item_set_visible(RID p_item, bool p_visible) {
 
 	canvas_item->visible = p_visible;
 
-	_mark_ysort_dirty(canvas_item, canvas_item_owner);
+	_mark_ysort_dirty(canvas_item);
 }
 
 void RendererCanvasCull::canvas_item_set_light_mask(RID p_item, int p_mask) {
@@ -1742,7 +1773,7 @@ void RendererCanvasCull::canvas_item_set_sort_children_by_y(RID p_item, bool p_e
 
 	canvas_item->sort_y = p_enable;
 
-	_mark_ysort_dirty(canvas_item, canvas_item_owner);
+	_mark_ysort_dirty(canvas_item);
 }
 
 void RendererCanvasCull::canvas_item_set_z_index(RID p_item, int p_z) {
@@ -2423,7 +2454,7 @@ bool RendererCanvasCull::free(RID p_rid) {
 				item_owner->child_items.erase(canvas_item);
 
 				if (item_owner->sort_y) {
-					_mark_ysort_dirty(item_owner, canvas_item_owner);
+					_mark_ysort_dirty(item_owner);
 				}
 			}
 		}
diff --git a/servers/rendering/renderer_canvas_cull.h b/servers/rendering/renderer_canvas_cull.h
index 91c03054f7..9a088d94ed 100644
--- a/servers/rendering/renderer_canvas_cull.h
+++ b/servers/rendering/renderer_canvas_cull.h
@@ -50,8 +50,7 @@ public:
 		bool children_order_dirty;
 		int ysort_children_count;
 		Color ysort_modulate;
-		Transform2D ysort_xform;
-		Vector2 ysort_pos;
+		Transform2D ysort_xform; // Relative to y-sorted subtree's root item (identity for such root). Its `origin.y` is used for sorting.
 		int ysort_index;
 		int ysort_parent_abs_z_index; // Absolute Z index of parent. Only populated and used when y-sorting.
 		uint32_t visibility_layer = 0xffffffff;
@@ -84,7 +83,6 @@ public:
 			index = 0;
 			ysort_children_count = -1;
 			ysort_xform = Transform2D();
-			ysort_pos = Vector2();
 			ysort_index = 0;
 			ysort_parent_abs_z_index = 0;
 		}
@@ -96,13 +94,15 @@ public:
 		}
 	};
 
-	struct ItemPtrSort {
+	struct ItemYSort {
 		_FORCE_INLINE_ bool operator()(const Item *p_left, const Item *p_right) const {
-			if (Math::is_equal_approx(p_left->ysort_pos.y, p_right->ysort_pos.y)) {
+			const real_t left_y = p_left->ysort_xform.columns[2].y;
+			const real_t right_y = p_right->ysort_xform.columns[2].y;
+			if (Math::is_equal_approx(left_y, right_y)) {
 				return p_left->ysort_index < p_right->ysort_index;
 			}
 
-			return p_left->ysort_pos.y < p_right->ysort_pos.y;
+			return left_y < right_y;
 		}
 	};
 
@@ -187,7 +187,11 @@ public:
 
 private:
 	void _render_canvas_item_tree(RID p_to_render_target, Canvas::ChildItem *p_child_items, int p_child_item_count, const Transform2D &p_transform, const Rect2 &p_clip_rect, const Color &p_modulate, RendererCanvasRender::Light *p_lights, RendererCanvasRender::Light *p_directional_lights, RS::CanvasItemTextureFilter p_default_filter, RS::CanvasItemTextureRepeat p_default_repeat, bool p_snap_2d_vertices_to_pixel, uint32_t p_canvas_cull_mask, RenderingMethod::RenderInfo *r_render_info = nullptr);
-	void _cull_canvas_item(Item *p_canvas_item, const Transform2D &p_parent_xform, const Rect2 &p_clip_rect, const Color &p_modulate, int p_z, RendererCanvasRender::Item **r_z_list, RendererCanvasRender::Item **r_z_last_list, Item *p_canvas_clip, Item *p_material_owner, bool p_allow_y_sort, uint32_t p_canvas_cull_mask, const Point2 &p_repeat_size, int p_repeat_times, RendererCanvasRender::Item *p_repeat_source_item);
+	void _cull_canvas_item(Item *p_canvas_item, const Transform2D &p_parent_xform, const Rect2 &p_clip_rect, const Color &p_modulate, int p_z, RendererCanvasRender::Item **r_z_list, RendererCanvasRender::Item **r_z_last_list, Item *p_canvas_clip, Item *p_material_owner, bool p_is_already_y_sorted, uint32_t p_canvas_cull_mask, const Point2 &p_repeat_size, int p_repeat_times, RendererCanvasRender::Item *p_repeat_source_item);
+
+	void _collect_ysort_children(RendererCanvasCull::Item *p_canvas_item, RendererCanvasCull::Item *p_material_owner, const Color &p_modulate, RendererCanvasCull::Item **r_items, int &r_index, int p_z);
+	int _count_ysort_children(RendererCanvasCull::Item *p_canvas_item);
+	void _mark_ysort_dirty(RendererCanvasCull::Item *ysort_owner);
 
 	static constexpr int z_range = RS::CANVAS_ITEM_Z_MAX - RS::CANVAS_ITEM_Z_MIN + 1;