1void _debug_node_verify_bound(uint32_t p_node_id) {
2 TNode &node = _nodes[p_node_id];
3 BVHABB_CLASS abb_before = node.aabb;
4
5 node_update_aabb(node);
6
7 BVHABB_CLASS abb_after = node.aabb;
8 CRASH_COND(abb_before != abb_after);
9}
10
11void node_update_aabb(TNode &tnode) {
12 tnode.aabb.set_to_max_opposite_extents();
13 tnode.height = 0;
14
15 if (!tnode.is_leaf()) {
16 for (int n = 0; n < tnode.num_children; n++) {
17 uint32_t child_node_id = tnode.children[n];
18
19 // merge with child aabb
20 const TNode &tchild = _nodes[child_node_id];
21 tnode.aabb.merge(tchild.aabb);
22
23 // do heights at the same time
24 if (tchild.height > tnode.height) {
25 tnode.height = tchild.height;
26 }
27 }
28
29 // the height of a non leaf is always 1 bigger than the biggest child
30 tnode.height++;
31
32#ifdef BVH_CHECKS
33 if (!tnode.num_children) {
34 // the 'blank' aabb will screw up parent aabbs
35 WARN_PRINT("BVH_Tree::TNode no children, AABB is undefined");
36 }
37#endif
38 } else {
39 // leaf
40 const TLeaf &leaf = _node_get_leaf(tnode);
41
42 for (int n = 0; n < leaf.num_items; n++) {
43 tnode.aabb.merge(leaf.get_aabb(n));
44 }
45
46 // now the leaf items are unexpanded, we expand only in the node AABB
47 tnode.aabb.expand(_node_expansion);
48#ifdef BVH_CHECKS
49 if (!leaf.num_items) {
50 // the 'blank' aabb will screw up parent aabbs
51 WARN_PRINT("BVH_Tree::TLeaf no items, AABB is undefined");
52 }
53#endif
54 }
55}
56
57void refit_all(int p_tree_id) {
58 refit_downward(_root_node_id[p_tree_id]);
59}
60
61void refit_upward(uint32_t p_node_id) {
62 while (p_node_id != BVHCommon::INVALID) {
63 TNode &tnode = _nodes[p_node_id];
64 node_update_aabb(tnode);
65 p_node_id = tnode.parent_id;
66 }
67}
68
69void refit_upward_and_balance(uint32_t p_node_id, uint32_t p_tree_id) {
70 while (p_node_id != BVHCommon::INVALID) {
71 uint32_t before = p_node_id;
72 p_node_id = _logic_balance(p_node_id, p_tree_id);
73
74 if (before != p_node_id) {
75 VERBOSE_PRINT("REBALANCED!");
76 }
77
78 TNode &tnode = _nodes[p_node_id];
79
80 // update overall aabb from the children
81 node_update_aabb(tnode);
82
83 p_node_id = tnode.parent_id;
84 }
85}
86
87void refit_downward(uint32_t p_node_id) {
88 TNode &tnode = _nodes[p_node_id];
89
90 // do children first
91 if (!tnode.is_leaf()) {
92 for (int n = 0; n < tnode.num_children; n++) {
93 refit_downward(tnode.children[n]);
94 }
95 }
96
97 node_update_aabb(tnode);
98}
99
100// go down to the leaves, then refit upward
101void refit_branch(uint32_t p_node_id) {
102 // our function parameters to keep on a stack
103 struct RefitParams {
104 uint32_t node_id;
105 };
106
107 // most of the iterative functionality is contained in this helper class
108 BVH_IterativeInfo<RefitParams> ii;
109
110 // alloca must allocate the stack from this function, it cannot be allocated in the
111 // helper class
112 ii.stack = (RefitParams *)alloca(ii.get_alloca_stacksize());
113
114 // seed the stack
115 ii.get_first()->node_id = p_node_id;
116
117 RefitParams rp;
118
119 // while there are still more nodes on the stack
120 while (ii.pop(rp)) {
121 TNode &tnode = _nodes[rp.node_id];
122
123 // do children first
124 if (!tnode.is_leaf()) {
125 for (int n = 0; n < tnode.num_children; n++) {
126 uint32_t child_id = tnode.children[n];
127
128 // add to the stack
129 RefitParams *child = ii.request();
130 child->node_id = child_id;
131 }
132 } else {
133 // leaf .. only refit upward if dirty
134 TLeaf &leaf = _node_get_leaf(tnode);
135 if (leaf.is_dirty()) {
136 leaf.set_dirty(false);
137 refit_upward(p_node_id);
138 }
139 }
140 } // while more nodes to pop
141}
142