tex_packer_core/packer/

maxrects.rs

use super::Packer;
use crate::config::{MaxRectsHeuristic, PackerConfig};
use crate::free_space::{prune_contained, subtract_intersections};
use crate::geometry::{
    PackingContext, PlacementGeometry, area_fit_score, bottom_ex_u32, contains_rect, intersects,
    overlap_1d, right_ex_u32,
};
use crate::model::{Frame, Rect};

pub struct MaxRectsPacker {
    config: PackerConfig,
    border: Rect,
    free: Vec<Rect>,
    used: Vec<Rect>,
    heuristic: MaxRectsHeuristic,
}

impl MaxRectsPacker {
    pub fn new(config: PackerConfig, heuristic: MaxRectsHeuristic) -> Self {
        let border = PackingContext::new(&config).usable_area();
        Self {
            config,
            border,
            free: vec![border],
            used: Vec::new(),
            heuristic,
        }
    }

    fn place_rect(&mut self, node: &Rect) {
        if self.config.mr_reference {
            return self.place_rect_ref(node);
        }
        self.free = subtract_intersections(self.free.iter().copied(), node);
        self.prune_free_list();
        self.used.push(*node);
    }

    fn place_rect_ref(&mut self, node: &Rect) {
        let mut new_free: Vec<Rect> = Vec::new();
        let mut i = 0usize;
        while i < self.free.len() {
            let fr = self.free[i];
            if intersects(&fr, node) {
                // remove this free rect; split into parts added to new_free
                self.free.swap_remove(i);
                self.split_free_node_ref(fr, node, &mut new_free);
            } else {
                i += 1;
            }
        }
        // Prune new_free against existing free; and remove dominated among new_free
        self.prune_new_vs_old(&mut new_free);
        self.prune_within(&mut new_free);
        // Merge new into free, then final prune pass
        self.free.extend(new_free);
        self.prune_free_list();
        self.used.push(*node);
    }

    fn split_free_node_ref(&self, fr: Rect, node: &Rect, out: &mut Vec<Rect>) {
        let fr_x2 = right_ex_u32(&fr);
        let fr_y2 = bottom_ex_u32(&fr);
        let n_x2 = right_ex_u32(node);
        let n_y2 = bottom_ex_u32(node);

        // Left
        if node.x > fr.x && node.x < fr_x2 {
            let w = node.x - fr.x;
            out.push(Rect::new(fr.x, fr.y, w, fr.h));
        }
        // Right
        if n_x2 < fr_x2 {
            let x = n_x2;
            let w = fr_x2 - n_x2;
            out.push(Rect::new(x, fr.y, w, fr.h));
        }
        // Top
        if node.y > fr.y && node.y < fr_y2 {
            let h = node.y - fr.y;
            out.push(Rect::new(fr.x, fr.y, fr.w, h));
        }
        // Bottom
        if n_y2 < fr_y2 {
            let y = n_y2;
            let h = fr_y2 - n_y2;
            out.push(Rect::new(fr.x, y, fr.w, h));
        }
        // filter zero areas handled by prune later
    }

    fn prune_new_vs_old(&mut self, new_free: &mut Vec<Rect>) {
        // Remove any new rect fully contained in any existing free rect
        new_free
            .retain(|nr| !self.free.iter().any(|of| contains_rect(of, nr)) && nr.w > 0 && nr.h > 0);
        // Remove any existing free rect fully contained in any remaining new rect
        let mut i = 0;
        while i < self.free.len() {
            if new_free.iter().any(|nr| contains_rect(nr, &self.free[i])) {
                self.free.swap_remove(i);
            } else {
                i += 1;
            }
        }
    }

    fn prune_within(&self, v: &mut Vec<Rect>) {
        let mut i = 0;
        while i < v.len() {
            let a = v[i];
            let a_x2 = right_ex_u32(&a);
            let a_y2 = bottom_ex_u32(&a);
            let mut remove_i = false;
            let mut j = 0;
            while j < v.len() {
                if i == j {
                    j += 1;
                    continue;
                }
                let b = v[j];
                let b_x2 = right_ex_u32(&b);
                let b_y2 = bottom_ex_u32(&b);
                if a.x >= b.x && a.y >= b.y && a_x2 <= b_x2 && a_y2 <= b_y2 {
                    remove_i = true;
                    break;
                }
                j += 1;
            }
            if remove_i {
                v.swap_remove(i);
            } else {
                i += 1;
            }
        }
    }

    fn prune_free_list(&mut self) {
        prune_contained(&mut self.free);
    }

