conspire/geometry/ntree/balance/octree/
mod.rs

1use crate::geometry::ntree::node::slot::Slot;
2#[cfg(test)]
3mod test;
4
5use crate::geometry::ntree::{
6    Orthotree,
7    balance::{Balance, Balancing},
8    node::cell::Cell,
9    pair::Pairing,
10};
11
12const D: usize = 3;
13const L: usize = 4;
14const M: usize = 6;
15const N: usize = 8;
16
17const FACE_ORTHANTS: [[usize; 4]; M] = [
18    [1, 3, 5, 7],
19    [0, 2, 4, 6],
20    [2, 3, 6, 7],
21    [0, 1, 4, 5],
22    [4, 5, 6, 7],
23    [0, 1, 2, 3],
24];
25
26impl<T, U, V> Orthotree<D, L, M, N, T, U, V>
27where
28    T: Cell,
29    U: Slot,
30{
31    fn deep_toward(&self, cell: U, orthants: &[usize], depth: usize) -> bool {
32        match self[cell].orthants() {
33            None => false,
34            Some(children) => {
35                depth == 0
36                    || orthants
37                        .iter()
38                        .any(|&orthant| self.deep_toward(children[orthant], orthants, depth - 1))
39            }
40        }
41    }
42    fn deep(&self, cell: U, face: usize, depth: usize) -> bool {
43        self.deep_toward(cell, &FACE_ORTHANTS[face], depth)
44    }
45    fn diagonally_deep(&self, children: &[U; N], face: usize, depth: usize) -> bool {
46        let (axis, side) = (face / 2, face % 2);
47        (0..D).filter(|&other| other != axis).any(|other| {
48            (0..2).any(|beyond| {
49                let last = D - axis - other;
50                let toward = ((1 - side) << axis) | ((1 - beyond) << other);
51                let along = [toward, toward | (1 << last)];
52                let adjacent = ((1 - side) << axis) | (beyond << other);
53                [adjacent, adjacent | (1 << last)].into_iter().any(|child| {
54                    self[children[child]].facets()[2 * other + beyond].is_some_and(|edge| {
55                        self.deep_toward(edge, &along, depth - 1) || {
56                            let up = (child >> last) & 1;
57                            self[edge].facets()[2 * last + up].is_some_and(|vertex| {
58                                self.deep_toward(vertex, &[toward | ((1 - up) << last)], depth - 1)
59                            })
60                        }
61                    })
62                })
63            })
64        })
65    }
66}
67
68impl<T, U, V> Balance for Orthotree<D, L, M, N, T, U, V>
69where
70    T: Cell,
71    U: Slot,
72    V: Copy,
73{
74    fn balance(&mut self, balancing: Balancing) -> bool {
75        self.balanced = balancing;
76        let mut balanced;
77        let mut balanced_already = true;
78        let mut index;
79        let mut subdivide;
80        loop {
81            balanced = true;
82            index = 0;
83            subdivide = false;
84            while index < self.len() {
85                if !self.nodes[index].is_unit() && self.nodes[index].is_leaf() {
86                    'faces: for (face, face_cell) in self.nodes[index].facets().iter().enumerate() {
87                        if let Some(neighbor) = face_cell
88                            && let Some(children) = self[*neighbor].orthants()
89                        {
90                            let unbalanced = match balancing {
91                                Balancing::Weak(depth) => self.deep(*neighbor, face, depth),
92                                Balancing::Strong(depth) => {
93                                    self.deep(*neighbor, face, depth)
94                                        || self.diagonally_deep(children, face, depth)
95                                }
96                                Balancing::None => false,
97                            };
98                            if unbalanced {
99                                subdivide = true;
100                                break 'faces;
101                            }
102                        }
103                    }
104                    if subdivide {
105                        self.subdivide(index).unwrap();
106                        balanced = false;
107                        balanced_already = false;
108                        subdivide = false;
109                    }
110                }
111                index += 1;
112            }
113            if balanced {
114                break;
115            }
116        }
117        balanced_already
118    }
119    fn pair_up(&mut self, pairing: Pairing) -> Result<bool, &'static str> {
120        self.paired = pairing;
121        self.pair(pairing)
122    }
123}
conspire/geometry/ntree/balance/octree/mod.rs

conspire/geometry/ntree/balance/octree/
mod.rs
