1
2public:
3struct ItemRef {
4 uint32_t tnode_id; // -1 is invalid
5 uint32_t item_id; // in the leaf
6
7 bool is_active() const { return tnode_id != BVHCommon::INACTIVE; }
8 void set_inactive() {
9 tnode_id = BVHCommon::INACTIVE;
10 item_id = BVHCommon::INACTIVE;
11 }
12};
13
14// extra info kept in separate parallel list to the references,
15// as this is less used as keeps cache better
16struct ItemExtra {
17 // Before doing user defined pairing checks (especially in the find_leavers function),
18 // we may want to check that two items have compatible tree ids and tree masks,
19 // as if they are incompatible they should not pair / collide.
20 bool are_item_trees_compatible(const ItemExtra &p_other) const {
21 uint32_t other_type = 1 << p_other.tree_id;
22 if (tree_collision_mask & other_type) {
23 return true;
24 }
25 uint32_t our_type = 1 << tree_id;
26 if (p_other.tree_collision_mask & our_type) {
27 return true;
28 }
29 return false;
30 }
31
32 // There can be multiple user defined trees
33 uint32_t tree_id;
34
35 // Defines which trees this item should collision check against.
36 // 1 << tree_id, and normally items would collide against there own
37 // tree (but not always).
38 uint32_t tree_collision_mask;
39
40 uint32_t last_updated_tick;
41 int32_t subindex;
42
43 T *userdata;
44
45 // the active reference is a separate list of which references
46 // are active so that we can slowly iterate through it over many frames for
47 // slow optimize.
48 uint32_t active_ref_id;
49};
50
51// tree leaf
52struct TLeaf {
53 uint16_t num_items;
54
55private:
56 uint16_t dirty;
57 // separate data orientated lists for faster SIMD traversal
58 uint32_t item_ref_ids[MAX_ITEMS];
59 BVHABB_CLASS aabbs[MAX_ITEMS];
60
61public:
62 // accessors
63 BVHABB_CLASS &get_aabb(uint32_t p_id) {
64 BVH_ASSERT(p_id < MAX_ITEMS);
65 return aabbs[p_id];
66 }
67 const BVHABB_CLASS &get_aabb(uint32_t p_id) const {
68 BVH_ASSERT(p_id < MAX_ITEMS);
69 return aabbs[p_id];
70 }
71
72 uint32_t &get_item_ref_id(uint32_t p_id) {
73 BVH_ASSERT(p_id < MAX_ITEMS);
74 return item_ref_ids[p_id];
75 }
76 const uint32_t &get_item_ref_id(uint32_t p_id) const {
77 BVH_ASSERT(p_id < MAX_ITEMS);
78 return item_ref_ids[p_id];
79 }
80
81 bool is_dirty() const { return dirty; }
82 void set_dirty(bool p) { dirty = p; }
83
84 void clear() {
85 num_items = 0;
86 set_dirty(true);
87 }
88 bool is_full() const { return num_items >= MAX_ITEMS; }
89
90 void remove_item_unordered(uint32_t p_id) {
91 BVH_ASSERT(p_id < num_items);
92 num_items--;
93 aabbs[p_id] = aabbs[num_items];
94 item_ref_ids[p_id] = item_ref_ids[num_items];
95 }
96
97 uint32_t request_item() {
98 if (num_items < MAX_ITEMS) {
99 uint32_t id = num_items;
100 num_items++;
101 return id;
102 }
103#ifdef DEV_ENABLED
104 return -1;
105#else
106 ERR_FAIL_V_MSG(0, "BVH request_item error.");
107#endif
108 }
109};
110
111// tree node
112struct TNode {
113 BVHABB_CLASS aabb;
114 // either number of children if positive
115 // or leaf id if negative (leaf id 0 is disallowed)
116 union {
117 int32_t num_children;
118 int32_t neg_leaf_id;
119 };
120 uint32_t parent_id; // or -1
121 uint16_t children[MAX_CHILDREN];
122
123 // height in the tree, where leaves are 0, and all above are 1+
124 // (or the highest where there is a tie off)
125 int32_t height;
126
127 bool is_leaf() const { return num_children < 0; }
128 void set_leaf_id(int id) { neg_leaf_id = -id; }
129 int get_leaf_id() const { return -neg_leaf_id; }
130
131 void clear() {
132 num_children = 0;
133 parent_id = BVHCommon::INVALID;
134 height = 0; // or -1 for testing
135
136 // for safety set to improbable value
137 aabb.set_to_max_opposite_extents();
138
139 // other members are not blanked for speed .. they may be uninitialized
140 }
141
142 bool is_full_of_children() const { return num_children >= MAX_CHILDREN; }
143
144 void remove_child_internal(uint32_t child_num) {
145 children[child_num] = children[num_children - 1];
146 num_children--;
147 }
148
149 int find_child(uint32_t p_child_node_id) {
150 BVH_ASSERT(!is_leaf());
151
152 for (int n = 0; n < num_children; n++) {
153 if (children[n] == p_child_node_id) {
154 return n;
155 }
156 }
157
158 // not found
159 return -1;
160 }
161};
162
163// instead of using linked list we maintain
164// item references (for quick lookup)
165PooledList<ItemRef, uint32_t, true> _refs;
166PooledList<ItemExtra, uint32_t, true> _extra;
167PooledList<ItemPairs> _pairs;
168
169// these 2 are not in sync .. nodes != leaves!
170PooledList<TNode, uint32_t, true> _nodes;
171PooledList<TLeaf, uint32_t, true> _leaves;
172
173// we can maintain an un-ordered list of which references are active,
174// in order to do a slow incremental optimize of the tree over each frame.
175// This will work best if dynamic objects and static objects are in a different tree.
176LocalVector<uint32_t, uint32_t, true> _active_refs;
177uint32_t _current_active_ref = 0;
178
179// instead of translating directly to the userdata output,
180// we keep an intermediate list of hits as reference IDs, which can be used
181// for pairing collision detection
182LocalVector<uint32_t, uint32_t, true> _cull_hits;
183
184// We can now have a user definable number of trees.
185// This allows using e.g. a non-pairable and pairable tree,
186// which can be more efficient for example, if we only need check non pairable against the pairable tree.
187// It also may be more efficient in terms of separating static from dynamic objects, by reducing housekeeping.
188// However this is a trade off, as there is a cost of traversing two trees.
189uint32_t _root_node_id[NUM_TREES];
190
191// these values may need tweaking according to the project
192// the bound of the world, and the average velocities of the objects
193
194// node expansion is important in the rendering tree
195// larger values give less re-insertion as items move...
196// but on the other hand over estimates the bounding box of nodes.
197// we can either use auto mode, where the expansion is based on the root node size, or specify manually
198real_t _node_expansion = 0.5;
199bool _auto_node_expansion = true;
200
201// pairing expansion important for physics pairing
202// larger values gives more 'sticky' pairing, and is less likely to exhibit tunneling
203// we can either use auto mode, where the expansion is based on the root node size, or specify manually
204real_t _pairing_expansion = 0.1;
205
206#ifdef BVH_ALLOW_AUTO_EXPANSION
207bool _auto_pairing_expansion = true;
208#endif
209
210// when using an expanded bound, we must detect the condition where a new AABB
211// is significantly smaller than the expanded bound, as this is a special case where we
212// should override the optimization and create a new expanded bound.
213// This threshold is derived from the _pairing_expansion, and should be recalculated
214// if _pairing_expansion is changed.
215real_t _aabb_shrinkage_threshold = 0.0;
216