Depsgraph: Comb code to a better state all over
[blender.git] / source / blender / depsgraph / intern / depsgraph_query_filter.cc
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2018 Blender Foundation.
19  * All rights reserved.
20  *
21  * Original Author: Joshua Leung
22  * Contributor(s): None Yet
23  *
24  * ***** END GPL LICENSE BLOCK *****
25  */
26
27 /** \file blender/depsgraph/intern/depsgraph_query_filter.cc
28  *  \ingroup depsgraph
29  *
30  * Implementation of Graph Filtering API
31  */
32
33 #include "MEM_guardedalloc.h"
34
35 extern "C" {
36 #include <string.h> // XXX: memcpy
37
38 #include "BLI_utildefines.h"
39 #include "BKE_idcode.h"
40 #include "BKE_main.h"
41 #include "BLI_listbase.h"
42 #include "BLI_ghash.h"
43
44 #include "BKE_action.h" // XXX: BKE_pose_channel_from_name
45 } /* extern "C" */
46
47 #include "DNA_object_types.h"
48 #include "DNA_scene_types.h"
49
50 #include "RNA_access.h"
51
52 #include "DEG_depsgraph.h"
53 #include "DEG_depsgraph_query.h"
54 #include "DEG_depsgraph_debug.h"
55
56 #include "intern/eval/deg_eval_copy_on_write.h"
57
58 #include "intern/depsgraph.h"
59 #include "intern/depsgraph_type.h"
60
61 #include "intern/node/deg_node.h"
62 #include "intern/node/deg_node_component.h"
63 #include "intern/node/deg_node_id.h"
64 #include "intern/node/deg_node_operation.h"
65
66
67 /* *************************************************** */
68 /* Graph Filtering Internals */
69
70 namespace DEG {
71
72 /* UserData for deg_add_retained_id_cb */
73 struct RetainedIdUserData {
74         DEG_FilterQuery *query;
75         GSet *set;
76 };
77
78 /* Helper for DEG_foreach_ancestor_id()
79  * Keep track of all ID's encountered in a set
80  */
81 static void deg_add_retained_id_cb(ID *id, void *user_data)
82 {
83         RetainedIdUserData *data = (RetainedIdUserData *)user_data;
84         BLI_gset_add(data->set, (void *)id);
85 }
86
87 /* ------------------------------------------- */
88
89 /* Remove relations pointing to the given OperationNode */
90 /* TODO: Make this part of OperationNode? */
91 static void deg_unlink_opnode(Depsgraph *graph, OperationNode *op_node)
92 {
93         vector<Relation *> all_links;
94
95         /* Collect all inlinks to this operation */
96         for (Relation *rel : op_node->inlinks) {
97                 all_links.push_back(rel);
98         }
99         /* Collect all outlinks from this operation */
100         for (Relation *rel : op_node->outlinks) {
101                 all_links.push_back(rel);
102         }
103
104         /* Delete all collected relations */
105         for (Relation *rel : all_links) {
106                 rel->unlink();
107                 OBJECT_GUARDED_DELETE(rel, Relation);
108         }
109
110         /* Remove from entry tags */
111         if (BLI_gset_haskey(graph->entry_tags, op_node)) {
112                 BLI_gset_remove(graph->entry_tags, op_node, NULL);
113         }
114 }
115
116 /* Remove every ID Node (and its associated subnodes, COW data) */
117 static void deg_filter_remove_unwanted_ids(Depsgraph *graph, GSet *retained_ids)
118 {
119         /* 1) First pass over ID nodes + their operations
120          * - Identify and tag ID's (via "custom_flags = 1") to be removed
121          * - Remove all links to/from operations that will be removed. */
122         for (IDNode *id_node : graph->id_nodes) {
123                 id_node->custom_flags = !BLI_gset_haskey(retained_ids, (void *)id_node->id_orig);
124                 if (id_node->custom_flags) {
125                         GHASH_FOREACH_BEGIN(ComponentNode *, comp_node, id_node->components)
126                         {
127                                 for (OperationNode *op_node : comp_node->operations) {
128                                         deg_unlink_opnode(graph, op_node);
129                                 }
130                         }
131                         GHASH_FOREACH_END();
132                 }
133         }
134
135         /* 2) Remove unwanted operations from graph->operations */
136         for (Depsgraph::OperationNodes::iterator it_opnode = graph->operations.begin();
137              it_opnode != graph->operations.end();
138              )
139         {
140                 OperationNode *op_node = *it_opnode;
141                 IDNode *id_node = op_node->owner->owner;
142                 if (id_node->custom_flags) {
143                         it_opnode = graph->operations.erase(it_opnode);
144                 }
145                 else {
146                         ++it_opnode;
147                 }
148         }
149
150         /* Free ID nodes that are no longer wanted
151          *
152          * This is loosely based on Depsgraph::clear_id_nodes().
153          * However, we don't worry about the conditional freeing for physics
154          * stuff, since it's rarely needed currently. */
155         for (Depsgraph::IDDepsNodes::iterator it_id = graph->id_nodes.begin();
156              it_id != graph->id_nodes.end();
157              )
158         {
159                 IDNode *id_node = *it_id;
160                 ID *id = id_node->id_orig;
161
162                 if (id_node->custom_flags) {
163                         /* Destroy node data, then remove from collections, and free */
164                         id_node->destroy();
165
166                         BLI_ghash_remove(graph->id_hash, id, NULL, NULL);
167                         it_id = graph->id_nodes.erase(it_id);
168
169                         OBJECT_GUARDED_DELETE(id_node, IDNode);
170                 }
171                 else {
172                         /* This node has not been marked for deletion. Increment iterator */
173                         ++it_id;
174                 }
175         }
176 }
177
178 } //namespace DEG
179
180 /* *************************************************** */
181 /* Graph Filtering API */
182
183 /* Obtain a new graph instance that only contains the subset of desired nodes
184  * WARNING: Do NOT pass an already filtered depsgraph through this function again,
185  *          as we are currently unable to accurately recreate it.
186  */
187 Depsgraph *DEG_graph_filter(const Depsgraph *graph_src, Main *bmain, DEG_FilterQuery *query)
188 {
189         const DEG::Depsgraph *deg_graph_src = reinterpret_cast<const DEG::Depsgraph *>(graph_src);
190         if (deg_graph_src == NULL) {
191                 return NULL;
192         }
193
194         /* Construct a full new depsgraph based on the one we got */
195         /* TODO: Improve the builders to not add any ID nodes we don't need later (e.g. ProxyBuilder?) */
196         Depsgraph *graph_new = DEG_graph_new(deg_graph_src->scene,
197                                              deg_graph_src->view_layer,
198                                              deg_graph_src->mode);
199         DEG_graph_build_from_view_layer(graph_new,
200                                         bmain,
201                                         deg_graph_src->scene,
202                                         deg_graph_src->view_layer);
203
204         /* Build a set of all the id's we want to keep */
205         GSet *retained_ids = BLI_gset_ptr_new(__func__);
206         DEG::RetainedIdUserData retained_id_data = {query, retained_ids};
207
208         LISTBASE_FOREACH(DEG_FilterTarget *, target, &query->targets) {
209                 /* Target Itself */
210                 BLI_gset_add(retained_ids, (void *)target->id);
211
212                 /* Target's Ancestors (i.e. things it depends on) */
213                 DEG_foreach_ancestor_ID(graph_new,
214                                         target->id,
215                                         DEG::deg_add_retained_id_cb,
216                                         &retained_id_data);
217         }
218
219         /* Remove everything we don't want to keep around anymore */
220         DEG::Depsgraph *deg_graph_new = reinterpret_cast<DEG::Depsgraph *>(graph_new);
221         if (BLI_gset_len(retained_ids) > 0) {
222                 DEG::deg_filter_remove_unwanted_ids(deg_graph_new, retained_ids);
223         }
224         // TODO: query->LOD filters
225
226         /* Free temp data */
227         BLI_gset_free(retained_ids, NULL);
228         retained_ids = NULL;
229
230         /* Print Stats */
231         // XXX: Hide behind debug flags
232         size_t s_outer, s_operations, s_relations;
233         size_t s_ids = deg_graph_src->id_nodes.size();
234         unsigned int s_idh = BLI_ghash_len(deg_graph_src->id_hash);
235
236         size_t n_outer, n_operations, n_relations;
237         size_t n_ids = deg_graph_new->id_nodes.size();
238         unsigned int n_idh = BLI_ghash_len(deg_graph_new->id_hash);
239
240         DEG_stats_simple(graph_src, &s_outer, &s_operations, &s_relations);
241         DEG_stats_simple(graph_new, &n_outer, &n_operations, &n_relations);
242
243         printf("%s: src = (ID's: %zu (%u), Out: %zu, Op: %zu, Rel: %zu)\n",
244                __func__, s_ids, s_idh, s_outer, s_operations, s_relations);
245         printf("%s: new = (ID's: %zu (%u), Out: %zu, Op: %zu, Rel: %zu)\n",
246                __func__, n_ids, n_idh, n_outer, n_operations, n_relations);
247
248         /* Return this new graph instance */
249         return graph_new;
250 }
251
252 /* *************************************************** */