13640457354

Committed 03 Mar 2025 09:09PM UTC coverage: 40.055% (-6.7%) from 46.757%

Build # 13640457354

Build Type

push

github

Committed by

web-flow

Commit Message

Hierarchical effects and GPU spawn event (#424)

This change introduces hierarchical effects, the ability of an effect to
be parented to another effect through the `EffectParent` component.
Child effects can inherit attributes from their parent when spawned
during the init pass, but are otherwise independent effects. They
replace the old group system, which is entirely removed. The parent
effect can emit GPU spawn events, which are consumed by the child effect
to spawn particles instead of the traditional CPU spawn count. Those GPU
spawn events currently are just the ID of the parent particles, to allow
read-only access to its attribute in _e.g._ the new
`InheritAttributeModifier`.

The ribbon/trail system is also reworked. The atomic linked list based
on `Attribute::PREV` and `Attribute::NEXT` is abandoned, and replaced
with an explicit sort compute pass which orders particles by
`Attribute::RIBBON_ID` first, and `Attribute::AGE` next. The ribbon ID
is any `u32` value unique to each ribbon/trail. Sorting particles by age
inside a given ribbon/trail allows avoiding the edge case where a
particle in the middle of a trail dies, leaving a gap in the list.

A migration guide is provided from v0.14 to the upcoming v0.15 which
will include this change, due to the large change of behavior and APIs.

Run Details

409 of 2997 new or added lines in 17 files covered. (13.65%)

53 existing lines in 11 files now uncovered.

3208 of 8009 relevant lines covered (40.05%)

18.67 hits per line

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

57.61

/src/render/batch.rs

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

#[cfg(feature = "2d")]
use bevy::math::FloatOrd;
use bevy::{
    prelude::*,
    render::{
        render_resource::{BufferId, CachedComputePipelineId},
        sync_world::MainEntity,
    },
    utils::HashMap,
};

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>,
    /// Index of the buffer of the parent effect, if any. If a parent exists,
    /// its particle buffer is made available (read-only) for a child effect to
    /// read its attributes.
    pub parent_buffer_index: Option<u32>,
    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>,
    /// GPU buffer storing the [`mesh`] of the effect.
    ///
    /// [`mesh`]: Self::mesh
    pub mesh_buffer_id: BufferId,
    /// Slice inside the GPU buffer for the effect mesh.
    pub mesh_slice: Range<u32>,
    /// 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);

pub(crate) struct SortedEffectBatchesIter<'a> {
    batches: &'a [EffectBatch],
    sorted_indices: &'a [u32],
    next: u32,
}

impl<'a> SortedEffectBatchesIter<'a> {
    pub fn new(source: &'a SortedEffectBatches) -> Self {
        assert_eq!(source.batches.len(), source.sorted_indices.len());
        Self {
            batches: &source.batches[..],
            sorted_indices: &source.sorted_indices[..],
            next: 0,
        }
    }
}

impl<'a> Iterator for SortedEffectBatchesIter<'a> {
    type Item = &'a EffectBatch;

    fn next(&mut self) -> Option<Self::Item> {
        if self.next < self.sorted_indices.len() as u32 {
            let index = self.sorted_indices[self.next as usize];
            let batch = &self.batches[index as usize];
            self.next += 1;
            Some(batch)
        } else {
            None
        }
    }
}

impl ExactSizeIterator for SortedEffectBatchesIter<'_> {
    fn len(&self) -> usize {
        self.sorted_indices.len()
    }
}

#[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>,
    /// Indices into [`batches`] defining the sorted order batches need to be
    /// processed in. Calcualted by [`sort()`].
    ///
    /// [`batches`]: Self::batches
    /// [`sort()`]: Self::sort
    sorted_indices: Vec<u32>,
}

