Implement Particle Trails

-Enable the trails and set the length in seconds
-Provide a mesh with a skeleton and a skin
-Or, alternatively use one of the built-in TubeTrailMesh/RibbonTrailMesh
-Works deterministically
-Fixed particle collisions (were broken)
-Not working in 2D yet (that will happen next)

4 files changed, 230 insertions, 58 deletions

diff --git a/servers/rendering/renderer_rd/shaders/particles.glsl b/servers/rendering/renderer_rd/shaders/particles.glsl
index 3712220dc4..beaff10793 100644
--- a/servers/rendering/renderer_rd/shaders/particles.glsl
+++ b/servers/rendering/renderer_rd/shaders/particles.glsl
@@ -76,6 +76,11 @@ struct FrameParams {
 	float time;
 	float delta;
 
+	uint frame;
+	uint pad0;
+	uint pad1;
+	uint pad2;
+
 	uint random_seed;
 	uint attractor_count;
 	uint collider_count;
@@ -92,10 +97,16 @@ layout(set = 1, binding = 0, std430) restrict buffer FrameHistory {
 }
 frame_history;
 
+#define PARTICLE_FLAG_ACTIVE uint(1)
+#define PARTICLE_FLAG_STARTED uint(2)
+#define PARTICLE_FLAG_TRAILED uint(4)
+#define PARTICLE_FRAME_MASK uint(0xFFFF)
+#define PARTICLE_FRAME_SHIFT uint(16)
+
 struct ParticleData {
 	mat4 xform;
 	vec3 velocity;
-	bool is_active;
+	uint flags;
 	vec4 color;
 	vec4 custom;
 };
@@ -162,7 +173,7 @@ layout(push_constant, binding = 0, std430) uniform Params {
 	bool use_fractional_delta;
 	bool sub_emitter_mode;
 	bool can_emit;
-	uint pad;
+	bool trail_pass;
 }
 params;
 
@@ -201,6 +212,14 @@ bool emit_subparticle(mat4 p_xform, vec3 p_velocity, vec4 p_color, vec4 p_custom
 void main() {
 	uint particle = gl_GlobalInvocationID.x;
 
+	if (params.trail_size > 1) {
+		if (params.trail_pass) {
+			particle += (particle / (params.trail_size - 1)) + 1;
+		} else {
+			particle *= params.trail_size;
+		}
+	}
+
 	if (particle >= params.total_particles * params.trail_size) {
 		return; //discard
 	}
@@ -229,7 +248,7 @@ void main() {
 		PARTICLE.color = vec4(1.0);
 		PARTICLE.custom = vec4(0.0);
 		PARTICLE.velocity = vec3(0.0);
-		PARTICLE.is_active = false;
+		PARTICLE.flags = 0;
 		PARTICLE.xform = mat4(
 				vec4(1.0, 0.0, 0.0, 0.0),
 				vec4(0.0, 1.0, 0.0, 0.0),
@@ -237,6 +256,29 @@ void main() {
 				vec4(0.0, 0.0, 0.0, 1.0));
 	}
 
+	//clear started flag if set
+
+	if (params.trail_pass) {
+		//trail started
+		uint src_idx = index * params.trail_size;
+		if (bool(particles.data[src_idx].flags & PARTICLE_FLAG_STARTED)) {
+			//save start conditions for trails
+			PARTICLE.color = particles.data[src_idx].color;
+			PARTICLE.custom = particles.data[src_idx].custom;
+			PARTICLE.velocity = particles.data[src_idx].velocity;
+			PARTICLE.flags = PARTICLE_FLAG_TRAILED | ((frame_history.data[0].frame & PARTICLE_FRAME_MASK) << PARTICLE_FRAME_SHIFT); //mark it as trailed, save in which frame it will start
+			PARTICLE.xform = particles.data[src_idx].xform;
+		}
+
+		if (bool(PARTICLE.flags & PARTICLE_FLAG_TRAILED) && ((PARTICLE.flags >> PARTICLE_FRAME_SHIFT) == (FRAME.frame & PARTICLE_FRAME_MASK))) { //check this is trailed and see if it should start now
+			// we just assume that this is the first frame of the particle, the rest is deterministic
+			PARTICLE.flags = PARTICLE_FLAG_ACTIVE | (particles.data[src_idx].flags & (PARTICLE_FRAME_MASK << PARTICLE_FRAME_SHIFT));
+			return; //- this appears like it should be correct, but it seems not to be.. wonder why.
+		}
+	} else {
+		PARTICLE.flags &= ~PARTICLE_FLAG_STARTED;
+	}
+
 	bool collided = false;
 	vec3 collision_normal = vec3(0.0);
 	float collision_depth = 0.0;
@@ -245,19 +287,17 @@ void main() {
 
 #if !defined(DISABLE_VELOCITY)
 
-	if (PARTICLE.is_active) {
+	if (bool(PARTICLE.flags & PARTICLE_FLAG_ACTIVE)) {
 		PARTICLE.xform[3].xyz += PARTICLE.velocity * local_delta;
 	}
 #endif
 
-	/* Process physics if active */
-
-	if (params.sub_emitter_mode) {
-		if (!PARTICLE.is_active) {
+	if (!params.trail_pass && params.sub_emitter_mode) {
+		if (!bool(PARTICLE.flags & PARTICLE_FLAG_ACTIVE)) {
 			int src_index = atomicAdd(src_particles.particle_count, -1) - 1;
 
 			if (src_index >= 0) {
-				PARTICLE.is_active = true;
+				PARTICLE.flags = (PARTICLE_FLAG_ACTIVE | PARTICLE_FLAG_STARTED | (FRAME.cycle << PARTICLE_FRAME_SHIFT));
 				restart = true;
 
 				if (bool(src_particles.data[src_index].flags & EMISSION_FLAG_HAS_POSITION)) {
@@ -339,16 +379,12 @@ void main() {
 			}
 		}
 
-		uint current_cycle = FRAME.cycle;
-
-		if (FRAME.system_phase < restart_phase) {
-			current_cycle -= uint(1);
+		if (params.trail_pass) {
+			restart = false;
 		}
 
-		uint particle_number = current_cycle * uint(params.total_particles) + particle;
-
 		if (restart) {
-			PARTICLE.is_active = FRAME.emitting;
+			PARTICLE.flags = FRAME.emitting ? (PARTICLE_FLAG_ACTIVE | PARTICLE_FLAG_STARTED | (FRAME.cycle << PARTICLE_FRAME_SHIFT)) : 0;
 			restart_position = true;
 			restart_rotation_scale = true;
 			restart_velocity = true;
@@ -357,11 +393,15 @@ void main() {
 		}
 	}
 
-	if (restart && PARTICLE.is_active) {
+	bool particle_active = bool(PARTICLE.flags & PARTICLE_FLAG_ACTIVE);
+
+	uint particle_number = (PARTICLE.flags >> PARTICLE_FRAME_SHIFT) * uint(params.total_particles) + index;
+
+	if (restart && particle_active) {
 #CODE : START
 	}
 
-	if (PARTICLE.is_active) {
+	if (particle_active) {
 		for (uint i = 0; i < FRAME.attractor_count; i++) {
 			vec3 dir;
 			float amount;
@@ -539,7 +579,12 @@ void main() {
 		}
 	}
 
-	if (PARTICLE.is_active) {
+	if (particle_active) {
 #CODE : PROCESS
 	}
+
+	PARTICLE.flags &= ~PARTICLE_FLAG_ACTIVE;
+	if (particle_active) {
+		PARTICLE.flags |= PARTICLE_FLAG_ACTIVE;
+	}
 }
diff --git a/servers/rendering/renderer_rd/shaders/particles_copy.glsl b/servers/rendering/renderer_rd/shaders/particles_copy.glsl
index 80adb49619..7804d66d1c 100644
--- a/servers/rendering/renderer_rd/shaders/particles_copy.glsl
+++ b/servers/rendering/renderer_rd/shaders/particles_copy.glsl
@@ -6,10 +6,14 @@
 
 layout(local_size_x = 64, local_size_y = 1, local_size_z = 1) in;
 
+#define PARTICLE_FLAG_ACTIVE uint(1)
+#define PARTICLE_FLAG_STARTED uint(2)
+#define PARTICLE_FLAG_TRAILED uint(4)
+
 struct ParticleData {
 	mat4 xform;
 	vec3 velocity;
-	bool is_active;
+	uint flags;
 	vec4 color;
 	vec4 custom;
 };
@@ -33,12 +37,30 @@ sort_buffer;
 
 #endif // USE_SORT_BUFFER
 
+layout(set = 2, binding = 0, std430) restrict readonly buffer TrailBindPoses {
+	mat4 data[];
+}
+trail_bind_poses;
+
 layout(push_constant, binding = 0, std430) uniform Params {
 	vec3 sort_direction;
 	uint total_particles;
+
+	uint trail_size;
+	uint trail_total;
+	float frame_delta;
+	float frame_remainder;
+
+	vec3 align_up;
+	uint align_mode;
 }
 params;
 
+#define TRANSFORM_ALIGN_DISABLED 0
+#define TRANSFORM_ALIGN_Z_BILLBOARD 1
+#define TRANSFORM_ALIGN_Y_TO_VELOCITY 2
+#define TRANSFORM_ALIGN_Z_BILLBOARD_Y_TO_VELOCITY 3
+
 void main() {
 #ifdef MODE_FILL_SORT_BUFFER
 
@@ -47,7 +69,11 @@ void main() {
 		return; //discard
 	}
 
-	sort_buffer.data[particle].x = dot(params.sort_direction, particles.data[particle].xform[3].xyz);
+	uint src_particle = particle;
+	if (params.trail_size > 1) {
+		src_particle = src_particle * params.trail_size + params.trail_size / 2; //use trail center for sorting
+	}
+	sort_buffer.data[particle].x = dot(params.sort_direction, particles.data[src_particle].xform[3].xyz);
 	sort_buffer.data[particle].y = float(particle);
 #endif
 
@@ -61,13 +87,78 @@ void main() {
 	}
 
 #ifdef USE_SORT_BUFFER
-	particle = uint(sort_buffer.data[particle].y); //use index from sort buffer
+
+	if (params.trail_size > 1) {
+		particle = uint(sort_buffer.data[particle / params.trail_size].y) + (particle % params.trail_size);
+	} else {
+		particle = uint(sort_buffer.data[particle].y); //use index from sort buffer
+	}
 #endif
 
 	mat4 txform;
 
-	if (particles.data[particle].is_active) {
-		txform = transpose(particles.data[particle].xform);
+	if (bool(particles.data[particle].flags & PARTICLE_FLAG_ACTIVE) || bool(particles.data[particle].flags & PARTICLE_FLAG_TRAILED)) {
+		txform = particles.data[particle].xform;
+		if (params.trail_size > 1) {
+			// since the steps dont fit precisely in the history frames, must do a tiny bit of
+			// interpolation to get them close to their intended location.
+			uint part_ofs = particle % params.trail_size;
+			float natural_ofs = fract((float(part_ofs) / float(params.trail_size)) * float(params.trail_total)) * params.frame_delta;
+
+			txform[3].xyz -= particles.data[particle].velocity * natural_ofs;
+		}
+
+		switch (params.align_mode) {
+			case TRANSFORM_ALIGN_DISABLED: {
+			} break; //nothing
+			case TRANSFORM_ALIGN_Z_BILLBOARD: {
+				mat3 local = mat3(normalize(cross(params.align_up, params.sort_direction)), params.align_up, params.sort_direction);
+				local = local * mat3(txform);
+				txform[0].xyz = local[0];
+				txform[1].xyz = local[1];
+				txform[2].xyz = local[2];
+
+			} break;
+			case TRANSFORM_ALIGN_Y_TO_VELOCITY: {
+				vec3 v = particles.data[particle].velocity;
+				float s = (length(txform[0]) + length(txform[1]) + length(txform[2])) / 3.0;
+				if (length(v) > 0.0) {
+					txform[1].xyz = normalize(v);
+				} else {
+					txform[1].xyz = normalize(txform[1].xyz);
+				}
+
+				txform[0].xyz = normalize(cross(txform[1].xyz, txform[2].xyz));
+				txform[2].xyz = vec3(0.0, 0.0, 1.0) * s;
+				txform[0].xyz *= s;
+				txform[1].xyz *= s;
+			} break;
+			case TRANSFORM_ALIGN_Z_BILLBOARD_Y_TO_VELOCITY: {
+				vec3 v = particles.data[particle].velocity;
+				vec3 sv = v - params.sort_direction * dot(params.sort_direction, v); //screen velocity
+				float s = (length(txform[0]) + length(txform[1]) + length(txform[2])) / 3.0;
+
+				if (length(sv) == 0) {
+					sv = params.align_up;
+				}
+
+				sv = normalize(sv);
+
+				txform[0].xyz = normalize(cross(sv, params.sort_direction)) * s;
+				txform[1].xyz = sv * s;
+				txform[2].xyz = params.sort_direction * s;
+
+			} break;
+		}
+
+		txform[3].xyz += particles.data[particle].velocity * params.frame_remainder;
+
+		if (params.trail_size > 1) {
+			uint part_ofs = particle % params.trail_size;
+			txform = txform * trail_bind_poses.data[part_ofs];
+		}
+
+		txform = transpose(txform);
 	} else {
 		txform = mat4(vec4(0.0), vec4(0.0), vec4(0.0), vec4(0.0)); //zero scale, becomes invisible
 	}
diff --git a/servers/rendering/renderer_rd/shaders/scene_forward_clustered.glsl b/servers/rendering/renderer_rd/shaders/scene_forward_clustered.glsl
index fce17c47e8..f0dbe4eedf 100644
--- a/servers/rendering/renderer_rd/shaders/scene_forward_clustered.glsl
+++ b/servers/rendering/renderer_rd/shaders/scene_forward_clustered.glsl
@@ -48,11 +48,11 @@ layout(location = 8) in vec4 custom2_attrib;
 layout(location = 9) in vec4 custom3_attrib;
 #endif
 
-#if defined(BONES_USED)
+#if defined(BONES_USED) || defined(USE_PARTICLE_TRAILS)
 layout(location = 10) in uvec4 bone_attrib;
 #endif
 
-#if defined(WEIGHTS_USED)
+#if defined(WEIGHTS_USED) || defined(USE_PARTICLE_TRAILS)
 layout(location = 11) in vec4 weight_attrib;
 #endif
 
@@ -125,10 +125,72 @@ void main() {
 
 	if (is_multimesh) {
 		//multimesh, instances are for it
-		uint offset = (instances.data[instance_index].flags >> INSTANCE_FLAGS_MULTIMESH_STRIDE_SHIFT) & INSTANCE_FLAGS_MULTIMESH_STRIDE_MASK;
-		offset *= gl_InstanceIndex;
 
 		mat4 matrix;
+
+#ifdef USE_PARTICLE_TRAILS
+		uint trail_size = (instances.data[instance_index].flags >> INSTANCE_FLAGS_PARTICLE_TRAIL_SHIFT) & INSTANCE_FLAGS_PARTICLE_TRAIL_MASK;
+		uint stride = 3 + 1 + 1; //particles always uses this format
+
+		uint offset = trail_size * stride * gl_InstanceIndex;
+
+#ifdef COLOR_USED
+		vec4 pcolor;
+#endif
+		{
+			uint boffset = offset + bone_attrib.x * stride;
+			matrix = mat4(transforms.data[boffset + 0], transforms.data[boffset + 1], transforms.data[boffset + 2], vec4(0.0, 0.0, 0.0, 1.0)) * weight_attrib.x;
+#ifdef COLOR_USED
+			pcolor = transforms.data[boffset + 3] * weight_attrib.x;
+#endif
+		}
+		if (weight_attrib.y > 0.001) {
+			uint boffset = offset + bone_attrib.y * stride;
+			matrix += mat4(transforms.data[boffset + 0], transforms.data[boffset + 1], transforms.data[boffset + 2], vec4(0.0, 0.0, 0.0, 1.0)) * weight_attrib.y;
+#ifdef COLOR_USED
+			pcolor += transforms.data[boffset + 3] * weight_attrib.y;
+#endif
+		}
+		if (weight_attrib.z > 0.001) {
+			uint boffset = offset + bone_attrib.z * stride;
+			matrix += mat4(transforms.data[boffset + 0], transforms.data[boffset + 1], transforms.data[boffset + 2], vec4(0.0, 0.0, 0.0, 1.0)) * weight_attrib.z;
+#ifdef COLOR_USED
+			pcolor += transforms.data[boffset + 3] * weight_attrib.z;
+#endif
+		}
+		if (weight_attrib.w > 0.001) {
+			uint boffset = offset + bone_attrib.w * stride;
+			matrix += mat4(transforms.data[boffset + 0], transforms.data[boffset + 1], transforms.data[boffset + 2], vec4(0.0, 0.0, 0.0, 1.0)) * weight_attrib.w;
+#ifdef COLOR_USED
+			pcolor += transforms.data[boffset + 3] * weight_attrib.w;
+#endif
+		}
+
+		instance_custom = transforms.data[offset + 4];
+
+#ifdef COLOR_USED
+		color_interp *= pcolor;
+#endif
+
+#else
+		uint stride = 0;
+		{
+			//TODO implement a small lookup table for the stride
+			if (bool(instances.data[instance_index].flags & INSTANCE_FLAGS_MULTIMESH_FORMAT_2D)) {
+				stride += 2;
+			} else {
+				stride += 3;
+			}
+			if (bool(instances.data[instance_index].flags & INSTANCE_FLAGS_MULTIMESH_HAS_COLOR)) {
+				stride += 1;
+			}
+			if (bool(instances.data[instance_index].flags & INSTANCE_FLAGS_MULTIMESH_HAS_CUSTOM_DATA)) {
+				stride += 1;
+			}
+		}
+
+		uint offset = stride * gl_InstanceIndex;
+
 		if (bool(instances.data[instance_index].flags & INSTANCE_FLAGS_MULTIMESH_FORMAT_2D)) {
 			matrix = mat4(transforms.data[offset + 0], transforms.data[offset + 1], vec4(0.0, 0.0, 1.0, 0.0), vec4(0.0, 0.0, 0.0, 1.0));
 			offset += 2;
@@ -148,6 +210,7 @@ void main() {
 			instance_custom = transforms.data[offset];
 		}
 
+#endif
 		//transpose
 		matrix = transpose(matrix);
 		world_matrix = world_matrix * matrix;
@@ -165,32 +228,6 @@ void main() {
 	vec3 binormal = normalize(cross(normal, tangent) * binormalf);
 #endif
 
-#if 0
-	if (bool(instances.data[instance_index].flags & INSTANCE_FLAGS_SKELETON)) {
-		//multimesh, instances are for it
-
-		uvec2 bones_01 = uvec2(bone_attrib.x & 0xFFFF, bone_attrib.x >> 16) * 3;
-		uvec2 bones_23 = uvec2(bone_attrib.y & 0xFFFF, bone_attrib.y >> 16) * 3;
-		vec2 weights_01 = unpackUnorm2x16(bone_attrib.z);
-		vec2 weights_23 = unpackUnorm2x16(bone_attrib.w);
-
-		mat4 m = mat4(transforms.data[bones_01.x], transforms.data[bones_01.x + 1], transforms.data[bones_01.x + 2], vec4(0.0, 0.0, 0.0, 1.0)) * weights_01.x;
-		m += mat4(transforms.data[bones_01.y], transforms.data[bones_01.y + 1], transforms.data[bones_01.y + 2], vec4(0.0, 0.0, 0.0, 1.0)) * weights_01.y;
-		m += mat4(transforms.data[bones_23.x], transforms.data[bones_23.x + 1], transforms.data[bones_23.x + 2], vec4(0.0, 0.0, 0.0, 1.0)) * weights_23.x;
-		m += mat4(transforms.data[bones_23.y], transforms.data[bones_23.y + 1], transforms.data[bones_23.y + 2], vec4(0.0, 0.0, 0.0, 1.0)) * weights_23.y;
-
-		//reverse order because its transposed
-		vertex = (vec4(vertex, 1.0) * m).xyz;
-		normal = (vec4(normal, 0.0) * m).xyz;
-
-#if defined(TANGENT_USED) || defined(NORMAL_MAP_USED) || defined(LIGHT_ANISOTROPY_USED)
-
-		tangent = (vec4(tangent, 0.0) * m).xyz;
-		binormal = (vec4(binormal, 0.0) * m).xyz;
-#endif
-	}
-#endif
-
 #ifdef UV_USED
 	uv_interp = uv_attrib;
 #endif
diff --git a/servers/rendering/renderer_rd/shaders/scene_forward_clustered_inc.glsl b/servers/rendering/renderer_rd/shaders/scene_forward_clustered_inc.glsl
index 48e331714d..83423cdc24 100644
--- a/servers/rendering/renderer_rd/shaders/scene_forward_clustered_inc.glsl
+++ b/servers/rendering/renderer_rd/shaders/scene_forward_clustered_inc.glsl
@@ -61,12 +61,11 @@ layout(set = 0, binding = 2) uniform sampler shadow_sampler;
 #define INSTANCE_FLAGS_MULTIMESH_FORMAT_2D (1 << 13)
 #define INSTANCE_FLAGS_MULTIMESH_HAS_COLOR (1 << 14)
 #define INSTANCE_FLAGS_MULTIMESH_HAS_CUSTOM_DATA (1 << 15)
-#define INSTANCE_FLAGS_MULTIMESH_STRIDE_SHIFT 16
+#define INSTANCE_FLAGS_PARTICLE_TRAIL_SHIFT 16
 //3 bits of stride
-#define INSTANCE_FLAGS_MULTIMESH_STRIDE_MASK 0x7
+#define INSTANCE_FLAGS_PARTICLE_TRAIL_MASK 0xFF
 
-#define INSTANCE_FLAGS_SKELETON (1 << 19)
-#define INSTANCE_FLAGS_NON_UNIFORM_SCALE (1 << 20)
+#define INSTANCE_FLAGS_NON_UNIFORM_SCALE (1 << 24)
 
 layout(set = 0, binding = 3, std430) restrict readonly buffer OmniLights {
 	LightData data[];