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

Nodes: cache children of frame nodes 

This allows for optimizations because one does not have to iterate
over all nodes anymore to find all nodes within a frame.

Differential Revision: https://developer.blender.org/D16106
This commit is contained in:
Iliya Katueshenock 2022-11-18 11:20:13 +01:00 committed by Jacques Lucke
parent dec459e424
commit 6239e089cf
Notes: blender-bot 2023-02-14 08:49:53 +01:00 
Referenced by issue #100627, Regression: Nodes UI: Node Frame updating after draw causes artifacts
12 changed files with 113 additions and 48 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

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

@ -730,8 +730,8 @@ void nodeInternalRelink(struct bNodeTree *ntree, struct bNode *node);
void nodeToView(const struct bNode *node, float x, float y, float *rx, float *ry);
void nodeFromView(const struct bNode *node, float x, float y, float *rx, float *ry);
bool nodeAttachNodeCheck(const struct bNode *node, const struct bNode *parent);
void nodeAttachNode(struct bNode *node, struct bNode *parent);
void nodeDetachNode(struct bNode *node);
void nodeAttachNode(struct bNodeTree *ntree, struct bNode *node, struct bNode *parent);
void nodeDetachNode(struct bNodeTree *ntree, struct bNode *node);
void nodePositionRelative(struct bNode *from_node,
struct bNode *to_node,

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

@ -84,6 +84,7 @@ class bNodeTreeRuntime : NonCopyable, NonMovable {
bool has_available_link_cycle = false;
bool has_undefined_nodes_or_sockets = false;
bNode *group_output_node = nullptr;
Vector<bNode *> root_frames;
};
/**
@ -154,6 +155,7 @@ class bNodeRuntime : NonCopyable, NonMovable {
int index_in_tree = -1;
bool has_available_linked_inputs = false;
bool has_available_linked_outputs = false;
Vector<bNode *> direct_children_in_frame;
bNodeTree *owner_tree = nullptr;
};
@ -323,6 +325,12 @@ inline blender::Span<bNodeSocket *> bNodeTree::all_sockets()
return this->runtime->sockets;
}
inline blender::Span<bNode *> bNodeTree::root_frames() const
{
BLI_assert(blender::bke::node_tree_runtime::topology_cache_is_available(*this));
return this->runtime->root_frames;
}
/** \} */
/* -------------------------------------------------------------------- */
@ -439,6 +447,13 @@ inline blender::Span<const bNodeLink *> bNode::internal_links_span() const
return this->runtime->internal_links;
}
inline blender::Span<bNode *> bNode::direct_children_in_frame() const
{
BLI_assert(blender::bke::node_tree_runtime::topology_cache_is_available(*this));
BLI_assert(this->is_frame());
return this->runtime->direct_children_in_frame;
}
inline const blender::nodes::NodeDeclaration *bNode::declaration() const
{
return this->runtime->declaration;

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

@ -54,6 +54,8 @@ void BKE_ntree_update_tag_active_output_changed(struct bNodeTree *ntree);
void BKE_ntree_update_tag_missing_runtime_data(struct bNodeTree *ntree);
/** Used when the interface sockets/values have changed. */
void BKE_ntree_update_tag_interface(struct bNodeTree *ntree);
/** Used when change parent node. */
void BKE_ntree_update_tag_parent_change(struct bNodeTree *ntree, struct bNode *node);
/** Used when an id data block changed that might be used by nodes that need to be updated. */
void BKE_ntree_update_tag_id_changed(struct Main *bmain, struct ID *id);
/** Used when an image user is updated that is used by any part of the node tree. */

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

@ -2571,7 +2571,7 @@ bool nodeAttachNodeCheck(const bNode *node, const bNode *parent)
return false;
}
void nodeAttachNode(bNode *node, bNode *parent)
void nodeAttachNode(bNodeTree *ntree, bNode *node, bNode *parent)
{
BLI_assert(parent->type == NODE_FRAME);
BLI_assert(nodeAttachNodeCheck(parent, node) == false);
@ -2580,11 +2580,12 @@ void nodeAttachNode(bNode *node, bNode *parent)
nodeToView(node, 0.0f, 0.0f, &locx, &locy);
node->parent = parent;
BKE_ntree_update_tag_parent_change(ntree, node);
/* transform to parent space */
nodeFromView(parent, locx, locy, &node->locx, &node->locy);
}
void nodeDetachNode(struct bNode *node)
void nodeDetachNode(bNodeTree *ntree, bNode *node)
{
if (node->parent) {
BLI_assert(node->parent->type == NODE_FRAME);
@ -2595,6 +2596,7 @@ void nodeDetachNode(struct bNode *node)
node->locx = locx;
node->locy = locy;
node->parent = nullptr;
BKE_ntree_update_tag_parent_change(ntree, node);
}
}
@ -2935,7 +2937,7 @@ static void node_unlink_attached(bNodeTree *ntree, bNode *parent)
{
LISTBASE_FOREACH (bNode *, node, &ntree->nodes) {
if (node->parent == parent) {
nodeDetachNode(node);
nodeDetachNode(ntree, node);
}
}
}

