Vulkan 学习笔记 04

本章代码在这里
本章的目标是实现初步的FrameGraph排序算法，Frame Graph介绍可以看这个，核心就是已知节点的输入输出，需要将节点排序成一个队列，代表最终的执行顺序。本次测试的图如下所示：

测试主程序如下，主要就是直接构建节点数据，随后使用FrameGraph进行拓扑排序：

#include "runtime/function/render/rhi/frame_graph/frame_graph.h"

#include <filesystem>
#include <iostream>
#include <memory>

using namespace ArchViz;
using namespace std;

int main(int argc, char** argv)
{
    FrameGraph graph;
    graph.name = "test_graph";

    // create nodes
    {
        FrameGraphNode node_a;
        node_a.name = "A";
        node_a.edges_forward.push_back({3});
        node_a.edges_forward.push_back({5});

        FrameGraphNode node_b;
        node_b.name = "B";
        node_b.edges_forward.push_back({1});
        node_b.edges_forward.push_back({2});
        node_b.edges_backward.push_back({4});

        FrameGraphNode node_c;
        node_c.name = "C";
        node_c.edges_forward.push_back({0});
        node_c.edges_backward.push_back({3});

        FrameGraphNode node_d;
        node_d.name = "D";
        node_d.edges_forward.push_back({0});
        node_d.edges_backward.push_back({3});
        node_d.edges_backward.push_back({5});

        FrameGraphNode node_e;
        node_e.name = "E";
        node_e.edges_backward.push_back({1});
        node_e.edges_backward.push_back({2});

        FrameGraphNode node_f;
        node_f.name = "F";
        node_f.edges_forward.push_back({2});
        node_f.edges_backward.push_back({4});

        graph.builder.node_cache.nodes.push_back(node_e);
        graph.builder.node_cache.nodes.push_back(node_c);
        graph.builder.node_cache.nodes.push_back(node_d);
        graph.builder.node_cache.nodes.push_back(node_b);
        graph.builder.node_cache.nodes.push_back(node_a);
        graph.builder.node_cache.nodes.push_back(node_f);
    }

    // graph.nodes.resize(graph.builder.node_cache.nodes.size());

    graph.init();

    for (uint32_t i = 0; i < graph.builder.node_cache.nodes.size(); ++i)
    {
        graph.nodes.push_back({i});
    }

    graph.compile();

    graph.printResult();

    std::string result;
    generate_graphviz(graph, result);
    cout << result << endl;

    graph.shutdown();

    return 0;
}

本章介绍的FrameGraph为了提高速度，将所有节点存到一个vector，通过int来索引，避免大量的内存分配带来的低效（后续将会优化，通过allocator来解决函数内部的内存分配与销毁问题）

#pragma once
#include "runtime/function/render/rhi/frame_graph/frame_resource.h"

namespace ArchViz
{
    struct FrameGraphNode
    {
        int32_t ref_count {0};

        // TODO: render pass handle
        uint32_t render_pass;
        // TODO: framebuffer handle
        uint32_t framebuffer;

        std::vector<FrameGraphResourceHandle> inputs;
        std::vector<FrameGraphResourceHandle> outputs;

        std::vector<FrameGraphNodeHandle> edges_forward;
        std::vector<FrameGraphNodeHandle> edges_backward;

        bool enabled {true};

        std::string name;
    };

    struct FrameGraphNodeCache
    {
        std::unordered_map<uint64_t, FrameGraphNodeHandle> node_map {};

        std::vector<FrameGraphNode> nodes;
    };

    struct FrameGraphBuilder
    {
        void init();
        void shutdown();

        FrameGraphNode* getNode(const std::string& name);
        FrameGraphNode* accessNode(FrameGraphNodeHandle handle);

        static constexpr uint32_t k_max_render_pass_count = 256;
        static constexpr uint32_t k_max_resources_count   = 1024;
        static constexpr uint32_t k_max_nodes_count       = 1024;

        static constexpr const char* k_name = "frame_graph_builder";

        FrameGraphNodeCache       node_cache;
    };

    struct FrameGraph
    {
        void init();
        void shutdown();

        // NOTE(marco): each frame we rebuild the graph so that we can enable only the nodes we are interested in
        void reset();
        void compile();

        void printResult();

        void render();

        FrameGraphBuilder builder;

        // NOTE(marco): nodes sorted in topological order
        std::vector<FrameGraphNodeHandle> nodes;

        std::string name;
    };

    FrameGraphResourceType string_to_resource_type(const std::string& input_type);

    void generate_graphviz(const FrameGraph& graph, std::string& result);
} // namespace ArchViz

FrameGraph的排序很简单，主要利用了节点内部的前向边指针，可以遍历到当前支链的起始节点。由于FrameGraph是有向无环图，因此一定可以找到这个起始节点。

    void FrameGraph::compile()
    {
        LOG_DEBUG("start compile frame graph");

        // - check that input has been produced by a different node
        // - cull inactive nodes

        // TODO: first clear all edges
        // TODO: re-compute all edges

        std::vector<FrameGraphNodeHandle> sorted_nodes;

        std::vector<uint8_t> visited;
        visited.resize(nodes.size());
        memset(visited.data(), 0, sizeof(uint8_t) * visited.size());

        std::vector<FrameGraphNodeHandle> stack;

        for (uint32_t i = 0; i < nodes.size(); ++i)
        {
            FrameGraphNode* node = builder.accessNode(nodes[i]);

            if (!node->enabled)
                continue;

            stack.push_back(nodes[i]);

            while (stack.size() > 0)
            {
                auto node_handle = stack.back();
                if (visited[node_handle.index] == 2)
                {
                    stack.pop_back();
                    continue;
                }

                if (visited[node_handle.index] == 1)
                {
                    visited[node_handle.index] = 2; // added
                    sorted_nodes.push_back(node_handle);
                    stack.pop_back();
                    continue;
                }

                visited[node_handle.index] = 1; // visited

                FrameGraphNode* node = builder.accessNode(node_handle);

                // Leaf node
                if (node->edges_backward.size() == 0)
                {
                    continue;
                }

                for (uint32_t r = 0; r < node->edges_backward.size(); ++r)
                {
                    FrameGraphNodeHandle child_handle = node->edges_backward[r];
                    if (!visited[child_handle.index])
                    {
                        stack.push_back(child_handle);
                    }
                }
            }
        }

        nodes.clear();
        for (auto sort : sorted_nodes)
        {
            nodes.push_back(sort);
        }

        LOG_DEBUG("finish compile frame graph");
    }

最后，为了方便调试，我添加了输出到graphviz格式的功能，可以在这里在线查看当前FrameGraph的节点结构。本次测试的输出结果如下：

digraph test_graph{
        A -> B;
        A -> F;
        B -> C;
        B -> D;
        D -> E;
        C -> E;
        F -> D;
}