vello_common/

multi_atlas.rs

// Copyright 2025 the Vello Authors
// SPDX-License-Identifier: Apache-2.0 OR MIT

//! Multi-atlas management for texture atlases.
//!
//! This module provides support for managing multiple texture atlases, allowing for handling of
//! large numbers of images.
//!
//! The allocator backend is [guillotiere](https://github.com/nical/guillotiere)'s tree-based
//! guillotine algorithm, providing O(1) neighbor lookup during deallocation and automatic
//! free-rect coalescing.

use alloc::vec::Vec;
pub use guillotiere::AllocId;
use guillotiere::AtlasAllocator;
use thiserror::Error;

/// The result of a successful rectangle allocation within a single atlas.
#[derive(Debug)]
pub struct Allocation {
    /// Opaque handle used for deallocation.
    pub id: AllocId,
    /// X coordinate of the top-left corner of the allocated rectangle.
    pub x: u32,
    /// Y coordinate of the top-left corner of the allocated rectangle.
    pub y: u32,
}

// ---------------------------------------------------------------------------
// Unified Atlas type
// ---------------------------------------------------------------------------

/// Represents a single atlas in the multi-atlas system.
pub struct Atlas {
    /// Unique identifier for this atlas.
    pub id: AtlasId,
    /// Rectangle allocator backend.
    allocator: AtlasAllocator,
    /// Current usage statistics.
    stats: AtlasUsageStats,
    /// Allocation counter.
    allocation_counter: u32,
}

impl Atlas {
    /// Create a new atlas with the given ID and size.
    pub fn new(id: AtlasId, width: u32, height: u32) -> Self {
        Self {
            id,
            allocator: AtlasAllocator::new(guillotiere::size2(width as i32, height as i32)),
            stats: AtlasUsageStats {
                allocated_area: 0,
                total_area: width * height,
                allocated_count: 0,
            },
            allocation_counter: 0,
        }
    }

    /// Try to allocate an image in this atlas.
    #[expect(
        clippy::cast_sign_loss,
        reason = "coordinates are always non-negative for valid allocations"
    )]
    pub fn allocate(&mut self, width: u32, height: u32) -> Option<Allocation> {
        let alloc = self
            .allocator
            .allocate(guillotiere::size2(width as i32, height as i32))?;
        self.stats.allocated_area += width * height;
        self.stats.allocated_count += 1;
        self.allocation_counter += 1;
        Some(Allocation {
            id: alloc.id,
            x: alloc.rectangle.min.x as u32,
            y: alloc.rectangle.min.y as u32,
        })
    }

    /// Deallocate an image from this atlas.
    pub fn deallocate(&mut self, alloc_id: AllocId, width: u32, height: u32) {
        self.allocator.deallocate(alloc_id);
        self.stats.allocated_area = self.stats.allocated_area.saturating_sub(width * height);
        self.stats.allocated_count = self.stats.allocated_count.saturating_sub(1);
    }

    /// Get current usage statistics.
    pub fn stats(&self) -> &AtlasUsageStats {
        &self.stats
    }
}

impl core::fmt::Debug for Atlas {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_struct("Atlas")
            .field("id", &self.id)
            .field("stats", &self.stats)
            .field("allocation_counter", &self.allocation_counter)
            .finish_non_exhaustive()
    }
}

// ---------------------------------------------------------------------------
// MultiAtlasManager
// ---------------------------------------------------------------------------

/// Manages multiple texture atlases.
pub struct MultiAtlasManager {
    /// All atlases managed by this instance.
    atlases: Vec<Atlas>,
    /// Configuration for atlas management.
    config: AtlasConfig,
    /// Round-robin counter for allocation strategy.
    round_robin_counter: usize,
}

impl MultiAtlasManager {
    /// Create a new multi-atlas manager with the given configuration.
    pub fn new(config: AtlasConfig) -> Self {
        let mut manager = Self {
            atlases: Vec::new(),
            config,
            round_robin_counter: 0,
        };

        for _ in 0..config.initial_atlas_count {
            manager
                .create_atlas()
                .expect("Failed to create initial atlas");
        }

        manager
    }

    /// Get the current configuration.
    pub fn config(&self) -> &AtlasConfig {
        &self.config
    }

