khora_data/render/
frame_graph.rs

1// Copyright 2025 eraflo
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Per-frame render graph: agents enqueue declarative passes here, the engine
16//! drains the graph after the scheduler completes and submits the recorded
17//! command buffers in topological order.
18//!
19//! Lives in `khora-data` because it is a *data container* — there is no
20//! GORNA strategy to negotiate, no behavior to swap. The submission step
21//! (`submit_frame_graph`) is invoked directly by `EngineCore`.
22
23use std::collections::{HashMap, HashSet, VecDeque};
24use std::sync::{Arc, Mutex};
25
26use khora_core::renderer::api::command::CommandBufferId;
27use khora_core::renderer::GraphicsDevice;
28
29/// Logical resource handle in the frame graph — used for declaring reads/writes.
30///
31/// Resources here are *abstract*: the actual GPU views live in `FrameContext`
32/// (`ColorTarget`, `DepthTarget`, `ShadowAtlasView`). The graph only orders
33/// passes; it does not allocate or alias resources yet.
34#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
35pub enum ResourceId {
36    /// Swapchain (or offscreen viewport) color attachment.
37    Color,
38    /// Frame depth attachment.
39    Depth,
40    /// Shadow atlas — written by `ShadowAgent`, read by `RenderAgent`.
41    ShadowAtlas,
42    /// Custom resource keyed by an opaque integer (plugin / future use).
43    Custom(u64),
44}
45
46/// Declarative description of a render pass.
47#[derive(Debug, Clone)]
48pub struct PassDescriptor {
49    /// Debug-friendly pass name.
50    pub name: &'static str,
51    /// Resources read by this pass.
52    pub reads: Vec<ResourceId>,
53    /// Resources written by this pass.
54    pub writes: Vec<ResourceId>,
55}
56
57impl PassDescriptor {
58    /// Builds a descriptor with the given name and no declared resources.
59    pub fn new(name: &'static str) -> Self {
60        Self {
61            name,
62            reads: Vec::new(),
63            writes: Vec::new(),
64        }
65    }
66
67    /// Adds a read dependency.
68    pub fn reads(mut self, id: ResourceId) -> Self {
69        self.reads.push(id);
70        self
71    }
72
73    /// Adds a write dependency.
74    pub fn writes(mut self, id: ResourceId) -> Self {
75        self.writes.push(id);
76        self
77    }
78}
79
80/// One pre-recorded pass: descriptor + finished command buffer.
81struct RecordedPass {
82    descriptor: PassDescriptor,
83    command_buffer: CommandBufferId,
84}
85
86/// A render pass an agent contributes for this frame.
87///
88/// Instead of locking the shared [`SharedFrameGraph`] to `add_pass` directly,
89/// a recording agent writes its contribution into a per-layer slot on its
90/// [`OutputDeck`](khora_core::lane::OutputDeck) ([`ScenePassSlot`],
91/// [`UiPassSlot`], [`OverlayPassSlot`]). The engine folds those slots into the
92/// graph in a fixed layer order (scene → ui → overlay) after the agent wave —
93/// preserving the previous insertion order while freeing the agents from the
94/// `Mutex<FrameGraph>`, so they can run concurrently.
95pub struct PassContribution {
96    /// The pass's resource read/write declaration.
97    pub descriptor: PassDescriptor,
98    /// The finished command buffer recorded for the pass.
99    pub command_buffer: CommandBufferId,
100}
101
102/// Deck slot carrying the main scene pass, written by `RenderAgent`.
103#[derive(Default)]
104pub struct ScenePassSlot(pub Option<PassContribution>);
105
106/// Deck slot carrying the UI pass, written by `UiAgent`.
107#[derive(Default)]
108pub struct UiPassSlot(pub Option<PassContribution>);
109
110/// Deck slot carrying the skybox / environment-background pass, written by
111/// `SkyboxAgent`. Folded in after the scene pass and before overlays, so the
112/// sky sits behind the geometry (depth-tested) and under the debug overlays.
113#[derive(Default)]
114pub struct SkyboxPassSlot(pub Option<PassContribution>);
115
116/// Deck slot carrying the overlay / debug-viz pass, written by `OverlayAgent`.
117#[derive(Default)]
118pub struct OverlayPassSlot(pub Option<PassContribution>);
119
120/// Per-frame collection of recorded passes.
121///
122/// Agents append passes during `execute()`. `submit_frame_graph` drains the
123/// graph in topological order and submits the buffers to the device.
124#[derive(Default)]
125pub struct FrameGraph {
126    passes: Vec<RecordedPass>,
127}
128
129impl FrameGraph {
130    /// Creates an empty frame graph.
131    pub fn new() -> Self {
132        Self { passes: Vec::new() }
133    }
134
135    /// Records a pass: descriptor + the command buffer the agent already produced.
136    pub fn add_pass(&mut self, descriptor: PassDescriptor, command_buffer: CommandBufferId) {
137        self.passes.push(RecordedPass {
138            descriptor,
139            command_buffer,
140        });
141    }
142
143    /// Number of recorded passes.
144    pub fn len(&self) -> usize {
145        self.passes.len()
146    }
147
148    /// Whether the graph has no recorded passes.
149    pub fn is_empty(&self) -> bool {
150        self.passes.is_empty()
151    }
152
153    /// Drops all recorded passes without submitting them — used to recover
154    /// from a frame error before the engine reaches the submit step.
155    pub fn clear(&mut self) {
156        self.passes.clear();
157    }
158
159    /// Drains the graph and returns command buffers in submission order.
160    ///
161    /// The order is computed by a stable Kahn's algorithm over read/write
162    /// dependencies: a pass that writes resource `R` must run before any
163    /// pass that reads `R`. Insertion order is the tie-breaker, so when the
164    /// declared order is already valid (the common case) the result equals
165    /// insertion order.
166    pub fn compile(&mut self) -> Vec<CommandBufferId> {
167        let passes = std::mem::take(&mut self.passes);
168        sorted_passes(passes)
169            .into_iter()
170            .map(|p| p.command_buffer)
171            .collect()
172    }
173}
174
175/// Shared, mutable handle on the per-frame graph — registered as a service.
176pub type SharedFrameGraph = Arc<Mutex<FrameGraph>>;
177
178/// Drains `graph` and submits every recorded command buffer in topological
179/// order. Returns the number of submitted buffers.
180pub fn submit_frame_graph(graph: &SharedFrameGraph, device: &dyn GraphicsDevice) -> usize {
181    let buffers = {
182        let mut guard = graph.lock().expect("FrameGraph mutex poisoned");
183        guard.compile()
184    };
185    let count = buffers.len();
186    for buffer in buffers {
187        device.submit_command_buffer(buffer);
188    }
189    count
190}
191
192// ─────────────────────────────────────────────────────────────────────────────
193// Topological sort — stable Kahn's algorithm
194// ─────────────────────────────────────────────────────────────────────────────
195
196fn sorted_passes(passes: Vec<RecordedPass>) -> Vec<RecordedPass> {
197    let n = passes.len();
198    if n <= 1 {
199        return passes;
200    }
201
202    // Edge i → j when pass i writes a resource that pass j reads (and j > i in
203    // insertion order; the latest writer is the one that produces the value
204    // for downstream readers).
205    let mut last_writer: HashMap<ResourceId, usize> = HashMap::new();
206    let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
207    let mut in_deg = vec![0usize; n];
208
209    for (i, pass) in passes.iter().enumerate() {
210        for read in &pass.descriptor.reads {
211            if let Some(&writer) = last_writer.get(read) {
212                if writer != i {
213                    adj[writer].push(i);
214                    in_deg[i] += 1;
215                }
216            }
217        }
218        for write in &pass.descriptor.writes {
219            last_writer.insert(*write, i);
220        }
221    }
222
223    let mut queue: VecDeque<usize> = (0..n).filter(|&i| in_deg[i] == 0).collect();
224    let mut order = Vec::with_capacity(n);
225    let mut visited: HashSet<usize> = HashSet::new();
226    while let Some(i) = queue.pop_front() {
227        if !visited.insert(i) {
228            continue;
229        }
230        order.push(i);
231        for &j in &adj[i] {
232            in_deg[j] -= 1;
233            if in_deg[j] == 0 {
234                queue.push_back(j);
235            }
236        }
237    }
238
239    debug_assert_eq!(order.len(), n, "FrameGraph cycle detected");
240
241    let mut indexed: Vec<Option<RecordedPass>> = passes.into_iter().map(Some).collect();
242    order
243        .into_iter()
244        .map(|i| indexed[i].take().expect("pass already taken"))
245        .collect()
246}
247
248#[cfg(test)]
249mod tests {
250    use super::*;
251    use khora_core::renderer::api::command::CommandBufferId;
252
253    fn buf(id: u64) -> CommandBufferId {
254        CommandBufferId(id)
255    }
256
257    #[test]
258    fn empty_graph_compiles_empty() {
259        let mut g = FrameGraph::new();
260        assert_eq!(g.compile().len(), 0);
261    }
262
263    #[test]
264    fn single_pass_returned_as_is() {
265        let mut g = FrameGraph::new();
266        g.add_pass(PassDescriptor::new("scene"), buf(1));
267        let order = g.compile();
268        assert_eq!(order, vec![buf(1)]);
269    }
270
271    #[test]
272    fn insertion_order_preserved_when_dependencies_match() {
273        let mut g = FrameGraph::new();
274        g.add_pass(
275            PassDescriptor::new("shadow").writes(ResourceId::ShadowAtlas),
276            buf(1),
277        );
278        g.add_pass(
279            PassDescriptor::new("scene")
280                .reads(ResourceId::ShadowAtlas)
281                .writes(ResourceId::Color),
282            buf(2),
283        );
284        g.add_pass(
285            PassDescriptor::new("ui")
286                .reads(ResourceId::Color)
287                .writes(ResourceId::Color),
288            buf(3),
289        );
290        assert_eq!(g.compile(), vec![buf(1), buf(2), buf(3)]);
291    }
292
293    #[test]
294    fn reads_force_writer_first_even_if_inserted_late() {
295        // A reader inserted before the writer is allowed: insertion-order tie
296        // breaks ties only when no edge is established. Here we test that
297        // edges are correctly built when reads precede writes in the input.
298        let mut g = FrameGraph::new();
299        // pass0 reads X but no one writes X yet → no edge.
300        g.add_pass(PassDescriptor::new("a").reads(ResourceId::Color), buf(1));
301        // pass1 writes X.
302        g.add_pass(PassDescriptor::new("b").writes(ResourceId::Color), buf(2));
303        // pass2 reads X → must be after pass1.
304        g.add_pass(PassDescriptor::new("c").reads(ResourceId::Color), buf(3));
305
306        let order = g.compile();
307        let pos_b = order.iter().position(|b| *b == buf(2)).unwrap();
308        let pos_c = order.iter().position(|b| *b == buf(3)).unwrap();
309        assert!(pos_b < pos_c);
310    }
311
312    #[test]
313    fn clear_drops_passes() {
314        let mut g = FrameGraph::new();
315        g.add_pass(PassDescriptor::new("scene"), buf(1));
316        g.add_pass(PassDescriptor::new("ui"), buf(2));
317        assert_eq!(g.len(), 2);
318        g.clear();
319        assert!(g.is_empty());
320    }
321}
khora_data/render/frame_graph.rs

khora_data/render/
frame_graph.rs
