index : binary-tree

        

            
            
        
        
0
1
2
3tree_refit :: (tree: *Tree, start_index: int) {
4    index := start_index;
5
6    while index > 0 {
7        i_left   := 2 * index + 1;
8        i_right  := 2 * index + 2;
9        i_parent := cast(int)floor((index - 1.0) / 2.0);
10
11        // Refit this node to enclose both children
12        tree.data[index].bounds = aabb_merge(tree.data[i_left].bounds,
13                                             tree.data[i_right].bounds);
14
15        index = i_parent;
16    }
17
18    // Refit the root (index 0) separately, since the while loop stops before it
19    i_left  := 1;
20    i_right := 2;
21    tree.data[0].bounds = aabb_merge(tree.data[i_left].bounds,
22                                     tree.data[i_right].bounds);
23}
24
25
26
27tree_rotate :: (tree: *Tree, index_b: int) {
28    // B is the node we're considering rotating at
29    // Its parent is A, its sibling is C
30    i_a := cast(int)floor((index_b - 1.0) / 2.0); // parent
31    i_c := (index_b % 2 == 1) ? index_b + 1 : index_b - 1; // sibling
32
33    i_d := 2 * index_b + 1; // B's left child
34    i_e := 2 * index_b + 2; // B's right child
35
36    if i_d >= tree.data.count return; // B is a leaf, nothing to rotate
37
38    // Compute cost of current arrangement vs swapping D or E up
39    cost_current := surface_area(tree.data[i_b]) + surface_area(tree.data[i_c]);
40    cost_swap_d  := surface_area(merge_bounds(tree.data[i_e], tree.data[i_c])) + surface_area(tree.data[i_d]);
41    cost_swap_e  := surface_area(merge_bounds(tree.data[i_d], tree.data[i_c])) + surface_area(tree.data[i_e]);
42
43    if cost_current <= cost_swap_d && cost_current <= cost_swap_e return; // already optimal
44
45    if cost_swap_d < cost_swap_e {
46        // Swap D and C: just swap their data in the array
47        tmp := tree.data[i_d];
48        tree.data[i_d] = tree.data[i_c];
49        tree.data[i_c] = tmp;
50        // Refit B since its children changed
51        tree.data[index_b] = merge_bounds(tree.data[i_d], tree.data[i_e]);
52    } else {
53        // Swap E and C
54        tmp := tree.data[i_e];
55        tree.data[i_e] = tree.data[i_c];
56        tree.data[i_c] = tmp;
57        // Refit B
58        tree.data[index_b] = merge_bounds(tree.data[i_d], tree.data[i_e]);
59    }
60    // A's bounds didn't change since D and C are both still under it
61}
62
63
64tree_collapse :: (tree: *Tree, parent_index: int) {
65    i_left  := 2 * parent_index + 1;
66    i_right := 2 * parent_index + 2;
67
68    // Sanity check — only collapse if both children are leaves
69    // (i.e. their own children slots are empty)
70    assert(tree_is_leaf(tree, i_left));
71    assert(tree_is_leaf(tree, i_right));
72
73    tree.data[i_left]  = EMPTY_NODE;
74    tree.data[i_right] = EMPTY_NODE;
75
76    // Parent is now a leaf — update its bounding volume or value here
77}
78
79tree_is_leaf :: (tree: Tree, index: int) -> bool {
80    i_left  := 2 * index + 1;
81    i_right := 2 * index + 2;
82    if i_left  >= tree.data.count then return true;
83    if i_right >= tree.data.count then return true;
84    return is_empty(tree.data[i_left]) && is_empty(tree.data[i_right]);
85}
86
87
88