diff options
Diffstat (limited to 'source/blender/depsgraph/intern')
23 files changed, 9082 insertions, 0 deletions
diff --git a/source/blender/depsgraph/intern/depsgraph.cc b/source/blender/depsgraph/intern/depsgraph.cc new file mode 100644 index 00000000000..e9b2a06cf7b --- /dev/null +++ b/source/blender/depsgraph/intern/depsgraph.cc @@ -0,0 +1,473 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): Sergey Sharybin + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph.cc + * \ingroup depsgraph + * + * Core routines for how the Depsgraph works. + */ + +#include <string.h> + +#include "MEM_guardedalloc.h" + +#include "BLI_listbase.h" + +extern "C" { +#include "DNA_action_types.h" +#include "DNA_armature_types.h" +#include "DNA_constraint_types.h" +#include "DNA_key_types.h" +#include "DNA_object_types.h" +#include "DNA_sequence_types.h" + +#include "RNA_access.h" +} + +#include "DEG_depsgraph.h" +#include "depsgraph.h" /* own include */ +#include "depsnode.h" +#include "depsnode_operation.h" +#include "depsnode_component.h" +#include "depsgraph_intern.h" + +static DEG_EditorUpdateIDCb deg_editor_update_id_cb = NULL; +static DEG_EditorUpdateSceneCb deg_editor_update_scene_cb = NULL; + +Depsgraph::Depsgraph() + : root_node(NULL), + need_update(false), + layers((1 << 20) - 1) +{ + BLI_spin_init(&lock); +} + +Depsgraph::~Depsgraph() +{ + /* Free root node - it won't have been freed yet... */ + clear_id_nodes(); + clear_subgraph_nodes(); + if (this->root_node != NULL) { + OBJECT_GUARDED_DELETE(this->root_node, RootDepsNode); + } + BLI_spin_end(&lock); +} + +/* Query Conditions from RNA ----------------------- */ + +static bool pointer_to_id_node_criteria(const PointerRNA *ptr, + const PropertyRNA *prop, + ID **id) +{ + if (!ptr->type) + return false; + + if (!prop) { + if (RNA_struct_is_ID(ptr->type)) { + *id = (ID *)ptr->data; + return true; + } + } + + return false; +} + +static bool pointer_to_component_node_criteria(const PointerRNA *ptr, + const PropertyRNA *prop, + ID **id, + eDepsNode_Type *type, + string *subdata) +{ + if (!ptr->type) + return false; + + /* Set default values for returns. */ + *id = (ID *)ptr->id.data; /* For obvious reasons... */ + *subdata = ""; /* Default to no subdata (e.g. bone) name + * lookup in most cases. */ + + /* Handling of commonly known scenarios... */ + if (ptr->type == &RNA_PoseBone) { + bPoseChannel *pchan = (bPoseChannel *)ptr->data; + + /* Bone - generally, we just want the bone component... */ + *type = DEPSNODE_TYPE_BONE; + *subdata = pchan->name; + + return true; + } + else if (ptr->type == &RNA_Bone) { + Bone *bone = (Bone *)ptr->data; + + /* armature-level bone, but it ends up going to bone component anyway */ + // TODO: the ID in thise case will end up being bArmature, not Object as needed! + *type = DEPSNODE_TYPE_BONE; + *subdata = bone->name; + //*id = ... + + return true; + } + else if (RNA_struct_is_a(ptr->type, &RNA_Constraint)) { + Object *ob = (Object *)ptr->id.data; + bConstraint *con = (bConstraint *)ptr->data; + + /* object or bone? */ + if (BLI_findindex(&ob->constraints, con) != -1) { + /* object transform */ + // XXX: for now, we can't address the specific constraint or the constraint stack... + *type = DEPSNODE_TYPE_TRANSFORM; + return true; + } + else if (ob->pose) { + bPoseChannel *pchan; + for (pchan = (bPoseChannel *)ob->pose->chanbase.first; pchan; pchan = pchan->next) { + if (BLI_findindex(&pchan->constraints, con) != -1) { + /* bone transforms */ + *type = DEPSNODE_TYPE_BONE; + *subdata = pchan->name; + return true; + } + } + } + } + else if (RNA_struct_is_a(ptr->type, &RNA_Modifier)) { + //ModifierData *md = (ModifierData *)ptr->data; + + /* Modifier */ + /* NOTE: subdata is not the same as "operation name", + * so although we have unique ops for modifiers, + * we can't lump them together + */ + *type = DEPSNODE_TYPE_BONE; + //*subdata = md->name; + + return true; + } + else if (ptr->type == &RNA_Object) { + //Object *ob = (Object *)ptr->data; + + /* Transforms props? */ + if (prop) { + const char *prop_identifier = RNA_property_identifier((PropertyRNA *)prop); + + if (strstr(prop_identifier, "location") || + strstr(prop_identifier, "rotation") || + strstr(prop_identifier, "scale")) + { + *type = DEPSNODE_TYPE_TRANSFORM; + return true; + } + } + // ... + } + else if (ptr->type == &RNA_ShapeKey) { + Key *key = (Key *)ptr->id.data; + + /* ShapeKeys are currently handled as geometry on the geometry that owns it */ + *id = key->from; // XXX + *type = DEPSNODE_TYPE_PARAMETERS; + + return true; + } + else if (RNA_struct_is_a(ptr->type, &RNA_Sequence)) { + Sequence *seq = (Sequence *)ptr->data; + /* Sequencer strip */ + *type = DEPSNODE_TYPE_SEQUENCER; + *subdata = seq->name; // xxx? + return true; + } + + if (prop) { + /* All unknown data effectively falls under "parameter evaluation" */ + *type = DEPSNODE_TYPE_PARAMETERS; + return true; + } + + return false; +} + +/* Convenience wrapper to find node given just pointer + property. */ +DepsNode *Depsgraph::find_node_from_pointer(const PointerRNA *ptr, + const PropertyRNA *prop) const +{ + ID *id; + eDepsNode_Type type; + string name; + + /* Get querying conditions. */ + if (pointer_to_id_node_criteria(ptr, prop, &id)) { + return find_id_node(id); + } + else if (pointer_to_component_node_criteria(ptr, prop, &id, &type, &name)) { + IDDepsNode *id_node = find_id_node(id); + if (id_node) + return id_node->find_component(type, name); + } + + return NULL; +} + +/* Node Management ---------------------------- */ + +RootDepsNode *Depsgraph::add_root_node() +{ + if (!root_node) { + DepsNodeFactory *factory = DEG_get_node_factory(DEPSNODE_TYPE_ROOT); + root_node = (RootDepsNode *)factory->create_node(NULL, "", "Root (Scene)"); + } + return root_node; +} + +TimeSourceDepsNode *Depsgraph::find_time_source(const ID *id) const +{ + /* Search for one attached to a particular ID? */ + if (id) { + /* Check if it was added as a component + * (as may be done for subgraphs needing timeoffset). + */ + IDDepsNode *id_node = find_id_node(id); + if (id_node) { + // XXX: review this +// return id_node->find_component(DEPSNODE_TYPE_TIMESOURCE); + } + BLI_assert(!"Not implemented yet"); + } + else { + /* Use "official" timesource. */ + return root_node->time_source; + } + return NULL; +} + +SubgraphDepsNode *Depsgraph::add_subgraph_node(const ID *id) +{ + DepsNodeFactory *factory = DEG_get_node_factory(DEPSNODE_TYPE_SUBGRAPH); + SubgraphDepsNode *subgraph_node = + (SubgraphDepsNode *)factory->create_node(id, "", id->name + 2); + + /* Add to subnodes list. */ + this->subgraphs.insert(subgraph_node); + + /* if there's an ID associated, add to ID-nodes lookup too */ + if (id) { +#if 0 + /* XXX subgraph node is NOT a true IDDepsNode - what is this supposed to do? */ + // TODO: what to do if subgraph's ID has already been added? + BLI_assert(!graph->find_id_node(id)); + graph->id_hash[id] = this; +#endif + } + + return subgraph_node; +} + +void Depsgraph::remove_subgraph_node(SubgraphDepsNode *subgraph_node) +{ + subgraphs.erase(subgraph_node); + OBJECT_GUARDED_DELETE(subgraph_node, SubgraphDepsNode); +} + +void Depsgraph::clear_subgraph_nodes() +{ + for (Subgraphs::iterator it = subgraphs.begin(); + it != subgraphs.end(); + ++it) + { + SubgraphDepsNode *subgraph_node = *it; + OBJECT_GUARDED_DELETE(subgraph_node, SubgraphDepsNode); + } + subgraphs.clear(); +} + +IDDepsNode *Depsgraph::find_id_node(const ID *id) const +{ + IDNodeMap::const_iterator it = this->id_hash.find(id); + return it != this->id_hash.end() ? it->second : NULL; +} + +IDDepsNode *Depsgraph::add_id_node(ID *id, const string &name) +{ + IDDepsNode *id_node = find_id_node(id); + if (!id_node) { + DepsNodeFactory *factory = DEG_get_node_factory(DEPSNODE_TYPE_ID_REF); + id_node = (IDDepsNode *)factory->create_node(id, "", name); + id->flag |= LIB_DOIT; + /* register */ + this->id_hash[id] = id_node; + } + return id_node; +} + +void Depsgraph::remove_id_node(const ID *id) +{ + IDDepsNode *id_node = find_id_node(id); + if (id_node) { + /* unregister */ + this->id_hash.erase(id); + OBJECT_GUARDED_DELETE(id_node, IDDepsNode); + } +} + +void Depsgraph::clear_id_nodes() +{ + for (IDNodeMap::const_iterator it = id_hash.begin(); + it != id_hash.end(); + ++it) + { + IDDepsNode *id_node = it->second; + OBJECT_GUARDED_DELETE(id_node, IDDepsNode); + } + id_hash.clear(); +} + +/* Add new relationship between two nodes. */ +DepsRelation *Depsgraph::add_new_relation(OperationDepsNode *from, + OperationDepsNode *to, + eDepsRelation_Type type, + const char *description) +{ + /* Create new relation, and add it to the graph. */ + DepsRelation *rel = OBJECT_GUARDED_NEW(DepsRelation, from, to, type, description); + return rel; +} + +/* Add new relation between two nodes */ +DepsRelation *Depsgraph::add_new_relation(DepsNode *from, DepsNode *to, + eDepsRelation_Type type, + const char *description) +{ + /* Create new relation, and add it to the graph. */ + DepsRelation *rel = OBJECT_GUARDED_NEW(DepsRelation, from, to, type, description); + return rel; +} + +/* ************************ */ +/* Relationships Management */ + +DepsRelation::DepsRelation(DepsNode *from, + DepsNode *to, + eDepsRelation_Type type, + const char *description) + : from(from), + to(to), + name(description), + type(type), + flag(0) +{ +#ifndef NDEBUG +/* + for (OperationDepsNode::Relations::const_iterator it = from->outlinks.begin(); + it != from->outlinks.end(); + ++it) + { + DepsRelation *rel = *it; + if (rel->from == from && + rel->to == to && + rel->type == type && + rel->name == description) + { + BLI_assert(!"Duplicated relation, should not happen!"); + } + } +*/ +#endif + + /* Hook it up to the nodes which use it. */ + from->outlinks.insert(this); + to->inlinks.insert(this); +} + +DepsRelation::~DepsRelation() +{ + /* Sanity check. */ + BLI_assert(this->from && this->to); + /* Remove it from the nodes that use it. */ + this->from->outlinks.erase(this); + this->to->inlinks.erase(this); +} + +/* Low level tagging -------------------------------------- */ + +/* Tag a specific node as needing updates. */ +void Depsgraph::add_entry_tag(OperationDepsNode *node) +{ + /* Sanity check. */ + if (!node) + return; + + /* Add to graph-level set of directly modified nodes to start searching from. + * NOTE: this is necessary since we have several thousand nodes to play with... + */ + this->entry_tags.insert(node); +} + +void Depsgraph::clear_all_nodes() +{ + clear_id_nodes(); + clear_subgraph_nodes(); + id_hash.clear(); + if (this->root_node) { + OBJECT_GUARDED_DELETE(this->root_node, RootDepsNode); + root_node = NULL; + } +} + +/* **************** */ +/* Public Graph API */ + +/* Initialize a new Depsgraph */ +Depsgraph *DEG_graph_new() +{ + return OBJECT_GUARDED_NEW(Depsgraph); +} + +/* Free graph's contents and graph itself */ +void DEG_graph_free(Depsgraph *graph) +{ + OBJECT_GUARDED_DELETE(graph, Depsgraph); +} + +/* Set callbacks which are being called when depsgraph changes. */ +void DEG_editors_set_update_cb(DEG_EditorUpdateIDCb id_func, + DEG_EditorUpdateSceneCb scene_func) +{ + deg_editor_update_id_cb = id_func; + deg_editor_update_scene_cb = scene_func; +} + +void deg_editors_id_update(Main *bmain, ID *id) +{ + if (deg_editor_update_id_cb != NULL) { + deg_editor_update_id_cb(bmain, id); + } +} + +void deg_editors_scene_update(Main *bmain, Scene *scene, bool updated) +{ + if (deg_editor_update_scene_cb != NULL) { + deg_editor_update_scene_cb(bmain, scene, updated); + } +} diff --git a/source/blender/depsgraph/intern/depsgraph.h b/source/blender/depsgraph/intern/depsgraph.h new file mode 100644 index 00000000000..9533fbd10d5 --- /dev/null +++ b/source/blender/depsgraph/intern/depsgraph.h @@ -0,0 +1,224 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): Sergey Sharybin + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph.h + * \ingroup depsgraph + * + * Datatypes for internal use in the Depsgraph + * + * All of these datatypes are only really used within the "core" depsgraph. + * In particular, node types declared here form the structure of operations + * in the graph. + */ + +#ifndef __DEPSGRAPH_H__ +#define __DEPSGRAPH_H__ + +#include "BLI_threads.h" /* for SpinLock */ + +#include "depsgraph_types.h" + +#include "depsgraph_util_map.h" +#include "depsgraph_util_set.h" + +struct PointerRNA; +struct PropertyRNA; + +struct DepsNode; +struct RootDepsNode; +struct TimeSourceDepsNode; +struct IDDepsNode; +struct SubgraphDepsNode; +struct ComponentDepsNode; +struct OperationDepsNode; + +/* *************************** */ +/* Relationships Between Nodes */ + +/* Settings/Tags on Relationship */ +typedef enum eDepsRelation_Flag { + /* "touched" tag is used when filtering, to know which to collect */ + DEPSREL_FLAG_TEMP_TAG = (1 << 0), + + /* "cyclic" link - when detecting cycles, this relationship was the one + * which triggers a cyclic relationship to exist in the graph + */ + DEPSREL_FLAG_CYCLIC = (1 << 1), +} eDepsRelation_Flag; + +/* B depends on A (A -> B) */ +struct DepsRelation { + /* the nodes in the relationship (since this is shared between the nodes) */ + DepsNode *from; /* A */ + DepsNode *to; /* B */ + + /* relationship attributes */ + const char *name; /* label for debugging */ + + eDepsRelation_Type type; /* type */ + int flag; /* (eDepsRelation_Flag) */ + + DepsRelation(DepsNode *from, + DepsNode *to, + eDepsRelation_Type type, + const char *description); + + ~DepsRelation(); +}; + +/* ********* */ +/* Depsgraph */ + +/* Dependency Graph object */ +struct Depsgraph { + typedef unordered_map<const ID *, IDDepsNode *> IDNodeMap; + typedef unordered_set<SubgraphDepsNode *> Subgraphs; + typedef unordered_set<OperationDepsNode *> EntryTags; + typedef vector<OperationDepsNode *> OperationNodes; + + Depsgraph(); + ~Depsgraph(); + + /** + * Find node which matches the specified description. + * + * \param id: ID block that is associated with this + * \param subdata: identifier used for sub-ID data (e.g. bone) + * \param type: type of node we're dealing with + * \param name: custom identifier assigned to node + * + * \return A node matching the required characteristics if it exists + * or NULL if no such node exists in the graph. + */ + DepsNode *find_node(const ID *id, + eDepsNode_Type type, + const string &subdata, + const string &name); + + /** + * Convenience wrapper to find node given just pointer + property. + * + * \param ptr: pointer to the data that node will represent + * \param prop: optional property affected - providing this effectively results in inner nodes being returned + * + * \return A node matching the required characteristics if it exists + * or NULL if no such node exists in the graph + */ + DepsNode *find_node_from_pointer(const PointerRNA *ptr, const PropertyRNA *prop) const; + + RootDepsNode *add_root_node(); + + TimeSourceDepsNode *find_time_source(const ID *id = NULL) const; + + SubgraphDepsNode *add_subgraph_node(const ID *id); + void remove_subgraph_node(SubgraphDepsNode *subgraph_node); + void clear_subgraph_nodes(); + + IDDepsNode *find_id_node(const ID *id) const; + IDDepsNode *add_id_node(ID *id, const string &name = ""); + void remove_id_node(const ID *id); + void clear_id_nodes(); + + /* Add new relationship between two nodes. */ + DepsRelation *add_new_relation(OperationDepsNode *from, + OperationDepsNode *to, + eDepsRelation_Type type, + const char *description); + + DepsRelation *add_new_relation(DepsNode *from, + DepsNode *to, + eDepsRelation_Type type, + const char *description); + + /* Tag a specific node as needing updates. */ + void add_entry_tag(OperationDepsNode *node); + + /* Clear storage used by all nodes. */ + void clear_all_nodes(); + + /* Core Graph Functionality ........... */ + + /* <ID : IDDepsNode> mapping from ID blocks to nodes representing these blocks + * (for quick lookups). */ + IDNodeMap id_hash; + + /* "root" node - the one where all evaluation enters from. */ + RootDepsNode *root_node; + + /* Subgraphs referenced in tree. */ + Subgraphs subgraphs; + + /* Indicates whether relations needs to be updated. */ + bool need_update; + + /* Quick-Access Temp Data ............. */ + + /* Nodes which have been tagged as "directly modified". */ + EntryTags entry_tags; + + /* Convenience Data ................... */ + + /* XXX: should be collected after building (if actually needed?) */ + /* All operation nodes, sorted in order of single-thread traversal order. */ + OperationNodes operations; + + /* Spin lock for threading-critical operations. + * Mainly used by graph evaluation. + */ + SpinLock lock; + + /* Layers Visibility .................. */ + + /* Visible layers bitfield, used for skipping invisible objects updates. */ + int layers; + + // XXX: additional stuff like eval contexts, mempools for allocating nodes from, etc. +}; + +/** + * Helper macros for iterating over set of relationship links + * incident on each node. + * + * \note it is safe to perform removal operations here... + * + * relations_set[in]: (DepsNode::Relations) set of relationships (in/out links) + * relation[out]: (DepsRelation *) identifier where DepsRelation that we're + * currently accessing comes up + */ +#define DEPSNODE_RELATIONS_ITER_BEGIN(relations_set_, relation_) \ + { \ + OperationDepsNode::Relations::const_iterator __rel_iter = relations_set_.begin(); \ + while (__rel_iter != relations_set_.end()) { \ + DepsRelation *relation_ = *__rel_iter; \ + ++__rel_iter; \ + + /* ... code for iterator body can be written here ... */ + +#define DEPSNODE_RELATIONS_ITER_END \ + } \ + } ((void)0) + +#endif /* __DEPSGRAPH_H__ */ diff --git a/source/blender/depsgraph/intern/depsgraph_build.cc b/source/blender/depsgraph/intern/depsgraph_build.cc new file mode 100644 index 00000000000..7a2ee2c416a --- /dev/null +++ b/source/blender/depsgraph/intern/depsgraph_build.cc @@ -0,0 +1,370 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): Based on original depsgraph.c code - Blender Foundation (2005-2013) + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph_build.cc + * \ingroup depsgraph + * + * Methods for constructing depsgraph. + */ + +#include <stack> + +#include "MEM_guardedalloc.h" + +extern "C" { +#include "BLI_blenlib.h" +#include "BLI_string.h" +#include "BLI_utildefines.h" + +#include "DNA_action_types.h" +#include "DNA_anim_types.h" +#include "DNA_armature_types.h" +#include "DNA_camera_types.h" +#include "DNA_constraint_types.h" +#include "DNA_curve_types.h" +#include "DNA_effect_types.h" +#include "DNA_group_types.h" +#include "DNA_key_types.h" +#include "DNA_lamp_types.h" +#include "DNA_material_types.h" +#include "DNA_mesh_types.h" +#include "DNA_meta_types.h" +#include "DNA_node_types.h" +#include "DNA_particle_types.h" +#include "DNA_object_types.h" +#include "DNA_rigidbody_types.h" +#include "DNA_scene_types.h" +#include "DNA_texture_types.h" +#include "DNA_world_types.h" + +#include "BKE_action.h" +#include "BKE_armature.h" +#include "BKE_animsys.h" +#include "BKE_constraint.h" +#include "BKE_curve.h" +#include "BKE_effect.h" +#include "BKE_fcurve.h" +#include "BKE_group.h" +#include "BKE_key.h" +#include "BKE_library.h" +#include "BKE_main.h" +#include "BKE_material.h" +#include "BKE_mball.h" +#include "BKE_modifier.h" +#include "BKE_node.h" +#include "BKE_object.h" +#include "BKE_particle.h" +#include "BKE_rigidbody.h" +#include "BKE_sound.h" +#include "BKE_texture.h" +#include "BKE_tracking.h" +#include "BKE_world.h" + +#include "DEG_depsgraph.h" +#include "DEG_depsgraph_debug.h" +#include "DEG_depsgraph_build.h" + +#include "RNA_access.h" +#include "RNA_types.h" +} /* extern "C" */ + +#include "depsnode.h" +#include "depsnode_component.h" +#include "depsgraph_debug.h" +#include "depsnode_operation.h" +#include "depsgraph_types.h" +#include "depsgraph_build.h" +#include "depsgraph_intern.h" + +#include "depsgraph_util_cycle.h" +#include "depsgraph_util_transitive.h" + +/* ****************** */ +/* External Build API */ + +static eDepsNode_Type deg_build_scene_component_type(eDepsSceneComponentType component) +{ + switch (component) { + case DEG_SCENE_COMP_PARAMETERS: return DEPSNODE_TYPE_PARAMETERS; + case DEG_SCENE_COMP_ANIMATION: return DEPSNODE_TYPE_ANIMATION; + case DEG_SCENE_COMP_SEQUENCER: return DEPSNODE_TYPE_SEQUENCER; + } + return DEPSNODE_TYPE_UNDEFINED; +} + +static eDepsNode_Type deg_build_object_component_type(eDepsObjectComponentType component) +{ + switch (component) { + case DEG_OB_COMP_PARAMETERS: return DEPSNODE_TYPE_PARAMETERS; + case DEG_OB_COMP_PROXY: return DEPSNODE_TYPE_PROXY; + case DEG_OB_COMP_ANIMATION: return DEPSNODE_TYPE_ANIMATION; + case DEG_OB_COMP_TRANSFORM: return DEPSNODE_TYPE_TRANSFORM; + case DEG_OB_COMP_GEOMETRY: return DEPSNODE_TYPE_GEOMETRY; + case DEG_OB_COMP_EVAL_POSE: return DEPSNODE_TYPE_EVAL_POSE; + case DEG_OB_COMP_BONE: return DEPSNODE_TYPE_BONE; + case DEG_OB_COMP_EVAL_PARTICLES: return DEPSNODE_TYPE_EVAL_PARTICLES; + case DEG_OB_COMP_SHADING: return DEPSNODE_TYPE_SHADING; + } + return DEPSNODE_TYPE_UNDEFINED; +} + +void DEG_add_scene_relation(DepsNodeHandle *handle, struct Scene *scene, eDepsSceneComponentType component, const char *description) +{ + eDepsNode_Type type = deg_build_scene_component_type(component); + ComponentKey comp_key(&scene->id, type); + handle->builder->add_node_handle_relation(comp_key, handle, DEPSREL_TYPE_GEOMETRY_EVAL, description); +} + +void DEG_add_object_relation(DepsNodeHandle *handle, struct Object *ob, eDepsObjectComponentType component, const char *description) +{ + eDepsNode_Type type = deg_build_object_component_type(component); + ComponentKey comp_key(&ob->id, type); + handle->builder->add_node_handle_relation(comp_key, handle, DEPSREL_TYPE_GEOMETRY_EVAL, description); +} + +void DEG_add_bone_relation(DepsNodeHandle *handle, struct Object *ob, const char *bone_name, eDepsObjectComponentType component, const char *description) +{ + eDepsNode_Type type = deg_build_object_component_type(component); + ComponentKey comp_key(&ob->id, type, bone_name); + + // XXX: "Geometry Eval" might not always be true, but this only gets called from modifier building now + handle->builder->add_node_handle_relation(comp_key, handle, DEPSREL_TYPE_GEOMETRY_EVAL, description); +} + +void DEG_add_special_eval_flag(Depsgraph *graph, ID *id, short flag) +{ + if (graph == NULL) { + BLI_assert(!"Graph should always be valid"); + return; + } + IDDepsNode *id_node = graph->find_id_node(id); + if (id_node == NULL) { + BLI_assert(!"ID should always be valid"); + return; + } + id_node->eval_flags |= flag; +} + +/* ********************** */ +/* Utilities for Builders */ + +/* Get unique identifier for FCurves and Drivers */ +string deg_fcurve_id_name(const FCurve *fcu) +{ + char index_buf[32]; + sprintf(index_buf, "[%d]", fcu->array_index); + + return string(fcu->rna_path) + index_buf; +} + +static void deg_graph_build_finalize(Depsgraph *graph) +{ + std::stack<OperationDepsNode *> stack; + + for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin(); + it_op != graph->operations.end(); + ++it_op) + { + OperationDepsNode *node = *it_op; + node->done = 0; + node->num_links_pending = 0; + for (OperationDepsNode::Relations::const_iterator it_rel = node->inlinks.begin(); + it_rel != node->inlinks.end(); + ++it_rel) + { + DepsRelation *rel = *it_rel; + if ((rel->from->type == DEPSNODE_TYPE_OPERATION) && + (rel->flag & DEPSREL_FLAG_CYCLIC) == 0) + { + ++node->num_links_pending; + } + } + if (node->num_links_pending == 0) { + stack.push(node); + } + IDDepsNode *id_node = node->owner->owner; + id_node->id->flag |= LIB_DOIT; + } + + while (!stack.empty()) { + OperationDepsNode *node = stack.top(); + if (node->done == 0 && node->outlinks.size() != 0) { + for (OperationDepsNode::Relations::const_iterator it_rel = node->outlinks.begin(); + it_rel != node->outlinks.end(); + ++it_rel) + { + DepsRelation *rel = *it_rel; + if (rel->to->type == DEPSNODE_TYPE_OPERATION) { + OperationDepsNode *to = (OperationDepsNode *)rel->to; + if ((rel->flag & DEPSREL_FLAG_CYCLIC) == 0) { + BLI_assert(to->num_links_pending > 0); + --to->num_links_pending; + } + if (to->num_links_pending == 0) { + stack.push(to); + } + } + } + node->done = 1; + } + else { + stack.pop(); + IDDepsNode *id_node = node->owner->owner; + for (OperationDepsNode::Relations::const_iterator it_rel = node->outlinks.begin(); + it_rel != node->outlinks.end(); + ++it_rel) + { + DepsRelation *rel = *it_rel; + if (rel->to->type == DEPSNODE_TYPE_OPERATION) { + OperationDepsNode *to = (OperationDepsNode *)rel->to; + IDDepsNode *id_to = to->owner->owner; + id_node->layers |= id_to->layers; + } + } + + /* Re-tag ID for update if it was tagged before the relations + * update tag. + */ + ID *id = id_node->id; + if (id->flag & LIB_ID_RECALC_ALL && + id->flag & LIB_DOIT) + { + id_node->tag_update(graph); + id->flag &= ~LIB_DOIT; + } + } + } +} + +/* ******************** */ +/* Graph Building API's */ + +/* Build depsgraph for the given scene, and dump results in given graph container */ +// XXX: assume that this is called from outside, given the current scene as the "main" scene +void DEG_graph_build_from_scene(Depsgraph *graph, Main *bmain, Scene *scene) +{ + /* 1) Generate all the nodes in the graph first */ + DepsgraphNodeBuilder node_builder(bmain, graph); + /* create root node for scene first + * - this way it should be the first in the graph, + * reflecting its role as the entrypoint + */ + node_builder.add_root_node(); + node_builder.build_scene(bmain, scene); + + /* 2) Hook up relationships between operations - to determine evaluation order */ + DepsgraphRelationBuilder relation_builder(graph); + /* hook scene up to the root node as entrypoint to graph */ + /* XXX what does this relation actually mean? + * it doesnt add any operations anyway and is not clear what part of the scene is to be connected. + */ + //relation_builder.add_relation(RootKey(), IDKey(scene), DEPSREL_TYPE_ROOT_TO_ACTIVE, "Root to Active Scene"); + relation_builder.build_scene(bmain, scene); + + /* Detect and solve cycles. */ + deg_graph_detect_cycles(graph); + + /* 3) Simplify the graph by removing redundant relations (to optimise traversal later) */ + // TODO: it would be useful to have an option to disable this in cases where it is causing trouble + if (G.debug_value == 799) { + deg_graph_transitive_reduction(graph); + } + + /* 4) Flush visibility layer and re-schedule nodes for update. */ + deg_graph_build_finalize(graph); + +#if 0 + if (!DEG_debug_consistency_check(graph)) { + printf("Consistency validation failed, ABORTING!\n"); + abort(); + } +#endif +} + +/* Tag graph relations for update. */ +void DEG_graph_tag_relations_update(Depsgraph *graph) +{ + graph->need_update = true; +} + +/* Tag all relations for update. */ +void DEG_relations_tag_update(Main *bmain) +{ + for (Scene *scene = (Scene *)bmain->scene.first; + scene != NULL; + scene = (Scene *)scene->id.next) + { + if (scene->depsgraph != NULL) { + DEG_graph_tag_relations_update(scene->depsgraph); + } + } +} + +/* Create new graph if didn't exist yet, + * or update relations if graph was tagged for update. + */ +void DEG_scene_relations_update(Main *bmain, Scene *scene) +{ + if (scene->depsgraph == NULL) { + /* Rebuild graph from scratch and exit. */ + scene->depsgraph = DEG_graph_new(); + DEG_graph_build_from_scene(scene->depsgraph, bmain, scene); + return; + } + + Depsgraph *graph = scene->depsgraph; + if (!graph->need_update) { + /* Graph is up to date, nothing to do. */ + return; + } + + /* Clear all previous nodes and operations. */ + graph->clear_all_nodes(); + graph->operations.clear(); + graph->entry_tags.clear(); + + /* Build new nodes and relations. */ + DEG_graph_build_from_scene(graph, bmain, scene); + + graph->need_update = false; +} + +/* Rebuild dependency graph only for a given scene. */ +void DEG_scene_relations_rebuild(Main *bmain, Scene *scene) +{ + if (scene->depsgraph != NULL) { + DEG_graph_tag_relations_update(scene->depsgraph); + } + DEG_scene_relations_update(bmain, scene); +} + +void DEG_scene_graph_free(Scene *scene) +{ + if (scene->depsgraph) { + DEG_graph_free(scene->depsgraph); + scene->depsgraph = NULL; + } +} diff --git a/source/blender/depsgraph/intern/depsgraph_build.h b/source/blender/depsgraph/intern/depsgraph_build.h new file mode 100644 index 00000000000..4088a3289ef --- /dev/null +++ b/source/blender/depsgraph/intern/depsgraph_build.h @@ -0,0 +1,408 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Lukas Toenne + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph_build.h + * \ingroup depsgraph + */ + +#ifndef __DEPSGRAPH_BUILD_H__ +#define __DEPSGRAPH_BUILD_H__ + +struct Base; +struct bGPdata; +struct ListBase; +struct GHash; +struct ID; +struct FCurve; +struct Group; +struct Key; +struct Main; +struct Material; +struct MTex; +struct bNodeTree; +struct Object; +struct bPoseChannel; +struct bConstraint; +struct Scene; +struct Tex; +struct World; + +struct PropertyRNA; + +struct Depsgraph; +struct DepsNode; +struct DepsNodeHandle; +struct RootDepsNode; +struct SubgraphDepsNode; +struct IDDepsNode; +struct TimeSourceDepsNode; +struct ComponentDepsNode; +struct OperationDepsNode; +struct RootPChanMap; + +struct DepsgraphNodeBuilder { + DepsgraphNodeBuilder(Main *bmain, Depsgraph *graph); + ~DepsgraphNodeBuilder(); + + RootDepsNode *add_root_node(); + IDDepsNode *add_id_node(ID *id); + TimeSourceDepsNode *add_time_source(ID *id); + + ComponentDepsNode *add_component_node(ID *id, eDepsNode_Type comp_type, const string &comp_name = ""); + + OperationDepsNode *add_operation_node(ComponentDepsNode *comp_node, eDepsOperation_Type optype, + DepsEvalOperationCb op, eDepsOperation_Code opcode, const string &description = ""); + OperationDepsNode *add_operation_node(ID *id, eDepsNode_Type comp_type, const string &comp_name, eDepsOperation_Type optype, + DepsEvalOperationCb op, eDepsOperation_Code opcode, const string &description = ""); + OperationDepsNode *add_operation_node(ID *id, eDepsNode_Type comp_type, eDepsOperation_Type optype, + DepsEvalOperationCb op, eDepsOperation_Code opcode, const string &description = "") + { + return add_operation_node(id, comp_type, "", optype, op, opcode, description); + } + + bool has_operation_node(ID *id, eDepsNode_Type comp_type, const string &comp_name, + eDepsOperation_Code opcode, const string &description = ""); + + OperationDepsNode *find_operation_node(ID *id, + eDepsNode_Type comp_type, + const string &comp_name, + eDepsOperation_Code opcode, + const string &description = ""); + + OperationDepsNode *find_operation_node(ID *id, + eDepsNode_Type comp_type, + eDepsOperation_Code opcode, + const string &description = "") + { + return find_operation_node(id, comp_type, "", opcode, description); + } + + void build_scene(Main *bmain, Scene *scene); + SubgraphDepsNode *build_subgraph(Group *group); + void build_group(Scene *scene, Base *base, Group *group); + void build_object(Scene *scene, Base *base, Object *ob); + void build_object_transform(Scene *scene, Object *ob); + void build_object_constraints(Scene *scene, Object *ob); + void build_pose_constraints(Object *ob, bPoseChannel *pchan); + void build_rigidbody(Scene *scene); + void build_particles(Object *ob); + void build_animdata(ID *id); + OperationDepsNode *build_driver(ID *id, FCurve *fcurve); + void build_ik_pose(Scene *scene, Object *ob, bPoseChannel *pchan, bConstraint *con); + void build_splineik_pose(Scene *scene, Object *ob, bPoseChannel *pchan, bConstraint *con); + void build_rig(Scene *scene, Object *ob); + void build_proxy_rig(Object *ob); + void build_shapekeys(Key *key); + void build_obdata_geom(Scene *scene, Object *ob); + void build_camera(Object *ob); + void build_lamp(Object *ob); + void build_nodetree(DepsNode *owner_node, bNodeTree *ntree); + void build_material(DepsNode *owner_node, Material *ma); + void build_texture(DepsNode *owner_node, Tex *tex); + void build_texture_stack(DepsNode *owner_node, MTex **texture_stack); + void build_world(World *world); + void build_compositor(Scene *scene); + void build_gpencil(bGPdata *gpd); + +private: + Main *m_bmain; + Depsgraph *m_graph; +}; + +struct RootKey +{ + RootKey() {} +}; + +struct TimeSourceKey +{ + TimeSourceKey() : id(NULL) {} + TimeSourceKey(ID *id) : id(id) {} + + string identifier() const + { + return string("TimeSourceKey"); + } + + ID *id; +}; + +struct ComponentKey +{ + ComponentKey() : + id(NULL), type(DEPSNODE_TYPE_UNDEFINED), name("") + {} + ComponentKey(ID *id, eDepsNode_Type type, const string &name = "") : + id(id), type(type), name(name) + {} + + string identifier() const + { + const char *idname = (id) ? id->name : "<None>"; + + char typebuf[5]; + sprintf(typebuf, "%d", type); + + return string("ComponentKey(") + idname + ", " + typebuf + ", '" + name + "')"; + } + + ID *id; + eDepsNode_Type type; + string name; +}; + +struct OperationKey +{ + OperationKey() : + id(NULL), component_type(DEPSNODE_TYPE_UNDEFINED), component_name(""), opcode(DEG_OPCODE_OPERATION), name("") + {} + + OperationKey(ID *id, eDepsNode_Type component_type, const string &name) : + id(id), component_type(component_type), component_name(""), opcode(DEG_OPCODE_OPERATION), name(name) + {} + OperationKey(ID *id, eDepsNode_Type component_type, const string &component_name, const string &name) : + id(id), component_type(component_type), component_name(component_name), opcode(DEG_OPCODE_OPERATION), name(name) + {} + + OperationKey(ID *id, eDepsNode_Type component_type, eDepsOperation_Code opcode) : + id(id), component_type(component_type), component_name(""), opcode(opcode), name("") + {} + OperationKey(ID *id, eDepsNode_Type component_type, const string &component_name, eDepsOperation_Code opcode) : + id(id), component_type(component_type), component_name(component_name), opcode(opcode), name("") + {} + + OperationKey(ID *id, eDepsNode_Type component_type, eDepsOperation_Code opcode, const string &name) : + id(id), component_type(component_type), component_name(""), opcode(opcode), name(name) + {} + OperationKey(ID *id, eDepsNode_Type component_type, const string &component_name, eDepsOperation_Code opcode, const string &name) : + id(id), component_type(component_type), component_name(component_name), opcode(opcode), name(name) + {} + + string identifier() const + { + char typebuf[5]; + sprintf(typebuf, "%d", component_type); + + return string("OperationKey(") + "t: " + typebuf + ", cn: '" + component_name + "', c: " + DEG_OPNAMES[opcode] + ", n: '" + name + "')"; + } + + + ID *id; + eDepsNode_Type component_type; + string component_name; + eDepsOperation_Code opcode; + string name; +}; + +struct RNAPathKey +{ + // Note: see depsgraph_build.cpp for implementation + RNAPathKey(ID *id, const char *path); + + RNAPathKey(ID *id, const PointerRNA &ptr, PropertyRNA *prop) : + id(id), ptr(ptr), prop(prop) + {} + + string identifier() const + { + const char *id_name = (id) ? id->name : "<No ID>"; + const char *prop_name = (prop) ? RNA_property_identifier(prop) : "<No Prop>"; + + return string("RnaPathKey(") + "id: " + id_name + ", prop: " + prop_name + "')"; + } + + + ID *id; + PointerRNA ptr; + PropertyRNA *prop; +}; + +struct DepsgraphRelationBuilder +{ + DepsgraphRelationBuilder(Depsgraph *graph); + + template <typename KeyFrom, typename KeyTo> + void add_relation(const KeyFrom &key_from, const KeyTo &key_to, + eDepsRelation_Type type, const char *description); + + template <typename KeyTo> + void add_relation(const TimeSourceKey &key_from, const KeyTo &key_to, + eDepsRelation_Type type, const char *description); + + template <typename KeyType> + void add_node_handle_relation(const KeyType &key_from, const DepsNodeHandle *handle, + eDepsRelation_Type type, const char *description); + + void build_scene(Main *bmain, Scene *scene); + void build_group(Main *bmain, Scene *scene, Object *object, Group *group); + void build_object(Main *bmain, Scene *scene, Object *ob); + void build_object_parent(Object *ob); + void build_constraints(Scene *scene, ID *id, eDepsNode_Type component_type, const char *component_subdata, + ListBase *constraints, RootPChanMap *root_map); + void build_animdata(ID *id); + void build_driver(ID *id, FCurve *fcurve); + void build_world(World *world); + void build_rigidbody(Scene *scene); + void build_particles(Scene *scene, Object *ob); + void build_ik_pose(Object *ob, bPoseChannel *pchan, bConstraint *con, RootPChanMap *root_map); + void build_splineik_pose(Object *ob, bPoseChannel *pchan, bConstraint *con, RootPChanMap *root_map); + void build_rig(Scene *scene, Object *ob); + void build_proxy_rig(Object *ob); + void build_shapekeys(ID *obdata, Key *key); + void build_obdata_geom(Main *bmain, Scene *scene, Object *ob); + void build_camera(Object *ob); + void build_lamp(Object *ob); + void build_nodetree(ID *owner, bNodeTree *ntree); + void build_material(ID *owner, Material *ma); + void build_texture(ID *owner, Tex *tex); + void build_texture_stack(ID *owner, MTex **texture_stack); + void build_compositor(Scene *scene); + void build_gpencil(ID *owner, bGPdata *gpd); + +protected: + RootDepsNode *find_node(const RootKey &key) const; + TimeSourceDepsNode *find_node(const TimeSourceKey &key) const; + ComponentDepsNode *find_node(const ComponentKey &key) const; + OperationDepsNode *find_node(const OperationKey &key) const; + DepsNode *find_node(const RNAPathKey &key) const; + OperationDepsNode *has_node(const OperationKey &key) const; + + void add_time_relation(TimeSourceDepsNode *timesrc, DepsNode *node_to, const char *description); + void add_operation_relation(OperationDepsNode *node_from, OperationDepsNode *node_to, + eDepsRelation_Type type, const char *description); + + template <typename KeyType> + DepsNodeHandle create_node_handle(const KeyType &key, const string &default_name = ""); + + bool needs_animdata_node(ID *id); + +private: + Depsgraph *m_graph; +}; + +struct DepsNodeHandle +{ + DepsNodeHandle(DepsgraphRelationBuilder *builder, OperationDepsNode *node, const string &default_name = "") : + builder(builder), + node(node), + default_name(default_name) + { + BLI_assert(node != NULL); + } + + DepsgraphRelationBuilder *builder; + OperationDepsNode *node; + const string &default_name; +}; + +/* Utilities for Builders ----------------------------------------------------- */ + +/* Get unique identifier for FCurves and Drivers */ +string deg_fcurve_id_name(const FCurve *fcu); + +template <typename KeyFrom, typename KeyTo> +void DepsgraphRelationBuilder::add_relation(const KeyFrom &key_from, + const KeyTo &key_to, + eDepsRelation_Type type, + const char *description) +{ + DepsNode *node_from = find_node(key_from); + DepsNode *node_to = find_node(key_to); + OperationDepsNode *op_from = node_from ? node_from->get_exit_operation() : NULL; + OperationDepsNode *op_to = node_to ? node_to->get_entry_operation() : NULL; + if (op_from && op_to) { + add_operation_relation(op_from, op_to, type, description); + } + else { + if (!op_from) { + /* XXX TODO handle as error or report if needed */ + fprintf(stderr, "add_relation(%d, %s) - Could not find op_from (%s)\n", + type, description, key_from.identifier().c_str()); + } + else { + fprintf(stderr, "add_relation(%d, %s) - Failed, but op_from (%s) was ok\n", + type, description, key_from.identifier().c_str()); + } + if (!op_to) { + /* XXX TODO handle as error or report if needed */ + fprintf(stderr, "add_relation(%d, %s) - Could not find op_to (%s)\n", + type, description, key_to.identifier().c_str()); + } + else { + fprintf(stderr, "add_relation(%d, %s) - Failed, but op_to (%s) was ok\n", + type, description, key_to.identifier().c_str()); + } + } +} + +template <typename KeyTo> +void DepsgraphRelationBuilder::add_relation(const TimeSourceKey &key_from, + const KeyTo &key_to, + eDepsRelation_Type type, + const char *description) +{ + (void)type; /* Ignored in release builds. */ + BLI_assert(type == DEPSREL_TYPE_TIME); + TimeSourceDepsNode *time_from = find_node(key_from); + DepsNode *node_to = find_node(key_to); + OperationDepsNode *op_to = node_to ? node_to->get_entry_operation() : NULL; + if (time_from && op_to) { + add_time_relation(time_from, op_to, description); + } + else { + } +} + +template <typename KeyType> +void DepsgraphRelationBuilder::add_node_handle_relation(const KeyType &key_from, + const DepsNodeHandle *handle, + eDepsRelation_Type type, + const char *description) +{ + DepsNode *node_from = find_node(key_from); + OperationDepsNode *op_from = node_from ? node_from->get_exit_operation() : NULL; + OperationDepsNode *op_to = handle->node->get_entry_operation(); + if (op_from && op_to) { + add_operation_relation(op_from, op_to, type, description); + } + else { + if (!op_from) { + /* XXX TODO handle as error or report if needed */ + } + if (!op_to) { + /* XXX TODO handle as error or report if needed */ + } + } +} + +template <typename KeyType> +DepsNodeHandle DepsgraphRelationBuilder::create_node_handle(const KeyType &key, + const string &default_name) +{ + return DepsNodeHandle(this, find_node(key), default_name); +} + +#endif /* __DEPSGRAPH_BUILD_H__ */ diff --git a/source/blender/depsgraph/intern/depsgraph_build_nodes.cc b/source/blender/depsgraph/intern/depsgraph_build_nodes.cc new file mode 100644 index 00000000000..c9d2ed35e17 --- /dev/null +++ b/source/blender/depsgraph/intern/depsgraph_build_nodes.cc @@ -0,0 +1,1201 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): Based on original depsgraph.c code - Blender Foundation (2005-2013) + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph_build_nodes.cc + * \ingroup depsgraph + * + * Methods for constructing depsgraph's nodes + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "MEM_guardedalloc.h" + +extern "C" { +#include "BLI_blenlib.h" +#include "BLI_string.h" +#include "BLI_utildefines.h" + +#include "DNA_action_types.h" +#include "DNA_anim_types.h" +#include "DNA_armature_types.h" +#include "DNA_camera_types.h" +#include "DNA_constraint_types.h" +#include "DNA_curve_types.h" +#include "DNA_effect_types.h" +#include "DNA_gpencil_types.h" +#include "DNA_group_types.h" +#include "DNA_key_types.h" +#include "DNA_lamp_types.h" +#include "DNA_material_types.h" +#include "DNA_mesh_types.h" +#include "DNA_meta_types.h" +#include "DNA_node_types.h" +#include "DNA_particle_types.h" +#include "DNA_object_types.h" +#include "DNA_rigidbody_types.h" +#include "DNA_scene_types.h" +#include "DNA_texture_types.h" +#include "DNA_world_types.h" + +#include "BKE_action.h" +#include "BKE_armature.h" +#include "BKE_animsys.h" +#include "BKE_constraint.h" +#include "BKE_curve.h" +#include "BKE_depsgraph.h" +#include "BKE_effect.h" +#include "BKE_fcurve.h" +#include "BKE_idcode.h" +#include "BKE_group.h" +#include "BKE_key.h" +#include "BKE_lattice.h" +#include "BKE_library.h" +#include "BKE_main.h" +#include "BKE_material.h" +#include "BKE_mesh.h" +#include "BKE_mball.h" +#include "BKE_modifier.h" +#include "BKE_node.h" +#include "BKE_object.h" +#include "BKE_particle.h" +#include "BKE_rigidbody.h" +#include "BKE_sound.h" +#include "BKE_texture.h" +#include "BKE_tracking.h" +#include "BKE_world.h" + +#include "DEG_depsgraph.h" +#include "DEG_depsgraph_build.h" + +#include "RNA_access.h" +#include "RNA_types.h" +} /* extern "C" */ + +#include "depsnode.h" +#include "depsnode_component.h" +#include "depsnode_operation.h" +#include "depsgraph_types.h" +#include "depsgraph_build.h" +#include "depsgraph_intern.h" + +/* ************ */ +/* Node Builder */ + +/* **** General purpose functions **** */ + +DepsgraphNodeBuilder::DepsgraphNodeBuilder(Main *bmain, Depsgraph *graph) : + m_bmain(bmain), + m_graph(graph) +{ +} + +DepsgraphNodeBuilder::~DepsgraphNodeBuilder() +{ +} + +RootDepsNode *DepsgraphNodeBuilder::add_root_node() +{ + return m_graph->add_root_node(); +} + +IDDepsNode *DepsgraphNodeBuilder::add_id_node(ID *id) +{ + const char *idtype_name = BKE_idcode_to_name(GS(id->name)); + return m_graph->add_id_node(id, string(id->name + 2) + "[" + idtype_name + "]"); +} + +TimeSourceDepsNode *DepsgraphNodeBuilder::add_time_source(ID *id) +{ + /* determine which node to attach timesource to */ + if (id) { +#if 0 /* XXX TODO */ + /* get ID node */ + IDDepsNode id_node = m_graph->find_id_node(id); + + /* depends on what this is... */ + switch (GS(id->name)) { + case ID_SCE: /* Scene - Usually sequencer strip causing time remapping... */ + { + // TODO... + } + break; + + case ID_GR: /* Group */ + { + // TODO... + } + break; + + // XXX: time source... + + default: /* Unhandled */ + printf("%s(): Unhandled ID - %s \n", __func__, id->name); + break; + } +#endif + } + else { + /* root-node */ + RootDepsNode *root_node = m_graph->root_node; + if (root_node) { + return root_node->add_time_source("Time Source"); + } + } + + return NULL; +} + +ComponentDepsNode *DepsgraphNodeBuilder::add_component_node( + ID *id, + eDepsNode_Type comp_type, + const string &comp_name) +{ + IDDepsNode *id_node = add_id_node(id); + ComponentDepsNode *comp_node = id_node->add_component(comp_type, comp_name); + comp_node->owner = id_node; + return comp_node; +} + +OperationDepsNode *DepsgraphNodeBuilder::add_operation_node( + ComponentDepsNode *comp_node, + eDepsOperation_Type optype, + DepsEvalOperationCb op, + eDepsOperation_Code opcode, + const string &description) +{ + OperationDepsNode *op_node = comp_node->has_operation(opcode, description); + if (op_node == NULL) { + op_node = comp_node->add_operation(optype, op, opcode, description); + m_graph->operations.push_back(op_node); + } + else { + fprintf(stderr, "add_operation: Operation already exists - %s has %s at %p\n", + comp_node->identifier().c_str(), + op_node->identifier().c_str(), + op_node); + BLI_assert(!"Should not happen!"); + } + return op_node; +} + +OperationDepsNode *DepsgraphNodeBuilder::add_operation_node( + ID *id, + eDepsNode_Type comp_type, + const string &comp_name, + eDepsOperation_Type optype, + DepsEvalOperationCb op, + eDepsOperation_Code opcode, + const string &description) +{ + ComponentDepsNode *comp_node = add_component_node(id, comp_type, comp_name); + return add_operation_node(comp_node, optype, op, opcode, description); +} + +bool DepsgraphNodeBuilder::has_operation_node(ID *id, + eDepsNode_Type comp_type, + const string &comp_name, + eDepsOperation_Code opcode, + const string &description) +{ + return find_operation_node(id, comp_type, comp_name, opcode, description) != NULL; +} + +OperationDepsNode *DepsgraphNodeBuilder::find_operation_node( + ID *id, + eDepsNode_Type comp_type, + const string &comp_name, + eDepsOperation_Code opcode, + const string &description) +{ + ComponentDepsNode *comp_node = add_component_node(id, comp_type, comp_name); + return comp_node->has_operation(opcode, description); +} + + +/* **** Build functions for entity nodes **** */ + +void DepsgraphNodeBuilder::build_scene(Main *bmain, Scene *scene) +{ + /* LIB_DOIT is used to indicate whether node for given ID was already + * created or not. This flag is being set in add_id_node(), so functions + * shouldn't bother with setting it, they only might query this flag when + * needed. + */ + BKE_main_id_tag_all(bmain, false); + + /* scene ID block */ + add_id_node(&scene->id); + + /* timesource */ + add_time_source(NULL); + + /* build subgraph for set, and link this in... */ + // XXX: depending on how this goes, that scene itself could probably store its + // own little partial depsgraph? + if (scene->set) { + build_scene(bmain, scene->set); + } + + /* scene objects */ + for (Base *base = (Base *)scene->base.first; base; base = base->next) { + Object *ob = base->object; + + /* object itself */ + build_object(scene, base, ob); + + /* object that this is a proxy for */ + // XXX: the way that proxies work needs to be completely reviewed! + if (ob->proxy) { + build_object(scene, base, ob->proxy); + } + + /* Object dupligroup. */ + if (ob->dup_group) { + build_group(scene, base, ob->dup_group); + } + } + + /* rigidbody */ + if (scene->rigidbody_world) { + build_rigidbody(scene); + } + + /* scene's animation and drivers */ + if (scene->adt) { + build_animdata(&scene->id); + } + + /* world */ + if (scene->world) { + build_world(scene->world); + } + + /* compo nodes */ + if (scene->nodetree) { + build_compositor(scene); + } + + /* sequencer */ + // XXX... + + /* grease pencil */ + if (scene->gpd) { + build_gpencil(scene->gpd); + } +} + +void DepsgraphNodeBuilder::build_group(Scene *scene, + Base *base, + Group *group) +{ + ID *group_id = &group->id; + if (group_id->flag & LIB_DOIT) { + return; + } + group_id->flag |= LIB_DOIT; + + for (GroupObject *go = (GroupObject *)group->gobject.first; + go != NULL; + go = go->next) + { + build_object(scene, base, go->ob); + } +} + +SubgraphDepsNode *DepsgraphNodeBuilder::build_subgraph(Group *group) +{ + /* sanity checks */ + if (!group) + return NULL; + + /* create new subgraph's data */ + Depsgraph *subgraph = DEG_graph_new(); + + DepsgraphNodeBuilder subgraph_builder(m_bmain, subgraph); + + /* add group objects */ + for (GroupObject *go = (GroupObject *)group->gobject.first; + go != NULL; + go = go->next) + { + /*Object *ob = go->ob;*/ + + /* Each "group object" is effectively a separate instance of the underlying + * object data. When the group is evaluated, the transform results and/or + * some other attributes end up getting overridden by the group + */ + } + + /* create a node for representing subgraph */ + SubgraphDepsNode *subgraph_node = m_graph->add_subgraph_node(&group->id); + subgraph_node->graph = subgraph; + + /* make a copy of the data this node will need? */ + // XXX: do we do this now, or later? + // TODO: need API function which queries graph's ID's hash, and duplicates those blocks thoroughly with all outside links removed... + + return subgraph_node; +} + +void DepsgraphNodeBuilder::build_object(Scene *scene, Base *base, Object *ob) +{ + if (ob->id.flag & LIB_DOIT) { + IDDepsNode *id_node = m_graph->find_id_node(&ob->id); + id_node->layers = base->lay; + return; + } + + IDDepsNode *id_node = add_id_node(&ob->id); + id_node->layers = base->lay; + + /* standard components */ + build_object_transform(scene, ob); + + + /* object data */ + if (ob->data) { + /* type-specific data... */ + switch (ob->type) { + case OB_MESH: /* Geometry */ + case OB_CURVE: + case OB_FONT: + case OB_SURF: + case OB_MBALL: + case OB_LATTICE: + { + /* TODO(sergey): This way using this object's + * properties as driver target works fine. + * + * Does this depend on other nodes? + */ + add_operation_node(&ob->id, DEPSNODE_TYPE_PARAMETERS, DEPSOP_TYPE_POST, NULL, + DEG_OPCODE_PLACEHOLDER, "Parameters Eval"); + + build_obdata_geom(scene, ob); + /* TODO(sergey): Only for until we support granular + * update of curves. + */ + if (ob->type == OB_FONT) { + Curve *curve = (Curve *)ob->data; + if (curve->textoncurve) { + id_node->eval_flags |= DAG_EVAL_NEED_CURVE_PATH; + } + } + break; + } + + case OB_ARMATURE: /* Pose */ + if (ob->id.lib != NULL && ob->proxy_from != NULL) { + build_proxy_rig(ob); + } + else { + build_rig(scene, ob); + } + break; + + case OB_LAMP: /* Lamp */ + build_lamp(ob); + break; + + case OB_CAMERA: /* Camera */ + build_camera(ob); + break; + + default: + { + ID *obdata = (ID *)ob->data; + if ((obdata->flag & LIB_DOIT) == 0) { + build_animdata(obdata); + } + break; + } + } + } + + /* Build animation data, + * + * Do it now because it's possible object data will affect + * on object's level animation, for example in case of rebuilding + * pose for proxy. + */ + build_animdata(&ob->id); + + /* particle systems */ + if (ob->particlesystem.first) { + build_particles(ob); + } + + /* grease pencil */ + if (ob->gpd) { + build_gpencil(ob->gpd); + } +} + +void DepsgraphNodeBuilder::build_object_transform(Scene *scene, Object *ob) +{ + /* local transforms (from transform channels - loc/rot/scale + deltas) */ + add_operation_node(&ob->id, DEPSNODE_TYPE_TRANSFORM, + DEPSOP_TYPE_INIT, function_bind(BKE_object_eval_local_transform, _1, scene, ob), + DEG_OPCODE_TRANSFORM_LOCAL); + + /* object parent */ + if (ob->parent) { + add_operation_node(&ob->id, DEPSNODE_TYPE_TRANSFORM, + DEPSOP_TYPE_EXEC, function_bind(BKE_object_eval_parent, _1, scene, ob), + DEG_OPCODE_TRANSFORM_PARENT); + } + + /* object constraints */ + if (ob->constraints.first) { + build_object_constraints(scene, ob); + } + + /* Temporary uber-update node, which does everything. + * It is for the being we're porting old dependencies into the new system. + * We'll get rid of this node as soon as all the granular update functions + * are filled in. + * + * TODO(sergey): Get rid of this node. + */ + add_operation_node(&ob->id, DEPSNODE_TYPE_TRANSFORM, + DEPSOP_TYPE_EXEC, function_bind(BKE_object_eval_uber_transform, _1, scene, ob), + DEG_OPCODE_OBJECT_UBEREVAL); + + /* object transform is done */ + add_operation_node(&ob->id, DEPSNODE_TYPE_TRANSFORM, + DEPSOP_TYPE_POST, function_bind(BKE_object_eval_done, _1, ob), + DEG_OPCODE_TRANSFORM_FINAL); +} + +/** + * Constraints Graph Notes + * + * For constraints, we currently only add a operation node to the Transform + * or Bone components (depending on whichever type of owner we have). + * This represents the entire constraints stack, which is for now just + * executed as a single monolithic block. At least initially, this should + * be sufficient for ensuring that the porting/refactoring process remains + * manageable. + * + * However, when the time comes for developing "node-based" constraints, + * we'll need to split this up into pre/post nodes for "constraint stack + * evaluation" + operation nodes for each constraint (i.e. the contents + * of the loop body used in the current "solve_constraints()" operation). + * + * -- Aligorith, August 2013 + */ +void DepsgraphNodeBuilder::build_object_constraints(Scene *scene, Object *ob) +{ + /* create node for constraint stack */ + add_operation_node(&ob->id, DEPSNODE_TYPE_TRANSFORM, + DEPSOP_TYPE_EXEC, function_bind(BKE_object_eval_constraints, _1, scene, ob), + DEG_OPCODE_TRANSFORM_CONSTRAINTS); +} + +void DepsgraphNodeBuilder::build_pose_constraints(Object *ob, bPoseChannel *pchan) +{ + /* create node for constraint stack */ + add_operation_node(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, + DEPSOP_TYPE_EXEC, function_bind(BKE_pose_constraints_evaluate, _1, ob, pchan), + DEG_OPCODE_BONE_CONSTRAINTS); +} + +/** + * Build graph nodes for AnimData block + * \param id: ID-Block which hosts the AnimData + */ +void DepsgraphNodeBuilder::build_animdata(ID *id) +{ + AnimData *adt = BKE_animdata_from_id(id); + + if (adt == NULL) + return; + + /* animation */ + if (adt->action || adt->nla_tracks.first || adt->drivers.first) { + // XXX: Hook up specific update callbacks for special properties which may need it... + + /* actions and NLA - as a single unit for now, as it gets complicated to schedule otherwise */ + if ((adt->action) || (adt->nla_tracks.first)) { + /* create the node */ + add_operation_node(id, DEPSNODE_TYPE_ANIMATION, + DEPSOP_TYPE_EXEC, function_bind(BKE_animsys_eval_animdata, _1, id), + DEG_OPCODE_ANIMATION, id->name); + + // TODO: for each channel affected, we might also want to add some support for running RNA update callbacks on them + // (which will be needed for proper handling of drivers later) + } + + /* drivers */ + for (FCurve *fcu = (FCurve *)adt->drivers.first; fcu; fcu = fcu->next) { + /* create driver */ + build_driver(id, fcu); + } + } +} + +/** + * Build graph node(s) for Driver + * \param id: ID-Block that driver is attached to + * \param fcu: Driver-FCurve + */ +OperationDepsNode *DepsgraphNodeBuilder::build_driver(ID *id, FCurve *fcu) +{ + ChannelDriver *driver = fcu->driver; + + /* Create data node for this driver */ + /* TODO(sergey): Avoid creating same operation multiple times, + * in the future we need to avoid lookup of the operation as well + * and use some tagging magic instead. + */ + OperationDepsNode *driver_op = find_operation_node(id, + DEPSNODE_TYPE_PARAMETERS, + DEG_OPCODE_DRIVER, + deg_fcurve_id_name(fcu)); + + if (driver_op == NULL) { + driver_op = add_operation_node(id, DEPSNODE_TYPE_PARAMETERS, + DEPSOP_TYPE_EXEC, function_bind(BKE_animsys_eval_driver, _1, id, fcu), + DEG_OPCODE_DRIVER, deg_fcurve_id_name(fcu)); + } + + /* tag "scripted expression" drivers as needing Python (due to GIL issues, etc.) */ + if (driver->type == DRIVER_TYPE_PYTHON) { + driver_op->flag |= DEPSOP_FLAG_USES_PYTHON; + } + + /* return driver node created */ + return driver_op; +} + +/* Recursively build graph for world */ +void DepsgraphNodeBuilder::build_world(World *world) +{ + ID *world_id = &world->id; + if (world_id->flag & LIB_DOIT) { + return; + } + + /* world itself */ + IDDepsNode *world_node = add_id_node(world_id); /* world shading/params? */ + + build_animdata(world_id); + + /* TODO: other settings? */ + + /* textures */ + build_texture_stack(world_node, world->mtex); + + /* world's nodetree */ + if (world->nodetree) { + build_nodetree(world_node, world->nodetree); + } +} + +/* Rigidbody Simulation - Scene Level */ +void DepsgraphNodeBuilder::build_rigidbody(Scene *scene) +{ + RigidBodyWorld *rbw = scene->rigidbody_world; + + /** + * Rigidbody Simulation Nodes + * ========================== + * + * There are 3 nodes related to Rigidbody Simulation: + * 1) "Initialize/Rebuild World" - this is called sparingly, only when the simulation + * needs to be rebuilt (mainly after file reload, or moving back to start frame) + * 2) "Do Simulation" - perform a simulation step - interleaved between the evaluation + * steps for clusters of objects (i.e. between those affected and/or not affected by + * the sim for instance) + * + * 3) "Pull Results" - grab the specific transforms applied for a specific object - + * performed as part of object's transform-stack building + */ + + /* create nodes ------------------------------------------------------------------------ */ + /* XXX: is this the right component, or do we want to use another one instead? */ + + /* init/rebuild operation */ + /*OperationDepsNode *init_node =*/ add_operation_node(&scene->id, DEPSNODE_TYPE_TRANSFORM, + DEPSOP_TYPE_REBUILD, function_bind(BKE_rigidbody_rebuild_sim, _1, scene), + DEG_OPCODE_RIGIDBODY_REBUILD); + + /* do-sim operation */ + // XXX: what happens if we need to split into several groups? + OperationDepsNode *sim_node = add_operation_node(&scene->id, DEPSNODE_TYPE_TRANSFORM, + DEPSOP_TYPE_SIM, function_bind(BKE_rigidbody_eval_simulation, _1, scene), + DEG_OPCODE_RIGIDBODY_SIM); + + /* XXX: For now, the sim node is the only one that really matters here. If any other + * sims get added later, we may have to remove these hacks... + */ + sim_node->owner->entry_operation = sim_node; + sim_node->owner->exit_operation = sim_node; + + + /* objects - simulation participants */ + if (rbw->group) { + for (GroupObject *go = (GroupObject *)rbw->group->gobject.first; go; go = go->next) { + Object *ob = go->ob; + + if (!ob || (ob->type != OB_MESH)) + continue; + + /* 2) create operation for flushing results */ + /* object's transform component - where the rigidbody operation lives */ + add_operation_node(&ob->id, DEPSNODE_TYPE_TRANSFORM, + DEPSOP_TYPE_EXEC, function_bind(BKE_rigidbody_object_sync_transforms, _1, scene, ob), + DEG_OPCODE_TRANSFORM_RIGIDBODY); + } + } +} + +void DepsgraphNodeBuilder::build_particles(Object *ob) +{ + /** + * Particle Systems Nodes + * ====================== + * + * There are two types of nodes associated with representing + * particle systems: + * 1) Component (EVAL_PARTICLES) - This is the particle-system + * evaluation context for an object. It acts as the container + * for all the nodes associated with a particular set of particle + * systems. + * 2) Particle System Eval Operation - This operation node acts as a + * blackbox evaluation step for one particle system referenced by + * the particle systems stack. All dependencies link to this operation. + */ + + /* component for all particle systems */ + ComponentDepsNode *psys_comp = add_component_node(&ob->id, DEPSNODE_TYPE_EVAL_PARTICLES); + + /* particle systems */ + for (ParticleSystem *psys = (ParticleSystem *)ob->particlesystem.first; psys; psys = psys->next) { + ParticleSettings *part = psys->part; + + /* particle settings */ + // XXX: what if this is used more than once! + build_animdata(&part->id); + + /* this particle system */ + // TODO: for now, this will just be a placeholder "ubereval" node + add_operation_node(psys_comp, + DEPSOP_TYPE_EXEC, function_bind(BKE_particle_system_eval, _1, ob, psys), + DEG_OPCODE_PSYS_EVAL, + psys->name); + } + + /* pointcache */ + // TODO... +} + +/* IK Solver Eval Steps */ +void DepsgraphNodeBuilder::build_ik_pose(Scene *scene, Object *ob, bPoseChannel *pchan, bConstraint *con) +{ + bKinematicConstraint *data = (bKinematicConstraint *)con->data; + + /* Find the chain's root. */ + bPoseChannel *rootchan = BKE_armature_ik_solver_find_root(pchan, data); + + if (has_operation_node(&ob->id, DEPSNODE_TYPE_EVAL_POSE, rootchan->name, + DEG_OPCODE_POSE_IK_SOLVER)) + { + return; + } + + /* Operation node for evaluating/running IK Solver. */ + add_operation_node(&ob->id, DEPSNODE_TYPE_EVAL_POSE, rootchan->name, + DEPSOP_TYPE_SIM, function_bind(BKE_pose_iktree_evaluate, _1, scene, ob, rootchan), + DEG_OPCODE_POSE_IK_SOLVER); +} + +/* Spline IK Eval Steps */ +void DepsgraphNodeBuilder::build_splineik_pose(Scene *scene, Object *ob, bPoseChannel *pchan, bConstraint *con) +{ + bSplineIKConstraint *data = (bSplineIKConstraint *)con->data; + + /* Find the chain's root. */ + bPoseChannel *rootchan = BKE_armature_splineik_solver_find_root(pchan, data); + + /* Operation node for evaluating/running Spline IK Solver. + * Store the "root bone" of this chain in the solver, so it knows where to start. + */ + add_operation_node(&ob->id, DEPSNODE_TYPE_EVAL_POSE, rootchan->name, + DEPSOP_TYPE_SIM, function_bind(BKE_pose_splineik_evaluate, _1, scene, ob, rootchan), + DEG_OPCODE_POSE_SPLINE_IK_SOLVER); +} + +/* Pose/Armature Bones Graph */ +void DepsgraphNodeBuilder::build_rig(Scene *scene, Object *ob) +{ + bArmature *arm = (bArmature *)ob->data; + + /* animation and/or drivers linking posebones to base-armature used to define them + * NOTE: AnimData here is really used to control animated deform properties, + * which ideally should be able to be unique across different instances. + * Eventually, we need some type of proxy/isolation mechanism in-between here + * to ensure that we can use same rig multiple times in same scene... + */ + build_animdata(&arm->id); + + /* Rebuild pose if not up to date. */ + if (ob->pose == NULL || (ob->pose->flag & POSE_RECALC)) { + BKE_pose_rebuild(ob, arm); + /* XXX: Without this animation gets lost in certain circumstances + * after loading file. Need to investigate further since it does + * not happen with simple scenes.. + */ + if (ob->adt) { + ob->adt->recalc |= ADT_RECALC_ANIM; + } + } + + /** + * Pose Rig Graph + * ============== + * + * Pose Component: + * - Mainly used for referencing Bone components. + * - This is where the evaluation operations for init/exec/cleanup + * (ik) solvers live, and are later hooked up (so that they can be + * interleaved during runtime) with bone-operations they depend on/affect. + * - init_pose_eval() and cleanup_pose_eval() are absolute first and last + * steps of pose eval process. ALL bone operations must be performed + * between these two... + * + * Bone Component: + * - Used for representing each bone within the rig + * - Acts to encapsulate the evaluation operations (base matrix + parenting, + * and constraint stack) so that they can be easily found. + * - Everything else which depends on bone-results hook up to the component only + * so that we can redirect those to point at either the the post-IK/ + * post-constraint/post-matrix steps, as needed. + */ + + /* pose eval context */ + add_operation_node(&ob->id, DEPSNODE_TYPE_EVAL_POSE, + DEPSOP_TYPE_INIT, function_bind(BKE_pose_eval_init, _1, scene, ob, ob->pose), DEG_OPCODE_POSE_INIT); + + add_operation_node(&ob->id, DEPSNODE_TYPE_EVAL_POSE, + DEPSOP_TYPE_POST, function_bind(BKE_pose_eval_flush, _1, scene, ob, ob->pose), DEG_OPCODE_POSE_DONE); + + /* bones */ + for (bPoseChannel *pchan = (bPoseChannel *)ob->pose->chanbase.first; pchan; pchan = pchan->next) { + /* node for bone eval */ + add_operation_node(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, + DEPSOP_TYPE_INIT, NULL, // XXX: BKE_pose_eval_bone_local + DEG_OPCODE_BONE_LOCAL); + + add_operation_node(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, + DEPSOP_TYPE_EXEC, function_bind(BKE_pose_eval_bone, _1, scene, ob, pchan), // XXX: BKE_pose_eval_bone_pose + DEG_OPCODE_BONE_POSE_PARENT); + + add_operation_node(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, + DEPSOP_TYPE_OUT, NULL, /* NOTE: dedicated noop for easier relationship construction */ + DEG_OPCODE_BONE_READY); + + add_operation_node(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, + DEPSOP_TYPE_POST, function_bind(BKE_pose_bone_done, _1, pchan), + DEG_OPCODE_BONE_DONE); + + /* constraints */ + if (pchan->constraints.first != NULL) { + build_pose_constraints(ob, pchan); + } + + /** + * IK Solvers... + * + * - These require separate processing steps are pose-level + * to be executed between chains of bones (i.e. once the + * base transforms of a bunch of bones is done) + * + * Unsolved Issues: + * - Care is needed to ensure that multi-headed trees work out the same as in ik-tree building + * - Animated chain-lengths are a problem... + */ + for (bConstraint *con = (bConstraint *)pchan->constraints.first; con; con = con->next) { + switch (con->type) { + case CONSTRAINT_TYPE_KINEMATIC: + build_ik_pose(scene, ob, pchan, con); + break; + + case CONSTRAINT_TYPE_SPLINEIK: + build_splineik_pose(scene, ob, pchan, con); + break; + + default: + break; + } + } + } +} + +void DepsgraphNodeBuilder::build_proxy_rig(Object *ob) +{ + ID *obdata = (ID *)ob->data; + build_animdata(obdata); + + add_operation_node(&ob->id, + DEPSNODE_TYPE_EVAL_POSE, + DEPSOP_TYPE_INIT, + function_bind(BKE_pose_eval_proxy_copy, _1, ob), + DEG_OPCODE_POSE_INIT); + + for (bPoseChannel *pchan = (bPoseChannel *)ob->pose->chanbase.first; + pchan != NULL; + pchan = pchan->next) + { + add_operation_node(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, + DEPSOP_TYPE_INIT, NULL, + DEG_OPCODE_BONE_LOCAL); + + add_operation_node(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, + DEPSOP_TYPE_EXEC, NULL, + DEG_OPCODE_BONE_READY); + + add_operation_node(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, + DEPSOP_TYPE_POST, NULL, + DEG_OPCODE_BONE_DONE); + } + + add_operation_node(&ob->id, + DEPSNODE_TYPE_EVAL_POSE, + DEPSOP_TYPE_POST, + NULL, + DEG_OPCODE_POSE_DONE); +} + +/* Shapekeys */ +void DepsgraphNodeBuilder::build_shapekeys(Key *key) +{ + build_animdata(&key->id); +} + +/* ObData Geometry Evaluation */ +// XXX: what happens if the datablock is shared! +void DepsgraphNodeBuilder::build_obdata_geom(Scene *scene, Object *ob) +{ + ID *obdata = (ID *)ob->data; + + /* Temporary uber-update node, which does everything. + * It is for the being we're porting old dependencies into the new system. + * We'll get rid of this node as soon as all the granular update functions + * are filled in. + * + * TODO(sergey): Get rid of this node. + */ + add_operation_node(&ob->id, DEPSNODE_TYPE_GEOMETRY, + DEPSOP_TYPE_POST, function_bind(BKE_object_eval_uber_data, _1, scene, ob), + DEG_OPCODE_GEOMETRY_UBEREVAL); + + add_operation_node(&ob->id, DEPSNODE_TYPE_GEOMETRY, + DEPSOP_TYPE_INIT, NULL, + DEG_OPCODE_PLACEHOLDER, "Eval Init"); + + // TODO: "Done" operation + + /* ShapeKeys */ + Key *key = BKE_key_from_object(ob); + if (key) + build_shapekeys(key); + + /* Modifiers */ + if (ob->modifiers.first) { + ModifierData *md; + + for (md = (ModifierData *)ob->modifiers.first; md; md = md->next) { + add_operation_node(&ob->id, DEPSNODE_TYPE_GEOMETRY, + DEPSOP_TYPE_EXEC, function_bind(BKE_object_eval_modifier, _1, scene, ob, md), + DEG_OPCODE_GEOMETRY_MODIFIER, md->name); + } + } + + /* materials */ + if (ob->totcol) { + int a; + + for (a = 1; a <= ob->totcol; a++) { + Material *ma = give_current_material(ob, a); + + if (ma) { + // XXX?! + ComponentDepsNode *geom_node = add_component_node(&ob->id, DEPSNODE_TYPE_GEOMETRY); + build_material(geom_node, ma); + } + } + } + + /* geometry collision */ + if (ELEM(ob->type, OB_MESH, OB_CURVE, OB_LATTICE)) { + // add geometry collider relations + } + + if (obdata->flag & LIB_DOIT) { + return; + } + + build_animdata(obdata); + + /* nodes for result of obdata's evaluation, and geometry evaluation on object */ + switch (ob->type) { + case OB_MESH: + { + //Mesh *me = (Mesh *)ob->data; + + /* evaluation operations */ + add_operation_node(obdata, DEPSNODE_TYPE_GEOMETRY, + DEPSOP_TYPE_INIT, function_bind(BKE_mesh_eval_geometry, _1, (Mesh *)obdata), + DEG_OPCODE_PLACEHOLDER, "Geometry Eval"); + break; + } + + case OB_MBALL: + { + Object *mom = BKE_mball_basis_find(scene, ob); + + /* motherball - mom depends on children! */ + if (mom == ob) { + /* metaball evaluation operations */ + /* NOTE: only the motherball gets evaluated! */ + add_operation_node(obdata, DEPSNODE_TYPE_GEOMETRY, + DEPSOP_TYPE_INIT, function_bind(BKE_mball_eval_geometry, _1, (MetaBall *)obdata), + DEG_OPCODE_PLACEHOLDER, "Geometry Eval"); + } + break; + } + + case OB_CURVE: + case OB_FONT: + { + /* curve evaluation operations */ + /* - calculate curve geometry (including path) */ + add_operation_node(obdata, DEPSNODE_TYPE_GEOMETRY, + DEPSOP_TYPE_INIT, function_bind(BKE_curve_eval_geometry, _1, (Curve *)obdata), + DEG_OPCODE_PLACEHOLDER, "Geometry Eval"); + + /* - calculate curve path - this is used by constraints, etc. */ + add_operation_node(obdata, DEPSNODE_TYPE_GEOMETRY, + DEPSOP_TYPE_EXEC, function_bind(BKE_curve_eval_path, _1, (Curve *)obdata), + DEG_OPCODE_GEOMETRY_PATH, "Path"); + break; + } + + case OB_SURF: /* Nurbs Surface */ + { + /* nurbs evaluation operations */ + add_operation_node(obdata, DEPSNODE_TYPE_GEOMETRY, + DEPSOP_TYPE_INIT, function_bind(BKE_curve_eval_geometry, _1, (Curve *)obdata), + DEG_OPCODE_PLACEHOLDER, "Geometry Eval"); + break; + } + + case OB_LATTICE: /* Lattice */ + { + /* lattice evaluation operations */ + add_operation_node(obdata, DEPSNODE_TYPE_GEOMETRY, + DEPSOP_TYPE_INIT, function_bind(BKE_lattice_eval_geometry, _1, (Lattice *)obdata), + DEG_OPCODE_PLACEHOLDER, "Geometry Eval"); + break; + } + } + + add_operation_node(obdata, DEPSNODE_TYPE_GEOMETRY, + DEPSOP_TYPE_POST, NULL, + DEG_OPCODE_PLACEHOLDER, "Eval Done"); + + /* Parameters for driver sources. */ + add_operation_node(obdata, DEPSNODE_TYPE_PARAMETERS, DEPSOP_TYPE_EXEC, NULL, + DEG_OPCODE_PLACEHOLDER, "Parameters Eval"); +} + +/* Cameras */ +void DepsgraphNodeBuilder::build_camera(Object *ob) +{ + /* TODO: Link scene-camera links in somehow... */ + Camera *cam = (Camera *)ob->data; + ID *camera_id = &cam->id; + if (camera_id->flag & LIB_DOIT) { + return; + } + + build_animdata(&cam->id); + + add_operation_node(camera_id, DEPSNODE_TYPE_PARAMETERS, DEPSOP_TYPE_EXEC, NULL, + DEG_OPCODE_PLACEHOLDER, "Parameters Eval"); + + if (cam->dof_ob != NULL) { + /* TODO(sergey): For now parametrs are on object level. */ + add_operation_node(&ob->id, DEPSNODE_TYPE_PARAMETERS, + DEPSOP_TYPE_EXEC, NULL, + DEG_OPCODE_PLACEHOLDER, + "Camera DOF"); + } +} + +/* Lamps */ +void DepsgraphNodeBuilder::build_lamp(Object *ob) +{ + Lamp *la = (Lamp *)ob->data; + ID *lamp_id = &la->id; + if (lamp_id->flag & LIB_DOIT) { + return; + } + + build_animdata(&la->id); + + /* node for obdata */ + ComponentDepsNode *param_node = add_component_node(lamp_id, DEPSNODE_TYPE_PARAMETERS); + + /* TODO(sergey): Is it really how we're supposed to work with drivers? */ + add_operation_node(lamp_id, DEPSNODE_TYPE_PARAMETERS, DEPSOP_TYPE_EXEC, NULL, + DEG_OPCODE_PLACEHOLDER, "Parameters Eval"); + + /* lamp's nodetree */ + if (la->nodetree) { + build_nodetree(param_node, la->nodetree); + } + + /* textures */ + build_texture_stack(param_node, la->mtex); +} + +void DepsgraphNodeBuilder::build_nodetree(DepsNode *owner_node, bNodeTree *ntree) +{ + if (!ntree) + return; + + /* nodetree itself */ + ID *ntree_id = &ntree->id; + + build_animdata(ntree_id); + + /* Parameters for drivers. */ + add_operation_node(ntree_id, DEPSNODE_TYPE_PARAMETERS, DEPSOP_TYPE_EXEC, NULL, + DEG_OPCODE_PLACEHOLDER, "Parameters Eval"); + + /* nodetree's nodes... */ + for (bNode *bnode = (bNode *)ntree->nodes.first; bnode; bnode = bnode->next) { + if (bnode->id) { + if (GS(bnode->id->name) == ID_MA) { + build_material(owner_node, (Material *)bnode->id); + } + else if (bnode->type == ID_TE) { + build_texture(owner_node, (Tex *)bnode->id); + } + else if (bnode->type == NODE_GROUP) { + bNodeTree *ntree = (bNodeTree *)bnode->id; + if ((ntree_id->flag & LIB_DOIT) == 0) { + build_nodetree(owner_node, ntree); + } + } + } + } + + // TODO: link from nodetree to owner_component? +} + +/* Recursively build graph for material */ +void DepsgraphNodeBuilder::build_material(DepsNode *owner_node, Material *ma) +{ + ID *ma_id = &ma->id; + if (ma_id->flag & LIB_DOIT) { + return; + } + + /* material itself */ + add_id_node(ma_id); + + add_operation_node(ma_id, DEPSNODE_TYPE_SHADING, + DEPSOP_TYPE_EXEC, NULL, + DEG_OPCODE_PLACEHOLDER, "Material Update"); + + /* material animation */ + build_animdata(ma_id); + + /* textures */ + build_texture_stack(owner_node, ma->mtex); + + /* material's nodetree */ + build_nodetree(owner_node, ma->nodetree); +} + +/* Texture-stack attached to some shading datablock */ +void DepsgraphNodeBuilder::build_texture_stack(DepsNode *owner_node, MTex **texture_stack) +{ + int i; + + /* for now assume that all texture-stacks have same number of max items */ + for (i = 0; i < MAX_MTEX; i++) { + MTex *mtex = texture_stack[i]; + if (mtex && mtex->tex) + build_texture(owner_node, mtex->tex); + } +} + +/* Recursively build graph for texture */ +void DepsgraphNodeBuilder::build_texture(DepsNode *owner_node, Tex *tex) +{ + ID *tex_id = &tex->id; + if (tex_id->flag & LIB_DOIT) { + return; + } + tex_id->flag |= LIB_DOIT; + /* texture itself */ + build_animdata(tex_id); + /* texture's nodetree */ + build_nodetree(owner_node, tex->nodetree); +} + +void DepsgraphNodeBuilder::build_compositor(Scene *scene) +{ + /* For now, just a plain wrapper? */ + // TODO: create compositing component? + // XXX: component type undefined! + //graph->get_node(&scene->id, NULL, DEPSNODE_TYPE_COMPOSITING, NULL); + + /* for now, nodetrees are just parameters; compositing occurs in internals of renderer... */ + ComponentDepsNode *owner_node = add_component_node(&scene->id, DEPSNODE_TYPE_PARAMETERS); + build_nodetree(owner_node, scene->nodetree); +} + +void DepsgraphNodeBuilder::build_gpencil(bGPdata *gpd) +{ + ID *gpd_id = &gpd->id; + + /* gpencil itself */ + // XXX: what about multiple users of same datablock? This should only get added once + add_id_node(gpd_id); + + /* The main reason Grease Pencil is included here is because the animation (and drivers) + * need to be hosted somewhere... + */ + build_animdata(gpd_id); +} diff --git a/source/blender/depsgraph/intern/depsgraph_build_relations.cc b/source/blender/depsgraph/intern/depsgraph_build_relations.cc new file mode 100644 index 00000000000..f51f51987d7 --- /dev/null +++ b/source/blender/depsgraph/intern/depsgraph_build_relations.cc @@ -0,0 +1,1841 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): Based on original depsgraph.c code - Blender Foundation (2005-2013) + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph_build_relations.cc + * \ingroup depsgraph + * + * Methods for constructing depsgraph + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "MEM_guardedalloc.h" + +extern "C" { +#include "BLI_blenlib.h" +#include "BLI_string.h" +#include "BLI_utildefines.h" + +#include "DNA_action_types.h" +#include "DNA_anim_types.h" +#include "DNA_armature_types.h" +#include "DNA_camera_types.h" +#include "DNA_constraint_types.h" +#include "DNA_curve_types.h" +#include "DNA_effect_types.h" +#include "DNA_gpencil_types.h" +#include "DNA_group_types.h" +#include "DNA_key_types.h" +#include "DNA_lamp_types.h" +#include "DNA_material_types.h" +#include "DNA_mesh_types.h" +#include "DNA_meta_types.h" +#include "DNA_node_types.h" +#include "DNA_particle_types.h" +#include "DNA_object_types.h" +#include "DNA_rigidbody_types.h" +#include "DNA_scene_types.h" +#include "DNA_texture_types.h" +#include "DNA_world_types.h" + +#include "BKE_action.h" +#include "BKE_armature.h" +#include "BKE_animsys.h" +#include "BKE_constraint.h" +#include "BKE_curve.h" +#include "BKE_effect.h" +#include "BKE_fcurve.h" +#include "BKE_group.h" +#include "BKE_key.h" +#include "BKE_library.h" +#include "BKE_main.h" +#include "BKE_material.h" +#include "BKE_mball.h" +#include "BKE_modifier.h" +#include "BKE_node.h" +#include "BKE_object.h" +#include "BKE_particle.h" +#include "BKE_rigidbody.h" +#include "BKE_sound.h" +#include "BKE_texture.h" +#include "BKE_tracking.h" +#include "BKE_world.h" + +#include "DEG_depsgraph.h" +#include "DEG_depsgraph_build.h" + +#include "RNA_access.h" +#include "RNA_types.h" +} /* extern "C" */ + +#include "depsnode.h" +#include "depsnode_component.h" +#include "depsnode_operation.h" +#include "depsgraph_build.h" +#include "depsgraph_debug.h" +#include "depsgraph_intern.h" +#include "depsgraph_types.h" + +#include "depsgraph_util_pchanmap.h" + +/* ***************** */ +/* Relations Builder */ + +/* **** General purpose functions **** */ + +RNAPathKey::RNAPathKey(ID *id, const char *path) : + id(id) +{ + /* create ID pointer for root of path lookup */ + PointerRNA id_ptr; + RNA_id_pointer_create(id, &id_ptr); + /* try to resolve path... */ + int index; + if (!RNA_path_resolve_full(&id_ptr, path, &this->ptr, &this->prop, &index)) { + this->ptr = PointerRNA_NULL; + this->prop = NULL; + } +} + +DepsgraphRelationBuilder::DepsgraphRelationBuilder(Depsgraph *graph) : + m_graph(graph) +{ +} + +RootDepsNode *DepsgraphRelationBuilder::find_node(const RootKey &key) const +{ + (void)key; + BLI_assert(!"Doesn't seem to be correct"); + return m_graph->root_node; +} + +TimeSourceDepsNode *DepsgraphRelationBuilder::find_node( + const TimeSourceKey &key) const +{ + if (key.id) { + /* XXX TODO */ + return NULL; + } + else { + return m_graph->root_node->time_source; + } +} + +ComponentDepsNode *DepsgraphRelationBuilder::find_node( + const ComponentKey &key) const +{ + IDDepsNode *id_node = m_graph->find_id_node(key.id); + if (!id_node) { + fprintf(stderr, "find_node component: Could not find ID %s\n", + (key.id != NULL) ? key.id->name : "<null>"); + return NULL; + } + + ComponentDepsNode *node = id_node->find_component(key.type, key.name); + return node; +} + +OperationDepsNode *DepsgraphRelationBuilder::find_node( + const OperationKey &key) const +{ + IDDepsNode *id_node = m_graph->find_id_node(key.id); + if (!id_node) { + fprintf(stderr, "find_node operation: Could not find ID\n"); + return NULL; + } + + ComponentDepsNode *comp_node = id_node->find_component(key.component_type, + key.component_name); + if (!comp_node) { + fprintf(stderr, "find_node operation: Could not find component\n"); + return NULL; + } + + OperationDepsNode *op_node = comp_node->find_operation(key.opcode, key.name); + if (!op_node) { + fprintf(stderr, "find_node_operation: Failed for (%s, '%s')\n", + DEG_OPNAMES[key.opcode], key.name.c_str()); + } + return op_node; +} + +DepsNode *DepsgraphRelationBuilder::find_node(const RNAPathKey &key) const +{ + return m_graph->find_node_from_pointer(&key.ptr, key.prop); +} + +OperationDepsNode *DepsgraphRelationBuilder::has_node( + const OperationKey &key) const +{ + IDDepsNode *id_node = m_graph->find_id_node(key.id); + if (!id_node) { + return NULL; + } + ComponentDepsNode *comp_node = id_node->find_component(key.component_type, + key.component_name); + if (!comp_node) { + return NULL; + } + return comp_node->has_operation(key.opcode, key.name); +} + +void DepsgraphRelationBuilder::add_time_relation(TimeSourceDepsNode *timesrc, + DepsNode *node_to, + const char *description) +{ + if (timesrc && node_to) { + m_graph->add_new_relation(timesrc, node_to, DEPSREL_TYPE_TIME, description); + } + else { + DEG_DEBUG_PRINTF("add_time_relation(%p = %s, %p = %s, %s) Failed\n", + timesrc, (timesrc) ? timesrc->identifier().c_str() : "<None>", + node_to, (node_to) ? node_to->identifier().c_str() : "<None>", + description); + } +} + +void DepsgraphRelationBuilder::add_operation_relation( + OperationDepsNode *node_from, + OperationDepsNode *node_to, + eDepsRelation_Type type, + const char *description) +{ + if (node_from && node_to) { + m_graph->add_new_relation(node_from, node_to, type, description); + } + else { + DEG_DEBUG_PRINTF("add_operation_relation(%p = %s, %p = %s, %d, %s) Failed\n", + node_from, (node_from) ? node_from->identifier().c_str() : "<None>", + node_to, (node_to) ? node_to->identifier().c_str() : "<None>", + type, description); + } +} + +/* **** Functions to build relations between entities **** */ + +void DepsgraphRelationBuilder::build_scene(Main *bmain, Scene *scene) +{ + /* LIB_DOIT is used to indicate whether node for given ID was already + * created or not. + */ + BKE_main_id_tag_all(bmain, false); + + if (scene->set) { + // TODO: link set to scene, especially our timesource... + } + + /* scene objects */ + for (Base *base = (Base *)scene->base.first; base; base = base->next) { + Object *ob = base->object; + + /* object itself */ + build_object(bmain, scene, ob); + + /* object that this is a proxy for */ + if (ob->proxy) { + build_object(bmain, scene, ob->proxy); + /* TODO(sergey): This is an inverted relation, matches old depsgraph + * behavior and need to be investigated if it still need to be inverted. + */ + ComponentKey ob_pose_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE); + ComponentKey proxy_pose_key(&ob->proxy->id, DEPSNODE_TYPE_EVAL_POSE); + add_relation(ob_pose_key, proxy_pose_key, DEPSREL_TYPE_TRANSFORM, "Proxy"); + } + + /* Object dupligroup. */ + if (ob->dup_group) { + build_group(bmain, scene, ob, ob->dup_group); + } + } + + /* rigidbody */ + if (scene->rigidbody_world) { + build_rigidbody(scene); + } + + /* scene's animation and drivers */ + if (scene->adt) { + build_animdata(&scene->id); + } + + /* world */ + if (scene->world) { + build_world(scene->world); + } + + /* compo nodes */ + if (scene->nodetree) { + build_compositor(scene); + } + + /* grease pencil */ + if (scene->gpd) { + build_gpencil(&scene->id, scene->gpd); + } +} + +void DepsgraphRelationBuilder::build_group(Main *bmain, + Scene *scene, + Object *object, + Group *group) +{ + ID *group_id = &group->id; + bool group_done = (group_id->flag & LIB_DOIT) != 0; + OperationKey object_local_transform_key(&object->id, + DEPSNODE_TYPE_TRANSFORM, + DEG_OPCODE_TRANSFORM_LOCAL); + for (GroupObject *go = (GroupObject *)group->gobject.first; + go != NULL; + go = go->next) + { + if (!group_done) { + build_object(bmain, scene, go->ob); + } + ComponentKey dupli_transform_key(&go->ob->id, DEPSNODE_TYPE_TRANSFORM); + add_relation(dupli_transform_key, + object_local_transform_key, + DEPSREL_TYPE_TRANSFORM, + "Dupligroup"); + } + group_id->flag |= LIB_DOIT; +} + +void DepsgraphRelationBuilder::build_object(Main *bmain, Scene *scene, Object *ob) +{ + if (ob->id.flag & LIB_DOIT) { + return; + } + + /* Object Transforms */ + eDepsOperation_Code base_op = (ob->parent) ? DEG_OPCODE_TRANSFORM_PARENT : DEG_OPCODE_TRANSFORM_LOCAL; + OperationKey base_op_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, base_op); + + OperationKey local_transform_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_LOCAL); + OperationKey parent_transform_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_PARENT); + OperationKey final_transform_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_FINAL); + + OperationKey ob_ubereval_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_OBJECT_UBEREVAL); + + /* parenting */ + if (ob->parent) { + /* parent relationship */ + build_object_parent(ob); + + /* local -> parent */ + add_relation(local_transform_key, parent_transform_key, DEPSREL_TYPE_COMPONENT_ORDER, "[ObLocal -> ObParent]"); + } + + /* object constraints */ + if (ob->constraints.first) { + OperationKey constraint_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_CONSTRAINTS); + + /* constraint relations */ + // TODO: provide base op + // XXX: this is broken + build_constraints(scene, &ob->id, DEPSNODE_TYPE_TRANSFORM, "", &ob->constraints, NULL); + + /* operation order */ + add_relation(base_op_key, constraint_key, DEPSREL_TYPE_COMPONENT_ORDER, "[ObBase-> Constraint Stack]"); + add_relation(constraint_key, final_transform_key, DEPSREL_TYPE_COMPONENT_ORDER, "[ObConstraints -> Done]"); + + // XXX + add_relation(constraint_key, ob_ubereval_key, DEPSREL_TYPE_COMPONENT_ORDER, "Temp Ubereval"); + add_relation(ob_ubereval_key, final_transform_key, DEPSREL_TYPE_COMPONENT_ORDER, "Temp Ubereval"); + } + else { + /* operation order */ + add_relation(base_op_key, final_transform_key, DEPSREL_TYPE_COMPONENT_ORDER, "Object Transform"); + + // XXX + add_relation(base_op_key, ob_ubereval_key, DEPSREL_TYPE_COMPONENT_ORDER, "Temp Ubereval"); + add_relation(ob_ubereval_key, final_transform_key, DEPSREL_TYPE_COMPONENT_ORDER, "Temp Ubereval"); + } + + + /* AnimData */ + build_animdata(&ob->id); + + // XXX: This should be hooked up by the build_animdata code + if (ob->adt && (ob->adt->action || ob->adt->nla_tracks.first)) { + ComponentKey adt_key(&ob->id, DEPSNODE_TYPE_ANIMATION); + add_relation(adt_key, local_transform_key, DEPSREL_TYPE_OPERATION, "Object Animation"); + } + + + /* object data */ + if (ob->data) { + ID *obdata_id = (ID *)ob->data; + + /* ob data animation */ + build_animdata(obdata_id); + + /* type-specific data... */ + switch (ob->type) { + case OB_MESH: /* Geometry */ + case OB_CURVE: + case OB_FONT: + case OB_SURF: + case OB_MBALL: + case OB_LATTICE: + { + build_obdata_geom(bmain, scene, ob); + break; + } + + + case OB_ARMATURE: /* Pose */ + if (ob->id.lib != NULL && ob->proxy_from != NULL) { + build_proxy_rig(ob); + } + else { + build_rig(scene, ob); + } + break; + + case OB_LAMP: /* Lamp */ + build_lamp(ob); + break; + + case OB_CAMERA: /* Camera */ + build_camera(ob); + break; + } + } + + /* particle systems */ + if (ob->particlesystem.first) { + build_particles(scene, ob); + } + + /* grease pencil */ + if (ob->gpd) { + build_gpencil(&ob->id, ob->gpd); + } +} + +void DepsgraphRelationBuilder::build_object_parent(Object *ob) +{ + /* XXX: for now, need to use the component key (not just direct to the parent op), or else the matrix doesn't get reset */ + // XXX: @sergey - it would be good if we got that backwards flushing working when tagging for updates + //OperationKey ob_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_PARENT); + ComponentKey ob_key(&ob->id, DEPSNODE_TYPE_TRANSFORM); + + /* type-specific links */ + switch (ob->partype) { + case PARSKEL: /* Armature Deform (Virtual Modifier) */ + { + ComponentKey parent_key(&ob->parent->id, DEPSNODE_TYPE_TRANSFORM); + add_relation(parent_key, ob_key, DEPSREL_TYPE_STANDARD, "Armature Deform Parent"); + break; + } + + case PARVERT1: /* Vertex Parent */ + case PARVERT3: + { + ComponentKey parent_key(&ob->parent->id, DEPSNODE_TYPE_GEOMETRY); + add_relation(parent_key, ob_key, DEPSREL_TYPE_GEOMETRY_EVAL, "Vertex Parent"); + /* XXX not sure what this is for or how you could be done properly - lukas */ + //parent_node->customdata_mask |= CD_MASK_ORIGINDEX; + + ComponentKey transform_key(&ob->parent->id, DEPSNODE_TYPE_TRANSFORM); + add_relation(transform_key, ob_key, DEPSREL_TYPE_TRANSFORM, "Vertex Parent TFM"); + break; + } + + case PARBONE: /* Bone Parent */ + { + ComponentKey parent_key(&ob->parent->id, DEPSNODE_TYPE_BONE, ob->parsubstr); + add_relation(parent_key, ob_key, DEPSREL_TYPE_TRANSFORM, "Bone Parent"); + break; + } + + default: + { + if (ob->parent->type == OB_LATTICE) { + /* Lattice Deform Parent - Virtual Modifier */ + // XXX: no virtual modifiers should be left! + ComponentKey parent_key(&ob->parent->id, DEPSNODE_TYPE_TRANSFORM); + ComponentKey geom_key(&ob->parent->id, DEPSNODE_TYPE_GEOMETRY); + + add_relation(parent_key, ob_key, DEPSREL_TYPE_STANDARD, "Lattice Deform Parent"); + add_relation(geom_key, ob_key, DEPSREL_TYPE_STANDARD, "Lattice Deform Parent Geom"); + } + else if (ob->parent->type == OB_CURVE) { + Curve *cu = (Curve *)ob->parent->data; + + if (cu->flag & CU_PATH) { + /* Follow Path */ + ComponentKey parent_key(&ob->parent->id, DEPSNODE_TYPE_GEOMETRY); + add_relation(parent_key, ob_key, DEPSREL_TYPE_TRANSFORM, "Curve Follow Parent"); + + ComponentKey transform_key(&ob->parent->id, DEPSNODE_TYPE_TRANSFORM); + add_relation(transform_key, ob_key, DEPSREL_TYPE_TRANSFORM, "Curve Follow TFM"); + } + else { + /* Standard Parent */ + ComponentKey parent_key(&ob->parent->id, DEPSNODE_TYPE_TRANSFORM); + add_relation(parent_key, ob_key, DEPSREL_TYPE_TRANSFORM, "Curve Parent"); + } + } + else { + /* Standard Parent */ + ComponentKey parent_key(&ob->parent->id, DEPSNODE_TYPE_TRANSFORM); + add_relation(parent_key, ob_key, DEPSREL_TYPE_TRANSFORM, "Parent"); + } + break; + } + } + + /* exception case: parent is duplivert */ + if ((ob->type == OB_MBALL) && (ob->parent->transflag & OB_DUPLIVERTS)) { + //dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_OB, "Duplivert"); + } +} + +void DepsgraphRelationBuilder::build_constraints(Scene *scene, ID *id, eDepsNode_Type component_type, const char *component_subdata, + ListBase *constraints, RootPChanMap *root_map) +{ + OperationKey constraint_op_key(id, component_type, component_subdata, + (component_type == DEPSNODE_TYPE_BONE) ? DEG_OPCODE_BONE_CONSTRAINTS : DEG_OPCODE_TRANSFORM_CONSTRAINTS); + + /* add dependencies for each constraint in turn */ + for (bConstraint *con = (bConstraint *)constraints->first; con; con = con->next) { + const bConstraintTypeInfo *cti = BKE_constraint_typeinfo_get(con); + + /* invalid constraint type... */ + if (cti == NULL) + continue; + + /* special case for camera tracking -- it doesn't use targets to define relations */ + // TODO: we can now represent dependencies in a much richer manner, so review how this is done... + if (ELEM(cti->type, CONSTRAINT_TYPE_FOLLOWTRACK, CONSTRAINT_TYPE_CAMERASOLVER, CONSTRAINT_TYPE_OBJECTSOLVER)) { + bool depends_on_camera = false; + + if (cti->type == CONSTRAINT_TYPE_FOLLOWTRACK) { + bFollowTrackConstraint *data = (bFollowTrackConstraint *)con->data; + + if (((data->clip) || (data->flag & FOLLOWTRACK_ACTIVECLIP)) && data->track[0]) + depends_on_camera = true; + + if (data->depth_ob) { + // DAG_RL_DATA_OB | DAG_RL_OB_OB + ComponentKey depth_key(&data->depth_ob->id, DEPSNODE_TYPE_TRANSFORM); + add_relation(depth_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name); + } + } + else if (cti->type == CONSTRAINT_TYPE_OBJECTSOLVER) { + depends_on_camera = true; + } + + if (depends_on_camera && scene->camera) { + // DAG_RL_DATA_OB | DAG_RL_OB_OB + ComponentKey camera_key(&scene->camera->id, DEPSNODE_TYPE_TRANSFORM); + add_relation(camera_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name); + } + + /* tracker <-> constraints */ + // FIXME: actually motionclip dependency on results of motionclip block here... + //dag_add_relation(dag, scenenode, node, DAG_RL_SCENE, "Scene Relation"); + } + else if (cti->get_constraint_targets) { + ListBase targets = {NULL, NULL}; + cti->get_constraint_targets(con, &targets); + + for (bConstraintTarget *ct = (bConstraintTarget *)targets.first; ct; ct = ct->next) { + if (!ct->tar) + continue; + + if (ELEM(con->type, CONSTRAINT_TYPE_KINEMATIC, CONSTRAINT_TYPE_SPLINEIK)) { + /* ignore IK constraints - these are handled separately (on pose level) */ + } + else if (ELEM(con->type, CONSTRAINT_TYPE_FOLLOWPATH, CONSTRAINT_TYPE_CLAMPTO)) { + /* these constraints require path geometry data... */ + ComponentKey target_key(&ct->tar->id, DEPSNODE_TYPE_GEOMETRY); + add_relation(target_key, constraint_op_key, DEPSREL_TYPE_GEOMETRY_EVAL, cti->name); // XXX: type = geom_transform + // TODO: path dependency + } + else if ((ct->tar->type == OB_ARMATURE) && (ct->subtarget[0])) { + /* bone */ + if (&ct->tar->id == id) { + /* same armature */ + eDepsOperation_Code target_key_opcode; + + /* Using "done" here breaks in-chain deps, while using "ready" here breaks most production rigs instead... + * So, we do a compromise here, and only do this when an IK chain conflict may occur + */ + if (root_map->has_common_root(component_subdata, ct->subtarget)) { + target_key_opcode = DEG_OPCODE_BONE_READY; + } + else { + target_key_opcode = DEG_OPCODE_BONE_DONE; + } + + OperationKey target_key(&ct->tar->id, DEPSNODE_TYPE_BONE, ct->subtarget, target_key_opcode); + add_relation(target_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name); + } + else { + /* different armature - we can safely use the result of that */ + OperationKey target_key(&ct->tar->id, DEPSNODE_TYPE_BONE, ct->subtarget, DEG_OPCODE_BONE_DONE); + add_relation(target_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name); + } + } + else if (ELEM(ct->tar->type, OB_MESH, OB_LATTICE) && (ct->subtarget[0])) { + /* vertex group */ + /* NOTE: for now, we don't need to represent vertex groups separately... */ + ComponentKey target_key(&ct->tar->id, DEPSNODE_TYPE_GEOMETRY); + add_relation(target_key, constraint_op_key, DEPSREL_TYPE_GEOMETRY_EVAL, cti->name); + + if (ct->tar->type == OB_MESH) { + //node2->customdata_mask |= CD_MASK_MDEFORMVERT; + } + } + else if (con->type == CONSTRAINT_TYPE_SHRINKWRAP) { + /* Constraints which requires the target object surface. */ + ComponentKey target_key(&ct->tar->id, DEPSNODE_TYPE_GEOMETRY); + add_relation(target_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name); + + /* NOTE: obdata eval now doesn't necessarily depend on the object's transform... */ + ComponentKey target_transform_key(&ct->tar->id, DEPSNODE_TYPE_TRANSFORM); + add_relation(target_transform_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name); + } + else { + /* standard object relation */ + // TODO: loc vs rot vs scale? + if (&ct->tar->id == id) { + /* Constraint targetting own object: + * - This case is fine IFF we're dealing with a bone constraint pointing to + * its own armature. In that case, it's just transform -> bone. + * - If however it is a real self targetting case, just make it depend on the + * previous constraint (or the pre-constraint state)... + */ + if ((ct->tar->type == OB_ARMATURE) && (component_type == DEPSNODE_TYPE_BONE)) { + OperationKey target_key(&ct->tar->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_FINAL); + add_relation(target_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name); + } + else { + OperationKey target_key(&ct->tar->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_LOCAL); + add_relation(target_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name); + } + } + else { + /* normal object dependency */ + OperationKey target_key(&ct->tar->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_FINAL); + add_relation(target_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name); + } + } + + /* Constraints which needs world's matrix for transform. + * TODO(sergey): More constraints here? + */ + if (ELEM(con->type, + CONSTRAINT_TYPE_ROTLIKE, + CONSTRAINT_TYPE_SIZELIKE, + CONSTRAINT_TYPE_LOCLIKE, + CONSTRAINT_TYPE_TRANSLIKE)) + { + /* TODO(sergey): Add used space check. */ + ComponentKey target_transform_key(&ct->tar->id, DEPSNODE_TYPE_TRANSFORM); + add_relation(target_transform_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name); + } + + } + + if (cti->flush_constraint_targets) + cti->flush_constraint_targets(con, &targets, 1); + } + } +} + +void DepsgraphRelationBuilder::build_animdata(ID *id) +{ + AnimData *adt = BKE_animdata_from_id(id); + + if (adt == NULL) + return; + + ComponentKey adt_key(id, DEPSNODE_TYPE_ANIMATION); + + /* animation */ + if (adt->action || adt->nla_tracks.first) { + /* wire up dependency to time source */ + TimeSourceKey time_src_key; + add_relation(time_src_key, adt_key, DEPSREL_TYPE_TIME, "[TimeSrc -> Animation]"); + + // XXX: Hook up specific update callbacks for special properties which may need it... + + // XXX: animdata "hierarchy" - top-level overrides need to go after lower-down + } + + /* drivers */ + for (FCurve *fcu = (FCurve *)adt->drivers.first; fcu; fcu = fcu->next) { + OperationKey driver_key(id, DEPSNODE_TYPE_PARAMETERS, DEG_OPCODE_DRIVER, deg_fcurve_id_name(fcu)); + + /* create the driver's relations to targets */ + build_driver(id, fcu); + + /* prevent driver from occurring before own animation... */ + if (adt->action || adt->nla_tracks.first) { + add_relation(adt_key, driver_key, DEPSREL_TYPE_OPERATION, + "[AnimData Before Drivers]"); + } + } +} + +void DepsgraphRelationBuilder::build_driver(ID *id, FCurve *fcu) +{ + ChannelDriver *driver = fcu->driver; + OperationKey driver_key(id, DEPSNODE_TYPE_PARAMETERS, DEG_OPCODE_DRIVER, deg_fcurve_id_name(fcu)); + bPoseChannel *pchan = NULL; + + /* create dependency between driver and data affected by it */ + /* - direct property relationship... */ + //RNAPathKey affected_key(id, fcu->rna_path); + //add_relation(driver_key, affected_key, DEPSREL_TYPE_DRIVER, "[Driver -> Data] DepsRel"); + + /* driver -> data components (for interleaved evaluation - bones/constraints/modifiers) */ + // XXX: this probably should probably be moved out into a separate function + if (strstr(fcu->rna_path, "pose.bones[") != NULL) { + /* interleaved drivers during bone eval */ + // TODO: ideally, if this is for a constraint, it goes to said constraint + Object *ob = (Object *)id; + char *bone_name; + + bone_name = BLI_str_quoted_substrN(fcu->rna_path, "pose.bones["); + pchan = BKE_pose_channel_find_name(ob->pose, bone_name); + + if (bone_name) { + MEM_freeN(bone_name); + bone_name = NULL; + } + + if (pchan) { + OperationKey bone_key(id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_LOCAL); + add_relation(driver_key, bone_key, DEPSREL_TYPE_DRIVER, "[Driver -> Bone]"); + } + else { + fprintf(stderr, + "Couldn't find bone name for driver path - '%s'\n", + fcu->rna_path); + } + } + else if (GS(id->name) == ID_AR && strstr(fcu->rna_path, "bones[")) { + /* drivers on armature-level bone settings (i.e. bbone stuff), + * which will affect the evaluation of corresponding pose bones + */ + IDDepsNode *arm_node = m_graph->find_id_node(id); + char *bone_name = BLI_str_quoted_substrN(fcu->rna_path, "bones["); + + if (arm_node && bone_name) { + /* find objects which use this, and make their eval callbacks depend on this */ + DEPSNODE_RELATIONS_ITER_BEGIN(arm_node->outlinks, rel) + { + IDDepsNode *to_node = (IDDepsNode *)rel->to; + + /* we only care about objects with pose data which use this... */ + if (GS(to_node->id->name) == ID_OB) { + Object *ob = (Object *)to_node->id; + bPoseChannel *pchan = BKE_pose_channel_find_name(ob->pose, bone_name); // NOTE: ob->pose may be NULL + + if (pchan) { + OperationKey bone_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_LOCAL); + add_relation(driver_key, bone_key, DEPSREL_TYPE_DRIVER, "[Arm Bone -> Driver -> Bone]"); + } + } + } + DEPSNODE_RELATIONS_ITER_END; + + /* free temp data */ + MEM_freeN(bone_name); + bone_name = NULL; + } + else { + fprintf(stderr, + "Couldn't find armature bone name for driver path - '%s'\n", + fcu->rna_path); + } + } + else if (GS(id->name) == ID_OB && strstr(fcu->rna_path, "modifiers[")) { + /* modifier driver - connect directly to the modifier */ + char *modifier_name = BLI_str_quoted_substrN(fcu->rna_path, "modifiers["); + if (modifier_name) { + OperationKey modifier_key(id, + DEPSNODE_TYPE_GEOMETRY, + DEG_OPCODE_GEOMETRY_MODIFIER, + modifier_name); + if (has_node(modifier_key)) { + add_relation(driver_key, modifier_key, DEPSREL_TYPE_DRIVER, "[Driver -> Modifier]"); + } + else { + printf("Unexisting driver RNA path: %s\n", fcu->rna_path); + } + + MEM_freeN(modifier_name); + } + } + else if (GS(id->name) == ID_KE && strstr(fcu->rna_path, "key_blocks[")) { + /* shape key driver - hook into the base geometry operation */ + // XXX: double check where this points + Key *shape_key = (Key *)id; + + ComponentKey geometry_key(shape_key->from, DEPSNODE_TYPE_GEOMETRY); + add_relation(driver_key, geometry_key, DEPSREL_TYPE_DRIVER, "[Driver -> ShapeKey Geom]"); + } + else { + if (GS(id->name) == ID_OB) { + /* assume that driver affects a transform... */ + OperationKey local_transform_key(id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_LOCAL); + add_relation(driver_key, local_transform_key, DEPSREL_TYPE_OPERATION, "[Driver -> Transform]"); + } + } + + /* ensure that affected prop's update callbacks will be triggered once done */ + // TODO: implement this once the functionality to add these links exists in RNA + // XXX: the data itself could also set this, if it were to be truly initialised later? + + /* loop over variables to get the target relationships */ + for (DriverVar *dvar = (DriverVar *)driver->variables.first; dvar; dvar = dvar->next) { + /* only used targets */ + DRIVER_TARGETS_USED_LOOPER(dvar) + { + if (dtar->id == NULL) + continue; + + /* special handling for directly-named bones */ + if ((dtar->flag & DTAR_FLAG_STRUCT_REF) && (dtar->pchan_name[0])) { + Object *ob = (Object *)dtar->id; + bPoseChannel *target_pchan = BKE_pose_channel_find_name(ob->pose, dtar->pchan_name); + if (target_pchan != NULL) { + /* get node associated with bone */ + // XXX: watch the space! + /* Some cases can't use final bone transform, for example: + * - Driving the bone with itself (addressed here) + * - Relations inside an IK chain (TODO?) + */ + if (dtar->id == id && + pchan != NULL && + STREQ(pchan->name, target_pchan->name)) + { + continue; + } + OperationKey target_key(dtar->id, DEPSNODE_TYPE_BONE, target_pchan->name, DEG_OPCODE_BONE_DONE); + add_relation(target_key, driver_key, DEPSREL_TYPE_DRIVER_TARGET, "[Bone Target -> Driver]"); + } + } + else if (dtar->flag & DTAR_FLAG_STRUCT_REF) { + /* get node associated with the object's transforms */ + OperationKey target_key(dtar->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_FINAL); + add_relation(target_key, driver_key, DEPSREL_TYPE_DRIVER_TARGET, "[Target -> Driver]"); + } + else if (dtar->rna_path && strstr(dtar->rna_path, "pose.bones[")) { + /* workaround for ensuring that local bone transforms don't end up + * having to wait for pose eval to finish (to prevent cycles) + */ + Object *ob = (Object *)dtar->id; + char *bone_name = BLI_str_quoted_substrN(dtar->rna_path, "pose.bones["); + bPoseChannel *target_pchan = BKE_pose_channel_find_name(ob->pose, bone_name); + if (bone_name) { + MEM_freeN(bone_name); + bone_name = NULL; + } + if (target_pchan) { + if (dtar->id == id && + pchan != NULL && + STREQ(pchan->name, target_pchan->name)) + { + continue; + } + OperationKey bone_key(dtar->id, DEPSNODE_TYPE_BONE, target_pchan->name, DEG_OPCODE_BONE_LOCAL); + add_relation(bone_key, driver_key, DEPSREL_TYPE_DRIVER, "[RNA Bone -> Driver]"); + } + } + else { + /* resolve path to get node */ + RNAPathKey target_key(dtar->id, dtar->rna_path ? dtar->rna_path : ""); + add_relation(target_key, driver_key, DEPSREL_TYPE_DRIVER_TARGET, "[RNA Target -> Driver]"); + } + } + DRIVER_TARGETS_LOOPER_END + } +} + +void DepsgraphRelationBuilder::build_world(World *world) +{ + ID *world_id = &world->id; + if (world_id->flag & LIB_DOIT) { + return; + } + world_id->flag |= LIB_DOIT; + + build_animdata(world_id); + + /* TODO: other settings? */ + + /* textures */ + build_texture_stack(world_id, world->mtex); + + /* world's nodetree */ + build_nodetree(world_id, world->nodetree); +} + +void DepsgraphRelationBuilder::build_rigidbody(Scene *scene) +{ + RigidBodyWorld *rbw = scene->rigidbody_world; + + OperationKey init_key(&scene->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_REBUILD); + OperationKey sim_key(&scene->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_SIM); + + /* rel between the two sim-nodes */ + add_relation(init_key, sim_key, DEPSREL_TYPE_OPERATION, "Rigidbody [Init -> SimStep]"); + + /* set up dependencies between these operations and other builtin nodes --------------- */ + + /* time dependency */ + TimeSourceKey time_src_key; + add_relation(time_src_key, init_key, DEPSREL_TYPE_TIME, "TimeSrc -> Rigidbody Reset/Rebuild (Optional)"); + add_relation(time_src_key, sim_key, DEPSREL_TYPE_TIME, "TimeSrc -> Rigidbody Sim Step"); + + /* objects - simulation participants */ + if (rbw->group) { + for (GroupObject *go = (GroupObject *)rbw->group->gobject.first; go; go = go->next) { + Object *ob = go->ob; + if (!ob || ob->type != OB_MESH) + continue; + + /* hook up evaluation order... + * 1) flushing rigidbody results follows base transforms being applied + * 2) rigidbody flushing can only be performed after simulation has been run + * + * 3) simulation needs to know base transforms to figure out what to do + * XXX: there's probably a difference between passive and active + * - passive don't change, so may need to know full transform... + */ + OperationKey rbo_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_RIGIDBODY); + + eDepsOperation_Code trans_opcode = ob->parent ? DEG_OPCODE_TRANSFORM_PARENT : DEG_OPCODE_TRANSFORM_LOCAL; + OperationKey trans_op(&ob->id, DEPSNODE_TYPE_TRANSFORM, trans_opcode); + + add_relation(trans_op, rbo_key, DEPSREL_TYPE_OPERATION, "Base Ob Transform -> RBO Sync"); + add_relation(sim_key, rbo_key, DEPSREL_TYPE_COMPONENT_ORDER, "Rigidbody Sim Eval -> RBO Sync"); + + /* if constraints exist, those depend on the result of the rigidbody sim + * - This allows constraints to modify the result of the sim (i.e. clamping) + * while still allowing the sim to depend on some changes to the objects. + * Also, since constraints are hooked up to the final nodes, this link + * means that we can also fit in there too... + * - Later, it might be good to include a constraint in the stack allowing us + * to control whether rigidbody eval gets interleaved into the constraint stack + */ + if (ob->constraints.first) { + OperationKey constraint_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_CONSTRAINTS); + add_relation(rbo_key, constraint_key, DEPSREL_TYPE_COMPONENT_ORDER, "RBO Sync -> Ob Constraints"); + } + else { + /* final object transform depends on rigidbody */ + OperationKey done_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_FINAL); + add_relation(rbo_key, done_key, DEPSREL_TYPE_COMPONENT_ORDER, "RBO Sync -> Done"); + + // XXX: ubereval will be removed eventually, but we still need it in the meantime + OperationKey uber_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_OBJECT_UBEREVAL); + add_relation(rbo_key, uber_key, DEPSREL_TYPE_COMPONENT_ORDER, "RBO Sync -> Uber (Temp)"); + } + + + /* needed to get correct base values */ + add_relation(trans_op, sim_key, DEPSREL_TYPE_OPERATION, "Base Ob Transform -> Rigidbody Sim Eval"); + } + } + + /* constraints */ + if (rbw->constraints) { + for (GroupObject *go = (GroupObject *)rbw->constraints->gobject.first; go; go = go->next) { + Object *ob = go->ob; + if (!ob || !ob->rigidbody_constraint) + continue; + + RigidBodyCon *rbc = ob->rigidbody_constraint; + + /* final result of the constraint object's transform controls how the + * constraint affects the physics sim for these objects + */ + ComponentKey trans_key(&ob->id, DEPSNODE_TYPE_TRANSFORM); + OperationKey ob1_key(&rbc->ob1->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_RIGIDBODY); + OperationKey ob2_key(&rbc->ob2->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_RIGIDBODY); + + /* - constrained-objects sync depends on the constraint-holder */ + add_relation(trans_key, ob1_key, DEPSREL_TYPE_TRANSFORM, "RigidBodyConstraint -> RBC.Object_1"); + add_relation(trans_key, ob2_key, DEPSREL_TYPE_TRANSFORM, "RigidBodyConstraint -> RBC.Object_2"); + + /* - ensure that sim depends on this constraint's transform */ + add_relation(trans_key, sim_key, DEPSREL_TYPE_TRANSFORM, "RigidBodyConstraint Transform -> RB Simulation"); + } + } +} + +void DepsgraphRelationBuilder::build_particles(Scene *scene, Object *ob) +{ + TimeSourceKey time_src_key; + OperationKey obdata_ubereval_key(&ob->id, + DEPSNODE_TYPE_GEOMETRY, + DEG_OPCODE_GEOMETRY_UBEREVAL); + + /* particle systems */ + for (ParticleSystem *psys = (ParticleSystem *)ob->particlesystem.first; psys; psys = psys->next) { + ParticleSettings *part = psys->part; + + /* particle settings */ + build_animdata(&part->id); + + /* this particle system */ + OperationKey psys_key(&ob->id, DEPSNODE_TYPE_EVAL_PARTICLES, DEG_OPCODE_PSYS_EVAL, psys->name); + + /* XXX: if particle system is later re-enabled, we must do full rebuild? */ + if (!psys_check_enabled(ob, psys)) + continue; + + /* TODO(sergey): Are all particle systems depends on time? + * Hair without dynamics i.e. + */ + add_relation(time_src_key, psys_key, + DEPSREL_TYPE_TIME, + "TimeSrc -> PSys"); + + /* TODO(sergey): Currently particle update is just a placeholder, + * hook it to the ubereval node so particle system is getting updated + * on playback. + */ + add_relation(psys_key, + obdata_ubereval_key, + DEPSREL_TYPE_OPERATION, + "PSys -> UberEval"); + +#if 0 + if (ELEM(part->phystype, PART_PHYS_KEYED, PART_PHYS_BOIDS)) { + ParticleTarget *pt; + + for (pt = psys->targets.first; pt; pt = pt->next) { + if (pt->ob && BLI_findlink(&pt->ob->particlesystem, pt->psys - 1)) { + node2 = dag_get_node(dag, pt->ob); + dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Particle Targets"); + } + } + } + + if (part->ren_as == PART_DRAW_OB && part->dup_ob) { + node2 = dag_get_node(dag, part->dup_ob); + /* note that this relation actually runs in the wrong direction, the problem + * is that dupli system all have this (due to parenting), and the render + * engine instancing assumes particular ordering of objects in list */ + dag_add_relation(dag, node, node2, DAG_RL_OB_OB, "Particle Object Visualization"); + if (part->dup_ob->type == OB_MBALL) + dag_add_relation(dag, node, node2, DAG_RL_DATA_DATA, "Particle Object Visualization"); + } + + if (part->ren_as == PART_DRAW_GR && part->dup_group) { + for (go = part->dup_group->gobject.first; go; go = go->next) { + node2 = dag_get_node(dag, go->ob); + dag_add_relation(dag, node2, node, DAG_RL_OB_OB, "Particle Group Visualization"); + } + } +#endif + + /* effectors */ + ListBase *effectors = pdInitEffectors_ex(scene, ob, psys, ob->lay, part->effector_weights, false); + + if (effectors) { + for (EffectorCache *eff = (EffectorCache *)effectors->first; eff; eff = eff->next) { + if (eff->psys) { + // XXX: DAG_RL_DATA_DATA | DAG_RL_OB_DATA + ComponentKey eff_key(&eff->ob->id, DEPSNODE_TYPE_GEOMETRY); // xxx: particles instead? + add_relation(eff_key, psys_key, DEPSREL_TYPE_STANDARD, "Particle Field"); + } + } + } + + pdEndEffectors(&effectors); + + /* boids */ + if (part->boids) { + BoidRule *rule = NULL; + BoidState *state = NULL; + + for (state = (BoidState *)part->boids->states.first; state; state = state->next) { + for (rule = (BoidRule *)state->rules.first; rule; rule = rule->next) { + Object *ruleob = NULL; + if (rule->type == eBoidRuleType_Avoid) + ruleob = ((BoidRuleGoalAvoid *)rule)->ob; + else if (rule->type == eBoidRuleType_FollowLeader) + ruleob = ((BoidRuleFollowLeader *)rule)->ob; + + if (ruleob) { + ComponentKey ruleob_key(&ruleob->id, DEPSNODE_TYPE_TRANSFORM); + add_relation(ruleob_key, psys_key, DEPSREL_TYPE_TRANSFORM, "Boid Rule"); + } + } + } + } + } + + /* pointcache */ + // TODO... +} + +/* IK Solver Eval Steps */ +void DepsgraphRelationBuilder::build_ik_pose(Object *ob, + bPoseChannel *pchan, + bConstraint *con, + RootPChanMap *root_map) +{ + bKinematicConstraint *data = (bKinematicConstraint *)con->data; + + /* attach owner to IK Solver too + * - assume that owner is always part of chain + * - see notes on direction of rel below... + */ + bPoseChannel *rootchan = BKE_armature_ik_solver_find_root(pchan, data); + OperationKey solver_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE, rootchan->name, DEG_OPCODE_POSE_IK_SOLVER); + + /* IK target */ + // XXX: this should get handled as part of the constraint code + if (data->tar != NULL) { + /* TODO(sergey): For until we'll store partial matricies in the depsgraph, + * we create dependency between target object and pose eval component. + * + * This way we ensuring the whole subtree is updated from scratch without + * need of intermediate matricies. This is an overkill, but good enough for + * testing IK solver. + */ + // FIXME: geometry targets... + ComponentKey pose_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE); + if ((data->tar->type == OB_ARMATURE) && (data->subtarget[0])) { + /* TODO(sergey): This is only for until granular update stores intermediate result. */ + if (data->tar != ob) { + /* different armature - can just read the results */ + ComponentKey target_key(&data->tar->id, DEPSNODE_TYPE_BONE, data->subtarget); + add_relation(target_key, pose_key, DEPSREL_TYPE_TRANSFORM, con->name); + } + else { + /* same armature - we'll use the ready state only, just in case this bone is in the chain we're solving */ + OperationKey target_key(&data->tar->id, DEPSNODE_TYPE_BONE, data->subtarget, DEG_OPCODE_BONE_DONE); + add_relation(target_key, solver_key, DEPSREL_TYPE_TRANSFORM, con->name); + } + } + else if (ELEM(data->tar->type, OB_MESH, OB_LATTICE) && (data->subtarget[0])) { + /* vertex group target */ + /* NOTE: for now, we don't need to represent vertex groups separately... */ + ComponentKey target_key(&data->tar->id, DEPSNODE_TYPE_GEOMETRY); + add_relation(target_key, solver_key, DEPSREL_TYPE_GEOMETRY_EVAL, con->name); + + if (data->tar->type == OB_MESH) { + //node2->customdata_mask |= CD_MASK_MDEFORMVERT; + } + } + else { + /* Standard Object Target */ + ComponentKey target_key(&data->tar->id, DEPSNODE_TYPE_TRANSFORM); + add_relation(target_key, pose_key, DEPSREL_TYPE_TRANSFORM, con->name); + } + + if ((data->tar == ob) && (data->subtarget[0])) { + /* Prevent target's constraints from linking to anything from same + * chain that it controls. + */ + root_map->add_bone(data->subtarget, rootchan->name); + } + } + + /* Pole Target */ + // XXX: this should get handled as part of the constraint code + if (data->poletar != NULL) { + if ((data->tar->type == OB_ARMATURE) && (data->subtarget[0])) { + // XXX: same armature issues - ready vs done? + ComponentKey target_key(&data->poletar->id, DEPSNODE_TYPE_BONE, data->subtarget); + add_relation(target_key, solver_key, DEPSREL_TYPE_TRANSFORM, con->name); + } + else if (ELEM(data->poletar->type, OB_MESH, OB_LATTICE) && (data->subtarget[0])) { + /* vertex group target */ + /* NOTE: for now, we don't need to represent vertex groups separately... */ + ComponentKey target_key(&data->poletar->id, DEPSNODE_TYPE_GEOMETRY); + add_relation(target_key, solver_key, DEPSREL_TYPE_GEOMETRY_EVAL, con->name); + + if (data->poletar->type == OB_MESH) { + //node2->customdata_mask |= CD_MASK_MDEFORMVERT; + } + } + else { + ComponentKey target_key(&data->poletar->id, DEPSNODE_TYPE_TRANSFORM); + add_relation(target_key, solver_key, DEPSREL_TYPE_TRANSFORM, con->name); + } + } + + DEG_DEBUG_PRINTF("\nStarting IK Build: pchan = %s, target = (%s, %s), segcount = %d\n", + pchan->name, data->tar->id.name, data->subtarget, data->rootbone); + + bPoseChannel *parchan = pchan; + /* exclude tip from chain? */ + if (!(data->flag & CONSTRAINT_IK_TIP)) { + OperationKey tip_transforms_key(&ob->id, DEPSNODE_TYPE_BONE, + parchan->name, DEG_OPCODE_BONE_LOCAL); + add_relation(solver_key, tip_transforms_key, + DEPSREL_TYPE_TRANSFORM, "IK Solver Result"); + parchan = pchan->parent; + } + + root_map->add_bone(parchan->name, rootchan->name); + + OperationKey parchan_transforms_key(&ob->id, DEPSNODE_TYPE_BONE, + parchan->name, DEG_OPCODE_BONE_READY); + add_relation(parchan_transforms_key, solver_key, + DEPSREL_TYPE_TRANSFORM, "IK Solver Owner"); + + /* Walk to the chain's root */ + //size_t segcount = 0; + int segcount = 0; + + while (parchan) { + /* Make IK-solver dependent on this bone's result, + * since it can only run after the standard results + * of the bone are know. Validate links step on the + * bone will ensure that users of this bone only + * grab the result with IK solver results... + */ + if (parchan != pchan) { + OperationKey parent_key(&ob->id, DEPSNODE_TYPE_BONE, parchan->name, DEG_OPCODE_BONE_READY); + add_relation(parent_key, solver_key, DEPSREL_TYPE_TRANSFORM, "IK Chain Parent"); + + OperationKey done_key(&ob->id, DEPSNODE_TYPE_BONE, parchan->name, DEG_OPCODE_BONE_DONE); + add_relation(solver_key, done_key, DEPSREL_TYPE_TRANSFORM, "IK Chain Result"); + } + parchan->flag |= POSE_DONE; + + OperationKey final_transforms_key(&ob->id, DEPSNODE_TYPE_BONE, parchan->name, DEG_OPCODE_BONE_DONE); + add_relation(solver_key, final_transforms_key, DEPSREL_TYPE_TRANSFORM, "IK Solver Result"); + + root_map->add_bone(parchan->name, rootchan->name); + + /* continue up chain, until we reach target number of items... */ + DEG_DEBUG_PRINTF(" %d = %s\n", segcount, parchan->name); + segcount++; + if ((segcount == data->rootbone) || (segcount > 255)) break; /* 255 is weak */ + + parchan = parchan->parent; + } + + OperationKey flush_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE, DEG_OPCODE_POSE_DONE); + add_relation(solver_key, flush_key, DEPSREL_TYPE_OPERATION, "PoseEval Result-Bone Link"); +} + +/* Spline IK Eval Steps */ +void DepsgraphRelationBuilder::build_splineik_pose(Object *ob, + bPoseChannel *pchan, + bConstraint *con, + RootPChanMap *root_map) +{ + bSplineIKConstraint *data = (bSplineIKConstraint *)con->data; + bPoseChannel *rootchan = BKE_armature_splineik_solver_find_root(pchan, data); + OperationKey transforms_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_READY); + OperationKey solver_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE, rootchan->name, DEG_OPCODE_POSE_SPLINE_IK_SOLVER); + + /* attach owner to IK Solver too + * - assume that owner is always part of chain + * - see notes on direction of rel below... + */ + add_relation(transforms_key, solver_key, DEPSREL_TYPE_TRANSFORM, "Spline IK Solver Owner"); + + /* attach path dependency to solver */ + if (data->tar) { + /* TODO(sergey): For until we'll store partial matricies in the depsgraph, + * we create dependency between target object and pose eval component. + * See IK pose for a bit more information. + */ + // TODO: the bigggest point here is that we need the curve PATH and not just the general geometry... + ComponentKey target_key(&data->tar->id, DEPSNODE_TYPE_GEOMETRY); + ComponentKey pose_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE); + add_relation(target_key, pose_key, DEPSREL_TYPE_TRANSFORM, "[Curve.Path -> Spline IK] DepsRel"); + } + + pchan->flag |= POSE_DONE; + OperationKey final_transforms_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_DONE); + add_relation(solver_key, final_transforms_key, DEPSREL_TYPE_TRANSFORM, "Spline IK Result"); + + root_map->add_bone(pchan->name, rootchan->name); + + /* Walk to the chain's root */ + //size_t segcount = 0; + int segcount = 0; + + for (bPoseChannel *parchan = pchan->parent; parchan; parchan = parchan->parent) { + /* Make Spline IK solver dependent on this bone's result, + * since it can only run after the standard results + * of the bone are know. Validate links step on the + * bone will ensure that users of this bone only + * grab the result with IK solver results... + */ + if (parchan != pchan) { + OperationKey parent_key(&ob->id, DEPSNODE_TYPE_BONE, parchan->name, DEG_OPCODE_BONE_READY); + add_relation(parent_key, solver_key, DEPSREL_TYPE_TRANSFORM, "Spline IK Solver Update"); + + OperationKey done_key(&ob->id, DEPSNODE_TYPE_BONE, parchan->name, DEG_OPCODE_BONE_DONE); + add_relation(solver_key, done_key, DEPSREL_TYPE_TRANSFORM, "IK Chain Result"); + } + parchan->flag |= POSE_DONE; + + OperationKey final_transforms_key(&ob->id, DEPSNODE_TYPE_BONE, parchan->name, DEG_OPCODE_BONE_DONE); + add_relation(solver_key, final_transforms_key, DEPSREL_TYPE_TRANSFORM, "Spline IK Solver Result"); + + root_map->add_bone(parchan->name, rootchan->name); + + /* continue up chain, until we reach target number of items... */ + segcount++; + if ((segcount == data->chainlen) || (segcount > 255)) break; /* 255 is weak */ + } + + OperationKey flush_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE, DEG_OPCODE_POSE_DONE); + add_relation(solver_key, flush_key, DEPSREL_TYPE_OPERATION, "PoseEval Result-Bone Link"); +} + +/* Pose/Armature Bones Graph */ +void DepsgraphRelationBuilder::build_rig(Scene *scene, Object *ob) +{ + /* Armature-Data */ + // TODO: selection status? + + /* attach links between pose operations */ + OperationKey init_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE, DEG_OPCODE_POSE_INIT); + OperationKey flush_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE, DEG_OPCODE_POSE_DONE); + + add_relation(init_key, flush_key, DEPSREL_TYPE_COMPONENT_ORDER, "[Pose Init -> Pose Cleanup]"); + + if (ob->adt && (ob->adt->action || ob->adt->nla_tracks.first)) { + ComponentKey animation_key(&ob->id, DEPSNODE_TYPE_ANIMATION); + add_relation(animation_key, init_key, DEPSREL_TYPE_OPERATION, "Rig Animation"); + } + + /* IK Solvers... + * - These require separate processing steps are pose-level + * to be executed between chains of bones (i.e. once the + * base transforms of a bunch of bones is done) + * + * - We build relations for these before the dependencies + * between ops in the same component as it is necessary + * to check whether such bones are in the same IK chain + * (or else we get weird issues with either in-chain + * references, or with bones being parented to IK'd bones) + * + * Unsolved Issues: + * - Care is needed to ensure that multi-headed trees work out the same as in ik-tree building + * - Animated chain-lengths are a problem... + */ + RootPChanMap root_map; + bool pose_depends_on_local_transform = false; + for (bPoseChannel *pchan = (bPoseChannel *)ob->pose->chanbase.first; pchan; pchan = pchan->next) { + for (bConstraint *con = (bConstraint *)pchan->constraints.first; con; con = con->next) { + switch (con->type) { + case CONSTRAINT_TYPE_KINEMATIC: + build_ik_pose(ob, pchan, con, &root_map); + pose_depends_on_local_transform = true; + break; + + case CONSTRAINT_TYPE_SPLINEIK: + build_splineik_pose(ob, pchan, con, &root_map); + pose_depends_on_local_transform = true; + break; + + /* Constraints which needs world's matrix for transform. + * TODO(sergey): More constraints here? + */ + case CONSTRAINT_TYPE_ROTLIKE: + case CONSTRAINT_TYPE_SIZELIKE: + case CONSTRAINT_TYPE_LOCLIKE: + case CONSTRAINT_TYPE_TRANSLIKE: + /* TODO(sergey): Add used space check. */ + pose_depends_on_local_transform = true; + break; + + default: + break; + } + } + } + //root_map.print_debug(); + + if (pose_depends_on_local_transform) { + /* TODO(sergey): Once partial updates are possible use relation between + * object transform and solver itself in it's build function. + */ + ComponentKey pose_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE); + ComponentKey local_transform_key(&ob->id, DEPSNODE_TYPE_TRANSFORM); + add_relation(local_transform_key, pose_key, DEPSREL_TYPE_TRANSFORM, "Local Transforms"); + } + + + /* links between operations for each bone */ + for (bPoseChannel *pchan = (bPoseChannel *)ob->pose->chanbase.first; pchan; pchan = pchan->next) { + OperationKey bone_local_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_LOCAL); + OperationKey bone_pose_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_POSE_PARENT); + OperationKey bone_ready_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_READY); + OperationKey bone_done_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_DONE); + + pchan->flag &= ~POSE_DONE; + + /* pose init to bone local */ + add_relation(init_key, bone_local_key, DEPSREL_TYPE_OPERATION, "PoseEval Source-Bone Link"); + + /* local to pose parenting operation */ + add_relation(bone_local_key, bone_pose_key, DEPSREL_TYPE_OPERATION, "Bone Local - PoseSpace Link"); + + /* parent relation */ + if (pchan->parent != NULL) { + eDepsOperation_Code parent_key_opcode; + + /* NOTE: this difference in handling allows us to prevent lockups while ensuring correct poses for separate chains */ + if (root_map.has_common_root(pchan->name, pchan->parent->name)) { + parent_key_opcode = DEG_OPCODE_BONE_READY; + } + else { + parent_key_opcode = DEG_OPCODE_BONE_DONE; + } + + OperationKey parent_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->parent->name, parent_key_opcode); + add_relation(parent_key, bone_pose_key, DEPSREL_TYPE_TRANSFORM, "[Parent Bone -> Child Bone]"); + } + + /* constraints */ + if (pchan->constraints.first != NULL) { + /* constraints stack and constraint dependencies */ + build_constraints(scene, &ob->id, DEPSNODE_TYPE_BONE, pchan->name, &pchan->constraints, &root_map); + + /* pose -> constraints */ + OperationKey constraints_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_CONSTRAINTS); + add_relation(bone_pose_key, constraints_key, DEPSREL_TYPE_OPERATION, "Constraints Stack"); + + /* constraints -> ready */ + // TODO: when constraint stack is exploded, this step should occur before the first IK solver + add_relation(constraints_key, bone_ready_key, DEPSREL_TYPE_OPERATION, "Constraints -> Ready"); + } + else { + /* pose -> ready */ + add_relation(bone_pose_key, bone_ready_key, DEPSREL_TYPE_OPERATION, "Pose -> Ready"); + } + + /* bone ready -> done + * NOTE: For bones without IK, this is all that's needed. + * For IK chains however, an additional rel is created from IK to done, + * with transitive reduction removing this one... + */ + add_relation(bone_ready_key, bone_done_key, DEPSREL_TYPE_OPERATION, "Ready -> Done"); + + /* assume that all bones must be done for the pose to be ready (for deformers) */ + add_relation(bone_done_key, flush_key, DEPSREL_TYPE_OPERATION, "PoseEval Result-Bone Link"); + } +} + +void DepsgraphRelationBuilder::build_proxy_rig(Object *ob) +{ + OperationKey pose_init_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE, DEG_OPCODE_POSE_INIT); + OperationKey pose_done_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE, DEG_OPCODE_POSE_DONE); + for (bPoseChannel *pchan = (bPoseChannel *)ob->pose->chanbase.first; + pchan != NULL; + pchan = pchan->next) + { + OperationKey bone_local_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_LOCAL); + OperationKey bone_ready_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_READY); + OperationKey bone_done_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_DONE); + add_relation(pose_init_key, bone_local_key, DEPSREL_TYPE_OPERATION, "Pose Init -> Bone Local"); + add_relation(bone_local_key, bone_ready_key, DEPSREL_TYPE_OPERATION, "Local -> Ready"); + add_relation(bone_ready_key, bone_done_key, DEPSREL_TYPE_OPERATION, "Ready -> Done"); + add_relation(bone_done_key, pose_done_key, DEPSREL_TYPE_OPERATION, "Bone Done -> Pose Done"); + } +} + +/* Shapekeys */ +void DepsgraphRelationBuilder::build_shapekeys(ID *obdata, Key *key) +{ + ComponentKey obdata_key(obdata, DEPSNODE_TYPE_GEOMETRY); + + /* attach animdata to geometry */ + build_animdata(&key->id); + + if (key->adt) { + // TODO: this should really be handled in build_animdata, since many of these cases will need it + if (key->adt->action || key->adt->nla_tracks.first) { + ComponentKey adt_key(&key->id, DEPSNODE_TYPE_ANIMATION); + add_relation(adt_key, obdata_key, DEPSREL_TYPE_OPERATION, "Animation"); + } + + /* NOTE: individual shapekey drivers are handled above already */ + } + + /* attach to geometry */ + // XXX: aren't shapekeys now done as a pseudo-modifier on object? + //ComponentKey key_key(&key->id, DEPSNODE_TYPE_GEOMETRY); // FIXME: this doesn't exist + //add_relation(key_key, obdata_key, DEPSREL_TYPE_GEOMETRY_EVAL, "Shapekeys"); +} + +/** + * ObData Geometry Evaluation + * ========================== + * + * The evaluation of geometry on objects is as follows: + * - The actual evaluated of the derived geometry (e.g. DerivedMesh, DispList, etc.) + * occurs in the Geometry component of the object which references this. This includes + * modifiers, and the temporary "ubereval" for geometry. + * - Therefore, each user of a piece of shared geometry data ends up evaluating its own + * version of the stuff, complete with whatever modifiers it may use. + * + * - The datablocks for the geometry data - "obdata" (e.g. ID_ME, ID_CU, ID_LT, etc.) are used for + * 1) calculating the bounding boxes of the geometry data, + * 2) aggregating inward links from other objects (e.g. for text on curve, etc.) + * and also for the links coming from the shapekey datablocks + * - Animation/Drivers affecting the parameters of the geometry are made to trigger + * updates on the obdata geometry component, which then trigger downstream + * re-evaluation of the individual instances of this geometry. + */ +// TODO: Materials and lighting should probably get their own component, instead of being lumped under geometry? +void DepsgraphRelationBuilder::build_obdata_geom(Main *bmain, Scene *scene, Object *ob) +{ + ID *obdata = (ID *)ob->data; + + /* Init operation of object-level geometry evaluation. */ + OperationKey geom_init_key(&ob->id, DEPSNODE_TYPE_GEOMETRY, DEG_OPCODE_PLACEHOLDER, "Eval Init"); + + /* get nodes for result of obdata's evaluation, and geometry evaluation on object */ + ComponentKey obdata_geom_key(obdata, DEPSNODE_TYPE_GEOMETRY); + ComponentKey geom_key(&ob->id, DEPSNODE_TYPE_GEOMETRY); + + /* link components to each other */ + add_relation(obdata_geom_key, geom_key, DEPSREL_TYPE_DATABLOCK, "Object Geometry Base Data"); + + /* Modifiers */ + if (ob->modifiers.first) { + ModifierData *md; + OperationKey prev_mod_key; + + for (md = (ModifierData *)ob->modifiers.first; md; md = md->next) { + const ModifierTypeInfo *mti = modifierType_getInfo((ModifierType)md->type); + OperationKey mod_key(&ob->id, DEPSNODE_TYPE_GEOMETRY, DEG_OPCODE_GEOMETRY_MODIFIER, md->name); + + if (md->prev) { + /* Stack relation: modifier depends on previous modifier in the stack */ + add_relation(prev_mod_key, mod_key, DEPSREL_TYPE_GEOMETRY_EVAL, "Modifier Stack"); + } + else { + /* Stack relation: first modifier depends on the geometry. */ + add_relation(geom_init_key, mod_key, DEPSREL_TYPE_GEOMETRY_EVAL, "Modifier Stack"); + } + + if (mti->updateDepsgraph) { + DepsNodeHandle handle = create_node_handle(mod_key); + mti->updateDepsgraph(md, bmain, scene, ob, &handle); + } + + if (BKE_object_modifier_use_time(ob, md)) { + TimeSourceKey time_src_key; + add_relation(time_src_key, mod_key, DEPSREL_TYPE_TIME, "Time Source"); + } + + prev_mod_key = mod_key; + } + } + + /* materials */ + if (ob->totcol) { + int a; + + for (a = 1; a <= ob->totcol; a++) { + Material *ma = give_current_material(ob, a); + + if (ma) + build_material(&ob->id, ma); + } + } + + /* geometry collision */ + if (ELEM(ob->type, OB_MESH, OB_CURVE, OB_LATTICE)) { + // add geometry collider relations + } + + /* Make sure uber update is the last in the dependencies. + * + * TODO(sergey): Get rid of this node. + */ + if (ob->type != OB_ARMATURE) { + /* Armatures does no longer require uber node. */ + OperationKey obdata_ubereval_key(&ob->id, DEPSNODE_TYPE_GEOMETRY, DEG_OPCODE_GEOMETRY_UBEREVAL); + if (ob->modifiers.last) { + ModifierData *md = (ModifierData *)ob->modifiers.last; + OperationKey mod_key(&ob->id, DEPSNODE_TYPE_GEOMETRY, DEG_OPCODE_GEOMETRY_MODIFIER, md->name); + add_relation(mod_key, obdata_ubereval_key, DEPSREL_TYPE_OPERATION, "Object Geometry UberEval"); + } + else { + add_relation(geom_init_key, obdata_ubereval_key, DEPSREL_TYPE_OPERATION, "Object Geometry UberEval"); + } + } + + if (obdata->flag & LIB_DOIT) { + return; + } + obdata->flag |= LIB_DOIT; + + /* Link object data evaluation node to exit operation. */ + OperationKey obdata_geom_eval_key(obdata, DEPSNODE_TYPE_GEOMETRY, DEG_OPCODE_PLACEHOLDER, "Geometry Eval"); + OperationKey obdata_geom_done_key(obdata, DEPSNODE_TYPE_GEOMETRY, DEG_OPCODE_PLACEHOLDER, "Eval Done"); + add_relation(obdata_geom_eval_key, obdata_geom_done_key, DEPSREL_TYPE_DATABLOCK, "ObData Geom Eval Done"); + + /* type-specific node/links */ + switch (ob->type) { + case OB_MESH: + break; + + case OB_MBALL: + { + Object *mom = BKE_mball_basis_find(scene, ob); + + /* motherball - mom depends on children! */ + if (mom != ob) { + /* non-motherball -> cannot be directly evaluated! */ + ComponentKey mom_key(&mom->id, DEPSNODE_TYPE_GEOMETRY); + add_relation(geom_key, mom_key, DEPSREL_TYPE_GEOMETRY_EVAL, "Metaball Motherball"); + } + break; + } + + case OB_CURVE: + case OB_FONT: + { + Curve *cu = (Curve *)obdata; + + /* curve's dependencies */ + // XXX: these needs geom data, but where is geom stored? + if (cu->bevobj) { + ComponentKey bevob_key(&cu->bevobj->id, DEPSNODE_TYPE_GEOMETRY); + add_relation(bevob_key, geom_key, DEPSREL_TYPE_GEOMETRY_EVAL, "Curve Bevel"); + } + if (cu->taperobj) { + ComponentKey taperob_key(&cu->taperobj->id, DEPSNODE_TYPE_GEOMETRY); + add_relation(taperob_key, geom_key, DEPSREL_TYPE_GEOMETRY_EVAL, "Curve Taper"); + } + if (ob->type == OB_FONT) { + if (cu->textoncurve) { + ComponentKey textoncurve_key(&cu->taperobj->id, DEPSNODE_TYPE_GEOMETRY); + add_relation(textoncurve_key, geom_key, DEPSREL_TYPE_GEOMETRY_EVAL, "Text on Curve"); + } + } + break; + } + + case OB_SURF: /* Nurbs Surface */ + { + break; + } + + case OB_LATTICE: /* Lattice */ + { + break; + } + } + + /* ShapeKeys */ + Key *key = BKE_key_from_object(ob); + if (key) { + build_shapekeys(obdata, key); + } + + if (needs_animdata_node(obdata)) { + ComponentKey animation_key(obdata, DEPSNODE_TYPE_ANIMATION); + ComponentKey parameters_key(obdata, DEPSNODE_TYPE_PARAMETERS); + add_relation(animation_key, parameters_key, + DEPSREL_TYPE_COMPONENT_ORDER, "Geom Parameters"); + } +} + +/* Cameras */ +// TODO: Link scene-camera links in somehow... +void DepsgraphRelationBuilder::build_camera(Object *ob) +{ + Camera *cam = (Camera *)ob->data; + ID *camera_id = &cam->id; + if (camera_id->flag & LIB_DOIT) { + return; + } + camera_id->flag |= LIB_DOIT; + + ComponentKey parameters_key(camera_id, DEPSNODE_TYPE_PARAMETERS); + + if (needs_animdata_node(camera_id)) { + ComponentKey animation_key(camera_id, DEPSNODE_TYPE_ANIMATION); + add_relation(animation_key, parameters_key, + DEPSREL_TYPE_COMPONENT_ORDER, "Camera Parameters"); + } + + /* DOF */ + if (cam->dof_ob) { + ComponentKey ob_param_key(&ob->id, DEPSNODE_TYPE_PARAMETERS); + ComponentKey dof_ob_key(&cam->dof_ob->id, DEPSNODE_TYPE_TRANSFORM); + add_relation(dof_ob_key, ob_param_key, DEPSREL_TYPE_TRANSFORM, "Camera DOF"); + } +} + +/* Lamps */ +void DepsgraphRelationBuilder::build_lamp(Object *ob) +{ + Lamp *la = (Lamp *)ob->data; + ID *lamp_id = &la->id; + if (lamp_id->flag & LIB_DOIT) { + return; + } + lamp_id->flag |= LIB_DOIT; + + ComponentKey parameters_key(lamp_id, DEPSNODE_TYPE_PARAMETERS); + + if (needs_animdata_node(lamp_id)) { + ComponentKey animation_key(lamp_id, DEPSNODE_TYPE_ANIMATION); + add_relation(animation_key, parameters_key, + DEPSREL_TYPE_COMPONENT_ORDER, "Lamp Parameters"); + } + + /* lamp's nodetree */ + if (la->nodetree) { + build_nodetree(lamp_id, la->nodetree); + ComponentKey nodetree_key(&la->nodetree->id, DEPSNODE_TYPE_PARAMETERS); + add_relation(nodetree_key, parameters_key, + DEPSREL_TYPE_COMPONENT_ORDER, "NTree->Lamp Parameters"); + } + + /* textures */ + build_texture_stack(lamp_id, la->mtex); +} + +void DepsgraphRelationBuilder::build_nodetree(ID *owner, bNodeTree *ntree) +{ + if (!ntree) + return; + + ID *ntree_id = &ntree->id; + + build_animdata(ntree_id); + + /* nodetree's nodes... */ + for (bNode *bnode = (bNode *)ntree->nodes.first; bnode; bnode = bnode->next) { + if (bnode->id) { + if (GS(bnode->id->name) == ID_MA) { + build_material(owner, (Material *)bnode->id); + } + else if (bnode->type == ID_TE) { + build_texture(owner, (Tex *)bnode->id); + } + else if (bnode->type == NODE_GROUP) { + bNodeTree *ntree = (bNodeTree *)bnode->id; + if ((ntree_id->flag & LIB_DOIT) == 0) { + build_nodetree(owner, ntree); + ntree_id->flag |= LIB_DOIT; + } + } + } + } + + if (needs_animdata_node(ntree_id)) { + ComponentKey parameters_key(ntree_id, DEPSNODE_TYPE_PARAMETERS); + ComponentKey animation_key(ntree_id, DEPSNODE_TYPE_ANIMATION); + add_relation(animation_key, parameters_key, + DEPSREL_TYPE_COMPONENT_ORDER, "NTree Parameters"); + } + + // TODO: link from nodetree to owner_component? +} + +/* Recursively build graph for material */ +void DepsgraphRelationBuilder::build_material(ID *owner, Material *ma) +{ + ID *ma_id = &ma->id; + if (ma_id->flag & LIB_DOIT) { + return; + } + ma_id->flag |= LIB_DOIT; + + /* animation */ + build_animdata(ma_id); + + /* textures */ + build_texture_stack(owner, ma->mtex); + + /* material's nodetree */ + build_nodetree(owner, ma->nodetree); +} + +/* Recursively build graph for texture */ +void DepsgraphRelationBuilder::build_texture(ID *owner, Tex *tex) +{ + ID *tex_id = &tex->id; + if (tex_id->flag & LIB_DOIT) { + return; + } + tex_id->flag |= LIB_DOIT; + + /* texture itself */ + build_animdata(tex_id); + + /* texture's nodetree */ + build_nodetree(owner, tex->nodetree); +} + +/* Texture-stack attached to some shading datablock */ +void DepsgraphRelationBuilder::build_texture_stack(ID *owner, MTex **texture_stack) +{ + int i; + + /* for now assume that all texture-stacks have same number of max items */ + for (i = 0; i < MAX_MTEX; i++) { + MTex *mtex = texture_stack[i]; + if (mtex && mtex->tex) + build_texture(owner, mtex->tex); + } +} + +void DepsgraphRelationBuilder::build_compositor(Scene *scene) +{ + /* For now, just a plain wrapper? */ + build_nodetree(&scene->id, scene->nodetree); +} + +void DepsgraphRelationBuilder::build_gpencil(ID *UNUSED(owner), bGPdata *gpd) +{ + /* animation */ + build_animdata(&gpd->id); + + // TODO: parent object (when that feature is implemented) +} + +bool DepsgraphRelationBuilder::needs_animdata_node(ID *id) +{ + AnimData *adt = BKE_animdata_from_id(id); + if (adt != NULL) { + return adt->action != NULL; + } + return false; +} + diff --git a/source/blender/depsgraph/intern/depsgraph_debug.cc b/source/blender/depsgraph/intern/depsgraph_debug.cc new file mode 100644 index 00000000000..59351495df0 --- /dev/null +++ b/source/blender/depsgraph/intern/depsgraph_debug.cc @@ -0,0 +1,1193 @@ +/* + * ***** 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) 2014 Blender Foundation. + * All rights reserved. + * + * Original Author: Lukas Toenne + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph_debug.cc + * \ingroup depsgraph + * + * Implementation of tools for debugging the depsgraph + */ + +//#include <stdlib.h> +#include <string.h> + +extern "C" { +#include "BLI_utildefines.h" +#include "BLI_listbase.h" +#include "BLI_ghash.h" +#include "BLI_string.h" + +#include "DNA_scene_types.h" +#include "DNA_userdef_types.h" + +#include "DEG_depsgraph.h" +#include "DEG_depsgraph_debug.h" +#include "DEG_depsgraph_build.h" + +#include "WM_api.h" +#include "WM_types.h" +} /* extern "C" */ + +#include "depsgraph_debug.h" +#include "depsnode.h" +#include "depsnode_component.h" +#include "depsnode_operation.h" +#include "depsgraph_intern.h" + +/* ****************** */ +/* Graphviz Debugging */ + +static SpinLock lock; + +#define NL "\r\n" + +/* Only one should be enabled, defines whether graphviz nodes + * get colored by individual types or classes. + */ +#define COLOR_SCHEME_NODE_CLASS 1 +//#define COLOR_SCHEME_NODE_TYPE 2 + +static const char *deg_debug_graphviz_fontname = "helvetica"; +static float deg_debug_graphviz_graph_label_size = 20.0f; +static float deg_debug_graphviz_node_label_size = 14.0f; +static const int deg_debug_max_colors = 12; +#if 0 +static const char *deg_debug_colors_dark[] = { + "#6e8997", "#144f77", "#76945b", + "#216a1d", "#a76665", "#971112", + "#a87f49", "#0a9540", "#86768e", + "#462866", "#a9a965", "#753b1a", +}; +#endif +#ifdef COLOR_SCHEME_NODE_TYPE +static const char *deg_debug_colors[] = { + "#a6cee3", "#1f78b4", "#b2df8a", + "#33a02c", "#fb9a99", "#e31a1c", + "#fdbf6f", "#ff7f00", "#cab2d6", + "#6a3d9a", "#ffff99", "#b15928", +}; +#endif +static const char *deg_debug_colors_light[] = { + "#8dd3c7", "#ffffb3", "#bebada", + "#fb8072", "#80b1d3", "#fdb462", + "#b3de69", "#fccde5", "#d9d9d9", + "#bc80bd", "#ccebc5", "#ffed6f", +}; + +#ifdef COLOR_SCHEME_NODE_TYPE +static const int deg_debug_node_type_color_map[][2] = { + {DEPSNODE_TYPE_ROOT, 0}, + {DEPSNODE_TYPE_TIMESOURCE, 1}, + {DEPSNODE_TYPE_ID_REF, 2}, + {DEPSNODE_TYPE_SUBGRAPH, 3}, + + /* Outer Types */ + {DEPSNODE_TYPE_PARAMETERS, 4}, + {DEPSNODE_TYPE_PROXY, 5}, + {DEPSNODE_TYPE_ANIMATION, 6}, + {DEPSNODE_TYPE_TRANSFORM, 7}, + {DEPSNODE_TYPE_GEOMETRY, 8}, + {DEPSNODE_TYPE_SEQUENCER, 9}, + {DEPSNODE_TYPE_SHADING, 10}, + {-1, 0} +}; +#endif + +#if 0 /* unused */ +static const int deg_debug_relation_type_color_map[][2] = { + {DEPSREL_TYPE_STANDARD, 0}, + {DEPSREL_TYPE_ROOT_TO_ACTIVE, 1}, + {DEPSREL_TYPE_DATABLOCK, 2}, + {DEPSREL_TYPE_TIME, 3}, + {DEPSREL_TYPE_COMPONENT_ORDER, 4}, + {DEPSREL_TYPE_OPERATION, 5}, + {DEPSREL_TYPE_DRIVER, 6}, + {DEPSREL_TYPE_DRIVER_TARGET, 7}, + {DEPSREL_TYPE_TRANSFORM, 8}, + {DEPSREL_TYPE_GEOMETRY_EVAL, 9}, + {DEPSREL_TYPE_UPDATE, 10}, + {DEPSREL_TYPE_UPDATE_UI, 11}, + {-1, 0} +}; +#endif + +static int deg_debug_node_color_index(const DepsNode *node) +{ +#ifdef COLOR_SCHEME_NODE_CLASS + /* Some special types. */ + switch (node->type) { + case DEPSNODE_TYPE_ID_REF: + return 5; + case DEPSNODE_TYPE_OPERATION: + { + OperationDepsNode *op_node = (OperationDepsNode *)node; + if (op_node->is_noop()) + return 8; + } + + default: + break; + } + /* Do others based on class. */ + switch (node->tclass) { + case DEPSNODE_CLASS_OPERATION: + return 4; + case DEPSNODE_CLASS_COMPONENT: + return 1; + default: + return 9; + } +#endif + +#ifdef COLOR_SCHEME_NODE_TYPE + const int (*pair)[2]; + for (pair = deg_debug_node_type_color_map; (*pair)[0] >= 0; ++pair) { + if ((*pair)[0] == node->type) { + return (*pair)[1]; + } + } + return -1; +#endif +} + +struct DebugContext { + FILE *file; + bool show_tags; + bool show_eval_priority; +}; + +static void deg_debug_fprintf(const DebugContext &ctx, const char *fmt, ...) ATTR_PRINTF_FORMAT(2, 3); +static void deg_debug_fprintf(const DebugContext &ctx, const char *fmt, ...) +{ + va_list args; + va_start(args, fmt); + vfprintf(ctx.file, fmt, args); + va_end(args); +} + +static void deg_debug_graphviz_legend_color(const DebugContext &ctx, + const char *name, + const char *color) +{ + deg_debug_fprintf(ctx, "<TR>"); + deg_debug_fprintf(ctx, "<TD>%s</TD>", name); + deg_debug_fprintf(ctx, "<TD BGCOLOR=\"%s\"></TD>", color); + deg_debug_fprintf(ctx, "</TR>" NL); +} + +#if 0 +static void deg_debug_graphviz_legend_line(const DebugContext &ctx, + const char *name, + const char *color, + const char *style) +{ + /* XXX TODO */ + deg_debug_fprintf(ctx, "" NL); +} + +static void deg_debug_graphviz_legend_cluster(const DebugContext &ctx, + const char *name, + const char *color, + const char *style) +{ + deg_debug_fprintf(ctx, "<TR>"); + deg_debug_fprintf(ctx, "<TD>%s</TD>", name); + deg_debug_fprintf(ctx, "<TD CELLPADDING=\"4\"><TABLE BORDER=\"1\" CELLBORDER=\"0\" CELLSPACING=\"0\" CELLPADDING=\"0\">"); + deg_debug_fprintf(ctx, "<TR><TD BGCOLOR=\"%s\"></TD></TR>", color); + deg_debug_fprintf(ctx, "</TABLE></TD>"); + deg_debug_fprintf(ctx, "</TR>" NL); +} +#endif + +static void deg_debug_graphviz_legend(const DebugContext &ctx) +{ + deg_debug_fprintf(ctx, "{" NL); + deg_debug_fprintf(ctx, "rank = sink;" NL); + deg_debug_fprintf(ctx, "Legend [shape=none, margin=0, label=<" NL); + deg_debug_fprintf(ctx, " <TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"4\">" NL); + deg_debug_fprintf(ctx, "<TR><TD COLSPAN=\"2\"><B>Legend</B></TD></TR>" NL); + +#ifdef COLOR_SCHEME_NODE_CLASS + const char **colors = deg_debug_colors_light; + deg_debug_graphviz_legend_color(ctx, "Operation", colors[4]); + deg_debug_graphviz_legend_color(ctx, "Component", colors[1]); + deg_debug_graphviz_legend_color(ctx, "ID Node", colors[5]); + deg_debug_graphviz_legend_color(ctx, "NOOP", colors[8]); +#endif + +#ifdef COLOR_SCHEME_NODE_TYPE + const int (*pair)[2]; + for (pair = deg_debug_node_type_color_map; (*pair)[0] >= 0; ++pair) { + DepsNodeFactory *nti = DEG_get_node_factory((eDepsNode_Type)(*pair)[0]); + deg_debug_graphviz_legend_color(ctx, + nti->tname().c_str(), + deg_debug_colors_light[(*pair)[1] % deg_debug_max_colors]); + } +#endif + + deg_debug_fprintf(ctx, "</TABLE>" NL); + deg_debug_fprintf(ctx, ">" NL); + deg_debug_fprintf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname); + deg_debug_fprintf(ctx, "];" NL); + deg_debug_fprintf(ctx, "}" NL); +} + +#if 0 /* unused */ +static int deg_debug_relation_type_color_index(eDepsRelation_Type type) +{ + const int (*pair)[2]; + for (pair = deg_debug_relation_type_color_map; (*pair)[0] >= 0; ++pair) { + if ((*pair)[0] == type) { + return (*pair)[1]; + } + } + return -1; +} +#endif + +static void deg_debug_graphviz_node_color(const DebugContext &ctx, + const DepsNode *node) +{ + const char *color_default = "black"; + const char *color_modified = "orangered4"; + const char *color_update = "dodgerblue3"; + const char *color = color_default; + if (ctx.show_tags) { + if (node->tclass == DEPSNODE_CLASS_OPERATION) { + OperationDepsNode *op_node = (OperationDepsNode *)node; + if (op_node->flag & DEPSOP_FLAG_DIRECTLY_MODIFIED) { + color = color_modified; + } + else if (op_node->flag & DEPSOP_FLAG_NEEDS_UPDATE) { + color = color_update; + } + } + } + deg_debug_fprintf(ctx, "\"%s\"", color); +} + +static void deg_debug_graphviz_node_penwidth(const DebugContext &ctx, + const DepsNode *node) +{ + float penwidth_default = 1.0f; + float penwidth_modified = 4.0f; + float penwidth_update = 4.0f; + float penwidth = penwidth_default; + if (ctx.show_tags) { + if (node->tclass == DEPSNODE_CLASS_OPERATION) { + OperationDepsNode *op_node = (OperationDepsNode *)node; + if (op_node->flag & DEPSOP_FLAG_DIRECTLY_MODIFIED) { + penwidth = penwidth_modified; + } + else if (op_node->flag & DEPSOP_FLAG_NEEDS_UPDATE) { + penwidth = penwidth_update; + } + } + } + deg_debug_fprintf(ctx, "\"%f\"", penwidth); +} + +static void deg_debug_graphviz_node_fillcolor(const DebugContext &ctx, + const DepsNode *node) +{ + const char *defaultcolor = "gainsboro"; + int color_index = deg_debug_node_color_index(node); + const char *fillcolor = color_index < 0 ? defaultcolor : deg_debug_colors_light[color_index % deg_debug_max_colors]; + deg_debug_fprintf(ctx, "\"%s\"", fillcolor); +} + +#if 0 /* implementation using stripes, a bit too noisy ... */ +static void deg_debug_graphviz_node_fillcolor(const DebugContext &ctx, + const DepsNode *node) +{ + const char *defaultcolor = "gainsboro"; + const char *color_needs_update = "orange"; + const int num_stripes = 10; + int color_index = deg_debug_node_color_index(node); + const char *base_color = color_index < 0 ? defaultcolor : deg_debug_colors_light[color_index % deg_debug_max_colors]; + if (ctx.show_tags && + (node->flag & (DEPSNODE_FLAG_DIRECTLY_MODIFIED | DEPSNODE_FLAG_NEEDS_UPDATE))) { + deg_debug_fprintf(ctx, "\""); + for (int i = 0; i < num_stripes; ++i) { + if (i > 0) { + deg_debug_fprintf(ctx, ":"); + } + deg_debug_fprintf(ctx, "%s:%s", base_color, color_needs_update); + } + deg_debug_fprintf(ctx, "\""); + } + else { + deg_debug_fprintf(ctx, "\"%s\"", base_color); + } +} +#endif + +static void deg_debug_graphviz_relation_color(const DebugContext &ctx, + const DepsRelation *UNUSED(rel)) +{ + const char *defaultcolor = "black"; +#if 0 /* disabled for now, edge colors are hardly distinguishable */ + int color = deg_debug_relation_type_color_index(rel->type); + if (color < 0) { + deg_debug_fprintf(ctx, "%s", defaultcolor); + } + else { + deg_debug_fprintf(ctx, "\"%s\"", deg_debug_colors_dark[color % deg_debug_max_colors]); + } +#else + deg_debug_fprintf(ctx, "%s", defaultcolor); +#endif +} + +static void deg_debug_graphviz_node_style(const DebugContext &ctx, const DepsNode *node) +{ + const char *base_style = "filled"; /* default style */ + if (ctx.show_tags) { + if (node->tclass == DEPSNODE_CLASS_OPERATION) { + OperationDepsNode *op_node = (OperationDepsNode *)node; + if (op_node->flag & (DEPSOP_FLAG_DIRECTLY_MODIFIED | DEPSOP_FLAG_NEEDS_UPDATE)) { + base_style = "striped"; + } + } + } + switch (node->tclass) { + case DEPSNODE_CLASS_GENERIC: + deg_debug_fprintf(ctx, "\"%s\"", base_style); + break; + case DEPSNODE_CLASS_COMPONENT: + deg_debug_fprintf(ctx, "\"%s\"", base_style); + break; + case DEPSNODE_CLASS_OPERATION: + deg_debug_fprintf(ctx, "\"%s,rounded\"", base_style); + break; + } +} + +static void deg_debug_graphviz_node_single(const DebugContext &ctx, + const DepsNode *node) +{ + const char *shape = "box"; + string name = node->identifier(); + float priority = -1.0f; + if (node->type == DEPSNODE_TYPE_ID_REF) { + IDDepsNode *id_node = (IDDepsNode *)node; + char buf[256]; + BLI_snprintf(buf, sizeof(buf), " (Layers: %d)", id_node->layers); + name += buf; + } + if (ctx.show_eval_priority && node->tclass == DEPSNODE_CLASS_OPERATION) { + priority = ((OperationDepsNode *)node)->eval_priority; + } + deg_debug_fprintf(ctx, "// %s\n", name.c_str()); + deg_debug_fprintf(ctx, "\"node_%p\"", node); + deg_debug_fprintf(ctx, "["); +// deg_debug_fprintf(ctx, "label=<<B>%s</B>>", name); + if (priority >= 0.0f) { + deg_debug_fprintf(ctx, "label=<%s<BR/>(<I>%.2f</I>)>", + name.c_str(), + priority); + } + else { + deg_debug_fprintf(ctx, "label=<%s>", name.c_str()); + } + deg_debug_fprintf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname); + deg_debug_fprintf(ctx, ",fontsize=%f", deg_debug_graphviz_node_label_size); + deg_debug_fprintf(ctx, ",shape=%s", shape); + deg_debug_fprintf(ctx, ",style="); deg_debug_graphviz_node_style(ctx, node); + deg_debug_fprintf(ctx, ",color="); deg_debug_graphviz_node_color(ctx, node); + deg_debug_fprintf(ctx, ",fillcolor="); deg_debug_graphviz_node_fillcolor(ctx, node); + deg_debug_fprintf(ctx, ",penwidth="); deg_debug_graphviz_node_penwidth(ctx, node); + deg_debug_fprintf(ctx, "];" NL); + deg_debug_fprintf(ctx, NL); +} + +static void deg_debug_graphviz_node_cluster_begin(const DebugContext &ctx, + const DepsNode *node) +{ + string name = node->identifier().c_str(); + if (node->type == DEPSNODE_TYPE_ID_REF) { + IDDepsNode *id_node = (IDDepsNode *)node; + char buf[256]; + BLI_snprintf(buf, sizeof(buf), " (Layers: %d)", id_node->layers); + name += buf; + } + deg_debug_fprintf(ctx, "// %s\n", name.c_str()); + deg_debug_fprintf(ctx, "subgraph \"cluster_%p\" {" NL, node); +// deg_debug_fprintf(ctx, "label=<<B>%s</B>>;" NL, name); + deg_debug_fprintf(ctx, "label=<%s>;" NL, name.c_str()); + deg_debug_fprintf(ctx, "fontname=\"%s\";" NL, deg_debug_graphviz_fontname); + deg_debug_fprintf(ctx, "fontsize=%f;" NL, deg_debug_graphviz_node_label_size); + deg_debug_fprintf(ctx, "style="); deg_debug_graphviz_node_style(ctx, node); deg_debug_fprintf(ctx, ";" NL); + deg_debug_fprintf(ctx, "color="); deg_debug_graphviz_node_color(ctx, node); deg_debug_fprintf(ctx, ";" NL); + deg_debug_fprintf(ctx, "fillcolor="); deg_debug_graphviz_node_fillcolor(ctx, node); deg_debug_fprintf(ctx, ";" NL); + deg_debug_fprintf(ctx, "penwidth="); deg_debug_graphviz_node_penwidth(ctx, node); deg_debug_fprintf(ctx, ";" NL); + /* dummy node, so we can add edges between clusters */ + deg_debug_fprintf(ctx, "\"node_%p\"", node); + deg_debug_fprintf(ctx, "["); + deg_debug_fprintf(ctx, "shape=%s", "point"); + deg_debug_fprintf(ctx, ",style=%s", "invis"); + deg_debug_fprintf(ctx, "];" NL); + deg_debug_fprintf(ctx, NL); +} + +static void deg_debug_graphviz_node_cluster_end(const DebugContext &ctx) +{ + deg_debug_fprintf(ctx, "}" NL); + deg_debug_fprintf(ctx, NL); +} + +static void deg_debug_graphviz_graph_nodes(const DebugContext &ctx, + const Depsgraph *graph); +static void deg_debug_graphviz_graph_relations(const DebugContext &ctx, + const Depsgraph *graph); + +static void deg_debug_graphviz_node(const DebugContext &ctx, + const DepsNode *node) +{ + switch (node->type) { + case DEPSNODE_TYPE_ID_REF: + { + const IDDepsNode *id_node = (const IDDepsNode *)node; + if (id_node->components.empty()) { + deg_debug_graphviz_node_single(ctx, node); + } + else { + deg_debug_graphviz_node_cluster_begin(ctx, node); + for (IDDepsNode::ComponentMap::const_iterator it = id_node->components.begin(); + it != id_node->components.end(); + ++it) + { + const ComponentDepsNode *comp = it->second; + deg_debug_graphviz_node(ctx, comp); + } + deg_debug_graphviz_node_cluster_end(ctx); + } + break; + } + case DEPSNODE_TYPE_SUBGRAPH: + { + SubgraphDepsNode *sub_node = (SubgraphDepsNode *)node; + if (sub_node->graph) { + deg_debug_graphviz_node_cluster_begin(ctx, node); + deg_debug_graphviz_graph_nodes(ctx, sub_node->graph); + deg_debug_graphviz_node_cluster_end(ctx); + } + else { + deg_debug_graphviz_node_single(ctx, node); + } + break; + } + case DEPSNODE_TYPE_PARAMETERS: + case DEPSNODE_TYPE_ANIMATION: + case DEPSNODE_TYPE_TRANSFORM: + case DEPSNODE_TYPE_PROXY: + case DEPSNODE_TYPE_GEOMETRY: + case DEPSNODE_TYPE_SEQUENCER: + case DEPSNODE_TYPE_EVAL_POSE: + case DEPSNODE_TYPE_BONE: + case DEPSNODE_TYPE_SHADING: + { + ComponentDepsNode *comp_node = (ComponentDepsNode *)node; + if (!comp_node->operations.empty()) { + deg_debug_graphviz_node_cluster_begin(ctx, node); + for (ComponentDepsNode::OperationMap::const_iterator it = comp_node->operations.begin(); + it != comp_node->operations.end(); + ++it) + { + const DepsNode *op_node = it->second; + deg_debug_graphviz_node(ctx, op_node); + } + deg_debug_graphviz_node_cluster_end(ctx); + } + else { + deg_debug_graphviz_node_single(ctx, node); + } + break; + } + default: + deg_debug_graphviz_node_single(ctx, node); + break; + } +} + +static bool deg_debug_graphviz_is_cluster(const DepsNode *node) +{ + switch (node->type) { + case DEPSNODE_TYPE_ID_REF: + { + const IDDepsNode *id_node = (const IDDepsNode *)node; + return !id_node->components.empty(); + } + case DEPSNODE_TYPE_SUBGRAPH: + { + SubgraphDepsNode *sub_node = (SubgraphDepsNode *)node; + return sub_node->graph != NULL; + } + case DEPSNODE_TYPE_PARAMETERS: + case DEPSNODE_TYPE_ANIMATION: + case DEPSNODE_TYPE_TRANSFORM: + case DEPSNODE_TYPE_PROXY: + case DEPSNODE_TYPE_GEOMETRY: + case DEPSNODE_TYPE_SEQUENCER: + case DEPSNODE_TYPE_EVAL_POSE: + case DEPSNODE_TYPE_BONE: + { + ComponentDepsNode *comp_node = (ComponentDepsNode *)node; + return !comp_node->operations.empty(); + } + default: + return false; + } +} + +static bool deg_debug_graphviz_is_owner(const DepsNode *node, + const DepsNode *other) +{ + switch (node->tclass) { + case DEPSNODE_CLASS_COMPONENT: + { + ComponentDepsNode *comp_node = (ComponentDepsNode *)node; + if (comp_node->owner == other) + return true; + break; + } + case DEPSNODE_CLASS_OPERATION: + { + OperationDepsNode *op_node = (OperationDepsNode *)node; + if (op_node->owner == other) + return true; + else if (op_node->owner->owner == other) + return true; + break; + } + default: break; + } + return false; +} + +static void deg_debug_graphviz_node_relations(const DebugContext &ctx, + const DepsNode *node) +{ + DEPSNODE_RELATIONS_ITER_BEGIN(node->inlinks, rel) + { + const DepsNode *tail = rel->to; /* same as node */ + const DepsNode *head = rel->from; + deg_debug_fprintf(ctx, "// %s -> %s\n", + head->identifier().c_str(), + tail->identifier().c_str()); + deg_debug_fprintf(ctx, "\"node_%p\"", head); + deg_debug_fprintf(ctx, " -> "); + deg_debug_fprintf(ctx, "\"node_%p\"", tail); + + deg_debug_fprintf(ctx, "["); + deg_debug_fprintf(ctx, "label=\"%s\"", rel->name); + deg_debug_fprintf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname); + deg_debug_fprintf(ctx, ",color="); deg_debug_graphviz_relation_color(ctx, rel); + /* NOTE: edge from node to own cluster is not possible and gives graphviz + * warning, avoid this here by just linking directly to the invisible + * placeholder node + */ + if (deg_debug_graphviz_is_cluster(tail) && !deg_debug_graphviz_is_owner(head, tail)) { + deg_debug_fprintf(ctx, ",ltail=\"cluster_%p\"", tail); + } + if (deg_debug_graphviz_is_cluster(head) && !deg_debug_graphviz_is_owner(tail, head)) { + deg_debug_fprintf(ctx, ",lhead=\"cluster_%p\"", head); + } + deg_debug_fprintf(ctx, "];" NL); + deg_debug_fprintf(ctx, NL); + } + DEPSNODE_RELATIONS_ITER_END; + +#if 0 + if (node->tclass == DEPSNODE_CLASS_COMPONENT) { + const ComponentDepsNode *comp_node = (const ComponentDepsNode *)node; + for (ComponentDepsNode::OperationMap::const_iterator it = comp_node->operations.begin(); + it != comp_node->operations.end(); + ++it) + { + OperationDepsNode *op_node = it->second; + deg_debug_graphviz_node_relations(ctx, op_node); + } + } + else if (node->type == DEPSNODE_TYPE_ID_REF) { + const IDDepsNode *id_node = (const IDDepsNode *)node; + for (IDDepsNode::ComponentMap::const_iterator it = id_node->components.begin(); + it != id_node->components.end(); + ++it) + { + const ComponentDepsNode *comp = it->second; + deg_debug_graphviz_node_relations(ctx, comp); + } + } + else if (node->type == DEPSNODE_TYPE_SUBGRAPH) { + SubgraphDepsNode *sub_node = (SubgraphDepsNode *)node; + if (sub_node->graph) { + deg_debug_graphviz_graph_relations(ctx, sub_node->graph); + } + } +#endif +} + +static void deg_debug_graphviz_graph_nodes(const DebugContext &ctx, + const Depsgraph *graph) +{ + if (graph->root_node) { + deg_debug_graphviz_node(ctx, graph->root_node); + } + for (Depsgraph::IDNodeMap::const_iterator it = graph->id_hash.begin(); + it != graph->id_hash.end(); + ++it) + { + DepsNode *node = it->second; + deg_debug_graphviz_node(ctx, node); + } + TimeSourceDepsNode *time_source = graph->find_time_source(NULL); + if (time_source != NULL) { + deg_debug_graphviz_node(ctx, time_source); + } +} + +static void deg_debug_graphviz_graph_relations(const DebugContext &ctx, + const Depsgraph *graph) +{ +#if 0 + if (graph->root_node) { + deg_debug_graphviz_node_relations(ctx, graph->root_node); + } + for (Depsgraph::IDNodeMap::const_iterator it = graph->id_hash.begin(); + it != graph->id_hash.end(); + ++it) + { + DepsNode *id_node = it->second; + deg_debug_graphviz_node_relations(ctx, id_node); + } +#else + /* XXX not in use yet */ +// for (Depsgraph::OperationNodes::const_iterator it = graph->all_opnodes.begin(); +// it != graph->all_opnodes.end(); +// ++it) +// { +// OperationDepsNode *op_node = *it; +// deg_debug_graphviz_node_relations(ctx, op_node); +// } + for (Depsgraph::IDNodeMap::const_iterator it = graph->id_hash.begin(); + it != graph->id_hash.end(); + ++it) + { + IDDepsNode *id_node = it->second; + for (IDDepsNode::ComponentMap::const_iterator it = id_node->components.begin(); + it != id_node->components.end(); + ++it) + { + ComponentDepsNode *comp_node = it->second; + for (ComponentDepsNode::OperationMap::const_iterator it = comp_node->operations.begin(); + it != comp_node->operations.end(); + ++it) + { + OperationDepsNode *op_node = it->second; + deg_debug_graphviz_node_relations(ctx, op_node); + } + } + } + + TimeSourceDepsNode *time_source = graph->find_time_source(NULL); + if (time_source != NULL) { + deg_debug_graphviz_node_relations(ctx, time_source); + } +#endif +} + +void DEG_debug_graphviz(const Depsgraph *graph, FILE *f, const char *label, bool show_eval) +{ +#if 0 /* generate shaded color set */ + static char colors[][3] = {{0xa6, 0xce, 0xe3},{0x1f, 0x78, 0xb4},{0xb2, 0xdf, 0x8a},{0x33, 0xa0, 0x2c}, + {0xfb, 0x9a, 0x99},{0xe3, 0x1a, 0x1c},{0xfd, 0xbf, 0x6f},{0xff, 0x7f, 0x00}, + {0xca, 0xb2, 0xd6},{0x6a, 0x3d, 0x9a},{0xff, 0xff, 0x99},{0xb1, 0x59, 0x28}}; + int i; + const float factor = 0.666f; + for (i=0; i < 12; ++i) + printf("\"#%x%x%x\"\n", (char)(colors[i][0] * factor), (char)(colors[i][1] * factor), (char)(colors[i][2] * factor)); +#endif + + if (!graph) { + return; + } + + DebugContext ctx; + ctx.file = f; + ctx.show_tags = show_eval; + ctx.show_eval_priority = show_eval; + + deg_debug_fprintf(ctx, "digraph depgraph {" NL); + deg_debug_fprintf(ctx, "rankdir=LR;" NL); + deg_debug_fprintf(ctx, "graph ["); + deg_debug_fprintf(ctx, "compound=true"); + deg_debug_fprintf(ctx, ",labelloc=\"t\""); + deg_debug_fprintf(ctx, ",fontsize=%f", deg_debug_graphviz_graph_label_size); + deg_debug_fprintf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname); + deg_debug_fprintf(ctx, ",label=\"%s\"", label); + deg_debug_fprintf(ctx, ",splines=ortho"); + deg_debug_fprintf(ctx, ",overlap=scalexy"); // XXX: only when using neato + deg_debug_fprintf(ctx, "];" NL); + + deg_debug_graphviz_graph_nodes(ctx, graph); + deg_debug_graphviz_graph_relations(ctx, graph); + + deg_debug_graphviz_legend(ctx); + + deg_debug_fprintf(ctx, "}" NL); +} + +#undef NL + +/* ************************************************ */ + +static string get_component_name(eDepsNode_Type type, const string &name = "") +{ + DepsNodeFactory *factory = DEG_get_node_factory(type); + if (name.empty()) { + return string(factory->tname()); + } + else { + return string(factory->tname()) + " | " + name; + } +} + +static void times_clear(DepsgraphStatsTimes ×) +{ + times.duration_last = 0.0f; +} + +static void times_add(DepsgraphStatsTimes ×, float time) +{ + times.duration_last += time; +} + +void DepsgraphDebug::eval_begin(const EvaluationContext *UNUSED(eval_ctx)) +{ + /* TODO(sergey): Stats are currently globally disabled. */ + /* verify_stats(); */ + reset_stats(); +} + +void DepsgraphDebug::eval_end(const EvaluationContext *UNUSED(eval_ctx)) +{ + WM_main_add_notifier(NC_SPACE | ND_SPACE_INFO_REPORT, NULL); +} + +void DepsgraphDebug::eval_step(const EvaluationContext *UNUSED(eval_ctx), + const char *message) +{ +#ifdef DEG_DEBUG_BUILD + if (deg_debug_eval_cb) + deg_debug_eval_cb(deg_debug_eval_userdata, message); +#else + (void)message; /* Ignored. */ +#endif +} + +void DepsgraphDebug::task_started(Depsgraph *graph, + const OperationDepsNode *node) +{ + if (stats) { + BLI_spin_lock(&graph->lock); + + ComponentDepsNode *comp = node->owner; + ID *id = comp->owner->id; + + DepsgraphStatsID *id_stats = get_id_stats(id, true); + times_clear(id_stats->times); + + /* XXX TODO use something like: if (id->flag & ID_DEG_DETAILS) {...} */ + if (0) { + /* XXX component name usage needs cleanup! currently mixes identifier and description strings! */ + DepsgraphStatsComponent *comp_stats = get_component_stats(id, get_component_name(comp->type, comp->name), true); + times_clear(comp_stats->times); + } + + BLI_spin_unlock(&graph->lock); + } +} + +void DepsgraphDebug::task_completed(Depsgraph *graph, + const OperationDepsNode *node, + double time) +{ + if (stats) { + BLI_spin_lock(&graph->lock); + + ComponentDepsNode *comp = node->owner; + ID *id = comp->owner->id; + + DepsgraphStatsID *id_stats = get_id_stats(id, true); + times_add(id_stats->times, time); + + /* XXX TODO use something like: if (id->flag & ID_DEG_DETAILS) {...} */ + if (0) { + /* XXX component name usage needs cleanup! currently mixes identifier and description strings! */ + DepsgraphStatsComponent *comp_stats = get_component_stats(id, get_component_name(comp->type, comp->name), true); + times_add(comp_stats->times, time); + } + + BLI_spin_unlock(&graph->lock); + } +} + +/* ********** */ +/* Statistics */ + +DepsgraphStats *DepsgraphDebug::stats = NULL; + +/* GHash callback */ +static void deg_id_stats_free(void *val) +{ + DepsgraphStatsID *id_stats = (DepsgraphStatsID *)val; + + if (id_stats) { + BLI_freelistN(&id_stats->components); + MEM_freeN(id_stats); + } +} + +void DepsgraphDebug::stats_init() +{ + if (!stats) { + stats = (DepsgraphStats *)MEM_callocN(sizeof(DepsgraphStats), "Depsgraph Stats"); + stats->id_stats = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "Depsgraph ID Stats Hash"); + } +} + +void DepsgraphDebug::stats_free() +{ + if (stats) { + BLI_ghash_free(stats->id_stats, NULL, deg_id_stats_free); + MEM_freeN(stats); + stats = NULL; + } +} + +void DepsgraphDebug::verify_stats() +{ + stats_init(); +} + +void DepsgraphDebug::reset_stats() +{ + if (!stats) { + return; + } + + /* XXX this doesn't work, will immediately clear all info, + * since most depsgraph updates have none or very few updates to handle. + * + * Could consider clearing only zero-user ID blocks here + */ +// BLI_ghash_clear(stats->id_stats, NULL, deg_id_stats_free); +} + +DepsgraphStatsID *DepsgraphDebug::get_id_stats(ID *id, bool create) +{ + DepsgraphStatsID *id_stats = (DepsgraphStatsID *)BLI_ghash_lookup(stats->id_stats, id); + + if (!id_stats && create) { + id_stats = (DepsgraphStatsID *)MEM_callocN(sizeof(DepsgraphStatsID), "Depsgraph ID Stats"); + id_stats->id = id; + + BLI_ghash_insert(stats->id_stats, id, id_stats); + } + + return id_stats; +} + +DepsgraphStatsComponent *DepsgraphDebug::get_component_stats( + DepsgraphStatsID *id_stats, + const string &name, + bool create) +{ + DepsgraphStatsComponent *comp_stats; + for (comp_stats = (DepsgraphStatsComponent *)id_stats->components.first; + comp_stats != NULL; + comp_stats = comp_stats->next) + { + if (STREQ(comp_stats->name, name.c_str())) + break; + } + if (!comp_stats && create) { + comp_stats = (DepsgraphStatsComponent *)MEM_callocN(sizeof(DepsgraphStatsComponent), "Depsgraph Component Stats"); + BLI_strncpy(comp_stats->name, name.c_str(), sizeof(comp_stats->name)); + BLI_addtail(&id_stats->components, comp_stats); + } + return comp_stats; +} + +/* ------------------------------------------------ */ + +DepsgraphStats *DEG_stats(void) +{ + return DepsgraphDebug::stats; +} + +void DEG_stats_verify() +{ + DepsgraphDebug::verify_stats(); +} + +DepsgraphStatsID *DEG_stats_id(ID *id) +{ + if (!DepsgraphDebug::stats) { + return NULL; + } + return DepsgraphDebug::get_id_stats(id, false); +} + +bool DEG_debug_compare(const struct Depsgraph *graph1, + const struct Depsgraph *graph2) +{ + BLI_assert(graph1 != NULL); + BLI_assert(graph2 != NULL); + if (graph1->operations.size() != graph2->operations.size()) { + return false; + } + /* TODO(sergey): Currently we only do real stupid check, + * which is fast but which isn't 100% reliable. + * + * Would be cool to make it more robust, but it's good enough + * for now. Also, proper graph check is actually NP-complex + * problem.. + */ + return true; +} + +bool DEG_debug_scene_relations_validate(Main *bmain, + Scene *scene) +{ + Depsgraph *depsgraph = DEG_graph_new(); + bool valid = true; + DEG_graph_build_from_scene(depsgraph, bmain, scene); + if (!DEG_debug_compare(depsgraph, scene->depsgraph)) { + fprintf(stderr, "ERROR! Depsgraph wasn't tagged for update when it should have!\n"); + BLI_assert(!"This should not happen!"); + valid = false; + } + DEG_graph_free(depsgraph); + return valid; +} + +bool DEG_debug_consistency_check(Depsgraph *graph) +{ + /* Validate links exists in both directions. */ + for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin(); + it_op != graph->operations.end(); + ++it_op) + { + OperationDepsNode *node = *it_op; + for (OperationDepsNode::Relations::const_iterator it_rel = node->outlinks.begin(); + it_rel != node->outlinks.end(); + ++it_rel) + { + DepsRelation *rel = *it_rel; + + int counter1 = 0; + for (OperationDepsNode::Relations::const_iterator tmp_rel = node->outlinks.begin(); + tmp_rel != node->outlinks.end(); + ++tmp_rel) + { + if (*tmp_rel == rel) { + ++counter1; + } + } + + int counter2 = 0; + for (OperationDepsNode::Relations::const_iterator tmp_rel = rel->to->inlinks.begin(); + tmp_rel != rel->to->inlinks.end(); + ++tmp_rel) + { + if (*tmp_rel == rel) { + ++counter2; + } + } + + if (counter1 != counter2) { + printf("Relation exists in outgoing direction but not in incoming (%d vs. %d).\n", + counter1, counter2); + return false; + } + } + } + + for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin(); + it_op != graph->operations.end(); + ++it_op) + { + OperationDepsNode *node = *it_op; + for (OperationDepsNode::Relations::const_iterator it_rel = node->inlinks.begin(); + it_rel != node->inlinks.end(); + ++it_rel) + { + DepsRelation *rel = *it_rel; + + int counter1 = 0; + for (OperationDepsNode::Relations::const_iterator tmp_rel = node->inlinks.begin(); + tmp_rel != node->inlinks.end(); + ++tmp_rel) + { + if (*tmp_rel == rel) { + ++counter1; + } + } + + int counter2 = 0; + for (OperationDepsNode::Relations::const_iterator tmp_rel = rel->from->outlinks.begin(); + tmp_rel != rel->from->outlinks.end(); + ++tmp_rel) + { + if (*tmp_rel == rel) { + ++counter2; + } + } + + if (counter1 != counter2) { + printf("Relation exists in incoming direction but not in outcoming (%d vs. %d).\n", + counter1, counter2); + } + } + } + + /* Validate node valency calculated in both directions. */ + for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin(); + it_op != graph->operations.end(); + ++it_op) + { + OperationDepsNode *node = *it_op; + node->num_links_pending = 0; + node->done = 0; + } + + for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin(); + it_op != graph->operations.end(); + ++it_op) + { + OperationDepsNode *node = *it_op; + if (node->done) { + printf("Node %s is twice in the operations!\n", + node->identifier().c_str()); + return false; + } + for (OperationDepsNode::Relations::const_iterator it_rel = node->outlinks.begin(); + it_rel != node->outlinks.end(); + ++it_rel) + { + DepsRelation *rel = *it_rel; + if (rel->to->type == DEPSNODE_TYPE_OPERATION) { + OperationDepsNode *to = (OperationDepsNode *)rel->to; + BLI_assert(to->num_links_pending < to->inlinks.size()); + ++to->num_links_pending; + } + } + node->done = 1; + } + + for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin(); + it_op != graph->operations.end(); + ++it_op) + { + OperationDepsNode *node = *it_op; + int num_links_pending = 0; + for (OperationDepsNode::Relations::const_iterator it_rel = node->inlinks.begin(); + it_rel != node->inlinks.end(); + ++it_rel) + { + DepsRelation *rel = *it_rel; + if (rel->from->type == DEPSNODE_TYPE_OPERATION) { + ++num_links_pending; + } + } + if (node->num_links_pending != num_links_pending) { + printf("Valency mismatch: %s, %u != %d\n", + node->identifier().c_str(), + node->num_links_pending, num_links_pending); + printf("Number of inlinks: %d\n", (int)node->inlinks.size()); + return false; + } + } + return true; +} + +/* ------------------------------------------------ */ + +/** + * Obtain simple statistics about the complexity of the depsgraph + * \param[out] r_outer The number of outer nodes in the graph + * \param[out] r_operations The number of operation nodes in the graph + * \param[out] r_relations The number of relations between (executable) nodes in the graph + */ +void DEG_stats_simple(const Depsgraph *graph, size_t *r_outer, + size_t *r_operations, size_t *r_relations) +{ + /* number of operations */ + if (r_operations) { + /* All operations should be in this list, allowing us to count the total + * number of nodes. + */ + *r_operations = graph->operations.size(); + } + + /* Count number of outer nodes and/or relations between these. */ + if (r_outer || r_relations) { + size_t tot_outer = 0; + size_t tot_rels = 0; + + for (Depsgraph::IDNodeMap::const_iterator it = graph->id_hash.begin(); + it != graph->id_hash.end(); + ++it) + { + IDDepsNode *id_node = it->second; + tot_outer++; + for (IDDepsNode::ComponentMap::const_iterator it = id_node->components.begin(); + it != id_node->components.end(); + ++it) + { + ComponentDepsNode *comp_node = it->second; + tot_outer++; + for (ComponentDepsNode::OperationMap::const_iterator it = comp_node->operations.begin(); + it != comp_node->operations.end(); + ++it) + { + OperationDepsNode *op_node = it->second; + tot_rels += op_node->inlinks.size(); + } + } + } + + TimeSourceDepsNode *time_source = graph->find_time_source(NULL); + if (time_source != NULL) { + tot_rels += time_source->inlinks.size(); + } + + if (r_relations) *r_relations = tot_rels; + if (r_outer) *r_outer = tot_outer; + } +} + diff --git a/source/blender/depsgraph/intern/depsgraph_debug.h b/source/blender/depsgraph/intern/depsgraph_debug.h new file mode 100644 index 00000000000..64b97855f57 --- /dev/null +++ b/source/blender/depsgraph/intern/depsgraph_debug.h @@ -0,0 +1,87 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph_debug.h + * \ingroup depsgraph + */ + +#ifndef __DEPSGRAPH_DEBUG_H__ +#define __DEPSGRAPH_DEBUG_H__ + +#include "depsgraph_types.h" + +extern "C" { +#include "BKE_global.h" +} + +struct DepsgraphStats; +struct DepsgraphStatsID; +struct DepsgraphStatsComponent; +struct DepsgraphSettings; +struct EvaluationContext; +struct OperationDepsNode; + +struct Depsgraph; + +struct DepsgraphDebug { + static DepsgraphStats *stats; + + static void stats_init(); + static void stats_free(); + + static void verify_stats(); + static void reset_stats(); + + static void eval_begin(const EvaluationContext *eval_ctx); + static void eval_end(const EvaluationContext *eval_ctx); + static void eval_step(const EvaluationContext *eval_ctx, + const char *message); + + static void task_started(Depsgraph *graph, const OperationDepsNode *node); + static void task_completed(Depsgraph *graph, + const OperationDepsNode *node, + double time); + + static DepsgraphStatsID *get_id_stats(ID *id, bool create); + static DepsgraphStatsComponent *get_component_stats(DepsgraphStatsID *id_stats, + const string &name, + bool create); + static DepsgraphStatsComponent *get_component_stats(ID *id, + const string &name, + bool create) + { + return get_component_stats(get_id_stats(id, create), name, create); + } +}; + +#define DEG_DEBUG_PRINTF(...) \ + { \ + if (G.debug & G_DEBUG_DEPSGRAPH) { \ + fprintf(stderr, __VA_ARGS__); \ + } \ + } \ + +#endif /* __DEPSGRAPH_DEBUG_H__ */ diff --git a/source/blender/depsgraph/intern/depsgraph_eval.cc b/source/blender/depsgraph/intern/depsgraph_eval.cc new file mode 100644 index 00000000000..17096931e57 --- /dev/null +++ b/source/blender/depsgraph/intern/depsgraph_eval.cc @@ -0,0 +1,394 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph_eval.cc + * \ingroup depsgraph + * + * Evaluation engine entrypoints for Depsgraph Engine. + */ + +#include "MEM_guardedalloc.h" + +#include "PIL_time.h" + +extern "C" { +#include "BLI_utildefines.h" +#include "BLI_task.h" + +#include "BKE_depsgraph.h" +#include "BKE_scene.h" + +#include "DEG_depsgraph.h" +} /* extern "C" */ + +#include "atomic_ops.h" + +#include "depsgraph.h" +#include "depsnode.h" +#include "depsnode_component.h" +#include "depsnode_operation.h" +#include "depsgraph_debug.h" + +#ifdef WITH_LEGACY_DEPSGRAPH +static bool use_legacy_depsgraph = true; +#endif + +bool DEG_depsgraph_use_legacy(void) +{ +#ifdef DISABLE_NEW_DEPSGRAPH + return true; +#elif defined(WITH_LEGACY_DEPSGRAPH) + return use_legacy_depsgraph; +#else + BLI_assert(!"Should not be used with new depsgraph"); + return false; +#endif +} + +void DEG_depsgraph_switch_to_legacy(void) +{ +#ifdef WITH_LEGACY_DEPSGRAPH + use_legacy_depsgraph = true; +#else + BLI_assert(!"Should not be used with new depsgraph"); +#endif +} + +void DEG_depsgraph_switch_to_new(void) +{ +#ifdef WITH_LEGACY_DEPSGRAPH + use_legacy_depsgraph = false; +#else + BLI_assert(!"Should not be used with new depsgraph"); +#endif +} + +/* ****************** */ +/* Evaluation Context */ + +/* Create new evaluation context. */ +EvaluationContext *DEG_evaluation_context_new(int mode) +{ + EvaluationContext *eval_ctx = + (EvaluationContext *)MEM_callocN(sizeof(EvaluationContext), + "EvaluationContext"); + eval_ctx->mode = mode; + return eval_ctx; +} + +/** + * Initialize evaluation context. + * Used by the areas which currently overrides the context or doesn't have + * access to a proper one. + */ +void DEG_evaluation_context_init(EvaluationContext *eval_ctx, int mode) +{ + eval_ctx->mode = mode; +} + +/* Free evaluation context. */ +void DEG_evaluation_context_free(EvaluationContext *eval_ctx) +{ + MEM_freeN(eval_ctx); +} + +/* ********************** */ +/* Evaluation Entrypoints */ + +/* Forward declarations. */ +static void schedule_children(TaskPool *pool, + Depsgraph *graph, + OperationDepsNode *node, + const int layers); + +struct DepsgraphEvalState { + EvaluationContext *eval_ctx; + Depsgraph *graph; + int layers; +}; + +static void deg_task_run_func(TaskPool *pool, + void *taskdata, + int UNUSED(threadid)) +{ + DepsgraphEvalState *state = (DepsgraphEvalState *)BLI_task_pool_userdata(pool); + OperationDepsNode *node = (OperationDepsNode *)taskdata; + + if (!node->is_noop()) { + /* Get context. */ + // TODO: who initialises this? "Init" operations aren't able to initialise it!!! + /* TODO(sergey): Wedon't use component contexts at this moment. */ + /* ComponentDepsNode *comp = node->owner; */ + BLI_assert(node->owner != NULL); + + /* Take note of current time. */ + double start_time = PIL_check_seconds_timer(); + DepsgraphDebug::task_started(state->graph, node); + + /* Should only be the case for NOOPs, which never get to this point. */ + BLI_assert(node->evaluate); + + /* Perform operation. */ + node->evaluate(state->eval_ctx); + + /* Note how long this took. */ + double end_time = PIL_check_seconds_timer(); + DepsgraphDebug::task_completed(state->graph, + node, + end_time - start_time); + } + + schedule_children(pool, state->graph, node, state->layers); +} + +static void calculate_pending_parents(Depsgraph *graph, int layers) +{ + for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin(); + it_op != graph->operations.end(); + ++it_op) + { + OperationDepsNode *node = *it_op; + IDDepsNode *id_node = node->owner->owner; + + node->num_links_pending = 0; + node->scheduled = false; + + /* count number of inputs that need updates */ + if ((id_node->layers & layers) != 0 && + (node->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0) + { + for (OperationDepsNode::Relations::const_iterator it_rel = node->inlinks.begin(); + it_rel != node->inlinks.end(); + ++it_rel) + { + DepsRelation *rel = *it_rel; + if (rel->from->type == DEPSNODE_TYPE_OPERATION && + (rel->flag & DEPSREL_FLAG_CYCLIC) == 0) + { + OperationDepsNode *from = (OperationDepsNode *)rel->from; + IDDepsNode *id_from_node = from->owner->owner; + if ((id_from_node->layers & layers) != 0 && + (from->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0) + { + ++node->num_links_pending; + } + } + } + } + } +} + +static void calculate_eval_priority(OperationDepsNode *node) +{ + if (node->done) { + return; + } + node->done = 1; + + if (node->flag & DEPSOP_FLAG_NEEDS_UPDATE) { + /* XXX standard cost of a node, could be estimated somewhat later on */ + const float cost = 1.0f; + /* NOOP nodes have no cost */ + node->eval_priority = node->is_noop() ? cost : 0.0f; + + for (OperationDepsNode::Relations::const_iterator it = node->outlinks.begin(); + it != node->outlinks.end(); + ++it) + { + DepsRelation *rel = *it; + OperationDepsNode *to = (OperationDepsNode *)rel->to; + BLI_assert(to->type == DEPSNODE_TYPE_OPERATION); + calculate_eval_priority(to); + node->eval_priority += to->eval_priority; + } + } + else { + node->eval_priority = 0.0f; + } +} + +static void schedule_graph(TaskPool *pool, + Depsgraph *graph, + const int layers) +{ + BLI_spin_lock(&graph->lock); + for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin(); + it != graph->operations.end(); + ++it) + { + OperationDepsNode *node = *it; + IDDepsNode *id_node = node->owner->owner; + if ((node->flag & DEPSOP_FLAG_NEEDS_UPDATE) && + node->num_links_pending == 0 && + (id_node->layers & layers) != 0) + { + BLI_task_pool_push(pool, deg_task_run_func, node, false, TASK_PRIORITY_LOW); + node->scheduled = true; + } + } + BLI_spin_unlock(&graph->lock); +} + +static void schedule_children(TaskPool *pool, + Depsgraph *graph, + OperationDepsNode *node, + const int layers) +{ + for (OperationDepsNode::Relations::const_iterator it = node->outlinks.begin(); + it != node->outlinks.end(); + ++it) + { + DepsRelation *rel = *it; + OperationDepsNode *child = (OperationDepsNode *)rel->to; + BLI_assert(child->type == DEPSNODE_TYPE_OPERATION); + + if (child->scheduled) { + /* Happens when having cyclic dependencies. */ + continue; + } + + IDDepsNode *id_child = child->owner->owner; + if ((id_child->layers & layers) != 0 && + (child->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0) + { + if ((rel->flag & DEPSREL_FLAG_CYCLIC) == 0) { + BLI_assert(child->num_links_pending > 0); + atomic_sub_uint32(&child->num_links_pending, 1); + } + + if (child->num_links_pending == 0) { + BLI_spin_lock(&graph->lock); + bool need_schedule = !child->scheduled; + child->scheduled = true; + BLI_spin_unlock(&graph->lock); + + if (need_schedule) { + BLI_task_pool_push(pool, deg_task_run_func, child, false, TASK_PRIORITY_LOW); + } + } + } + } +} + +/** + * Evaluate all nodes tagged for updating, + * \warning This is usually done as part of main loop, but may also be + * called from frame-change update. + * + * \note Time sources should be all valid! + */ +void DEG_evaluate_on_refresh_ex(EvaluationContext *eval_ctx, + Depsgraph *graph, + const int layers) +{ + /* Generate base evaluation context, upon which all the others are derived. */ + // TODO: this needs both main and scene access... + + /* Nothing to update, early out. */ + if (graph->entry_tags.size() == 0) { + return; + } + + /* Set time for the current graph evaluation context. */ + TimeSourceDepsNode *time_src = graph->find_time_source(); + eval_ctx->ctime = time_src->cfra; + + /* XXX could use a separate pool for each eval context */ + DepsgraphEvalState state; + state.eval_ctx = eval_ctx; + state.graph = graph; + state.layers = layers; + + TaskScheduler *task_scheduler = BLI_task_scheduler_get(); + TaskPool *task_pool = BLI_task_pool_create(task_scheduler, &state); + + if (G.debug & G_DEBUG_DEPSGRAPH_NO_THREADS) { + BLI_pool_set_num_threads(task_pool, 1); + } + + calculate_pending_parents(graph, layers); + + /* Clear tags. */ + for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin(); + it != graph->operations.end(); + ++it) + { + OperationDepsNode *node = *it; + node->done = 0; + } + + /* Calculate priority for operation nodes. */ + for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin(); + it != graph->operations.end(); + ++it) + { + OperationDepsNode *node = *it; + calculate_eval_priority(node); + } + + DepsgraphDebug::eval_begin(eval_ctx); + + schedule_graph(task_pool, graph, layers); + + BLI_task_pool_work_and_wait(task_pool); + BLI_task_pool_free(task_pool); + + DepsgraphDebug::eval_end(eval_ctx); + + /* Clear any uncleared tags - just in case. */ + DEG_graph_clear_tags(graph); +} + +/* Evaluate all nodes tagged for updating. */ +void DEG_evaluate_on_refresh(EvaluationContext *eval_ctx, + Depsgraph *graph, + Scene *scene) +{ + /* Update time on primary timesource. */ + TimeSourceDepsNode *tsrc = graph->find_time_source(); + tsrc->cfra = BKE_scene_frame_get(scene);; + + DEG_evaluate_on_refresh_ex(eval_ctx, graph, graph->layers); +} + +/* Frame-change happened for root scene that graph belongs to. */ +void DEG_evaluate_on_framechange(EvaluationContext *eval_ctx, + Main *bmain, + Depsgraph *graph, + float ctime, + const int layers) +{ + /* Update time on primary timesource. */ + TimeSourceDepsNode *tsrc = graph->find_time_source(); + tsrc->cfra = ctime; + + tsrc->tag_update(graph); + + DEG_graph_flush_updates(bmain, graph); + + /* Perform recalculation updates. */ + DEG_evaluate_on_refresh_ex(eval_ctx, graph, layers); +} diff --git a/source/blender/depsgraph/intern/depsgraph_intern.h b/source/blender/depsgraph/intern/depsgraph_intern.h new file mode 100644 index 00000000000..7fdc2454564 --- /dev/null +++ b/source/blender/depsgraph/intern/depsgraph_intern.h @@ -0,0 +1,168 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph_intern.h + * \ingroup depsgraph + * + * API's for internal use in the Depsgraph + * - Also, defines for "Node Type Info" + */ + +#ifndef __DEPSGRAPH_INTERN_H__ +#define __DEPSGRAPH_INTERN_H__ + +#include <cstdlib> + +#include "MEM_guardedalloc.h" + +#include "depsgraph.h" +#include "depsnode.h" + +struct Main; +struct Group; +struct Scene; + +/* Graph Building ======================================================== */ + +/** + * Build depsgraph for the given group, and dump results in given graph container + * This is usually used for building subgraphs for groups to use... + */ +void DEG_graph_build_from_group(Depsgraph *graph, struct Main *bmain, struct Group *group); + +/* Build subgraph for group */ +DepsNode *DEG_graph_build_group_subgraph(Depsgraph *graph_main, struct Main *bmain, struct Group *group); + +/* Graph Copying ========================================================= */ +/* (Part of the Filtering API) */ + +/** + * Depsgraph Copying Context (dcc) + * + * Keeps track of node relationships/links/etc. during the copy + * operation so that they can be safely remapped... + */ +typedef struct DepsgraphCopyContext { + struct GHash *nodes_hash; /* <DepsNode, DepsNode> mapping from src node to dst node */ + struct GHash *rels_hash; // XXX: same for relationships? + + // XXX: filtering criteria... +} DepsgraphCopyContext; + +/* Internal Filtering API ---------------------------------------------- */ + +/* Create filtering context */ +// XXX: needs params for conditions? +DepsgraphCopyContext *DEG_filter_init(void); + +/* Free filtering context once filtering is done */ +void DEG_filter_cleanup(DepsgraphCopyContext *dcc); + + +/* Data Copy Operations ------------------------------------------------ */ + +/** + * Make a (deep) copy of provided node and it's little subgraph + * \warning Newly created node is not added to the existing graph + * \param dcc: Context info for helping resolve links + */ +DepsNode *DEG_copy_node(DepsgraphCopyContext *dcc, const DepsNode *src); + +/* Node Types Handling ================================================= */ + +/* "Typeinfo" for Node Types ------------------------------------------- */ + +/* Typeinfo Struct (nti) */ +struct DepsNodeFactory { + virtual eDepsNode_Type type() const = 0; + virtual eDepsNode_Class tclass() const = 0; + virtual const char *tname() const = 0; + + virtual DepsNode *create_node(const ID *id, const string &subdata, const string &name) const = 0; + virtual DepsNode *copy_node(DepsgraphCopyContext *dcc, const DepsNode *copy) const = 0; +}; + +template <class NodeType> +struct DepsNodeFactoryImpl : public DepsNodeFactory { + eDepsNode_Type type() const { return NodeType::typeinfo.type; } + eDepsNode_Class tclass() const { return NodeType::typeinfo.tclass; } + const char *tname() const { return NodeType::typeinfo.tname; } + + DepsNode *create_node(const ID *id, const string &subdata, const string &name) const + { + DepsNode *node = OBJECT_GUARDED_NEW(NodeType); + + /* populate base node settings */ + node->type = type(); + node->tclass = tclass(); + + if (!name.empty()) + /* set name if provided ... */ + node->name = name; + else + /* ... otherwise use default type name */ + node->name = tname(); + + node->init(id, subdata); + + return node; + } + + virtual DepsNode *copy_node(DepsgraphCopyContext *dcc, const DepsNode *copy) const + { + BLI_assert(copy->type == type()); + DepsNode *node = OBJECT_GUARDED_NEW(NodeType); + + /* populate base node settings */ + node->type = type(); + node->tclass = tclass(); + // XXX: need to review the name here, as we can't have exact duplicates... + node->name = copy->name; + + node->copy(dcc, static_cast<const NodeType *>(copy)); + + return node; + } +}; + +/* Typeinfo Management -------------------------------------------------- */ + +/* Register typeinfo */ +void DEG_register_node_typeinfo(DepsNodeFactory *factory); + +/* Get typeinfo for specified type */ +DepsNodeFactory *DEG_get_node_factory(const eDepsNode_Type type); + +/* Get typeinfo for provided node */ +DepsNodeFactory *DEG_node_get_factory(const DepsNode *node); + +/* Editors Integration -------------------------------------------------- */ + +void deg_editors_id_update(struct Main *bmain, struct ID *id); + +void deg_editors_scene_update(struct Main *bmain, struct Scene *scene, bool updated); + +#endif /* __DEPSGRAPH_INTERN_H__ */ diff --git a/source/blender/depsgraph/intern/depsgraph_query.cc b/source/blender/depsgraph/intern/depsgraph_query.cc new file mode 100644 index 00000000000..73193747b93 --- /dev/null +++ b/source/blender/depsgraph/intern/depsgraph_query.cc @@ -0,0 +1,217 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph_query.cc + * \ingroup depsgraph + * + * Implementation of Querying and Filtering API's + */ + +#include "MEM_guardedalloc.h" + +extern "C" { +#include "BLI_utildefines.h" +#include "BLI_ghash.h" + +#include "BKE_main.h" + +#include "DEG_depsgraph_query.h" +} /* extern "C" */ + +#include "depsgraph_queue.h" +#include "depsnode.h" +#include "depsnode_operation.h" +#include "depsgraph_intern.h" + +/* ************************* */ +/* Low-Level Graph Traversal */ + +#if 0 +/* Prepare for graph traversal, by tagging nodes, etc. */ +static void DEG_graph_traverse_begin(Depsgraph * /*graph*/) +{ + /* go over all nodes, initialising the valence counts */ + // XXX: this will end up being O(|V|), which is bad when we're just updating a few nodes... +} + +/* Perform a traversal of graph from given starting node (in execution order) */ +// TODO: additional flags for controlling the process? +void DEG_graph_traverse_from_node(Depsgraph *graph, OperationDepsNode *start_node, + DEG_FilterPredicate filter, void *filter_data, + DEG_NodeOperation op, void *operation_data) +{ + DepsgraphQueue *q; + + /* sanity checks */ + if (ELEM(NULL, graph, start_node, op)) + return; + + /* add node as starting node to be evaluated, with value of 0 */ + q = DEG_queue_new(); + + start_node->num_links_pending = 0; + DEG_queue_push(q, start_node, 0.0f); + + /* while we still have nodes in the queue, grab and work on next one */ + do { + /* grab item at front of queue */ + // XXX: in practice, we may need to wait until one becomes available... + OperationDepsNode *node = (OperationDepsNode *)DEG_queue_pop(q); + + /* perform operation on node */ + op(graph, node, operation_data); + + /* schedule up operations which depend on this */ + DEPSNODE_RELATIONS_ITER_BEGIN(node->outlinks, rel) + { + /* ensure that relationship is not tagged for ignoring (i.e. cyclic, etc.) */ + // TODO: cyclic refs should probably all get clustered towards the end, so that we can just stop on the first one + if ((rel->flag & DEPSREL_FLAG_CYCLIC) == 0) { + OperationDepsNode *child_node = (OperationDepsNode *)rel->to; + + /* only visit node if the filtering function agrees */ + if ((filter == NULL) || filter(graph, child_node, filter_data)) { + /* schedule up node... */ + child_node->num_links_pending--; + DEG_queue_push(q, child_node, (float)child_node->num_links_pending); + } + } + } + DEPSNODE_RELATIONS_ITER_END; + } while (DEG_queue_is_empty(q) == false); + + /* cleanup */ + DEG_queue_free(q); +} +#endif + +/* ************************************************************** */ +/* Filtering API - Basically, making a copy of the existing graph */ + +/* Create filtering context */ +// TODO: allow passing in a number of criteria? +DepsgraphCopyContext *DEG_filter_init() +{ + DepsgraphCopyContext *dcc = (DepsgraphCopyContext *)MEM_callocN(sizeof(DepsgraphCopyContext), "DepsgraphCopyContext"); + + /* init hashes for easy lookups */ + dcc->nodes_hash = BLI_ghash_ptr_new("Depsgraph Filter NodeHash"); + dcc->rels_hash = BLI_ghash_ptr_new("Depsgraph Filter Relationship Hash"); // XXX? + + /* store filtering criteria? */ + // xxx... + + return dcc; +} + +/* Cleanup filtering context */ +void DEG_filter_cleanup(DepsgraphCopyContext *dcc) +{ + /* sanity check */ + if (dcc == NULL) + return; + + /* free hashes - contents are weren't copied, so are ok... */ + BLI_ghash_free(dcc->nodes_hash, NULL, NULL); + BLI_ghash_free(dcc->rels_hash, NULL, NULL); + + /* clear filtering criteria */ + // ... + + /* free dcc itself */ + MEM_freeN(dcc); +} + +/* -------------------------------------------------- */ + +/* Create a copy of provided node */ +// FIXME: the handling of sub-nodes and links will need to be subject to filtering options... +// XXX: perhaps this really shouldn't be exposed, as it will just be a sub-step of the evaluation process? +DepsNode *DEG_copy_node(DepsgraphCopyContext *dcc, const DepsNode *src) +{ + /* sanity check */ + if (src == NULL) + return NULL; + + DepsNodeFactory *factory = DEG_get_node_factory(src->type); + BLI_assert(factory != NULL); + DepsNode *dst = factory->copy_node(dcc, src); + + /* add this node-pair to the hash... */ + BLI_ghash_insert(dcc->nodes_hash, (DepsNode *)src, dst); + +#if 0 /* XXX TODO */ + /* now, fix up any links in standard "node header" (i.e. DepsNode struct, that all + * all others are derived from) that are now corrupt + */ + { + /* relationships to other nodes... */ + // FIXME: how to handle links? We may only have partial set of all nodes still? + // XXX: the exact details of how to handle this are really part of the querying API... + + // XXX: BUT, for copying subgraphs, we'll need to define an API for doing this stuff anyways + // (i.e. for resolving and patching over links that exist within subtree...) + dst->inlinks.clear(); + dst->outlinks.clear(); + + /* clear traversal data */ + dst->num_links_pending = 0; + dst->lasttime = 0; + } + + /* fix links */ + // XXX... +#endif + + /* return copied node */ + return dst; +} + +bool DEG_id_type_tagged(Main *bmain, short idtype) +{ + return bmain->id_tag_update[((unsigned char *)&idtype)[0]] != 0; +} + +short DEG_get_eval_flags_for_id(Depsgraph *graph, ID *id) +{ + if (graph == NULL) { + /* Happens when converting objects to mesh from a python script + * after modifying scene graph. + * + * Currently harmless because it's only called for temporary + * objects which are out of the DAG anyway. + */ + return 0; + } + + IDDepsNode *id_node = graph->find_id_node(id); + if (id_node == NULL) { + /* TODO(sergey): Does it mean we need to check set scene? */ + return 0; + } + + return id_node->eval_flags; +} diff --git a/source/blender/depsgraph/intern/depsgraph_queue.cc b/source/blender/depsgraph/intern/depsgraph_queue.cc new file mode 100644 index 00000000000..da60d73bc46 --- /dev/null +++ b/source/blender/depsgraph/intern/depsgraph_queue.cc @@ -0,0 +1,177 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph_queue.cc + * \ingroup depsgraph + * + * Implementation of special queue type for use in Depsgraph traversals. + */ + +#include <stdlib.h> + +#include "MEM_guardedalloc.h" + +extern "C" { +#include "BLI_utildefines.h" +#include "BLI_heap.h" +#include "BLI_ghash.h" +} /* extern "C" */ + +#include "depsgraph_queue.h" + +/* ****************************** */ +/* Depsgraph Queue implementation */ + +/* Data Management ----------------------------------------- */ + +DepsgraphQueue *DEG_queue_new(void) +{ + DepsgraphQueue *q = (DepsgraphQueue *)MEM_callocN(sizeof(DepsgraphQueue), "DEG_queue_new()"); + + /* init data structures for use here */ + q->pending_heap = BLI_heap_new(); + q->pending_hash = BLI_ghash_ptr_new("DEG Queue Pending Hash"); + + q->ready_heap = BLI_heap_new(); + + /* init settings */ + q->idx = 0; + q->tot = 0; + + /* return queue */ + return q; +} + +void DEG_queue_free(DepsgraphQueue *q) +{ + /* free data structures */ + BLI_assert(BLI_heap_size(q->pending_heap) == 0); + BLI_assert(BLI_heap_size(q->ready_heap) == 0); + BLI_assert(BLI_ghash_size(q->pending_hash) == 0); + + BLI_heap_free(q->pending_heap, NULL); + BLI_heap_free(q->ready_heap, NULL); + BLI_ghash_free(q->pending_hash, NULL, NULL); + + /* free queue itself */ + MEM_freeN(q); +} + +/* Statistics --------------------------------------------- */ + +/* Get the number of nodes which are we should visit, but are not able to yet */ +size_t DEG_queue_num_pending(DepsgraphQueue *q) +{ + return BLI_heap_size(q->pending_heap); +} + +/* Get the number of nodes which are now ready to be visited */ +size_t DEG_queue_num_ready(DepsgraphQueue *q) +{ + return BLI_heap_size(q->ready_heap); +} + +/* Get total size of queue */ +size_t DEG_queue_size(DepsgraphQueue *q) +{ + return DEG_queue_num_pending(q) + DEG_queue_num_ready(q); +} + +/* Check if queue has any items in it (still passing through) */ +bool DEG_queue_is_empty(DepsgraphQueue *q) +{ + return DEG_queue_size(q) == 0; +} + +/* Queue Operations --------------------------------------- */ + +/** + * Add DepsNode to the queue + * \param dnode: ``(DepsNode *)`` node to add to the queue + * Each node is only added once to the queue; Subsequent pushes + * merely update its status (e.g. moving it from "pending" to "ready") + * \param cost: new "num_links_pending" count for node *after* it has encountered + * via an outlink from the node currently being visited + * (i.e. we're one of the dependencies which may now be able to be processed) + */ +void DEG_queue_push(DepsgraphQueue *q, void *dnode, float cost) +{ + HeapNode *hnode = NULL; + + /* Shortcut: Directly add to ready if node isn't waiting on anything now... */ + if (cost == 0) { + /* node is now ready to be visited - schedule it up for such */ + if (BLI_ghash_haskey(q->pending_hash, dnode)) { + /* remove from pending queue - we're moving it to the scheduling queue */ + hnode = (HeapNode *)BLI_ghash_lookup(q->pending_hash, dnode); + BLI_heap_remove(q->pending_heap, hnode); + + BLI_ghash_remove(q->pending_hash, dnode, NULL, NULL); + } + + /* schedule up node using latest count (of ready nodes) */ + BLI_heap_insert(q->ready_heap, (float)q->idx, dnode); + q->idx++; + } + else { + /* node is still waiting on some other ancestors, + * so add it to the pending heap in the meantime... + */ + // XXX: is this even necessary now? + if (BLI_ghash_haskey(q->pending_hash, dnode)) { + /* just update cost on pending node */ + hnode = (HeapNode *)BLI_ghash_lookup(q->pending_hash, dnode); + BLI_heap_remove(q->pending_heap, hnode); + BLI_heap_insert(q->pending_heap, cost, hnode); + } + else { + /* add new node to pending queue, and increase size of overall queue */ + hnode = BLI_heap_insert(q->pending_heap, cost, dnode); + q->tot++; + } + } +} + +/* Grab a "ready" node from the queue */ +void *DEG_queue_pop(DepsgraphQueue *q) +{ + /* sanity check: if there are no "ready" nodes, + * start pulling from "pending" to keep things moving, + * but throw a warning so that we know that something's up here... + */ + if (BLI_heap_is_empty(q->ready_heap)) { + // XXX: this should never happen + // XXX: if/when it does happen, we may want instead to just wait until something pops up here... + printf("DepsgraphHeap Warning: No more ready nodes available. Trying from pending (idx = %d, tot = %d, pending = %d, ready = %d)\n", + (int)q->idx, (int)q->tot, (int)DEG_queue_num_pending(q), (int)DEG_queue_num_ready(q)); + + return BLI_heap_popmin(q->pending_heap); + } + else { + /* only grab "ready" nodes */ + return BLI_heap_popmin(q->ready_heap); + } +} diff --git a/source/blender/depsgraph/intern/depsgraph_queue.h b/source/blender/depsgraph/intern/depsgraph_queue.h new file mode 100644 index 00000000000..b85d46bd173 --- /dev/null +++ b/source/blender/depsgraph/intern/depsgraph_queue.h @@ -0,0 +1,91 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph_queue.h + * \ingroup depsgraph + * + * Defines for special queue type for use in Depsgraph traversals. + */ + +#ifndef __DEPSGRAPH_QUEUE_H__ +#define __DEPSGRAPH_QUEUE_H__ + +struct DepsNode; + +struct Heap; +struct GHash; + +/* *********************************************** */ +/* Dependency Graph Traversal Queue + * + * There are two parts to this: + * a) "Pending" Nodes - This part contains the set of nodes + * which are related to those which have been visited + * previously, but are not yet ready to actually be visited. + * b) "Scheduled" Nodes - These are the nodes whose ancestors + * have all been evaluated already, which means that any + * or all of them can be picked (in practically in order) to + * be visited immediately. + * + * Internally, the queue makes sure that each node in the graph + * only gets added to the queue once. This is because there can + * be multiple inlinks to each node given the way that the relations + * work. + */ + +/* Depsgraph Queue Type */ +typedef struct DepsgraphQueue { + /* Pending */ + struct Heap *pending_heap; /* (valence:int, DepsNode*) */ + struct GHash *pending_hash; /* (DepsNode* : HeapNode*>) */ + + /* Ready to be visited - fifo */ + struct Heap *ready_heap; /* (idx:int, DepsNode*) */ + + /* Size/Order counts */ + size_t idx; /* total number of nodes which are/have been ready so far (including those already visited) */ + size_t tot; /* total number of nodes which have passed through queue; mainly for debug */ +} DepsgraphQueue; + +/* ************************** */ +/* Depsgraph Queue Operations */ + +/* Data management */ +DepsgraphQueue *DEG_queue_new(void); +void DEG_queue_free(DepsgraphQueue *q); + +/* Statistics */ +size_t DEG_queue_num_pending(DepsgraphQueue *q); +size_t DEG_queue_num_ready(DepsgraphQueue *q); + +size_t DEG_queue_size(DepsgraphQueue *q); +bool DEG_queue_is_empty(DepsgraphQueue *q); + +/* Operations */ +void DEG_queue_push(DepsgraphQueue *q, void *dnode, float cost = 0.0f); +void *DEG_queue_pop(DepsgraphQueue *q); + +#endif /* DEPSGRAPH_QUEUE_H */ diff --git a/source/blender/depsgraph/intern/depsgraph_tag.cc b/source/blender/depsgraph/intern/depsgraph_tag.cc new file mode 100644 index 00000000000..65d75fccad3 --- /dev/null +++ b/source/blender/depsgraph/intern/depsgraph_tag.cc @@ -0,0 +1,541 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph_tag.cc + * \ingroup depsgraph + * + * Core routines for how the Depsgraph works. + */ + +#include <stdio.h> +#include <cstring> +#include <queue> + +extern "C" { +#include "BLI_utildefines.h" + +#include "DNA_object_types.h" +#include "DNA_particle_types.h" +#include "DNA_screen_types.h" +#include "DNA_windowmanager_types.h" + +#include "BKE_library.h" +#include "BKE_main.h" +#include "BKE_node.h" + +#define new new_ +#include "BKE_screen.h" +#undef new + +#include "DEG_depsgraph.h" +} /* extern "C" */ + +#include "depsgraph_debug.h" +#include "depsnode.h" +#include "depsnode_component.h" +#include "depsnode_operation.h" +#include "depsgraph_intern.h" + +/* *********************** */ +/* Update Tagging/Flushing */ + +/* Legacy depsgraph did some special trickery for things like particle systems + * when tagging ID for an update. Ideally that tagging needs to become obsolete + * in favor of havng dedicated node for that which gets tagged, but for until + * design of those areas is more clear we'll do the same legacy code here. + * - sergey - + */ +#define DEPSGRAPH_USE_LEGACY_TAGGING + +namespace { + +/* Data-Based Tagging ------------------------------- */ + +void lib_id_recalc_tag(Main *bmain, ID *id) +{ + id->flag |= LIB_ID_RECALC; + DEG_id_type_tag(bmain, GS(id->name)); +} + +void lib_id_recalc_data_tag(Main *bmain, ID *id) +{ + id->flag |= LIB_ID_RECALC_DATA; + DEG_id_type_tag(bmain, GS(id->name)); +} + +void lib_id_recalc_tag_flag(Main *bmain, ID *id, int flag) +{ + if (flag) { + /* This bit of code ensures legacy object->recalc flags + * are still filled in the same way as it was expected + * with the old dependency graph. + * + * This is because some areas like motion paths and likely + * some other physics baking process are doing manual scene + * update on all the frames, trying to minimize number of + * updates. + * + * But this flag will also let us to re-construct entry + * nodes for update after relations update and after layer + * visibility changes. + */ + short idtype = GS(id->name); + if (idtype == ID_OB) { + Object *object = (Object *)id; + object->recalc |= (flag & OB_RECALC_ALL); + } + + if (flag & OB_RECALC_OB) + lib_id_recalc_tag(bmain, id); + if (flag & (OB_RECALC_DATA | PSYS_RECALC)) + lib_id_recalc_data_tag(bmain, id); + } + else { + lib_id_recalc_tag(bmain, id); + } +} + +#ifdef DEPSGRAPH_USE_LEGACY_TAGGING +void depsgraph_legacy_handle_update_tag(Main *bmain, ID *id, short flag) +{ + if (flag) { + Object *object; + short idtype = GS(id->name); + if (idtype == ID_PA) { + ParticleSystem *psys; + for (object = (Object *)bmain->object.first; + object != NULL; + object = (Object *)object->id.next) + { + for (psys = (ParticleSystem *)object->particlesystem.first; + psys != NULL; + psys = (ParticleSystem *)psys->next) + { + if (&psys->part->id == id) { + DEG_id_tag_update_ex(bmain, &object->id, flag & OB_RECALC_ALL); + psys->recalc |= (flag & PSYS_RECALC); + } + } + } + } + } +} +#endif + +} /* namespace */ + +/* Tag all nodes in ID-block for update. + * This is a crude measure, but is most convenient for old code. + */ +void DEG_graph_id_tag_update(Main *bmain, Depsgraph *graph, ID *id) +{ + IDDepsNode *node = graph->find_id_node(id); + lib_id_recalc_tag(bmain, id); + if (node != NULL) { + node->tag_update(graph); + } +} + +/* Tag nodes related to a specific piece of data */ +void DEG_graph_data_tag_update(Depsgraph *graph, const PointerRNA *ptr) +{ + DepsNode *node = graph->find_node_from_pointer(ptr, NULL); + if (node) { + node->tag_update(graph); + } + else { + printf("Missing node in %s\n", __func__); + BLI_assert(!"Shouldn't happens since it'll miss crucial update."); + } +} + +/* Tag nodes related to a specific property. */ +void DEG_graph_property_tag_update(Depsgraph *graph, + const PointerRNA *ptr, + const PropertyRNA *prop) +{ + DepsNode *node = graph->find_node_from_pointer(ptr, prop); + if (node) { + node->tag_update(graph); + } + else { + printf("Missing node in %s\n", __func__); + BLI_assert(!"Shouldn't happens since it'll miss crucial update."); + } +} + +/* Tag given ID for an update in all the dependency graphs. */ +void DEG_id_tag_update(ID *id, short flag) +{ + DEG_id_tag_update_ex(G.main, id, flag); +} + +void DEG_id_tag_update_ex(Main *bmain, ID *id, short flag) +{ + if (id == NULL) { + /* Ideally should not happen, but old depsgraph allowed this. */ + return; + } + DEG_DEBUG_PRINTF("%s: id=%s flag=%d\n", __func__, id->name, flag); + lib_id_recalc_tag_flag(bmain, id, flag); + for (Scene *scene = (Scene *)bmain->scene.first; + scene != NULL; + scene = (Scene *)scene->id.next) + { + if (scene->depsgraph) { + Depsgraph *graph = scene->depsgraph; + if (flag == 0) { + /* TODO(sergey): Currently blender is still tagging IDs + * for recalc just using flag=0. This isn't totally correct + * but we'd better deal with such cases and don't fail. + */ + DEG_graph_id_tag_update(bmain, graph, id); + continue; + } + if (flag & OB_RECALC_DATA && GS(id->name) == ID_OB) { + Object *object = (Object *)id; + if (object->data != NULL) { + DEG_graph_id_tag_update(bmain, + graph, + (ID *)object->data); + } + } + if (flag & (OB_RECALC_OB | OB_RECALC_DATA)) { + DEG_graph_id_tag_update(bmain, graph, id); + } + } + } + +#ifdef DEPSGRAPH_USE_LEGACY_TAGGING + /* Special handling from the legacy depsgraph. + * TODO(sergey): Need to get rid of those once all the areas + * are re-formulated in terms of franular nodes. + */ + depsgraph_legacy_handle_update_tag(bmain, id, flag); +#endif +} + +/* Tag given ID type for update. */ +void DEG_id_type_tag(Main *bmain, short idtype) +{ + if (idtype == ID_NT) { + /* Stupid workaround so parent datablocks of nested nodetree get looped + * over when we loop over tagged datablock types. + */ + DEG_id_type_tag(bmain, ID_MA); + DEG_id_type_tag(bmain, ID_TE); + DEG_id_type_tag(bmain, ID_LA); + DEG_id_type_tag(bmain, ID_WO); + DEG_id_type_tag(bmain, ID_SCE); + } + /* We tag based on first ID type character to avoid + * looping over all ID's in case there are no tags. + */ + bmain->id_tag_update[((unsigned char *)&idtype)[0]] = 1; +} + +/* Update Flushing ---------------------------------- */ + +/* FIFO queue for tagged nodes that need flushing */ +/* XXX This may get a dedicated implementation later if needed - lukas */ +typedef std::queue<OperationDepsNode *> FlushQueue; + +/* Flush updates from tagged nodes outwards until all affected nodes are tagged. */ +void DEG_graph_flush_updates(Main *bmain, Depsgraph *graph) +{ + /* sanity check */ + if (graph == NULL) + return; + + /* Nothing to update, early out. */ + if (graph->entry_tags.size() == 0) { + return; + } + + /* TODO(sergey): With a bit of flag magic we can get rid of this + * extra loop. + */ + for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin(); + it != graph->operations.end(); + ++it) + { + OperationDepsNode *node = *it; + node->scheduled = false; + } + + FlushQueue queue; + /* Starting from the tagged "entry" nodes, flush outwards... */ + /* NOTE: Also need to ensure that for each of these, there is a path back to + * root, or else they won't be done. + * NOTE: Count how many nodes we need to handle - entry nodes may be + * component nodes which don't count for this purpose! + */ + for (Depsgraph::EntryTags::const_iterator it = graph->entry_tags.begin(); + it != graph->entry_tags.end(); + ++it) + { + OperationDepsNode *node = *it; + IDDepsNode *id_node = node->owner->owner; + queue.push(node); + deg_editors_id_update(bmain, id_node->id); + node->scheduled = true; + } + + while (!queue.empty()) { + OperationDepsNode *node = queue.front(); + queue.pop(); + + IDDepsNode *id_node = node->owner->owner; + lib_id_recalc_tag(bmain, id_node->id); + /* TODO(sergey): For until we've got proper data nodes in the graph. */ + lib_id_recalc_data_tag(bmain, id_node->id); + + ID *id = id_node->id; + /* This code is used to preserve those areas which does direct + * object update, + * + * Plus it ensures visibility changes and relations and layers + * visibility update has proper flags to work with. + */ + if (GS(id->name) == ID_OB) { + Object *object = (Object *)id; + ComponentDepsNode *comp_node = node->owner; + if (comp_node->type == DEPSNODE_TYPE_ANIMATION) { + object->recalc |= OB_RECALC_TIME; + } + else if (comp_node->type == DEPSNODE_TYPE_TRANSFORM) { + object->recalc |= OB_RECALC_OB; + } + else { + object->recalc |= OB_RECALC_DATA; + } + } + + /* Flush to nodes along links... */ + for (OperationDepsNode::Relations::const_iterator it = node->outlinks.begin(); + it != node->outlinks.end(); + ++it) + { + DepsRelation *rel = *it; + OperationDepsNode *to_node = (OperationDepsNode *)rel->to; + if (to_node->scheduled == false) { + to_node->flag |= DEPSOP_FLAG_NEEDS_UPDATE; + queue.push(to_node); + to_node->scheduled = true; + deg_editors_id_update(bmain, id_node->id); + } + } + + /* TODO(sergey): For until incremental updates are possible + * witin a component at least we tag the whole component + * for update. + */ + for (ComponentDepsNode::OperationMap::iterator it = node->owner->operations.begin(); + it != node->owner->operations.end(); + ++it) + { + OperationDepsNode *op = it->second; + op->flag |= DEPSOP_FLAG_NEEDS_UPDATE; + } + } +} + +/* Recursively push updates out to all nodes dependent on this, + * until all affected are tagged and/or scheduled up for eval + */ +void DEG_ids_flush_tagged(Main *bmain) +{ + for (Scene *scene = (Scene *)bmain->scene.first; + scene != NULL; + scene = (Scene *)scene->id.next) + { + /* TODO(sergey): Only visible scenes? */ + if (scene->depsgraph != NULL) { + DEG_graph_flush_updates(bmain, scene->depsgraph); + } + } +} + +/* Clear tags from all operation nodes. */ +void DEG_graph_clear_tags(Depsgraph *graph) +{ + /* Go over all operation nodes, clearing tags. */ + for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin(); + it != graph->operations.end(); + ++it) + { + OperationDepsNode *node = *it; + + /* Clear node's "pending update" settings. */ + node->flag &= ~(DEPSOP_FLAG_DIRECTLY_MODIFIED | DEPSOP_FLAG_NEEDS_UPDATE); + /* Reset so that it can be bumped up again. */ + node->num_links_pending = 0; + node->scheduled = false; + } + + /* Clear any entry tags which haven't been flushed. */ + graph->entry_tags.clear(); +} + +/* Update dependency graph when visible scenes/layers changes. */ +void DEG_graph_on_visible_update(Main *bmain, Scene *scene) +{ + Depsgraph *graph = scene->depsgraph; + wmWindowManager *wm = (wmWindowManager *)bmain->wm.first; + int old_layers = graph->layers; + if (wm != NULL) { + BKE_main_id_flag_listbase(&bmain->scene, LIB_DOIT, true); + graph->layers = 0; + for (wmWindow *win = (wmWindow *)wm->windows.first; + win != NULL; + win = (wmWindow *)win->next) + { + Scene *scene = win->screen->scene; + if (scene->id.flag & LIB_DOIT) { + graph->layers |= BKE_screen_visible_layers(win->screen, scene); + scene->id.flag &= ~LIB_DOIT; + } + } + } + else { + /* All the layers for background render for now. */ + graph->layers = (1 << 20) - 1; + } + if (old_layers != graph->layers) { + /* Tag all objects which becomes visible (or which becomes needed for dependencies) + * for recalc. + * + * This is mainly needed on file load only, after that updates of invisible objects + * will be stored in the pending list. + */ + for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin(); + it != graph->operations.end(); + ++it) + { + OperationDepsNode *node = *it; + IDDepsNode *id_node = node->owner->owner; + ID *id = id_node->id; + if ((id->flag & LIB_ID_RECALC_ALL) != 0 || + (id_node->layers & scene->lay_updated) == 0) + { + id_node->tag_update(graph); + } + /* A bit of magic: if object->recalc is set it means somebody tagged + * it for update. If corresponding ID recalc flags are zero it means + * graph has been evaluated after that and the recalc was skipped + * because of visibility check. + */ + if (GS(id->name) == ID_OB) { + Object *object = (Object *)id; + if ((id->flag & LIB_ID_RECALC_ALL) == 0 && + (object->recalc & OB_RECALC_ALL) != 0) + { + id_node->tag_update(graph); + ComponentDepsNode *anim_comp = + id_node->find_component(DEPSNODE_TYPE_ANIMATION); + if (anim_comp != NULL && object->recalc & OB_RECALC_TIME) { + anim_comp->tag_update(graph); + } + } + } + } + } + scene->lay_updated |= graph->layers; +} + +void DEG_on_visible_update(Main *bmain, const bool UNUSED(do_time)) +{ + for (Scene *scene = (Scene *)bmain->scene.first; + scene != NULL; + scene = (Scene *)scene->id.next) + { + if (scene->depsgraph != NULL) { + DEG_graph_on_visible_update(bmain, scene); + } + } +} + +/* Check if something was changed in the database and inform + * editors about this. + */ +void DEG_ids_check_recalc(Main *bmain, Scene *scene, bool time) +{ + ListBase *lbarray[MAX_LIBARRAY]; + int a; + bool updated = false; + + /* Loop over all ID types. */ + a = set_listbasepointers(bmain, lbarray); + while (a--) { + ListBase *lb = lbarray[a]; + ID *id = (ID *)lb->first; + + /* We tag based on first ID type character to avoid + * looping over all ID's in case there are no tags. + */ + if (id && bmain->id_tag_update[(unsigned char)id->name[0]]) { + updated = true; + break; + } + } + + deg_editors_scene_update(bmain, scene, (updated || time)); +} + +void DEG_ids_clear_recalc(Main *bmain) +{ + ListBase *lbarray[MAX_LIBARRAY]; + bNodeTree *ntree; + int a; + + /* TODO(sergey): Re-implement POST_UPDATE_HANDLER_WORKAROUND using entry_tags + * and id_tags storage from the new dependency graph. + */ + + /* Loop over all ID types. */ + a = set_listbasepointers(bmain, lbarray); + while (a--) { + ListBase *lb = lbarray[a]; + ID *id = (ID *)lb->first; + + /* We tag based on first ID type character to avoid + * looping over all ID's in case there are no tags. + */ + if (id && bmain->id_tag_update[(unsigned char)id->name[0]]) { + for (; id; id = (ID *)id->next) { + id->flag &= ~(LIB_ID_RECALC | LIB_ID_RECALC_DATA); + + /* Some ID's contain semi-datablock nodetree */ + ntree = ntreeFromID(id); + if (ntree != NULL) { + ntree->id.flag &= ~(LIB_ID_RECALC | LIB_ID_RECALC_DATA); + } + } + } + } + + memset(bmain->id_tag_update, 0, sizeof(bmain->id_tag_update)); +} diff --git a/source/blender/depsgraph/intern/depsgraph_type_defines.cc b/source/blender/depsgraph/intern/depsgraph_type_defines.cc new file mode 100644 index 00000000000..5a3048a4aa3 --- /dev/null +++ b/source/blender/depsgraph/intern/depsgraph_type_defines.cc @@ -0,0 +1,102 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph_type_defines.cc + * \ingroup depsgraph + * + * Defines and code for core node types. + */ + +extern "C" { +#include "BLI_utildefines.h" +#include "BLI_ghash.h" + +#include "DEG_depsgraph.h" +} /* extern "C" */ + +#include "depsgraph_intern.h" +#include "depsnode.h" +#include "depsnode_component.h" +#include "depsnode_operation.h" + +/* ************ */ +/* External API */ + +/* Global type registry */ + +/** + * \note For now, this is a hashtable not array, since the core node types + * currently do not have contiguous ID values. Using a hash here gives us + * more flexibility, albeit using more memory and also sacrificing a little + * speed. Later on, when things stabilise we may turn this back to an array + * since there are only just a few node types that an array would cope fine... + */ +static GHash *_depsnode_typeinfo_registry = NULL; + +/* Registration ------------------------------------------- */ + +/* Register node type */ +void DEG_register_node_typeinfo(DepsNodeFactory *factory) +{ + BLI_assert(factory != NULL); + BLI_ghash_insert(_depsnode_typeinfo_registry, SET_INT_IN_POINTER(factory->type()), factory); +} + +/* Register all node types */ +void DEG_register_node_types(void) +{ + /* initialise registry */ + _depsnode_typeinfo_registry = BLI_ghash_int_new("Depsgraph Node Type Registry"); + + /* register node types */ + DEG_register_base_depsnodes(); + DEG_register_component_depsnodes(); + DEG_register_operation_depsnodes(); +} + +/* Free registry on exit */ +void DEG_free_node_types(void) +{ + BLI_ghash_free(_depsnode_typeinfo_registry, NULL, NULL); +} + +/* Getters ------------------------------------------------- */ + +/* Get typeinfo for specified type */ +DepsNodeFactory *DEG_get_node_factory(const eDepsNode_Type type) +{ + /* look up type - at worst, it doesn't exist in table yet, and we fail */ + return (DepsNodeFactory *)BLI_ghash_lookup(_depsnode_typeinfo_registry, SET_INT_IN_POINTER(type)); +} + +/* Get typeinfo for provided node */ +DepsNodeFactory *DEG_node_get_factory(const DepsNode *node) +{ + if (!node) + return NULL; + + return DEG_get_node_factory(node->type); +} diff --git a/source/blender/depsgraph/intern/depsgraph_types.h b/source/blender/depsgraph/intern/depsgraph_types.h new file mode 100644 index 00000000000..3616fe85496 --- /dev/null +++ b/source/blender/depsgraph/intern/depsgraph_types.h @@ -0,0 +1,173 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph_types.h + * \ingroup depsgraph + * + * Datatypes for internal use in the Depsgraph + * + * All of these datatypes are only really used within the "core" depsgraph. + * In particular, node types declared here form the structure of operations + * in the graph. + */ + +#ifndef __DEPSGRAPH_TYPES_H__ +#define __DEPSGRAPH_TYPES_H__ + +#include "depsgraph_util_function.h" + +/* TODO(sergey): Ideally we'll just use char* and statically allocated strings + * to avoid any possible overhead caused by string (re)allocation/formatting. + */ +#include <string> +#include <vector> + +using std::string; +using std::vector; + +struct bAction; +struct ChannelDriver; +struct ModifierData; +struct PointerRNA; +struct EvaluationContext; +struct FCurve; + +/* Evaluation Operation for atomic operation */ +// XXX: move this to another header that can be exposed? +typedef function<void(struct EvaluationContext *)> DepsEvalOperationCb; + +/* Metatype of Nodes - The general "level" in the graph structure the node serves */ +typedef enum eDepsNode_Class { + DEPSNODE_CLASS_GENERIC = 0, /* Types generally unassociated with user-visible entities, but needed for graph functioning */ + + DEPSNODE_CLASS_COMPONENT = 1, /* [Outer Node] An "aspect" of evaluating/updating an ID-Block, requiring certain types of evaluation behaviours */ + DEPSNODE_CLASS_OPERATION = 2, /* [Inner Node] A glorified function-pointer/callback for scheduling up evaluation operations for components, subject to relationship requirements */ +} eDepsNode_Class; + +/* Types of Nodes */ +typedef enum eDepsNode_Type { + DEPSNODE_TYPE_UNDEFINED = -1, /* fallback type for invalid return value */ + + DEPSNODE_TYPE_OPERATION = 0, /* Inner Node (Operation) */ + + /* Generic Types */ + DEPSNODE_TYPE_ROOT = 1, /* "Current Scene" - basically whatever kicks off the evaluation process */ + DEPSNODE_TYPE_TIMESOURCE = 2, /* Time-Source */ + + DEPSNODE_TYPE_ID_REF = 3, /* ID-Block reference - used as landmarks/collection point for components, but not usually part of main graph */ + DEPSNODE_TYPE_SUBGRAPH = 4, /* Isolated sub-graph - used for keeping instanced data separate from instances using them */ + + /* Outer Types */ + DEPSNODE_TYPE_PARAMETERS = 11, /* Parameters Component - Default when nothing else fits (i.e. just SDNA property setting) */ + DEPSNODE_TYPE_PROXY = 12, /* Generic "Proxy-Inherit" Component */ // XXX: Also for instancing of subgraphs? + DEPSNODE_TYPE_ANIMATION = 13, /* Animation Component */ // XXX: merge in with parameters? + DEPSNODE_TYPE_TRANSFORM = 14, /* Transform Component (Parenting/Constraints) */ + DEPSNODE_TYPE_GEOMETRY = 15, /* Geometry Component (DerivedMesh/Displist) */ + DEPSNODE_TYPE_SEQUENCER = 16, /* Sequencer Component (Scene Only) */ + + /* Evaluation-Related Outer Types (with Subdata) */ + DEPSNODE_TYPE_EVAL_POSE = 21, /* Pose Component - Owner/Container of Bones Eval */ + DEPSNODE_TYPE_BONE = 22, /* Bone Component - Child/Subcomponent of Pose */ + + DEPSNODE_TYPE_EVAL_PARTICLES = 23, /* Particle Systems Component */ + DEPSNODE_TYPE_SHADING = 24, /* Material Shading Component */ +} eDepsNode_Type; + +/* Identifiers for common operations (as an enum) */ +typedef enum eDepsOperation_Code { +#define DEF_DEG_OPCODE(label) DEG_OPCODE_##label, +#include "depsnode_opcodes.h" +#undef DEF_DEG_OPCODE +} eDepsOperation_Code; + +/* String defines for these opcodes, defined in depsnode_operation.cpp */ +extern const char *DEG_OPNAMES[]; + + +/* Type of operation */ +typedef enum eDepsOperation_Type { + /* Primary operation types */ + DEPSOP_TYPE_INIT = 0, /* initialise evaluation data */ + DEPSOP_TYPE_EXEC = 1, /* standard evaluation step */ + DEPSOP_TYPE_POST = 2, /* cleanup evaluation data + flush results */ + + /* Additional operation types */ + DEPSOP_TYPE_OUT = 3, /* indicator for outputting a temporary result that other components can use */ // XXX? + DEPSOP_TYPE_SIM = 4, /* indicator for things like IK Solvers and Rigidbody Sim steps which modify final results of separate entities at once */ + DEPSOP_TYPE_REBUILD = 5, /* rebuild internal evaluation data - used for Rigidbody Reset and Armature Rebuild-On-Load */ +} eDepsOperation_Type; + +/* Types of relationships between nodes + * + * This is used to provide additional hints to use when filtering + * the graph, so that we can go without doing more extensive + * data-level checks... + */ +typedef enum eDepsRelation_Type { + /* reationship type unknown/irrelevant */ + DEPSREL_TYPE_STANDARD = 0, + + /* root -> active scene or entity (screen, image, etc.) */ + DEPSREL_TYPE_ROOT_TO_ACTIVE, + + /* general datablock dependency */ + DEPSREL_TYPE_DATABLOCK, + + /* time dependency */ + DEPSREL_TYPE_TIME, + + /* component depends on results of another */ + DEPSREL_TYPE_COMPONENT_ORDER, + + /* relationship is just used to enforce ordering of operations + * (e.g. "init()" callback done before "exec() and "cleanup()") + */ + DEPSREL_TYPE_OPERATION, + + /* relationship results from a property driver affecting property */ + DEPSREL_TYPE_DRIVER, + + /* relationship is something driver depends on */ + DEPSREL_TYPE_DRIVER_TARGET, + + /* relationship is used for transform stack + * (e.g. parenting, user transforms, constraints) + */ + DEPSREL_TYPE_TRANSFORM, + + /* relationship is used for geometry evaluation + * (e.g. metaball "motherball" or modifiers) + */ + DEPSREL_TYPE_GEOMETRY_EVAL, + + /* relationship is used to trigger a post-change validity updates */ + DEPSREL_TYPE_UPDATE, + + /* relationship is used to trigger editor/screen updates */ + DEPSREL_TYPE_UPDATE_UI, +} eDepsRelation_Type; + +#endif /* __DEPSGRAPH_TYPES_H__ */ diff --git a/source/blender/depsgraph/intern/depsnode.cc b/source/blender/depsgraph/intern/depsnode.cc new file mode 100644 index 00000000000..1736aadf999 --- /dev/null +++ b/source/blender/depsgraph/intern/depsnode.cc @@ -0,0 +1,316 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsnode.cc + * \ingroup depsgraph + */ + +#include <stdio.h> +#include <string.h> + +#include "BLI_utildefines.h" + +extern "C" { +#include "DNA_ID.h" +#include "DNA_anim_types.h" + +#include "BKE_animsys.h" + +#include "DEG_depsgraph.h" +} + +#include "depsnode.h" /* own include */ +#include "depsnode_component.h" +#include "depsnode_operation.h" +#include "depsgraph_intern.h" + +/* *************** */ +/* Node Management */ + +/* Add ------------------------------------------------ */ + +DepsNode::TypeInfo::TypeInfo(eDepsNode_Type type, const char *tname) +{ + this->type = type; + if (type == DEPSNODE_TYPE_OPERATION) + this->tclass = DEPSNODE_CLASS_OPERATION; + else if (type < DEPSNODE_TYPE_PARAMETERS) + this->tclass = DEPSNODE_CLASS_GENERIC; + else + this->tclass = DEPSNODE_CLASS_COMPONENT; + this->tname = tname; +} + +DepsNode::DepsNode() +{ + this->name[0] = '\0'; +} + +DepsNode::~DepsNode() +{ + /* free links + * note: deleting relations will remove them from the node relations set, + * but only touch the same position as we are using here, which is safe. + */ + DEPSNODE_RELATIONS_ITER_BEGIN(this->inlinks, rel) + { + OBJECT_GUARDED_DELETE(rel, DepsRelation); + } + DEPSNODE_RELATIONS_ITER_END; + + DEPSNODE_RELATIONS_ITER_BEGIN(this->outlinks, rel) + { + OBJECT_GUARDED_DELETE(rel, DepsRelation); + } + DEPSNODE_RELATIONS_ITER_END; +} + + +/* Generic identifier for Depsgraph Nodes. */ +string DepsNode::identifier() const +{ + char typebuf[7]; + sprintf(typebuf, "(%d)", type); + + return string(typebuf) + " : " + name; +} + +/* ************* */ +/* Generic Nodes */ + +/* Time Source Node ============================================== */ + +void TimeSourceDepsNode::tag_update(Depsgraph *graph) +{ + for (DepsNode::Relations::const_iterator it = outlinks.begin(); + it != outlinks.end(); + ++it) + { + DepsRelation *rel = *it; + DepsNode *node = rel->to; + node->tag_update(graph); + } +} + + +/* Root Node ============================================== */ + +RootDepsNode::RootDepsNode() : scene(NULL), time_source(NULL) +{ +} + +RootDepsNode::~RootDepsNode() +{ + OBJECT_GUARDED_DELETE(time_source, TimeSourceDepsNode); +} + +TimeSourceDepsNode *RootDepsNode::add_time_source(const string &name) +{ + if (!time_source) { + DepsNodeFactory *factory = DEG_get_node_factory(DEPSNODE_TYPE_TIMESOURCE); + time_source = (TimeSourceDepsNode *)factory->create_node(NULL, "", name); + /*time_source->owner = this;*/ // XXX + } + return time_source; +} + +DEG_DEPSNODE_DEFINE(RootDepsNode, DEPSNODE_TYPE_ROOT, "Root DepsNode"); +static DepsNodeFactoryImpl<RootDepsNode> DNTI_ROOT; + +/* Time Source Node ======================================= */ + +DEG_DEPSNODE_DEFINE(TimeSourceDepsNode, DEPSNODE_TYPE_TIMESOURCE, "Time Source"); +static DepsNodeFactoryImpl<TimeSourceDepsNode> DNTI_TIMESOURCE; + +/* ID Node ================================================ */ + +/* Initialize 'id' node - from pointer data given. */ +void IDDepsNode::init(const ID *id, const string &UNUSED(subdata)) +{ + /* Store ID-pointer. */ + BLI_assert(id != NULL); + this->id = (ID *)id; + this->layers = (1 << 20) - 1; + this->eval_flags = 0; + + /* NOTE: components themselves are created if/when needed. + * This prevents problems with components getting added + * twice if an ID-Ref needs to be created to house it... + */ +} + +/* Free 'id' node. */ +IDDepsNode::~IDDepsNode() +{ + clear_components(); +} + +/* Copy 'id' node. */ +void IDDepsNode::copy(DepsgraphCopyContext *dcc, const IDDepsNode *src) +{ + (void)src; /* Ignored. */ + /* Iterate over items in original hash, adding them to new hash. */ + for (IDDepsNode::ComponentMap::const_iterator it = this->components.begin(); + it != this->components.end(); + ++it) + { + /* Get current <type : component> mapping. */ + ComponentIDKey c_key = it->first; + DepsNode *old_component = it->second; + + /* Make a copy of component. */ + ComponentDepsNode *component = (ComponentDepsNode *)DEG_copy_node(dcc, old_component); + + /* Add new node to hash... */ + this->components[c_key] = component; + } + + // TODO: perform a second loop to fix up links? + BLI_assert(!"Not expected to be used"); +} + +ComponentDepsNode *IDDepsNode::find_component(eDepsNode_Type type, + const string &name) const +{ + ComponentIDKey key(type, name); + ComponentMap::const_iterator it = components.find(key); + return it != components.end() ? it->second : NULL; +} + +ComponentDepsNode *IDDepsNode::add_component(eDepsNode_Type type, + const string &name) +{ + ComponentIDKey key(type, name); + ComponentDepsNode *comp_node = find_component(type, name); + if (!comp_node) { + DepsNodeFactory *factory = DEG_get_node_factory(type); + comp_node = (ComponentDepsNode *)factory->create_node(this->id, "", name); + + /* Register. */ + this->components[key] = comp_node; + comp_node->owner = this; + } + return comp_node; +} + +void IDDepsNode::remove_component(eDepsNode_Type type, const string &name) +{ + ComponentIDKey key(type, name); + ComponentDepsNode *comp_node = find_component(type, name); + if (comp_node) { + /* Unregister. */ + this->components.erase(key); + OBJECT_GUARDED_DELETE(comp_node, ComponentDepsNode); + } +} + +void IDDepsNode::clear_components() +{ + for (ComponentMap::const_iterator it = components.begin(); + it != components.end(); + ++it) + { + ComponentDepsNode *comp_node = it->second; + OBJECT_GUARDED_DELETE(comp_node, ComponentDepsNode); + } + components.clear(); +} + +void IDDepsNode::tag_update(Depsgraph *graph) +{ + for (ComponentMap::const_iterator it = components.begin(); + it != components.end(); + ++it) + { + ComponentDepsNode *comp_node = it->second; + /* TODO(sergey): What about drievrs? */ + bool do_component_tag = comp_node->type != DEPSNODE_TYPE_ANIMATION; + if (comp_node->type == DEPSNODE_TYPE_ANIMATION) { + AnimData *adt = BKE_animdata_from_id(id); + BLI_assert(adt != NULL); + if (adt->recalc & ADT_RECALC_ANIM) { + do_component_tag = true; + } + } + if (do_component_tag) { + comp_node->tag_update(graph); + } + } +} + +DEG_DEPSNODE_DEFINE(IDDepsNode, DEPSNODE_TYPE_ID_REF, "ID Node"); +static DepsNodeFactoryImpl<IDDepsNode> DNTI_ID_REF; + +/* Subgraph Node ========================================== */ + +/* Initialize 'subgraph' node - from pointer data given. */ +void SubgraphDepsNode::init(const ID *id, const string &UNUSED(subdata)) +{ + /* Store ID-ref if provided. */ + this->root_id = (ID *)id; + + /* NOTE: graph will need to be added manually, + * as we don't have any way of passing this down. + */ +} + +/* Free 'subgraph' node */ +SubgraphDepsNode::~SubgraphDepsNode() +{ + /* Only free if graph not shared, of if this node is the first + * reference to it... + */ + // XXX: prune these flags a bit... + if ((this->flag & SUBGRAPH_FLAG_FIRSTREF) || !(this->flag & SUBGRAPH_FLAG_SHARED)) { + /* Free the referenced graph. */ + DEG_graph_free(this->graph); + this->graph = NULL; + } +} + +/* Copy 'subgraph' node - Assume that the subgraph doesn't get copied for now... */ +void SubgraphDepsNode::copy(DepsgraphCopyContext * /*dcc*/, + const SubgraphDepsNode * /*src*/) +{ + //const SubgraphDepsNode *src_node = (const SubgraphDepsNode *)src; + //SubgraphDepsNode *dst_node = (SubgraphDepsNode *)dst; + + /* for now, subgraph itself isn't copied... */ + BLI_assert(!"Not expected to be used"); +} + +DEG_DEPSNODE_DEFINE(SubgraphDepsNode, DEPSNODE_TYPE_SUBGRAPH, "Subgraph Node"); +static DepsNodeFactoryImpl<SubgraphDepsNode> DNTI_SUBGRAPH; + + +void DEG_register_base_depsnodes() +{ + DEG_register_node_typeinfo(&DNTI_ROOT); + DEG_register_node_typeinfo(&DNTI_TIMESOURCE); + + DEG_register_node_typeinfo(&DNTI_ID_REF); + DEG_register_node_typeinfo(&DNTI_SUBGRAPH); +} diff --git a/source/blender/depsgraph/intern/depsnode.h b/source/blender/depsgraph/intern/depsnode.h new file mode 100644 index 00000000000..53826ae8e71 --- /dev/null +++ b/source/blender/depsgraph/intern/depsnode.h @@ -0,0 +1,248 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsnode.h + * \ingroup depsgraph + */ + +#ifndef __DEPSNODE_H__ +#define __DEPSNODE_H__ + +#include "depsgraph_types.h" + +#include "depsgraph_util_hash.h" +#include "depsgraph_util_map.h" +#include "depsgraph_util_set.h" + +struct ID; +struct Scene; + +struct Depsgraph; +struct DepsRelation; +struct DepsgraphCopyContext; +struct OperationDepsNode; + +/* *********************************** */ +/* Base-Defines for Nodes in Depsgraph */ + +/* All nodes in Depsgraph are descended from this. */ +struct DepsNode { + /* Helper class for static typeinfo in subclasses. */ + struct TypeInfo { + TypeInfo(eDepsNode_Type type, const char *tname); + + eDepsNode_Type type; + eDepsNode_Class tclass; + const char *tname; + }; + + /* Identifier - mainly for debugging purposes. */ + string name; + + /* Structural type of node. */ + eDepsNode_Type type; + + /* Type of data/behaviour represented by node... */ + eDepsNode_Class tclass; + + /* Relationships between nodes + * The reason why all depsgraph nodes are descended from this type (apart + * from basic serialization benefits - from the typeinfo) is that we can have + * relationships between these nodes! + */ + typedef unordered_set<DepsRelation *> Relations; + + /* Nodes which this one depends on. */ + Relations inlinks; + + /* Nodes which depend on this one. */ + Relations outlinks; + + /* Generic tag for traversal algorithms */ + int done; + + /* Methods. */ + + DepsNode(); + virtual ~DepsNode(); + + virtual string identifier() const; + string full_identifier() const; + + virtual void init(const ID * /*id*/, + const string &/*subdata*/) {} + virtual void copy(DepsgraphCopyContext * /*dcc*/, + const DepsNode * /*src*/) {} + + virtual void tag_update(Depsgraph * /*graph*/) {} + + virtual OperationDepsNode *get_entry_operation() { return NULL; } + virtual OperationDepsNode *get_exit_operation() { return NULL; } +}; + +/* Macros for common static typeinfo. */ +#define DEG_DEPSNODE_DECLARE \ + static const DepsNode::TypeInfo typeinfo +#define DEG_DEPSNODE_DEFINE(NodeType, type_, tname_) \ + const DepsNode::TypeInfo NodeType::typeinfo = DepsNode::TypeInfo(type_, tname_) + +/* Generic Nodes ======================= */ + +struct ComponentDepsNode; +struct IDDepsNode; + +/* Time Source Node. */ +struct TimeSourceDepsNode : public DepsNode { + /* New "current time". */ + float cfra; + + /* time-offset relative to the "official" time source that this one has. */ + float offset; + + // TODO: evaluate() operation needed + + void tag_update(Depsgraph *graph); + + DEG_DEPSNODE_DECLARE; +}; + +/* Root Node. */ +struct RootDepsNode : public DepsNode { + RootDepsNode(); + ~RootDepsNode(); + + TimeSourceDepsNode *add_time_source(const string &name = ""); + + /* scene that this corresponds to */ + Scene *scene; + + /* Entrypoint node for time-changed. */ + TimeSourceDepsNode *time_source; + + DEG_DEPSNODE_DECLARE; +}; + +/* ID-Block Reference */ +struct IDDepsNode : public DepsNode { + struct ComponentIDKey { + ComponentIDKey(eDepsNode_Type type, const string &name = "") + : type(type), name(name) {} + + bool operator== (const ComponentIDKey &other) const + { + return type == other.type && name == other.name; + } + + eDepsNode_Type type; + string name; + }; + + /* XXX can't specialize std::hash for this purpose, because ComponentIDKey is + * a nested type ... + * + * http://stackoverflow.com/a/951245 + */ + struct component_key_hash { + bool operator() (const ComponentIDKey &key) const + { + return hash_combine(hash<int>()(key.type), hash<string>()(key.name)); + } + }; + + typedef unordered_map<ComponentIDKey, + ComponentDepsNode *, + component_key_hash> ComponentMap; + + void init(const ID *id, const string &subdata); + void copy(DepsgraphCopyContext *dcc, const IDDepsNode *src); + ~IDDepsNode(); + + ComponentDepsNode *find_component(eDepsNode_Type type, + const string &name = "") const; + ComponentDepsNode *add_component(eDepsNode_Type type, + const string &name = ""); + void remove_component(eDepsNode_Type type, const string &name = ""); + void clear_components(); + + void tag_update(Depsgraph *graph); + + /* ID Block referenced. */ + ID *id; + + /* Hash to make it faster to look up components. */ + ComponentMap components; + + /* Layers of this node with accumulated layers of it's output relations. */ + int layers; + + /* Additional flags needed for scene evaluation. + * TODO(sergey): Only needed for until really granular updates + * of all the entities. + */ + int eval_flags; + + DEG_DEPSNODE_DECLARE; +}; + +/* Subgraph Reference. */ +struct SubgraphDepsNode : public DepsNode { + void init(const ID *id, const string &subdata); + void copy(DepsgraphCopyContext *dcc, const SubgraphDepsNode *src); + ~SubgraphDepsNode(); + + /* Instanced graph. */ + Depsgraph *graph; + + /* ID-block at root of subgraph (if applicable). */ + ID *root_id; + + /* Number of nodes which use/reference this subgraph - if just 1, it may be + * possible to merge into main, + */ + size_t num_users; + + /* (eSubgraphRef_Flag) assorted settings for subgraph node. */ + int flag; + + DEG_DEPSNODE_DECLARE; +}; + +/* Flags for subgraph node */ +typedef enum eSubgraphRef_Flag { + /* Subgraph referenced is shared with another reference, so shouldn't + * free on exit. + */ + SUBGRAPH_FLAG_SHARED = (1 << 0), + + /* Node is first reference to subgraph, so it can be freed when we are + * removed. + */ + SUBGRAPH_FLAG_FIRSTREF = (1 << 1), +} eSubgraphRef_Flag; + +void DEG_register_base_depsnodes(); + +#endif /* __DEPSNODE_H__ */ diff --git a/source/blender/depsgraph/intern/depsnode_component.cc b/source/blender/depsgraph/intern/depsnode_component.cc new file mode 100644 index 00000000000..1d939c6580d --- /dev/null +++ b/source/blender/depsgraph/intern/depsnode_component.cc @@ -0,0 +1,318 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsnode_component.cc + * \ingroup depsgraph + */ + +#include <stdio.h> +#include <string.h> + +extern "C" { +#include "BLI_utildefines.h" + +#include "DNA_object_types.h" + +#include "BKE_action.h" +} /* extern "C" */ + +#include "depsnode_component.h" /* own include */ +#include "depsnode_operation.h" +#include "depsgraph_intern.h" + +/* *********** */ +/* Outer Nodes */ + +/* Standard Component Methods ============================= */ + +ComponentDepsNode::ComponentDepsNode() : + entry_operation(NULL), + exit_operation(NULL) +{ +} + +/* Initialize 'component' node - from pointer data given */ +void ComponentDepsNode::init(const ID * /*id*/, + const string & /*subdata*/) +{ + /* hook up eval context? */ + // XXX: maybe this needs a special API? +} + +/* Copy 'component' node */ +void ComponentDepsNode::copy(DepsgraphCopyContext * /*dcc*/, + const ComponentDepsNode * /*src*/) +{ +#if 0 // XXX: remove all this + /* duplicate list of operation nodes */ + this->operations.clear(); + + for (OperationMap::const_iterator it = src->operations.begin(); it != src->operations.end(); ++it) { + const string &pchan_name = it->first; + OperationDepsNode *src_op = it->second; + + /* recursive copy */ + DepsNodeFactory *factory = DEG_node_get_factory(src_op); + OperationDepsNode *dst_op = (OperationDepsNode *)factory->copy_node(dcc, src_op); + this->operations[pchan_name] = dst_op; + + /* fix links... */ + // ... + } + + /* copy evaluation contexts */ + // +#endif + BLI_assert(!"Not expected to be called"); +} + +/* Free 'component' node */ +ComponentDepsNode::~ComponentDepsNode() +{ + clear_operations(); +} + +string ComponentDepsNode::identifier() const +{ + string &idname = this->owner->name; + + char typebuf[7]; + sprintf(typebuf, "(%d)", type); + + return string(typebuf) + name + " : " + idname; +} + +OperationDepsNode *ComponentDepsNode::find_operation(OperationIDKey key) const +{ + OperationMap::const_iterator it = this->operations.find(key); + + if (it != this->operations.end()) { + return it->second; + } + else { + fprintf(stderr, "%s: find_operation(%s) failed\n", + this->identifier().c_str(), key.identifier().c_str()); + BLI_assert(!"Request for non-existing operation, should not happen"); + return NULL; + } +} + +OperationDepsNode *ComponentDepsNode::find_operation(eDepsOperation_Code opcode, const string &name) const +{ + OperationIDKey key(opcode, name); + return find_operation(key); +} + +OperationDepsNode *ComponentDepsNode::has_operation(OperationIDKey key) const +{ + OperationMap::const_iterator it = this->operations.find(key); + if (it != this->operations.end()) { + return it->second; + } + return NULL; +} + +OperationDepsNode *ComponentDepsNode::has_operation(eDepsOperation_Code opcode, + const string &name) const +{ + OperationIDKey key(opcode, name); + return has_operation(key); +} + +OperationDepsNode *ComponentDepsNode::add_operation(eDepsOperation_Type optype, DepsEvalOperationCb op, eDepsOperation_Code opcode, const string &name) +{ + OperationDepsNode *op_node = has_operation(opcode, name); + if (!op_node) { + DepsNodeFactory *factory = DEG_get_node_factory(DEPSNODE_TYPE_OPERATION); + op_node = (OperationDepsNode *)factory->create_node(this->owner->id, "", name); + + /* register opnode in this component's operation set */ + OperationIDKey key(opcode, name); + this->operations[key] = op_node; + + /* set as entry/exit node of component (if appropriate) */ + if (optype == DEPSOP_TYPE_INIT) { + BLI_assert(this->entry_operation == NULL); + this->entry_operation = op_node; + } + else if (optype == DEPSOP_TYPE_POST) { + // XXX: review whether DEPSOP_TYPE_OUT is better than DEPSOP_TYPE_POST, or maybe have both? + BLI_assert(this->exit_operation == NULL); + this->exit_operation = op_node; + } + + /* set backlink */ + op_node->owner = this; + } + else { + fprintf(stderr, "add_operation: Operation already exists - %s has %s at %p\n", + this->identifier().c_str(), op_node->identifier().c_str(), op_node); + BLI_assert(!"Should not happen!"); + } + + /* attach extra data */ + op_node->evaluate = op; + op_node->optype = optype; + op_node->opcode = opcode; + op_node->name = name; + + return op_node; +} + +void ComponentDepsNode::remove_operation(eDepsOperation_Code opcode, const string &name) +{ + OperationDepsNode *op_node = find_operation(opcode, name); + if (op_node) { + /* unregister */ + this->operations.erase(OperationIDKey(opcode, name)); + OBJECT_GUARDED_DELETE(op_node, OperationDepsNode); + } +} + +void ComponentDepsNode::clear_operations() +{ + for (OperationMap::const_iterator it = operations.begin(); it != operations.end(); ++it) { + OperationDepsNode *op_node = it->second; + OBJECT_GUARDED_DELETE(op_node, OperationDepsNode); + } + operations.clear(); +} + +void ComponentDepsNode::tag_update(Depsgraph *graph) +{ + OperationDepsNode *entry_op = get_entry_operation(); + if (entry_op != NULL && entry_op->flag & DEPSOP_FLAG_NEEDS_UPDATE) { + return; + } + for (OperationMap::const_iterator it = operations.begin(); it != operations.end(); ++it) { + OperationDepsNode *op_node = it->second; + op_node->tag_update(graph); + } +} + +OperationDepsNode *ComponentDepsNode::get_entry_operation() +{ + if (entry_operation) + return entry_operation; + else if (operations.size() == 1) + return operations.begin()->second; + return NULL; +} + +OperationDepsNode *ComponentDepsNode::get_exit_operation() +{ + if (exit_operation) + return exit_operation; + else if (operations.size() == 1) + return operations.begin()->second; + return NULL; +} + +/* Parameter Component Defines ============================ */ + +DEG_DEPSNODE_DEFINE(ParametersComponentDepsNode, DEPSNODE_TYPE_PARAMETERS, "Parameters Component"); +static DepsNodeFactoryImpl<ParametersComponentDepsNode> DNTI_PARAMETERS; + +/* Animation Component Defines ============================ */ + +DEG_DEPSNODE_DEFINE(AnimationComponentDepsNode, DEPSNODE_TYPE_ANIMATION, "Animation Component"); +static DepsNodeFactoryImpl<AnimationComponentDepsNode> DNTI_ANIMATION; + +/* Transform Component Defines ============================ */ + +DEG_DEPSNODE_DEFINE(TransformComponentDepsNode, DEPSNODE_TYPE_TRANSFORM, "Transform Component"); +static DepsNodeFactoryImpl<TransformComponentDepsNode> DNTI_TRANSFORM; + +/* Proxy Component Defines ================================ */ + +DEG_DEPSNODE_DEFINE(ProxyComponentDepsNode, DEPSNODE_TYPE_PROXY, "Proxy Component"); +static DepsNodeFactoryImpl<ProxyComponentDepsNode> DNTI_PROXY; + +/* Geometry Component Defines ============================= */ + +DEG_DEPSNODE_DEFINE(GeometryComponentDepsNode, DEPSNODE_TYPE_GEOMETRY, "Geometry Component"); +static DepsNodeFactoryImpl<GeometryComponentDepsNode> DNTI_GEOMETRY; + +/* Sequencer Component Defines ============================ */ + +DEG_DEPSNODE_DEFINE(SequencerComponentDepsNode, DEPSNODE_TYPE_SEQUENCER, "Sequencer Component"); +static DepsNodeFactoryImpl<SequencerComponentDepsNode> DNTI_SEQUENCER; + +/* Pose Component ========================================= */ + +DEG_DEPSNODE_DEFINE(PoseComponentDepsNode, DEPSNODE_TYPE_EVAL_POSE, "Pose Eval Component"); +static DepsNodeFactoryImpl<PoseComponentDepsNode> DNTI_EVAL_POSE; + +/* Bone Component ========================================= */ + +/* Initialize 'bone component' node - from pointer data given */ +void BoneComponentDepsNode::init(const ID *id, const string &subdata) +{ + /* generic component-node... */ + ComponentDepsNode::init(id, subdata); + + /* name of component comes is bone name */ + /* TODO(sergey): This sets name to an empty string because subdata is + * empty. Is it a bug? + */ + //this->name = subdata; + + /* bone-specific node data */ + Object *ob = (Object *)id; + this->pchan = BKE_pose_channel_find_name(ob->pose, subdata.c_str()); +} + +DEG_DEPSNODE_DEFINE(BoneComponentDepsNode, DEPSNODE_TYPE_BONE, "Bone Component"); +static DepsNodeFactoryImpl<BoneComponentDepsNode> DNTI_BONE; + +/* Particles Component Defines ============================ */ + +DEG_DEPSNODE_DEFINE(ParticlesComponentDepsNode, DEPSNODE_TYPE_EVAL_PARTICLES, "Particles Component"); +static DepsNodeFactoryImpl<ParticlesComponentDepsNode> DNTI_EVAL_PARTICLES; + +/* Shading Component Defines ============================ */ + +DEG_DEPSNODE_DEFINE(ShadingComponentDepsNode, DEPSNODE_TYPE_SHADING, "Shading Component"); +static DepsNodeFactoryImpl<ShadingComponentDepsNode> DNTI_SHADING; + + +/* Node Types Register =================================== */ + +void DEG_register_component_depsnodes() +{ + DEG_register_node_typeinfo(&DNTI_PARAMETERS); + DEG_register_node_typeinfo(&DNTI_PROXY); + DEG_register_node_typeinfo(&DNTI_ANIMATION); + DEG_register_node_typeinfo(&DNTI_TRANSFORM); + DEG_register_node_typeinfo(&DNTI_GEOMETRY); + DEG_register_node_typeinfo(&DNTI_SEQUENCER); + + DEG_register_node_typeinfo(&DNTI_EVAL_POSE); + DEG_register_node_typeinfo(&DNTI_BONE); + + DEG_register_node_typeinfo(&DNTI_EVAL_PARTICLES); + DEG_register_node_typeinfo(&DNTI_SHADING); +} diff --git a/source/blender/depsgraph/intern/depsnode_component.h b/source/blender/depsgraph/intern/depsnode_component.h new file mode 100644 index 00000000000..e3550bb2371 --- /dev/null +++ b/source/blender/depsgraph/intern/depsnode_component.h @@ -0,0 +1,201 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsnode_component.h + * \ingroup depsgraph + */ + +#ifndef __DEPSNODE_COMPONENT_H__ +#define __DEPSNODE_COMPONENT_H__ + +#include "depsnode.h" + +#include "depsgraph_util_hash.h" +#include "depsgraph_util_map.h" +#include "depsgraph_util_set.h" + +struct ID; +struct bPoseChannel; + +struct Depsgraph; +struct DepsgraphCopyContext; +struct EvaluationContext; +struct OperationDepsNode; +struct BoneComponentDepsNode; + + +/* ID Component - Base type for all components */ +struct ComponentDepsNode : public DepsNode { + /* Key used to look up operations within a component */ + struct OperationIDKey + { + eDepsOperation_Code opcode; + string name; + + + OperationIDKey() : + opcode(DEG_OPCODE_OPERATION), name("") + {} + OperationIDKey(eDepsOperation_Code opcode) : + opcode(opcode), name("") + {} + OperationIDKey(eDepsOperation_Code opcode, const string &name) : + opcode(opcode), name(name) + {} + + string identifier() const + { + char codebuf[5]; + sprintf(codebuf, "%d", opcode); + + return string("OperationIDKey(") + codebuf + ", " + name + ")"; + } + + bool operator==(const OperationIDKey &other) const + { + return (opcode == other.opcode) && (name == other.name); + } + }; + + /* XXX can't specialize std::hash for this purpose, because ComponentKey is a nested type ... + * http://stackoverflow.com/a/951245 + */ + struct operation_key_hash { + bool operator() (const OperationIDKey &key) const + { + return hash_combine(hash<int>()(key.opcode), hash<string>()(key.name)); + } + }; + + /* Typedef for container of operations */ + typedef unordered_map<OperationIDKey, OperationDepsNode *, operation_key_hash> OperationMap; + + + ComponentDepsNode(); + ~ComponentDepsNode(); + + void init(const ID *id, const string &subdata); + void copy(DepsgraphCopyContext *dcc, const ComponentDepsNode *src); + + string identifier() const; + + /* Find an existing operation, will throw an assert() if it does not exist. */ + OperationDepsNode *find_operation(OperationIDKey key) const; + OperationDepsNode *find_operation(eDepsOperation_Code opcode, const string &name) const; + + /* Check operation exists and return it. */ + OperationDepsNode *has_operation(OperationIDKey key) const; + OperationDepsNode *has_operation(eDepsOperation_Code opcode, const string &name) const; + + /** + * Create a new node for representing an operation and add this to graph + * \warning If an existing node is found, it will be modified. This helps when node may + * have been partially created earlier (e.g. parent ref before parent item is added) + * + * \param type: Operation node type (corresponding to context/component that it operates in) + * \param optype: Role that operation plays within component (i.e. where in eval process) + * \param op: The operation to perform + * \param name: Identifier for operation - used to find/locate it again + */ + OperationDepsNode *add_operation(eDepsOperation_Type optype, DepsEvalOperationCb op, eDepsOperation_Code opcode, const string &name); + + void remove_operation(eDepsOperation_Code opcode, const string &name); + void clear_operations(); + + void tag_update(Depsgraph *graph); + + /* Evaluation Context Management .................. */ + + /* Initialize component's evaluation context used for the specified purpose */ + virtual bool eval_context_init(EvaluationContext * /*eval_ctx*/) { return false; } + /* Free data in component's evaluation context which is used for the specified purpose + * NOTE: this does not free the actual context in question + */ + virtual void eval_context_free(EvaluationContext * /*eval_ctx*/) {} + + OperationDepsNode *get_entry_operation(); + OperationDepsNode *get_exit_operation(); + + IDDepsNode *owner; + + OperationMap operations; /* inner nodes for this component */ + OperationDepsNode *entry_operation; + OperationDepsNode *exit_operation; + + // XXX: a poll() callback to check if component's first node can be started? +}; + +/* ---------------------------------------- */ + +struct ParametersComponentDepsNode : public ComponentDepsNode { + DEG_DEPSNODE_DECLARE; +}; + +struct AnimationComponentDepsNode : public ComponentDepsNode { + DEG_DEPSNODE_DECLARE; +}; + +struct TransformComponentDepsNode : public ComponentDepsNode { + DEG_DEPSNODE_DECLARE; +}; + +struct ProxyComponentDepsNode : public ComponentDepsNode { + DEG_DEPSNODE_DECLARE; +}; + +struct GeometryComponentDepsNode : public ComponentDepsNode { + DEG_DEPSNODE_DECLARE; +}; + +struct SequencerComponentDepsNode : public ComponentDepsNode { + DEG_DEPSNODE_DECLARE; +}; + +struct PoseComponentDepsNode : public ComponentDepsNode { + DEG_DEPSNODE_DECLARE; +}; + +/* Bone Component */ +struct BoneComponentDepsNode : public ComponentDepsNode { + void init(const ID *id, const string &subdata); + + struct bPoseChannel *pchan; /* the bone that this component represents */ + + DEG_DEPSNODE_DECLARE; +}; + +struct ParticlesComponentDepsNode : public ComponentDepsNode { + DEG_DEPSNODE_DECLARE; +}; + +struct ShadingComponentDepsNode : public ComponentDepsNode { + DEG_DEPSNODE_DECLARE; +}; + + +void DEG_register_component_depsnodes(); + +#endif /* __DEPSNODE_COMPONENT_H__ */ diff --git a/source/blender/depsgraph/intern/depsnode_opcodes.h b/source/blender/depsgraph/intern/depsnode_opcodes.h new file mode 100644 index 00000000000..b81822c0ac5 --- /dev/null +++ b/source/blender/depsgraph/intern/depsnode_opcodes.h @@ -0,0 +1,145 @@ +/* + * ***** 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) 2014 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsnode_opcodes.h + * \ingroup depsgraph + * + * \par OpCodes for OperationDepsNodes + * + * This file defines all the "operation codes" (opcodes) used to identify + * common operation node types. The intention of these defines is to have + * a fast and reliable way of identifying the relevant nodes within a component + * without having to use fragile dynamic strings. + * + * This file is meant to be used like UI_icons.h. That is, before including + * the file, the host file must define the DEG_OPCODE(_label) macro, which + * is responsible for converting the define into whatever form is suitable. + * Therefore, it intentionally doesn't have header guards. + */ + + +/* Example macro define: */ +/* #define DEF_DEG_OPCODE(label) DEG_OPCODE_##label, */ + +/* Generic Operations ------------------------------ */ + +/* Placeholder for operations which don't need special mention */ +DEF_DEG_OPCODE(OPERATION) + +// XXX: Placeholder while porting depsgraph code +DEF_DEG_OPCODE(PLACEHOLDER) + +DEF_DEG_OPCODE(NOOP) + +/* Animation, Drivers, etc. ------------------------ */ + +/* NLA + Action */ +DEF_DEG_OPCODE(ANIMATION) + +/* Driver */ +DEF_DEG_OPCODE(DRIVER) + +/* Proxy Inherit? */ +//DEF_DEG_OPCODE(PROXY) + +/* Transform --------------------------------------- */ + +/* Transform entry point - local transforms only */ +DEF_DEG_OPCODE(TRANSFORM_LOCAL) + +/* Parenting */ +DEF_DEG_OPCODE(TRANSFORM_PARENT) + +/* Constraints */ +DEF_DEG_OPCODE(TRANSFORM_CONSTRAINTS) +//DEF_DEG_OPCODE(TRANSFORM_CONSTRAINTS_INIT) +//DEF_DEG_OPCODE(TRANSFORM_CONSTRAINT) +//DEF_DEG_OPCODE(TRANSFORM_CONSTRAINTS_DONE) + +/* Rigidbody Sim - Perform Sim */ +DEF_DEG_OPCODE(RIGIDBODY_REBUILD) +DEF_DEG_OPCODE(RIGIDBODY_SIM) + +/* Rigidbody Sim - Copy Results to Object */ +DEF_DEG_OPCODE(TRANSFORM_RIGIDBODY) + +/* Transform exitpoint */ +DEF_DEG_OPCODE(TRANSFORM_FINAL) + +/* XXX: ubereval is for temporary porting purposes only */ +DEF_DEG_OPCODE(OBJECT_UBEREVAL) + +/* Geometry ---------------------------------------- */ + +/* XXX: Placeholder - UberEval */ +DEF_DEG_OPCODE(GEOMETRY_UBEREVAL) + +/* Modifier */ +DEF_DEG_OPCODE(GEOMETRY_MODIFIER) + +/* Curve Objects - Path Calculation (used for path-following tools) */ +DEF_DEG_OPCODE(GEOMETRY_PATH) + +/* Pose -------------------------------------------- */ + +/* Init IK Trees, etc. */ +DEF_DEG_OPCODE(POSE_INIT) + +/* Free IK Trees + Compute Deform Matrices */ +DEF_DEG_OPCODE(POSE_DONE) + +/* IK/Spline Solvers */ +DEF_DEG_OPCODE(POSE_IK_SOLVER) +DEF_DEG_OPCODE(POSE_SPLINE_IK_SOLVER) + +/* Bone -------------------------------------------- */ + +/* Bone local transforms - Entrypoint */ +DEF_DEG_OPCODE(BONE_LOCAL) + +/* Pose-space conversion (includes parent + restpose) */ +DEF_DEG_OPCODE(BONE_POSE_PARENT) + +/* Constraints */ +DEF_DEG_OPCODE(BONE_CONSTRAINTS) +//DEF_DEG_OPCODE(BONE_CONSTRAINTS_INIT) +//DEF_DEG_OPCODE(BONE_CONSTRAINT) +//DEF_DEG_OPCODE(BONE_CONSTRAINTS_DONE) + +/* Bone transforms are ready + * - "READY" This (internal) noop is used to signal that all pre-IK operations are done. + * Its role is to help mediate situations where cyclic relations may otherwise form + * (i.e. one bone in chain targetting another in same chain) + * - "DONE" This noop is used to signal that the bone's final pose transform can be read by others + */ +// TODO: deform mats could get calculated in the final_transform ops... +DEF_DEG_OPCODE(BONE_READY) +DEF_DEG_OPCODE(BONE_DONE) + +/* Particles --------------------------------------- */ + +/* XXX: placeholder - Particle System eval */ +DEF_DEG_OPCODE(PSYS_EVAL) diff --git a/source/blender/depsgraph/intern/depsnode_operation.cc b/source/blender/depsgraph/intern/depsnode_operation.cc new file mode 100644 index 00000000000..6aeb163356b --- /dev/null +++ b/source/blender/depsgraph/intern/depsnode_operation.cc @@ -0,0 +1,104 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsnode_operation.cc + * \ingroup depsgraph + */ + +#include "MEM_guardedalloc.h" + +extern "C" { +#include "BLI_utildefines.h" +} /* extern "C" */ + +#include "depsnode_operation.h" /* own include */ +#include "depsnode_component.h" +#include "depsgraph.h" +#include "depsgraph_intern.h" + +/* ******************************************************************* */ +/* OpNode Identifiers Array - Exported to other depsgraph files too... */ + +/* identifiers for operations */ +const char *DEG_OPNAMES[] = { +#define DEF_DEG_OPCODE(label) #label, +#include "depsnode_opcodes.h" +#undef DEF_DEG_OPCODE + + "<Invalid>" +}; + +/* *********** */ +/* Inner Nodes */ + +OperationDepsNode::OperationDepsNode() : + eval_priority(0.0f), + flag(0) +{ +} + +OperationDepsNode::~OperationDepsNode() +{ +} + +string OperationDepsNode::identifier() const +{ + BLI_assert((opcode > 0) && (opcode < ARRAY_SIZE(DEG_OPNAMES))); + return string(DEG_OPNAMES[opcode]) + "(" + name + ")"; +} + +/* Full node identifier, including owner name. + * used for logging and debug prints. + */ +string OperationDepsNode::full_identifier() const +{ + string owner_str = ""; + if (owner->type == DEPSNODE_TYPE_BONE) { + owner_str = owner->owner->name + "." + owner->name; + } + else { + owner_str = owner->owner->name; + } + return owner_str + "." + identifier(); +} + +void OperationDepsNode::tag_update(Depsgraph *graph) +{ + if (flag & DEPSOP_FLAG_NEEDS_UPDATE) { + return; + } + /* Tag for update, but also note that this was the source of an update. */ + flag |= (DEPSOP_FLAG_NEEDS_UPDATE | DEPSOP_FLAG_DIRECTLY_MODIFIED); + graph->add_entry_tag(this); +} + +DEG_DEPSNODE_DEFINE(OperationDepsNode, DEPSNODE_TYPE_OPERATION, "Operation"); +static DepsNodeFactoryImpl<OperationDepsNode> DNTI_OPERATION; + +void DEG_register_operation_depsnodes() +{ + DEG_register_node_typeinfo(&DNTI_OPERATION); +} diff --git a/source/blender/depsgraph/intern/depsnode_operation.h b/source/blender/depsgraph/intern/depsnode_operation.h new file mode 100644 index 00000000000..1119e10805d --- /dev/null +++ b/source/blender/depsgraph/intern/depsnode_operation.h @@ -0,0 +1,90 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsnode_operation.h + * \ingroup depsgraph + */ + +#ifndef __DEPSNODE_OPERATION_H__ +#define __DEPSNODE_OPERATION_H__ + +#include "depsnode.h" + +struct ID; + +struct Depsgraph; +struct DepsgraphCopyContext; + +/* Flags for Depsgraph Nodes */ +typedef enum eDepsOperation_Flag { + /* node needs to be updated */ + DEPSOP_FLAG_NEEDS_UPDATE = (1 << 0), + + /* node was directly modified, causing need for update */ + /* XXX: intention is to make it easier to tell when we just need to take subgraphs */ + DEPSOP_FLAG_DIRECTLY_MODIFIED = (1 << 1), + + /* Operation is evaluated using CPython; has GIL and security implications... */ + DEPSOP_FLAG_USES_PYTHON = (1 << 2), +} eDepsOperation_Flag; + +/* Atomic Operation - Base type for all operations */ +struct OperationDepsNode : public DepsNode { + + + OperationDepsNode(); + ~OperationDepsNode(); + + string identifier() const; + string full_identifier() const; + + void tag_update(Depsgraph *graph); + + bool is_noop() const { return (bool)evaluate == false; } + + OperationDepsNode *get_entry_operation() { return this; } + OperationDepsNode *get_exit_operation() { return this; } + + ComponentDepsNode *owner; /* component that contains the operation */ + + DepsEvalOperationCb evaluate; /* callback for operation */ + + + uint32_t num_links_pending; /* how many inlinks are we still waiting on before we can be evaluated... */ + float eval_priority; + bool scheduled; + + short optype; /* (eDepsOperation_Type) stage of evaluation */ + int opcode; /* (eDepsOperation_Code) identifier for the operation being performed */ + + int flag; /* (eDepsOperation_Flag) extra settings affecting evaluation */ + + DEG_DEPSNODE_DECLARE; +}; + +void DEG_register_operation_depsnodes(); + +#endif /* __DEPSNODE_OPERATION_H__ */ |