Closed fire closed 3 years ago
Excellent job on this proposal.
Very good proposal!
Amazing writeup! Sorry to comment without adding more information but I had to ask: Is this being worked on right now? If there's a fork I could try out with the suggested changes I'd love to at least contribute by testing them!
Amazing writeup! Sorry to comment without adding more information but I had to ask: Is this being worked on right now? If there's a fork I could try out with the suggested changes I'd love to at least contribute by testing them!
@setzer22 Thanks! I'm the author of this proposal. I had made it for GSOC 2020, but didn't get selected. Anyways, I'll start implementing it soon. I'll make a PR and mention it here, so that you guys can see it anytime :) And if you're interested, you can contribute to it once I open the PR.
Thanks! I'm the author of this proposal. I had made it for GSOC 2020, but didn't get selected. Anyways, I'll start implementing it soon. I'll make a PR and mention it here, so that you guys can see it anytime :)
@theoway were you able to work on this proposal? I am planning to take this up for my GSOC application. I would really love to see some improvements on the VS.
@theoway were you able to work on this proposal? I am planning to take this up for my GSOC application. I would really love to see some improvements on the VS.
@rishabhabhani As a matter of fact, Yes. I'm extending my previous proposal, that is this one, with some improvements as discussed by the members. See, I've been already working on this for quite some time. There are other issues that you can apply for.
@theoway Ah, that's great to hear you're still on it. I just didn't see any updates here so I was wondering. Anyways, All the best with this proposal.
https://github.com/godotengine/godot/pull/49343 PR for the proposal. I'll be adding visuals and examples so that you guys can be see the progress.
Removing "archived" since this was implemented in https://github.com/godotengine/godot/pull/49343
Describe the project you are working on:
Multiplayer 3d game.
Describe the problem or limitation you are having in your project:
Visual Shader graphs in Godot can become extremely messy and there's even a bug that scrambles the graph randomly.
Describe the feature / enhancement and how it helps to overcome the problem or limitation:
Looking for collaborators.
Co-Authored with theoway#7853
The proposal aims to organize the node's position in graph edit, visual shader editor and visual script editor.
This proposal is inspired by Sugiyama's methodology, which is very popular and commonly used in software to draw directed graphs automatically. The method has been modified to fit the needs of the users, keeping in mind the design architecture and implementation of the graph editing system in Godot Engine.
This feature will find its use in Visual Script Editor and Visual Shader Editor. Users can use this feature to auto-arrange the node positions, in a horizontal-block layout. This will help the users save time from rearranging the nodes while editing to get clarity and better organization, especially when the visual scripts and visual shaders have a large number of nodes.
https://www.youtube.com/watch?v=LY3E5VGnAuQ
https://www.youtube.com/watch?v=plafUnYKhu4
Describe how your proposal will work, with code, pseudocode, mockups, and/or diagrams:
Design Abstract
The idea is to add functionality to the graph edit system that will automatically rearrange the nodes, dividing them into layers and blocks, making them comprehensive and easy to read. This functionality can be used in Visual Script Editor and Visual Shader Editor (as they also use graph edit system) to automatically reorganize the nodes. The feature will also handle the cases when the grid is turned on/off or when its scaling is changed.
Preliminaries
The references below are made according to the graph edit, visual script and visual shaders of Godot.
Methodology
This methodology consists of three phases
The node layout in graph edit is a Directed Acyclic Graph (DAG) with the nodes being the vertices and the sequence, data connections being the edges. The auto-arrangement procedure only works for layered graphs. That's why the DAG obtained from the graph edit system(or visual script/visual shaders) is converted into a layered graph by following the Layering and Ordering and Cross-Minimisation methods.
Once we have a layered graph with a minimum number of edge crossings, we then place the vertices(nodes of the visual script) in horizontal blocks. Edges between the blocks will be drawn straight. To achieve this, Preprocessing, Horizontal Alignment and Inner Shift methods will be used.
In the final phase, the blocks are moved as close as possible, while keeping the edges straight inside the blocks, and assigning explicit y coordinates to the nodes. The method used for this phase is Place Block With Straightening.
The various techniques mentioned in the methodology are explained below
In this process, the graph will be divided into non-empty layers. Layering is done in such a way that an edge will always point from the node of the upper layer to the lower layer node. There will be no edges (connections) between nodes of the same layers. The direction of edges is orthogonal to the layers. To do this, the Longest Path Layering algorithm will be used.
Result: This will result in the layering of the graph. Each vertex will be assigned a layer.
2) Ordering and Cross-Minimisation:
This process involves ordering vertices in each layer so that a minimum number of edge crossings occur. This is achieved by going layer by layer and trying to minimize the inner-crossings between adjacent layers. Inner-crossings is the crossing of two inner edges(edges that have starting points and ending points at the two adjacent layers) between adjacent layers.
3) Preprocessing:
This method resolves the crossing on non-inner segments and inner-segments(Inner-segments are the edges between two adjacent layers). It also marks the non-inner segments to favour the horizontal alignment of edges inside the blocks.
Result: Non-inner segments are marked so that they can be avoided during block formation.
The left image shows a layered graph. The right image shows the same layered graph with inner crossings and non-inner segments removed. Note:- See Preliminaries point 5.
4) Horizontal Alignment: After the preprocessing is done, the nodes are placed inside blocks in a bottommost alignment with their median, upper neighbours. (upper neighbour means the nodes that lie to the left because we are considering horizontal alignment)
Now the vertices with similar roots are placed in the same blocks.Each block holds the following content:
Result: The nodes of the visual script are now divided into blocks.
Note:- See Preliminaries point 5.
5) Inner Shift: This method tries to achieve straight edges within each block by shifting individual nodes inside a block. When calculating inner_shift(The shift in the offset of the node is termed as inner_shift), it considers different sizes of the nodes and port connections, which tells which output port is connected to which input port, because nodes in the visual script can have multiple input/output ports.
Result: The nodes in each block are aligned horizontally with straight edges between each node(vertex) inside each block.
6) Place Block With Straightening:
These blocks that are formed can further be divided into classes. A class is defined by a unique sink that is reachable by all of the class's nodes(See the figure below for clarification). In this final process, the blocks and classes are compacted vertically. While iterating through each block, the inner_shifts and sizes of blocks are considered; this allows the block to 'flow' into each other, leaving little free space. But this can lead to overlapping, that's why a threshold value is calculated to prevent the nodes from moving further, resulting in a straight edge. But the threshold of a block cannot be calculated until it's connected block has already been placed. To handle such cases, a queue data structure is used to store edges of such blocks. When all the blocks have been placed, edges are fetched from the Queue and check how far the concerned block can be moved without exceeding the threshold value.
Result: The blocks and classes have been compacted vertically without introducing bends within the blocks.
Without Straightening
place_block() with thresholding
After post_process()
Results
Here, the visual script is used as an example; results will be similar for graph editing and visual shaders.
The horizontal blocks have been circled out, with the arrows pointing to the starting node of the block (With in-degree 0). This is when the grid is turned off.
When the grid is turned on, they will snap like this, always to the leftmost edge(with some gap for clarity). The starting node(pointed with the arrow) will snap to the leftmost corner of the grid, and the other nodes will be placed relative to that.
Another case is when the scaling is changed.
Known Problems and Solutions
When a visual script is reorganized, the nodes enclosed by a comment node might get positioned out of that after reorganization. Solution:- Constraints can be applied when ordering the nodes and making the blocks to keep the nodes belonging to a comment node together.
Overlapping of nodes due to different horizontal lengths, like shown below
Solution: A check can be performed for overlapping when placing the node to make necessary adjustments.
References
Timeline
If this enhancement will not be used often, can it be worked around with a few lines of script?:
This is not a small number of lines.
Is there a reason why this should be core and not an add-on in the asset library?:
Modifying graph edit requires core c++. Runtime performance might be a problem in gdscript. This solves a common problem that should be in core.