Depsgraph: cache effector relations, for performance and stability.

To find all effectors in the scene, we need to loop over all objects.
Doing this during depsgraph evaluation caused crashes because not all
objects are guaranteed to be evaluated yet.

To fix this, we now cache the relations as part of the dependency graph
build. As a bonus this also makes evaluation faster for big scenes,
since looping over all objects for each particle system is slow.

Fixes T55156.

8 files changed, 203 insertions, 48 deletions

diff --git a/source/blender/depsgraph/CMakeLists.txt b/source/blender/depsgraph/CMakeLists.txt
index 8f6eee244f7..0673a3177b7 100644
--- a/source/blender/depsgraph/CMakeLists.txt
+++ b/source/blender/depsgraph/CMakeLists.txt
@@ -67,6 +67,7 @@ set(SRC
 	intern/depsgraph_build.cc
 	intern/depsgraph_debug.cc
 	intern/depsgraph_eval.cc
+	intern/depsgraph_physics.cc
 	intern/depsgraph_query.cc
 	intern/depsgraph_query_foreach.cc
 	intern/depsgraph_query_iter.cc
@@ -76,6 +77,7 @@ set(SRC
 	DEG_depsgraph.h
 	DEG_depsgraph_build.h
 	DEG_depsgraph_debug.h
+	DEG_depsgraph_physics.h
 	DEG_depsgraph_query.h
 
 	intern/builder/deg_builder.h
diff --git a/source/blender/depsgraph/DEG_depsgraph_physics.h b/source/blender/depsgraph/DEG_depsgraph_physics.h
new file mode 100644
index 00000000000..6bffe0c2358
--- /dev/null
+++ b/source/blender/depsgraph/DEG_depsgraph_physics.h
@@ -0,0 +1,51 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2018 Blender Foundation.
+ * All rights reserved.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/depsgraph/DEG_depsgraph_physics.h
+ *  \ingroup depsgraph
+ *
+ * Physics utilities for effectors and collision.
+ */
+
+#ifndef __DEG_DEPSGRAPH_PHYSICS_H__
+#define __DEG_DEPSGRAPH_PHYSICS_H__
+
+#include "DEG_depsgraph.h"
+
+struct Colllection;
+struct Depsgraph;
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* Get effector relations from collection or entire scene during evaluation,
+ * these are created during depsgraph relations building. */
+struct ListBase *DEG_get_effector_relations(const struct Depsgraph *depsgraph,
+                                            struct Collection *collection);
+
+#ifdef __cplusplus
+} /* extern "C" */
+#endif
+
+#endif  /* __DEG_DEPSGRAPH_PHYSICS_H__ */
diff --git a/source/blender/depsgraph/intern/builder/deg_builder_relations.cc b/source/blender/depsgraph/intern/builder/deg_builder_relations.cc
index d36e7eceb88..c9b9cf38cc5 100644
--- a/source/blender/depsgraph/intern/builder/deg_builder_relations.cc
+++ b/source/blender/depsgraph/intern/builder/deg_builder_relations.cc
@@ -333,52 +333,49 @@ void DepsgraphRelationBuilder::add_forcefield_relations(
         bool add_absorption,
         const char *name)
 {
-	::Depsgraph *depsgraph = reinterpret_cast<::Depsgraph*>(graph_);
-	ListBase *effectors = pdInitEffectors(depsgraph, scene, object, psys, eff, false);
-	if (effectors == NULL) {
-		return;
-	}
-	LISTBASE_FOREACH (EffectorCache *, eff, effectors) {
-		if (eff->ob != object) {
-			ComponentKey eff_key(&eff->ob->id, DEG_NODE_TYPE_TRANSFORM);
+	ListBase *relations = deg_build_effector_relations(graph_, eff->group);
+
+	LISTBASE_FOREACH (EffectorRelation *, relation, relations) {
+		if (relation->ob != object) {
+			ComponentKey eff_key(&relation->ob->id, DEG_NODE_TYPE_TRANSFORM);
 			add_relation(eff_key, key, name);
+
+			if (relation->pd->forcefield == PFIELD_SMOKEFLOW && relation->pd->f_source) {
+				ComponentKey trf_key(&relation->pd->f_source->id,
+				                     DEG_NODE_TYPE_TRANSFORM);
+				add_relation(trf_key, key, "Smoke Force Domain");
+				ComponentKey eff_key(&relation->pd->f_source->id,
+				                     DEG_NODE_TYPE_GEOMETRY);
+				add_relation(eff_key, key, "Smoke Force Domain");
+			}
+			if (add_absorption && (relation->pd->flag & PFIELD_VISIBILITY)) {
+				add_collision_relations(key,
+				                        scene,
+				                        object,
+				                        NULL,
+				                        true,
+				                        "Force Absorption");
+			}
 		}
-		if (eff->psys != NULL) {
-			if (eff->ob != object) {
-				ComponentKey eff_key(&eff->ob->id, DEG_NODE_TYPE_EVAL_PARTICLES);
+		if (relation->psys) {
+			if (relation->ob != object) {
+				ComponentKey eff_key(&relation->ob->id, DEG_NODE_TYPE_EVAL_PARTICLES);
 				add_relation(eff_key, key, name);
 				/* TODO: remove this when/if EVAL_PARTICLES is sufficient
 				 * for up to date particles.
 				 */
-				ComponentKey mod_key(&eff->ob->id, DEG_NODE_TYPE_GEOMETRY);
+				ComponentKey mod_key(&relation->ob->id, DEG_NODE_TYPE_GEOMETRY);
 				add_relation(mod_key, key, name);
 			}
-			else if (eff->psys != psys) {
-				OperationKey eff_key(&eff->ob->id,
+			else if (relation->psys != psys) {
+				OperationKey eff_key(&relation->ob->id,
 				                     DEG_NODE_TYPE_EVAL_PARTICLES,
 				                     DEG_OPCODE_PARTICLE_SYSTEM_EVAL,
-				                     eff->psys->name);
+				                     relation->psys->name);
 				add_relation(eff_key, key, name);
 			}
 		}
-		if (eff->pd->forcefield == PFIELD_SMOKEFLOW && eff->pd->f_source) {
-			ComponentKey trf_key(&eff->pd->f_source->id,
-			                     DEG_NODE_TYPE_TRANSFORM);
-			add_relation(trf_key, key, "Smoke Force Domain");
-			ComponentKey eff_key(&eff->pd->f_source->id,
-			                     DEG_NODE_TYPE_GEOMETRY);
-			add_relation(eff_key, key, "Smoke Force Domain");
-		}
-		if (add_absorption && (eff->pd->flag & PFIELD_VISIBILITY)) {
-			add_collision_relations(key,
-			                        scene,
-			                        object,
-			                        NULL,
-			                        true,
-			                        "Force Absorption");
-		}
 	}
-	pdEndEffectors(&effectors);
 }
 
 Depsgraph *DepsgraphRelationBuilder::getGraph()
diff --git a/source/blender/depsgraph/intern/depsgraph.cc b/source/blender/depsgraph/intern/depsgraph.cc
index 16427d3eb59..5b7cf3d5a16 100644
--- a/source/blender/depsgraph/intern/depsgraph.cc
+++ b/source/blender/depsgraph/intern/depsgraph.cc
@@ -93,7 +93,8 @@ Depsgraph::Depsgraph(Scene *scene,
     mode(mode),
     ctime(BKE_scene_frame_get(scene)),
     scene_cow(NULL),
-    is_active(false)
+    is_active(false),
+	effector_relations(NULL)
 {
 	BLI_spin_init(&lock);
 	id_hash = BLI_ghash_ptr_new("Depsgraph id hash");
@@ -360,6 +361,8 @@ void Depsgraph::clear_id_nodes()
 	/* Clear containers. */
 	BLI_ghash_clear(id_hash, NULL, NULL);
 	id_nodes.clear();
+	/* Clear physics relation caches. */
+	deg_clear_physics_relations(this);
 }
 
 /* Add new relationship between two nodes. */
diff --git a/source/blender/depsgraph/intern/depsgraph.h b/source/blender/depsgraph/intern/depsgraph.h
index a69be39c50b..a27af42e7b9 100644
--- a/source/blender/depsgraph/intern/depsgraph.h
+++ b/source/blender/depsgraph/intern/depsgraph.h
@@ -226,6 +226,10 @@ struct Depsgraph {
 	/* NITE: Corresponds to G_DEBUG_DEPSGRAPH_* flags. */
 	int debug_flags;
 	string debug_name;
+
+	/* Cached list of effectors for collections and the scene created
+	 * along with relations, for fast lookup during evaluation. */
+	GHash *effector_relations;
 };
 
 }  // namespace DEG
diff --git a/source/blender/depsgraph/intern/depsgraph_build.cc b/source/blender/depsgraph/intern/depsgraph_build.cc
index 9c03e8c4ca3..da64478404b 100644
--- a/source/blender/depsgraph/intern/depsgraph_build.cc
+++ b/source/blender/depsgraph/intern/depsgraph_build.cc
@@ -357,31 +357,30 @@ void DEG_add_forcefield_relations(DepsNodeHandle *handle,
                                   const char *name)
 {
 	Depsgraph *depsgraph = DEG_get_graph_from_handle(handle);
-	ListBase *effectors = pdInitEffectors(depsgraph, scene, object, NULL, effector_weights, false);
-	if (effectors == NULL) {
-		return;
-	}
-	for (EffectorCache *eff = (EffectorCache*)effectors->first; eff; eff = eff->next) {
-		if (eff->ob != object && eff->pd->forcefield != skip_forcefield) {
-			DEG_add_object_relation(handle, eff->ob, DEG_OB_COMP_TRANSFORM, name);
-			if (eff->psys) {
-				DEG_add_object_relation(handle, eff->ob, DEG_OB_COMP_EVAL_PARTICLES, name);
+	DEG::Depsgraph *deg_graph = (DEG::Depsgraph *)depsgraph;
+	ListBase *relations = deg_build_effector_relations(deg_graph, effector_weights->group);
+
+	LISTBASE_FOREACH (EffectorRelation *, relation, relations) {
+		if (relation->ob != object && relation->pd->forcefield != skip_forcefield) {
+			DEG_add_object_relation(handle, relation->ob, DEG_OB_COMP_TRANSFORM, name);
+			if (relation->psys) {
+				DEG_add_object_relation(handle, relation->ob, DEG_OB_COMP_EVAL_PARTICLES, name);
 				/* TODO: remove this when/if EVAL_PARTICLES is sufficient
 				 * for up to date particles.
 				 */
-				DEG_add_object_relation(handle, eff->ob, DEG_OB_COMP_GEOMETRY, name);
+				DEG_add_object_relation(handle, relation->ob, DEG_OB_COMP_GEOMETRY, name);
 			}
-			if (eff->pd->forcefield == PFIELD_SMOKEFLOW && eff->pd->f_source) {
+			if (relation->pd->forcefield == PFIELD_SMOKEFLOW && relation->pd->f_source) {
 				DEG_add_object_relation(handle,
-				                        eff->pd->f_source,
+				                        relation->pd->f_source,
 				                        DEG_OB_COMP_TRANSFORM,
 				                        "Smoke Force Domain");
 				DEG_add_object_relation(handle,
-				                        eff->pd->f_source,
+				                        relation->pd->f_source,
 				                        DEG_OB_COMP_GEOMETRY,
 				                        "Smoke Force Domain");
 			}
-			if (add_absorption && (eff->pd->flag & PFIELD_VISIBILITY)) {
+			if (add_absorption && (relation->pd->flag & PFIELD_VISIBILITY)) {
 				DEG_add_collision_relations(handle,
 				                            scene,
 				                            object,
@@ -393,5 +392,4 @@ void DEG_add_forcefield_relations(DepsNodeHandle *handle,
 			}
 		}
 	}
-	pdEndEffectors(&effectors);
 }
diff --git a/source/blender/depsgraph/intern/depsgraph_intern.h b/source/blender/depsgraph/intern/depsgraph_intern.h
index 526cecde457..cd5508a4088 100644
--- a/source/blender/depsgraph/intern/depsgraph_intern.h
+++ b/source/blender/depsgraph/intern/depsgraph_intern.h
@@ -50,6 +50,7 @@ extern "C" {
 
 struct DEGEditorUpdateContext;
 struct Collection;
+struct ListBase;
 struct Main;
 struct Scene;
 
@@ -139,4 +140,9 @@ bool deg_terminal_do_color(void);
 string deg_color_for_pointer(const void *pointer);
 string deg_color_end(void);
 
+/* Physics Utilities -------------------------------------------------- */
+
+struct ListBase *deg_build_effector_relations(Depsgraph *graph, struct Collection *collection);
+void deg_clear_physics_relations(Depsgraph *graph);
+
 }  // namespace DEG
diff --git a/source/blender/depsgraph/intern/depsgraph_physics.cc b/source/blender/depsgraph/intern/depsgraph_physics.cc
new file mode 100644
index 00000000000..d26ba845dd5
--- /dev/null
+++ b/source/blender/depsgraph/intern/depsgraph_physics.cc
@@ -0,0 +1,94 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2018 Blender Foundation.
+ * All rights reserved.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/depsgraph/intern/depsgraph_physics.cc
+ *  \ingroup depsgraph
+ *
+ * Physics utilities for effectors and collision.
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_compiler_compat.h"
+#include "BLI_ghash.h"
+
+extern "C" {
+#include "BKE_effect.h"
+} /* extern "C" */
+
+#include "DNA_group_types.h"
+
+#include "DEG_depsgraph_physics.h"
+
+#include "depsgraph.h"
+#include "depsgraph_intern.h"
+
+/************************ Public API *************************/
+
+ListBase *DEG_get_effector_relations(const Depsgraph *graph,
+                                     Collection *collection)
+{
+	const DEG::Depsgraph *deg_graph = reinterpret_cast<const DEG::Depsgraph *>(graph);
+	if (deg_graph->effector_relations == NULL) {
+		return NULL;
+	}
+
+	return (ListBase*)BLI_ghash_lookup(deg_graph->effector_relations, collection);
+}
+
+/*********************** Internal API ************************/
+
+namespace DEG
+{
+
+ListBase *deg_build_effector_relations(Depsgraph *graph,
+                                       Collection *collection)
+{
+	if (graph->effector_relations == NULL) {
+		graph->effector_relations = BLI_ghash_ptr_new("Depsgraph effector relations hash");
+	}
+
+	ListBase *relations = reinterpret_cast<ListBase*>(BLI_ghash_lookup(graph->effector_relations, collection));
+	if (relations == NULL) {
+		::Depsgraph *depsgraph = reinterpret_cast<::Depsgraph*>(graph);
+		relations = BKE_effector_relations_create(depsgraph, graph->view_layer, collection);
+		BLI_ghash_insert(graph->effector_relations, collection, relations);
+	}
+
+	return relations;
+}
+
+static void free_effector_relations(void *value)
+{
+	BKE_effector_relations_free(reinterpret_cast<ListBase*>(value));
+}
+
+void deg_clear_physics_relations(Depsgraph *graph)
+{
+	if (graph->effector_relations) {
+		BLI_ghash_free(graph->effector_relations, NULL, free_effector_relations);
+		graph->effector_relations = NULL;
+	}
+}
+
+}