18243240671

Committed 04 Oct 2025 10:36AM UTC coverage: 66.58% (+0.1%) from 66.455%

Build # 18243240671

Build Type

push

github

Committed by

web-flow

Commit Message

Split extraction and render into unit systems (#499)

Reorganize most of the extraction and render systems into smaller,
unit-like systems with limited (ideally, a single) responsibility. Split
most of the data into separate, smaller components too. This not only
enable better multithreading, but also greatly simplify maintenance by
clarifying the logic and responsibility of each system and component.

As part of this change, add a "ready state" to the effect, which is read
back from the render world and informs the main world about whether an
effect is ready for simulation and rendering. This includes:

- All GPU resources being allocated, and in particular the PSOs
  (pipelines) which in Bevy are compiled asynchronously and can be very
  slow (many frames of delay).
- The ready state of all descendant effects, recursively. This ensures a
  child is ready to _e.g._ receive GPU spawn events before its parent,
  which emits those events, starts simulating.

This new ready state is accessed via
`CompiledParticleEffect::is_ready()`. Note that the state is updated
during the extract phase with the information collected from the
previous render frame, so by the time `is_ready()` returns `true`,
already one frame of simulation and rendering generally occurred.

Remove the outdated `copyless` dependency.

Run Details

594 of 896 new or added lines in 12 files covered. (66.29%)

21 existing lines in 3 files now uncovered.

5116 of 7684 relevant lines covered (66.58%)

416.91 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

94.67

/src/render/batch.rs

use std::{fmt::Debug, num::NonZeroU32, ops::Range};

use bevy::{
    ecs::entity::EntityHashMap,
    prelude::*,
    render::{render_resource::CachedComputePipelineId, sync_world::MainEntity},
};
use fixedbitset::FixedBitSet;

use super::{
    effect_cache::{DispatchBufferIndices, EffectSlice},
    event::{CachedChildInfo, CachedEffectEvents},
    BufferBindingSource, ExtractedEffectMesh, LayoutFlags, PropertyBindGroupKey,
};
use crate::{
    render::{
        buffer_table::BufferTableId, effect_cache::SlabId, ExtractedEffect, ExtractedSpawner,
    },
    AlphaMode, EffectAsset, ParticleLayout, TextureLayout,
};

#[derive(Debug, Clone, Copy)]
pub(crate) enum BatchSpawnInfo {
    /// Spawn a number of particles uploaded from CPU each frame.
    CpuSpawner {
        /// Total number of particles to spawn for the batch. This is only used
        /// to calculate the number of compute workgroups to dispatch.
        total_spawn_count: u32,
    },

    /// Spawn a number of particles calculated on GPU from "spawn events", which
    /// generally emitted by another effect.
    GpuSpawner {
        /// Index into the init indirect dispatch buffer of the
        /// [`GpuDispatchIndirect`] instance for this batch.
        ///
        /// [`GpuDispatchIndirect`]: super::GpuDispatchIndirect
        init_indirect_dispatch_index: u32,
        /// Index of the [`EventBuffer`] where the GPU spawn events consumed by
        /// this batch are stored.
        ///
        /// [`EventBuffer`]: super::event::EventBuffer
        #[allow(dead_code)]
        event_buffer_index: u32,
    },
}

/// Batch of effects dispatched and rendered together.
#[derive(Debug, Clone)]
pub(crate) struct EffectBatch {
    /// Handle of the underlying effect asset describing the effect.
    pub handle: Handle<EffectAsset>,
    /// ID of the particle slab in the [`EffectBuffer`] where all the batched
    /// effects are stored.
    ///
    /// [`EffectBuffer`]: super::effect_cache::EffectBuffer
    pub slab_id: SlabId,
    /// Slice of particles in the GPU effect buffer referenced by
    /// [`EffectBatch::slab_id`].
    pub slice: Range<u32>,
    /// Spawn info for this batch
    pub spawn_info: BatchSpawnInfo,
    /// Specialized init and update compute pipelines.
    pub init_and_update_pipeline_ids: InitAndUpdatePipelineIds,
    /// Configured shader used for the particle rendering of this group.
    /// Note that we don't need to keep the init/update shaders alive because
    /// their pipeline specialization is doing it via the specialization key.
    pub render_shader: Handle<Shader>,
    /// ID of the particle slab where the parent effect is stored, if any. If a
    /// parent exists, its particle buffer is made available (read-only) for
    /// a child effect to read its attributes.
    pub parent_slab_id: Option<SlabId>,
    pub parent_min_binding_size: Option<NonZeroU32>,
    pub parent_binding_source: Option<BufferBindingSource>,
    /// Event buffers of child effects, if any.
    pub child_event_buffers: Vec<(Entity, BufferBindingSource)>,
    /// Index of the property buffer, if any.
    pub property_key: Option<PropertyBindGroupKey>,
    /// Offset in bytes into the property buffer where the Property struct is
    /// located for this effect.
    // FIXME: This is a per-instance value which prevents batching :(
    pub property_offset: Option<u32>,
    /// Index of the first [`GpuSpawnerParams`] entry of the effects in the
    /// batch. Subsequent batched effects have their entries following linearly
    /// after that one.
    ///
    /// [`GpuSpawnerParams`]: super::GpuSpawnerParams
    pub spawner_base: u32,
    /// The indices within the various indirect dispatch buffers.
    // FIXME - this is per-effect not per-batch
    pub dispatch_buffer_indices: DispatchBufferIndices,
    /// Indirect draw args.
    pub draw_indirect_buffer_row_index: BufferTableId,
    /// Metadata table row index.
    // FIXME - this is per-effect not per-batch
    pub metadata_table_id: BufferTableId,
    /// Particle layout shared by all batched effects and groups.
    pub particle_layout: ParticleLayout,
    /// Flags describing the render layout.
    pub layout_flags: LayoutFlags,
    /// Asset ID of the effect mesh to draw.
    pub mesh: AssetId<Mesh>,
    /// Texture layout.
    pub texture_layout: TextureLayout,
    /// Textures.
    pub textures: Vec<Handle<Image>>,
    /// Alpha mode.
    pub alpha_mode: AlphaMode,
    /// Entities holding the source [`ParticleEffect`] instances which were
    /// batched into this single batch. Used to determine visibility per view.
    ///
    /// [`ParticleEffect`]: crate::ParticleEffect
    pub entities: Vec<u32>,
    pub cached_effect_events: Option<CachedEffectEvents>,
    pub sort_fill_indirect_dispatch_index: Option<u32>,
}

#[derive(Debug, Clone, Copy)]
pub(crate) struct EffectBatchIndex(pub u32);

#[derive(Debug, Default, Resource)]
pub(crate) struct SortedEffectBatches {
    /// Effect batches in the order they were inserted by [`push()`], indexed by
    /// the returned [`EffectBatchIndex`].
    ///
    /// [`push()`]: Self::push
    batches: Vec<EffectBatch>,
    /// Index of the dispatch queue used for indirect fill dispatch and
    /// submitted to [`GpuBufferOperations`].
    pub(super) dispatch_queue_index: Option<u32>,
}

impl SortedEffectBatches {
    pub fn clear(&mut self) {
        self.batches.clear();
        self.dispatch_queue_index = None;
    }

    pub fn push(&mut self, effect_batch: EffectBatch) -> EffectBatchIndex {
        let index = self.batches.len() as u32;
        self.batches.push(effect_batch);
        EffectBatchIndex(index)
    }

    #[allow(dead_code)]
    pub fn len(&self) -> usize {
        self.batches.len()
    }

    pub fn is_empty(&self) -> bool {
        self.batches.is_empty()
    }

    /// Get an iterator over the sorted sequence of effect batches.
    #[inline]
    pub fn iter(&self) -> &[EffectBatch] {
        &self.batches
    }

    pub fn get(&self, index: EffectBatchIndex) -> Option<&EffectBatch> {
        if index.0 < self.batches.len() as u32 {
            Some(&self.batches[index.0 as usize])
        } else {
            None
        }
    }
}

/// Information that the [`EffectSorter`] maintains in order to sort each
/// effect into the proper order.
pub(crate) struct EffectToBeSorted {
    /// The render-world entity of the effect.
    pub(crate) entity: Entity,
    /// The index of the buffer that the indirect indices for this effect are
    /// stored in.
    pub(crate) slab_id: SlabId,
    /// The offset within the buffer described above at which the indirect
    /// indices for this effect start.
    ///
    /// This is in elements, not bytes.
    pub(crate) base_instance: u32,
}

/// The key that we sort effects by for optimum batching.
#[derive(Clone, Copy, PartialEq, PartialOrd, Eq, Ord)]
struct EffectSortKey {
    /// The level in the dependency graph.
    ///
    /// Parents always have lower levels than their children.
    level: u32,
    /// The index of the buffer that the indirect indices for this effect are
    /// stored in.
    slab_id: SlabId,
    /// The offset within the buffer described above at which the indirect
    /// indices for this effect start.
    base_instance: u32,
}

/// Sorts effects into the proper order for batching.
///
/// This places parents before children and also tries to place effects in the
/// same slab together.
pub(crate) struct EffectSorter {
    /// Information that we keep about each effect.
    pub effects: Vec<EffectToBeSorted>,
    /// A mapping from a child to its parent, if it has one.
    pub child_to_parent: EntityHashMap<Entity>,
}

impl EffectSorter {
    /// Creates a new [`EffectSorter`].
    pub fn new() -> EffectSorter {
        EffectSorter {
            effects: vec![],
            child_to_parent: default(),
        }
    }

    /// Insert an effect to be sorted.
    pub fn insert(
        &mut self,
        entity: Entity,
        slab_id: SlabId,
        base_instance: u32,
        parent: Option<Entity>,
    ) {
        self.effects.push(EffectToBeSorted {
            entity,
            slab_id,
            base_instance,
        });
        if let Some(parent) = parent {
            self.child_to_parent.insert(entity, parent);
        }
    }

    /// Sorts all the effects into the optimal order for batching.
    pub fn sort(&mut self) {
        // trace!("Sorting {} effects...", self.effects.len());
        // for effect in &self.effects {
        //     trace!(
        //         "+ {}: slab={:?} base_instance={:?}",
        //         effect.entity,
        //         effect.slab_id,
        //         effect.base_instance
        //     );
        // }
        // trace!("child->parent:");
        // for (k, v) in &self.child_to_parent {
        //     trace!("+ c[{k}] -> p[{v}]");
        // }

        // First, create a map of entity to index.
        let mut entity_to_index = EntityHashMap::default();
        for (index, effect) in self.effects.iter().enumerate() {
            entity_to_index.insert(effect.entity, index);
        }

        // Next, create a map of children to their parents.
        let mut children_to_parent: Vec<_> = (0..self.effects.len()).map(|_| vec![]).collect();
        for (kid, parent) in self.child_to_parent.iter() {
            let (parent_index, kid_index) = (entity_to_index[parent], entity_to_index[kid]);
            children_to_parent[kid_index].push(parent_index);
        }

        // Now topologically sort the graph. Create an ordering that places
        // children before parents.
        // https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
        let mut ordering = vec![0; self.effects.len()];
        let mut visiting = FixedBitSet::with_capacity(self.effects.len());
        let mut visited = FixedBitSet::with_capacity(self.effects.len());
        while let Some(effect_index) = visited.zeroes().next() {
            visit(
                &mut ordering,
                &mut visiting,
                &mut visited,
                &children_to_parent,
                effect_index,
            );
        }

        // Compute levels.
        let mut levels = vec![0; self.effects.len()];
        for effect_index in ordering.into_iter().rev() {
            let level = levels[effect_index];
            for &parent in &children_to_parent[effect_index] {
                levels[parent] = levels[parent].max(level + 1);
            }
        }

        // Now sort the result.
        self.effects.sort_unstable_by_key(|effect| EffectSortKey {
            level: levels[entity_to_index[&effect.entity]],
            slab_id: effect.slab_id,
            base_instance: effect.base_instance,
        });

        // Helper function for topologically sorting the effect dependency graph
        fn visit(
            ordering: &mut Vec<usize>,
            visiting: &mut FixedBitSet,
            visited: &mut FixedBitSet,
            children_to_parent: &[Vec<usize>],
            effect_index: usize,
        ) {
            if visited.contains(effect_index) {
                return;
            }
            debug_assert!(
                !visiting.contains(effect_index),
                "Parent-child effect relation contains a cycle"
            );

            visiting.insert(effect_index);

            for &parent in &children_to_parent[effect_index] {
                visit(ordering, visiting, visited, children_to_parent, parent);
            }

            visited.insert(effect_index);
            ordering.push(effect_index);
        }
    }
}

/// Single effect batch to drive rendering.
///
/// This component is spawned into the render world during the prepare phase
/// ([`prepare_effects()`]), once per effect batch per group. In turns it
/// references an [`EffectBatch`] component containing all the shared data for
/// all the groups of the effect.
#[derive(Debug, Component)]
pub(crate) struct EffectDrawBatch {
    /// Index of the [`EffectBatch`] in the [`SortedEffectBatches`] this draw
    /// batch is part of.
    ///
    /// Note: currently there's a 1:1 mapping between effect batch and draw
    /// batch.
    pub effect_batch_index: EffectBatchIndex,
    /// Position of the emitter so we can compute distance to camera.
    pub translation: Vec3,
    /// The main-world entity that contains this effect.
    #[allow(dead_code)]
    pub main_entity: MainEntity,
}

impl EffectBatch {
    /// Create a new batch from a single input.
    pub fn from_input(
        main_entity: Entity,
        extracted_effect: &ExtractedEffect,
        extracted_spawner: &ExtractedSpawner,
        cached_mesh: &ExtractedEffectMesh,
        cached_effect_events: Option<&CachedEffectEvents>,
        cached_child_info: Option<&CachedChildInfo>,
        input: &mut BatchInput,
        dispatch_buffer_indices: DispatchBufferIndices,
        draw_indirect_buffer_row_index: BufferTableId,
        metadata_table_id: BufferTableId,
        property_key: Option<PropertyBindGroupKey>,
        property_offset: Option<u32>,
    ) -> EffectBatch {
        assert_eq!(property_key.is_some(), property_offset.is_some());
        assert_eq!(
            input.event_buffer_index.is_some(),
            input.init_indirect_dispatch_index.is_some()
        );

        let spawn_info = if let Some(event_buffer_index) = input.event_buffer_index {
            BatchSpawnInfo::GpuSpawner {
                init_indirect_dispatch_index: input.init_indirect_dispatch_index.unwrap(),
                event_buffer_index,
            }
        } else {
            BatchSpawnInfo::CpuSpawner {
                total_spawn_count: extracted_spawner.spawn_count,
            }
        };

        EffectBatch {
            handle: extracted_effect.handle.clone(),
            slab_id: input.effect_slice.slab_id,
            slice: input.effect_slice.slice.clone(),
            spawn_info,
            init_and_update_pipeline_ids: input.init_and_update_pipeline_ids,
            render_shader: extracted_effect.effect_shaders.render.clone(),
            parent_slab_id: input.parent_slab_id,
            parent_min_binding_size: cached_child_info
                .map(|cci| cci.parent_particle_layout.min_binding_size32()),
            parent_binding_source: cached_child_info
                .map(|cci| cci.parent_buffer_binding_source.clone()),
            child_event_buffers: input.child_effects.clone(),
            property_key,
            property_offset,
            spawner_base: input.spawner_index,
            particle_layout: input.effect_slice.particle_layout.clone(),
            dispatch_buffer_indices,
            draw_indirect_buffer_row_index,
            metadata_table_id,
            layout_flags: extracted_effect.layout_flags,
            mesh: cached_mesh.mesh,
            texture_layout: extracted_effect.texture_layout.clone(),
            textures: extracted_effect.textures.clone(),
            alpha_mode: extracted_effect.alpha_mode,
            entities: vec![main_entity.index()],
            cached_effect_events: cached_effect_events.cloned(),
            sort_fill_indirect_dispatch_index: None, // set later as needed
        }
    }
}

/// Effect batching input, obtained from extracted effects.
#[derive(Debug, Component)]
pub(crate) struct BatchInput {
    /// Effect slices.
    pub effect_slice: EffectSlice,
    /// Compute pipeline IDs of the specialized and cached pipelines.
    pub init_and_update_pipeline_ids: InitAndUpdatePipelineIds,
    /// ID of the particle slab of the parent effect, if any.
    pub parent_slab_id: Option<SlabId>,
    /// Index of the event buffer, if this effect consumes GPU spawn events.
    pub event_buffer_index: Option<u32>,
    /// Child effects, if any.
    pub child_effects: Vec<(Entity, BufferBindingSource)>,

    /// Index of the [`GpuSpawnerParams`] in the
    /// [`EffectsCache::spawner_buffer`].
    pub spawner_index: u32,
    /// Index of the init indirect dispatch struct, if any.
    // FIXME - Contains a single effect's data; should handle multiple ones.
    pub init_indirect_dispatch_index: Option<u32>,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub(crate) struct InitAndUpdatePipelineIds {
    pub init: CachedComputePipelineId,
    pub update: CachedComputePipelineId,
}

#[cfg(test)]
mod tests {
    use bevy::ecs::entity::Entity;

    use super::*;

    fn insert_entry(
        sorter: &mut EffectSorter,
        entity: Entity,
        slab_id: SlabId,
        base_instance: u32,
        parent: Option<Entity>,
    ) {
        sorter.effects.push(EffectToBeSorted {
            entity,
            base_instance,
            slab_id,
        });
        if let Some(parent) = parent {
            sorter.child_to_parent.insert(entity, parent);
        }
    }

    #[test]
    fn toposort_batches() {
        let mut sorter = EffectSorter::new();

        // Some "parent" effect
        let e1 = Entity::from_raw(1);
        insert_entry(&mut sorter, e1, SlabId::new(42), 0, None);
        assert_eq!(sorter.effects.len(), 1);
        assert_eq!(sorter.effects[0].entity, e1);
        assert!(sorter.child_to_parent.is_empty());

        // Some "child" effect in a different buffer
        let e2 = Entity::from_raw(2);
        insert_entry(&mut sorter, e2, SlabId::new(5), 30, Some(e1));
        assert_eq!(sorter.effects.len(), 2);
        assert_eq!(sorter.effects[0].entity, e1);
        assert_eq!(sorter.effects[1].entity, e2);
        assert_eq!(sorter.child_to_parent.len(), 1);
        assert_eq!(sorter.child_to_parent[&e2], e1);

        sorter.sort();
        assert_eq!(sorter.effects.len(), 2);
        assert_eq!(sorter.effects[0].entity, e2); // child first
        assert_eq!(sorter.effects[1].entity, e1); // parent after
        assert_eq!(sorter.child_to_parent.len(), 1); // unchanged
        assert_eq!(sorter.child_to_parent[&e2], e1); // unchanged

        // Some "child" effect in the same buffer as its parent
        let e3 = Entity::from_raw(3);
        insert_entry(&mut sorter, e3, SlabId::new(42), 20, Some(e1));
        assert_eq!(sorter.effects.len(), 3);
        assert_eq!(sorter.effects[0].entity, e2); // from previous sort
        assert_eq!(sorter.effects[1].entity, e1); // from previous sort
        assert_eq!(sorter.effects[2].entity, e3); // simply appended
        assert_eq!(sorter.child_to_parent.len(), 2);
        assert_eq!(sorter.child_to_parent[&e2], e1);
        assert_eq!(sorter.child_to_parent[&e3], e1);

        sorter.sort();
        assert_eq!(sorter.effects.len(), 3);
        assert_eq!(sorter.effects[0].entity, e2); // child first
        assert_eq!(sorter.effects[1].entity, e3); // other child next (in same buffer as parent)
        assert_eq!(sorter.effects[2].entity, e1); // finally, parent
        assert_eq!(sorter.child_to_parent.len(), 2);
        assert_eq!(sorter.child_to_parent[&e2], e1);
        assert_eq!(sorter.child_to_parent[&e3], e1);
    }
}

1	use std::{fmt::Debug, num::NonZeroU32, ops::Range};
2
3	use bevy::{
4	ecs::entity::EntityHashMap,
5	prelude::*,
6	render::{render_resource::CachedComputePipelineId, sync_world::MainEntity},
7	};
8	use fixedbitset::FixedBitSet;
9
10	use super::{
11	effect_cache::{DispatchBufferIndices, EffectSlice},
12	event::{CachedChildInfo, CachedEffectEvents},
13	BufferBindingSource, ExtractedEffectMesh, LayoutFlags, PropertyBindGroupKey,
14	};
15	use crate::{
16	render::{
17	buffer_table::BufferTableId, effect_cache::SlabId, ExtractedEffect, ExtractedSpawner,
18	},
19	AlphaMode, EffectAsset, ParticleLayout, TextureLayout,
20	};
21
22	#[derive(Debug, Clone, Copy)]
23	pub(crate) enum BatchSpawnInfo {
24	/// Spawn a number of particles uploaded from CPU each frame.
25	CpuSpawner {
26	/// Total number of particles to spawn for the batch. This is only used
27	/// to calculate the number of compute workgroups to dispatch.
28	total_spawn_count: u32,
29	},
30
31	/// Spawn a number of particles calculated on GPU from "spawn events", which
32	/// generally emitted by another effect.
33	GpuSpawner {
34	/// Index into the init indirect dispatch buffer of the
35	/// [`GpuDispatchIndirect`] instance for this batch.
36	///
37	/// [`GpuDispatchIndirect`]: super::GpuDispatchIndirect
38	init_indirect_dispatch_index: u32,
39	/// Index of the [`EventBuffer`] where the GPU spawn events consumed by
40	/// this batch are stored.
41	///
42	/// [`EventBuffer`]: super::event::EventBuffer
43	#[allow(dead_code)]
44	event_buffer_index: u32,
45	},
46	}
47
48	/// Batch of effects dispatched and rendered together.
49	#[derive(Debug, Clone)]
50	pub(crate) struct EffectBatch {
51	/// Handle of the underlying effect asset describing the effect.
52	pub handle: Handle<EffectAsset>,
53	/// ID of the particle slab in the [`EffectBuffer`] where all the batched
54	/// effects are stored.
55	///
56	/// [`EffectBuffer`]: super::effect_cache::EffectBuffer
57	pub slab_id: SlabId,
58	/// Slice of particles in the GPU effect buffer referenced by
59	/// [`EffectBatch::slab_id`].
60	pub slice: Range<u32>,
61	/// Spawn info for this batch
62	pub spawn_info: BatchSpawnInfo,
63	/// Specialized init and update compute pipelines.
64	pub init_and_update_pipeline_ids: InitAndUpdatePipelineIds,
65	/// Configured shader used for the particle rendering of this group.
66	/// Note that we don't need to keep the init/update shaders alive because
67	/// their pipeline specialization is doing it via the specialization key.
68	pub render_shader: Handle<Shader>,
69	/// ID of the particle slab where the parent effect is stored, if any. If a
70	/// parent exists, its particle buffer is made available (read-only) for
71	/// a child effect to read its attributes.
72	pub parent_slab_id: Option<SlabId>,
73	pub parent_min_binding_size: Option<NonZeroU32>,
74	pub parent_binding_source: Option<BufferBindingSource>,
75	/// Event buffers of child effects, if any.
76	pub child_event_buffers: Vec<(Entity, BufferBindingSource)>,
77	/// Index of the property buffer, if any.
78	pub property_key: Option<PropertyBindGroupKey>,
79	/// Offset in bytes into the property buffer where the Property struct is
80	/// located for this effect.
81	// FIXME: This is a per-instance value which prevents batching :(
82	pub property_offset: Option<u32>,
83	/// Index of the first [`GpuSpawnerParams`] entry of the effects in the
84	/// batch. Subsequent batched effects have their entries following linearly
85	/// after that one.
86	///
87	/// [`GpuSpawnerParams`]: super::GpuSpawnerParams
88	pub spawner_base: u32,
89	/// The indices within the various indirect dispatch buffers.
90	// FIXME - this is per-effect not per-batch
91	pub dispatch_buffer_indices: DispatchBufferIndices,
92	/// Indirect draw args.
93	pub draw_indirect_buffer_row_index: BufferTableId,
94	/// Metadata table row index.
95	// FIXME - this is per-effect not per-batch
96	pub metadata_table_id: BufferTableId,
97	/// Particle layout shared by all batched effects and groups.
98	pub particle_layout: ParticleLayout,
99	/// Flags describing the render layout.
100	pub layout_flags: LayoutFlags,
101	/// Asset ID of the effect mesh to draw.
102	pub mesh: AssetId<Mesh>,
103	/// Texture layout.
104	pub texture_layout: TextureLayout,
105	/// Textures.
106	pub textures: Vec<Handle<Image>>,
107	/// Alpha mode.
108	pub alpha_mode: AlphaMode,
109	/// Entities holding the source [`ParticleEffect`] instances which were
110	/// batched into this single batch. Used to determine visibility per view.
111	///
112	/// [`ParticleEffect`]: crate::ParticleEffect
113	pub entities: Vec<u32>,
114	pub cached_effect_events: Option<CachedEffectEvents>,
115	pub sort_fill_indirect_dispatch_index: Option<u32>,
116	}
117
118	#[derive(Debug, Clone, Copy)]
119	pub(crate) struct EffectBatchIndex(pub u32);
120
121	#[derive(Debug, Default, Resource)]
122	pub(crate) struct SortedEffectBatches {
123	/// Effect batches in the order they were inserted by [`push()`], indexed by
124	/// the returned [`EffectBatchIndex`].
125	///
126	/// [`push()`]: Self::push
127	batches: Vec<EffectBatch>,
128	/// Index of the dispatch queue used for indirect fill dispatch and
129	/// submitted to [`GpuBufferOperations`].
130	pub(super) dispatch_queue_index: Option<u32>,
131	}
132
133	impl SortedEffectBatches {
134	pub fn clear(&mut self) {	1,030✔
135	self.batches.clear();	2,060✔
136	self.dispatch_queue_index = None;	1,030✔
137	}
138
139	pub fn push(&mut self, effect_batch: EffectBatch) -> EffectBatchIndex {	1,012✔
140	let index = self.batches.len() as u32;	2,024✔
141	self.batches.push(effect_batch);	3,036✔
142	EffectBatchIndex(index)	1,012✔
143	}
144
145	#[allow(dead_code)]
UNCOV 146	pub fn len(&self) -> usize {	×
UNCOV 147	self.batches.len()	×
148	}
149
150	pub fn is_empty(&self) -> bool {	1,030✔
151	self.batches.is_empty()	2,060✔
152	}
153
154	/// Get an iterator over the sorted sequence of effect batches.
155	#[inline]
156	pub fn iter(&self) -> &[EffectBatch] {	4,048✔
157	&self.batches	4,048✔
158	}
159
160	pub fn get(&self, index: EffectBatchIndex) -> Option<&EffectBatch> {	4,047✔
161	if index.0 < self.batches.len() as u32 {	8,094✔
162	Some(&self.batches[index.0 as usize])	4,047✔
163	} else {
164	None	×
165	}
166	}
167	}
168
169	/// Information that the [`EffectSorter`] maintains in order to sort each
170	/// effect into the proper order.
171	pub(crate) struct EffectToBeSorted {
172	/// The render-world entity of the effect.
173	pub(crate) entity: Entity,
174	/// The index of the buffer that the indirect indices for this effect are
175	/// stored in.
176	pub(crate) slab_id: SlabId,
177	/// The offset within the buffer described above at which the indirect
178	/// indices for this effect start.
179	///
180	/// This is in elements, not bytes.
181	pub(crate) base_instance: u32,
182	}
183
184	/// The key that we sort effects by for optimum batching.
185	#[derive(Clone, Copy, PartialEq, PartialOrd, Eq, Ord)]
186	struct EffectSortKey {
187	/// The level in the dependency graph.
188	///
189	/// Parents always have lower levels than their children.
190	level: u32,
191	/// The index of the buffer that the indirect indices for this effect are
192	/// stored in.
193	slab_id: SlabId,
194	/// The offset within the buffer described above at which the indirect
195	/// indices for this effect start.
196	base_instance: u32,
197	}
198
199	/// Sorts effects into the proper order for batching.
200	///
201	/// This places parents before children and also tries to place effects in the
202	/// same slab together.
203	pub(crate) struct EffectSorter {
204	/// Information that we keep about each effect.
205	pub effects: Vec<EffectToBeSorted>,
206	/// A mapping from a child to its parent, if it has one.
207	pub child_to_parent: EntityHashMap<Entity>,
208	}
209
210	impl EffectSorter {
211	/// Creates a new [`EffectSorter`].
212	pub fn new() -> EffectSorter {	1,031✔
213	EffectSorter {
214	effects: vec![],	1,031✔
215	child_to_parent: default(),	1,031✔
216	}
217	}
218
219	/// Insert an effect to be sorted.
220	pub fn insert(	1,012✔
221	&mut self,
222	entity: Entity,
223	slab_id: SlabId,
224	base_instance: u32,
225	parent: Option<Entity>,
226	) {
227	self.effects.push(EffectToBeSorted {	3,036✔
228	entity,	2,024✔
229	slab_id,	1,012✔
230	base_instance,	1,012✔
231	});
232	if let Some(parent) = parent {	1,012✔
233	self.child_to_parent.insert(entity, parent);
234	}
235	}
236
237	/// Sorts all the effects into the optimal order for batching.
238	pub fn sort(&mut self) {	1,032✔
239	// trace!("Sorting {} effects...", self.effects.len());
240	// for effect in &self.effects {
241	// trace!(
242	// "+ {}: slab={:?} base_instance={:?}",
243	// effect.entity,
244	// effect.slab_id,
245	// effect.base_instance
246	// );
247	// }
248	// trace!("child->parent:");
249	// for (k, v) in &self.child_to_parent {
250	// trace!("+ c[{k}] -> p[{v}]");
251	// }
252
253	// First, create a map of entity to index.
254	let mut entity_to_index = EntityHashMap::default();	2,064✔
255	for (index, effect) in self.effects.iter().enumerate() {	3,081✔
256	entity_to_index.insert(effect.entity, index);
257	}
258
259	// Next, create a map of children to their parents.
260	let mut children_to_parent: Vec<_> = (0..self.effects.len()).map(\|_\| vec![]).collect();	5,160✔
261	for (kid, parent) in self.child_to_parent.iter() {	2,067✔
262	let (parent_index, kid_index) = (entity_to_index[parent], entity_to_index[kid]);
263	children_to_parent[kid_index].push(parent_index);
264	}
265
266	// Now topologically sort the graph. Create an ordering that places
267	// children before parents.
268	// https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
269	let mut ordering = vec![0; self.effects.len()];	4,128✔
270	let mut visiting = FixedBitSet::with_capacity(self.effects.len());	4,128✔
271	let mut visited = FixedBitSet::with_capacity(self.effects.len());	4,128✔
272	while let Some(effect_index) = visited.zeroes().next() {	3,064✔
273	visit(
274	&mut ordering,
275	&mut visiting,
276	&mut visited,
277	&children_to_parent,
278	effect_index,
279	);
280	}
281
282	// Compute levels.
283	let mut levels = vec![0; self.effects.len()];	4,128✔
284	for effect_index in ordering.into_iter().rev() {	5,130✔
285	let level = levels[effect_index];
286	for &parent in &children_to_parent[effect_index] {	6✔
287	levels[parent] = levels[parent].max(level + 1);
288	}
289	}
290
291	// Now sort the result.
292	self.effects.sort_unstable_by_key(\|effect\| EffectSortKey {	2,064✔
293	level: levels[entity_to_index[&effect.entity]],	16✔
294	slab_id: effect.slab_id,	8✔
295	base_instance: effect.base_instance,	8✔
296	});
297
298	// Helper function for topologically sorting the effect dependency graph
299	fn visit(	1,019✔
300	ordering: &mut Vec<usize>,
301	visiting: &mut FixedBitSet,
302	visited: &mut FixedBitSet,
303	children_to_parent: &[Vec<usize>],
304	effect_index: usize,
305	) {
306	if visited.contains(effect_index) {	3,057✔
307	return;	2✔
308	}
309	debug_assert!(
310	!visiting.contains(effect_index),
NEW 311	"Parent-child effect relation contains a cycle"	×
312	);
313
314	visiting.insert(effect_index);	3,051✔
315
316	for &parent in &children_to_parent[effect_index] {	1,020✔
317	visit(ordering, visiting, visited, children_to_parent, parent);
318	}
319
320	visited.insert(effect_index);	3,051✔
321	ordering.push(effect_index);	3,051✔
322	}
323	}
324	}
325
326	/// Single effect batch to drive rendering.
327	///
328	/// This component is spawned into the render world during the prepare phase
329	/// ([`prepare_effects()`]), once per effect batch per group. In turns it
330	/// references an [`EffectBatch`] component containing all the shared data for
331	/// all the groups of the effect.
332	#[derive(Debug, Component)]
333	pub(crate) struct EffectDrawBatch {
334	/// Index of the [`EffectBatch`] in the [`SortedEffectBatches`] this draw
335	/// batch is part of.
336	///
337	/// Note: currently there's a 1:1 mapping between effect batch and draw
338	/// batch.
339	pub effect_batch_index: EffectBatchIndex,
340	/// Position of the emitter so we can compute distance to camera.
341	pub translation: Vec3,
342	/// The main-world entity that contains this effect.
343	#[allow(dead_code)]
344	pub main_entity: MainEntity,
345	}
346
347	impl EffectBatch {
348	/// Create a new batch from a single input.
349	pub fn from_input(	1,012✔
350	main_entity: Entity,
351	extracted_effect: &ExtractedEffect,
352	extracted_spawner: &ExtractedSpawner,
353	cached_mesh: &ExtractedEffectMesh,
354	cached_effect_events: Option<&CachedEffectEvents>,
355	cached_child_info: Option<&CachedChildInfo>,
356	input: &mut BatchInput,
357	dispatch_buffer_indices: DispatchBufferIndices,
358	draw_indirect_buffer_row_index: BufferTableId,
359	metadata_table_id: BufferTableId,
360	property_key: Option<PropertyBindGroupKey>,
361	property_offset: Option<u32>,
362	) -> EffectBatch {
363	assert_eq!(property_key.is_some(), property_offset.is_some());	5,060✔
364	assert_eq!(	1,012✔
365	input.event_buffer_index.is_some(),	2,024✔
366	input.init_indirect_dispatch_index.is_some()	2,024✔
367	);
368
369	let spawn_info = if let Some(event_buffer_index) = input.event_buffer_index {	2,024✔
370	BatchSpawnInfo::GpuSpawner {
371	init_indirect_dispatch_index: input.init_indirect_dispatch_index.unwrap(),
372	event_buffer_index,
373	}
374	} else {
375	BatchSpawnInfo::CpuSpawner {
376	total_spawn_count: extracted_spawner.spawn_count,	1,012✔
377	}
378	};
379
380	EffectBatch {
381	handle: extracted_effect.handle.clone(),	2,024✔
382	slab_id: input.effect_slice.slab_id,	1,012✔
383	slice: input.effect_slice.slice.clone(),	2,024✔
384	spawn_info,
385	init_and_update_pipeline_ids: input.init_and_update_pipeline_ids,	1,012✔
386	render_shader: extracted_effect.effect_shaders.render.clone(),	2,024✔
387	parent_slab_id: input.parent_slab_id,	1,012✔
388	parent_min_binding_size: cached_child_info	1,012✔
389	.map(\|cci\| cci.parent_particle_layout.min_binding_size32()),
390	parent_binding_source: cached_child_info	1,012✔
391	.map(\|cci\| cci.parent_buffer_binding_source.clone()),
392	child_event_buffers: input.child_effects.clone(),	2,024✔
393	property_key,
394	property_offset,
395	spawner_base: input.spawner_index,	1,012✔
396	particle_layout: input.effect_slice.particle_layout.clone(),	2,024✔
397	dispatch_buffer_indices,
398	draw_indirect_buffer_row_index,
399	metadata_table_id,
400	layout_flags: extracted_effect.layout_flags,	1,012✔
401	mesh: cached_mesh.mesh,	1,012✔
402	texture_layout: extracted_effect.texture_layout.clone(),	2,024✔
403	textures: extracted_effect.textures.clone(),	2,024✔
404	alpha_mode: extracted_effect.alpha_mode,	1,012✔
405	entities: vec![main_entity.index()],	3,036✔
406	cached_effect_events: cached_effect_events.cloned(),	2,024✔
407	sort_fill_indirect_dispatch_index: None, // set later as needed
408	}
409	}
410	}
411
412	/// Effect batching input, obtained from extracted effects.
413	#[derive(Debug, Component)]
414	pub(crate) struct BatchInput {
415	/// Effect slices.
416	pub effect_slice: EffectSlice,
417	/// Compute pipeline IDs of the specialized and cached pipelines.
418	pub init_and_update_pipeline_ids: InitAndUpdatePipelineIds,
419	/// ID of the particle slab of the parent effect, if any.
420	pub parent_slab_id: Option<SlabId>,
421	/// Index of the event buffer, if this effect consumes GPU spawn events.
422	pub event_buffer_index: Option<u32>,
423	/// Child effects, if any.
424	pub child_effects: Vec<(Entity, BufferBindingSource)>,
425
426	/// Index of the [`GpuSpawnerParams`] in the
427	/// [`EffectsCache::spawner_buffer`].
428	pub spawner_index: u32,
429	/// Index of the init indirect dispatch struct, if any.
430	// FIXME - Contains a single effect's data; should handle multiple ones.
431	pub init_indirect_dispatch_index: Option<u32>,
432	}
433
434	#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
435	pub(crate) struct InitAndUpdatePipelineIds {
436	pub init: CachedComputePipelineId,
437	pub update: CachedComputePipelineId,
438	}
439
440	#[cfg(test)]
441	mod tests {
442	use bevy::ecs::entity::Entity;
443
444	use super::*;
445
446	fn insert_entry(
447	sorter: &mut EffectSorter,
448	entity: Entity,
449	slab_id: SlabId,
450	base_instance: u32,
451	parent: Option<Entity>,
452	) {
453	sorter.effects.push(EffectToBeSorted {
454	entity,
455	base_instance,
456	slab_id,
457	});
458	if let Some(parent) = parent {
459	sorter.child_to_parent.insert(entity, parent);
460	}
461	}
462
463	#[test]
464	fn toposort_batches() {
465	let mut sorter = EffectSorter::new();
466
467	// Some "parent" effect
468	let e1 = Entity::from_raw(1);
469	insert_entry(&mut sorter, e1, SlabId::new(42), 0, None);
470	assert_eq!(sorter.effects.len(), 1);
471	assert_eq!(sorter.effects[0].entity, e1);
472	assert!(sorter.child_to_parent.is_empty());
473
474	// Some "child" effect in a different buffer
475	let e2 = Entity::from_raw(2);
476	insert_entry(&mut sorter, e2, SlabId::new(5), 30, Some(e1));
477	assert_eq!(sorter.effects.len(), 2);
478	assert_eq!(sorter.effects[0].entity, e1);
479	assert_eq!(sorter.effects[1].entity, e2);
480	assert_eq!(sorter.child_to_parent.len(), 1);
481	assert_eq!(sorter.child_to_parent[&e2], e1);
482
483	sorter.sort();
484	assert_eq!(sorter.effects.len(), 2);
485	assert_eq!(sorter.effects[0].entity, e2); // child first
486	assert_eq!(sorter.effects[1].entity, e1); // parent after
487	assert_eq!(sorter.child_to_parent.len(), 1); // unchanged
488	assert_eq!(sorter.child_to_parent[&e2], e1); // unchanged
489
490	// Some "child" effect in the same buffer as its parent
491	let e3 = Entity::from_raw(3);
492	insert_entry(&mut sorter, e3, SlabId::new(42), 20, Some(e1));
493	assert_eq!(sorter.effects.len(), 3);
494	assert_eq!(sorter.effects[0].entity, e2); // from previous sort
495	assert_eq!(sorter.effects[1].entity, e1); // from previous sort
496	assert_eq!(sorter.effects[2].entity, e3); // simply appended
497	assert_eq!(sorter.child_to_parent.len(), 2);
498	assert_eq!(sorter.child_to_parent[&e2], e1);
499	assert_eq!(sorter.child_to_parent[&e3], e1);
500
501	sorter.sort();
502	assert_eq!(sorter.effects.len(), 3);
503	assert_eq!(sorter.effects[0].entity, e2); // child first
504	assert_eq!(sorter.effects[1].entity, e3); // other child next (in same buffer as parent)
505	assert_eq!(sorter.effects[2].entity, e1); // finally, parent
506	assert_eq!(sorter.child_to_parent.len(), 2);
507	assert_eq!(sorter.child_to_parent[&e2], e1);
508	assert_eq!(sorter.child_to_parent[&e3], e1);
509	}
510	}

djeedai / bevy_hanabi / 18243240671

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous