Quelle  guillotine.rs   Sprache: unbekannt

/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

use api::units::{DeviceIntPoint, DeviceIntRect, DeviceIntSize};

//TODO: gather real-world statistics on the bin usage in order to assist the decision
// on where to place the size thresholds.

const NUM_BINS: usize = 3;
/// The minimum number of pixels on each side that we require for rects to be classified as
/// particular bin of freelists.
const MIN_RECT_AXIS_SIZES: [i32; NUM_BINS] = [1, 16, 32];

#[derive(Debug, Clone, Copy, PartialEq, PartialOrd)]
struct FreeListBin(u8);

#[derive(Debug, Clone, Copy)]
struct FreeListIndex(usize);

impl FreeListBin {
    fn for_size(size: &DeviceIntSize) -> Self {
        MIN_RECT_AXIS_SIZES
            .iter()
            .enumerate()
            .rev()
            .find(|(_, &min_size)| min_size <= size.width && min_size <= size.height)
            .map(|(id, _)| FreeListBin(id as u8))
            .unwrap_or_else(|| panic!("Unable to find a bin for {:?}!", size))
    }
}

#[derive(Debug, Clone, Copy, PartialEq)]
#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
pub struct FreeRectSlice(pub u32);

#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
struct FreeRect {
    slice: FreeRectSlice,
    rect: DeviceIntRect,
}

#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
struct FreeRectSize {
    width: i16,
    height: i16,
}

#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
struct Bin {
    // Store sizes with fewer bits per item and in a separate array to speed up
    // the search.
    sizes: Vec<FreeRectSize>,
    rects: Vec<FreeRect>,
}

/// A texture allocator using the guillotine algorithm.
///
/// See sections 2.2 and 2.2.5 in "A Thousand Ways to Pack the Bin - A Practical Approach to Two-
/// Dimensional Rectangle Bin Packing":
///
///    http://clb.demon.fi/files/RectangleBinPack.pdf
///
/// This approach was chosen because of its simplicity and good performance.
///
/// Note: the allocations are spread across multiple textures, and also are binned
/// orthogonally in order to speed up the search.
#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
pub struct GuillotineAllocator {
    bins: [Bin; NUM_BINS],
}

impl GuillotineAllocator {
    pub fn new(initial_size: Option<DeviceIntSize>) -> Self {
        let mut allocator = GuillotineAllocator {
            bins: [
                Bin { rects: Vec::new(), sizes: Vec::new() },
                Bin { rects: Vec::new(), sizes: Vec::new() },
                Bin { rects: Vec::new(), sizes: Vec::new() },
            ],
        };

        if let Some(initial_size) = initial_size {
            allocator.push(
                FreeRectSlice(0),
                initial_size.into(),
            );
        }

        allocator
    }

    fn push(&mut self, slice: FreeRectSlice, rect: DeviceIntRect) {
        let id = FreeListBin::for_size(&rect.size()).0 as usize;
        self.bins[id].rects.push(FreeRect {
            slice,
            rect,
        });
        self.bins[id].sizes.push(FreeRectSize {
            width: rect.width() as i16,
            height: rect.height() as i16,
        });
    }

    /// Find a suitable rect in the free list. We choose the first fit.
    fn find_index_of_best_rect(
        &self,
        requested_dimensions: &DeviceIntSize,
    ) -> Option<(FreeListBin, FreeListIndex)> {

        let start_bin = FreeListBin::for_size(&requested_dimensions);

        let w = requested_dimensions.width as i16;
        let h = requested_dimensions.height as i16;
        (start_bin.0 .. NUM_BINS as u8)
            .find_map(|id| {
                self.bins[id as usize].sizes
                    .iter()
                    .position(|candidate| w <= candidate.width && h <= candidate.height)
                    .map(|index| (FreeListBin(id), FreeListIndex(index)))
            })
    }