    /// Create a new atlas and return its ID.
    pub fn create_atlas(&mut self) -> Result<AtlasId, AtlasError> {
        if self.atlases.len() >= self.config.max_atlases {
            return Err(AtlasError::AtlasLimitReached {
                max_atlases: self.config.max_atlases,
                diagnostics: AtlasSpaceDiagnostics::Unavailable,
            });
        }

        let atlas_id = AtlasId::new(self.next_atlas_id());

        let atlas = Atlas::new(atlas_id, self.config.atlas_size.0, self.config.atlas_size.1);
        self.atlases.push(atlas);

        Ok(atlas_id)
    }

    /// Get the next available atlas ID.
    pub fn next_atlas_id(&self) -> u32 {
        u32::try_from(self.atlases.len()).unwrap()
    }

    /// Try to allocate space for an image with the given dimensions.
    pub fn try_allocate(&mut self, width: u32, height: u32) -> Result<AtlasAllocation, AtlasError> {
        self.try_allocate_excluding(width, height, None)
    }

    /// Try to allocate space for an image with the given dimensions,
    /// optionally excluding a specific atlas.
    pub fn try_allocate_excluding(
        &mut self,
        width: u32,
        height: u32,
        exclude_atlas_id: Option<AtlasId>,
    ) -> Result<AtlasAllocation, AtlasError> {
        // Check if the image is too large for any atlas
        if width > self.config.atlas_size.0 || height > self.config.atlas_size.1 {
            return Err(AtlasError::TextureTooLarge {
                width,
                height,
                max_width: self.config.atlas_size.0,
                max_height: self.config.atlas_size.1,
            });
        }

        // Try allocation based on strategy
        match self.config.allocation_strategy {
            AllocationStrategy::FirstFit => {
                self.allocate_first_fit(width, height, exclude_atlas_id)
            }
            AllocationStrategy::BestFit => self.allocate_best_fit(width, height, exclude_atlas_id),
            AllocationStrategy::LeastUsed => {
                self.allocate_least_used(width, height, exclude_atlas_id)
            }
            AllocationStrategy::RoundRobin => {
                self.allocate_round_robin(width, height, exclude_atlas_id)
            }
        }
    }

    fn space_diagnostics(&self, width: u32, height: u32) -> AtlasSpaceDiagnostics {
        let mut atlases = Vec::new();

        for atlas in &self.atlases {
            let mut free_area = 0_u64;
            let mut free_rectangle_count = 0;
            let mut largest_free_width = 0;
            let mut largest_free_height = 0;
            let mut largest_free_area = 0_u64;
            atlas.allocator.for_each_free_rectangle(|rect| {
                let rect_width = rect.width() as u32;
                let rect_height = rect.height() as u32;
                let rect_area = u64::from(rect_width) * u64::from(rect_height);
                free_area += rect_area;
                free_rectangle_count += 1;

                if rect_area > largest_free_area {
                    largest_free_area = rect_area;
                    largest_free_width = rect_width;
                    largest_free_height = rect_height;
                }
            });

            atlases.push(AtlasLayerDiagnostics {
                atlas_id: atlas.id,
                total_area: u64::from(atlas.stats.total_area),
                free_area,
                free_rectangle_count,
                largest_free_width,
                largest_free_height,
            });
        }

        AtlasSpaceDiagnostics::Allocation {
            width,
            height,
            atlas_width: self.config.atlas_size.0,
            atlas_height: self.config.atlas_size.1,
            max_atlases: self.config.max_atlases,
            atlases,
        }
    }

    fn no_space_available(&self, width: u32, height: u32) -> AtlasError {
        AtlasError::NoSpaceAvailable(self.space_diagnostics(width, height))
    }

    fn atlas_limit_reached(&self, width: u32, height: u32) -> AtlasError {
        AtlasError::AtlasLimitReached {
            max_atlases: self.config.max_atlases,
            diagnostics: self.space_diagnostics(width, height),
        }
    }

    /// Allocate using first-fit strategy: try atlases in order until one has space.
    fn allocate_first_fit(
        &mut self,
        width: u32,
        height: u32,
        exclude_atlas_id: Option<AtlasId>,
    ) -> Result<AtlasAllocation, AtlasError> {
        for atlas in &mut self.atlases {
            if Some(atlas.id) == exclude_atlas_id {
                continue;
            }

            if let Some(allocation) = atlas.allocate(width, height) {
                return Ok(AtlasAllocation {
                    atlas_id: atlas.id,
                    allocation,
                });
            }
        }

        // Try creating a new atlas if auto-grow is enabled
        if self.config.auto_grow {
            let atlas_id = self
                .create_atlas()
                .map_err(|_| self.atlas_limit_reached(width, height))?;
            let atlas = self.atlases.last_mut().unwrap();
            if let Some(allocation) = atlas.allocate(width, height) {
                return Ok(AtlasAllocation {
                    atlas_id,
                    allocation,
                });
            }
        }

        Err(self.no_space_available(width, height))
    }

