blender
/
blender
136
406
Fork 590
Code Issues 6.2k Pull Requests 764 Projects 19 Wiki Activity

Nodes: Remove "level" building pass on update 

The node level was an indication of how deep the node was in the tree.
It was only used for detecting link cycles. Now that the node topology
cache from 25e307d725 exists, this calculation can be removed
completely.

The level calculation was quadratic and very slow on larger node trees.
In the mouse house file with a few thousand nodes, it took 23ms on
every single update. Another benefit is storing slightly less runtime
data, though this was only 2 bytes per node.

Differential Revision: https://developer.blender.org/D16566
This commit is contained in:
Hans Goudey 2022-11-21 11:34:22 -06:00
parent b391037424
commit be1745425c
4 changed files with 19 additions and 72 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

2
source/blender/blenkernel/BKE_node.h
View File

@ -512,8 +512,6 @@ bool ntreeHasTree(const struct bNodeTree *ntree, const struct bNodeTree *lookup)
void ntreeUpdateAllNew(struct Main *main);
void ntreeUpdateAllUsers(struct Main *main, struct ID *id);
void ntreeUpdateNodeLevels(struct bNodeTree *ntree);
/**
* XXX: old trees handle output flags automatically based on special output
* node types and last active selection.

3
source/blender/blenkernel/BKE_node_runtime.hh
View File

@ -146,9 +146,8 @@ class bNodeRuntime : NonCopyable, NonMovable {
/** #eNodeTreeChangedFlag. */
uint32_t changed_flag = 0;
/** Both for dependency and sorting. */
/** For dependency and sorting. */
short done = 0;
short level = 0;
/** Used as a boolean for execution. */
uint8_t need_exec = 0;

56
source/blender/blenkernel/intern/node.cc
View File

@ -4078,62 +4078,6 @@ void BKE_node_instance_hash_remove_untagged(bNodeInstanceHash *hash,
MEM_freeN(untagged);
}
/* ************** dependency stuff *********** */
/* node is guaranteed to be not checked before */
static int node_get_deplist_recurs(bNodeTree *ntree, bNode *node, bNode ***nsort)
{
int level = 0xFFF;
node->runtime->done = true;
/* check linked nodes */
LISTBASE_FOREACH (bNodeLink *, link, &ntree->links) {
if (link->tonode == node) {
bNode *fromnode = link->fromnode;
if (fromnode->runtime->done == 0) {
fromnode->runtime->level = node_get_deplist_recurs(ntree, fromnode, nsort);
}
if (fromnode->runtime->level <= level) {
level = fromnode->runtime->level - 1;
}
}
}
/* check parent node */
if (node->parent) {
if (node->parent->runtime->done == 0) {
node->parent->runtime->level = node_get_deplist_recurs(ntree, node->parent, nsort);
}
if (node->parent->runtime->level <= level) {
level = node->parent->runtime->level - 1;
}
}
if (nsort) {
**nsort = node;
(*nsort)++;
}
return level;
}
/* only updates node->level for detecting cycles links */
void ntreeUpdateNodeLevels(bNodeTree *ntree)
{
/* first clear tag */
LISTBASE_FOREACH (bNode *, node, &ntree->nodes) {
node->runtime->done = false;
}
/* recursive check */
LISTBASE_FOREACH (bNode *, node, &ntree->nodes) {
if (node->runtime->done == 0) {
node->runtime->level = node_get_deplist_recurs(ntree, node, nullptr);
}
}
}
void ntreeUpdateAllNew(Main *main)
{
Vector<bNodeTree *> new_ntrees;

30
source/blender/blenkernel/intern/node_tree_update.cc
View File

@ -998,7 +998,6 @@ class NodeTreeMainUpdater {
result.output_changed = this->check_if_output_changed(ntree);
this->update_socket_link_and_use(ntree);
this->update_node_levels(ntree);
this->update_link_validation(ntree);
if (ntree.type == NTREE_TEXTURE) {
@ -1269,25 +1268,32 @@ class NodeTreeMainUpdater {
}
}
void update_node_levels(bNodeTree &ntree)
{
ntreeUpdateNodeLevels(&ntree);
}
void update_link_validation(bNodeTree &ntree)
{
const Span<const bNode *> toposort = ntree.toposort_left_to_right();
/* Build an array of toposort indices to allow retrieving the "depth" for each node. */
Array<int> toposort_indices(toposort.size());
for (const int i : toposort.index_range()) {
const bNode &node = *toposort[i];
toposort_indices[node.runtime->index_in_tree] = i;
}
LISTBASE_FOREACH (bNodeLink *, link, &ntree.links) {
link->flag |= NODE_LINK_VALID;
if (link->fromnode && link->tonode &&
link->fromnode->runtime->level <= link->tonode->runtime->level) {
const bNode &from_node = *link->fromnode;
const bNode &to_node = *link->tonode;
if (toposort_indices[from_node.runtime->index_in_tree] >
toposort_indices[to_node.runtime->index_in_tree]) {
link->flag &= ~NODE_LINK_VALID;
continue;
}
else if (ntree.typeinfo->validate_link) {
const eNodeSocketDatatype from_type = static_cast<eNodeSocketDatatype>(
link->fromsock->type);
const eNodeSocketDatatype to_type = static_cast<eNodeSocketDatatype>(link->tosock->type);
if (ntree.typeinfo->validate_link) {
const eNodeSocketDatatype from_type = eNodeSocketDatatype(link->fromsock->type);
const eNodeSocketDatatype to_type = eNodeSocketDatatype(link->tosock->type);
if (!ntree.typeinfo->validate_link(from_type, to_type)) {
link->flag &= ~NODE_LINK_VALID;
continue;
}
}
}