1void _split_inform_references(uint32_t p_node_id) {
2 TNode &node = _nodes[p_node_id];
3 TLeaf &leaf = _node_get_leaf(node);
4
5 for (int n = 0; n < leaf.num_items; n++) {
6 uint32_t ref_id = leaf.get_item_ref_id(n);
7
8 ItemRef &ref = _refs[ref_id];
9 ref.tnode_id = p_node_id;
10 ref.item_id = n;
11 }
12}
13
14void _split_leaf_sort_groups_simple(int &num_a, int &num_b, uint16_t *group_a, uint16_t *group_b, const BVHABB_CLASS *temp_bounds, const BVHABB_CLASS full_bound) {
15 // special case for low leaf sizes .. should static compile out
16 if constexpr (MAX_ITEMS < 4) {
17 uint32_t ind = group_a[0];
18
19 // add to b
20 group_b[num_b++] = ind;
21
22 // remove from a
23 group_a[0] = group_a[num_a - 1];
24 num_a--;
25 return;
26 }
27
28 POINT center = full_bound.calculate_center();
29 POINT size = full_bound.calculate_size();
30
31 int order[POINT::AXIS_COUNT];
32
33 order[0] = size.min_axis_index();
34 order[POINT::AXIS_COUNT - 1] = size.max_axis_index();
35
36 static_assert(POINT::AXIS_COUNT <= 3, "BVH POINT::AXIS_COUNT has unexpected size");
37 if constexpr (POINT::AXIS_COUNT == 3) {
38 order[1] = 3 - (order[0] + order[2]);
39 }
40
41 // simplest case, split on the longest axis
42 int split_axis = order[0];
43 for (int a = 0; a < num_a; a++) {
44 uint32_t ind = group_a[a];
45
46 if (temp_bounds[ind].min.coord[split_axis] > center.coord[split_axis]) {
47 // add to b
48 group_b[num_b++] = ind;
49
50 // remove from a
51 group_a[a] = group_a[num_a - 1];
52 num_a--;
53
54 // do this one again, as it has been replaced
55 a--;
56 }
57 }
58
59 // detect when split on longest axis failed
60 int min_threshold = MAX_ITEMS / 4;
61 int min_group_size[POINT::AXIS_COUNT];
62 min_group_size[0] = MIN(num_a, num_b);
63 if (min_group_size[0] < min_threshold) {
64 // slow but sure .. first move everything back into a
65 for (int b = 0; b < num_b; b++) {
66 group_a[num_a++] = group_b[b];
67 }
68 num_b = 0;
69
70 // now calculate the best split
71 for (int axis = 1; axis < POINT::AXIS_COUNT; axis++) {
72 split_axis = order[axis];
73 int count = 0;
74
75 for (int a = 0; a < num_a; a++) {
76 uint32_t ind = group_a[a];
77
78 if (temp_bounds[ind].min.coord[split_axis] > center.coord[split_axis]) {
79 count++;
80 }
81 }
82
83 min_group_size[axis] = MIN(count, num_a - count);
84 } // for axis
85
86 // best axis
87 int best_axis = 0;
88 int best_min = min_group_size[0];
89 for (int axis = 1; axis < POINT::AXIS_COUNT; axis++) {
90 if (min_group_size[axis] > best_min) {
91 best_min = min_group_size[axis];
92 best_axis = axis;
93 }
94 }
95
96 // now finally do the split
97 if (best_min > 0) {
98 split_axis = order[best_axis];
99
100 for (int a = 0; a < num_a; a++) {
101 uint32_t ind = group_a[a];
102
103 if (temp_bounds[ind].min.coord[split_axis] > center.coord[split_axis]) {
104 // add to b
105 group_b[num_b++] = ind;
106
107 // remove from a
108 group_a[a] = group_a[num_a - 1];
109 num_a--;
110
111 // do this one again, as it has been replaced
112 a--;
113 }
114 }
115 } // if there was a split!
116 } // if the longest axis wasn't a good split
117
118 // special case, none crossed threshold
119 if (!num_b) {
120 uint32_t ind = group_a[0];
121
122 // add to b
123 group_b[num_b++] = ind;
124
125 // remove from a
126 group_a[0] = group_a[num_a - 1];
127 num_a--;
128 }
129 // opposite problem! :)
130 if (!num_a) {
131 uint32_t ind = group_b[0];
132
133 // add to a
134 group_a[num_a++] = ind;
135
136 // remove from b
137 group_b[0] = group_b[num_b - 1];
138 num_b--;
139 }
140}
141
142void _split_leaf_sort_groups(int &num_a, int &num_b, uint16_t *group_a, uint16_t *group_b, const BVHABB_CLASS *temp_bounds) {
143 BVHABB_CLASS groupb_aabb;
144 groupb_aabb.set_to_max_opposite_extents();
145 for (int n = 0; n < num_b; n++) {
146 int which = group_b[n];
147 groupb_aabb.merge(temp_bounds[which]);
148 }
149 BVHABB_CLASS groupb_aabb_new;
150
151 BVHABB_CLASS rest_aabb;
152
153 float best_size = FLT_MAX;
154 int best_candidate = -1;
155
156 // find most likely from a to move into b
157 for (int check = 0; check < num_a; check++) {
158 rest_aabb.set_to_max_opposite_extents();
159 groupb_aabb_new = groupb_aabb;
160
161 // find aabb of all the rest
162 for (int rest = 0; rest < num_a; rest++) {
163 if (rest == check) {
164 continue;
165 }
166
167 int which = group_a[rest];
168 rest_aabb.merge(temp_bounds[which]);
169 }
170
171 groupb_aabb_new.merge(temp_bounds[group_a[check]]);
172
173 // now compare the sizes
174 float size = groupb_aabb_new.get_area() + rest_aabb.get_area();
175 if (size < best_size) {
176 best_size = size;
177 best_candidate = check;
178 }
179 }
180
181 // we should now have the best, move it from group a to group b
182 group_b[num_b++] = group_a[best_candidate];
183
184 // remove best candidate from group a
185 num_a--;
186 group_a[best_candidate] = group_a[num_a];
187}
188
189uint32_t split_leaf(uint32_t p_node_id, const BVHABB_CLASS &p_added_item_aabb) {
190 return split_leaf_complex(p_node_id, p_added_item_aabb);
191}
192
193// aabb is the new inserted node
194uint32_t split_leaf_complex(uint32_t p_node_id, const BVHABB_CLASS &p_added_item_aabb) {
195 VERBOSE_PRINT("split_leaf");
196
197 // note the tnode before and AFTER splitting may be a different address
198 // in memory because the vector could get relocated. So we need to reget
199 // the tnode after the split
200 BVH_ASSERT(_nodes[p_node_id].is_leaf());
201
202 // first create child leaf nodes
203 uint32_t *child_ids = (uint32_t *)alloca(sizeof(uint32_t) * MAX_CHILDREN);
204
205 for (int n = 0; n < MAX_CHILDREN; n++) {
206 // create node children
207 TNode *child_node = _nodes.request(child_ids[n]);
208
209 child_node->clear();
210
211 // back link to parent
212 child_node->parent_id = p_node_id;
213
214 // make each child a leaf node
215 node_make_leaf(child_ids[n]);
216 }
217
218 // don't get any leaves or nodes till AFTER the split
219 TNode &tnode = _nodes[p_node_id];
220 uint32_t orig_leaf_id = tnode.get_leaf_id();
221 const TLeaf &orig_leaf = _node_get_leaf(tnode);
222
223 // store the final child ids
224 for (int n = 0; n < MAX_CHILDREN; n++) {
225 tnode.children[n] = child_ids[n];
226 }
227
228 // mark as no longer a leaf node
229 tnode.num_children = MAX_CHILDREN;
230
231 // 2 groups, A and B, and assign children to each to split equally
232 int max_children = orig_leaf.num_items + 1; // plus 1 for the wildcard .. the item being added
233 //CRASH_COND(max_children > MAX_CHILDREN);
234
235 uint16_t *group_a = (uint16_t *)alloca(sizeof(uint16_t) * max_children);
236 uint16_t *group_b = (uint16_t *)alloca(sizeof(uint16_t) * max_children);
237
238 // we are copying the ABBs. This is ugly, but we need one extra for the inserted item...
239 BVHABB_CLASS *temp_bounds = (BVHABB_CLASS *)alloca(sizeof(BVHABB_CLASS) * max_children);
240
241 int num_a = max_children;
242 int num_b = 0;
243
244 // setup - start with all in group a
245 for (int n = 0; n < orig_leaf.num_items; n++) {
246 group_a[n] = n;
247 temp_bounds[n] = orig_leaf.get_aabb(n);
248 }
249 // wildcard
250 int wildcard = orig_leaf.num_items;
251
252 group_a[wildcard] = wildcard;
253 temp_bounds[wildcard] = p_added_item_aabb;
254
255 // we can choose here either an equal split, or just 1 in the new leaf
256 _split_leaf_sort_groups_simple(num_a, num_b, group_a, group_b, temp_bounds, tnode.aabb);
257
258 uint32_t wildcard_node = BVHCommon::INVALID;
259
260 // now there should be equal numbers in both groups
261 for (int n = 0; n < num_a; n++) {
262 int which = group_a[n];
263
264 if (which != wildcard) {
265 const BVHABB_CLASS &source_item_aabb = orig_leaf.get_aabb(which);
266 uint32_t source_item_ref_id = orig_leaf.get_item_ref_id(which);
267 //const Item &source_item = orig_leaf.get_item(which);
268 _node_add_item(tnode.children[0], source_item_ref_id, source_item_aabb);
269 } else {
270 wildcard_node = tnode.children[0];
271 }
272 }
273 for (int n = 0; n < num_b; n++) {
274 int which = group_b[n];
275
276 if (which != wildcard) {
277 const BVHABB_CLASS &source_item_aabb = orig_leaf.get_aabb(which);
278 uint32_t source_item_ref_id = orig_leaf.get_item_ref_id(which);
279 //const Item &source_item = orig_leaf.get_item(which);
280 _node_add_item(tnode.children[1], source_item_ref_id, source_item_aabb);
281 } else {
282 wildcard_node = tnode.children[1];
283 }
284 }
285
286 // now remove all items from the parent and replace with the child nodes
287 _leaves.free(orig_leaf_id);
288
289 // we should keep the references up to date!
290 for (int n = 0; n < MAX_CHILDREN; n++) {
291 _split_inform_references(tnode.children[n]);
292 }
293
294 refit_upward(p_node_id);
295
296 BVH_ASSERT(wildcard_node != BVHCommon::INVALID);
297 return wildcard_node;
298}
299