    /// Allocate using best-fit strategy: choose the atlas with the smallest remaining space that
    /// can fit the image.
    fn allocate_best_fit(
        &mut self,
        width: u32,
        height: u32,
        exclude_atlas_id: Option<AtlasId>,
    ) -> Result<AtlasAllocation, AtlasError> {
        let mut best_atlas_idx = None;
        let mut best_remaining_space = u32::MAX;

        // Find the atlas with the least remaining space that can fit the image
        for (idx, atlas) in self.atlases.iter().enumerate() {
            if Some(atlas.id) == exclude_atlas_id {
                continue;
            }

            let stats = atlas.stats();
            let remaining_space = stats.total_area - stats.allocated_area;

            if remaining_space >= width * height && remaining_space < best_remaining_space {
                best_remaining_space = remaining_space;
                best_atlas_idx = Some(idx);
            }
        }

        if let Some(idx) = best_atlas_idx {
            let atlas = &mut self.atlases[idx];
            if let Some(allocation) = atlas.allocate(width, height) {
                return Ok(AtlasAllocation {
                    atlas_id: atlas.id,
                    allocation,
                });
            }
        }

        // Fallback to first-fit if best-fit didn't work
        self.allocate_first_fit(width, height, exclude_atlas_id)
    }

    /// Allocate using least-used strategy: prefer the atlas with the lowest usage percentage.
    fn allocate_least_used(
        &mut self,
        width: u32,
        height: u32,
        exclude_atlas_id: Option<AtlasId>,
    ) -> Result<AtlasAllocation, AtlasError> {
        let mut best_atlas_idx = None;
        let mut lowest_usage = f32::MAX;

        // Find the atlas with the lowest usage percentage
        for (idx, atlas) in self.atlases.iter().enumerate() {
            if Some(atlas.id) == exclude_atlas_id {
                continue;
            }

            let usage = atlas.stats().usage_percentage();
            if usage < lowest_usage {
                lowest_usage = usage;
                best_atlas_idx = Some(idx);
            }
        }

        if let Some(idx) = best_atlas_idx
            && let Some(allocation) = self.atlases[idx].allocate(width, height)
        {
            let atlas_id = self.atlases[idx].id;
            return Ok(AtlasAllocation {
                atlas_id,
                allocation,
            });
        }

        // Fallback to first-fit if least-used didn't work
        self.allocate_first_fit(width, height, exclude_atlas_id)
    }

    /// Allocate using round-robin strategy: cycle through atlases using a round-robin counter.
    fn allocate_round_robin(
        &mut self,
        width: u32,
        height: u32,
        exclude_atlas_id: Option<AtlasId>,
    ) -> Result<AtlasAllocation, AtlasError> {
        if self.atlases.is_empty() {
            return self.allocate_first_fit(width, height, exclude_atlas_id);
        }

        let start_idx = self.round_robin_counter % self.atlases.len();

        // Try starting from the round-robin position
        for i in 0..self.atlases.len() {
            let idx = (start_idx + i) % self.atlases.len();

            if Some(self.atlases[idx].id) == exclude_atlas_id {
                continue;
            }

            if let Some(allocation) = self.atlases[idx].allocate(width, height) {
                let atlas_id = self.atlases[idx].id;
                self.round_robin_counter = (idx + 1) % self.atlases.len();
                return Ok(AtlasAllocation {
                    atlas_id,
                    allocation,
                });
            }
        }

        // Try creating a new atlas if auto-grow is enabled
        if self.config.auto_grow {
            let atlas_id = self
                .create_atlas()
                .map_err(|_| self.atlas_limit_reached(width, height))?;
            let atlas = self.atlases.last_mut().unwrap();
            if let Some(allocation) = atlas.allocate(width, height) {
                self.round_robin_counter = self.atlases.len() - 1;
                return Ok(AtlasAllocation {
                    atlas_id,
                    allocation,
                });
            }
        }

        Err(self.no_space_available(width, height))
    }

