rg3d_core/
rectpack.rs

1//! Rectangle packer is used to pack set of smaller rectangles into one big, it
2//! used in texture atlas packer.
3
4use crate::{
5    math::Rect,
6    num_traits::Zero,
7    pool::{Handle, Pool},
8};
9use nalgebra::Scalar;
10use num_traits::NumAssign;
11
12struct RectPackNode<T>
13where
14    T: NumAssign + Scalar + PartialOrd + Copy,
15{
16    filled: bool,
17    split: bool,
18    bounds: Rect<T>,
19    left: Handle<RectPackNode<T>>,
20    right: Handle<RectPackNode<T>>,
21}
22
23impl<T> RectPackNode<T>
24where
25    T: NumAssign + Scalar + PartialOrd + Copy,
26{
27    fn new(bounds: Rect<T>) -> Self {
28        Self {
29            bounds,
30            filled: false,
31            split: false,
32            left: Handle::NONE,
33            right: Handle::NONE,
34        }
35    }
36}
37
38/// See module docs.
39pub struct RectPacker<T>
40where
41    T: NumAssign + Scalar + PartialOrd + Copy,
42{
43    nodes: Pool<RectPackNode<T>>,
44    root: Handle<RectPackNode<T>>,
45    width: T,
46    height: T,
47    unvisited: Vec<Handle<RectPackNode<T>>>,
48}
49
50impl<T> RectPacker<T>
51where
52    T: NumAssign + Scalar + PartialOrd + Copy,
53{
54    /// Creates new instance of rectangle packer with given bounds.
55    ///
56    /// # How to choose bounds
57    ///
58    /// If you have a set of rectangles and you need to calculate average side length of a square,
59    /// then calculate total area of your triangles by sum of width*height and then take square
60    /// root out of area. You'll get side length of a square which can be used as width and height
61    /// parameters.
62    pub fn new(w: T, h: T) -> Self {
63        let mut nodes = Pool::new();
64        let root = nodes.spawn(RectPackNode::new(Rect::new(
65            Zero::zero(),
66            Zero::zero(),
67            w,
68            h,
69        )));
70        Self {
71            nodes,
72            root,
73            width: w,
74            height: h,
75            unvisited: Default::default(),
76        }
77    }
78
79    /// Clears packer and prepares it for another run. It is much cheaper than create new packer,
80    /// because it reuses previously allocated memory.
81    pub fn clear(&mut self) {
82        self.nodes.clear();
83        self.unvisited.clear();
84        self.root = self.nodes.spawn(RectPackNode::new(Rect::new(
85            Zero::zero(),
86            Zero::zero(),
87            self.width,
88            self.height,
89        )));
90    }
91
92    /// Tries to find free place to put rectangle with given size. Returns None if there insufficient
93    /// space.
94    pub fn find_free(&mut self, w: T, h: T) -> Option<Rect<T>> {
95        if self.unvisited.is_empty() {
96            self.unvisited.push(self.root);
97        }
98
99        while let Some(node_handle) = self.unvisited.pop() {
100            let node = self.nodes.borrow_mut(node_handle);
101            if node.split {
102                self.unvisited.push(node.right);
103                self.unvisited.push(node.left);
104            } else if !node.filled && node.bounds.w() >= w && node.bounds.h() >= h {
105                if node.bounds.w() == w && node.bounds.h() == h {
106                    node.filled = true;
107                    return Some(node.bounds);
108                }
109
110                // Split and continue
111                node.split = true;
112
113                let (left_bounds, right_bounds) = if node.bounds.w() - w > node.bounds.h() - h {
114                    (
115                        Rect::new(node.bounds.x(), node.bounds.y(), w, node.bounds.h()),
116                        Rect::new(
117                            node.bounds.x() + w,
118                            node.bounds.y(),
119                            node.bounds.w() - w,
120                            node.bounds.h(),
121                        ),
122                    )
123                } else {
124                    (
125                        Rect::new(node.bounds.x(), node.bounds.y(), node.bounds.w(), h),
126                        Rect::new(
127                            node.bounds.x(),
128                            node.bounds.y() + h,
129                            node.bounds.w(),
130                            node.bounds.h() - h,
131                        ),
132                    )
133                };
134
135                let left = self.nodes.spawn(RectPackNode::new(left_bounds));
136                let right = self.nodes.spawn(RectPackNode::new(right_bounds));
137
138                let node = self.nodes.borrow_mut(node_handle);
139                node.left = left;
140                node.right = right;
141
142                self.unvisited.push(left);
143            }
144        }
145
146        None
147    }
148}
rg3d_core/rectpack.rs

rg3d_core/
rectpack.rs
