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

4 files changed, 74 insertions, 228 deletions

diff --git a/source/blender/modifiers/intern/MOD_cloth.c b/source/blender/modifiers/intern/MOD_cloth.c
index 6cc2f097be8..d15a6fcb1c8 100644
--- a/source/blender/modifiers/intern/MOD_cloth.c
+++ b/source/blender/modifiers/intern/MOD_cloth.c
@@ -123,19 +123,11 @@ static void updateDepgraph(ModifierData *md, DagForest *forest,
 {
 	ClothModifierData *clmd = (ClothModifierData *) md;
 	
-	Base *base;
-	
 	if (clmd) {
-		for (base = scene->base.first; base; base = base->next) {
-			Object *ob1 = base->object;
-			if (ob1 != ob) {
-				CollisionModifierData *coll_clmd = (CollisionModifierData *)modifiers_findByType(ob1, eModifierType_Collision);
-				if (coll_clmd) {
-					DagNode *curNode = dag_get_node(forest, ob1);
-					dag_add_relation(forest, curNode, obNode, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Cloth Collision");
-				}
-			}
-		}
+		/* Actual code uses get_collisionobjects */
+		dag_add_collision_relations(forest, scene, ob, obNode, clmd->coll_parms->group, ob->lay|scene->lay, eModifierType_Collision, NULL, true, "Cloth Collision");
+
+		dag_add_forcefield_relations(forest, scene, ob, obNode, clmd->sim_parms->effector_weights, true, 0, "Cloth Field");
 	}
 }
 
@@ -147,16 +139,10 @@ static void updateDepsgraph(ModifierData *md,
 {
 	ClothModifierData *clmd = (ClothModifierData *)md;
 	if (clmd != NULL) {
-		Base *base;
-		for (base = scene->base.first; base; base = base->next) {
-			Object *ob1 = base->object;
-			if (ob1 != ob) {
-				CollisionModifierData *coll_clmd = (CollisionModifierData *)modifiers_findByType(ob1, eModifierType_Collision);
-				if (coll_clmd) {
-					DEG_add_object_relation(node, ob1, DEG_OB_COMP_TRANSFORM, "Cloth Modifier");
-				}
-			}
-		}
+		/* Actual code uses get_collisionobjects */
+		DEG_add_collision_relations(node, scene, ob, clmd->coll_parms->group, ob->lay|scene->lay, eModifierType_Collision, NULL, true, "Cloth Collision");
+
+		DEG_add_forcefield_relations(node, scene, ob, clmd->sim_parms->effector_weights, true, 0, "Cloth Field");
 	}
 }
 
diff --git a/source/blender/modifiers/intern/MOD_dynamicpaint.c b/source/blender/modifiers/intern/MOD_dynamicpaint.c
index edf959f42c6..bde20e56748 100644
--- a/source/blender/modifiers/intern/MOD_dynamicpaint.c
+++ b/source/blender/modifiers/intern/MOD_dynamicpaint.c
@@ -114,6 +114,11 @@ static DerivedMesh *applyModifier(ModifierData *md, Object *ob,
 	return dm;
 }
 
+static bool is_brush_cb(Object *UNUSED(ob), ModifierData *pmd)
+{
+	return ((DynamicPaintModifierData*)pmd)->brush != NULL;
+}
+
 static void updateDepgraph(ModifierData *md, DagForest *forest,
                            struct Main *UNUSED(bmain),
                            struct Scene *scene,
@@ -124,16 +129,13 @@ static void updateDepgraph(ModifierData *md, DagForest *forest,
 
 	/* add relation from canvases to all brush objects */
 	if (pmd && pmd->canvas) {
-		Base *base = scene->base.first;
-
-		for (; base; base = base->next) {
-			DynamicPaintModifierData *pmd2 =
-			        (DynamicPaintModifierData *)modifiers_findByType(base->object, eModifierType_DynamicPaint);
-
-			if (pmd2 && pmd2->brush && ob != base->object) {
-				DagNode *brushNode = dag_get_node(forest, base->object);
-				dag_add_relation(forest, brushNode, obNode, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Dynamic Paint Brush");
+		for (DynamicPaintSurface *surface = pmd->canvas->surfaces.first; surface; surface = surface->next) {
+			if (surface->effect & MOD_DPAINT_EFFECT_DO_DRIP) {
+				dag_add_forcefield_relations(forest, scene, ob, obNode, surface->effector_weights, true, 0, "Dynamic Paint Field");
 			}
+
+			/* Actual code uses custom loop over group/scene without layer checks in dynamicPaint_doStep */
+			dag_add_collision_relations(forest, scene, ob, obNode, surface->brush_group, -1, eModifierType_DynamicPaint, is_brush_cb, false, "Dynamic Paint Brush");
 		}
 	}
 }
@@ -147,13 +149,13 @@ static void updateDepsgraph(ModifierData *md,
 	DynamicPaintModifierData *pmd = (DynamicPaintModifierData *)md;
 	/* Add relation from canvases to all brush objects. */
 	if (pmd->canvas != NULL) {
-		Base *base = scene->base.first;
-		for (; base; base = base->next) {
-			DynamicPaintModifierData *pmd2 =
-			        (DynamicPaintModifierData *)modifiers_findByType(base->object, eModifierType_DynamicPaint);
-			if (pmd2 && pmd2->brush && ob != base->object) {
-				DEG_add_object_relation(node, base->object, DEG_OB_COMP_TRANSFORM, "Dynamic Paint Brush");
+		for (DynamicPaintSurface *surface = pmd->canvas->surfaces.first; surface; surface = surface->next) {
+			if (surface->effect & MOD_DPAINT_EFFECT_DO_DRIP) {
+				DEG_add_forcefield_relations(node, scene, ob, surface->effector_weights, true, 0, "Dynamic Paint Field");
 			}
+
+			/* Actual code uses custom loop over group/scene without layer checks in dynamicPaint_doStep */
+			DEG_add_collision_relations(node, scene, ob, surface->brush_group, -1, eModifierType_DynamicPaint, is_brush_cb, false, "Dynamic Paint Brush");
 		}
 	}
 }
diff --git a/source/blender/modifiers/intern/MOD_smoke.c b/source/blender/modifiers/intern/MOD_smoke.c
index 237d4cc6718..f04d7432a8f 100644
--- a/source/blender/modifiers/intern/MOD_smoke.c
+++ b/source/blender/modifiers/intern/MOD_smoke.c
@@ -117,219 +117,48 @@ static bool dependsOnTime(ModifierData *UNUSED(md))
 	return true;
 }
 
-static void update_depsgraph_flow_coll_object(DagForest *forest,
-                                              DagNode *obNode,
-                                              Object *object2)
+static bool is_flow_cb(Object *UNUSED(ob), ModifierData *md)
 {
-	SmokeModifierData *smd;
-	if ((object2->id.tag & LIB_TAG_DOIT) == 0) {
-		return;
-	}
-	object2->id.tag &= ~LIB_TAG_DOIT;
-	smd = (SmokeModifierData *)modifiers_findByType(object2, eModifierType_Smoke);
-	if (smd && (((smd->type & MOD_SMOKE_TYPE_FLOW) && smd->flow) ||
-	            ((smd->type & MOD_SMOKE_TYPE_COLL) && smd->coll)))
-	{
-		DagNode *curNode = dag_get_node(forest, object2);
-		dag_add_relation(forest, curNode, obNode, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Smoke Flow/Coll");
-	}
-	if ((object2->transflag & OB_DUPLIGROUP) && object2->dup_group) {
-		GroupObject *go;
-		for (go = object2->dup_group->gobject.first;
-		     go != NULL;
-		     go = go->next)
-		{
-			if (go->ob == NULL) {
-				continue;
-			}
-			update_depsgraph_flow_coll_object(forest, obNode, go->ob);
-		}
-	}
+	SmokeModifierData *smd = (SmokeModifierData *) md;
+	return (smd->type & MOD_SMOKE_TYPE_FLOW) && smd->flow;
 }
 
-static void update_depsgraph_field_source_object(DagForest *forest,
-                                                 DagNode *obNode,
-                                                 Object *object,
-                                                 Object *object2)
+static bool is_coll_cb(Object *UNUSED(ob), ModifierData *md)
 {
-	if ((object2->id.tag & LIB_TAG_DOIT) == 0) {
-		return;
-	}
-	object2->id.tag &= ~LIB_TAG_DOIT;
-	if (object2->pd && object2->pd->forcefield == PFIELD_SMOKEFLOW && object2->pd->f_source == object) {
-		DagNode *node2 = dag_get_node(forest, object2);
-		dag_add_relation(forest, obNode, node2, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Field Source Object");
-	}
-	if ((object2->transflag & OB_DUPLIGROUP) && object2->dup_group) {
-		GroupObject *go;
-		for (go = object2->dup_group->gobject.first;
-		     go != NULL;
-		     go = go->next)
-		{
-			if (go->ob == NULL) {
-				continue;
-			}
-			update_depsgraph_field_source_object(forest, obNode, object, go->ob);
-		}
-	}
+	SmokeModifierData *smd = (SmokeModifierData *) md;
+	return (smd->type & MOD_SMOKE_TYPE_COLL) && smd->coll;
 }
 
 static void updateDepgraph(ModifierData *md, DagForest *forest,
-                           struct Main *bmain,
+                           struct Main *UNUSED(bmain),
                            struct Scene *scene, struct Object *ob,
                            DagNode *obNode)
 {
 	SmokeModifierData *smd = (SmokeModifierData *) md;
-	Base *base;
 
 	if (smd && (smd->type & MOD_SMOKE_TYPE_DOMAIN) && smd->domain) {
-		if (smd->domain->fluid_group || smd->domain->coll_group) {
-			GroupObject *go = NULL;
-			
-			if (smd->domain->fluid_group)
-				for (go = smd->domain->fluid_group->gobject.first; go; go = go->next) {
-					if (go->ob) {
-						SmokeModifierData *smd2 = (SmokeModifierData *)modifiers_findByType(go->ob, eModifierType_Smoke);
-						
-						/* check for initialized smoke object */
-						if (smd2 && (smd2->type & MOD_SMOKE_TYPE_FLOW) && smd2->flow) {
-							DagNode *curNode = dag_get_node(forest, go->ob);
-							dag_add_relation(forest, curNode, obNode, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Smoke Flow");
-						}
-					}
-				}
-
-			if (smd->domain->coll_group)
-				for (go = smd->domain->coll_group->gobject.first; go; go = go->next) {
-					if (go->ob) {
-						SmokeModifierData *smd2 = (SmokeModifierData *)modifiers_findByType(go->ob, eModifierType_Smoke);
-						
-						/* check for initialized smoke object */
-						if (smd2 && (smd2->type & MOD_SMOKE_TYPE_COLL) && smd2->coll) {
-							DagNode *curNode = dag_get_node(forest, go->ob);
-							dag_add_relation(forest, curNode, obNode, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Smoke Coll");
-						}
-					}
-				}
-		}
-		else {
-			BKE_main_id_tag_listbase(&bmain->object, LIB_TAG_DOIT, true);
-			base = scene->base.first;
-			for (; base; base = base->next) {
-				update_depsgraph_flow_coll_object(forest, obNode, base->object);
-			}
-		}
-		/* add relation to all "smoke flow" force fields */
-		base = scene->base.first;
-		BKE_main_id_tag_listbase(&bmain->object, LIB_TAG_DOIT, true);
-		for (; base; base = base->next) {
-			update_depsgraph_field_source_object(forest, obNode, ob, base->object);
-		}
-	}
-}
+		/* Actual code uses get_collisionobjects */
+		dag_add_collision_relations(forest, scene, ob, obNode, smd->domain->fluid_group, ob->lay|scene->lay, eModifierType_Smoke, is_flow_cb, true, "Smoke Flow");
+		dag_add_collision_relations(forest, scene, ob, obNode, smd->domain->coll_group, ob->lay|scene->lay, eModifierType_Smoke, is_coll_cb, true, "Smoke Coll");
 
-static void update_depsgraph_flow_coll_object_new(struct DepsNodeHandle *node,
-                                                  Object *object2)
-{
-	SmokeModifierData *smd;
-	if ((object2->id.tag & LIB_TAG_DOIT) == 0) {
-		return;
-	}
-	object2->id.tag &= ~LIB_TAG_DOIT;
-	smd = (SmokeModifierData *)modifiers_findByType(object2, eModifierType_Smoke);
-	if (smd && (((smd->type & MOD_SMOKE_TYPE_FLOW) && smd->flow) ||
-	            ((smd->type & MOD_SMOKE_TYPE_COLL) && smd->coll)))
-	{
-		DEG_add_object_relation(node, object2, DEG_OB_COMP_TRANSFORM, "Smoke Flow/Coll");
-		DEG_add_object_relation(node, object2, DEG_OB_COMP_GEOMETRY, "Smoke Flow/Coll");
-	}
-	if ((object2->transflag & OB_DUPLIGROUP) && object2->dup_group) {
-		GroupObject *go;
-		for (go = object2->dup_group->gobject.first;
-		     go != NULL;
-		     go = go->next)
-		{
-			if (go->ob == NULL) {
-				continue;
-			}
-			update_depsgraph_flow_coll_object_new(node, go->ob);
-		}
-	}
-}
-
-static void update_depsgraph_field_source_object_new(struct DepsNodeHandle *node,
-                                                     Object *object,
-                                                     Object *object2)
-{
-	if ((object2->id.tag & LIB_TAG_DOIT) == 0) {
-		return;
-	}
-	object2->id.tag &= ~LIB_TAG_DOIT;
-	if (object2->pd && object2->pd->forcefield == PFIELD_SMOKEFLOW && object2->pd->f_source == object) {
-		DEG_add_object_relation(node, object2, DEG_OB_COMP_TRANSFORM, "Field Source Object");
-		DEG_add_object_relation(node, object2, DEG_OB_COMP_GEOMETRY, "Field Source Object");
-	}
-	if ((object2->transflag & OB_DUPLIGROUP) && object2->dup_group) {
-		GroupObject *go;
-		for (go = object2->dup_group->gobject.first;
-		     go != NULL;
-		     go = go->next)
-		{
-			if (go->ob == NULL) {
-				continue;
-			}
-			update_depsgraph_field_source_object_new(node, object, go->ob);
-		}
+		dag_add_forcefield_relations(forest, scene, ob, obNode, smd->domain->effector_weights, true, PFIELD_SMOKEFLOW, "Smoke Force Field");
 	}
 }
 
 static void updateDepsgraph(ModifierData *md,
-                            struct Main *bmain,
+                            struct Main *UNUSED(bmain),
                             struct Scene *scene,
                             Object *ob,
                             struct DepsNodeHandle *node)
 {
 	SmokeModifierData *smd = (SmokeModifierData *)md;
-	Base *base;
+
 	if (smd && (smd->type & MOD_SMOKE_TYPE_DOMAIN) && smd->domain) {
-		if (smd->domain->fluid_group || smd->domain->coll_group) {
-			GroupObject *go = NULL;
-			if (smd->domain->fluid_group != NULL) {
-				for (go = smd->domain->fluid_group->gobject.first; go; go = go->next) {
-					if (go->ob != NULL) {
-						SmokeModifierData *smd2 = (SmokeModifierData *)modifiers_findByType(go->ob, eModifierType_Smoke);
-						/* Check for initialized smoke object. */
-						if (smd2 && (smd2->type & MOD_SMOKE_TYPE_FLOW) && smd2->flow) {
-							DEG_add_object_relation(node, go->ob, DEG_OB_COMP_TRANSFORM, "Smoke Flow");
-						}
-					}
-				}
-			}
-			if (smd->domain->coll_group != NULL) {
-				for (go = smd->domain->coll_group->gobject.first; go; go = go->next) {
-					if (go->ob != NULL) {
-						SmokeModifierData *smd2 = (SmokeModifierData *)modifiers_findByType(go->ob, eModifierType_Smoke);
-						/* Check for initialized smoke object. */
-						if (smd2 && (smd2->type & MOD_SMOKE_TYPE_COLL) && smd2->coll) {
-							DEG_add_object_relation(node, go->ob, DEG_OB_COMP_TRANSFORM, "Smoke Coll");
-						}
-					}
-				}
-			}
-		}
-		else {
-			BKE_main_id_tag_listbase(&bmain->object, LIB_TAG_DOIT, true);
-			base = scene->base.first;
-			for (; base; base = base->next) {
-				update_depsgraph_flow_coll_object_new(node, base->object);
-			}
-		}
-		/* add relation to all "smoke flow" force fields */
-		base = scene->base.first;
-		BKE_main_id_tag_listbase(&bmain->object, LIB_TAG_DOIT, true);
-		for (; base; base = base->next) {
-			update_depsgraph_field_source_object_new(node, ob, base->object);
-		}
+		/* Actual code uses get_collisionobjects */
+		DEG_add_collision_relations(node, scene, ob, smd->domain->fluid_group, ob->lay|scene->lay, eModifierType_Smoke, is_flow_cb, true, "Smoke Flow");
+		DEG_add_collision_relations(node, scene, ob, smd->domain->coll_group, ob->lay|scene->lay, eModifierType_Smoke, is_coll_cb, true, "Smoke Coll");
+
+		DEG_add_forcefield_relations(node, scene, ob, smd->domain->effector_weights, true, PFIELD_SMOKEFLOW, "Smoke Force Field");
 	}
 }
 
diff --git a/source/blender/modifiers/intern/MOD_softbody.c b/source/blender/modifiers/intern/MOD_softbody.c
index 98a1412d0c6..17adc7f1520 100644
--- a/source/blender/modifiers/intern/MOD_softbody.c
+++ b/source/blender/modifiers/intern/MOD_softbody.c
@@ -35,6 +35,7 @@
 #include <stdio.h>
 
 #include "DNA_scene_types.h"
+#include "DNA_object_force.h"
 
 #include "BLI_utildefines.h"
 
@@ -42,6 +43,9 @@
 #include "BKE_particle.h"
 #include "BKE_softbody.h"
 
+#include "depsgraph_private.h"
+#include "DEG_depsgraph_build.h"
+
 #include "MOD_modifiertypes.h"
 
 static void deformVerts(ModifierData *md, Object *ob,
@@ -58,6 +62,31 @@ static bool dependsOnTime(ModifierData *UNUSED(md))
 	return true;
 }
 
+static void updateDepgraph(ModifierData *UNUSED(md), DagForest *forest,
+                           struct Main *UNUSED(bmain),
+                           Scene *scene, Object *ob, DagNode *obNode)
+{
+	if (ob->soft) {
+		/* Actual code uses ccd_build_deflector_hash */
+		dag_add_collision_relations(forest, scene, ob, obNode, ob->soft->collision_group, ob->lay, eModifierType_Collision, NULL, false, "Softbody Collision");
+
+		dag_add_forcefield_relations(forest, scene, ob, obNode, ob->soft->effector_weights, true, 0, "Softbody Field");
+	}
+}
+
+static void updateDepsgraph(ModifierData *UNUSED(md),
+                            struct Main *UNUSED(bmain),
+                            struct Scene *scene,
+                            Object *ob,
+                            struct DepsNodeHandle *node)
+{
+	if (ob->soft) {
+		/* Actual code uses ccd_build_deflector_hash */
+		DEG_add_collision_relations(node, scene, ob, ob->soft->collision_group, ob->lay, eModifierType_Collision, NULL, false, "Softbody Collision");
+
+		DEG_add_forcefield_relations(node, scene, ob, ob->soft->effector_weights, true, 0, "Softbody Field");
+	}
+}
 
 ModifierTypeInfo modifierType_Softbody = {
 	/* name */              "Softbody",
@@ -80,8 +109,8 @@ ModifierTypeInfo modifierType_Softbody = {
 	/* requiredDataMask */  NULL,
 	/* freeData */          NULL,
 	/* isDisabled */        NULL,
-	/* updateDepgraph */    NULL,
-	/* updateDepsgraph */   NULL,
+	/* updateDepgraph */    updateDepgraph,
+	/* updateDepsgraph */   updateDepsgraph,
 	/* dependsOnTime */     dependsOnTime,
 	/* dependsOnNormals */	NULL,
 	/* foreachObjectLink */ NULL,