21565578469

Committed 01 Feb 2026 03:38PM UTC coverage: 58.351% (-8.1%) from 66.442%

Build # 21565578469

Build Type

push

github

Committed by

web-flow

Commit Message

Update to Bevy v0.18 (#521)

Thanks to @morgenthum for the original work.

Run Details

93 of 170 new or added lines in 6 files covered. (54.71%)

968 existing lines in 17 files now uncovered.

4954 of 8490 relevant lines covered (58.35%)

190.51 hits per line

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

93.42

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

djeedai / bevy_hanabi / 21565578469

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