rust/lib-hedgewars-engine/src/render/atlas.rs
changeset 14741 b110cbe52e51
parent 14738 16024046d458
child 14743 c97faf0aef78
equal deleted inserted replaced
14740:abc6aaf481c4 14741:b110cbe52e51
     1 use integral_geometry::{Rect, Size};
     1 use integral_geometry::{Rect, Size};
     2 use std::cmp::{max, min, Ordering};
     2 use std::cmp::{max, min, Ordering};
     3 
     3 
     4 pub struct Atlas {
     4 #[derive(PartialEq, Eq, PartialOrd, Ord, Clone)]
     5     size: Size,
       
     6     free_rects: Vec<Rect>,
       
     7     used_rects: Vec<Rect>,
       
     8 }
       
     9 
       
    10 #[derive(PartialEq, Eq, PartialOrd, Ord)]
       
    11 struct Fit {
     5 struct Fit {
    12     short_size: u32,
     6     short_size: u32,
    13     long_size: u32,
     7     long_size: u32,
    14 }
     8 }
    15 
     9 
    33             None
    27             None
    34         }
    28         }
    35     }
    29     }
    36 }
    30 }
    37 
    31 
    38 fn split_rect(free_rect: Rect, rect: Rect) -> Vec<Rect> {
    32 pub struct Atlas {
    39     let mut result = vec![];
    33     size: Size,
    40     if free_rect.intersects(&rect) {
    34     free_rects: Vec<Rect>,
    41         if rect.left() > free_rect.left() {
    35     used_rects: Vec<Rect>,
    42             let trim = free_rect.right() - rect.left() + 1;
       
    43             result.push(free_rect.with_margins(0, -trim, 0, 0))
       
    44         }
       
    45         if rect.right() < free_rect.right() {
       
    46             let trim = rect.right() - free_rect.left() + 1;
       
    47             result.push(free_rect.with_margins(-trim, 0, 0, 0))
       
    48         }
       
    49         if rect.top() > free_rect.top() {
       
    50             let trim = free_rect.bottom() - rect.top() + 1;
       
    51             result.push(free_rect.with_margins(0, 0, 0, -trim));
       
    52         }
       
    53         if rect.bottom() < free_rect.bottom() {
       
    54             let trim = rect.bottom() - free_rect.top() + 1;
       
    55             result.push(free_rect.with_margins(0, 0, -trim, 0));
       
    56         }
       
    57     }
       
    58     result
       
    59 }
    36 }
    60 
    37 
    61 impl Atlas {
    38 impl Atlas {
    62     pub fn new(size: Size) -> Self {
    39     pub fn new(size: Size) -> Self {
    63         Self {
    40         Self {
    64             size,
    41             size,
    65             free_rects: vec![Rect::at_origin(size)],
    42             free_rects: vec![Rect::at_origin(size)],
    66             used_rects: vec![],
    43             used_rects: vec![],
    67         }
    44         }
       
    45     }
       
    46 
       
    47     pub fn size(&self) -> Size {
       
    48         self.size
    68     }
    49     }
    69 
    50 
    70     fn find_position(&self, size: Size) -> Option<(Rect, Fit)> {
    51     fn find_position(&self, size: Size) -> Option<(Rect, Fit)> {
    71         let mut best_rect = Rect::EMPTY;
    52         let mut best_rect = Rect::EMPTY;
    72         let mut best_fit = Fit::new();
    53         let mut best_fit = Fit::new();
   105             })
    86             })
   106             .cloned()
    87             .cloned()
   107             .collect();
    88             .collect();
   108     }
    89     }
   109 
    90 
   110     pub fn insert_adaptive(&mut self, size: Size) -> Option<Rect> {
    91     pub fn insert(&mut self, size: Size) -> Option<Rect> {
   111         let (rect, fit) = self.find_position(size)?;
    92         let (rect, _) = self.find_position(size)?;
   112 
    93 
   113         let mut rects_to_process = self.free_rects.len();
    94         let mut rects_to_process = self.free_rects.len();
   114         let mut i = 0;
    95         let mut i = 0;
   115 
    96 
   116         while i < rects_to_process {
    97         while i < rects_to_process {
   131 
   112 
   132     pub fn insert_set<Iter>(&mut self, sizes: Iter) -> Vec<Rect>
   113     pub fn insert_set<Iter>(&mut self, sizes: Iter) -> Vec<Rect>
   133     where
   114     where
   134         Iter: Iterator<Item = Size>,
   115         Iter: Iterator<Item = Size>,
   135     {
   116     {
   136         unimplemented!()
   117         let mut sizes: Vec<_> = sizes.collect();
       
   118         let mut result = vec![];
       
   119 
       
   120         while let Some((index, (rect, _))) = sizes
       
   121             .iter()
       
   122             .enumerate()
       
   123             .filter_map(|(i, s)| self.find_position(*s).map(|res| (i, res)))
       
   124             .min_by_key(|(_, (_, fit))| fit.clone())
       
   125         {
       
   126             result.push(rect);
       
   127             sizes.swap_remove(index);
       
   128         }
       
   129         if sizes.is_empty() {
       
   130             self.used_rects.extend_from_slice(&result);
       
   131             result
       
   132         } else {
       
   133             vec![]
       
   134         }
   137     }
   135     }
   138 
   136 
   139     pub fn reset(&mut self) {
   137     pub fn reset(&mut self) {
   140         self.free_rects.clear();
   138         self.free_rects.clear();
   141         self.used_rects.clear();
   139         self.used_rects.clear();
   142         self.free_rects.push(Rect::at_origin(self.size));
   140         self.free_rects.push(Rect::at_origin(self.size));
   143     }
   141     }
   144 }
   142 }
   145 
   143 
       
   144 pub struct AtlasCollection {
       
   145     texture_size: Size,
       
   146     atlases: Vec<Atlas>,
       
   147 }
       
   148 
       
   149 impl AtlasCollection {
       
   150     pub fn new(texture_size: Size) -> Self {
       
   151         Self {
       
   152             texture_size,
       
   153             atlases: vec![],
       
   154         }
       
   155     }
       
   156 
       
   157     fn repack(&mut self, size: Size) -> bool {
       
   158         for atlas in &mut self.atlases {
       
   159             let mut temp_atlas = Atlas::new(atlas.size());
       
   160             let sizes = atlas
       
   161                 .used_rects
       
   162                 .iter()
       
   163                 .map(|r| r.size())
       
   164                 .chain(std::iter::once(size));
       
   165             if !temp_atlas.insert_set(sizes).is_empty() {
       
   166                 std::mem::swap(atlas, &mut temp_atlas);
       
   167                 return true;
       
   168             }
       
   169         }
       
   170         false
       
   171     }
       
   172 
       
   173     pub fn insert_sprite(&mut self, size: Size) -> bool {
       
   174         if !self.texture_size.contains(size) {
       
   175             false
       
   176         } else {
       
   177             if let Some(rect) = self
       
   178                 .atlases
       
   179                 .iter_mut()
       
   180                 .find_map(|a| a.insert(size))
       
   181             {
       
   182 
       
   183             } else if !self.repack(size) {
       
   184                 let mut atlas = Atlas::new(self.texture_size);
       
   185                 atlas.insert(size);
       
   186                 self.atlases.push(atlas);
       
   187             }
       
   188             true
       
   189         }
       
   190     }
       
   191 }
       
   192 
       
   193 fn split_rect(free_rect: Rect, rect: Rect) -> Vec<Rect> {
       
   194     let mut result = vec![];
       
   195     if free_rect.intersects(&rect) {
       
   196         if rect.left() > free_rect.left() {
       
   197             let trim = free_rect.right() - rect.left() + 1;
       
   198             result.push(free_rect.with_margins(0, -trim, 0, 0))
       
   199         }
       
   200         if rect.right() < free_rect.right() {
       
   201             let trim = rect.right() - free_rect.left() + 1;
       
   202             result.push(free_rect.with_margins(-trim, 0, 0, 0))
       
   203         }
       
   204         if rect.top() > free_rect.top() {
       
   205             let trim = free_rect.bottom() - rect.top() + 1;
       
   206             result.push(free_rect.with_margins(0, 0, 0, -trim));
       
   207         }
       
   208         if rect.bottom() < free_rect.bottom() {
       
   209             let trim = rect.bottom() - free_rect.top() + 1;
       
   210             result.push(free_rect.with_margins(0, 0, -trim, 0));
       
   211         }
       
   212     }
       
   213     result
       
   214 }
       
   215 
   146 #[cfg(test)]
   216 #[cfg(test)]
   147 mod tests {
   217 mod tests {
   148     use super::Atlas;
   218     use super::Atlas;
   149     use integral_geometry::{Rect, Size};
   219     use integral_geometry::{Rect, Size};
   150 
   220 
   151     #[test]
   221     #[test]
   152     fn insert() {
   222     fn insert() {
   153         let atlas_size = Size::square(16);
   223         let atlas_size = Size::square(16);
   154         let mut atlas = Atlas::new(atlas_size);
   224         let mut atlas = Atlas::new(atlas_size);
   155 
   225 
   156         assert_eq!(None, atlas.insert_adaptive(Size::square(20)));
   226         assert_eq!(None, atlas.insert(Size::square(20)));
   157 
   227 
   158         let rect_size = Size::new(11, 3);
   228         let rect_size = Size::new(11, 3);
   159         let rect = atlas.insert_adaptive(rect_size).unwrap();
   229         let rect = atlas.insert(rect_size).unwrap();
   160         assert_eq!(rect, Rect::at_origin(rect_size));
   230         assert_eq!(rect, Rect::at_origin(rect_size));
   161         assert_eq!(2, atlas.free_rects.len());
   231         assert_eq!(2, atlas.free_rects.len());
   162     }
   232     }
   163 }
   233 }