# HG changeset patch
# User alfadur
# Date 1561066436 -10800
# Node ID 9cf0c2f44f0ec37fb72f07fda1e5116f55c106bc
# Parent  9231247b1f836a20216f21fb70bb7a8014a0cb05
add a way to reference atlas contents

diff -r 9231247b1f83 -r 9cf0c2f44f0e rust/lib-hedgewars-engine/src/render/atlas.rs
--- a/rust/lib-hedgewars-engine/src/render/atlas.rs	Thu Jun 20 16:05:03 2019 +0300
+++ b/rust/lib-hedgewars-engine/src/render/atlas.rs	Fri Jun 21 00:33:56 2019 +0300
@@ -1,5 +1,9 @@
 use integral_geometry::{Rect, Size};
-use std::cmp::{max, min, Ordering};
+use itertools::Itertools;
+use std::{
+    cmp::{max, min, Ordering},
+    ops::Index,
+};
 
 #[derive(PartialEq, Eq, PartialOrd, Ord, Clone)]
 struct Fit {
@@ -50,6 +54,10 @@
     const fn total(&self) -> usize {
         self.total_area
     }
+
+    const fn free(&self) -> usize {
+        self.total_area - self.used_area
+    }
 }
 
 impl std::fmt::Debug for UsedSpace {
@@ -63,14 +71,14 @@
     }
 }
 
