1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

use crate::mesh::Mesh;
use std::hash::Hash;
use std::collections::{HashMap, VecDeque};

struct MeshQueue<K: Hash + Eq> {
    meshes: VecDeque<(K, Mesh)>,
    total_vertices: usize,
    max_vertices: usize,
    dirty: bool,
}

impl<K: Hash + Eq> MeshQueue<K> {
    pub fn new(max_vertices: usize) -> MeshQueue<K> {
        MeshQueue {
            meshes: VecDeque::new(),
            total_vertices: 0,
            max_vertices,
            dirty: false,
        }
    }

    pub fn push(
        &mut self,
        new_members: Vec<(K, Mesh)>,
        total_new_vertices: usize,
    ) -> (Vec<(K, Mesh)>, usize) {
        if total_new_vertices > self.max_vertices {
            panic!("New meshes too big for one queue");
        }

        let mut dropped = Vec::new();
        let mut total_dropped_vertices = 0;

        while self.total_vertices + total_new_vertices > self.max_vertices {
            let next_member_to_drop = self
                .meshes
                .pop_front()
                .expect("Should still have meshes left");
            self.total_vertices -= next_member_to_drop.1.vertices.len();
            total_dropped_vertices += next_member_to_drop.1.vertices.len();
            dropped.push(next_member_to_drop);
        }

        self.meshes.extend(new_members);
        self.total_vertices += total_new_vertices;
        self.dirty = true;

        (dropped, total_dropped_vertices)
    }

    pub fn remove(&mut self, key: &K) {
        let index = self
            .meshes
            .iter()
            .position(|(k, _)| k == key)
            .expect("Should contain key to be removed");
        let (_, old_mesh) = self.meshes.remove(index).unwrap();
        self.total_vertices -= old_mesh.vertices.len();
        self.dirty = true;
    }

    pub fn get_mesh_if_changed(&mut self) -> Option<Mesh> {
        if self.dirty {
            self.dirty = false;
            Some(self.meshes.iter().map(|(_, mesh)| mesh).sum())
        } else {
            None
        }
    }
}

pub struct MeshGrouper<K: Hash + Eq + Clone> {
    groups: Vec<MeshQueue<K>>,
    group_membership: HashMap<K, usize>,
    max_vertices_per_group: usize,
}

pub struct GroupChange {
    pub group_id: usize,
    pub new_group_mesh: Mesh,
}

impl<K: Hash + Eq + Clone> MeshGrouper<K> {
    pub fn new(max_vertices_per_group: usize) -> MeshGrouper<K> {
        MeshGrouper {
            groups: Vec::new(),
            group_membership: HashMap::new(),
            max_vertices_per_group,
        }
    }

    pub fn update<RemI: IntoIterator<Item = K>, AddI: IntoIterator<Item = (K, Mesh)>>(
        &mut self,
        to_remove: RemI,
        to_add: AddI,
    ) -> Vec<GroupChange> {
        for key_to_remove in to_remove {
            let group_idx = self.group_membership[&key_to_remove];
            self.groups[group_idx].remove(&key_to_remove);
        }

        for new_member in to_add {
            let mut current_group_idx = 0;
            let new_member_n_vertices = new_member.1.vertices.len();
            let mut to_push = (vec![new_member], new_member_n_vertices);

            while !to_push.0.is_empty() {
                // all members that are currently to push will fit in the current group!
                for (member_key, _) in &to_push.0 {
                    self.group_membership
                        .insert(member_key.clone(), current_group_idx);
                }

                let found_group = if let Some(group) = self.groups.get_mut(current_group_idx) {
                    to_push = group.push(to_push.0, to_push.1);
                    current_group_idx += 1;
                    true
                } else {
                    false
                };

                if !found_group {
                    let mut new_group = MeshQueue::new(self.max_vertices_per_group);
                    to_push = new_group.push(to_push.0, to_push.1);
                    self.groups.push(new_group);
                    // the rest should always fit in the last new group
                    assert!(to_push.0.is_empty());
                }
            }
        }

        self.groups
            .iter_mut()
            .enumerate()
            .filter_map(|(i, group)| {
                group.get_mesh_if_changed().map(|mesh| GroupChange {
                    group_id: i,
                    new_group_mesh: mesh,
                })
            })
            .collect()
    }
}