X-Git-Url: https://harrygodden.com/git/?a=blobdiff_plain;f=bvh.h;h=b04c3de2b95f38342259a85d54386854ce295488;hb=38514b4ba03412ad51df02dc2ba345e1be41005d;hp=1997bedc964dcb30c25fad9c8ffe08ba034c816a;hpb=f014a592925b224f846d8adfc6559539fae1a096;p=carveJwlIkooP6JGAAIwe30JlM.git diff --git a/bvh.h b/bvh.h index 1997bed..b04c3de 100644 --- a/bvh.h +++ b/bvh.h @@ -21,8 +21,8 @@ * system: the system we created above which will deal with the data * * call bh_create( bh_tree *bh, u32 item_count ) - * VG_STATIC int bh_ray( bh_tree *bh, u32 inode, v3f co, v3f dir, ray_hit *hit ) - * VG_STATIC int bh_select( bh_tree *bh, boxf box, u32 *buffer, int len ) + * static int bh_ray( bh_tree *bh, u32 inode, v3f co, v3f dir, ray_hit *hit ) + * static int bh_select( bh_tree *bh, boxf box, u32 *buffer, int len ) */ typedef struct bh_node bh_node; @@ -55,6 +55,7 @@ struct bh_tree{ }; struct bh_system{ + u32 system_type; void (*expand_bound)( void *user, boxf bound, u32 item_index ); float (*item_centroid)( void *user, u32 item_index, int axis ); void (*item_closest)( void *user, u32 item_index, v3f point, v3f closest ); @@ -71,17 +72,24 @@ struct bh_system{ int (*cast_ray)( void *user, u32 index, v3f co, v3f dir, ray_hit *hit ); }; -VG_STATIC void bh_update_bounds( bh_tree *bh, u32 inode ){ +static float scene_bh_centroid( void *user, u32 item_index, int axis ); +static void scene_bh_swap( void *user, u32 ia, u32 ib ); +static void scene_bh_expand_bound( void *user, boxf bound, u32 item_index ); + +static void bh_update_bounds( bh_tree *bh, u32 inode ){ bh_node *node = &bh->nodes[ inode ]; box_init_inf( node->bbx ); for( u32 i=0; icount; i++ ){ u32 idx = node->start+i; - bh->system->expand_bound( bh->user, node->bbx, idx ); + if( bh->system->system_type == 0x1 ) + scene_bh_expand_bound( bh->user, node->bbx, idx ); + else + bh->system->expand_bound( bh->user, node->bbx, idx ); } } -VG_STATIC void bh_subdivide( bh_tree *bh, u32 inode ){ +static void bh_subdivide( bh_tree *bh, u32 inode ){ bh_node *node = &bh->nodes[ inode ]; if( node->count <= bh->max_per_leaf ) @@ -96,10 +104,13 @@ VG_STATIC void bh_subdivide( bh_tree *bh, u32 inode ){ float split = node->bbx[0][axis] + extent[axis]*0.5f; float avg = 0.0; - for( u32 t=0; tcount; t++ ) - { + for( u32 t=0; tcount; t++ ){ u32 idx = node->start+t; - avg += bh->system->item_centroid( bh->user, idx, axis ); + + if( bh->system->system_type == 0x1 ) + avg += scene_bh_centroid( bh->user, idx, axis ); + else + avg += bh->system->item_centroid( bh->user, idx, axis ); } avg /= (float)node->count; split = avg; @@ -109,10 +120,20 @@ VG_STATIC void bh_subdivide( bh_tree *bh, u32 inode ){ j = i + node->count-1; while( i <= j ){ - if( bh->system->item_centroid( bh->user, i, axis ) < split ) + f32 centroid; + + if( bh->system->system_type == 0x1 ) + centroid = scene_bh_centroid( bh->user, i, axis ); + else + centroid = bh->system->item_centroid( bh->user, i, axis ); + + if( centroid < split ) i ++; else{ - bh->system->item_swap( bh->user, i, j ); + if( bh->system->system_type == 0x1 ) + scene_bh_swap( bh->user, i, j ); + else + bh->system->item_swap( bh->user, i, j ); j --; } } @@ -141,7 +162,7 @@ VG_STATIC void bh_subdivide( bh_tree *bh, u32 inode ){ bh_subdivide( bh, ir ); } -VG_STATIC bh_tree *bh_create( void *lin_alloc, bh_system *system, +static bh_tree *bh_create( void *lin_alloc, bh_system *system, void *user, u32 item_count, u32 max_per_leaf ){ assert( max_per_leaf > 0 ); @@ -177,7 +198,7 @@ VG_STATIC bh_tree *bh_create( void *lin_alloc, bh_system *system, * Draw items in this leaf node. * *item_debug() must be set! */ -VG_STATIC void bh_debug_leaf( bh_tree *bh, bh_node *node ){ +static void bh_debug_leaf( bh_tree *bh, bh_node *node ){ vg_line_boxf( node->bbx, 0xff00ff00 ); if( bh->system->item_debug ){ @@ -191,7 +212,7 @@ VG_STATIC void bh_debug_leaf( bh_tree *bh, bh_node *node ){ /* * Trace the bh tree all the way down to the leaf nodes where pos is inside */ -VG_STATIC void bh_debug_trace( bh_tree *bh, u32 inode, v3f pos, u32 colour ){ +static void bh_debug_trace( bh_tree *bh, u32 inode, v3f pos, u32 colour ){ bh_node *node = &bh->nodes[ inode ]; if( (pos[0] >= node->bbx[0][0] && pos[0] <= node->bbx[1][0]) && @@ -210,55 +231,6 @@ VG_STATIC void bh_debug_trace( bh_tree *bh, u32 inode, v3f pos, u32 colour ){ } } -VG_STATIC int bh_ray( bh_tree *bh, v3f co, v3f dir, ray_hit *hit ){ - if( bh->node_count < 2 ) - return 0; - - int count = 0; - u32 stack[100]; - u32 depth = 2; - - stack[0] = 0; - stack[1] = bh->nodes[0].il; - stack[2] = bh->nodes[0].ir; - - v3f dir_inv; - v3_div( (v3f){1.0f,1.0f,1.0f}, dir, dir_inv ); - - while(depth){ - bh_node *inode = &bh->nodes[ stack[depth] ]; - if( ray_aabb1( inode->bbx, co, dir_inv, hit->dist ) ){ - if( inode->count ){ - for( u32 i=0; icount; i++ ){ - u32 idx = inode->start+i; - - if( bh->system->cast_ray ) - count += bh->system->cast_ray( bh->user, idx, co, dir, hit ); - else - count ++; - } - - depth --; - } - else{ - if( depth+1 >= vg_list_size(stack) ){ - vg_error( "Maximum stack reached!\n" ); - return count; - } - - stack[depth] = inode->il; - stack[depth+1] = inode->ir; - depth ++; - } - } - else{ - depth --; - } - } - - return count; -} - typedef struct bh_iter bh_iter; struct bh_iter{ struct { @@ -295,21 +267,21 @@ struct bh_iter{ i32 depth, i; }; -VG_STATIC void bh_iter_init_generic( i32 root, bh_iter *it ){ +static void bh_iter_init_generic( i32 root, bh_iter *it ){ it->stack[0].id = root; it->stack[0].depth = 0; it->depth = 0; it->i = 0; } -VG_STATIC void bh_iter_init_box( i32 root, bh_iter *it, boxf box ){ +static void bh_iter_init_box( i32 root, bh_iter *it, boxf box ){ bh_iter_init_generic( root, it ); it->query = k_bh_query_box; box_copy( box, it->box.box ); } -VG_STATIC void bh_iter_init_ray( i32 root, bh_iter *it, v3f co, +static void bh_iter_init_ray( i32 root, bh_iter *it, v3f co, v3f dir, f32 max_dist ){ bh_iter_init_generic( root, it ); it->query = k_bh_query_ray; @@ -319,7 +291,7 @@ VG_STATIC void bh_iter_init_ray( i32 root, bh_iter *it, v3f co, it->ray.max_dist = max_dist; } -VG_STATIC void bh_iter_init_range( i32 root, bh_iter *it, v3f co, f32 range ){ +static void bh_iter_init_range( i32 root, bh_iter *it, v3f co, f32 range ){ bh_iter_init_generic( root, it ); it->query = k_bh_query_range; @@ -332,7 +304,7 @@ VG_STATIC void bh_iter_init_range( i32 root, bh_iter *it, v3f co, f32 range ){ * * this is like a 'broad phase only' deal. */ -VG_STATIC i32 bh_next( bh_tree *bh, bh_iter *it, i32 *em ){ +static i32 bh_next( bh_tree *bh, bh_iter *it, i32 *em ){ while( it->depth >= 0 ){ bh_node *inode = &bh->nodes[ it->stack[it->depth].id ]; @@ -388,7 +360,7 @@ VG_STATIC i32 bh_next( bh_tree *bh, bh_iter *it, i32 *em ){ return 0; } -VG_STATIC int bh_closest_point( bh_tree *bh, v3f pos, +static int bh_closest_point( bh_tree *bh, v3f pos, v3f closest, float max_dist ) { if( bh->node_count < 2 )