conspire/geometry/ntree/balance/octree/mod.rs
1use crate::geometry::ntree::{
2 Orthotree,
3 balance::{Balance, Balancing},
4 node::split::Split,
5 pair::Pairing,
6};
7use std::{array::from_fn, ops::Add};
8
9const NUM_EDGES: usize = 8;
10
11const D: usize = 3;
12const L: usize = 4;
13const M: usize = 6;
14const N: usize = 8;
15
16impl<T, U, V> Balance for Orthotree<D, L, M, N, T, U, V>
17where
18 T: Add<Output = T> + Copy + Split + Into<usize>,
19 U: Copy + From<usize> + Into<usize>,
20 V: Copy,
21{
22 fn balance(&mut self, balancing: Balancing) -> bool {
23 self.balanced = balancing;
24 let mut balanced;
25 let mut balanced_already = true;
26 let mut edges = [false; NUM_EDGES];
27 let mut index;
28 let mut subdivide;
29 let mut vertices = [false; 2];
30 let strong = matches!(balancing, Balancing::Strong);
31 loop {
32 balanced = true;
33 index = 0;
34 subdivide = false;
35 while index < self.len() {
36 if !self[index.into()].is_unit() && self[index.into()].is_leaf() {
37 'faces: for (face, face_cell) in self[index.into()].facets().iter().enumerate()
38 {
39 if let Some(neighbor) = face_cell
40 && let Some(kids) = self[*neighbor].orthants()
41 {
42 if strong {
43 edges = from_fn(|_| false);
44 vertices = from_fn(|_| false);
45 }
46 if match face {
47 0 => {
48 if strong {
49 if let Some(edge_cell) = self[kids[1]].facets()[2] {
50 edges[0] = self[edge_cell].is_tree()
51 }
52 if let Some(edge_cell) = self[kids[5]].facets()[2] {
53 edges[1] = self[edge_cell].is_tree()
54 }
55 if let Some(edge_cell) = self[kids[5]].facets()[5] {
56 edges[2] = self[edge_cell].is_tree()
57 }
58 if let Some(edge_cell) = self[kids[7]].facets()[5] {
59 if let Some(vertex_cell) = self[edge_cell].facets()[3] {
60 vertices[0] = self[vertex_cell].is_tree()
61 }
62 edges[3] = self[edge_cell].is_tree()
63 }
64 if let Some(edge_cell) = self[kids[3]].facets()[3] {
65 edges[4] = self[edge_cell].is_tree()
66 }
67 if let Some(edge_cell) = self[kids[7]].facets()[3] {
68 edges[5] = self[edge_cell].is_tree()
69 }
70 if let Some(edge_cell) = self[kids[1]].facets()[4] {
71 edges[6] = self[edge_cell].is_tree()
72 }
73 if let Some(edge_cell) = self[kids[3]].facets()[4] {
74 if let Some(vertex_cell) = self[edge_cell].facets()[3] {
75 vertices[1] = self[vertex_cell].is_tree()
76 }
77 edges[7] = self[edge_cell].is_tree()
78 }
79 }
80 self[kids[1]].is_tree()
81 || self[kids[3]].is_tree()
82 || self[kids[5]].is_tree()
83 || self[kids[7]].is_tree()
84 || edges.into_iter().any(|edge| edge)
85 || vertices.into_iter().any(|vertex| vertex)
86 }
87 1 => {
88 if strong {
89 if let Some(edge_cell) = self[kids[2]].facets()[3] {
90 edges[0] = self[edge_cell].is_tree()
91 }
92 if let Some(edge_cell) = self[kids[6]].facets()[3] {
93 edges[1] = self[edge_cell].is_tree()
94 }
95 if let Some(edge_cell) = self[kids[4]].facets()[5] {
96 if let Some(vertex_cell) = self[edge_cell].facets()[2] {
97 vertices[0] = self[vertex_cell].is_tree()
98 }
99 edges[2] = self[edge_cell].is_tree()
100 }
101 if let Some(edge_cell) = self[kids[6]].facets()[5] {
102 edges[3] = self[edge_cell].is_tree()
103 }
104 if let Some(edge_cell) = self[kids[0]].facets()[2] {
105 edges[4] = self[edge_cell].is_tree()
106 }
107 if let Some(edge_cell) = self[kids[4]].facets()[2] {
108 edges[5] = self[edge_cell].is_tree()
109 }
110 if let Some(edge_cell) = self[kids[0]].facets()[4] {
111 if let Some(vertex_cell) = self[edge_cell].facets()[2] {
112 vertices[1] = self[vertex_cell].is_tree()
113 }
114 edges[6] = self[edge_cell].is_tree()
115 }
116 if let Some(edge_cell) = self[kids[2]].facets()[4] {
117 edges[7] = self[edge_cell].is_tree()
118 }
119 }
120 self[kids[0]].is_tree()
121 || self[kids[2]].is_tree()
122 || self[kids[4]].is_tree()
123 || self[kids[6]].is_tree()
124 || edges.into_iter().any(|edge| edge)
125 || vertices.into_iter().any(|vertex| vertex)
126 }
127 2 => {
128 if strong {
129 if let Some(edge_cell) = self[kids[3]].facets()[1] {
130 edges[0] = self[edge_cell].is_tree()
131 }
132 if let Some(edge_cell) = self[kids[7]].facets()[1] {
133 edges[1] = self[edge_cell].is_tree()
134 }
135 if let Some(edge_cell) = self[kids[6]].facets()[5] {
136 if let Some(vertex_cell) = self[edge_cell].facets()[0] {
137 vertices[0] = self[vertex_cell].is_tree()
138 }
139 edges[2] = self[edge_cell].is_tree()
140 }
141 if let Some(edge_cell) = self[kids[7]].facets()[5] {
142 edges[3] = self[edge_cell].is_tree()
143 }
144 if let Some(edge_cell) = self[kids[2]].facets()[0] {
145 edges[4] = self[edge_cell].is_tree()
146 }
147 if let Some(edge_cell) = self[kids[6]].facets()[0] {
148 edges[5] = self[edge_cell].is_tree()
149 }
150 if let Some(edge_cell) = self[kids[2]].facets()[4] {
151 if let Some(vertex_cell) = self[edge_cell].facets()[0] {
152 vertices[1] = self[vertex_cell].is_tree()
153 }
154 edges[6] = self[edge_cell].is_tree()
155 }
156 if let Some(edge_cell) = self[kids[3]].facets()[4] {
157 edges[7] = self[edge_cell].is_tree()
158 }
159 }
160 self[kids[2]].is_tree()
161 || self[kids[3]].is_tree()
162 || self[kids[6]].is_tree()
163 || self[kids[7]].is_tree()
164 || edges.into_iter().any(|edge: bool| edge)
165 || vertices.into_iter().any(|vertex| vertex)
166 }
167 3 => {
168 if strong {
169 if let Some(edge_cell) = self[kids[0]].facets()[0] {
170 edges[0] = self[edge_cell].is_tree()
171 }
172 if let Some(edge_cell) = self[kids[4]].facets()[0] {
173 edges[1] = self[edge_cell].is_tree()
174 }
175 if let Some(edge_cell) = self[kids[4]].facets()[5] {
176 edges[2] = self[edge_cell].is_tree()
177 }
178 if let Some(edge_cell) = self[kids[5]].facets()[5] {
179 if let Some(vertex_cell) = self[edge_cell].facets()[1] {
180 vertices[0] = self[vertex_cell].is_tree()
181 }
182 edges[3] = self[edge_cell].is_tree()
183 }
184 if let Some(edge_cell) = self[kids[1]].facets()[1] {
185 edges[4] = self[edge_cell].is_tree()
186 }
187 if let Some(edge_cell) = self[kids[5]].facets()[1] {
188 edges[5] = self[edge_cell].is_tree()
189 }
190 if let Some(edge_cell) = self[kids[0]].facets()[4] {
191 edges[6] = self[edge_cell].is_tree()
192 }
193 if let Some(edge_cell) = self[kids[1]].facets()[4] {
194 if let Some(vertex_cell) = self[edge_cell].facets()[1] {
195 vertices[1] = self[vertex_cell].is_tree()
196 }
197 edges[7] = self[edge_cell].is_tree()
198 }
199 }
200 self[kids[0]].is_tree()
201 || self[kids[1]].is_tree()
202 || self[kids[4]].is_tree()
203 || self[kids[5]].is_tree()
204 || edges.into_iter().any(|edge| edge)
205 || vertices.into_iter().any(|vertex| vertex)
206 }
207 4 => {
208 if strong {
209 if let Some(edge_cell) = self[kids[5]].facets()[1] {
210 edges[0] = self[edge_cell].is_tree()
211 }
212 if let Some(edge_cell) = self[kids[7]].facets()[1] {
213 edges[1] = self[edge_cell].is_tree()
214 }
215 if let Some(edge_cell) = self[kids[6]].facets()[3] {
216 edges[2] = self[edge_cell].is_tree()
217 }
218 if let Some(edge_cell) = self[kids[7]].facets()[3] {
219 edges[3] = self[edge_cell].is_tree()
220 }
221 if let Some(edge_cell) = self[kids[4]].facets()[0] {
222 edges[4] = self[edge_cell].is_tree()
223 }
224 if let Some(edge_cell) = self[kids[6]].facets()[0] {
225 edges[5] = self[edge_cell].is_tree()
226 }
227 if let Some(edge_cell) = self[kids[4]].facets()[2] {
228 edges[6] = self[edge_cell].is_tree()
229 }
230 if let Some(edge_cell) = self[kids[5]].facets()[2] {
231 edges[7] = self[edge_cell].is_tree()
232 }
233 }
234 edges.into_iter().any(|edge| edge)
235 || self[kids[4]].is_tree()
236 || self[kids[5]].is_tree()
237 || self[kids[6]].is_tree()
238 || self[kids[7]].is_tree()
239 }
240 5 => {
241 if strong {
242 if let Some(edge_cell) = self[kids[1]].facets()[1] {
243 edges[0] = self[edge_cell].is_tree()
244 }
245 if let Some(edge_cell) = self[kids[3]].facets()[1] {
246 edges[1] = self[edge_cell].is_tree()
247 }
248 if let Some(edge_cell) = self[kids[2]].facets()[3] {
249 edges[2] = self[edge_cell].is_tree()
250 }
251 if let Some(edge_cell) = self[kids[3]].facets()[3] {
252 edges[3] = self[edge_cell].is_tree()
253 }
254 if let Some(edge_cell) = self[kids[0]].facets()[0] {
255 edges[4] = self[edge_cell].is_tree()
256 }
257 if let Some(edge_cell) = self[kids[2]].facets()[0] {
258 edges[5] = self[edge_cell].is_tree()
259 }
260 if let Some(edge_cell) = self[kids[0]].facets()[2] {
261 edges[6] = self[edge_cell].is_tree()
262 }
263 if let Some(edge_cell) = self[kids[1]].facets()[2] {
264 edges[7] = self[edge_cell].is_tree()
265 }
266 }
267 edges.into_iter().any(|edge| edge)
268 || self[kids[0]].is_tree()
269 || self[kids[1]].is_tree()
270 || self[kids[2]].is_tree()
271 || self[kids[3]].is_tree()
272 }
273 _ => unreachable!(),
274 } {
275 subdivide = true;
276 break 'faces;
277 }
278 }
279 }
280 if subdivide {
281 self.subdivide(index.into()).unwrap();
282 balanced = false;
283 balanced_already = false;
284 subdivide = false;
285 }
286 }
287 index += 1;
288 }
289 if balanced {
290 break;
291 }
292 }
293 balanced_already
294 }
295 fn pair_up(&mut self, pairing: Pairing) -> Result<bool, &'static str> {
296 self.paired = pairing;
297 self.pair(pairing)
298 }
299}