add player guide
[carveJwlIkooP6JGAAIwe30JlM.git] / bvh.h
1 /*
2 * Copyright (C) 2021-2022 Mt.ZERO Software, Harry Godden - All Rights Reserved
3 */
4
5 #ifndef BVH_H
6 #define BVH_H
7
8 #include "vg/vg_mem.h"
9 #include "vg/vg_m.h"
10 #include "vg/vg_lines.h"
11
12 /*
13 * Usage:
14 *
15 * create a bh_system with functions filled out for expand, centroid, and swap.
16 * optionally include item_debug and cast_ray functions if needed, otherwise,
17 * set them to null
18 *
19 * create a bh_tree struct with:
20 * user: a pointer back the base of the data you are ordering
21 * system: the system we created above which will deal with the data
22 *
23 * call bh_create( bh_tree *bh, u32 item_count )
24 * VG_STATIC int bh_ray( bh_tree *bh, u32 inode, v3f co, v3f dir, ray_hit *hit )
25 * VG_STATIC int bh_select( bh_tree *bh, boxf box, u32 *buffer, int len )
26 */
27
28 typedef struct bh_node bh_node;
29 typedef struct bh_tree bh_tree;
30 typedef struct bh_system bh_system;
31
32 typedef struct ray_hit ray_hit;
33 struct ray_hit{
34 float dist;
35 u32 *tri;
36 v3f pos, normal;
37 };
38
39 struct bh_tree{
40 u32 node_count;
41
42 bh_system *system;
43 void *user;
44 u32 max_per_leaf;
45
46 struct bh_node
47 {
48 boxf bbx;
49
50 /* if il is 0, this is a leaf */
51 int il, count;
52 union{ int ir, start; };
53 }
54 nodes[];
55 };
56
57 struct bh_system{
58 void (*expand_bound)( void *user, boxf bound, u32 item_index );
59 float (*item_centroid)( void *user, u32 item_index, int axis );
60 void (*item_closest)( void *user, u32 item_index, v3f point, v3f closest );
61 void (*item_swap)( void *user, u32 ia, u32 ib );
62
63 /*
64 * Optional:
65 * item_debug - draw this item quickly usually with lines
66 * cast_ray - shoot a ray against the object, if this is not set,
67 * raycasts will simply return the hit on the bvh node
68 */
69
70 void (*item_debug)( void *user, u32 item_index );
71 int (*cast_ray)( void *user, u32 index, v3f co, v3f dir, ray_hit *hit );
72 };
73
74 VG_STATIC void bh_update_bounds( bh_tree *bh, u32 inode ){
75 bh_node *node = &bh->nodes[ inode ];
76
77 box_init_inf( node->bbx );
78 for( u32 i=0; i<node->count; i++ ){
79 u32 idx = node->start+i;
80 bh->system->expand_bound( bh->user, node->bbx, idx );
81 }
82 }
83
84 VG_STATIC void bh_subdivide( bh_tree *bh, u32 inode ){
85 bh_node *node = &bh->nodes[ inode ];
86
87 if( node->count <= bh->max_per_leaf )
88 return;
89
90 v3f extent;
91 v3_sub( node->bbx[1], node->bbx[0], extent );
92
93 int axis = 0;
94 if( extent[1] > extent[0] ) axis = 1;
95 if( extent[2] > extent[axis] ) axis = 2;
96
97 float split = node->bbx[0][axis] + extent[axis]*0.5f;
98 float avg = 0.0;
99 for( u32 t=0; t<node->count; t++ )
100 {
101 u32 idx = node->start+t;
102 avg += bh->system->item_centroid( bh->user, idx, axis );
103 }
104 avg /= (float)node->count;
105 split = avg;
106
107
108 i32 i = node->start,
109 j = i + node->count-1;
110
111 while( i <= j ){
112 if( bh->system->item_centroid( bh->user, i, axis ) < split )
113 i ++;
114 else{
115 bh->system->item_swap( bh->user, i, j );
116 j --;
117 }
118 }
119
120 u32 left_count = i - node->start;
121 if( left_count == 0 || left_count == node->count ) return;
122
123 u32 il = bh->node_count ++,
124 ir = bh->node_count ++;
125
126 bh_node *lnode = &bh->nodes[il],
127 *rnode = &bh->nodes[ir];
128
129 lnode->start = node->start;
130 lnode->count = left_count;
131 rnode->start = i;
132 rnode->count = node->count - left_count;
133
134 node->il = il;
135 node->ir = ir;
136 node->count = 0;
137
138 bh_update_bounds( bh, il );
139 bh_update_bounds( bh, ir );
140 bh_subdivide( bh, il );
141 bh_subdivide( bh, ir );
142 }
143
144 VG_STATIC bh_tree *bh_create( void *lin_alloc, bh_system *system,
145 void *user, u32 item_count, u32 max_per_leaf ){
146 assert( max_per_leaf > 0 );
147
148 u32 alloc_count = VG_MAX( 1, item_count );
149
150 u32 totsize = sizeof(bh_tree) + sizeof(bh_node)*(alloc_count*2-1);
151 bh_tree *bh = vg_linear_alloc( lin_alloc, vg_align8(totsize) );
152 bh->system = system;
153 bh->user = user;
154 bh->max_per_leaf = max_per_leaf;
155
156 bh_node *root = &bh->nodes[0];
157 bh->node_count = 1;
158
159 root->il = 0;
160 root->ir = 0;
161 root->count = item_count;
162 root->start = 0;
163
164 bh_update_bounds( bh, 0 );
165
166 if( item_count > 2 )
167 bh_subdivide( bh, 0 );
168
169 totsize = vg_align8(sizeof(bh_tree) + sizeof(bh_node) * bh->node_count);
170 bh = vg_linear_resize( lin_alloc, bh, totsize );
171
172 vg_success( "BVH done, size: %u/%u\n", bh->node_count, (alloc_count*2-1) );
173 return bh;
174 }
175
176 /*
177 * Draw items in this leaf node.
178 * *item_debug() must be set!
179 */
180 VG_STATIC void bh_debug_leaf( bh_tree *bh, bh_node *node ){
181 vg_line_boxf( node->bbx, 0xff00ff00 );
182
183 if( bh->system->item_debug ){
184 for( u32 i=0; i<node->count; i++ ){
185 u32 idx = node->start+i;
186 bh->system->item_debug( bh->user, idx );
187 }
188 }
189 }
190
191 /*
192 * Trace the bh tree all the way down to the leaf nodes where pos is inside
193 */
194 VG_STATIC void bh_debug_trace( bh_tree *bh, u32 inode, v3f pos, u32 colour ){
195 bh_node *node = &bh->nodes[ inode ];
196
197 if( (pos[0] >= node->bbx[0][0] && pos[0] <= node->bbx[1][0]) &&
198 (pos[2] >= node->bbx[0][2] && pos[2] <= node->bbx[1][2]) )
199 {
200 if( !node->count ){
201 vg_line_boxf( node->bbx, colour );
202
203 bh_debug_trace( bh, node->il, pos, colour );
204 bh_debug_trace( bh, node->ir, pos, colour );
205 }
206 else{
207 if( bh->system->item_debug )
208 bh_debug_leaf( bh, node );
209 }
210 }
211 }
212
213 VG_STATIC int bh_ray( bh_tree *bh, v3f co, v3f dir, ray_hit *hit ){
214 if( bh->node_count < 2 )
215 return 0;
216
217 int count = 0;
218 u32 stack[100];
219 u32 depth = 2;
220
221 stack[0] = 0;
222 stack[1] = bh->nodes[0].il;
223 stack[2] = bh->nodes[0].ir;
224
225 v3f dir_inv;
226 v3_div( (v3f){1.0f,1.0f,1.0f}, dir, dir_inv );
227
228 while(depth){
229 bh_node *inode = &bh->nodes[ stack[depth] ];
230 if( ray_aabb1( inode->bbx, co, dir_inv, hit->dist ) ){
231 if( inode->count ){
232 for( u32 i=0; i<inode->count; i++ ){
233 u32 idx = inode->start+i;
234
235 if( bh->system->cast_ray )
236 count += bh->system->cast_ray( bh->user, idx, co, dir, hit );
237 else
238 count ++;
239 }
240
241 depth --;
242 }
243 else{
244 if( depth+1 >= vg_list_size(stack) ){
245 vg_error( "Maximum stack reached!\n" );
246 return count;
247 }
248
249 stack[depth] = inode->il;
250 stack[depth+1] = inode->ir;
251 depth ++;
252 }
253 }
254 else{
255 depth --;
256 }
257 }
258
259 return count;
260 }
261
262 typedef struct bh_iter bh_iter;
263 struct bh_iter{
264 struct {
265 i32 id, depth;
266 }
267 stack[64];
268
269 enum bh_query_type{
270 k_bh_query_box,
271 k_bh_query_ray
272 }
273 query;
274
275 union{
276 struct{
277 boxf box;
278 }
279 box;
280
281 struct{
282 v3f co, inv_dir;
283 f32 max_dist;
284 }
285 ray;
286 };
287
288 i32 depth, i;
289 };
290
291 VG_STATIC void bh_iter_init_box( i32 root, bh_iter *it, boxf box ){
292 it->query = k_bh_query_box;
293 it->stack[0].id = root;
294 it->stack[0].depth = 0;
295 it->depth = 0;
296 it->i = 0;
297
298 box_copy( box, it->box.box );
299 }
300
301 VG_STATIC void bh_iter_init_ray( i32 root, bh_iter *it, v3f co,
302 v3f dir, f32 max_dist ){
303 it->query = k_bh_query_ray;
304 it->stack[0].id = root;
305 it->stack[0].depth = 0;
306 it->depth = 0;
307 it->i = 0;
308
309 v3_div( (v3f){1.0f,1.0f,1.0f}, dir, it->ray.inv_dir );
310 v3_copy( co, it->ray.co );
311 it->ray.max_dist = max_dist;
312 }
313
314 VG_STATIC i32 bh_next( bh_tree *bh, bh_iter *it, i32 *em ){
315 while( it->depth >= 0 ){
316 bh_node *inode = &bh->nodes[ it->stack[it->depth].id ];
317
318 /* Only process overlapping nodes */
319 i32 q = 0;
320
321 if( it->query == k_bh_query_box )
322 q = box_overlap( inode->bbx, it->box.box );
323 else
324 q = ray_aabb1( inode->bbx, it->ray.co,
325 it->ray.inv_dir, it->ray.max_dist );
326
327 if( !q ){
328 it->depth --;
329 continue;
330 }
331
332 if( inode->count ){
333 if( it->i < inode->count ){
334 *em = inode->start+it->i;
335 it->i ++;
336 return 1;
337 }
338 else{
339 it->depth --;
340 it->i = 0;
341 }
342 }
343 else{
344 if( it->depth+1 >= vg_list_size(it->stack) ){
345 vg_error( "Maximum stack reached!\n" );
346 return 0;
347 }
348
349 it->stack[it->depth ].id = inode->il;
350 it->stack[it->depth+1].id = inode->ir;
351 it->depth ++;
352 it->i = 0;
353 }
354 }
355
356 return 0;
357 }
358
359 VG_STATIC int bh_closest_point( bh_tree *bh, v3f pos,
360 v3f closest, float max_dist )
361 {
362 if( bh->node_count < 2 )
363 return -1;
364
365 max_dist = max_dist*max_dist;
366
367 int queue[ 128 ],
368 depth = 0,
369 best_item = -1;
370
371 queue[0] = 0;
372
373 while( depth >= 0 ){
374 bh_node *inode = &bh->nodes[ queue[depth] ];
375
376 v3f p1;
377 closest_point_aabb( pos, inode->bbx, p1 );
378
379 /* branch into node if its closer than current best */
380 float node_dist = v3_dist2( pos, p1 );
381 if( node_dist < max_dist ){
382 if( inode->count ){
383 for( int i=0; i<inode->count; i++ ){
384 v3f p2;
385 bh->system->item_closest( bh->user, inode->start+i, pos, p2 );
386
387 float item_dist = v3_dist2( pos, p2 );
388 if( item_dist < max_dist ){
389 max_dist = item_dist;
390 v3_copy( p2, closest );
391 best_item = inode->start+i;
392 }
393 }
394
395 depth --;
396 }
397 else{
398 queue[depth] = inode->il;
399 queue[depth+1] = inode->ir;
400
401 depth ++;
402 }
403 }
404 else
405 depth --;
406 }
407
408 return best_item;
409 }
410
411 #endif /* BVH_H */