ce7fbe078e46ee1b126289307f718cace03bb85e
2 * Copyright (C) 2021-2022 Mt.ZERO Software, Harry Godden - All Rights Reserved
10 #include "vg/vg_lines.h"
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,
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
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 )
28 typedef struct bh_node bh_node
;
29 typedef struct bh_tree bh_tree
;
30 typedef struct bh_system bh_system
;
32 typedef struct ray_hit ray_hit
;
50 /* if il is 0, this is a leaf */
52 union{ int ir
, start
; };
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
);
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
70 void (*item_debug
)( void *user
, u32 item_index
);
71 int (*cast_ray
)( void *user
, u32 index
, v3f co
, v3f dir
, ray_hit
*hit
);
74 VG_STATIC
void bh_update_bounds( bh_tree
*bh
, u32 inode
){
75 bh_node
*node
= &bh
->nodes
[ inode
];
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
);
84 VG_STATIC
void bh_subdivide( bh_tree
*bh
, u32 inode
){
85 bh_node
*node
= &bh
->nodes
[ inode
];
87 if( node
->count
<= bh
->max_per_leaf
)
91 v3_sub( node
->bbx
[1], node
->bbx
[0], extent
);
94 if( extent
[1] > extent
[0] ) axis
= 1;
95 if( extent
[2] > extent
[axis
] ) axis
= 2;
97 float split
= node
->bbx
[0][axis
] + extent
[axis
]*0.5f
;
99 for( u32 t
=0; t
<node
->count
; t
++ )
101 u32 idx
= node
->start
+t
;
102 avg
+= bh
->system
->item_centroid( bh
->user
, idx
, axis
);
104 avg
/= (float)node
->count
;
109 j
= i
+ node
->count
-1;
112 if( bh
->system
->item_centroid( bh
->user
, i
, axis
) < split
)
115 bh
->system
->item_swap( bh
->user
, i
, j
);
120 u32 left_count
= i
- node
->start
;
121 if( left_count
== 0 || left_count
== node
->count
) return;
123 u32 il
= bh
->node_count
++,
124 ir
= bh
->node_count
++;
126 bh_node
*lnode
= &bh
->nodes
[il
],
127 *rnode
= &bh
->nodes
[ir
];
129 lnode
->start
= node
->start
;
130 lnode
->count
= left_count
;
132 rnode
->count
= node
->count
- left_count
;
138 bh_update_bounds( bh
, il
);
139 bh_update_bounds( bh
, ir
);
140 bh_subdivide( bh
, il
);
141 bh_subdivide( bh
, ir
);
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 );
148 u32 alloc_count
= VG_MAX( 1, item_count
);
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
) );
154 bh
->max_per_leaf
= max_per_leaf
;
156 bh_node
*root
= &bh
->nodes
[0];
161 root
->count
= item_count
;
164 bh_update_bounds( bh
, 0 );
167 bh_subdivide( bh
, 0 );
169 totsize
= vg_align8(sizeof(bh_tree
) + sizeof(bh_node
) * bh
->node_count
);
170 bh
= vg_linear_resize( lin_alloc
, bh
, totsize
);
172 vg_success( "BVH done, size: %u/%u\n", bh
->node_count
, (alloc_count
*2-1) );
177 * Draw items in this leaf node.
178 * *item_debug() must be set!
180 VG_STATIC
void bh_debug_leaf( bh_tree
*bh
, bh_node
*node
){
181 vg_line_boxf( node
->bbx
, 0xff00ff00 );
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
);
192 * Trace the bh tree all the way down to the leaf nodes where pos is inside
194 VG_STATIC
void bh_debug_trace( bh_tree
*bh
, u32 inode
, v3f pos
, u32 colour
){
195 bh_node
*node
= &bh
->nodes
[ inode
];
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]) )
201 vg_line_boxf( node
->bbx
, colour
);
203 bh_debug_trace( bh
, node
->il
, pos
, colour
);
204 bh_debug_trace( bh
, node
->ir
, pos
, colour
);
207 if( bh
->system
->item_debug
)
208 bh_debug_leaf( bh
, node
);
214 VG_STATIC
int bh_ray( bh_tree
*bh
, v3f co
, v3f dir
, ray_hit
*hit
){
215 if( bh
->node_count
< 2 )
223 stack
[1] = bh
->nodes
[0].il
;
224 stack
[2] = bh
->nodes
[0].ir
;
227 v3_div( (v3f
){1.0f
,1.0f
,1.0f
}, dir
, dir_inv
);
230 bh_node
*inode
= &bh
->nodes
[ stack
[depth
] ];
231 if( ray_aabb1( inode
->bbx
, co
, dir_inv
, hit
->dist
) ){
233 for( u32 i
=0; i
<inode
->count
; i
++ ){
234 u32 idx
= inode
->start
+i
;
236 if( bh
->system
->cast_ray
)
237 count
+= bh
->system
->cast_ray( bh
->user
, idx
, co
, dir
, hit
);
245 if( depth
+1 >= vg_list_size(stack
) ){
246 vg_error( "Maximum stack reached!\n" );
250 stack
[depth
] = inode
->il
;
251 stack
[depth
+1] = inode
->ir
;
264 typedef struct bh_iter bh_iter
;
300 VG_STATIC
void bh_iter_init_generic( i32 root
, bh_iter
*it
){
301 it
->stack
[0].id
= root
;
302 it
->stack
[0].depth
= 0;
307 VG_STATIC
void bh_iter_init_box( i32 root
, bh_iter
*it
, boxf box
){
308 bh_iter_init_generic( root
, it
);
309 it
->query
= k_bh_query_box
;
311 box_copy( box
, it
->box
.box
);
314 VG_STATIC
void bh_iter_init_ray( i32 root
, bh_iter
*it
, v3f co
,
315 v3f dir
, f32 max_dist
){
316 bh_iter_init_generic( root
, it
);
317 it
->query
= k_bh_query_ray
;
319 v3_div( (v3f
){1.0f
,1.0f
,1.0f
}, dir
, it
->ray
.inv_dir
);
320 v3_copy( co
, it
->ray
.co
);
321 it
->ray
.max_dist
= max_dist
;
324 VG_STATIC
void bh_iter_init_range( i32 root
, bh_iter
*it
, v3f co
, f32 range
){
325 bh_iter_init_generic( root
, it
);
326 it
->query
= k_bh_query_range
;
328 v3_copy( co
, it
->range
.co
);
329 it
->range
.dist_sqr
= range
*range
;
332 /* NOTE: does not compute anything beyond the leaf level. element level tests
333 * should be implemented by the users code.
335 * this is like a 'broad phase only' deal.
337 VG_STATIC i32
bh_next( bh_tree
*bh
, bh_iter
*it
, i32
*em
){
338 while( it
->depth
>= 0 ){
339 bh_node
*inode
= &bh
->nodes
[ it
->stack
[it
->depth
].id
];
341 /* Only process overlapping nodes */
344 if( it
->i
) /* already checked */
347 if( it
->query
== k_bh_query_box
)
348 q
= box_overlap( inode
->bbx
, it
->box
.box
);
349 else if( it
->query
== k_bh_query_ray
)
350 q
= ray_aabb1( inode
->bbx
, it
->ray
.co
,
351 it
->ray
.inv_dir
, it
->ray
.max_dist
);
354 closest_point_aabb( it
->range
.co
, inode
->bbx
, nearest
);
356 if( v3_dist2( nearest
, it
->range
.co
) <= it
->range
.dist_sqr
)
367 if( it
->i
< inode
->count
){
368 *em
= inode
->start
+it
->i
;
378 if( it
->depth
+1 >= vg_list_size(it
->stack
) ){
379 vg_error( "Maximum stack reached!\n" );
383 it
->stack
[it
->depth
].id
= inode
->il
;
384 it
->stack
[it
->depth
+1].id
= inode
->ir
;
393 VG_STATIC
int bh_closest_point( bh_tree
*bh
, v3f pos
,
394 v3f closest
, float max_dist
)
396 if( bh
->node_count
< 2 )
399 max_dist
= max_dist
*max_dist
;
408 bh_node
*inode
= &bh
->nodes
[ queue
[depth
] ];
411 closest_point_aabb( pos
, inode
->bbx
, p1
);
413 /* branch into node if its closer than current best */
414 float node_dist
= v3_dist2( pos
, p1
);
415 if( node_dist
< max_dist
){
417 for( int i
=0; i
<inode
->count
; i
++ ){
419 bh
->system
->item_closest( bh
->user
, inode
->start
+i
, pos
, p2
);
421 float item_dist
= v3_dist2( pos
, p2
);
422 if( item_dist
< max_dist
){
423 max_dist
= item_dist
;
424 v3_copy( p2
, closest
);
425 best_item
= inode
->start
+i
;
432 queue
[depth
] = inode
->il
;
433 queue
[depth
+1] = inode
->ir
;