impl SortedEffectBatches {
    pub fn clear(&mut self) {
        self.batches.clear();
        self.sorted_indices.clear();
    }

    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) -> SortedEffectBatchesIter {
        assert_eq!(
            self.batches.len(),
            self.sorted_indices.len(),
            "Invalid sorted size. Did you call sort() beforehand?"
        );
        SortedEffectBatchesIter::new(self)
    }

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

    /// Sort the effect batches.
    pub fn sort(&mut self) {
        self.sorted_indices.clear();
        self.sorted_indices.reserve_exact(self.batches.len());

        // Kahn’s algorithm for topological sorting.

        // Note: we sort by particle buffer index. In theory with batching this is
        // incorrect, because a parent and child could be batched together in the same
        // buffer, in the wrong order. However currently batching is broken and we
        // allocate one effect instance per buffer, so this works. Ideally we'd take
        // care of sorting earlier during batching.

        // Build a map from buffer index to batch index.
        let batch_index_from_buffer_index = self
            .batches
            .iter()
            .enumerate()
            .map(|(index, effect_batch)| (effect_batch.buffer_index, index))
            .collect::<HashMap<_, _>>();
        // In theory with batching we could have multiple batches referencing the same
        // buffer if we failed to batch some effect instances together which
        // otherwise share a same particle buffer. In practice this currently doesn't
        // happen because batching is disabled, so we always create one buffer
        // per effect instance. But this will need to be fixed later.
        assert_eq!(
            batch_index_from_buffer_index.len(),
            self.batches.len(),
            "FIXME: Duplicate buffer index in batches. This is not implemented yet."
        );

        // Build a map from the batch index of a child to the batch index of its
        // parent.
        let mut parent_batch_index_from_batch_index = HashMap::with_capacity(self.batches.len());
        for (batch_index, effect_batch) in self.batches.iter().enumerate() {
            if let Some(parent_buffer_index) = effect_batch.parent_buffer_index {
                let parent_batch_index = batch_index_from_buffer_index
                    .get(&parent_buffer_index)
                    .unwrap();
                parent_batch_index_from_batch_index.insert(batch_index as u32, *parent_batch_index);
            }
        }

        // Store the number of children per batch; we need to decrement it below
        // HACK - during tests we don't want to create Buffers so grab the count another
        // (slower) way
        #[cfg(test)]
        let mut child_count = {
            let mut counts = vec![0; self.batches.len()];
            for (_, parent_batch_index) in &parent_batch_index_from_batch_index {
                counts[*parent_batch_index] += 1;
            }
            counts
        };
        #[cfg(not(test))]
        let mut child_count = self
            .batches
            .iter()
            .map(|effect_batch| effect_batch.child_event_buffers.len() as u32)
            .collect::<Vec<_>>();

        // Insert in queue all effects without any child
        let mut queue = VecDeque::new();
        for (batch_index, count) in child_count.iter().enumerate() {
            if *count == 0 {
                queue.push_back(batch_index as u32);
            }
        }

        // Process queue
        while let Some(batch_index) = queue.pop_front() {
            // The batch has no unprocessed child, so it can be inserted in the final result
            assert!(child_count[batch_index as usize] == 0);
            self.sorted_indices.push(batch_index);

            // If it has a parent, that parent has one less child to be processed, so is one
            // step closer to being inserted itself in the final result.
            let Some(parent_batch_index) = parent_batch_index_from_batch_index.get(&batch_index)
            else {
                continue;
            };
            assert!(child_count[*parent_batch_index] > 0);
            child_count[*parent_batch_index] -= 1;

            // If this was the last child effect of that parent, then the parent is ready
            // and can be inserted itself.
            if child_count[*parent_batch_index] == 0 {
                queue.push_back(*parent_batch_index as u32);
            }
        }

        assert_eq!(
            self.sorted_indices.len(),
            self.batches.len(),
            "Cycle detected in effects"
        );
    }
}

/// 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,
    /// For 2D rendering, the Z coordinate used as the sort key. Ignored for 3D
    /// rendering.
    #[cfg(feature = "2d")]
    pub z_sort_key_2d: FloatOrd,
    /// For 3d rendering, the position of the emitter so we can compute distance
    /// to camera. Ignored for 2D rendering.
    #[cfg(feature = "3d")]
    pub translation_3d: Vec3,
}

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_buffer_index: input.parent_buffer_index,
            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_base,
            particle_layout: input.effect_slice.particle_layout.clone(),
            dispatch_buffer_indices,
            layout_flags: input.layout_flags,
            mesh: cached_mesh.mesh,
            mesh_buffer_id: cached_mesh.buffer.id(),
            mesh_slice: cached_mesh.range.clone(),
            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 buffer of the parent effect, if any.
    pub parent_buffer_index: Option<u32>,
    /// 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_base: u32,
    /// Number of particles to spawn for this effect.
    pub spawn_count: u32,
    /// Emitter position, for 3D sorting.
    #[cfg(feature = "3d")]
    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>,
    /// Sort key, for 2D only.
    #[cfg(feature = "2d")]
    pub z_sort_key_2d: FloatOrd,
}

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

