15813086919

Committed 22 Jun 2025 09:34PM UTC coverage: 66.748% (+0.2%) from 66.537%

Build # 15813086919

Build Type

Pull #480

github

Committed by

web-flow

Commit Message

Merge 2cdfbbc21 into aa073c5e6

Pull Request Pull Request #480: Allow multiple effects to be packed into a single buffer again.

Run Details

133 of 152 new or added lines in 4 files covered. (87.5%)

298 existing lines in 7 files now uncovered.

5191 of 7777 relevant lines covered (66.75%)

357.88 hits per line

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

94.2

/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, CachedMesh, LayoutFlags, PropertyBindGroupKey,
};
use crate::{AlphaMode, EffectAsset, EffectShader, 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>,
    /// Index of the [`EffectBuffer`].
    ///
    /// [`EffectBuffer`]: super::effect_cache::EffectBuffer
    pub buffer_index: u32,
    /// Slice of particles in the GPU effect buffer referenced by
    /// [`EffectBatch::buffer_index`].
    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>,
    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.
    pub dispatch_buffer_indices: DispatchBufferIndices,
    /// 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) -> impl Iterator<Item = &EffectBatch> {
        self.batches.iter()
    }

    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
        }
    }
}

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

/// 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) buffer_index: u32,
    /// 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.
    buffer_index: u32,
    /// The offset within the buffer described above at which the indirect
    /// indices for this effect start.
    base_instance: u32,
}

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

    /// Sorts all the effects into the optimal order for batching.
    pub(crate) fn sort(&mut self) {
        // 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]],
            buffer_index: effect.buffer_index,
            base_instance: effect.base_instance,
        });

        // A 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(
        cached_mesh: &CachedMesh,
        cached_effect_events: Option<&CachedEffectEvents>,
        cached_child_info: Option<&CachedChildInfo>,
        input: &mut BatchInput,
        dispatch_buffer_indices: DispatchBufferIndices,
        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: input.spawn_count,
            }
        };

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

djeedai / bevy_hanabi / 15813086919

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