    // Split that results in the single largest area (Min Area Split Rule, MINAS).
    fn split_guillotine(&mut self, chosen: &FreeRect, requested_dimensions: &DeviceIntSize) {
        let candidate_free_rect_to_right = DeviceIntRect::from_origin_and_size(
            DeviceIntPoint::new(
                chosen.rect.min.x + requested_dimensions.width,
                chosen.rect.min.y,
            ),
            DeviceIntSize::new(
                chosen.rect.width() - requested_dimensions.width,
                requested_dimensions.height,
            ),
        );
        let candidate_free_rect_to_bottom = DeviceIntRect::from_origin_and_size(
            DeviceIntPoint::new(
                chosen.rect.min.x,
                chosen.rect.min.y + requested_dimensions.height,
            ),
            DeviceIntSize::new(
                requested_dimensions.width,
                chosen.rect.height() - requested_dimensions.height,
            ),
        );

        // Guillotine the rectangle.
        let new_free_rect_to_right;
        let new_free_rect_to_bottom;
        if candidate_free_rect_to_right.area() > candidate_free_rect_to_bottom.area() {
            new_free_rect_to_right = DeviceIntRect::from_origin_and_size(
                candidate_free_rect_to_right.min,
                DeviceIntSize::new(
                    candidate_free_rect_to_right.width(),
                    chosen.rect.height(),
                ),
            );
            new_free_rect_to_bottom = candidate_free_rect_to_bottom
        } else {
            new_free_rect_to_right = candidate_free_rect_to_right;
            new_free_rect_to_bottom = DeviceIntRect::from_origin_and_size(
                candidate_free_rect_to_bottom.min,
                DeviceIntSize::new(
                    chosen.rect.width(),
                    candidate_free_rect_to_bottom.height(),
                ),
            )
        }

        // Add the guillotined rects back to the free list.
        if !new_free_rect_to_right.is_empty() {
            self.push(chosen.slice, new_free_rect_to_right);
        }
        if !new_free_rect_to_bottom.is_empty() {
            self.push(chosen.slice, new_free_rect_to_bottom);
        }
    }

    pub fn allocate(
        &mut self, requested_dimensions: &DeviceIntSize
    ) -> Option<(FreeRectSlice, DeviceIntPoint)> {
        let mut requested_dimensions = *requested_dimensions;
        // Round up the size to a multiple of 8. This reduces the fragmentation
        // of the atlas.
        requested_dimensions.width = (requested_dimensions.width + 7) & !7;
        requested_dimensions.height = (requested_dimensions.height + 7) & !7;

        if requested_dimensions.width == 0 || requested_dimensions.height == 0 {
            return Some((FreeRectSlice(0), DeviceIntPoint::new(0, 0)));
        }

        let (bin, index) = self.find_index_of_best_rect(&requested_dimensions)?;

        // Remove the rect from the free list and decide how to guillotine it.
        let chosen = self.bins[bin.0 as usize].rects.swap_remove(index.0);
        self.bins[bin.0 as usize].sizes.swap_remove(index.0);
        self.split_guillotine(&chosen, &requested_dimensions);

        // Return the result.
        Some((chosen.slice, chosen.rect.min))
    }

    /// Add a new slice to the allocator, and immediately allocate a rect from it.
    pub fn extend(
        &mut self,
        slice: FreeRectSlice,
        total_size: DeviceIntSize,
        requested_dimensions: DeviceIntSize,
    ) {
        self.split_guillotine(
            &FreeRect { slice, rect: total_size.into() },
            &requested_dimensions
        );
    }
}

#[cfg(test)]
fn random_fill(count: usize, texture_size: i32) -> f32 {
    use rand::{thread_rng, Rng};

    let total_rect = DeviceIntRect::from_size(
        DeviceIntSize::new(texture_size, texture_size),
    );
    let mut rng = thread_rng();
    let mut allocator = GuillotineAllocator::new(None);

    // check for empty allocation
    assert_eq!(
        allocator.allocate(&DeviceIntSize::new(0, 12)),
        Some((FreeRectSlice(0), DeviceIntPoint::zero())),
    );

    let mut slices: Vec<Vec<DeviceIntRect>> = Vec::new();
    let mut requested_area = 0f32;
    // fill up the allocator
    for _ in 0 .. count {
        let size = DeviceIntSize::new(
            rng.gen_range(1, texture_size),
            rng.gen_range(1, texture_size),
        );
        requested_area += size.area() as f32;

        match allocator.allocate(&size) {
            Some((slice, origin)) => {
                let rect = DeviceIntRect::from_origin_and_size(origin, size);
                assert_eq!(None, slices[slice.0 as usize].iter().find(|r| r.intersects(&rect)));
                assert!(total_rect.contains_box(&rect));
                slices[slice.0 as usize].push(rect);
            }
            None => {
                allocator.extend(FreeRectSlice(slices.len() as u32), total_rect.size(), size);
                let rect = DeviceIntRect::from_size(size);
                slices.push(vec![rect]);
            }
        }
    }
    // validate the free rects
    for (i, bin) in allocator.bins.iter().enumerate() {
        for fr in &bin.rects {
            assert_eq!(FreeListBin(i as u8), FreeListBin::for_size(&fr.rect.size()));
            assert_eq!(None, slices[fr.slice.0 as usize].iter().find(|r| r.intersects(&fr.rect)));
            assert!(total_rect.contains_box(&fr.rect));
            slices[fr.slice.0 as usize].push(fr.rect);
        }
    }

    let allocated_area = slices.len() as f32 * (texture_size * texture_size) as f32;
    requested_area / allocated_area
}

#[test]
fn test_small() {
    random_fill(100, 100);
}

#[test]
fn test_large() {
    random_fill(1000, 10000);
}