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