-pub struct Atlas {
+pub struct Atlas<T> {
     size: Size,
     free_rects: Vec<Rect>,
-    used_rects: Vec<Rect>,
+    used_rects: Vec<(Rect, T)>,
     splits: Vec<Rect>,
 }
 
-impl Atlas {
+impl<T: Copy> Atlas<T> {
     pub fn new(size: Size) -> Self {
         Self {
             size,
@@ -85,7 +93,7 @@
     }
 
     pub fn used_space(&self) -> UsedSpace {
-        let used = self.used_rects.iter().map(|r| r.size().area()).sum();
+        let used = self.used_rects.iter().map(|(r, _)| r.size().area()).sum();
         UsedSpace::new(used, self.size.area())
     }
 
@@ -116,7 +124,7 @@
         }
     }
 
-    fn split_insert(&mut self, rect: Rect) {
+    fn split_insert(&mut self, rect: Rect, value: T) {
         let mut splits = std::mem::replace(&mut self.splits, vec![]);
         let mut buffer = [Rect::EMPTY; 4];
 
@@ -133,31 +141,31 @@
         self.free_rects.extend(splits.drain(..));
         std::mem::replace(&mut self.splits, splits);
 
-        self.used_rects.push(rect);
+        self.used_rects.push((rect, value));
     }
 
-    pub fn insert(&mut self, size: Size) -> Option<Rect> {
+    pub fn insert(&mut self, size: Size, value: T) -> Option<Rect> {
         let (rect, _) = self.find_position(size)?;
-        self.split_insert(rect);
+        self.split_insert(rect, value);
         Some(rect)
     }
 
-    pub fn insert_set<Iter>(&mut self, sizes: Iter) -> Vec<Rect>
+    pub fn insert_set<Iter>(&mut self, sizes: Iter) -> Vec<(Rect, T)>
     where
-        Iter: Iterator<Item = Size>,
+        Iter: Iterator<Item = (Size, T)>,
     {
         let mut sizes: Vec<_> = sizes.collect();
-        let mut result = vec![];
+        let mut result = Vec::with_capacity(sizes.len());
 
-        while let Some((index, (rect, _))) = sizes
+        while let Some((index, (rect, _), value)) = sizes
             .iter()
             .enumerate()
-            .filter_map(|(i, s)| self.find_position(*s).map(|res| (i, res)))
-            .min_by_key(|(_, (_, fit))| fit.clone())
+            .filter_map(|(i, (s, v))| self.find_position(*s).map(|res| (i, res, v)))
+            .min_by_key(|(_, (_, fit), _)| fit.clone())
         {
-            self.split_insert(rect);
+            self.split_insert(rect, *value);
 
-            result.push(rect);
+            result.push((rect, *value));
             sizes.swap_remove(index);
         }
         result
@@ -170,51 +178,88 @@
     }
 }
 
+pub type SpriteIndex = u32;
+pub type SpriteLocation = (u32, Rect);
+
 pub struct AtlasCollection {
+    next_index: SpriteIndex,
     texture_size: Size,
-    atlases: Vec<Atlas>,
+    atlases: Vec<Atlas<SpriteIndex>>,
+    rects: Vec<SpriteLocation>,
 }
 
 impl AtlasCollection {
     pub fn new(texture_size: Size) -> Self {
         Self {
+            next_index: 0,
             texture_size,
             atlases: vec![],
+            rects: vec![],
         }
     }
 
     fn repack(&mut self, size: Size) -> bool {
-        for atlas in &mut self.atlases {
-            let mut temp_atlas = Atlas::new(atlas.size());
-            let sizes = atlas
-                .used_rects
-                .iter()
-                .map(|r| r.size())
-                .chain(std::iter::once(size));
-            if !temp_atlas.insert_set(sizes).is_empty() {
-                std::mem::swap(atlas, &mut temp_atlas);
-                return true;
+        for (atlas_index, atlas) in self.atlases.iter_mut().enumerate() {
+            if atlas.used_space().free() >= size.area() {
+                let mut temp_atlas = Atlas::new(atlas.size());
+                let sizes = atlas
+                    .used_rects
+                    .iter()
+                    .map(|(r, v)| (r.size(), *v))
+                    .chain(std::iter::once((size, self.next_index)));
+                let inserts = temp_atlas.insert_set(sizes);
+                if inserts.len() > atlas.used_rects.len() {
+                    self.rects.push((0, Rect::EMPTY));
+                    for (rect, index) in inserts {
+                        self.rects[index as usize] = (atlas_index as u32, rect);
+                    }
+                    std::mem::swap(atlas, &mut temp_atlas);
+                    return true;
+                }
             }
         }
         false
     }
 
-    pub fn insert_sprite(&mut self, size: Size) -> bool {
+    #[inline]
+    fn consume_index(&mut self) -> Option<SpriteIndex> {
+        let result = Some(self.next_index);
+        self.next_index += 1;
+        result
+    }
+
+    pub fn insert_sprite(&mut self, size: Size) -> Option<SpriteIndex> {
         if !self.texture_size.contains(size) {
-            false
+            None
         } else {
-            if let Some(rect) = self.atlases.iter_mut().find_map(|a| a.insert(size)) {
-
+            let index = self.next_index;
+            if let Some(index_rect) = self
+                .atlases
+                .iter_mut()
+                .enumerate()
+                .find_map(|(i, a)| a.insert(size, index).map(|r| (i as u32, r)))
+            {
+                self.rects.push(index_rect);
             } else if !self.repack(size) {
                 let mut atlas = Atlas::new(self.texture_size);
-                atlas.insert(size);
+                let rect = atlas.insert(size, index)?;
                 self.atlases.push(atlas);
+                self.rects.push(((self.atlases.len() - 1) as u32, rect))
             }
-            true
+            self.consume_index()
         }
     }
 }
 
+impl Index<SpriteIndex> for AtlasCollection {
+    type Output = SpriteLocation;
+
+    #[inline]
+    fn index(&self, index: SpriteIndex) -> &Self::Output {
+        &self.rects[index as usize]
+    }
+}
+
 #[inline]
 fn filter_swap_remove<T, F>(vec: &mut Vec<T>, predicate: F)
 where
@@ -309,10 +354,10 @@
         let atlas_size = Size::square(16);
         let mut atlas = Atlas::new(atlas_size);
 
-        assert_eq!(None, atlas.insert(Size::square(20)));
+        assert_eq!(None, atlas.insert(Size::square(20), ()));
 
         let rect_size = Size::new(11, 3);
-        let rect = atlas.insert(rect_size).unwrap();
+        let rect = atlas.insert(rect_size, ()).unwrap();
 
         assert_eq!(rect, Rect::at_origin(rect_size));
         assert_eq!(2, atlas.free_rects.len());
@@ -356,6 +401,12 @@
         }
     }
 
+    impl HasSize for (Rect, ()) {
+        fn size(&self) -> Size {
+            self.0.size()
+        }
+    }
+
     fn sum_area<S: HasSize>(items: &[S]) -> usize {
         items.iter().map(|s| s.size().area()).sum()
     }
@@ -365,7 +416,7 @@
         fn prop_insert(rects in Vec::<TestRect>::arbitrary()) {
             let container = Rect::at_origin(Size::square(2048));
             let mut atlas = Atlas::new(container.size());
-            let inserted: Vec<_> = rects.iter().filter_map(|TestRect(size)| atlas.insert(*size)).collect();
+            let inserted: Vec<_> = rects.iter().filter_map(|TestRect(size)| atlas.insert(*size, ())).collect();
 
             let mut inserted_pairs = inserted.iter().cartesian_product(inserted.iter());
 
@@ -384,12 +435,12 @@
             let mut atlas = Atlas::new(container.size());
             let mut set_atlas = Atlas::new(container.size());
 
-            let inserted: Vec<_> = rects.iter().filter_map(|TestRect(size)| atlas.insert(*size)).collect();
-            let set_inserted: Vec<_> = set_atlas.insert_set(rects.iter().map(|TestRect(size)| *size));
+            let inserted: Vec<_> = rects.iter().filter_map(|TestRect(size)| atlas.insert(*size, ())).collect();
+            let set_inserted: Vec<_> = set_atlas.insert_set(rects.iter().map(|TestRect(size)| (*size, ())));
 
             let mut set_inserted_pairs = set_inserted.iter().cartesian_product(set_inserted.iter());
 
-            assert!(set_inserted_pairs.all(|(r1, r2)| r1 == r2 || r1 != r2 && !r1.intersects(r2)));
+            assert!(set_inserted_pairs.all(|((r1, _), (r2, _))| r1 == r2 || r1 != r2 && !r1.intersects(r2)));
             assert!(set_atlas.used_space().used() <= atlas.used_space().used());
 
             assert_eq!(sum_area(&set_inserted), sum_area(&inserted));