diff options
author | Jacques Lucke <jacques@blender.org> | 2020-06-09 18:08:41 +0300 |
---|---|---|
committer | Jacques Lucke <jacques@blender.org> | 2020-06-09 18:08:41 +0300 |
commit | e1cc9aa7f2813004cad34a580e2faa1b7ca21db1 (patch) | |
tree | d73e31186b808c6290a6fc4ecc7bcf97844f7144 | |
parent | b37fca650eeaefc0980ffa10a56c80a5ee875c01 (diff) |
Nodes: efficient node tree queries and inlining
This adds two data structures that wrap a node tree. However, they work
on different abstraction levels.
`NodeTreeRef` is an immutable structure that makes working with a node
tree in C++ much more efficient and convenient. It supports various
queries efficiently, that are not easily possible using just `bNodeTree`.
`DerivedNodeTree` builds on top of `NodeTreeRef`. It contains a flattened
view on the node tree, i.e. with node groups being inlined. Every inlined
node still knows its "call stack". It supports pretty much the same queries
as `NodeTreeRef`.
Both data structures come with a dot graph exporter for debugging purposes.
Reviewers: brecht
Differential Revision: https://developer.blender.org/D7628
-rw-r--r-- | source/blender/blenkernel/BKE_derived_node_tree.hh | 453 | ||||
-rw-r--r-- | source/blender/blenkernel/BKE_node_tree_ref.hh | 448 | ||||
-rw-r--r-- | source/blender/blenkernel/CMakeLists.txt | 4 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/derived_node_tree.cc | 442 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/node_tree_ref.cc | 178 |
5 files changed, 1525 insertions, 0 deletions
diff --git a/source/blender/blenkernel/BKE_derived_node_tree.hh b/source/blender/blenkernel/BKE_derived_node_tree.hh new file mode 100644 index 00000000000..009d9b747f9 --- /dev/null +++ b/source/blender/blenkernel/BKE_derived_node_tree.hh @@ -0,0 +1,453 @@ +/* + * 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. + */ + +#ifndef __BKE_DERIVED_NODE_TREE_HH__ +#define __BKE_DERIVED_NODE_TREE_HH__ + +/** \file + * \ingroup bke + * + * DerivedNodeTree provides a flattened view on a bNodeTree, i.e. node groups are inlined. It + * builds on top of NodeTreeRef and supports similar queries efficiently. + * + * Every inlined node remembers its path to the parent ("call stack"). + * + * Unlinked group node inputs are handled separately from other sockets. + * + * There is a dot graph exporter for debugging purposes. + */ + +#include "BKE_node_tree_ref.hh" + +namespace BKE { + +class DSocket; +class DInputSocket; +class DOutputSocket; +class DNode; +class DParentNode; +class DGroupInput; +class DerivedNodeTree; + +class DSocket : blender::NonCopyable, blender::NonMovable { + protected: + DNode *m_node; + const SocketRef *m_socket_ref; + uint m_id; + + friend DerivedNodeTree; + + public: + const DNode &node() const; + + uint id() const; + uint index() const; + + bool is_input() const; + bool is_output() const; + + const DSocket &as_base() const; + const DInputSocket &as_input() const; + const DOutputSocket &as_output() const; + + PointerRNA *rna() const; + StringRefNull idname() const; + StringRefNull name() const; +}; + +class DInputSocket : public DSocket { + private: + Vector<DOutputSocket *> m_linked_sockets; + Vector<DGroupInput *> m_linked_group_inputs; + + friend DerivedNodeTree; + + public: + const InputSocketRef &socket_ref() const; + + Span<const DOutputSocket *> linked_sockets() const; + Span<const DGroupInput *> linked_group_inputs() const; + + bool is_linked() const; +}; + +class DOutputSocket : public DSocket { + private: + Vector<DInputSocket *> m_linked_sockets; + + friend DerivedNodeTree; + + public: + const OutputSocketRef &socket_ref() const; + Span<const DInputSocket *> linked_sockets() const; +}; + +class DGroupInput : blender::NonCopyable, blender::NonMovable { + private: + const InputSocketRef *m_socket_ref; + DParentNode *m_parent; + Vector<DInputSocket *> m_linked_sockets; + uint m_id; + + friend DerivedNodeTree; + + public: + const InputSocketRef &socket_ref() const; + const DParentNode *parent() const; + Span<const DInputSocket *> linked_sockets() const; + uint id() const; + StringRefNull name() const; +}; + +class DNode : blender::NonCopyable, blender::NonMovable { + private: + const NodeRef *m_node_ref; + DParentNode *m_parent; + + Span<DInputSocket *> m_inputs; + Span<DOutputSocket *> m_outputs; + + uint m_id; + + friend DerivedNodeTree; + + public: + const NodeRef &node_ref() const; + const DParentNode *parent() const; + + Span<const DInputSocket *> inputs() const; + Span<const DOutputSocket *> outputs() const; + + const DInputSocket &input(uint index) const; + const DOutputSocket &output(uint index) const; + + uint id() const; + + PointerRNA *rna() const; + StringRefNull idname() const; + StringRefNull name() const; + + private: + void destruct_with_sockets(); +}; + +class DParentNode : blender::NonCopyable, blender::NonMovable { + private: + const NodeRef *m_node_ref; + DParentNode *m_parent; + uint m_id; + + friend DerivedNodeTree; + + public: + const DParentNode *parent() const; + const NodeRef &node_ref() const; + uint id() const; +}; + +using NodeTreeRefMap = Map<bNodeTree *, std::unique_ptr<const NodeTreeRef>>; + +class DerivedNodeTree : blender::NonCopyable, blender::NonMovable { + private: + LinearAllocator<> m_allocator; + bNodeTree *m_btree; + Vector<DNode *> m_nodes_by_id; + Vector<DGroupInput *> m_group_inputs; + Vector<DParentNode *> m_parent_nodes; + + Vector<DSocket *> m_sockets_by_id; + Vector<DInputSocket *> m_input_sockets; + Vector<DOutputSocket *> m_output_sockets; + + Map<std::string, Vector<DNode *>> m_nodes_by_idname; + + public: + DerivedNodeTree(bNodeTree *btree, NodeTreeRefMap &node_tree_refs); + ~DerivedNodeTree(); + + Span<const DNode *> nodes() const; + Span<const DNode *> nodes_with_idname(StringRef idname) const; + + Span<const DSocket *> sockets() const; + Span<const DInputSocket *> input_sockets() const; + Span<const DOutputSocket *> output_sockets() const; + + std::string to_dot() const; + + private: + /* Utility functions used during construction. */ + void insert_nodes_and_links_in_id_order(const NodeTreeRef &tree_ref, + DParentNode *parent, + Vector<DNode *> &all_nodes); + DNode &create_node(const NodeRef &node_ref, + DParentNode *parent, + MutableSpan<DSocket *> r_sockets_map); + void expand_groups(Vector<DNode *> &all_nodes, + Vector<DGroupInput *> &all_group_inputs, + Vector<DParentNode *> &all_parent_nodes, + NodeTreeRefMap &node_tree_refs); + void expand_group_node(DNode &group_node, + Vector<DNode *> &all_nodes, + Vector<DGroupInput *> &all_group_inputs, + Vector<DParentNode *> &all_parent_nodes, + NodeTreeRefMap &node_tree_refs); + void create_group_inputs_for_unlinked_inputs(DNode &node, + Vector<DGroupInput *> &all_group_inputs); + void relink_group_inputs(const NodeTreeRef &group_ref, + Span<DNode *> nodes_by_id, + DNode &group_node); + void relink_group_outputs(const NodeTreeRef &group_ref, + Span<DNode *> nodes_by_id, + DNode &group_node); + void remove_expanded_group_interfaces(Vector<DNode *> &all_nodes); + void remove_unused_group_inputs(Vector<DGroupInput *> &all_group_inputs); + void store_in_this_and_init_ids(Vector<DNode *> &&all_nodes, + Vector<DGroupInput *> &&all_group_inputs, + Vector<DParentNode *> &&all_parent_nodes); +}; + +/* -------------------------------------------------------------------- + * DSocket inline methods. + */ + +inline const DNode &DSocket::node() const +{ + return *m_node; +} + +inline uint DSocket::id() const +{ + return m_id; +} + +inline uint DSocket::index() const +{ + return m_socket_ref->index(); +} + +inline bool DSocket::is_input() const +{ + return m_socket_ref->is_input(); +} + +inline bool DSocket::is_output() const +{ + return m_socket_ref->is_output(); +} + +inline const DSocket &DSocket::as_base() const +{ + return *this; +} + +inline const DInputSocket &DSocket::as_input() const +{ + return *(DInputSocket *)this; +} + +inline const DOutputSocket &DSocket::as_output() const +{ + return *(DOutputSocket *)this; +} + +inline PointerRNA *DSocket::rna() const +{ + return m_socket_ref->rna(); +} + +inline StringRefNull DSocket::idname() const +{ + return m_socket_ref->idname(); +} + +inline StringRefNull DSocket::name() const +{ + return m_socket_ref->name(); +} + +/* -------------------------------------------------------------------- + * DInputSocket inline methods. + */ + +inline const InputSocketRef &DInputSocket::socket_ref() const +{ + return m_socket_ref->as_input(); +} + +inline Span<const DOutputSocket *> DInputSocket::linked_sockets() const +{ + return m_linked_sockets.as_span(); +} + +inline Span<const DGroupInput *> DInputSocket::linked_group_inputs() const +{ + return m_linked_group_inputs.as_span(); +} + +inline bool DInputSocket::is_linked() const +{ + return m_linked_sockets.size() > 0 || m_linked_group_inputs.size() > 0; +} + +/* -------------------------------------------------------------------- + * DOutputSocket inline methods. + */ + +inline const OutputSocketRef &DOutputSocket::socket_ref() const +{ + return m_socket_ref->as_output(); +} + +inline Span<const DInputSocket *> DOutputSocket::linked_sockets() const +{ + return m_linked_sockets.as_span(); +} + +/* -------------------------------------------------------------------- + * DGroupInput inline methods. + */ + +inline const InputSocketRef &DGroupInput::socket_ref() const +{ + return *m_socket_ref; +} + +inline const DParentNode *DGroupInput::parent() const +{ + return m_parent; +} + +inline Span<const DInputSocket *> DGroupInput::linked_sockets() const +{ + return m_linked_sockets.as_span(); +} + +inline uint DGroupInput::id() const +{ + return m_id; +} + +inline StringRefNull DGroupInput::name() const +{ + return m_socket_ref->name(); +} + +/* -------------------------------------------------------------------- + * DNode inline methods. + */ + +inline const NodeRef &DNode::node_ref() const +{ + return *m_node_ref; +} + +inline const DParentNode *DNode::parent() const +{ + return m_parent; +} + +inline Span<const DInputSocket *> DNode::inputs() const +{ + return m_inputs; +} + +inline Span<const DOutputSocket *> DNode::outputs() const +{ + return m_outputs; +} + +inline const DInputSocket &DNode::input(uint index) const +{ + return *m_inputs[index]; +} + +inline const DOutputSocket &DNode::output(uint index) const +{ + return *m_outputs[index]; +} + +inline uint DNode::id() const +{ + return m_id; +} + +inline PointerRNA *DNode::rna() const +{ + return m_node_ref->rna(); +} + +inline StringRefNull DNode::idname() const +{ + return m_node_ref->idname(); +} + +inline StringRefNull DNode::name() const +{ + return m_node_ref->name(); +} + +/* -------------------------------------------------------------------- + * DParentNode inline methods. + */ + +inline const DParentNode *DParentNode::parent() const +{ + return m_parent; +} + +inline const NodeRef &DParentNode::node_ref() const +{ + return *m_node_ref; +} + +inline uint DParentNode::id() const +{ + return m_id; +} + +/* -------------------------------------------------------------------- + * DerivedNodeTree inline methods. + */ + +inline Span<const DNode *> DerivedNodeTree::nodes() const +{ + return m_nodes_by_id.as_span(); +} + +inline Span<const DNode *> DerivedNodeTree::nodes_with_idname(StringRef idname) const +{ + const Vector<DNode *> *nodes = m_nodes_by_idname.lookup_ptr(idname); + if (nodes == nullptr) { + return {}; + } + else { + return nodes->as_span(); + } +} + +inline Span<const DInputSocket *> DerivedNodeTree::input_sockets() const +{ + return m_input_sockets.as_span(); +} + +inline Span<const DOutputSocket *> DerivedNodeTree::output_sockets() const +{ + return m_output_sockets.as_span(); +} + +} // namespace BKE + +#endif /* __BKE_DERIVED_NODE_TREE_HH__ */ diff --git a/source/blender/blenkernel/BKE_node_tree_ref.hh b/source/blender/blenkernel/BKE_node_tree_ref.hh new file mode 100644 index 00000000000..043ef957af7 --- /dev/null +++ b/source/blender/blenkernel/BKE_node_tree_ref.hh @@ -0,0 +1,448 @@ +/* + * 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. + */ + +#ifndef __BKE_NODE_TREE_REF_HH__ +#define __BKE_NODE_TREE_REF_HH__ + +/** \file + * \ingroup bke + * + * NodeTreeRef makes querying information about a bNodeTree more efficient. It is an immutable data + * structure. It should not be used after anymore, after the underlying node tree changed. + * + * The following queries are supported efficiently: + * - socket -> index of socket + * - socket -> directly linked sockets + * - socket -> linked sockets when skipping reroutes + * - socket -> node + * - socket/node -> rna pointer + * - node -> inputs/outputs + * - node -> tree + * - tree -> all nodes + * - tree -> all (input/output) sockets + * - idname -> nodes + * + * Every socket has an id. The id-space is shared between input and output sockets. + * When storing data per socket, it is often better to use the id as index into an array, instead + * of a hash table. + * + * Every node has an id as well. The same rule regarding hash tables applies. + * + * There is an utility to export this data structure as graph in dot format. + */ + +#include "BLI_array.hh" +#include "BLI_linear_allocator.hh" +#include "BLI_map.hh" +#include "BLI_string_ref.hh" +#include "BLI_timeit.hh" +#include "BLI_utility_mixins.hh" +#include "BLI_vector.hh" + +#include "BKE_node.h" + +#include "DNA_node_types.h" + +#include "RNA_access.h" + +namespace BKE { + +using blender::Array; +using blender::IndexRange; +using blender::LinearAllocator; +using blender::Map; +using blender::MutableSpan; +using blender::Span; +using blender::StringRef; +using blender::StringRefNull; +using blender::Vector; + +class SocketRef; +class InputSocketRef; +class OutputSocketRef; +class NodeRef; +class NodeTreeRef; + +class SocketRef : blender::NonCopyable, blender::NonMovable { + protected: + NodeRef *m_node; + bNodeSocket *m_bsocket; + bool m_is_input; + uint m_id; + uint m_index; + PointerRNA m_rna; + Vector<SocketRef *> m_linked_sockets; + Vector<SocketRef *> m_directly_linked_sockets; + + friend NodeTreeRef; + + public: + Span<const SocketRef *> linked_sockets() const; + Span<const SocketRef *> directly_linked_sockets() const; + bool is_linked() const; + + const NodeRef &node() const; + const NodeTreeRef &tree() const; + + uint id() const; + uint index() const; + + bool is_input() const; + bool is_output() const; + + const SocketRef &as_base() const; + const InputSocketRef &as_input() const; + const OutputSocketRef &as_output() const; + + PointerRNA *rna() const; + + StringRefNull idname() const; + StringRefNull name() const; + + bNodeSocket *bsocket() const; + bNode *bnode() const; + bNodeTree *btree() const; +}; + +class InputSocketRef final : public SocketRef { + public: + Span<const OutputSocketRef *> linked_sockets() const; + Span<const OutputSocketRef *> directly_linked_sockets() const; +}; + +class OutputSocketRef final : public SocketRef { + public: + Span<const InputSocketRef *> linked_sockets() const; + Span<const InputSocketRef *> directly_linked_sockets() const; +}; + +class NodeRef : blender::NonCopyable, blender::NonMovable { + private: + NodeTreeRef *m_tree; + bNode *m_bnode; + PointerRNA m_rna; + uint m_id; + Vector<InputSocketRef *> m_inputs; + Vector<OutputSocketRef *> m_outputs; + + friend NodeTreeRef; + + public: + const NodeTreeRef &tree() const; + + Span<const InputSocketRef *> inputs() const; + Span<const OutputSocketRef *> outputs() const; + + const InputSocketRef &input(uint index) const; + const OutputSocketRef &output(uint index) const; + + bNode *bnode() const; + bNodeTree *btree() const; + + PointerRNA *rna() const; + StringRefNull idname() const; + StringRefNull name() const; + + uint id() const; + + bool is_reroute_node() const; + bool is_group_node() const; + bool is_group_input_node() const; + bool is_group_output_node() const; +}; + +class NodeTreeRef : blender::NonCopyable, blender::NonMovable { + private: + LinearAllocator<> m_allocator; + bNodeTree *m_btree; + Vector<NodeRef *> m_nodes_by_id; + Vector<SocketRef *> m_sockets_by_id; + Vector<InputSocketRef *> m_input_sockets; + Vector<OutputSocketRef *> m_output_sockets; + Map<std::string, Vector<NodeRef *>> m_nodes_by_idname; + + public: + NodeTreeRef(bNodeTree *btree); + ~NodeTreeRef(); + + Span<const NodeRef *> nodes() const; + Span<const NodeRef *> nodes_with_idname(StringRef idname) const; + + Span<const SocketRef *> sockets() const; + Span<const InputSocketRef *> input_sockets() const; + Span<const OutputSocketRef *> output_sockets() const; + + bNodeTree *btree() const; + + std::string to_dot() const; + + private: + /* Utility functions used during construction. */ + InputSocketRef &find_input_socket(Map<bNode *, NodeRef *> &node_mapping, + bNode *bnode, + bNodeSocket *bsocket); + OutputSocketRef &find_output_socket(Map<bNode *, NodeRef *> &node_mapping, + bNode *bnode, + bNodeSocket *bsocket); + void find_targets_skipping_reroutes(OutputSocketRef &socket_ref, Vector<SocketRef *> &r_targets); +}; + +/* -------------------------------------------------------------------- + * SocketRef inline methods. + */ + +inline Span<const SocketRef *> SocketRef::linked_sockets() const +{ + return m_linked_sockets.as_span(); +} + +inline Span<const SocketRef *> SocketRef::directly_linked_sockets() const +{ + return m_directly_linked_sockets.as_span(); +} + +inline bool SocketRef::is_linked() const +{ + return m_linked_sockets.size() > 0; +} + +inline const NodeRef &SocketRef::node() const +{ + return *m_node; +} + +inline const NodeTreeRef &SocketRef::tree() const +{ + return m_node->tree(); +} + +inline uint SocketRef::id() const +{ + return m_id; +} + +inline uint SocketRef::index() const +{ + return m_index; +} + +inline bool SocketRef::is_input() const +{ + return m_is_input; +} + +inline bool SocketRef::is_output() const +{ + return !m_is_input; +} + +inline const SocketRef &SocketRef::as_base() const +{ + return *this; +} + +inline const InputSocketRef &SocketRef::as_input() const +{ + BLI_assert(this->is_input()); + return *(const InputSocketRef *)this; +} + +inline const OutputSocketRef &SocketRef::as_output() const +{ + BLI_assert(this->is_output()); + return *(const OutputSocketRef *)this; +} + +inline PointerRNA *SocketRef::rna() const +{ + return const_cast<PointerRNA *>(&m_rna); +} + +inline StringRefNull SocketRef::idname() const +{ + return m_bsocket->idname; +} + +inline StringRefNull SocketRef::name() const +{ + return m_bsocket->name; +} + +inline bNodeSocket *SocketRef::bsocket() const +{ + return m_bsocket; +} + +inline bNode *SocketRef::bnode() const +{ + return m_node->bnode(); +} + +inline bNodeTree *SocketRef::btree() const +{ + return m_node->btree(); +} + +/* -------------------------------------------------------------------- + * InputSocketRef inline methods. + */ + +inline Span<const OutputSocketRef *> InputSocketRef::linked_sockets() const +{ + return m_linked_sockets.as_span().cast<const OutputSocketRef *>(); +} + +inline Span<const OutputSocketRef *> InputSocketRef::directly_linked_sockets() const +{ + return m_directly_linked_sockets.as_span().cast<const OutputSocketRef *>(); +} + +/* -------------------------------------------------------------------- + * OutputSocketRef inline methods. + */ + +inline Span<const InputSocketRef *> OutputSocketRef::linked_sockets() const +{ + return m_linked_sockets.as_span().cast<const InputSocketRef *>(); +} + +inline Span<const InputSocketRef *> OutputSocketRef::directly_linked_sockets() const +{ + return m_directly_linked_sockets.as_span().cast<const InputSocketRef *>(); +} + +/* -------------------------------------------------------------------- + * NodeRef inline methods. + */ + +inline const NodeTreeRef &NodeRef::tree() const +{ + return *m_tree; +} + +inline Span<const InputSocketRef *> NodeRef::inputs() const +{ + return m_inputs.as_span(); +} + +inline Span<const OutputSocketRef *> NodeRef::outputs() const +{ + return m_outputs.as_span(); +} + +inline const InputSocketRef &NodeRef::input(uint index) const +{ + return *m_inputs[index]; +} + +inline const OutputSocketRef &NodeRef::output(uint index) const +{ + return *m_outputs[index]; +} + +inline bNode *NodeRef::bnode() const +{ + return m_bnode; +} + +inline bNodeTree *NodeRef::btree() const +{ + return m_tree->btree(); +} + +inline PointerRNA *NodeRef::rna() const +{ + return const_cast<PointerRNA *>(&m_rna); +} + +inline StringRefNull NodeRef::idname() const +{ + return m_bnode->idname; +} + +inline StringRefNull NodeRef::name() const +{ + return m_bnode->name; +} + +inline uint NodeRef::id() const +{ + return m_id; +} + +inline bool NodeRef::is_reroute_node() const +{ + return m_bnode->type == NODE_REROUTE; +} + +inline bool NodeRef::is_group_node() const +{ + return m_bnode->type == NODE_GROUP; +} + +inline bool NodeRef::is_group_input_node() const +{ + return m_bnode->type == NODE_GROUP_INPUT; +} + +inline bool NodeRef::is_group_output_node() const +{ + return m_bnode->type == NODE_GROUP_OUTPUT; +} + +/* -------------------------------------------------------------------- + * NodeRef inline methods. + */ + +inline Span<const NodeRef *> NodeTreeRef::nodes() const +{ + return m_nodes_by_id.as_span(); +} + +inline Span<const NodeRef *> NodeTreeRef::nodes_with_idname(StringRef idname) const +{ + const Vector<NodeRef *> *nodes = m_nodes_by_idname.lookup_ptr(idname); + if (nodes == nullptr) { + return {}; + } + else { + return nodes->as_span(); + } +} + +inline Span<const SocketRef *> NodeTreeRef::sockets() const +{ + return m_sockets_by_id.as_span(); +} + +inline Span<const InputSocketRef *> NodeTreeRef::input_sockets() const +{ + return m_input_sockets.as_span(); +} + +inline Span<const OutputSocketRef *> NodeTreeRef::output_sockets() const +{ + return m_output_sockets.as_span(); +} + +inline bNodeTree *NodeTreeRef::btree() const +{ + return m_btree; +} + +} // namespace BKE + +#endif /* __BKE_NODE_TREE_REF_HH__ */ diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt index 817fe849eab..89712a1aed2 100644 --- a/source/blender/blenkernel/CMakeLists.txt +++ b/source/blender/blenkernel/CMakeLists.txt @@ -104,6 +104,7 @@ set(SRC intern/customdata_file.c intern/data_transfer.c intern/deform.c + intern/derived_node_tree.cc intern/displist.c intern/displist_tangent.c intern/dynamicpaint.c @@ -183,6 +184,7 @@ set(SRC intern/multires_unsubdivide.c intern/nla.c intern/node.c + intern/node_tree_ref.cc intern/object.c intern/object_deform.c intern/object_dupli.c @@ -291,6 +293,7 @@ set(SRC BKE_customdata_file.h BKE_data_transfer.h BKE_deform.h + BKE_derived_node_tree.hh BKE_displist.h BKE_displist_tangent.h BKE_duplilist.h @@ -349,6 +352,7 @@ set(SRC BKE_multires.h BKE_nla.h BKE_node.h + BKE_node_tree_ref.hh BKE_object.h BKE_object_deform.h BKE_object_facemap.h diff --git a/source/blender/blenkernel/intern/derived_node_tree.cc b/source/blender/blenkernel/intern/derived_node_tree.cc new file mode 100644 index 00000000000..80ae521642e --- /dev/null +++ b/source/blender/blenkernel/intern/derived_node_tree.cc @@ -0,0 +1,442 @@ +/* + * 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. + */ + +#include "BKE_derived_node_tree.hh" + +#include "BLI_dot_export.hh" + +#define UNINITIALIZED_ID UINT32_MAX + +namespace BKE { + +static const NodeTreeRef &get_tree_ref(NodeTreeRefMap &node_tree_refs, bNodeTree *btree) +{ + return *node_tree_refs.lookup_or_add(btree, + [&]() { return blender::make_unique<NodeTreeRef>(btree); }); +} + +DerivedNodeTree::DerivedNodeTree(bNodeTree *btree, NodeTreeRefMap &node_tree_refs) : m_btree(btree) +{ + const NodeTreeRef &main_tree_ref = get_tree_ref(node_tree_refs, btree); + + Vector<DNode *> all_nodes; + Vector<DGroupInput *> all_group_inputs; + Vector<DParentNode *> all_parent_nodes; + + this->insert_nodes_and_links_in_id_order(main_tree_ref, nullptr, all_nodes); + this->expand_groups(all_nodes, all_group_inputs, all_parent_nodes, node_tree_refs); + this->remove_expanded_group_interfaces(all_nodes); + this->remove_unused_group_inputs(all_group_inputs); + this->store_in_this_and_init_ids( + std::move(all_nodes), std::move(all_group_inputs), std::move(all_parent_nodes)); +} + +BLI_NOINLINE void DerivedNodeTree::insert_nodes_and_links_in_id_order(const NodeTreeRef &tree_ref, + DParentNode *parent, + Vector<DNode *> &all_nodes) +{ + Array<DSocket *, 64> sockets_map(tree_ref.sockets().size()); + + /* Insert nodes. */ + for (const NodeRef *node_ref : tree_ref.nodes()) { + DNode &node = this->create_node(*node_ref, parent, sockets_map); + all_nodes.append(&node); + } + + /* Insert links. */ + for (const NodeRef *node_ref : tree_ref.nodes()) { + for (const InputSocketRef *to_socket_ref : node_ref->inputs()) { + DInputSocket *to_socket = (DInputSocket *)sockets_map[to_socket_ref->id()]; + for (const OutputSocketRef *from_socket_ref : to_socket_ref->linked_sockets()) { + DOutputSocket *from_socket = (DOutputSocket *)sockets_map[from_socket_ref->id()]; + to_socket->m_linked_sockets.append(from_socket); + from_socket->m_linked_sockets.append(to_socket); + } + } + } +} + +DNode &DerivedNodeTree::create_node(const NodeRef &node_ref, + DParentNode *parent, + MutableSpan<DSocket *> r_sockets_map) +{ + DNode &node = *m_allocator.construct<DNode>(); + node.m_node_ref = &node_ref; + node.m_parent = parent; + node.m_id = UNINITIALIZED_ID; + + node.m_inputs = m_allocator.construct_elements_and_pointer_array<DInputSocket>( + node_ref.inputs().size()); + node.m_outputs = m_allocator.construct_elements_and_pointer_array<DOutputSocket>( + node_ref.outputs().size()); + + for (uint i : node.m_inputs.index_range()) { + const InputSocketRef &socket_ref = node_ref.input(i); + DInputSocket &socket = *node.m_inputs[i]; + + socket.m_id = UNINITIALIZED_ID; + socket.m_node = &node; + socket.m_socket_ref = &socket_ref; + + r_sockets_map[socket_ref.id()] = &socket; + } + + for (uint i : node.m_outputs.index_range()) { + const OutputSocketRef &socket_ref = node_ref.output(i); + DOutputSocket &socket = *node.m_outputs[i]; + + socket.m_id = UNINITIALIZED_ID; + socket.m_node = &node; + socket.m_socket_ref = &socket_ref; + + r_sockets_map[socket_ref.id()] = &socket; + } + + return node; +} + +BLI_NOINLINE void DerivedNodeTree::expand_groups(Vector<DNode *> &all_nodes, + Vector<DGroupInput *> &all_group_inputs, + Vector<DParentNode *> &all_parent_nodes, + NodeTreeRefMap &node_tree_refs) +{ + for (uint i = 0; i < all_nodes.size(); i++) { + DNode &node = *all_nodes[i]; + if (node.m_node_ref->is_group_node()) { + this->expand_group_node(node, all_nodes, all_group_inputs, all_parent_nodes, node_tree_refs); + } + } +} + +BLI_NOINLINE void DerivedNodeTree::expand_group_node(DNode &group_node, + Vector<DNode *> &all_nodes, + Vector<DGroupInput *> &all_group_inputs, + Vector<DParentNode *> &all_parent_nodes, + NodeTreeRefMap &node_tree_refs) +{ + const NodeRef &group_node_ref = *group_node.m_node_ref; + BLI_assert(group_node_ref.is_group_node()); + + bNodeTree *btree = (bNodeTree *)group_node_ref.bnode()->id; + if (btree == nullptr) { + return; + } + + const NodeTreeRef &group_ref = get_tree_ref(node_tree_refs, btree); + + DParentNode &parent = *m_allocator.construct<DParentNode>(); + parent.m_id = all_parent_nodes.append_and_get_index(&parent); + parent.m_parent = group_node.m_parent; + parent.m_node_ref = &group_node_ref; + + this->insert_nodes_and_links_in_id_order(group_ref, &parent, all_nodes); + Span<DNode *> new_nodes_by_id = all_nodes.as_span().take_back(group_ref.nodes().size()); + + this->create_group_inputs_for_unlinked_inputs(group_node, all_group_inputs); + this->relink_group_inputs(group_ref, new_nodes_by_id, group_node); + this->relink_group_outputs(group_ref, new_nodes_by_id, group_node); +} + +BLI_NOINLINE void DerivedNodeTree::create_group_inputs_for_unlinked_inputs( + DNode &node, Vector<DGroupInput *> &all_group_inputs) +{ + for (DInputSocket *input_socket : node.m_inputs) { + if (input_socket->is_linked()) { + continue; + } + + DGroupInput &group_input = *m_allocator.construct<DGroupInput>(); + group_input.m_id = UNINITIALIZED_ID; + group_input.m_socket_ref = &input_socket->socket_ref(); + group_input.m_parent = node.m_parent; + + group_input.m_linked_sockets.append(input_socket); + input_socket->m_linked_group_inputs.append(&group_input); + all_group_inputs.append(&group_input); + } +} + +BLI_NOINLINE void DerivedNodeTree::relink_group_inputs(const NodeTreeRef &group_ref, + Span<DNode *> nodes_by_id, + DNode &group_node) +{ + Span<const NodeRef *> node_refs = group_ref.nodes_with_idname("NodeGroupInput"); + if (node_refs.size() == 0) { + return; + } + /* TODO: Pick correct group input node if there are more than one. */ + const NodeRef &input_node_ref = *node_refs[0]; + DNode &input_node = *nodes_by_id[input_node_ref.id()]; + + uint input_amount = group_node.inputs().size(); + BLI_assert(input_amount == input_node_ref.outputs().size() - 1); + + for (uint input_index : IndexRange(input_amount)) { + DInputSocket *outside_group = group_node.m_inputs[input_index]; + DOutputSocket *inside_group = input_node.m_outputs[input_index]; + + for (DOutputSocket *outside_connected : outside_group->m_linked_sockets) { + outside_connected->m_linked_sockets.remove_first_occurrence_and_reorder(outside_group); + } + + for (DGroupInput *outside_connected : outside_group->m_linked_group_inputs) { + outside_connected->m_linked_sockets.remove_first_occurrence_and_reorder(outside_group); + } + + for (DInputSocket *inside_connected : inside_group->m_linked_sockets) { + inside_connected->m_linked_sockets.remove_first_occurrence_and_reorder(inside_group); + + for (DOutputSocket *outside_connected : outside_group->m_linked_sockets) { + inside_connected->m_linked_sockets.append(outside_connected); + outside_connected->m_linked_sockets.append(inside_connected); + } + + for (DGroupInput *outside_connected : outside_group->m_linked_group_inputs) { + inside_connected->m_linked_group_inputs.append(outside_connected); + outside_connected->m_linked_sockets.append(inside_connected); + } + } + + inside_group->m_linked_sockets.clear(); + outside_group->m_linked_sockets.clear(); + outside_group->m_linked_group_inputs.clear(); + } +} + +BLI_NOINLINE void DerivedNodeTree::relink_group_outputs(const NodeTreeRef &group_ref, + Span<DNode *> nodes_by_id, + DNode &group_node) +{ + Span<const NodeRef *> node_refs = group_ref.nodes_with_idname("NodeGroupOutput"); + if (node_refs.size() == 0) { + return; + } + /* TODO: Pick correct group output node if there are more than one. */ + const NodeRef &output_node_ref = *node_refs[0]; + DNode &output_node = *nodes_by_id[output_node_ref.id()]; + + uint output_amount = group_node.outputs().size(); + BLI_assert(output_amount == output_node_ref.inputs().size() - 1); + + for (uint output_index : IndexRange(output_amount)) { + DOutputSocket *outside_group = group_node.m_outputs[output_index]; + DInputSocket *inside_group = output_node.m_inputs[output_index]; + + for (DInputSocket *outside_connected : outside_group->m_linked_sockets) { + outside_connected->m_linked_sockets.remove_first_occurrence_and_reorder(outside_group); + } + + for (DOutputSocket *inside_connected : inside_group->m_linked_sockets) { + inside_connected->m_linked_sockets.remove_first_occurrence_and_reorder(inside_group); + + for (DInputSocket *outside_connected : outside_group->m_linked_sockets) { + inside_connected->m_linked_sockets.append(outside_connected); + outside_connected->m_linked_sockets.append(inside_connected); + } + } + + for (DGroupInput *inside_connected : inside_group->m_linked_group_inputs) { + inside_connected->m_linked_sockets.remove_first_occurrence_and_reorder(inside_group); + + for (DInputSocket *outside_connected : outside_group->m_linked_sockets) { + inside_connected->m_linked_sockets.append(outside_connected); + outside_connected->m_linked_group_inputs.append(inside_connected); + } + } + + outside_group->m_linked_sockets.clear(); + inside_group->m_linked_sockets.clear(); + } +} + +BLI_NOINLINE void DerivedNodeTree::remove_expanded_group_interfaces(Vector<DNode *> &all_nodes) +{ + int index = 0; + while (index < all_nodes.size()) { + DNode &node = *all_nodes[index]; + const NodeRef &node_ref = *node.m_node_ref; + if (node_ref.is_group_node() || + (node.m_parent != nullptr && + (node_ref.is_group_input_node() || node_ref.is_group_output_node()))) { + all_nodes.remove_and_reorder(index); + node.destruct_with_sockets(); + } + else { + index++; + } + } +} + +BLI_NOINLINE void DerivedNodeTree::remove_unused_group_inputs( + Vector<DGroupInput *> &all_group_inputs) +{ + int index = 0; + while (index < all_group_inputs.size()) { + DGroupInput &group_input = *all_group_inputs[index]; + if (group_input.m_linked_sockets.is_empty()) { + all_group_inputs.remove_and_reorder(index); + group_input.~DGroupInput(); + } + else { + index++; + } + } +} + +void DNode::destruct_with_sockets() +{ + for (DInputSocket *socket : m_inputs) { + socket->~DInputSocket(); + } + for (DOutputSocket *socket : m_outputs) { + socket->~DOutputSocket(); + } + this->~DNode(); +} + +BLI_NOINLINE void DerivedNodeTree::store_in_this_and_init_ids( + Vector<DNode *> &&all_nodes, + Vector<DGroupInput *> &&all_group_inputs, + Vector<DParentNode *> &&all_parent_nodes) +{ + m_nodes_by_id = std::move(all_nodes); + m_group_inputs = std::move(all_group_inputs); + m_parent_nodes = std::move(all_parent_nodes); + + for (uint node_index : m_nodes_by_id.index_range()) { + DNode *node = m_nodes_by_id[node_index]; + node->m_id = node_index; + + m_nodes_by_idname.lookup_or_add_default(node->idname()).append(node); + + for (DInputSocket *socket : node->m_inputs) { + socket->m_id = m_sockets_by_id.append_and_get_index(socket); + m_input_sockets.append(socket); + } + for (DOutputSocket *socket : node->m_outputs) { + socket->m_id = m_sockets_by_id.append_and_get_index(socket); + m_output_sockets.append(socket); + } + } + + for (uint i : m_group_inputs.index_range()) { + m_group_inputs[i]->m_id = i; + } +} + +DerivedNodeTree::~DerivedNodeTree() +{ + for (DInputSocket *socket : m_input_sockets) { + socket->~DInputSocket(); + } + for (DOutputSocket *socket : m_output_sockets) { + socket->~DOutputSocket(); + } + for (DNode *node : m_nodes_by_id) { + node->~DNode(); + } + for (DGroupInput *group_input : m_group_inputs) { + group_input->~DGroupInput(); + } + for (DParentNode *parent : m_parent_nodes) { + parent->~DParentNode(); + } +} + +namespace Dot = blender::DotExport; + +static Dot::Cluster *get_cluster_for_parent(Dot::DirectedGraph &graph, + Map<const DParentNode *, Dot::Cluster *> &clusters, + const DParentNode *parent) +{ + if (parent == nullptr) { + return nullptr; + } + return clusters.lookup_or_add(parent, [&]() { + Dot::Cluster *parent_cluster = get_cluster_for_parent(graph, clusters, parent->parent()); + bNodeTree *btree = (bNodeTree *)parent->node_ref().bnode()->id; + Dot::Cluster *new_cluster = &graph.new_cluster(parent->node_ref().name() + " / " + + StringRef(btree->id.name + 2)); + new_cluster->set_parent_cluster(parent_cluster); + return new_cluster; + }); +} + +std::string DerivedNodeTree::to_dot() const +{ + Dot::DirectedGraph digraph; + digraph.set_rankdir(Dot::Attr_rankdir::LeftToRight); + + Map<const DNode *, Dot::NodeWithSocketsRef> dot_nodes; + Map<const DGroupInput *, Dot::NodeWithSocketsRef> dot_group_inputs; + Map<const DParentNode *, Dot::Cluster *> dot_clusters; + + for (const DNode *node : m_nodes_by_id) { + Dot::Node &dot_node = digraph.new_node(""); + dot_node.set_background_color("white"); + + Vector<std::string> input_names; + for (const DInputSocket *socket : node->inputs()) { + input_names.append(socket->name()); + } + Vector<std::string> output_names; + for (const DOutputSocket *socket : node->outputs()) { + output_names.append(socket->name()); + } + + dot_nodes.add_new(node, + Dot::NodeWithSocketsRef(dot_node, node->name(), input_names, output_names)); + + Dot::Cluster *cluster = get_cluster_for_parent(digraph, dot_clusters, node->parent()); + dot_node.set_parent_cluster(cluster); + } + + for (const DGroupInput *group_input : m_group_inputs) { + Dot::Node &dot_node = digraph.new_node(""); + dot_node.set_background_color("white"); + + std::string group_input_name = group_input->name(); + dot_group_inputs.add_new( + group_input, Dot::NodeWithSocketsRef(dot_node, "Group Input", {}, {group_input_name})); + + Dot::Cluster *cluster = get_cluster_for_parent(digraph, dot_clusters, group_input->parent()); + dot_node.set_parent_cluster(cluster); + } + + for (const DNode *to_node : m_nodes_by_id) { + Dot::NodeWithSocketsRef &to_dot_node = dot_nodes.lookup(to_node); + + for (const DInputSocket *to_socket : to_node->inputs()) { + for (const DOutputSocket *from_socket : to_socket->linked_sockets()) { + const DNode *from_node = &from_socket->node(); + Dot::NodeWithSocketsRef &from_dot_node = dot_nodes.lookup(from_node); + + digraph.new_edge(from_dot_node.output(from_socket->index()), + to_dot_node.input(to_socket->index())); + } + for (const DGroupInput *group_input : to_socket->linked_group_inputs()) { + Dot::NodeWithSocketsRef &from_dot_node = dot_group_inputs.lookup(group_input); + + digraph.new_edge(from_dot_node.output(0), to_dot_node.input(to_socket->index())); + } + } + } + + digraph.set_random_cluster_bgcolors(); + return digraph.to_dot_string(); +} + +} // namespace BKE diff --git a/source/blender/blenkernel/intern/node_tree_ref.cc b/source/blender/blenkernel/intern/node_tree_ref.cc new file mode 100644 index 00000000000..517c1b85aff --- /dev/null +++ b/source/blender/blenkernel/intern/node_tree_ref.cc @@ -0,0 +1,178 @@ +/* + * 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. + */ + +#include "BKE_node_tree_ref.hh" + +#include "BLI_dot_export.hh" + +namespace BKE { + +NodeTreeRef::NodeTreeRef(bNodeTree *btree) : m_btree(btree) +{ + Map<bNode *, NodeRef *> node_mapping; + + LISTBASE_FOREACH (bNode *, bnode, &btree->nodes) { + NodeRef &node = *m_allocator.construct<NodeRef>(); + + node.m_tree = this; + node.m_bnode = bnode; + node.m_id = m_nodes_by_id.append_and_get_index(&node); + RNA_pointer_create(&btree->id, &RNA_Node, bnode, &node.m_rna); + + LISTBASE_FOREACH (bNodeSocket *, bsocket, &bnode->inputs) { + InputSocketRef &socket = *m_allocator.construct<InputSocketRef>(); + socket.m_node = &node; + socket.m_index = node.m_inputs.append_and_get_index(&socket); + socket.m_is_input = true; + socket.m_bsocket = bsocket; + socket.m_id = m_sockets_by_id.append_and_get_index(&socket); + RNA_pointer_create(&btree->id, &RNA_NodeSocket, bsocket, &socket.m_rna); + } + + LISTBASE_FOREACH (bNodeSocket *, bsocket, &bnode->outputs) { + OutputSocketRef &socket = *m_allocator.construct<OutputSocketRef>(); + socket.m_node = &node; + socket.m_index = node.m_outputs.append_and_get_index(&socket); + socket.m_is_input = false; + socket.m_bsocket = bsocket; + socket.m_id = m_sockets_by_id.append_and_get_index(&socket); + RNA_pointer_create(&btree->id, &RNA_NodeSocket, bsocket, &socket.m_rna); + } + + m_input_sockets.extend(node.m_inputs); + m_output_sockets.extend(node.m_outputs); + + node_mapping.add_new(bnode, &node); + } + + LISTBASE_FOREACH (bNodeLink *, blink, &btree->links) { + OutputSocketRef &from_socket = this->find_output_socket( + node_mapping, blink->fromnode, blink->fromsock); + InputSocketRef &to_socket = this->find_input_socket( + node_mapping, blink->tonode, blink->tosock); + + from_socket.m_directly_linked_sockets.append(&to_socket); + to_socket.m_directly_linked_sockets.append(&from_socket); + } + + for (OutputSocketRef *socket : m_output_sockets) { + if (!socket->m_node->is_reroute_node()) { + this->find_targets_skipping_reroutes(*socket, socket->m_linked_sockets); + for (SocketRef *target : socket->m_linked_sockets) { + target->m_linked_sockets.append(socket); + } + } + } + + for (NodeRef *node : m_nodes_by_id) { + m_nodes_by_idname.lookup_or_add_default(node->idname()).append(node); + } +} + +NodeTreeRef::~NodeTreeRef() +{ + for (NodeRef *node : m_nodes_by_id) { + node->~NodeRef(); + } + for (InputSocketRef *socket : m_input_sockets) { + socket->~InputSocketRef(); + } + for (OutputSocketRef *socket : m_output_sockets) { + socket->~OutputSocketRef(); + } +} + +InputSocketRef &NodeTreeRef::find_input_socket(Map<bNode *, NodeRef *> &node_mapping, + bNode *bnode, + bNodeSocket *bsocket) +{ + NodeRef *node = node_mapping.lookup(bnode); + for (SocketRef *socket : node->m_inputs) { + if (socket->m_bsocket == bsocket) { + return *(InputSocketRef *)socket; + } + } + BLI_assert(false); + return *node->m_inputs[0]; +} + +OutputSocketRef &NodeTreeRef::find_output_socket(Map<bNode *, NodeRef *> &node_mapping, + bNode *bnode, + bNodeSocket *bsocket) +{ + NodeRef *node = node_mapping.lookup(bnode); + for (SocketRef *socket : node->m_outputs) { + if (socket->m_bsocket == bsocket) { + return *(OutputSocketRef *)socket; + } + } + BLI_assert(false); + return *node->m_outputs[0]; +} + +void NodeTreeRef::find_targets_skipping_reroutes(OutputSocketRef &socket, + Vector<SocketRef *> &r_targets) +{ + for (SocketRef *direct_target : socket.m_directly_linked_sockets) { + if (direct_target->m_node->is_reroute_node()) { + this->find_targets_skipping_reroutes(*direct_target->m_node->m_outputs[0], r_targets); + } + else { + r_targets.append_non_duplicates(direct_target); + } + } +} + +std::string NodeTreeRef::to_dot() const +{ + namespace Dot = blender::DotExport; + + Dot::DirectedGraph digraph; + digraph.set_rankdir(Dot::Attr_rankdir::LeftToRight); + + Map<const NodeRef *, Dot::NodeWithSocketsRef> dot_nodes; + + for (const NodeRef *node : m_nodes_by_id) { + Dot::Node &dot_node = digraph.new_node(""); + dot_node.set_background_color("white"); + + Vector<std::string> input_names; + Vector<std::string> output_names; + for (const InputSocketRef *socket : node->inputs()) { + input_names.append(socket->name()); + } + for (const OutputSocketRef *socket : node->outputs()) { + output_names.append(socket->name()); + } + + dot_nodes.add_new(node, + Dot::NodeWithSocketsRef(dot_node, node->name(), input_names, output_names)); + } + + for (const OutputSocketRef *from_socket : m_output_sockets) { + for (const InputSocketRef *to_socket : from_socket->directly_linked_sockets()) { + Dot::NodeWithSocketsRef &from_dot_node = dot_nodes.lookup(&from_socket->node()); + Dot::NodeWithSocketsRef &to_dot_node = dot_nodes.lookup(&to_socket->node()); + + digraph.new_edge(from_dot_node.output(from_socket->index()), + to_dot_node.input(to_socket->index())); + } + } + + return digraph.to_dot_string(); +} + +} // namespace BKE |