Differential D6905 Diff 21948 source/blender/depsgraph/intern/builder/deg_builder_relations.cc

Changeset View

Standalone View

source/blender/depsgraph/intern/builder/deg_builder_relations.cc

Show All 18 Lines

/** \file		/** \file
* \ingroup depsgraph		* \ingroup depsgraph
*		*
* Methods for constructing depsgraph		* Methods for constructing depsgraph
*/		*/

#include "intern/builder/deg_builder_relations.h"		#include "intern/builder/deg_builder_relations.h"
		#include "intern/builder/deg_builder_cycle.h"

#include <stdio.h>		#include <stdio.h>
#include <stdlib.h>		#include <stdlib.h>
#include <cstring> /* required for STREQ later on. */		#include <cstring> /* required for STREQ later on. */
		#include <deque>
		#include <unordered_set>

#include "MEM_guardedalloc.h"		#include "MEM_guardedalloc.h"

		#include "PIL_time_utildefines.h"

#include "BLI_utildefines.h"		#include "BLI_utildefines.h"
#include "BLI_blenlib.h"		#include "BLI_blenlib.h"

extern "C" {		extern "C" {
#include "DNA_action_types.h"		#include "DNA_action_types.h"
#include "DNA_anim_types.h"		#include "DNA_anim_types.h"
#include "DNA_armature_types.h"		#include "DNA_armature_types.h"
#include "DNA_camera_types.h"		#include "DNA_camera_types.h"
▲ Show 20 Lines • Show All 72 Lines • ▼ Show 20 Lines
#include "intern/node/deg_node_operation.h"		#include "intern/node/deg_node_operation.h"
#include "intern/node/deg_node_time.h"		#include "intern/node/deg_node_time.h"

#include "intern/depsgraph_relation.h"		#include "intern/depsgraph_relation.h"
#include "intern/depsgraph_type.h"		#include "intern/depsgraph_type.h"

namespace DEG {		namespace DEG {

		using std::deque;
		using std::unordered_set;

/* ***************** */		/* ***************** */
/* Relations Builder */		/* Relations Builder */

namespace {		namespace {

bool driver_target_depends_on_time(const DriverTarget *target)		bool driver_target_depends_on_time(const DriverTarget *target)
{		{
if (target->idtype == ID_SCE &&		if (target->idtype == ID_SCE &&
▲ Show 20 Lines • Show All 1,195 Lines • ▼ Show 20 Lines	LISTBASE_FOREACH (FCurve *, fcu, &adt->drivers) {
OperationKey driver_key(id,		OperationKey driver_key(id,
NodeType::PARAMETERS,		NodeType::PARAMETERS,
OperationCode::DRIVER,		OperationCode::DRIVER,
fcu->rna_path ? fcu->rna_path : "",		fcu->rna_path ? fcu->rna_path : "",
fcu->array_index);		fcu->array_index);

/* create the driver's relations to targets */		/* create the driver's relations to targets */
build_driver(id, fcu);		build_driver(id, fcu);
/* Special case for array drivers: we can not multithread them because
* of the way how they work internally: animation system will write the
* whole array back to RNA even when changing individual array value.
*
* Some tricky things here:
* - array_index is -1 for single channel drivers, meaning we only have
* to do some magic when array_index is not -1.
* - We do relation from next array index to a previous one, so we don't
* have to deal with array index 0.
*
* TODO(sergey): Avoid liner lookup somehow. */
if (fcu->array_index > 0) {
FCurve *fcu_prev = nullptr;
LISTBASE_FOREACH (FCurve *, fcu_candidate, &adt->drivers) {
/* Writing to different RNA paths is */
const char *rna_path = fcu->rna_path ? fcu->rna_path : "";
if (!STREQ(fcu_candidate->rna_path, rna_path)) {
continue;
}
/* We only do relation from previous fcurve to previous one. */
if (fcu_candidate->array_index >= fcu->array_index) {
continue;
}
/* Choose fcurve with highest possible array index. */
if (fcu_prev == nullptr \|\| fcu_candidate->array_index > fcu_prev->array_index) {
fcu_prev = fcu_candidate;
}
}
if (fcu_prev != nullptr) {
OperationKey prev_driver_key(id,
NodeType::PARAMETERS,
OperationCode::DRIVER,
fcu_prev->rna_path ? fcu_prev->rna_path : "",
fcu_prev->array_index);
OperationKey driver_key(id,
NodeType::PARAMETERS,
OperationCode::DRIVER,
fcu->rna_path ? fcu->rna_path : "",
fcu->array_index);
add_relation(prev_driver_key, driver_key, "Driver Order");
}
}

/* prevent driver from occurring before own animation... */		/* prevent driver from occurring before own animation... */
if (adt->action \|\| adt->nla_tracks.first) {		if (adt->action \|\| adt->nla_tracks.first) {
add_relation(adt_key, driver_key, "AnimData Before Drivers");		add_relation(adt_key, driver_key, "AnimData Before Drivers");
}		}
}		}
}		}

▲ Show 20 Lines • Show All 1,322 Lines • ▼ Show 20 Lines	if (animation_data->action != nullptr) {
copy_on_write_key,		copy_on_write_key,
"Eval Order",		"Eval Order",
RELATION_FLAG_GODMODE \| RELATION_FLAG_NO_FLUSH);		RELATION_FLAG_GODMODE \| RELATION_FLAG_NO_FLUSH);
}		}
}		}
#endif		#endif
}		}

		static bool is_reachable(Node const from, Node const to)
		{
		if (from == to) {
		return true;
		}

		// Perform a graph walk by shifting 'to' towards its incoming connections.
		sergeyUnsubmitted Done Inline Actions shifting -> waling is more commonly used terminology i would think. sergey: shifting -> waling is more commonly used terminology i would think.
		// Shifting 'from' towards its outgoing connections is 10x slower on the Spring rig.
		deque<Node *> queue;
		unordered_set<Node *> seen;
		queue.push_back(to);
		while (!queue.empty()) {
		// Visit the next node to inspect.
		Node *visit = queue.back();
		queue.pop_back();

		if (visit == from) {
		return true;
		}

		// Queue all incoming relations that we haven't seen before.
		for (Relation *relation : visit->inlinks) {
		Node *prev_node = relation->from;

		if (seen.insert(prev_node).second) {
		queue.push_back(prev_node);
		}
		}
		}
		return false;
		}

		void DepsgraphRelationBuilder::build_driver_relations()
		{
		TIMEIT_START(build_driver_relations);
		sergeyUnsubmitted Done Inline Actions Ignore in release. OR! Respect `--debug-depsgraph-time`. sergey: Ignore in release. OR! Respect `--debug-depsgraph-time`.
		for (IDNode *id_node : graph_->id_nodes) {
		build_driver_relations(id_node);
		}
		TIMEIT_END(build_driver_relations);
		}

		void DepsgraphRelationBuilder::build_driver_relations(IDNode *id_node)
		{
		/* Add relations between drivers that write to the same datablock.
		*
		* This prevents threading issues when two separate RNA properties write to
		* the same memory address. For example:
		* - Drivers on individual array elements, as the animation system will write
		* the whole array back to RNA even when changing individual array value.
		* - Drivers on RNA properties that map to a single bit flag. Changing the RNA
		* value will write the entire int containing the bit, in a non-thread-safe
		* way.
		*/
		ID *id_orig = id_node->id_orig;
		AnimData *adt = BKE_animdata_from_id(id_orig);
		if (adt == nullptr) {
		return;
		}

		// Mapping from RNA prefix -> set of driver evaluation nodes:
		typedef vector<Node *> DriverGroup;
		typedef map<string, DriverGroup> DriverGroupMap;
		DriverGroupMap driver_groups;

		LISTBASE_FOREACH (FCurve *, fcu, &adt->drivers) {
		// Get the RNA path except the part after the last dot.
		char *last_dot = strrchr(fcu->rna_path, '.');
		string rna_prefix("");
		sergeyUnsubmitted Done Inline Actions No need to explicitly initialize to empty string. sergey: No need to explicitly initialize to empty string.
		if (last_dot != nullptr) {
		rna_prefix = string(fcu->rna_path, last_dot);
		}

		// Insert this driver node into the group belonging to the RNA prefix.
		OperationKey driver_key(
		id_orig, NodeType::PARAMETERS, OperationCode::DRIVER, fcu->rna_path, fcu->array_index);
		Node *node_driver = get_node(driver_key);
		driver_groups[rna_prefix].push_back(node_driver);
		}

		for (pair<string, DriverGroup> prefix_group : driver_groups) {
		// For each node in the driver group, try to connect it to another node
		sergeyUnsubmitted Done Inline Actions Make it obvious that nodes are connected within the same group. sergey: Make it obvious that nodes are connected within the same group.
		// without creating any cycles.
		int num_drivers = prefix_group.second.size();
		for (int from_index = 0; from_index < num_drivers; ++from_index) {
		Node *op_from = prefix_group.second[from_index];

		// Start by trying the next node in the group.
		for (int to_offset = 1; to_offset < num_drivers - 1; ++to_offset) {
		int to_index = (from_index + to_offset) % num_drivers;
		Node *op_to = prefix_group.second[to_index];

		// If to->from is already reachable, adding from->to would create a cycle.
		sergeyUnsubmitted Done Inline Actions How about making a little pseudo-graphic 3 nodes (A -> B -> C) example to visualize exactly? sergey: How about making a little pseudo-graphic 3 nodes (A -> B -> C) example to visualize exactly?
		if (is_reachable(op_to, op_from)) {
		continue;
		}

		// No need to connect this node if it is already depending on one of the other nodes in
		// this group.
		if (is_reachable(op_from, op_to)) {
		break;
		}

		add_operation_relation(
		op_from->get_exit_operation(), op_to->get_entry_operation(), "Driver Serialisation");
		break;
		}
		}
		}
		}

/* ** ID traversal callbacks functions ** */		/* ** ID traversal callbacks functions ** */

void DepsgraphRelationBuilder::modifier_walk(void *user_data,		void DepsgraphRelationBuilder::modifier_walk(void *user_data,
struct Object * /object/,		struct Object * /object/,
struct ID **idpoin,		struct ID **idpoin,
int /cb_flag/)		int /cb_flag/)
{		{
BuilderWalkUserData data = (BuilderWalkUserData )user_data;		BuilderWalkUserData data = (BuilderWalkUserData )user_data;
Show All 21 Lines