利用者:Lucarood/Modifier Nodes/Proposal

Modifier Nodes

This is a proposal for modifier nodes. A simple proof of concept implementation has been done, but the concepts discussed here are still in development, thus some things are prone to change. The proposed system will be discussed here both from a user perspective as well as from a technical implementation perspective.

User Side

• Only mesh data is manipulated by the node tree.
• Any mesh can be input into a node tree, by means of a "mesh input" node.
• Object data (coordinates and such) can be input into the tree, but objects themselves are not passed through the tree, and object data is never altered by the tree.
• Modifiers will have no notion of world/local space, as they no longer act on single objects, but can now manipulate meshes from multiple objects at once.
• Meshes can be converted into world/local space, by means of a "convert space" node, giving the user full control over the space in which modifiers act.
• A modifier node tree is not exclusive to one object, thus the same tree can be used by many objects.
• An object can hold a reference to a node tree, which makes that node tree be applied for that object. (when a node tree is being evaluated for an object we'll call that object the "evaluated object")
• Mesh input nodes actually refer to an object, giving them awareness of space, and allowing the user to input the mesh in either local or world space.
• If no object is specified in the mesh input node, the evaluated object is input (dynamic mesh), giving the ability to dynamically manipulate the mesh from any object using that tree, rather than an explicitly specified mesh (explicit mesh).
• Every node that outputs a mesh, also has a "mesh id" output socket. This can be used to later refer to this mesh, even after it has been altered by other nodes.
• A "mesh join" node allows multiple meshes to be processed as a single mesh further down the node tree (compound mesh). Note that all the mesh ids are preserved.
• A "mesh split" node takes a mesh and a mesh id input, and allows the mesh with the given id to be extracted from a compound mesh, even after being manipulated by deformation modifiers and other nodes.
• The meshes input into nodes with temporal caching (physics and such), can never be a mixture of explicit and dynamic meshes joined together, but can only come from either explicit or dynamic inputs at a time.
• The mesh that is output from the node tree is determined by a "mesh output" node.
• The output node can have sockets for multiple data types, such as mesh, points (particles), voxels (volumetrics), etc. (alternatively separate output nodes can exist for this purpose)

Here you can see two mesh inputs being used, where the topmost one has the object field left empty, so that it will input the mesh from currently evaluated object (i.e. whatever object is using this tree). The other mesh input specifies the object, and thus will input the mesh from it, regardless of what object is being evaluated.

Here, both the sphere and the cone objects are using the same tree. In the resulting meshes, it can be observed how the tree is dynamically using the meshes from each object being evaluated, as well as the explicitly specified object (torus).

Implementation

There are two possibilities for the tree evaluation. One where the whole tree is a single node in the depsgraph, in which case changing any data that the tree or part of the tree depends on will invalidate the whole tree, and call for a re-evaluation. In this case, the node system will have its own evaluation scheme, and will be limited to a single thread (somewhat similar to the current modifier stack). The other possibility, arrived at after discussion with Sergey, is to register each node in the tree as an individual node in the depsgraph as well (perhaps in a subgraph), allowing the depsgraph itself to handle the tree evaluation. This has the advantage of allowing selective invalidation of the tree, depending on the data that changed. And this also allows the node system to take advantage of the scheduling and multi-threading already implemented in the depsgraph.

This document considers the first option, and discusses an evaluation scheme for the node tree, independent of the depsgraph. This is due to the increased complexity of a depsgraph based implementation. This is also the system that was used in the proof of concept implementation. This is likely fine to get the system going initially, without having to make too many changes to other parts of Blender, but for a more optimal implementation, the depsgraph should handle the evaluation. Some of the concepts discussed here would still be relevant in that case.

The most straight forward way to linearly evaluate the node tree, is to do depth first backwards traversal, starting with the output node, and calling the nodes connected to the inputs of the node being evaluated. Callback functions exist for each output socket, and are called by the following nodes connected to them in the tree.

Data

There are two main classes of data passed through the tree:

• Global evaluation data. This is passed backwards along the tree, as an argument in all the socket callback executions.
• Node results. This is passed forwards as the return from the socket callback functions, and contains the data actually computed by the node.

Node result data can exist in multiple forms, depending of the type of socket. The most important type being the mesh type, returned by nearly all modifiers. Mesh sockets return a mesh wrapper, which consists of a struct containing the modifier's resulting mesh and some additional meta-data necessary for the evaluation of the subsequent nodes. The main meta-data contained in the mesh wrapper, is a set of two hashtables that contain offsets and lengths of mesh data within a compound mesh. Whenever two meshes are joined in the node tree, keys are added to the hashtables, pointing to the offsets and lengths of the data from the original meshes within the new joined mesh. One of the hashtables contains all the offsets of sub-meshes contained within a compound mesh, and its keys are the addresses of the sockets from which the meshes were returned. The other hashtable contains only offsets of meshes that can be traced back to actual mesh data-blocks on objects, and its keys are the addresses of these original mesh data-blocks, which means that this second hashtable lacks meshes that passed through generative modifiers. Every time a mesh passes through a deformation modifier, or a mesh join/split node, all the existing keys in the hashtables are preserved, and another key referring to the entire mesh is added to the socket-keyed hashtable. When going through a generative modifier, all the previous keys are lost, and only the key of the current socket is added.

Mesh wrapper:

• Compound mesh.
• Mesh offset table (socket keys).
• Mesh offset table (mesh keys).
• flags (discussed below).

Global evaluation data has the main function of being used as a container for the "best" deformation-only mesh (more on that later). But it also serves to pass some data to the nodes, such as the object currently being evaluated, and the apply flag, which tells modifiers which type of mesh they should compute (render/preview and such).

Global evaluation data:

• Deformation mesh (double pointer to a mesh wrapper).
• Call depth (used for determining the "best" deformation mesh, clarified below).
• Evaluation object.
• Call depth.

Deformation mesh determination

The deformation-only mesh is used in places where the original mesh is wanted, but with deformed coordinates, such as vertex paint. This is easy to achieve with a linear system such as the current modifier stack, but it becomes more tricky once you introduce a non-linear workflow such as a node system, because then multiple branches can deform the mesh in different ways. In this situation, a heuristic is necessary to determine which mesh state to use. Here, what is used, is the closest mesh to the output node, which has not passed through generative modifiers. Or rather, the mesh with the lowest call depth, when walking the tree backwards from the output node.

The deformation mesh is replaced in the global data, if the current node has lower call depth than currently present in the global data, and the address of the mesh from the evaluation object can be found in the hashtable of the current node state (meaning it hasn't passed thought any generative modifiers, and the original mesh can still be extracted from the current mesh). When the mesh is replaced in the global data, the current call depth is of course also updated. Also, an "is_deformation" flag is set on the new mesh wrapper being set as deformation mesh, while that flag is cleared on the previously set deformation mesh wrapper, if any (will come in handy later).

Tree evaluation-time caching

This cache is only for use during the tree evaluation, and is always freed after the whole tree was evaluated. A mesh computed by an output socket callback function will be cached in the socket, if the socket has more than one link connected to it, meaning the output is used in multiple other places. If a single link is connected to the socket, there is no use for caching, as that state will not be retrieved again later. When the socket has multiple connected links, the state will be retrieved again later, and caching will prevent the need to recompute it. In that situation, the resulting mesh is stored in the socket, and a copy of it is returned. Also, an "is_cached" flag is set on the cached mesh.

Mesh Wrapper freeing

The mesh wrapper freeing function will free the mesh it contains, if any. It will also free all the offset hashtables and the offset structs they contain. Note, however, that while both hashtables are freed, only the data in the socket-keyed table should be freed, as the mesh-keyed table will always contain only a subset of the data in the other table, thus this data will already be freed. Also, the freeing function will not free anything if any of the "is_cached" or "is_deformation" flags are set, as that indicates that this mesh wrapper is still in use somewhere else.

Tree evaluation

This is an overview of the call sequence for the tree evaluation. In actuality it is slightly more nuanced, but this is the general gist.

• Evaluation starts on the output node.
• The callback function of the mesh output socket connected to the input of the output node is called.
• It is checked if the socket has a cached result. And if so, a copy of the cached mesh wrapper is returned, and this socket evaluation is finished. (the reason for copying is explained later).
• If no cache is found, evaluation continues:
• Each of these callback functions will then subsequently execute the callbacks of the sockets connected to the current node which are needed to compute the current output.
• Now that all the necessary inputs have been collected, the node operation itself if executed (i.e. the modifier). Note that the modifier is executed directly on the mesh(es) passed to the node inputs.
• If this is a deformation-only modifier, then it is just a matter of adding a new entry in the socket-keyed hashtable, and following operations can occur on the same mesh wrapper.
• If a generative node is being evaluated, that means a new mesh was created by the modifier execution, then:
  • A new mesh wrapper is created, and the current socket is added as an entry to the hashtable.
  • The mesh wrapper(s) input to this node are of no further use, so the freeing function is called for these meshes (this is safe, because in the event of any of these meshes being set as global deformation mesh, it will not be freed).
• Now it is checked if the mesh of the evaluation object is a key within the mesh-keyed hashtable of the newly computed mesh wrapper.
  • If that is the case, this mesh is applicable as deformation mesh, so it is verified if the current call depth is smaller than the global call depth.
  • If that is also the case, we can set this as the global deformation mesh, so the "is_deformation" flag is unset in the current global mesh wrapper, and set in the new mesh wrapper.
  • Now the free function is called for the old global deformation mesh wrapper (this is safe, because in the event of this mesh being cached, it will not be freed).
  • Lastly, the new mesh wrapper is set in the global data, and the global call depth is updated.
• The number of links connected to the current output socket is checked.
  • If only one link is connected to the socket, the current mesh wrapper is returned as is, and this socket evaluation is finished.
  • If multiple links are connected to the socket, this mesh will be needed by other nodes later.
    • The "is_cached" flag is set in the new mesh wrapper, and the mesh wrapper is stored in the socket cache.
    • A copy of the mesh wrapper is returned, instead of the original mesh wrapper. This is to avoid conflicts, as generally, the different nodes making use of this mesh will modify it in different ways.
• After all nodes have been evaluated, the final mesh wrapper will have been returned by the output socket callback connected to the output node, which was called in the beginning.
• Now the tree evaluation has to be finished, and intermediate data cleaned:
  • The mesh is taken from the final mesh wrapper, to later be returned by the tree evaluation function.
  • The final mesh wrapper's mesh is set to NULL, and the mesh wrapper is freed (this way we keep the mesh itself).
  • It is checked if any mesh wrapper was set in the global deformation.
    • If so, the relevant portion of the mesh is extracted, by means of the offsets stored in the mesh hashtable (necessary as the mesh might contain more than the data we need, if meshes were joined).
    • Then the "is_deformation" flag is unset, and the free function is called for the deformation mesh wrapper (this mesh wrapper might still be cached, in which case it will not be freed).
    • If no global deformation mesh wrapper is found, the undeformed original mesh from the object is used instead.
  • Most of the intermediate data (mesh wrappers) was freed during the evaluation of the nodes/sockets, however, cached mesh wrappers are still in memory.
    • The intermediate data is no longer needed, as the final result was achieved, so we iterate over all the sockets in the tree, check if they have cached data, unset the "is_cached" flag for the mesh wrappers, and call the freeing function for this data.
• At this point, the final mesh and deformation mesh have been computed and set in the return arguments, and all the intermediate data has been cleaned, so the node tree evaluation function can exit.

Final notes on temporal caching

For modifiers that depend on data computed on previous frames (i.e. physics), this data should have a dedicated caching system. This is a completely different matter than the tree evaluation-time caching discussed above. The actual caching system for this, is beyond the scope of this document, and deserves a full proposal itself. However, a quick observation about storing this cache is relevant. Cached simulations should be stored at node tree level whenever all the meshes input to the simulation are explicit meshes (i.e. come from mesh input nodes with explicitly defined objects), because the simulation will be the same, regardless of what object is using the node tree. On the other hand, when dynamic meshes are input (i.e. the object field is blank on the mesh input node), the caches should be stored on the currently evaluated object, as the simulation will be different for each object using the node tree. This is also why it is not possible to mix explicit and dynamic meshes with the same function (simulation or collision meshes and such) for simulations.