Fix depsgraph to compute more accurate links for collision & force.

Current implementation more or less indiscriminately links physics
objects to colliders and forces, ignoring precise details of layer
checks and collider groups. The new depsgraph seemed to lack some
such links at all. The relevant code in modifiers suffers from a
lot of duplication.

Different physics simulations use independent implementations of
collision and similar things, which results in a lot of variance:

* Cloth collides with objects on same or visible layer with dupli.
* Softbody collides with objects on same layer without dupli.
* Non-hair particles collide on same layer with dupli.
* Smoke uses same code as cloth, but needs different modifier.
* Dynamic paint "collides" with brushes on any layer without dupli.

Force fields with absorption also imply dependency on colliders:

* For most systems, colliders are selected from same layer as field.
* For non-hair particles, it uses the same exact set as the particles.

As a special quirk, smoke ignores smoke flow force fields; on the other
hand dependency on such field implies dependency on the smoke domain.

This introduces two utility functions each for old and new depsgraph
that are flexible enough to handle all these variations, and uses them
to handle particles, cloth, smoke, softbody and dynpaint.

One thing to watch out for is that depsgraph code shouldn't rely on
any properties that don't cause a graph rebuild when changed. This
was violated in the original code that was building force field links,
while taking zero field weights into account.

This change may cause new dependency cycles in cases where necessary
dependencies were missing, but may also remove cycles in situations
where unnecessary links were previously created. It's also now possible
to solve some cycles by switching to explicit groups, since they are
now properly taken into account for dependencies.

Differential Revision: https://developer.blender.org/D2141

6 files changed, 89 insertions, 77 deletions