    /// Deallocate space in the specified atlas.
    pub fn deallocate(
        &mut self,
        atlas_id: AtlasId,
        alloc_id: AllocId,
        width: u32,
        height: u32,
    ) -> Result<(), AtlasError> {
        // Since atlases only grow (never deallocate) and id is the index into the atlases vec,
        // we can do a lookup instead of a linear search
        let atlas = self
            .atlases
            .get_mut(atlas_id.0 as usize)
            .ok_or(AtlasError::AtlasNotFound(atlas_id))?;
        atlas.deallocate(alloc_id, width, height);
        Ok(())
    }

    /// Get statistics for all atlases.
    pub fn atlas_stats(&self) -> Vec<(AtlasId, &AtlasUsageStats)> {
        self.atlases
            .iter()
            .map(|atlas| (atlas.id, atlas.stats()))
            .collect()
    }

    /// Get the number of atlases.
    pub fn atlas_count(&self) -> usize {
        self.atlases.len()
    }
}

impl core::fmt::Debug for MultiAtlasManager {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_struct("MultiAtlasManager")
            .field("atlas_count", &self.atlases.len())
            .field("config", &self.config)
            .field("next_atlas_id", &self.next_atlas_id())
            .field("round_robin_counter", &self.round_robin_counter)
            .field("atlases", &self.atlases)
            .finish()
    }
}

/// Errors that can occur during atlas operations.
#[derive(Debug, Clone, Error)]
pub enum AtlasError {
    /// No space available in any atlas.
    #[error("No space available in any atlas{0}")]
    NoSpaceAvailable(AtlasSpaceDiagnostics),
    /// Maximum number of atlases reached.
    #[error("Maximum atlas count reached ({max_atlases}){diagnostics}")]
    AtlasLimitReached {
        /// The configured maximum number of atlases.
        max_atlases: usize,
        /// Details about the failed allocation, when available.
        diagnostics: AtlasSpaceDiagnostics,
    },
    /// The requested texture size is too large for any atlas.
    #[error("Texture too large ({width}x{height}) for atlas (maximum {max_width}x{max_height})")]
    TextureTooLarge {
        /// The width of the requested texture.
        width: u32,
        /// The height of the requested texture.
        height: u32,
        /// The maximum texture width supported by the atlas.
        max_width: u32,
        /// The maximum texture height supported by the atlas.
        max_height: u32,
    },
    /// The specified atlas was not found.
    #[error("Atlas with Id {0:?} not found")]
    AtlasNotFound(AtlasId),
}

/// Free-space details collected after an atlas allocation fails.
#[derive(Clone)]
pub enum AtlasSpaceDiagnostics {
    /// No allocation context is available.
    Unavailable,
    /// Details about the requested allocation and available atlas space.
    Allocation {
        /// The requested allocation width.
        width: u32,
        /// The requested allocation height.
        height: u32,
        /// The width shared by all atlas layers.
        atlas_width: u32,
        /// The height shared by all atlas layers.
        atlas_height: u32,
        /// The configured maximum number of atlas layers.
        max_atlases: usize,
        /// Per-layer details for each atlas considered for the allocation.
        atlases: Vec<AtlasLayerDiagnostics>,
    },
}

impl core::fmt::Debug for AtlasSpaceDiagnostics {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        let Self::Allocation {
            width,
            height,
            atlas_width,
            atlas_height,
            max_atlases,
            atlases,
        } = self
        else {
            return f.write_str("Unavailable");
        };

        f.debug_struct("Allocation")
            .field("requested", &Dimensions(*width, *height))
            .field("layer_size", &Dimensions(*atlas_width, *atlas_height))
            .field("max_atlases", max_atlases)
            .field("atlas_layers", atlases)
            .finish()
    }
}

impl core::fmt::Display for AtlasSpaceDiagnostics {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        let Self::Allocation {
            width,
            height,
            atlas_width: _,
            atlas_height: _,
            max_atlases,
            atlases,
        } = self
        else {
            return Ok(());
        };

        let total_area = atlases.iter().map(|atlas| atlas.total_area).sum::<u64>();
        let free_area = atlases.iter().map(|atlas| atlas.free_area).sum::<u64>();
        let used_percentage = if total_area == 0 {
            0.0
        } else {
            (1.0 - free_area as f64 / total_area as f64) * 100.0
        };
        write!(
            f,
            ": failed to allocate {width}x{height} across {} atlas layers \
             (maximum {max_atlases}; {used_percentage:.1}% used)",
            atlases.len(),
        )
    }
}

