tessera_ui/
render_graph.rs

1//! Render graph fragments and nodes for Tessera.
2//!
3//! ## Usage
4//!
5//! Build per-component render fragments and merge them into a frame graph.
6
7use std::{
8    any::TypeId,
9    collections::{BinaryHeap, HashMap},
10};
11
12use smallvec::SmallVec;
13
14use crate::{
15    Command, CompositeCommand, ComputeCommand, DrawCommand, DrawRegion, SampleRegion,
16    px::{Px, PxPosition, PxRect, PxSize},
17};
18
19/// Resource identifier used by render graph nodes.
20#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
21pub enum RenderResourceId {
22    /// The main scene color buffer.
23    SceneColor,
24    /// The main scene depth buffer.
25    SceneDepth,
26    /// A local texture allocated by a fragment.
27    Local(u32),
28    /// A persistent texture owned by a pipeline.
29    External(u32),
30}
31
32/// Descriptor for a local render texture.
33#[derive(Debug, Clone, PartialEq, Eq)]
34pub struct RenderTextureDesc {
35    /// Pixel size of the texture.
36    pub size: PxSize,
37    /// Texture format.
38    pub format: wgpu::TextureFormat,
39}
40
41/// Render graph resource description.
42#[derive(Debug, Clone, PartialEq, Eq)]
43pub enum RenderResource {
44    /// A texture resource allocated for a fragment.
45    Texture(RenderTextureDesc),
46}
47
48/// Descriptor for a persistent external texture.
49#[derive(Debug, Clone, PartialEq, Eq)]
50pub struct ExternalTextureDesc {
51    /// Registry handle identifier for the texture.
52    pub handle_id: u32,
53    /// Pixel size of the texture.
54    pub size: PxSize,
55    /// Texture format.
56    pub format: wgpu::TextureFormat,
57    /// MSAA sample count for render targets.
58    pub sample_count: u32,
59    /// Whether to clear the texture on the first render pass write.
60    pub clear_on_first_use: bool,
61}
62
63/// A single render op inside a fragment graph.
64#[derive(Clone)]
65pub struct RenderFragmentOp {
66    /// The command to execute.
67    pub command: Command,
68    /// Type identifier used for batching.
69    pub type_id: TypeId,
70    /// Resource read by this op.
71    pub read: Option<RenderResourceId>,
72    /// Resource written by this op.
73    pub write: Option<RenderResourceId>,
74    /// Local dependencies inside the fragment.
75    pub deps: SmallVec<[u32; 2]>,
76    /// Optional size override for this op.
77    pub size_override: Option<PxSize>,
78    /// Optional position override for this op (SceneColor ops treat it as
79    /// offset).
80    pub position_override: Option<PxPosition>,
81}
82
83/// A per-component render fragment.
84#[derive(Default, Clone)]
85pub struct RenderFragment {
86    ops: Vec<RenderFragmentOp>,
87    resources: Vec<RenderResource>,
88}
89
90impl RenderFragment {
91    /// Returns fragment ops in insertion order.
92    #[must_use]
93    pub fn ops(&self) -> &[RenderFragmentOp] {
94        &self.ops
95    }
96
97    /// Returns local resources declared by this fragment.
98    #[must_use]
99    pub fn resources(&self) -> &[RenderResource] {
100        &self.resources
101    }
102
103    /// Adds a local texture resource to the fragment.
104    pub fn add_local_texture(&mut self, desc: RenderTextureDesc) -> RenderResourceId {
105        let index = self.resources.len() as u32;
106        self.resources.push(RenderResource::Texture(desc));
107        RenderResourceId::Local(index)
108    }
109
110    /// Adds a draw command with default scene resource bindings.
111    pub fn push_draw_command<C: DrawCommand + 'static>(&mut self, command: C) -> u32 {
112        let type_id = TypeId::of::<C>();
113        let read = command
114            .sample_region()
115            .is_some()
116            .then_some(RenderResourceId::SceneColor);
117        let write = Some(RenderResourceId::SceneColor);
118
119        let op = RenderFragmentOp {
120            command: Command::Draw(Box::new(command)),
121            type_id,
122            read,
123            write,
124            deps: SmallVec::new(),
125            size_override: None,
126            position_override: None,
127        };
128        self.push_op(op)
129    }
130
131    /// Adds a compute command with default scene resource bindings.
132    pub fn push_compute_command<C: ComputeCommand + 'static>(&mut self, command: C) -> u32 {
133        let type_id = TypeId::of::<C>();
134        let read = Some(RenderResourceId::SceneColor);
135        let write = Some(RenderResourceId::SceneColor);
136
137        let op = RenderFragmentOp {
138            command: Command::Compute(Box::new(command)),
139            type_id,
140            read,
141            write,
142            deps: SmallVec::new(),
143            size_override: None,
144            position_override: None,
145        };
146        self.push_op(op)
147    }
148
149    /// Adds a composite command with default scene resource bindings.
150    pub fn push_composite_command<C: CompositeCommand + 'static>(&mut self, command: C) -> u32 {
151        let type_id = TypeId::of::<C>();
152        let op = RenderFragmentOp {
153            command: Command::Composite(Box::new(command)),
154            type_id,
155            read: None,
156            write: Some(RenderResourceId::SceneColor),
157            deps: SmallVec::new(),
158            size_override: None,
159            position_override: None,
160        };
161        self.push_op(op)
162    }
163
164    /// Adds a render op to the fragment.
165    pub fn push_op(&mut self, op: RenderFragmentOp) -> u32 {
166        let index = self.ops.len() as u32;
167        self.ops.push(op);
168        index
169    }
170
171    /// Clears all ops and resources in the fragment.
172    pub fn clear(&mut self) {
173        self.ops.clear();
174        self.resources.clear();
175    }
176}
177
178/// A render op after merging into the frame graph.
179#[derive(Clone)]
180pub struct RenderGraphOp {
181    /// The command to execute.
182    pub command: Command,
183    /// Type identifier used for batching and ordering.
184    pub type_id: TypeId,
185    /// Resource read for the op.
186    pub read: Option<RenderResourceId>,
187    /// Resource write for the op.
188    pub write: Option<RenderResourceId>,
189    /// Dependencies on other ops by index.
190    pub deps: SmallVec<[usize; 2]>,
191    /// Measured size of the op.
192    pub size: PxSize,
193    /// Absolute position of the op.
194    pub position: PxPosition,
195    /// Opacity multiplier applied during record.
196    pub opacity: f32,
197    /// Sequence index used to preserve authoring order.
198    pub sequence_index: usize,
199}
200
201/// Frame-level render graph.
202#[derive(Default)]
203pub struct RenderGraph {
204    ops: Vec<RenderGraphOp>,
205    resources: Vec<RenderResource>,
206    external_resources: Vec<ExternalTextureDesc>,
207}
208
209/// Owned render graph payload for graph transforms.
210pub struct RenderGraphParts {
211    /// Render ops for the frame.
212    pub ops: Vec<RenderGraphOp>,
213    /// Resource declarations referenced by the ops.
214    pub resources: Vec<RenderResource>,
215    /// External resources referenced by the ops.
216    pub external_resources: Vec<ExternalTextureDesc>,
217}
218
219impl RenderGraph {
220    /// Returns ops in the graph.
221    #[must_use]
222    pub fn ops(&self) -> &[RenderGraphOp] {
223        &self.ops
224    }
225
226    /// Returns local resources in the graph.
227    #[must_use]
228    pub fn resources(&self) -> &[RenderResource] {
229        &self.resources
230    }
231
232    /// Returns external resources in the graph.
233    #[must_use]
234    pub fn external_resources(&self) -> &[ExternalTextureDesc] {
235        &self.external_resources
236    }
237
238    /// Decomposes the graph into owned parts for graph processing.
239    #[must_use]
240    pub fn into_parts(self) -> RenderGraphParts {
241        RenderGraphParts {
242            ops: self.ops,
243            resources: self.resources,
244            external_resources: self.external_resources,
245        }
246    }
247
248    /// Builds a render graph from owned parts.
249    #[must_use]
250    pub fn from_parts(parts: RenderGraphParts) -> Self {
251        Self {
252            ops: parts.ops,
253            resources: parts.resources,
254            external_resources: parts.external_resources,
255        }
256    }
257
258    /// Consumes the graph and returns an execution-ready payload.
259    pub(crate) fn into_execution(self) -> RenderGraphExecution {
260        RenderGraphExecution {
261            ops: order_ops(self.ops),
262            resources: self.resources,
263            external_resources: self.external_resources,
264        }
265    }
266}
267
268/// Ordered render ops with resource declarations for the current frame.
269pub(crate) struct RenderGraphExecution {
270    pub(crate) ops: Vec<RenderGraphOp>,
271    pub(crate) resources: Vec<RenderResource>,
272    pub(crate) external_resources: Vec<ExternalTextureDesc>,
273}
274
275/// Builder for a frame-level render graph.
276pub(crate) struct RenderGraphBuilder {
277    ops: Vec<RenderGraphOp>,
278    resources: Vec<RenderResource>,
279    external_resources: Vec<ExternalTextureDesc>,
280    sequence_index: usize,
281}
282
283impl RenderGraphBuilder {
284    /// Creates a new render graph builder.
285    pub(crate) fn new() -> Self {
286        Self {
287            ops: Vec::new(),
288            resources: Vec::new(),
289            external_resources: Vec::new(),
290            sequence_index: 0,
291        }
292    }
293
294    /// Pushes a clip push op into the graph.
295    pub(crate) fn push_clip_push(&mut self, rect: PxRect) {
296        self.ops.push(RenderGraphOp {
297            command: Command::ClipPush(rect),
298            type_id: TypeId::of::<Command>(),
299            read: None,
300            write: None,
301            deps: SmallVec::new(),
302            size: PxSize::ZERO,
303            position: PxPosition::ZERO,
304            opacity: 1.0,
305            sequence_index: self.sequence_index,
306        });
307        self.sequence_index += 1;
308    }
309
310    /// Pushes a clip pop op into the graph.
311    pub(crate) fn push_clip_pop(&mut self) {
312        self.ops.push(RenderGraphOp {
313            command: Command::ClipPop,
314            type_id: TypeId::of::<Command>(),
315            read: None,
316            write: None,
317            deps: SmallVec::new(),
318            size: PxSize::ZERO,
319            position: PxPosition::ZERO,
320            opacity: 1.0,
321            sequence_index: self.sequence_index,
322        });
323        self.sequence_index += 1;
324    }
325
326    /// Appends a fragment into the frame graph.
327    pub(crate) fn append_fragment(
328        &mut self,
329        mut fragment: RenderFragment,
330        size: PxSize,
331        position: PxPosition,
332        opacity: f32,
333    ) {
334        if fragment.ops.is_empty() {
335            return;
336        }
337
338        let mut resource_map: Vec<RenderResourceId> = Vec::with_capacity(fragment.resources.len());
339        for resource in fragment.resources.drain(..) {
340            let index = self.resources.len() as u32;
341            self.resources.push(resource);
342            resource_map.push(RenderResourceId::Local(index));
343        }
344
345        let base_index = self.ops.len();
346
347        for mut op in fragment.ops.drain(..) {
348            let writes_scene = op.write == Some(RenderResourceId::SceneColor);
349            let position_override = op.position_override.unwrap_or(PxPosition::ZERO);
350            let size_override = op.size_override.unwrap_or(size);
351
352            let read = op.read.map(|r| map_resource(r, &resource_map));
353            let write = op.write.map(|w| map_resource(w, &resource_map));
354            let deps = op
355                .deps
356                .iter()
357                .map(|dep| base_index + *dep as usize)
358                .collect::<SmallVec<[usize; 2]>>();
359
360            if let Command::Draw(ref mut command) = op.command {
361                command.apply_opacity(opacity);
362            }
363
364            let resolved_position = if writes_scene {
365                position + position_override
366            } else {
367                position_override
368            };
369
370            self.ops.push(RenderGraphOp {
371                command: op.command,
372                type_id: op.type_id,
373                read,
374                write,
375                deps,
376                size: size_override,
377                position: resolved_position,
378                opacity,
379                sequence_index: self.sequence_index,
380            });
381            self.sequence_index += 1;
382        }
383    }
384
385    /// Finishes graph construction.
386    pub(crate) fn finish(self) -> RenderGraph {
387        RenderGraph {
388            ops: self.ops,
389            resources: self.resources,
390            external_resources: self.external_resources,
391        }
392    }
393}
394
395fn map_resource(resource: RenderResourceId, local_map: &[RenderResourceId]) -> RenderResourceId {
396    match resource {
397        RenderResourceId::Local(index) => local_map
398            .get(index as usize)
399            .copied()
400            .unwrap_or(RenderResourceId::Local(index)),
401        RenderResourceId::External(index) => RenderResourceId::External(index),
402        other => other,
403    }
404}
405
406fn order_ops(ops: Vec<RenderGraphOp>) -> Vec<RenderGraphOp> {
407    if ops.is_empty() {
408        return ops;
409    }
410
411    let infos: Vec<OpInfo> = ops.iter().map(OpInfo::new).collect();
412    let mut potentials: HashMap<(OpCategory, TypeId), usize> = HashMap::new();
413    for info in &infos {
414        *potentials.entry((info.category, info.type_id)).or_insert(0) += 1;
415    }
416
417    let mut outgoing: Vec<SmallVec<[usize; 4]>> = vec![SmallVec::new(); ops.len()];
418    let mut in_degree = vec![0usize; ops.len()];
419
420    for (idx, op) in ops.iter().enumerate() {
421        for dep in &op.deps {
422            add_edge(&mut outgoing, &mut in_degree, *dep, idx);
423        }
424    }
425
426    let mut by_sequence: Vec<usize> = (0..ops.len()).collect();
427    by_sequence.sort_by_key(|idx| ops[*idx].sequence_index);
428    for (offset, &left) in by_sequence.iter().enumerate() {
429        for &right in &by_sequence[offset + 1..] {
430            if needs_ordering(&infos[left], &infos[right], &ops[left], &ops[right]) {
431                add_edge(&mut outgoing, &mut in_degree, left, right);
432            }
433        }
434    }
435
436    let mut ready = BinaryHeap::new();
437    for (idx, degree) in in_degree.iter().enumerate() {
438        if *degree == 0 {
439            ready.push(PriorityNode::new(idx, &infos, &potentials));
440        }
441    }
442
443    let mut ordered_indices = Vec::with_capacity(ops.len());
444    let mut last_type_id: Option<TypeId> = None;
445
446    while !ready.is_empty() {
447        let highest_category = ready.peek().map(|node| node.category);
448        let mut selected: Option<PriorityNode> = None;
449        if let (Some(last_type), Some(high_cat)) = (last_type_id, highest_category) {
450            let mut deferred = Vec::new();
451            while let Some(node) = ready.pop() {
452                if node.category == high_cat && node.type_id == last_type {
453                    selected = Some(node);
454                    break;
455                }
456                deferred.push(node);
457            }
458            for node in deferred {
459                ready.push(node);
460            }
461        }
462
463        let priority_node = selected.unwrap_or_else(|| {
464            ready
465                .pop()
466                .expect("ready queue should not be empty while sorting ops")
467        });
468        let u = priority_node.node_index;
469        ordered_indices.push(u);
470        match priority_node.category {
471            OpCategory::StateChange => last_type_id = None,
472            _ => last_type_id = Some(priority_node.type_id),
473        }
474
475        for &next in &outgoing[u] {
476            in_degree[next] -= 1;
477            if in_degree[next] == 0 {
478                ready.push(PriorityNode::new(next, &infos, &potentials));
479            }
480        }
481    }
482
483    if ordered_indices.len() != ops.len() {
484        let mut fallback = ops;
485        fallback.sort_by_key(|op| op.sequence_index);
486        return fallback;
487    }
488
489    let mut ops = ops;
490    let mut ops_by_index: Vec<Option<RenderGraphOp>> = ops.drain(..).map(Some).collect();
491    let mut ordered = Vec::with_capacity(ordered_indices.len());
492    for index in ordered_indices {
493        if let Some(op) = ops_by_index[index].take() {
494            ordered.push(op);
495        }
496    }
497
498    ordered
499}
500
501#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
502enum OpCategory {
503    ContinuationDraw,
504    BarrierDraw,
505    Compute,
506    StateChange,
507}
508
509struct OpInfo {
510    category: OpCategory,
511    type_id: TypeId,
512    sequence_index: usize,
513    read_rect: Option<PxRect>,
514    write_rect: Option<PxRect>,
515}
516
517impl OpInfo {
518    fn new(op: &RenderGraphOp) -> Self {
519        let category = match &op.command {
520            Command::Draw(command) => {
521                if command.sample_region().is_some() {
522                    OpCategory::BarrierDraw
523                } else {
524                    OpCategory::ContinuationDraw
525                }
526            }
527            Command::Compute(_) => OpCategory::Compute,
528            Command::Composite(_) => OpCategory::StateChange,
529            Command::ClipPush(_) | Command::ClipPop => OpCategory::StateChange,
530        };
531
532        Self {
533            category,
534            type_id: op.type_id,
535            sequence_index: op.sequence_index,
536            read_rect: scene_read_rect(op),
537            write_rect: scene_write_rect(op),
538        }
539    }
540}
541
542#[derive(Debug, Clone, Copy, PartialEq, Eq)]
543struct PriorityNode {
544    category: OpCategory,
545    type_id: TypeId,
546    original_index: usize,
547    node_index: usize,
548    batch_potential: usize,
549}
550
551impl PriorityNode {
552    fn new(
553        node_index: usize,
554        infos: &[OpInfo],
555        potentials: &HashMap<(OpCategory, TypeId), usize>,
556    ) -> Self {
557        let info = &infos[node_index];
558        let batch_potential = potentials
559            .get(&(info.category, info.type_id))
560            .copied()
561            .unwrap_or(1);
562        Self {
563            category: info.category,
564            type_id: info.type_id,
565            original_index: info.sequence_index,
566            node_index,
567            batch_potential,
568        }
569    }
570}
571
572impl Ord for PriorityNode {
573    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
574        self.category
575            .cmp(&other.category)
576            .then_with(|| other.batch_potential.cmp(&self.batch_potential))
577            .then_with(|| other.original_index.cmp(&self.original_index))
578    }
579}
580
581impl PartialOrd for PriorityNode {
582    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
583        Some(self.cmp(other))
584    }
585}
586
587fn add_edge(
588    outgoing: &mut [SmallVec<[usize; 4]>],
589    in_degree: &mut [usize],
590    from: usize,
591    to: usize,
592) {
593    if from == to || outgoing[from].contains(&to) {
594        return;
595    }
596    outgoing[from].push(to);
597    in_degree[to] += 1;
598}
599
600fn needs_ordering(
601    left: &OpInfo,
602    right: &OpInfo,
603    left_op: &RenderGraphOp,
604    right_op: &RenderGraphOp,
605) -> bool {
606    if left.category == OpCategory::StateChange || right.category == OpCategory::StateChange {
607        return true;
608    }
609
610    if non_scene_conflict(left_op, right_op) {
611        return true;
612    }
613
614    scene_conflict(left, right)
615}
616
617fn non_scene_conflict(left: &RenderGraphOp, right: &RenderGraphOp) -> bool {
618    if let Some(resource) = left.write {
619        if resource == RenderResourceId::SceneColor {
620            return false;
621        }
622        if Some(resource) == right.read || Some(resource) == right.write {
623            return true;
624        }
625    }
626
627    if let Some(resource) = left.read {
628        if resource == RenderResourceId::SceneColor {
629            return false;
630        }
631        if Some(resource) == right.write {
632            return true;
633        }
634    }
635
636    false
637}
638
639fn scene_conflict(left: &OpInfo, right: &OpInfo) -> bool {
640    if let (Some(write_left), Some(write_right)) = (left.write_rect, right.write_rect)
641        && !write_left.is_orthogonal(&write_right)
642    {
643        return true;
644    }
645    if let (Some(write_left), Some(read_right)) = (left.write_rect, right.read_rect)
646        && !write_left.is_orthogonal(&read_right)
647    {
648        return true;
649    }
650    if let (Some(read_left), Some(write_right)) = (left.read_rect, right.write_rect)
651        && !read_left.is_orthogonal(&write_right)
652    {
653        return true;
654    }
655    false
656}
657
658fn scene_read_rect(op: &RenderGraphOp) -> Option<PxRect> {
659    if op.read != Some(RenderResourceId::SceneColor) {
660        return None;
661    }
662    match &op.command {
663        Command::Draw(command) => command
664            .sample_region()
665            .map(|region| sample_region_rect(region, op.position, op.size)),
666        Command::Compute(command) => {
667            Some(sample_region_rect(command.barrier(), op.position, op.size))
668        }
669        Command::Composite(_) => None,
670        Command::ClipPush(_) | Command::ClipPop => None,
671    }
672}
673
674fn scene_write_rect(op: &RenderGraphOp) -> Option<PxRect> {
675    if op.write != Some(RenderResourceId::SceneColor) {
676        return None;
677    }
678    match &op.command {
679        Command::Draw(command) => Some(
680            command
681                .ordering_rect(op.position, op.size)
682                .unwrap_or_else(|| draw_region_rect(command.draw_region(), op.position, op.size)),
683        ),
684        Command::Compute(_) => Some(PxRect::from_position_size(op.position, op.size)),
685        Command::Composite(_) => None,
686        Command::ClipPush(_) | Command::ClipPop => None,
687    }
688}
689
690fn sample_region_rect(region: SampleRegion, position: PxPosition, size: PxSize) -> PxRect {
691    match region {
692        SampleRegion::Global => PxRect::new(Px::ZERO, Px::ZERO, Px::MAX, Px::MAX),
693        SampleRegion::PaddedLocal(_) => {
694            // Use component bounds to avoid padded sampling regions forcing dependencies.
695            PxRect::from_position_size(position, size)
696        }
697        SampleRegion::Absolute(rect) => rect,
698    }
699}
700
701fn draw_region_rect(region: DrawRegion, position: PxPosition, size: PxSize) -> PxRect {
702    match region {
703        DrawRegion::Global => PxRect::new(Px::ZERO, Px::ZERO, Px::MAX, Px::MAX),
704        DrawRegion::PaddedLocal(padding) => padded_rect(position, size, padding),
705        DrawRegion::Absolute(rect) => rect,
706    }
707}
708
709fn padded_rect(position: PxPosition, size: PxSize, padding: crate::PaddingRect) -> PxRect {
710    PxRect::new(
711        position.x - padding.left,
712        position.y - padding.top,
713        size.width + padding.left + padding.right,
714        size.height + padding.top + padding.bottom,
715    )
716}
tessera_ui/render_graph.rs

tessera_ui/
render_graph.rs