diff --git a/source/blender/blenkernel/BKE_collision.h b/source/blender/blenkernel/BKE_collision.h
index d5b4a584ec6..8fedcd4ab06 100644
--- a/source/blender/blenkernel/BKE_collision.h
+++ b/source/blender/blenkernel/BKE_collision.h
@@ -146,6 +146,10 @@ void collision_get_collider_velocity(float vel_old[3], float vel_new[3], struct
 /////////////////////////////////////////////////
 // used in effect.c
 /////////////////////////////////////////////////
+
+/* explicit control over layer mask and dupli recursion */
+struct Object **get_collisionobjects_ext(struct Scene *scene, struct Object *self, struct Group *group, int layer, unsigned int *numcollobj, unsigned int modifier_type, bool dupli);
+
 struct Object **get_collisionobjects(struct Scene *scene, struct Object *self, struct Group *group, unsigned int *numcollobj, unsigned int modifier_type);
 
 typedef struct ColliderCache {
diff --git a/source/blender/blenkernel/BKE_effect.h b/source/blender/blenkernel/BKE_effect.h
index f8fee444d91..b934ec7166d 100644
--- a/source/blender/blenkernel/BKE_effect.h
+++ b/source/blender/blenkernel/BKE_effect.h
@@ -110,7 +110,7 @@ typedef struct EffectorCache {
 } EffectorCache;
 
 void            free_partdeflect(struct PartDeflect *pd);
-struct ListBase *pdInitEffectors(struct Scene *scene, struct Object *ob_src, struct ParticleSystem *psys_src, struct EffectorWeights *weights, bool precalc);
+struct ListBase *pdInitEffectors(struct Scene *scene, struct Object *ob_src, struct ParticleSystem *psys_src, struct EffectorWeights *weights, bool for_simulation);
 void            pdEndEffectors(struct ListBase **effectors);
 void            pdPrecalculateEffectors(struct ListBase *effectors);
 void            pdDoEffectors(struct ListBase *effectors, struct ListBase *colliders, struct EffectorWeights *weights, struct EffectedPoint *point, float *force, float *impulse);
diff --git a/source/blender/blenkernel/depsgraph_private.h b/source/blender/blenkernel/depsgraph_private.h
index 7b3199efb41..69ca75836d9 100644
--- a/source/blender/blenkernel/depsgraph_private.h
+++ b/source/blender/blenkernel/depsgraph_private.h
@@ -34,6 +34,11 @@
 #include "DNA_constraint_types.h"
 #include "BKE_constraint.h"
 
+struct Scene;
+struct Group;
+struct EffectorWeights;
+struct ModifierData;
+
 /* **** DAG relation types *** */
 
 /* scene link to object */
@@ -152,6 +157,11 @@ DagNode *dag_get_node(DagForest *forest, void *fob);
 DagNode *dag_get_sub_node(DagForest *forest, void *fob);
 void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, short rel, const char *name);
 
+typedef bool (*DagCollobjFilterFunction)(struct Object *obj, struct ModifierData *md);
+
+void dag_add_collision_relations(DagForest *dag, struct Scene *scene, Object *ob, DagNode *node, struct Group *group, int layer, unsigned int modifier_type, DagCollobjFilterFunction fn, bool dupli, const char *name);
+void dag_add_forcefield_relations(DagForest *dag, struct Scene *scene, Object *ob, DagNode *node, struct EffectorWeights *eff, bool add_absorption, int skip_forcefield, const char *name);
+
 void graph_print_queue(DagNodeQueue *nqueue);
 void graph_print_queue_dist(DagNodeQueue *nqueue);
 void graph_print_adj_list(DagForest *dag);
diff --git a/source/blender/blenkernel/intern/collision.c b/source/blender/blenkernel/intern/collision.c
index 8cac856b560..35a7aafdbde 100644
--- a/source/blender/blenkernel/intern/collision.c
+++ b/source/blender/blenkernel/intern/collision.c
@@ -503,12 +503,13 @@ static void add_collision_object(Object ***objs, unsigned int *numobj, unsigned
 
 // return all collision objects in scene
 // collision object will exclude self 
-Object **get_collisionobjects(Scene *scene, Object *self, Group *group, unsigned int *numcollobj, unsigned int modifier_type)
+Object **get_collisionobjects_ext(Scene *scene, Object *self, Group *group, int layer, unsigned int *numcollobj, unsigned int modifier_type, bool dupli)
 {
 	Base *base;
 	Object **objs;
 	GroupObject *go;
 	unsigned int numobj= 0, maxobj= 100;
+	int level = dupli ? 0 : 1;
 	
 	objs= MEM_callocN(sizeof(Object *)*maxobj, "CollisionObjectsArray");
 
@@ -516,16 +517,14 @@ Object **get_collisionobjects(Scene *scene, Object *self, Group *group, unsigned
 	if (group) {
 		/* use specified group */
 		for (go= group->gobject.first; go; go= go->next)
-			add_collision_object(&objs, &numobj, &maxobj, go->ob, self, 0, modifier_type);
+			add_collision_object(&objs, &numobj, &maxobj, go->ob, self, level, modifier_type);
 	}
 	else {
 		Scene *sce_iter;
 		/* add objects in same layer in scene */
 		for (SETLOOPER(scene, sce_iter, base)) {
-			/* Need to check for active layers, too.
-			Otherwise this check fails if the objects are not on the same layer - DG */
-			if ((base->lay & self->lay) || (base->lay & scene->lay))
-				add_collision_object(&objs, &numobj, &maxobj, base->object, self, 0, modifier_type);
+			if ( base->lay & layer )
+				add_collision_object(&objs, &numobj, &maxobj, base->object, self, level, modifier_type);
 
 		}
 	}
@@ -535,6 +534,13 @@ Object **get_collisionobjects(Scene *scene, Object *self, Group *group, unsigned
 	return objs;
 }
 
+Object **get_collisionobjects(Scene *scene, Object *self, Group *group, unsigned int *numcollobj, unsigned int modifier_type)
+{
+	/* Need to check for active layers, too.
+	   Otherwise this check fails if the objects are not on the same layer - DG */
+	return get_collisionobjects_ext(scene, self, group, self->lay | scene->lay, numcollobj, modifier_type, true);
+}
+
 static void add_collider_cache_object(ListBase **objs, Object *ob, Object *self, int level)
 {
 	CollisionModifierData *cmd= NULL;
diff --git a/source/blender/blenkernel/intern/depsgraph.c b/source/blender/blenkernel/intern/depsgraph.c
index 45a23c39910..5f8332dcf0c 100644
--- a/source/blender/blenkernel/intern/depsgraph.c
+++ b/source/blender/blenkernel/intern/depsgraph.c
@@ -59,11 +59,14 @@
 #include "DNA_windowmanager_types.h"
 #include "DNA_movieclip_types.h"
 #include "DNA_mask_types.h"
+#include "DNA_modifier_types.h"
+#include "DNA_rigidbody_types.h"
 
 #include "BKE_anim.h"
 #include "BKE_animsys.h"
 #include "BKE_action.h"
 #include "BKE_DerivedMesh.h"
+#include "BKE_collision.h"
 #include "BKE_effect.h"
 #include "BKE_fcurve.h"
 #include "BKE_global.h"
@@ -450,49 +453,51 @@ static void dag_add_lamp_driver_relations(DagForest *dag, DagNode *node, Lamp *l
 	la->id.tag &= ~LIB_TAG_DOIT;
 }
 
-static void check_and_create_collision_relation(DagForest *dag, Object *ob, DagNode *node, Object *ob1, int skip_forcefield, bool no_collision)
+static void create_collision_relation(DagForest *dag, DagNode *node, Object *ob1, const char *name)
 {
-	DagNode *node2;
-	if (ob1->pd && (ob1->pd->deflect || ob1->pd->forcefield) && (ob1 != ob)) {
-		if ((skip_forcefield && ob1->pd->forcefield == skip_forcefield) || (no_collision && ob1->pd->forcefield == 0))
-			return;
-		node2 = dag_get_node(dag, ob1);
-		dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Field Collision");
+	DagNode *node2 = dag_get_node(dag, ob1);
+	dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, name);
+}
+
+void dag_add_collision_relations(DagForest *dag, Scene *scene, Object *ob, DagNode *node, Group *group, int layer, unsigned int modifier_type, DagCollobjFilterFunction fn, bool dupli, const char *name)
+{
+	unsigned int numcollobj;
+	Object **collobjs = get_collisionobjects_ext(scene, ob, group, layer, &numcollobj, modifier_type, dupli);
+
+	for (unsigned int i = 0; i < numcollobj; i++) {
+		Object *ob1 = collobjs[i];
+
+		if (!fn || fn(ob1, modifiers_findByType(ob1, modifier_type))) {
+			create_collision_relation(dag, node, ob1, name);
+		}
 	}
+
+	if (collobjs)
+		MEM_freeN(collobjs);
 }
 
-static void dag_add_collision_field_relation(DagForest *dag, Scene *scene, Object *ob, DagNode *node, int skip_forcefield, bool no_collision)
+void dag_add_forcefield_relations(DagForest *dag, Scene *scene, Object *ob, DagNode *node, EffectorWeights *effector_weights, bool add_absorption, int skip_forcefield, const char *name)
 {
-	Base *base;
-	ParticleSystem *particle_system;
+	ListBase *effectors = pdInitEffectors(scene, ob, NULL, effector_weights, false);
 
-	for (particle_system = ob->particlesystem.first;
-	     particle_system;
-	     particle_system = particle_system->next)
-	{
-		EffectorWeights *effector_weights = particle_system->part->effector_weights;
-		if (effector_weights->group) {
-			GroupObject *group_object;
+	if (effectors) {
+		for (EffectorCache *eff = effectors->first; eff; eff = eff->next) {
+			if (eff->ob != ob && eff->pd->forcefield != skip_forcefield) {
+				create_collision_relation(dag, node, eff->ob, name);
 
-			for (group_object = effector_weights->group->gobject.first;
-			     group_object;
-			     group_object = group_object->next)
-			{
-				if ((group_object->ob->lay & ob->lay)) {
-					check_and_create_collision_relation(dag, ob, node, group_object->ob, skip_forcefield, no_collision);
+				if (eff->pd->forcefield == PFIELD_SMOKEFLOW && eff->pd->f_source) {
+					create_collision_relation(dag, node, eff->pd->f_source, "Smoke Force Domain");
+				}
+
+				if (add_absorption && (eff->pd->flag & PFIELD_VISIBILITY)) {
+					/* Actual code uses get_collider_cache */
+					dag_add_collision_relations(dag, scene, ob, node, NULL, eff->ob->lay, eModifierType_Collision, NULL, true, "Force Absorption");
 				}
 			}
 		}
 	}
 
-	/* would be nice to have a list of colliders here
-	 * so for now walk all objects in scene check 'same layer rule' */
-	for (base = scene->base.first; base; base = base->next) {
-		if ((base->lay & ob->lay)) {
-			Object *ob1 = base->object;
-			check_and_create_collision_relation(dag, ob, node, ob1, skip_forcefield, no_collision);
-		}
-	}
+	pdEndEffectors(&effectors);
 }
 
 static void build_dag_object(DagForest *dag, DagNode *scenenode, Main *bmain, Scene *scene, Object *ob, int mask)
@@ -643,23 +648,13 @@ static void build_dag_object(DagForest *dag, DagNode *scenenode, Main *bmain, Sc
 		}
 	}
 
-	/* softbody collision  */
+	/* rigidbody force fields  */
 	if ((ob->type == OB_MESH) || (ob->type == OB_CURVE) || (ob->type == OB_LATTICE)) {
-		if (ob->particlesystem.first ||
-		    modifiers_isModifierEnabled(ob, eModifierType_Softbody) ||
-		    modifiers_isModifierEnabled(ob, eModifierType_Cloth) ||
-		    modifiers_isModifierEnabled(ob, eModifierType_DynamicPaint))
-		{
-			dag_add_collision_field_relation(dag, scene, ob, node, 0, false);  /* TODO: use effectorweight->group */
-		}
-		else if (modifiers_isModifierEnabled(ob, eModifierType_Smoke)) {
-			dag_add_collision_field_relation(dag, scene, ob, node, PFIELD_SMOKEFLOW, false);
-		}
-		else if (ob->rigidbody_object) {
-			dag_add_collision_field_relation(dag, scene, ob, node, 0, true);
+		if (ob->rigidbody_object && scene->rigidbody_world) {
+			dag_add_forcefield_relations(dag, scene, ob, node, scene->rigidbody_world->effector_weights, true, 0, "Force Field");
 		}
 	}
-	
+
 	/* object data drivers */
 	if (ob->data) {
 		AnimData *adt = BKE_animdata_from_id((ID *)ob->data);
@@ -763,8 +758,6 @@ static void build_dag_object(DagForest *dag, DagNode *scenenode, Main *bmain, Sc
 			BoidRule *rule = NULL;
 			BoidState *state = NULL;
 			ParticleSettings *part = psys->part;
-			ListBase *effectors = NULL;
-			EffectorCache *eff;
 
 			if (part->adt) {
 				dag_add_driver_relation(part->adt, dag, node, 1);
@@ -803,18 +796,12 @@ static void build_dag_object(DagForest *dag, DagNode *scenenode, Main *bmain, Sc
 				}
 			}
 
-			effectors = pdInitEffectors(scene, ob, psys, part->effector_weights, false);
-
-			if (effectors) {
-				for (eff = effectors->first; eff; eff = eff->next) {
-					if (eff->psys) {
-						node2 = dag_get_node(dag, eff->ob);
-						dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Particle Field");
-					}
-				}
+			if (part->type != PART_HAIR) {
+				/* Actual code uses get_collider_cache */
+				dag_add_collision_relations(dag, scene, ob, node, part->collision_group, ob->lay, eModifierType_Collision, NULL, true, "Particle Collision");
 			}
 
-			pdEndEffectors(&effectors);
+			dag_add_forcefield_relations(dag, scene, ob, node, part->effector_weights, part->type == PART_HAIR, 0, "Particle Force Field");
 
 			if (part->boids) {
 				for (state = part->boids->states.first; state; state = state->next) {
diff --git a/source/blender/blenkernel/intern/effect.c b/source/blender/blenkernel/intern/effect.c
index 5090e46f1fc..7e6897a2858 100644
--- a/source/blender/blenkernel/intern/effect.c
+++ b/source/blender/blenkernel/intern/effect.c
@@ -155,15 +155,20 @@ static EffectorCache *new_effector_cache(Scene *scene, Object *ob, ParticleSyste
 	eff->frame = -1;
 	return eff;
 }
-static void add_object_to_effectors(ListBase **effectors, Scene *scene, EffectorWeights *weights, Object *ob, Object *ob_src)
+static void add_object_to_effectors(ListBase **effectors, Scene *scene, EffectorWeights *weights, Object *ob, Object *ob_src, bool for_simulation)
 {
 	EffectorCache *eff = NULL;
 
-	if ( ob == ob_src || weights->weight[ob->pd->forcefield] == 0.0f )
+	if ( ob == ob_src )
 		return;
 
-	if (ob->pd->shape == PFIELD_SHAPE_POINTS && !ob->derivedFinal )
-		return;
+	if (for_simulation) {
+		if (weights->weight[ob->pd->forcefield] == 0.0f )
+			return;
+
+		if (ob->pd->shape == PFIELD_SHAPE_POINTS && !ob->derivedFinal )
+			return;
+	}
 
 	if (*effectors == NULL)
 		*effectors = MEM_callocN(sizeof(ListBase), "effectors list");
@@ -175,7 +180,7 @@ static void add_object_to_effectors(ListBase **effectors, Scene *scene, Effector
 
 	BLI_addtail(*effectors, eff);
 }
-static void add_particles_to_effectors(ListBase **effectors, Scene *scene, EffectorWeights *weights, Object *ob, ParticleSystem *psys, ParticleSystem *psys_src)
+static void add_particles_to_effectors(ListBase **effectors, Scene *scene, EffectorWeights *weights, Object *ob, ParticleSystem *psys, ParticleSystem *psys_src, bool for_simulation)
 {
 	ParticleSettings *part= psys->part;
 
@@ -185,14 +190,14 @@ static void add_particles_to_effectors(ListBase **effectors, Scene *scene, Effec
 	if ( psys == psys_src && (part->flag & PART_SELF_EFFECT) == 0)
 		return;
 
-	if ( part->pd && part->pd->forcefield && weights->weight[part->pd->forcefield] != 0.0f) {
+	if ( part->pd && part->pd->forcefield && (!for_simulation || weights->weight[part->pd->forcefield] != 0.0f)) {
 		if (*effectors == NULL)
 			*effectors = MEM_callocN(sizeof(ListBase), "effectors list");
 
 		BLI_addtail(*effectors, new_effector_cache(scene, ob, psys, part->pd));
 	}
 
-	if (part->pd2 && part->pd2->forcefield && weights->weight[part->pd2->forcefield] != 0.0f) {
+	if (part->pd2 && part->pd2->forcefield && (!for_simulation || weights->weight[part->pd2->forcefield] != 0.0f)) {
 		if (*effectors == NULL)
 			*effectors = MEM_callocN(sizeof(ListBase), "effectors list");
 
@@ -202,7 +207,7 @@ static void add_particles_to_effectors(ListBase **effectors, Scene *scene, Effec
 
 /* returns ListBase handle with objects taking part in the effecting */
 ListBase *pdInitEffectors(Scene *scene, Object *ob_src, ParticleSystem *psys_src,
-                          EffectorWeights *weights, bool precalc)
+                          EffectorWeights *weights, bool for_simulation)
 {
 	Base *base;
 	unsigned int layer= ob_src->lay;
@@ -214,13 +219,13 @@ ListBase *pdInitEffectors(Scene *scene, Object *ob_src, ParticleSystem *psys_src
 		for (go= weights->group->gobject.first; go; go= go->next) {
 			if ( (go->ob->lay & layer) ) {
 				if ( go->ob->pd && go->ob->pd->forcefield )
-					add_object_to_effectors(&effectors, scene, weights, go->ob, ob_src);
+					add_object_to_effectors(&effectors, scene, weights, go->ob, ob_src, for_simulation);
 
 				if ( go->ob->particlesystem.first ) {
 					ParticleSystem *psys= go->ob->particlesystem.first;
 
 					for ( ; psys; psys=psys->next )
-						add_particles_to_effectors(&effectors, scene, weights, go->ob, psys, psys_src);
+						add_particles_to_effectors(&effectors, scene, weights, go->ob, psys, psys_src, for_simulation);
 				}
 			}
 		}
@@ -229,19 +234,19 @@ ListBase *pdInitEffectors(Scene *scene, Object *ob_src, ParticleSystem *psys_src
 		for (base = scene->base.first; base; base= base->next) {
 			if ( (base->lay & layer) ) {
 				if ( base->object->pd && base->object->pd->forcefield )
-					add_object_to_effectors(&effectors, scene, weights, base->object, ob_src);
+					add_object_to_effectors(&effectors, scene, weights, base->object, ob_src, for_simulation);
 
 				if ( base->object->particlesystem.first ) {
 					ParticleSystem *psys= base->object->particlesystem.first;
 
 					for ( ; psys; psys=psys->next )
-						add_particles_to_effectors(&effectors, scene, weights, base->object, psys, psys_src);
+						add_particles_to_effectors(&effectors, scene, weights, base->object, psys, psys_src, for_simulation);
 				}
 			}
 		}
 	}
 	
-	if (precalc)
+	if (for_simulation)
 		pdPrecalculateEffectors(effectors);
 	
 	return effectors;