#[cfg(test)]
mod tests {
    use super::*;

    fn make_batch(buffer_index: u32, parent_buffer_index: Option<u32>) -> EffectBatch {
        EffectBatch {
            handle: default(),
            buffer_index,
            slice: 0..0,
            spawn_info: BatchSpawnInfo::CpuSpawner {
                total_spawn_count: 0,
            },
            init_and_update_pipeline_ids: InitAndUpdatePipelineIds {
                init: CachedComputePipelineId::INVALID,
                update: CachedComputePipelineId::INVALID,
            },
            render_shader: default(),
            parent_buffer_index,
            parent_min_binding_size: default(),
            parent_binding_source: default(),
            child_event_buffers: default(),
            property_key: default(),
            property_offset: default(),
            spawner_base: default(),
            dispatch_buffer_indices: default(),
            particle_layout: ParticleLayout::empty(),
            layout_flags: LayoutFlags::NONE,
            mesh: default(),
            mesh_buffer_id: NonZeroU32::new(1).unwrap().into(),
            mesh_slice: 0..0,
            texture_layout: default(),
            textures: default(),
            alpha_mode: default(),
            entities: default(),
            cached_effect_events: default(),
            sort_fill_indirect_dispatch_index: default(),
        }
    }

    #[test]
    fn toposort_batches() {
        let mut seb = SortedEffectBatches::default();
        assert!(seb.is_empty());
        assert_eq!(seb.len(), 0);

        seb.push(make_batch(42, None));
        assert!(!seb.is_empty());
        assert_eq!(seb.len(), 1);

        seb.push(make_batch(5, Some(42)));
        assert!(!seb.is_empty());
        assert_eq!(seb.len(), 2);

        seb.sort();
        assert!(!seb.is_empty());
        assert_eq!(seb.len(), 2);
        let sorted_batches = seb.iter().collect::<Vec<_>>();
        assert_eq!(sorted_batches.len(), 2);
        assert_eq!(sorted_batches[0].buffer_index, 5);
        assert_eq!(sorted_batches[1].buffer_index, 42);

        seb.push(make_batch(6, Some(42)));
        assert!(!seb.is_empty());
        assert_eq!(seb.len(), 3);

        seb.sort();
        assert!(!seb.is_empty());
        assert_eq!(seb.len(), 3);
        let sorted_batches = seb.iter().collect::<Vec<_>>();
        assert_eq!(sorted_batches.len(), 3);
        assert_eq!(sorted_batches[0].buffer_index, 5);
        assert_eq!(sorted_batches[1].buffer_index, 6);
        assert_eq!(sorted_batches[2].buffer_index, 42);

        seb.push(make_batch(55, Some(5)));
        assert!(!seb.is_empty());
        assert_eq!(seb.len(), 4);

        seb.sort();
        assert!(!seb.is_empty());
        assert_eq!(seb.len(), 4);
        let sorted_batches = seb.iter().collect::<Vec<_>>();
        assert_eq!(sorted_batches.len(), 4);
        assert_eq!(sorted_batches[0].buffer_index, 6);
        assert_eq!(sorted_batches[1].buffer_index, 55);
        assert_eq!(sorted_batches[2].buffer_index, 5);
        assert_eq!(sorted_batches[3].buffer_index, 42);
    }
}