66
source/blender/blenkernel/intern/node_runtime.cc
View File

@ -372,6 +372,36 @@ static void update_toposort(const bNodeTree &ntree,
BLI_assert(tree_runtime.nodes.size() == r_sorted_nodes.size());
}
static void update_root_frames(const bNodeTree &ntree)
{
bNodeTreeRuntime &tree_runtime = *ntree.runtime;
Span<bNode *> nodes = tree_runtime.nodes;
tree_runtime.root_frames.clear();
for (bNode *node : nodes) {
if (!node->parent && node->is_frame()) {
tree_runtime.root_frames.append(node);
}
}
}
static void update_direct_frames_childrens(const bNodeTree &ntree)
{
bNodeTreeRuntime &tree_runtime = *ntree.runtime;
Span<bNode *> nodes = tree_runtime.nodes;
for (bNode *node : nodes) {
node->runtime->direct_children_in_frame.clear();
}
for (bNode *node : nodes) {
if (const bNode *frame = node->parent) {
frame->runtime->direct_children_in_frame.append(node);
}
}
}
static void update_group_output_node(const bNodeTree &ntree)
{
bNodeTreeRuntime &tree_runtime = *ntree.runtime;
@ -403,22 +433,26 @@ static void ensure_topology_cache(const bNodeTree &ntree)
update_socket_vectors_and_owner_node(ntree);
update_internal_links(ntree);
update_directly_linked_links_and_sockets(ntree);
threading::parallel_invoke([&]() { update_logical_origins(ntree); },
[&]() { update_nodes_by_type(ntree); },
[&]() { update_sockets_by_identifier(ntree); },
[&]() {
update_toposort(ntree,
ToposortDirection::LeftToRight,
tree_runtime.toposort_left_to_right,
tree_runtime.has_available_link_cycle);
},
[&]() {
bool dummy;
update_toposort(ntree,
ToposortDirection::RightToLeft,
tree_runtime.toposort_right_to_left,
dummy);
});
threading::parallel_invoke(
tree_runtime.nodes.size() > 32,
[&]() { update_logical_origins(ntree); },
[&]() { update_nodes_by_type(ntree); },
[&]() { update_sockets_by_identifier(ntree); },
[&]() {
update_toposort(ntree,
ToposortDirection::LeftToRight,
tree_runtime.toposort_left_to_right,
tree_runtime.has_available_link_cycle);
},
[&]() {
bool dummy;
update_toposort(ntree,
ToposortDirection::RightToLeft,
tree_runtime.toposort_right_to_left,
dummy);
},
[&]() { update_root_frames(ntree); },
[&]() { update_direct_frames_childrens(ntree); });
update_group_output_node(ntree);
tree_runtime.topology_cache_exists = true;
});

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