/// Free-space details for one atlas texture-array layer.
#[derive(Clone)]
pub struct AtlasLayerDiagnostics {
    /// The atlas represented by this layer.
    pub atlas_id: AtlasId,
    /// The total layer area, in texels.
    pub total_area: u64,
    /// The total free layer area, in texels.
    pub free_area: u64,
    /// The number of disjoint free rectangles in the layer.
    pub free_rectangle_count: usize,
    /// The width of the largest free rectangle by area.
    pub largest_free_width: u32,
    /// The height of the largest free rectangle by area.
    pub largest_free_height: u32,
}

impl AtlasLayerDiagnostics {
    /// Calculate layer utilization as a percentage from 0 to 100.
    pub fn utilization_percentage(&self) -> f64 {
        if self.total_area == 0 {
            0.0
        } else {
            (1.0 - self.free_area as f64 / self.total_area as f64) * 100.0
        }
    }

    /// Calculate layer fragmentation as a percentage from 0 to 100.
    pub fn fragmentation_percentage(&self) -> f64 {
        if self.free_area == 0 {
            0.0
        } else {
            let largest_free_area =
                u64::from(self.largest_free_width) * u64::from(self.largest_free_height);
            (1.0 - largest_free_area as f64 / self.free_area as f64) * 100.0
        }
    }
}

impl core::fmt::Debug for AtlasLayerDiagnostics {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_struct("Layer")
            .field("atlas_id", &self.atlas_id)
            .field("utilization", &Percentage(self.utilization_percentage()))
            .field("capacity", &self.total_area)
            .field("free", &self.free_area)
            .field(
                "largest_free_rectangle",
                &Dimensions(self.largest_free_width, self.largest_free_height),
            )
            .field("free_rectangles", &self.free_rectangle_count)
            .field(
                "fragmentation",
                &Percentage(self.fragmentation_percentage()),
            )
            .finish()
    }
}

struct Dimensions(u32, u32);

impl core::fmt::Debug for Dimensions {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        write!(f, "{}x{}", self.0, self.1)
    }
}

struct Percentage(f64);

impl core::fmt::Debug for Percentage {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        write!(f, "{:.1}%", self.0)
    }
}

/// Unique identifier for an atlas.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct AtlasId(pub u32);

impl AtlasId {
    /// Create a new atlas ID.
    pub fn new(id: u32) -> Self {
        Self(id)
    }

    /// Get the raw ID value.
    pub fn as_u32(self) -> u32 {
        self.0
    }
}

/// Usage statistics for an atlas.
#[derive(Debug, Clone)]
pub struct AtlasUsageStats {
    /// Total allocated area in pixels.
    pub allocated_area: u32,
    /// Total available area in pixels.
    pub total_area: u32,
    /// Number of allocated images.
    pub allocated_count: u32,
}

impl AtlasUsageStats {
    /// Calculate usage percentage (0.0 to 1.0).
    pub fn usage_percentage(&self) -> f32 {
        if self.total_area == 0 {
            0.0
        } else {
            self.allocated_area as f32 / self.total_area as f32
        }
    }
}

/// Result of an atlas allocation attempt.
#[derive(Debug)]
pub struct AtlasAllocation {
    /// The atlas where the allocation was made.
    pub atlas_id: AtlasId,
    /// The allocation details.
    pub allocation: Allocation,
}

/// Configuration for multiple atlas support.
///
/// Note that any values provided here are recommendations and might not be fully
/// honored depending on the capabilities of the backend. For example, if you define
/// the atlas size to be 8192x8192 but the device only supports texture sizes up to 4096x4096,
/// the backend will likely decide to instead use the value that is compatible with the device.
#[derive(Debug, Clone, Copy)]
pub struct AtlasConfig {
    /// Initial number of atlases to create.
    ///
    /// Set this to zero to allocate the first atlas lazily.
    pub initial_atlas_count: usize,
    /// Maximum number of atlases to create.
    pub max_atlases: usize,
    // TODO: Make those u16 instead?
    /// Size of each atlas texture.
    pub atlas_size: (u32, u32),
    /// Whether to automatically create new atlases when needed.
    pub auto_grow: bool,
    /// Strategy for allocating images across atlases.
    pub allocation_strategy: AllocationStrategy,
}

impl Default for AtlasConfig {
    fn default() -> Self {
        Self {
            initial_atlas_count: 0,
            max_atlases: 8,
            atlas_size: (4096, 4096),
            auto_grow: true,
            allocation_strategy: AllocationStrategy::FirstFit,
        }
    }
}