1	use std::{collections::VecDeque, fmt::Debug, num::NonZeroU32, ops::Range};
2
3	#[cfg(feature = "2d")]
4	use bevy::math::FloatOrd;
5	use bevy::{
6	prelude::*,
7	render::{
8	render_resource::{BufferId, CachedComputePipelineId},
9	sync_world::MainEntity,
10	},
11	utils::HashMap,
12	};
13
14	use super::{
15	effect_cache::{DispatchBufferIndices, EffectSlice},
16	event::{CachedChildInfo, CachedEffectEvents},
17	BufferBindingSource, CachedMesh, LayoutFlags, PropertyBindGroupKey,
18	};
19	use crate::{AlphaMode, EffectAsset, EffectShader, ParticleLayout, TextureLayout};
20
21	#[derive(Debug, Clone, Copy)]
22	pub(crate) enum BatchSpawnInfo {
23	/// Spawn a number of particles uploaded from CPU each frame.
24	CpuSpawner {
25	/// Total number of particles to spawn for the batch. This is only used
26	/// to calculate the number of compute workgroups to dispatch.
27	total_spawn_count: u32,
28	},
29
30	/// Spawn a number of particles calculated on GPU from "spawn events", which
31	/// generally emitted by another effect.
32	GpuSpawner {
33	/// Index into the init indirect dispatch buffer of the
34	/// [`GpuDispatchIndirect`] instance for this batch.
35	///
36	/// [`GpuDispatchIndirect`]: super::GpuDispatchIndirect
37	init_indirect_dispatch_index: u32,
38	/// Index of the [`EventBuffer`] where the GPU spawn events consumed by
39	/// this batch are stored.
40	///
41	/// [`EventBuffer`]: super::event::EventBuffer
42	#[allow(dead_code)]
43	event_buffer_index: u32,
44	},
45	}
46
47	/// Batch of effects dispatched and rendered together.
48	#[derive(Debug, Clone)]
49	pub(crate) struct EffectBatch {
50	/// Handle of the underlying effect asset describing the effect.
51	pub handle: Handle<EffectAsset>,
52	/// Index of the [`EffectBuffer`].
53	///
54	/// [`EffectBuffer`]: super::effect_cache::EffectBuffer
55	pub buffer_index: u32,
56	/// Slice of particles in the GPU effect buffer referenced by
57	/// [`EffectBatch::buffer_index`].
58	pub slice: Range<u32>,
59	/// Spawn info for this batch
60	pub spawn_info: BatchSpawnInfo,
61	/// Specialized init and update compute pipelines.
62	pub init_and_update_pipeline_ids: InitAndUpdatePipelineIds,
63	/// Configured shader used for the particle rendering of this group.
64	/// Note that we don't need to keep the init/update shaders alive because
65	/// their pipeline specialization is doing it via the specialization key.
66	pub render_shader: Handle<Shader>,
67	/// Index of the buffer of the parent effect, if any. If a parent exists,
68	/// its particle buffer is made available (read-only) for a child effect to
69	/// read its attributes.
70	pub parent_buffer_index: Option<u32>,
71	pub parent_min_binding_size: Option<NonZeroU32>,
72	pub parent_binding_source: Option<BufferBindingSource>,
73	/// Event buffers of child effects, if any.
74	pub child_event_buffers: Vec<(Entity, BufferBindingSource)>,
75	/// Index of the property buffer, if any.
76	pub property_key: Option<PropertyBindGroupKey>,
77	/// Offset in bytes into the property buffer where the Property struct is
78	/// located for this effect.
79	// FIXME: This is a per-instance value which prevents batching :(
80	pub property_offset: Option<u32>,
81	/// Index of the first [`GpuSpawnerParams`] entry of the effects in the
82	/// batch. Subsequent batched effects have their entries following linearly
83	/// after that one.
84	///
85	/// [`GpuSpawnerParams`]: super::GpuSpawnerParams
86	pub spawner_base: u32,
87	/// The indices within the various indirect dispatch buffers.
88	pub dispatch_buffer_indices: DispatchBufferIndices,
89	/// Particle layout shared by all batched effects and groups.
90	pub particle_layout: ParticleLayout,
91	/// Flags describing the render layout.
92	pub layout_flags: LayoutFlags,
93	/// Asset ID of the effect mesh to draw.
94	pub mesh: AssetId<Mesh>,
95	/// GPU buffer storing the [`mesh`] of the effect.
96	///
97	/// [`mesh`]: Self::mesh
98	pub mesh_buffer_id: BufferId,
99	/// Slice inside the GPU buffer for the effect mesh.
100	pub mesh_slice: Range<u32>,
101	/// Texture layout.
102	pub texture_layout: TextureLayout,
103	/// Textures.
104	pub textures: Vec<Handle<Image>>,
105	/// Alpha mode.
106	pub alpha_mode: AlphaMode,
107	/// Entities holding the source [`ParticleEffect`] instances which were
108	/// batched into this single batch. Used to determine visibility per view.
109	///
110	/// [`ParticleEffect`]: crate::ParticleEffect
111	pub entities: Vec<u32>,
112	pub cached_effect_events: Option<CachedEffectEvents>,
113	pub sort_fill_indirect_dispatch_index: Option<u32>,
114	}
115
116	#[derive(Debug, Clone, Copy)]
117	pub(crate) struct EffectBatchIndex(pub u32);
118
119	pub(crate) struct SortedEffectBatchesIter<'a> {
120	batches: &'a [EffectBatch],
121	sorted_indices: &'a [u32],
122	next: u32,
123	}
124
125	impl<'a> SortedEffectBatchesIter<'a> {
126	pub fn new(source: &'a SortedEffectBatches) -> Self {	3✔
127	assert_eq!(source.batches.len(), source.sorted_indices.len());	3✔
128	Self {
129	batches: &source.batches[..],	3✔
130	sorted_indices: &source.sorted_indices[..],	3✔
131	next: 0,
132	}
133	}
134	}
135
136	impl<'a> Iterator for SortedEffectBatchesIter<'a> {
137	type Item = &'a EffectBatch;
138
139	fn next(&mut self) -> Option<Self::Item> {	12✔
140	if self.next < self.sorted_indices.len() as u32 {	12✔
141	let index = self.sorted_indices[self.next as usize];	9✔
142	let batch = &self.batches[index as usize];	9✔
143	self.next += 1;	9✔
144	Some(batch)	9✔
145	} else {
146	None	3✔
147	}
148	}
149	}
150
151	impl ExactSizeIterator for SortedEffectBatchesIter<'_> {
NEW 152	fn len(&self) -> usize {	×
NEW 153	self.sorted_indices.len()	×
154	}
155	}
156
157	#[derive(Debug, Default, Resource)]
158	pub(crate) struct SortedEffectBatches {
159	/// Effect batches in the order they were inserted by [`push()`], indexed by
160	/// the returned [`EffectBatchIndex`].
161	///
162	/// [`push()`]: Self::push
163	batches: Vec<EffectBatch>,
164	/// Indices into [`batches`] defining the sorted order batches need to be
165	/// processed in. Calcualted by [`sort()`].
166	///
167	/// [`batches`]: Self::batches
168	/// [`sort()`]: Self::sort
169	sorted_indices: Vec<u32>,
170	}
171
172	impl SortedEffectBatches {
NEW 173	pub fn clear(&mut self) {	×
NEW 174	self.batches.clear();	×
NEW 175	self.sorted_indices.clear();	×
176	}
177
178	pub fn push(&mut self, effect_batch: EffectBatch) -> EffectBatchIndex {	4✔
179	let index = self.batches.len() as u32;	4✔
180	self.batches.push(effect_batch);	4✔
181	EffectBatchIndex(index)	4✔
182	}
183
184	#[allow(dead_code)]
185	pub fn len(&self) -> usize {	8✔
186	self.batches.len()	8✔
187	}
188
189	pub fn is_empty(&self) -> bool {	8✔
190	self.batches.is_empty()	8✔
191	}
192
193	/// Get an iterator over the sorted sequence of effect batches.
194	#[inline]
195	pub fn iter(&self) -> SortedEffectBatchesIter {	3✔
196	assert_eq!(	3✔
197	self.batches.len(),	3✔
198	self.sorted_indices.len(),	3✔
NEW 199	"Invalid sorted size. Did you call sort() beforehand?"	×
200	);
201	SortedEffectBatchesIter::new(self)	3✔
202	}
203
NEW 204	pub fn get(&self, index: EffectBatchIndex) -> Option<&EffectBatch> {	×
NEW 205	if index.0 < self.batches.len() as u32 {	×
NEW 206	Some(&self.batches[index.0 as usize])	×
207	} else {
NEW 208	None	×
209	}
210	}
211
212	/// Sort the effect batches.
213	pub fn sort(&mut self) {	3✔
214	self.sorted_indices.clear();	3✔
215	self.sorted_indices.reserve_exact(self.batches.len());	3✔
216
217	// Kahn’s algorithm for topological sorting.
218
219	// Note: we sort by particle buffer index. In theory with batching this is
220	// incorrect, because a parent and child could be batched together in the same
221	// buffer, in the wrong order. However currently batching is broken and we
222	// allocate one effect instance per buffer, so this works. Ideally we'd take
223	// care of sorting earlier during batching.
224
225	// Build a map from buffer index to batch index.
226	let batch_index_from_buffer_index = self	3✔
227	.batches	3✔
228	.iter()
229	.enumerate()
230	.map(\|(index, effect_batch)\| (effect_batch.buffer_index, index))	15✔
231	.collect::<HashMap<_, _>>();
232	// In theory with batching we could have multiple batches referencing the same
233	// buffer if we failed to batch some effect instances together which
234	// otherwise share a same particle buffer. In practice this currently doesn't
235	// happen because batching is disabled, so we always create one buffer
236	// per effect instance. But this will need to be fixed later.
237	assert_eq!(	3✔
238	batch_index_from_buffer_index.len(),	3✔
239	self.batches.len(),	3✔
NEW 240	"FIXME: Duplicate buffer index in batches. This is not implemented yet."	×
241	);
242
243	// Build a map from the batch index of a child to the batch index of its
244	// parent.
245	let mut parent_batch_index_from_batch_index = HashMap::with_capacity(self.batches.len());	3✔
246	for (batch_index, effect_batch) in self.batches.iter().enumerate() {	12✔
247	if let Some(parent_buffer_index) = effect_batch.parent_buffer_index {	15✔
248	let parent_batch_index = batch_index_from_buffer_index
249	.get(&parent_buffer_index)
250	.unwrap();
251	parent_batch_index_from_batch_index.insert(batch_index as u32, *parent_batch_index);
252	}
253	}
254
255	// Store the number of children per batch; we need to decrement it below
256	// HACK - during tests we don't want to create Buffers so grab the count another
257	// (slower) way
258	#[cfg(test)]
259	let mut child_count = {
260	let mut counts = vec![0; self.batches.len()];
261	for (_, parent_batch_index) in &parent_batch_index_from_batch_index {
262	counts[*parent_batch_index] += 1;
263	}
264	counts
265	};
266	#[cfg(not(test))]
267	let mut child_count = self	3✔
268	.batches	3✔
269	.iter()
270	.map(\|effect_batch\| effect_batch.child_event_buffers.len() as u32)	3✔
271	.collect::<Vec<_>>();
272
273	// Insert in queue all effects without any child
274	let mut queue = VecDeque::new();	3✔
275	for (batch_index, count) in child_count.iter().enumerate() {	12✔
276	if *count == 0 {	14✔
277	queue.push_back(batch_index as u32);	5✔
278	}
279	}
280
281	// Process queue
282	while let Some(batch_index) = queue.pop_front() {	21✔
283	// The batch has no unprocessed child, so it can be inserted in the final result
284	assert!(child_count[batch_index as usize] == 0);
285	self.sorted_indices.push(batch_index);	9✔
286
287	// If it has a parent, that parent has one less child to be processed, so is one
288	// step closer to being inserted itself in the final result.
289	let Some(parent_batch_index) = parent_batch_index_from_batch_index.get(&batch_index)	6✔
290	else {
291	continue;	3✔
292	};
293	assert!(child_count[*parent_batch_index] > 0);
294	child_count[*parent_batch_index] -= 1;	6✔
295
296	// If this was the last child effect of that parent, then the parent is ready
297	// and can be inserted itself.
298	if child_count[*parent_batch_index] == 0 {	10✔
299	queue.push_back(*parent_batch_index as u32);	4✔
300	}
301	}
302
303	assert_eq!(	3✔
304	self.sorted_indices.len(),	3✔
305	self.batches.len(),	3✔
NEW 306	"Cycle detected in effects"	×
307	);
308	}
309	}
310
311	/// Single effect batch to drive rendering.
312	///
313	/// This component is spawned into the render world during the prepare phase
314	/// ([`prepare_effects()`]), once per effect batch per group. In turns it
315	/// references an [`EffectBatch`] component containing all the shared data for
316	/// all the groups of the effect.
317	#[derive(Debug, Component)]
318	pub(crate) struct EffectDrawBatch {
319	/// Index of the [`EffectBatch`] in the [`SortedEffectBatches`] this draw
320	/// batch is part of.
321	///
322	/// Note: currently there's a 1:1 mapping between effect batch and draw
323	/// batch.
324	pub effect_batch_index: EffectBatchIndex,
325	/// For 2D rendering, the Z coordinate used as the sort key. Ignored for 3D
326	/// rendering.
327	#[cfg(feature = "2d")]
328	pub z_sort_key_2d: FloatOrd,
329	/// For 3d rendering, the position of the emitter so we can compute distance
330	/// to camera. Ignored for 2D rendering.
331	#[cfg(feature = "3d")]
332	pub translation_3d: Vec3,
333	}
334
335	impl EffectBatch {
336	/// Create a new batch from a single input.
337	pub fn from_input(	×
338	cached_mesh: &CachedMesh,
339	cached_effect_events: Option<&CachedEffectEvents>,
340	cached_child_info: Option<&CachedChildInfo>,
341	input: &mut BatchInput,
342	dispatch_buffer_indices: DispatchBufferIndices,
343	property_key: Option<PropertyBindGroupKey>,
344	property_offset: Option<u32>,
345	) -> EffectBatch {
346	assert_eq!(property_key.is_some(), property_offset.is_some());	×
NEW 347	assert_eq!(	×
NEW 348	input.event_buffer_index.is_some(),	×
NEW 349	input.init_indirect_dispatch_index.is_some()	×
350	);
351
NEW 352	let spawn_info = if let Some(event_buffer_index) = input.event_buffer_index {	×
353	BatchSpawnInfo::GpuSpawner {
354	init_indirect_dispatch_index: input.init_indirect_dispatch_index.unwrap(),
355	event_buffer_index,
356	}
357	} else {
358	BatchSpawnInfo::CpuSpawner {
NEW 359	total_spawn_count: input.spawn_count,	×
360	}
361	};
362
363	EffectBatch {
NEW 364	handle: input.handle.clone(),	×
NEW 365	buffer_index: input.effect_slice.buffer_index,	×
NEW 366	slice: input.effect_slice.slice.clone(),	×
367	spawn_info,
NEW 368	init_and_update_pipeline_ids: input.init_and_update_pipeline_ids,	×
NEW 369	render_shader: input.shaders.render.clone(),	×
NEW 370	parent_buffer_index: input.parent_buffer_index,	×
NEW 371	parent_min_binding_size: cached_child_info	×
372	.map(\|cci\| cci.parent_particle_layout.min_binding_size32()),
NEW 373	parent_binding_source: cached_child_info	×
374	.map(\|cci\| cci.parent_buffer_binding_source.clone()),
NEW 375	child_event_buffers: input.child_effects.clone(),	×
376	property_key,
377	property_offset,
NEW 378	spawner_base: input.spawner_base,	×
NEW 379	particle_layout: input.effect_slice.particle_layout.clone(),	×
380	dispatch_buffer_indices,
UNCOV 381	layout_flags: input.layout_flags,	×
382	mesh: cached_mesh.mesh,	×
NEW 383	mesh_buffer_id: cached_mesh.buffer.id(),	×
384	mesh_slice: cached_mesh.range.clone(),	×
385	texture_layout: input.texture_layout.clone(),	×
386	textures: input.textures.clone(),	×
387	alpha_mode: input.alpha_mode,	×
388	entities: vec![input.main_entity.id().index()],	×
NEW 389	cached_effect_events: cached_effect_events.cloned(),	×
390	sort_fill_indirect_dispatch_index: None, // set later as needed
391	}
392	}
393	}
394
395	/// Effect batching input, obtained from extracted effects.
396	#[derive(Debug, Component)]
397	pub(crate) struct BatchInput {
398	/// Handle of the underlying effect asset describing the effect.
399	pub handle: Handle<EffectAsset>,
400	/// Main entity of the [`ParticleEffect`], used for visibility.
401	pub main_entity: MainEntity,
402	/// Render entity of the [`CachedEffect`].
403	#[allow(dead_code)]
404	pub entity: Entity,
405	/// Effect slices.
406	pub effect_slice: EffectSlice,
407	/// Compute pipeline IDs of the specialized and cached pipelines.
408	pub init_and_update_pipeline_ids: InitAndUpdatePipelineIds,
409	/// Index of the buffer of the parent effect, if any.
410	pub parent_buffer_index: Option<u32>,
411	/// Index of the event buffer, if this effect consumes GPU spawn events.
412	pub event_buffer_index: Option<u32>,
413	/// Child effects, if any.
414	pub child_effects: Vec<(Entity, BufferBindingSource)>,
415	/// Various flags related to the effect.
416	pub layout_flags: LayoutFlags,
417	/// Texture layout.
418	pub texture_layout: TextureLayout,
419	/// Textures.
420	pub textures: Vec<Handle<Image>>,
421	/// Alpha mode.
422	pub alpha_mode: AlphaMode,
423	#[allow(dead_code)]
424	pub particle_layout: ParticleLayout,
425	/// Effect shaders.
426	pub shaders: EffectShader,
427	/// Index of the [`GpuSpawnerParams`] in the
428	/// [`EffectsCache::spawner_buffer`].
429	pub spawner_base: u32,
430	/// Number of particles to spawn for this effect.
431	pub spawn_count: u32,
432	/// Emitter position, for 3D sorting.
433	#[cfg(feature = "3d")]
434	pub position: Vec3,
435	/// Index of the init indirect dispatch struct, if any.
436	// FIXME - Contains a single effect's data; should handle multiple ones.
437	pub init_indirect_dispatch_index: Option<u32>,
438	/// Sort key, for 2D only.
439	#[cfg(feature = "2d")]
440	pub z_sort_key_2d: FloatOrd,
441	}
442
443	#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
444	pub(crate) struct InitAndUpdatePipelineIds {
445	pub init: CachedComputePipelineId,
446	pub update: CachedComputePipelineId,
447	}
448
449	#[cfg(test)]
450	mod tests {
451	use super::*;
452
453	fn make_batch(buffer_index: u32, parent_buffer_index: Option<u32>) -> EffectBatch {
454	EffectBatch {
455	handle: default(),
456	buffer_index,
457	slice: 0..0,
458	spawn_info: BatchSpawnInfo::CpuSpawner {
459	total_spawn_count: 0,
460	},
461	init_and_update_pipeline_ids: InitAndUpdatePipelineIds {
462	init: CachedComputePipelineId::INVALID,
463	update: CachedComputePipelineId::INVALID,
464	},
465	render_shader: default(),
466	parent_buffer_index,
467	parent_min_binding_size: default(),
468	parent_binding_source: default(),
469	child_event_buffers: default(),
470	property_key: default(),
471	property_offset: default(),
472	spawner_base: default(),
473	dispatch_buffer_indices: default(),
474	particle_layout: ParticleLayout::empty(),
475	layout_flags: LayoutFlags::NONE,
476	mesh: default(),
477	mesh_buffer_id: NonZeroU32::new(1).unwrap().into(),
478	mesh_slice: 0..0,
479	texture_layout: default(),
480	textures: default(),
481	alpha_mode: default(),
482	entities: default(),
483	cached_effect_events: default(),
484	sort_fill_indirect_dispatch_index: default(),
485	}
486	}
487
488	#[test]
489	fn toposort_batches() {
490	let mut seb = SortedEffectBatches::default();
491	assert!(seb.is_empty());
492	assert_eq!(seb.len(), 0);
493
494	seb.push(make_batch(42, None));
495	assert!(!seb.is_empty());
496	assert_eq!(seb.len(), 1);
497
498	seb.push(make_batch(5, Some(42)));
499	assert!(!seb.is_empty());
500	assert_eq!(seb.len(), 2);
501
502	seb.sort();
503	assert!(!seb.is_empty());
504	assert_eq!(seb.len(), 2);
505	let sorted_batches = seb.iter().collect::<Vec<_>>();
506	assert_eq!(sorted_batches.len(), 2);
507	assert_eq!(sorted_batches[0].buffer_index, 5);
508	assert_eq!(sorted_batches[1].buffer_index, 42);
509
510	seb.push(make_batch(6, Some(42)));
511	assert!(!seb.is_empty());
512	assert_eq!(seb.len(), 3);
513
514	seb.sort();
515	assert!(!seb.is_empty());
516	assert_eq!(seb.len(), 3);
517	let sorted_batches = seb.iter().collect::<Vec<_>>();
518	assert_eq!(sorted_batches.len(), 3);
519	assert_eq!(sorted_batches[0].buffer_index, 5);
520	assert_eq!(sorted_batches[1].buffer_index, 6);
521	assert_eq!(sorted_batches[2].buffer_index, 42);
522
523	seb.push(make_batch(55, Some(5)));
524	assert!(!seb.is_empty());
525	assert_eq!(seb.len(), 4);
526
527	seb.sort();
528	assert!(!seb.is_empty());
529	assert_eq!(seb.len(), 4);
530	let sorted_batches = seb.iter().collect::<Vec<_>>();
531	assert_eq!(sorted_batches.len(), 4);
532	assert_eq!(sorted_batches[0].buffer_index, 6);
533	assert_eq!(sorted_batches[1].buffer_index, 55);
534	assert_eq!(sorted_batches[2].buffer_index, 5);
535	assert_eq!(sorted_batches[3].buffer_index, 42);
536	}
537	}

djeedai / bevy_hanabi / 13640457354

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