Fix #33113: cycles not rendering motion blur correct with dying particles.

There were a bunch of other issues with dupli motion blur and syncing, the problem
being that there was no proper way to detect corresponding duplis between frames
or updates. As a solution, a persistent_id was added to the DupliObject. It's an
extension of the previous index value, with one index for each dupli level. This
can be used to reliably find matching dupli objects between frames. Works with
nested duplis, multiple particle systems, etc.

4 files changed, 129 insertions, 195 deletions

diff --git a/intern/cycles/blender/blender_object.cpp b/intern/cycles/blender/blender_object.cpp
index 1b920249733..a18cb79c102 100644
--- a/intern/cycles/blender/blender_object.cpp
+++ b/intern/cycles/blender/blender_object.cpp
@@ -86,11 +86,11 @@ static uint object_ray_visibility(BL::Object b_ob)
 
 /* Light */
 
-void BlenderSync::sync_light(BL::Object b_parent, int b_index, BL::Object b_ob, Transform& tfm)
+void BlenderSync::sync_light(BL::Object b_parent, int persistent_id[OBJECT_PERSISTENT_ID_SIZE], BL::Object b_ob, Transform& tfm)
 {
 	/* test if we need to sync */
 	Light *light;
-	ObjectKey key(b_parent, b_index, b_ob);
+	ObjectKey key(b_parent, persistent_id, b_ob);
 
 	if(!light_map.sync(&light, b_ob, b_parent, key))
 		return;
@@ -196,23 +196,24 @@ void BlenderSync::sync_background_light()
 
 /* Object */
 
-void BlenderSync::sync_object(BL::Object b_parent, int b_index, BL::DupliObject b_dupli_ob, Transform& tfm, uint layer_flag, int motion, int particle_id)
+Object *BlenderSync::sync_object(BL::Object b_parent, int persistent_id[OBJECT_PERSISTENT_ID_SIZE], BL::DupliObject b_dupli_ob, Transform& tfm, uint layer_flag, int motion)
 {
 	BL::Object b_ob = (b_dupli_ob ? b_dupli_ob.object() : b_parent);
 	
 	/* light is handled separately */
 	if(object_is_light(b_ob)) {
 		if(!motion)
-			sync_light(b_parent, b_index, b_ob, tfm);
-		return;
+			sync_light(b_parent, persistent_id, b_ob, tfm);
+
+		return NULL;
 	}
 
 	/* only interested in object that we can create meshes from */
 	if(!object_is_mesh(b_ob))
-		return;
+		return NULL;
 
 	/* key to lookup object */
-	ObjectKey key(b_parent, b_index, b_ob);
+	ObjectKey key(b_parent, persistent_id, b_ob);
 	Object *object;
 
 	/* motion vector case */
@@ -234,7 +235,7 @@ void BlenderSync::sync_object(BL::Object b_parent, int b_index, BL::DupliObject
 				sync_mesh_motion(b_ob, object->mesh, motion);
 		}
 
-		return;
+		return object;
 	}
 
 	/* test if we need to sync */
@@ -248,13 +249,14 @@ void BlenderSync::sync_object(BL::Object b_parent, int b_index, BL::DupliObject
 	/* mesh sync */
 	object->mesh = sync_mesh(b_ob, object_updated);
 
+	/* sspecial case not tracked by object update flags */
 	if(use_holdout != object->use_holdout) {
 		object->use_holdout = use_holdout;
 		scene->object_manager->tag_update(scene);
 	}
 
-	/* object sync */
-	/* transform comparison should not be needed, but duplis don't work perfect
+	/* object sync
+	 * transform comparison should not be needed, but duplis don't work perfect
 	 * in the depsgraph and may not signal changes, so this is a workaround */
 	if(object_updated || (object->mesh && object->mesh->need_update) || tfm != object->tfm) {
 		object->name = b_ob.name().c_str();
@@ -264,7 +266,10 @@ void BlenderSync::sync_object(BL::Object b_parent, int b_index, BL::DupliObject
 		object->motion.post = tfm;
 		object->use_motion = false;
 
-		object->random_id = hash_int_2d(hash_string(object->name.c_str()), b_index);
+		object->random_id = hash_string(object->name.c_str());
+		if(persistent_id)
+			for(int i = 0; i < OBJECT_PERSISTENT_ID_SIZE; i++)
+				object->random_id = hash_int_2d(object->random_id, persistent_id[i]);
 
 		/* visibility flags for both parent */
 		object->visibility = object_ray_visibility(b_ob) & PATH_RAY_ALL;
@@ -289,10 +294,10 @@ void BlenderSync::sync_object(BL::Object b_parent, int b_index, BL::DupliObject
 			object->dupli_uv = make_float2(0.0f, 0.0f);
 		}
 
-		object->particle_id = particle_id;
-
 		object->tag_update(scene);
 	}
+
+	return object;
 }
 
 /* Object Loop */
@@ -314,7 +319,9 @@ void BlenderSync::sync_objects(BL::SpaceView3D b_v3d, int motion)
 	/* object loop */
 	BL::Scene::objects_iterator b_ob;
 	BL::Scene b_sce = b_scene;
-	int particle_offset = 1;	/* first particle is dummy for regular, non-instanced objects */
+
+	/* global particle index counter */
+	int particle_id = 1;
 
 	bool cancel = false;
 
@@ -327,16 +334,14 @@ void BlenderSync::sync_objects(BL::SpaceView3D b_v3d, int motion)
 			if(!hide) {
 				progress.set_sync_status("Synchronizing object", (*b_ob).name());
 
-				int num_particles = object_count_particles(*b_ob);
-
 				if(b_ob->is_duplicator()) {
-					hide = true; /* duplicators hidden by default */
+					/* duplicators hidden by default */
+					hide = true;
 
 					/* dupli objects */
 					b_ob->dupli_list_create(b_scene, 2);
 
 					BL::Object::dupli_list_iterator b_dup;
-					int b_index = 0;
 
 					for(b_ob->dupli_list.begin(b_dup); b_dup != b_ob->dupli_list.end(); ++b_dup) {
 						Transform tfm = get_transform(b_dup->matrix());
@@ -345,7 +350,8 @@ void BlenderSync::sync_objects(BL::SpaceView3D b_v3d, int motion)
 						bool emitter_hide = false;
 
 						if(b_dup_ob.is_duplicator()) {
-							emitter_hide = true;	/* duplicators hidden by default */
+							/* duplicators hidden by default */
+							emitter_hide = true;
 							
 							/* check if we should render or hide particle emitter */
 							BL::Object::particle_systems_iterator b_psys;
@@ -355,21 +361,34 @@ void BlenderSync::sync_objects(BL::SpaceView3D b_v3d, int motion)
 						}
 
 						if(!(b_dup->hide() || dup_hide || emitter_hide)) {
-							sync_object(*b_ob, b_index, *b_dup, tfm, ob_layer, motion, b_dup->particle_index() + particle_offset);
+							/* the persistent_id allows us to match dupli objects
+							 * between frames and updates */
+							BL::Array<int, OBJECT_PERSISTENT_ID_SIZE> persistent_id = b_dup->persistent_id();
+
+							/* sync object and mesh or light data */
+							Object *object = sync_object(*b_ob, persistent_id.data, *b_dup, tfm, ob_layer, motion);
+
+							/* sync possible particle data, note particle_id
+							 * starts counting at 1, first is dummy particle */
+							if(!motion && object && sync_dupli_particle(*b_ob, *b_dup, object)) {
+								if(particle_id != object->particle_id) {
+									object->particle_id = particle_id;
+									scene->object_manager->tag_update(scene);
+								}
+
+								particle_id++;
+							}
+
 						}
-						
-						++b_index;
 					}
 
 					b_ob->dupli_list_clear();
 				}
 
-				/* sync particles and check if we should render or hide particle emitter */
+				/* check if we should render or hide particle emitter */
 				BL::Object::particle_systems_iterator b_psys;
-				for(b_ob->particle_systems.begin(b_psys); b_psys != b_ob->particle_systems.end(); ++b_psys) {
-					if(!motion)
-						sync_particles(*b_ob, *b_psys);
 
+				for(b_ob->particle_systems.begin(b_psys); b_psys != b_ob->particle_systems.end(); ++b_psys) {
 					if(b_psys->settings().use_render_emitter())
 						hide = false;
 				}
@@ -377,10 +396,8 @@ void BlenderSync::sync_objects(BL::SpaceView3D b_v3d, int motion)
 				if(!hide) {
 					/* object itself */
 					Transform tfm = get_transform(b_ob->matrix_world());
-					sync_object(*b_ob, 0, PointerRNA_NULL, tfm, ob_layer, motion, 0);
+					sync_object(*b_ob, NULL, PointerRNA_NULL, tfm, ob_layer, motion);
 				}
-
-				particle_offset += num_particles;
 			}
 
 			cancel = progress.get_cancel();
diff --git a/intern/cycles/blender/blender_particles.cpp b/intern/cycles/blender/blender_particles.cpp
index c4c6d2f79a3..769cd9f532d 100644
--- a/intern/cycles/blender/blender_particles.cpp
+++ b/intern/cycles/blender/blender_particles.cpp
@@ -17,6 +17,7 @@
  */
 
 #include "mesh.h"
+#include "object.h"
 #include "particles.h"
 
 #include "blender_sync.h"
@@ -28,170 +29,57 @@ CCL_NAMESPACE_BEGIN
 
 /* Utilities */
 
-
-/* Particles Sync */
-
-bool BlenderSync::psys_need_update(BL::ParticleSystem b_psys)
-{
-	/* Particle data is only needed for
-	 * a) Billboard render mode if object's own material uses particle info
-	 * b) object/group render mode if any dupli object's material uses particle info
-	 *
-	 * Note: Meshes have to be synced at this point!
-	 */
-	bool need_update = false;
-	
-	switch (b_psys.settings().render_type()) {
-		/* XXX not implemented yet! 
-		 * billboards/strands would become part of the mesh data (?),
-		 * so the mesh attributes would store whether particle info is required.
-		 */
-		#if 0
-		case BL::ParticleSettings::render_type_BILLBOARD:
-		case BL::ParticleSettings::render_type_PATH: {	/* for strand rendering */
-			BL::ID key = (BKE_object_is_modified(b_ob))? b_ob: b_ob.data();
-			Mesh *mesh = mesh_map.find(key);
-			if(mesh) {
-				need_update |= mesh->need_attribute(scene, ATTR_STD_PARTICLE) && mesh->need_update;
-			}
-			break;
-		}
-		#endif
-		
-		case BL::ParticleSettings::render_type_OBJECT: {
-			BL::Object b_dupli_ob = b_psys.settings().dupli_object();
-			if(b_dupli_ob) {
-				BL::ID key = (BKE_object_is_modified(b_dupli_ob))? b_dupli_ob: b_dupli_ob.data();
-				Mesh *mesh = mesh_map.find(key);
-				if(mesh) {
-					need_update |= mesh->need_attribute(scene, ATTR_STD_PARTICLE) && mesh->need_update;
-				}
-			}
-			break;
-		}
-		
-		case BL::ParticleSettings::render_type_GROUP: {
-			BL::Group b_dupli_group = b_psys.settings().dupli_group();
-			if(b_dupli_group) {
-				BL::Group::objects_iterator b_gob;
-				for (b_dupli_group.objects.begin(b_gob); b_gob != b_dupli_group.objects.end(); ++b_gob) {
-					BL::ID key = (BKE_object_is_modified(*b_gob))? *b_gob: b_gob->data();
-					Mesh *mesh = mesh_map.find(key);
-					if(mesh) {
-						need_update |= mesh->need_attribute(scene, ATTR_STD_PARTICLE) && mesh->need_update;
-					}
-				}
-			}
-			break;
-		}
-		
-		default:
-			/* avoid compiler warning */
-			break;
-	}
-	
-	return need_update;
-}
-
-static bool use_particle_system(BL::ParticleSystem b_psys)
-{
-	/* only use duplicator particles? disabled particle info for
-	 * halo and billboard to reduce particle count.
-	 * Probably not necessary since particles don't contain a huge amount
-	 * of data compared to other textures.
-	 */
-	#if 0
-	int render_type = b_psys->settings().render_type();
-	return (render_type == BL::ParticleSettings::render_type_OBJECT
-	        || render_type == BL::ParticleSettings::render_type_GROUP);
-	#endif
-	
-	return true;
-}
-
-static bool use_particle(BL::Particle b_pa, bool preview, bool show_unborn, bool use_dead)
-{
-	return b_pa.is_exist() && (!preview || b_pa.is_visible()) &&
-		(b_pa.alive_state() != BL::Particle::alive_state_UNBORN || show_unborn) &&
-		(b_pa.alive_state() != BL::Particle::alive_state_DEAD || use_dead);
-}
-
-static int psys_count_particles(BL::ParticleSystem b_psys, bool preview)
+bool BlenderSync::sync_dupli_particle(BL::Object b_ob, BL::DupliObject b_dup, Object *object)
 {
-	BL::ParticleSystem::particles_iterator b_pa;
-	bool show_unborn = b_psys.settings().show_unborn();
-	bool use_dead = b_psys.settings().use_dead();
-	int num = 0;
+	/* test if this dupli was generated from a particle sytem */
+	BL::ParticleSystem b_psys = b_dup.particle_system();
+	if(!b_psys)
+		return false;
 
-	for(b_psys.particles.begin(b_pa); b_pa != b_psys.particles.end(); ++b_pa)
-		if(use_particle(*b_pa, preview, show_unborn, use_dead))
-			++num;
+	/* test if we need particle data */
+	if(!object->mesh->need_attribute(scene, ATTR_STD_PARTICLE))
+		return false;
 
-	return num;
-}
+	/* don't handle child particles yet */
+	BL::Array<int, OBJECT_PERSISTENT_ID_SIZE> persistent_id = b_dup.persistent_id();
 
-int BlenderSync::object_count_particles(BL::Object b_ob)
-{
-	BL::Object::particle_systems_iterator b_psys;
-	int num = 0;
+	if(persistent_id[0] >= b_psys.particles.length())
+		return false;
 
-	for(b_ob.particle_systems.begin(b_psys); b_psys != b_ob.particle_systems.end(); ++b_psys)
-		if(use_particle_system(*b_psys))
-			num += psys_count_particles(*b_psys, preview);
+	/* find particle system */
+	ParticleSystemKey key(b_ob, persistent_id);
+	ParticleSystem *psys;
 
-	return num;
-}
+	bool first_use = !particle_system_map.is_used(key);
+	bool need_update = particle_system_map.sync(&psys, b_ob, b_dup.object(), key);
 
-void BlenderSync::sync_particles(BL::Object b_ob, BL::ParticleSystem b_psys)
-{
-	/* depending on settings the psys may not even be rendered */
-	if(!use_particle_system(b_psys))
-		return;
-	
-	/* key to lookup particle system */
-	ParticleSystemKey key(b_ob, b_psys);
-	ParticleSystem *psys;
-	
-	/* test if we need to sync */
-	bool object_updated = false;
-	
-	if(particle_system_map.sync(&psys, b_ob, b_ob, key))
-		object_updated = true;
-	
-	bool need_update = psys_need_update(b_psys);
-	
-	if(object_updated || need_update) {
-		bool show_unborn = b_psys.settings().show_unborn();
-		bool use_dead = b_psys.settings().use_dead();
+	/* no update needed? */
+	if(!need_update && !object->mesh->need_update && !scene->object_manager->need_update)
+		return true;
 
-		int num = psys_count_particles(b_psys, preview);
+	/* first time used in this sync loop? clear and tag update */
+	if(first_use) {
 		psys->particles.clear();
-		psys->particles.reserve(num);
-		
-		BL::ParticleSystem::particles_iterator b_pa;
-		int index = 0;
-
-		for(b_psys.particles.begin(b_pa); b_pa != b_psys.particles.end(); ++b_pa) {
-			if(use_particle(*b_pa, preview, show_unborn, use_dead)) {
-				Particle pa;
-				
-				pa.index = index;
-				pa.age = b_scene.frame_current() - b_pa->birth_time();
-				pa.lifetime = b_pa->lifetime();
-				pa.location = get_float3(b_pa->location());
-				pa.rotation = get_float4(b_pa->rotation());
-				pa.size = b_pa->size();
-				pa.velocity = get_float3(b_pa->velocity());
-				pa.angular_velocity = get_float3(b_pa->angular_velocity());
-				
-				psys->particles.push_back(pa);
-			}
-			
-			++index;
-		}
-		
 		psys->tag_update(scene);
 	}
+
+	/* add particle */
+	BL::Particle b_pa = b_psys.particles[persistent_id[0]];
+	Particle pa;
+	
+	pa.index = persistent_id[0];
+	pa.age = b_scene.frame_current() - b_pa.birth_time();
+	pa.lifetime = b_pa.lifetime();
+	pa.location = get_float3(b_pa.location());
+	pa.rotation = get_float4(b_pa.rotation());
+	pa.size = b_pa.size();
+	pa.velocity = get_float3(b_pa.velocity());
+	pa.angular_velocity = get_float3(b_pa.angular_velocity());
+
+	psys->particles.push_back(pa);
+
+	/* return that this object has particle data */
+	return true;
 }
 
 CCL_NAMESPACE_END
diff --git a/intern/cycles/blender/blender_sync.h b/intern/cycles/blender/blender_sync.h
index 36cd5e684a7..9a478118c04 100644
--- a/intern/cycles/blender/blender_sync.h
+++ b/intern/cycles/blender/blender_sync.h
@@ -42,6 +42,7 @@ class Film;
 class Light;
 class Mesh;
 class Object;
+class ParticleSystem;
 class Scene;
 class Shader;
 class ShaderGraph;
@@ -80,20 +81,20 @@ private:
 
 	void sync_nodes(Shader *shader, BL::ShaderNodeTree b_ntree);
 	Mesh *sync_mesh(BL::Object b_ob, bool object_updated);
-	void sync_object(BL::Object b_parent, int b_index, BL::DupliObject b_dupli_object, Transform& tfm, uint layer_flag, int motion, int particle_id);
-	void sync_light(BL::Object b_parent, int b_index, BL::Object b_ob, Transform& tfm);
+	Object *sync_object(BL::Object b_parent, int persistent_id[OBJECT_PERSISTENT_ID_SIZE], BL::DupliObject b_dupli_object, Transform& tfm, uint layer_flag, int motion);
+	void sync_light(BL::Object b_parent, int persistent_id[OBJECT_PERSISTENT_ID_SIZE], BL::Object b_ob, Transform& tfm);
 	void sync_background_light();
 	void sync_mesh_motion(BL::Object b_ob, Mesh *mesh, int motion);
 	void sync_camera_motion(BL::Object b_ob, int motion);
-	void sync_particles(BL::Object b_ob, BL::ParticleSystem b_psys);
+
+	/* particles */
+	bool sync_dupli_particle(BL::Object b_ob, BL::DupliObject b_dup, Object *object);
 
 	/* util */
 	void find_shader(BL::ID id, vector<uint>& used_shaders, int default_shader);
 	bool BKE_object_is_modified(BL::Object b_ob);
 	bool object_is_mesh(BL::Object b_ob);
 	bool object_is_light(BL::Object b_ob);
-	bool psys_need_update(BL::ParticleSystem b_psys);
-	int object_count_particles(BL::Object b_ob);
 
 	/* variables */
 	BL::RenderEngine b_engine;
diff --git a/intern/cycles/blender/blender_util.h b/intern/cycles/blender/blender_util.h
index df1e99882b8..5c47b124642 100644
--- a/intern/cycles/blender/blender_util.h
+++ b/intern/cycles/blender/blender_util.h
@@ -284,6 +284,12 @@ public:
 		return recalc;
 	}
 
+	bool is_used(const K& key)
+	{
+		T *data = find(key);
+		return (data)? used_set.find(data) != used_set.end(): NULL;
+	}
+
 	void used(T *data)
 	{
 		/* tag data as still in use */
@@ -343,27 +349,49 @@ protected:
 
 /* Object Key */
 
+enum { OBJECT_PERSISTENT_ID_SIZE = 8 };
+
 struct ObjectKey {
 	void *parent;
-	int index;
+	int id[OBJECT_PERSISTENT_ID_SIZE];
 	void *ob;
 
-	ObjectKey(void *parent_, int index_, void *ob_)
-	: parent(parent_), index(index_), ob(ob_) {}
+	ObjectKey(void *parent_, int id_[OBJECT_PERSISTENT_ID_SIZE], void *ob_)
+	: parent(parent_), ob(ob_)
+	{
+		if(id_)
+			memcpy(id, id_, sizeof(id));
+		else
+			memset(id, 0, sizeof(id));
+	}
 
 	bool operator<(const ObjectKey& k) const
-	{ return (parent < k.parent || (parent == k.parent && (index < k.index || (index == k.index && ob < k.ob)))); }
+	{
+		return (parent < k.parent) ||
+		       (parent == k.parent && (memcmp(id, k.id, sizeof(id)) < 0)) ||
+		       (memcmp(id, k.id, sizeof(id)) == 0 && ob < k.ob);
+	}
 };
 
 struct ParticleSystemKey {
 	void *ob;
-	void *psys;
+	int id[OBJECT_PERSISTENT_ID_SIZE];
 
-	ParticleSystemKey(void *ob_, void *psys_)
-	: ob(ob_), psys(psys_) {}
+	ParticleSystemKey(void *ob_, int id_[OBJECT_PERSISTENT_ID_SIZE])
+	: ob(ob_)
+	{
+		if(id_)
+			memcpy(id, id_, sizeof(id));
+		else
+			memset(id, 0, sizeof(id));
+	}
 
 	bool operator<(const ParticleSystemKey& k) const
-	{ return (ob < k.ob && psys < k.psys); }
+	{
+		/* first id is particle index, we don't compare that */
+		return (ob < k.ob) ||
+		       (ob == k.ob && (memcmp(id+1, k.id+1, sizeof(int)*(OBJECT_PERSISTENT_ID_SIZE-1)) < 0));
+	}
 };
 
 CCL_NAMESPACE_END