/// Strategy for allocating images across multiple atlases.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum AllocationStrategy {
    /// Try atlases in order until one has space.
    #[default]
    FirstFit,
    /// Choose the atlas with the smallest remaining space that can fit the image.
    BestFit,
    /// Prefer the atlas with the lowest usage percentage.
    LeastUsed,
    /// Cycle through atlases in round-robin fashion.
    RoundRobin,
}

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

    #[test]
    fn test_atlas_creation() {
        let mut manager = MultiAtlasManager::new(AtlasConfig {
            initial_atlas_count: 0,
            ..Default::default()
        });

        let atlas_id = manager.create_atlas().unwrap();
        assert_eq!(atlas_id.as_u32(), 0);
        assert_eq!(manager.atlas_count(), 1);
    }

    #[test]
    fn test_default_lazily_creates_first_atlas() {
        let mut manager = MultiAtlasManager::new(AtlasConfig::default());
        assert_eq!(manager.atlas_count(), 0);

        let allocation = manager.try_allocate(100, 100).unwrap();
        assert_eq!(allocation.atlas_id.as_u32(), 0);
        assert_eq!(manager.atlas_count(), 1);
    }

    #[test]
    fn test_allocation_strategies() {
        let mut manager = MultiAtlasManager::new(AtlasConfig {
            initial_atlas_count: 1,
            max_atlases: 3,
            atlas_size: (256, 256),
            allocation_strategy: AllocationStrategy::FirstFit,
            auto_grow: true,
        });

        // Should create atlas automatically
        let allocation = manager.try_allocate(100, 100).unwrap();
        assert_eq!(allocation.atlas_id.as_u32(), 0);
    }

    #[test]
    fn test_atlas_limit() {
        let mut manager = MultiAtlasManager::new(AtlasConfig {
            initial_atlas_count: 1,
            max_atlases: 1,
            atlas_size: (256, 256),
            allocation_strategy: AllocationStrategy::FirstFit,
            auto_grow: false,
        });

        assert!(matches!(
            manager.create_atlas(),
            Err(AtlasError::AtlasLimitReached {
                max_atlases: 1,
                diagnostics: AtlasSpaceDiagnostics::Unavailable,
            })
        ));
    }

    #[test]
    fn test_no_space_diagnostics() {
        let mut manager = MultiAtlasManager::new(AtlasConfig {
            initial_atlas_count: 1,
            max_atlases: 1,
            atlas_size: (256, 256),
            auto_grow: false,
            ..Default::default()
        });
        manager.try_allocate(128, 256).unwrap();

        let Err(AtlasError::NoSpaceAvailable(AtlasSpaceDiagnostics::Allocation {
            width: 129,
            height: 256,
            atlas_width: 256,
            atlas_height: 256,
            max_atlases: 1,
            atlases,
        })) = manager.try_allocate(129, 256)
        else {
            panic!("expected no-space diagnostics");
        };
        assert_eq!(atlases.len(), 1);
        let atlas = &atlases[0];
        assert_eq!(atlas.atlas_id, AtlasId::new(0));
        assert_eq!(atlas.total_area, 65_536);
        assert_eq!(atlas.free_area, 32_768);
        assert_eq!(atlas.free_rectangle_count, 1);
        assert_eq!(
            (atlas.largest_free_width, atlas.largest_free_height),
            (128, 256)
        );
        assert_eq!(atlas.fragmentation_percentage(), 0.0);
    }

    #[test]
    fn test_atlas_limit_diagnostics() {
        let mut manager = MultiAtlasManager::new(AtlasConfig {
            initial_atlas_count: 1,
            max_atlases: 1,
            atlas_size: (256, 256),
            auto_grow: true,
            ..Default::default()
        });
        manager.try_allocate(128, 256).unwrap();

        let Err(AtlasError::AtlasLimitReached {
            max_atlases: 1,
            diagnostics:
                AtlasSpaceDiagnostics::Allocation {
                    width: 129,
                    height: 256,
                    atlas_width: 256,
                    atlas_height: 256,
                    max_atlases: 1,
                    atlases,
                },
        }) = manager.try_allocate(129, 256)
        else {
            panic!("expected atlas-limit diagnostics");
        };
        assert_eq!(atlases.len(), 1);
    }

    #[test]
    fn test_fragmentation_per_atlas_layer() {
        let atlases = [
            AtlasLayerDiagnostics {
                atlas_id: AtlasId::new(0),
                total_area: 100,
                free_area: 100,
                free_rectangle_count: 1,
                largest_free_width: 10,
                largest_free_height: 10,
            },
            AtlasLayerDiagnostics {
                atlas_id: AtlasId::new(1),
                total_area: 100,
                free_area: 100,
                free_rectangle_count: 2,
                largest_free_width: 5,
                largest_free_height: 10,
            },
        ];

        assert_eq!(atlases[0].fragmentation_percentage(), 0.0);
        assert_eq!(atlases[1].fragmentation_percentage(), 50.0);
    }

    #[test]
    fn test_texture_too_large() {
        let mut manager = MultiAtlasManager::new(AtlasConfig {
            atlas_size: (256, 256),
            ..Default::default()
        });

        let result = manager.try_allocate(300, 300);
        assert!(matches!(
            result,
            Err(AtlasError::TextureTooLarge {
                width: 300,
                height: 300,
                max_width: 256,
                max_height: 256,
            })
        ));
    }

    #[test]
    fn test_first_fit_allocation_strategy() {
        let mut manager = MultiAtlasManager::new(AtlasConfig {
            initial_atlas_count: 3,
            max_atlases: 3,
            atlas_size: (256, 256),
            allocation_strategy: AllocationStrategy::FirstFit,
            auto_grow: false,
        });

        // First allocation should go to atlas 0
        let allocation0 = manager.try_allocate(100, 100).unwrap();
        assert_eq!(allocation0.atlas_id.as_u32(), 0);

        // Second allocation should also go to atlas 0 (first fit)
        let allocation1 = manager.try_allocate(50, 50).unwrap();
        assert_eq!(allocation1.atlas_id.as_u32(), 0);

        // Third allocation should still go to atlas 0 (first fit continues to use same atlas)
        let allocation2 = manager.try_allocate(80, 80).unwrap();
        assert_eq!(allocation2.atlas_id.as_u32(), 0);

        // Try to allocate something very large that definitely won't fit in atlas 0's remaining space
        // This should force it to go to atlas 1
        let allocation3 = manager.try_allocate(200, 200).unwrap();
        assert_eq!(allocation3.atlas_id.as_u32(), 1);

        // Next small allocation should go back to atlas 0 (first fit tries atlas 0 first)
        let allocation4 = manager.try_allocate(20, 20).unwrap();
        assert_eq!(allocation4.atlas_id.as_u32(), 0);
    }

    #[test]
    fn test_best_fit_allocation_strategy() {
        let mut manager = MultiAtlasManager::new(AtlasConfig {
            initial_atlas_count: 3,
            max_atlases: 3,
            atlas_size: (256, 256),
            allocation_strategy: AllocationStrategy::BestFit,
            auto_grow: false,
        });

        // All atlases start empty, so first allocation goes to atlas 0 (first available)
        let allocation0 = manager.try_allocate(150, 150).unwrap();
        assert_eq!(allocation0.atlas_id.as_u32(), 0);

        // Second allocation should also go to atlas 0 since it still has the least remaining space
        // that can fit the image (all atlases have same remaining space, so it picks the first)
        let allocation1 = manager.try_allocate(100, 100).unwrap();
        assert_eq!(allocation1.atlas_id.as_u32(), 0);

        // Now atlas 0 has less remaining space than atlases 1 and 2
        // For a small allocation, it should still go to atlas 0 (best fit - least remaining space)
        let allocation2 = manager.try_allocate(100, 100).unwrap();
        assert_eq!(allocation2.atlas_id.as_u32(), 0);

        // Now try to allocate something very large that won't fit in atlas 0's remaining space
        // This should force it to go to atlas 1 (which has the most remaining space)
        let allocation3 = manager.try_allocate(200, 200).unwrap();
        assert_eq!(allocation3.atlas_id.as_u32(), 1);

        // Now atlas 1 has less remaining space
        // A small allocation should go to atlas 0 as it can
        let allocation4 = manager.try_allocate(80, 80).unwrap();
        assert_eq!(allocation4.atlas_id.as_u32(), 0);

        // Now atlas 1 has less remaining space but it can't fit the allocation
        // It should go to atlas 2 (best fit - least remaining space)
        let allocation5 = manager.try_allocate(80, 80).unwrap();
        assert_eq!(allocation5.atlas_id.as_u32(), 2);
    }

    #[test]
    fn test_least_used_allocation_strategy() {
        let mut manager = MultiAtlasManager::new(AtlasConfig {
            initial_atlas_count: 3,
            max_atlases: 3,
            atlas_size: (256, 256),
            allocation_strategy: AllocationStrategy::LeastUsed,
            auto_grow: false,
        });

        // First allocation goes to atlas 0 (all atlases have 0% usage, picks first)
        let allocation0 = manager.try_allocate(100, 100).unwrap();
        assert_eq!(allocation0.atlas_id.as_u32(), 0);

        // Second allocation should go to atlas 1 (least used among remaining)
        let allocation1 = manager.try_allocate(50, 50).unwrap();
        assert_eq!(allocation1.atlas_id.as_u32(), 1);

        // Third allocation should go to atlas 2 (least used)
        let allocation2 = manager.try_allocate(30, 30).unwrap();
        assert_eq!(allocation2.atlas_id.as_u32(), 2);

        // Fourth allocation should go to atlas 2 again (still least used)
        let allocation3 = manager.try_allocate(30, 30).unwrap();
        assert_eq!(allocation3.atlas_id.as_u32(), 2);
    }

    #[test]
    fn test_round_robin_allocation_strategy() {
        let mut manager = MultiAtlasManager::new(AtlasConfig {
            initial_atlas_count: 3,
            max_atlases: 3,
            atlas_size: (256, 256),
            allocation_strategy: AllocationStrategy::RoundRobin,
            auto_grow: false,
        });

        // Allocations should cycle through atlases in order
        let allocation0 = manager.try_allocate(50, 50).unwrap();
        assert_eq!(allocation0.atlas_id.as_u32(), 0);

        let allocation1 = manager.try_allocate(50, 50).unwrap();
        assert_eq!(allocation1.atlas_id.as_u32(), 1);

        let allocation2 = manager.try_allocate(50, 50).unwrap();
        assert_eq!(allocation2.atlas_id.as_u32(), 2);

        // Should wrap back to atlas 0
        let allocation3 = manager.try_allocate(50, 50).unwrap();
        assert_eq!(allocation3.atlas_id.as_u32(), 0);

        // Continue the cycle
        let allocation4 = manager.try_allocate(50, 50).unwrap();
        assert_eq!(allocation4.atlas_id.as_u32(), 1);
    }

    #[test]
    fn test_auto_grow() {
        let mut manager = MultiAtlasManager::new(AtlasConfig {
            initial_atlas_count: 1,
            max_atlases: 3,
            atlas_size: (256, 256),
            allocation_strategy: AllocationStrategy::FirstFit,
            auto_grow: true,
        });

        let allocation0 = manager.try_allocate(256, 256).unwrap();
        assert_eq!(allocation0.atlas_id.as_u32(), 0);

        let allocation1 = manager.try_allocate(256, 256).unwrap();
        assert_eq!(allocation1.atlas_id.as_u32(), 1);

        let allocation2 = manager.try_allocate(256, 256).unwrap();
        assert_eq!(allocation2.atlas_id.as_u32(), 2);
    }

    fn test_allocate_excluding_with_strategy(strategy: AllocationStrategy) {
        let mut manager = MultiAtlasManager::new(AtlasConfig {
            initial_atlas_count: 3,
            max_atlases: 3,
            atlas_size: (256, 256),
            allocation_strategy: strategy,
            auto_grow: false,
        });

        let allocation0 = manager.try_allocate(100, 100).unwrap();
        let first_atlas = allocation0.atlas_id;
        let allocation1 = manager
            .try_allocate_excluding(256, 256, Some(first_atlas))
            .unwrap();
        assert_ne!(allocation1.atlas_id, first_atlas);

        let second_atlas = allocation1.atlas_id;
        let allocation2 = manager
            .try_allocate_excluding(100, 100, Some(second_atlas))
            .unwrap();
        assert_ne!(allocation2.atlas_id, second_atlas);

        let allocation3 = manager
            .try_allocate_excluding(100, 100, Some(first_atlas))
            .unwrap();
        assert_ne!(allocation3.atlas_id, first_atlas);
    }

    #[test]
    fn test_allocate_excluding_first_fit() {
        test_allocate_excluding_with_strategy(AllocationStrategy::FirstFit);
    }

    #[test]
    fn test_allocate_excluding_best_fit() {
        test_allocate_excluding_with_strategy(AllocationStrategy::BestFit);
    }

    #[test]
    fn test_allocate_excluding_least_used() {
        test_allocate_excluding_with_strategy(AllocationStrategy::LeastUsed);
    }

    #[test]
    fn test_allocate_excluding_round_robin() {
        test_allocate_excluding_with_strategy(AllocationStrategy::RoundRobin);
    }
}