@ -44,6 +44,7 @@ enum eNodeTreeChangedFlag {
NTREE_CHANGED_REMOVED_SOCKET = (1 << 7),
NTREE_CHANGED_SOCKET_PROPERTY = (1 << 8),
NTREE_CHANGED_INTERNAL_LINK = (1 << 9),
NTREE_CHANGED_PARENT = (1 << 10),
NTREE_CHANGED_ALL = -1,
};
@ -1704,6 +1705,11 @@ void BKE_ntree_update_tag_interface(bNodeTree *ntree)
add_tree_tag(ntree, NTREE_CHANGED_INTERFACE);
}
void BKE_ntree_update_tag_parent_change(bNodeTree *ntree, bNode *node)
{
add_node_tag(ntree, node, NTREE_CHANGED_PARENT);
}
void BKE_ntree_update_tag_id_changed(Main *bmain, ID *id)
{
FOREACH_NODETREE_BEGIN (bmain, ntree, ntree_id) {

2
source/blender/editors/space_node/node_add.cc
View File

@ -205,7 +205,7 @@ static int add_reroute_exec(bContext *C, wmOperator *op)
for (const int i : frame_nodes.index_range()) {
bNode *frame_node = frame_nodes.last(i);
if (BLI_rctf_isect_pt_v(&frame_node->totr, insert_point)) {
nodeAttachNode(reroute, frame_node);
nodeAttachNode(&ntree, reroute, frame_node);
break;
}
}

12
source/blender/editors/space_node/node_edit.cc
View File

@ -1319,7 +1319,7 @@ bool node_link_is_hidden_or_dimmed(const View2D &v2d, const bNodeLink &link)
/** \name Node Duplicate Operator
* \{ */
static void node_duplicate_reparent_recursive(const Map<const bNode *, bNode *> &node_map,
static void node_duplicate_reparent_recursive(bNodeTree *ntree, const Map<const bNode *, bNode *> &node_map,
bNode *node)
{
bNode *parent;
@ -1330,15 +1330,15 @@ static void node_duplicate_reparent_recursive(const Map<const bNode *, bNode *>
for (parent = node->parent; parent; parent = parent->parent) {
if (parent->flag & SELECT) {
if (!(parent->flag & NODE_TEST)) {
node_duplicate_reparent_recursive(node_map, parent);
node_duplicate_reparent_recursive(ntree, node_map, parent);
}
break;
}
}
/* reparent node copy to parent copy */
if (parent) {
nodeDetachNode(node_map.lookup(node));
nodeAttachNode(node_map.lookup(node), node_map.lookup(parent));
nodeDetachNode(ntree, node_map.lookup(node));
nodeAttachNode(ntree, node_map.lookup(node), node_map.lookup(parent));
}
}
@ -1432,7 +1432,7 @@ static int node_duplicate_exec(bContext *C, wmOperator *op)
/* reparent copied nodes */
LISTBASE_FOREACH (bNode *, node, &ntree->nodes) {
if ((node->flag & SELECT) && !(node->flag & NODE_TEST)) {
node_duplicate_reparent_recursive(node_map, node);
node_duplicate_reparent_recursive(ntree, node_map, node);
}
/* only has to check old nodes */
@ -2269,7 +2269,7 @@ static int node_clipboard_copy_exec(bContext *C, wmOperator * /*op*/)
new_node->parent = node_map.lookup(new_node->parent);
}
else {
nodeDetachNode(new_node);
nodeDetachNode(ntree, new_node);
}
}
}

6
source/blender/editors/space_node/node_group.cc
View File

@ -488,7 +488,7 @@ static bool node_group_separate_selected(
/* ensure valid parent pointers, detach if parent stays inside the group */
if (newnode->parent && !(newnode->parent->flag & NODE_SELECT)) {
nodeDetachNode(newnode);
nodeDetachNode(&ngroup, newnode);
}
/* migrate node */
@ -842,7 +842,7 @@ static void node_group_make_insert_selected(const bContext &C, bNodeTree &ntree,
}
if (node_group_make_use_node(*node->parent, gnode) &&
!node_group_make_use_node(*node, gnode)) {
nodeDetachNode(node);
nodeDetachNode(&ntree, node);
}
}
@ -865,7 +865,7 @@ static void node_group_make_insert_selected(const bContext &C, bNodeTree &ntree,
/* ensure valid parent pointers, detach if parent stays outside the group */
if (node->parent && !(node->parent->flag & NODE_SELECT)) {
nodeDetachNode(node);
nodeDetachNode(&ntree, node);
}
/* change node-collection membership */

31
source/blender/editors/space_node/node_relationships.cc
View File

@ -1601,8 +1601,8 @@ static int node_parent_set_exec(bContext *C, wmOperator * /*op*/)
continue;
}
if (node->flag & NODE_SELECT) {
nodeDetachNode(node);
nodeAttachNode(node, frame);
nodeDetachNode(&ntree, node);
nodeAttachNode(&ntree, node, frame);
}
}
@ -1637,7 +1637,8 @@ void NODE_OT_parent_set(wmOperatorType *ot)
#define NODE_JOIN_DONE 1
#define NODE_JOIN_IS_DESCENDANT 2
static void node_join_attach_recursive(bNode *node,
static void node_join_attach_recursive(bNodeTree &ntree,
bNode *node,
bNode *frame,
const Set<bNode *> &selected_nodes)
{
@ -1649,7 +1650,7 @@ static void node_join_attach_recursive(bNode *node,
else if (node->parent) {
/* call recursively */
if (!(node->parent->done & NODE_JOIN_DONE)) {
node_join_attach_recursive(node->parent, frame, selected_nodes);
node_join_attach_recursive(ntree, node->parent, frame, selected_nodes);
}
/* in any case: if the parent is a descendant, so is the child */
@ -1658,13 +1659,13 @@ static void node_join_attach_recursive(bNode *node,
}
else if (selected_nodes.contains(node)) {
/* if parent is not an descendant of the frame, reattach the node */
nodeDetachNode(node);
nodeAttachNode(node, frame);
nodeDetachNode(&ntree, node);
nodeAttachNode(&ntree, node, frame);
node->done |= NODE_JOIN_IS_DESCENDANT;
}
}
else if (selected_nodes.contains(node)) {
nodeAttachNode(node, frame);
nodeAttachNode(&ntree, node, frame);
node->done |= NODE_JOIN_IS_DESCENDANT;
}
}
@ -1687,7 +1688,7 @@ static int node_join_exec(bContext *C, wmOperator * /*op*/)
LISTBASE_FOREACH (bNode *, node, &ntree.nodes) {
if (!(node->done & NODE_JOIN_DONE)) {
node_join_attach_recursive(node, frame_node, selected_nodes);
node_join_attach_recursive(ntree, node, frame_node, selected_nodes);
}
}
@ -1760,7 +1761,7 @@ static int node_attach_invoke(bContext *C, wmOperator * /*op*/, const wmEvent *e
/* disallow moving a parent into its child */
if (nodeAttachNodeCheck(frame, node) == false) {
/* attach all unparented nodes */
nodeAttachNode(node, frame);
nodeAttachNode(&ntree, node, frame);
}
}
else {
@ -1775,8 +1776,8 @@ static int node_attach_invoke(bContext *C, wmOperator * /*op*/, const wmEvent *e
if (parent) {
/* disallow moving a parent into its child */
if (nodeAttachNodeCheck(frame, node) == false) {
nodeDetachNode(node);
nodeAttachNode(node, frame);
nodeDetachNode(&ntree, node);
nodeAttachNode(&ntree, node, frame);
}
}
}
@ -1814,14 +1815,14 @@ void NODE_OT_attach(wmOperatorType *ot)
#define NODE_DETACH_DONE 1
#define NODE_DETACH_IS_DESCENDANT 2
static void node_detach_recursive(bNode *node)
static void node_detach_recursive(bNodeTree &ntree, bNode *node)
{
node->done |= NODE_DETACH_DONE;
if (node->parent) {
/* call recursively */
if (!(node->parent->done & NODE_DETACH_DONE)) {
node_detach_recursive(node->parent);
node_detach_recursive(ntree, node->parent);
}
/* in any case: if the parent is a descendant, so is the child */
@ -1830,7 +1831,7 @@ static void node_detach_recursive(bNode *node)
}
else if (node->flag & NODE_SELECT) {
/* if parent is not a descendant of a selected node, detach */
nodeDetachNode(node);
nodeDetachNode(&ntree, node);
node->done |= NODE_DETACH_IS_DESCENDANT;
}
}
@ -1854,7 +1855,7 @@ static int node_detach_exec(bContext *C, wmOperator * /*op*/)
*/
LISTBASE_FOREACH (bNode *, node, &ntree.nodes) {
if (!(node->done & NODE_DETACH_DONE)) {
node_detach_recursive(node);
node_detach_recursive(ntree, node);
}
}

4
source/blender/makesdna/DNA_node_types.h
View File

@ -407,6 +407,8 @@ typedef struct bNode {
/** Lookup socket of this node by its identifier. */
const bNodeSocket &input_by_identifier(blender::StringRef identifier) const;
const bNodeSocket &output_by_identifier(blender::StringRef identifier) const;
/** If node is frame, will return all children nodes. */
blender::Span<bNode *> direct_children_in_frame() const;
/** Node tree this node belongs to. */
const bNodeTree &owner_tree() const;
#endif
@ -650,6 +652,8 @@ typedef struct bNodeTree {
/** Efficient lookup of all nodes with a specific type. */
blender::Span<bNode *> nodes_by_type(blender::StringRefNull type_idname);
blender::Span<const bNode *> nodes_by_type(blender::StringRefNull type_idname) const;
/** Frame nodes without any parents. */
blender::Span<bNode *> root_frames() const;
/**
* Cached toposort of all nodes. If there are cycles, the returned array is not actually a
* toposort. However, if a connected component does not contain a cycle, this component is sorted

5
source/blender/makesrna/intern/rna_nodetree.c
View File

@ -2333,6 +2333,7 @@ static void rna_Node_parent_set(PointerRNA *ptr,
{
bNode *node = ptr->data;
bNode *parent = value.data;
bNodeTree *ntree = (bNodeTree *)ptr->owner_id;
if (parent) {
/* XXX only Frame node allowed for now,
@ -2348,9 +2349,9 @@ static void rna_Node_parent_set(PointerRNA *ptr,
}
}
nodeDetachNode(node);
nodeDetachNode(ntree, node);
if (parent) {
nodeAttachNode(node, parent);
nodeAttachNode(ntree, node, parent);
}
}