    fn score(&self, fr: &Rect, w: u32, h: u32) -> (i128, i128) {
        let leftover_h = fr.w as i128 - w as i128;
        let leftover_v = fr.h as i128 - h as i128;
        let short_fit = leftover_h.abs().min(leftover_v.abs());
        let long_fit = leftover_h.abs().max(leftover_v.abs());
        let area_fit = area_fit_score(fr, w, h);
        match self.heuristic {
            MaxRectsHeuristic::BestAreaFit => (area_fit, short_fit),
            MaxRectsHeuristic::BestShortSideFit => (short_fit, long_fit),
            MaxRectsHeuristic::BestLongSideFit => (long_fit, short_fit),
            MaxRectsHeuristic::BottomLeft => (fr.y as i128, fr.x as i128),
            MaxRectsHeuristic::ContactPoint => {
                // maximize contact score: use negative for minimization
                let contact = self.contact_point_score(fr.x, fr.y, w, h);
                (-(contact as i128), area_fit)
            }
        }
    }

    fn find_position(&self, w: u32, h: u32) -> Option<(Rect, bool)> {
        let mut best_score1 = i128::MAX;
        let mut best_score2 = i128::MAX;
        let mut best_rect = Rect::new(0, 0, 0, 0);
        let mut best_rot = false;
        let mut best_top = u32::MAX; // tie-break: prefer smaller top side (y + h)
        let mut best_left = u32::MAX; // then prefer smaller x

        for fr in &self.free {
            // normal
            if fr.w >= w && fr.h >= h {
                let (s1, s2) = self.score(fr, w, h);
                let top = fr.y.saturating_add(h);
                if s1 < best_score1
                    || (s1 == best_score1
                        && (s2 < best_score2
                            || (s2 == best_score2
                                && (top < best_top || (top == best_top && fr.x < best_left)))))
                {
                    best_score1 = s1;
                    best_score2 = s2;
                    best_top = top;
                    best_left = fr.x;
                    best_rect = Rect::new(fr.x, fr.y, w, h);
                    best_rot = false;
                }
                // perfect fit early-out
                if fr.w == w && fr.h == h {
                    return Some((Rect::new(fr.x, fr.y, w, h), false));
                }
            }
            // rotated
            if self.config.allow_rotation && fr.w >= h && fr.h >= w {
                let (s1, s2) = self.score(fr, h, w);
                let top = fr.y.saturating_add(w);
                if s1 < best_score1
                    || (s1 == best_score1
                        && (s2 < best_score2
                            || (s2 == best_score2
                                && (top < best_top || (top == best_top && fr.x < best_left)))))
                {
                    best_score1 = s1;
                    best_score2 = s2;
                    best_top = top;
                    best_left = fr.x;
                    best_rect = Rect::new(fr.x, fr.y, h, w);
                    best_rot = true;
                }
                // perfect fit early-out (rotated)
                if fr.w == h && fr.h == w {
                    return Some((Rect::new(fr.x, fr.y, h, w), true));
                }
            }
        }

        if best_rect.w == 0 || best_rect.h == 0 {
            None
        } else {
            Some((best_rect, best_rot))
        }
    }

    fn contact_point_score(&self, x: u32, y: u32, w: u32, h: u32) -> u64 {
        let node = Rect::new(x, y, w, h);
        let mut score = 0u64;
        // contact with borders
        let border_right = right_ex_u32(&self.border);
        let border_bottom = bottom_ex_u32(&self.border);
        if node.x == self.border.x {
            score += node.h as u64;
        }
        if node.y == self.border.y {
            score += node.w as u64;
        }
        if right_ex_u32(&node) == border_right {
            score += node.h as u64;
        }
        if bottom_ex_u32(&node) == border_bottom {
            score += node.w as u64;
        }

        // contact with used rectangles
        for u in &self.used {
            // vertical contact (left/right edges)
            if node.x == right_ex_u32(u) || u.x == right_ex_u32(&node) {
                let overlap = overlap_1d(node.y, bottom_ex_u32(&node), u.y, bottom_ex_u32(u));
                score += overlap as u64;
            }
            // horizontal contact (top/bottom edges)
            if node.y == bottom_ex_u32(u) || u.y == bottom_ex_u32(&node) {
                let overlap = overlap_1d(node.x, right_ex_u32(&node), u.x, right_ex_u32(u));
                score += overlap as u64;
            }
        }
        score
    }

    pub fn free_list_len(&self) -> usize {
        self.free.len()
    }
}

impl<K: Clone> Packer<K> for MaxRectsPacker {
    fn can_pack(&self, rect: &Rect) -> bool {
        let geometry = PlacementGeometry::new(rect, &self.config);
        self.find_position(geometry.reserved_w, geometry.reserved_h)
            .is_some()
    }

    fn pack(&mut self, key: K, rect: &Rect) -> Option<Frame<K>> {
        let geometry = PlacementGeometry::new(rect, &self.config);
        if let Some((place, rotated)) = self.find_position(geometry.reserved_w, geometry.reserved_h)
        {
            self.place_rect(&place);
            Some(geometry.frame(key, *rect, &place, rotated))
        } else {
            None
        }
    }
}