index : binary-tree

diff --git a/notes.txt b/notes.txt new file mode 100644 index 0000000..d6eca8a --- /dev/null +++ b/notes.txt @@ -0,0 +1,88 @@ tree_refit :: (tree: *Tree, start_index: int) {     index := start_index;     while index > 0 {         i_left   := 2 * index + 1;         i_right  := 2 * index + 2;         i_parent := cast(int)floor((index - 1.0) / 2.0);         // Refit this node to enclose both children         tree.data[index].bounds = aabb_merge(tree.data[i_left].bounds,                                              tree.data[i_right].bounds);         index = i_parent;     }     // Refit the root (index 0) separately, since the while loop stops before it     i_left  := 1;     i_right := 2;     tree.data[0].bounds = aabb_merge(tree.data[i_left].bounds,                                      tree.data[i_right].bounds); } tree_rotate :: (tree: *Tree, index_b: int) {     // B is the node we're considering rotating at     // Its parent is A, its sibling is C     i_a := cast(int)floor((index_b - 1.0) / 2.0); // parent     i_c := (index_b % 2 == 1) ? index_b + 1 : index_b - 1; // sibling     i_d := 2 * index_b + 1; // B's left child     i_e := 2 * index_b + 2; // B's right child     if i_d >= tree.data.count return; // B is a leaf, nothing to rotate     // Compute cost of current arrangement vs swapping D or E up     cost_current := surface_area(tree.data[i_b]) + surface_area(tree.data[i_c]);     cost_swap_d  := surface_area(merge_bounds(tree.data[i_e], tree.data[i_c])) + surface_area(tree.data[i_d]);     cost_swap_e  := surface_area(merge_bounds(tree.data[i_d], tree.data[i_c])) + surface_area(tree.data[i_e]);     if cost_current <= cost_swap_d && cost_current <= cost_swap_e return; // already optimal     if cost_swap_d < cost_swap_e {         // Swap D and C: just swap their data in the array         tmp := tree.data[i_d];         tree.data[i_d] = tree.data[i_c];         tree.data[i_c] = tmp;         // Refit B since its children changed         tree.data[index_b] = merge_bounds(tree.data[i_d], tree.data[i_e]);     } else {         // Swap E and C         tmp := tree.data[i_e];         tree.data[i_e] = tree.data[i_c];         tree.data[i_c] = tmp;         // Refit B         tree.data[index_b] = merge_bounds(tree.data[i_d], tree.data[i_e]);     }     // A's bounds didn't change since D and C are both still under it } tree_collapse :: (tree: *Tree, parent_index: int) {     i_left  := 2 * parent_index + 1;     i_right := 2 * parent_index + 2;     // Sanity check — only collapse if both children are leaves     // (i.e. their own children slots are empty)     assert(tree_is_leaf(tree, i_left));     assert(tree_is_leaf(tree, i_right));     tree.data[i_left]  = EMPTY_NODE;     tree.data[i_right] = EMPTY_NODE;     // Parent is now a leaf — update its bounding volume or value here } tree_is_leaf :: (tree: Tree, index: int) -> bool {     i_left  := 2 * index + 1;     i_right := 2 * index + 2;     if i_left  >= tree.data.count then return true;     if i_right >= tree.data.count then return true;     return is_empty(tree.data[i_left]) && is_empty(tree.data[i_right]); }