X-Git-Url: https://harrygodden.com/git/?a=blobdiff_plain;f=bvh.h;h=ddc81ca7c1ad5793d45d72ca579aeccab7e85657;hb=bc40c302f1b8313bdd3c773fcfa2f850511c4634;hp=8b6b0784785973f1adf89ddbbb01636d656f1d64;hpb=6c1541ad6a2915912e7439661820a786cb145af4;p=carveJwlIkooP6JGAAIwe30JlM.git diff --git a/bvh.h b/bvh.h index 8b6b078..ddc81ca 100644 --- a/bvh.h +++ b/bvh.h @@ -26,6 +26,13 @@ typedef struct bh_node bh_node; typedef struct bh_tree bh_tree; typedef struct bh_system bh_system; +typedef struct ray_hit ray_hit; +struct ray_hit{ + float dist; + u32 *tri; + v3f pos, normal; +}; + struct bh_tree { u32 node_count; @@ -68,8 +75,7 @@ VG_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++ ) - { + for( u32 i=0; icount; i++ ){ u32 idx = node->start+i; bh->system->expand_bound( bh->user, node->bbx, idx ); } @@ -90,7 +96,6 @@ VG_STATIC void bh_subdivide( bh_tree *bh, u32 inode ) if( extent[2] > extent[axis] ) axis = 2; float split = node->bbx[0][axis] + extent[axis]*0.5f; - float avg = 0.0; for( u32 t=0; tcount; t++ ) { @@ -98,18 +103,16 @@ VG_STATIC void bh_subdivide( bh_tree *bh, u32 inode ) avg += bh->system->item_centroid( bh->user, idx, axis ); } avg /= (float)node->count; - split = avg; + i32 i = node->start, j = i + node->count-1; - while( i <= j ) - { + while( i <= j ){ if( bh->system->item_centroid( bh->user, i, axis ) < split ) i ++; - else - { + else{ bh->system->item_swap( bh->user, i, j ); j --; } @@ -144,16 +147,9 @@ VG_STATIC bh_tree *bh_create( void *lin_alloc, bh_system *system, { assert( max_per_leaf > 0 ); - if( item_count == 0 ) - { - bh_tree *bh = vg_linear_alloc( lin_alloc, sizeof(bh_tree) ); - bh->node_count = 0; - bh->system = system; - bh->user = user; - return bh; - } + u32 alloc_count = VG_MAX( 1, item_count ); - u32 totsize = sizeof(bh_tree) + sizeof(bh_node)*(item_count*2-1); + u32 totsize = sizeof(bh_tree) + sizeof(bh_node)*(alloc_count*2-1); bh_tree *bh = vg_linear_alloc( lin_alloc, vg_align8(totsize) ); bh->system = system; bh->user = user; @@ -168,12 +164,14 @@ VG_STATIC bh_tree *bh_create( void *lin_alloc, bh_system *system, root->start = 0; bh_update_bounds( bh, 0 ); - bh_subdivide( bh, 0 ); - totsize = sizeof(bh_tree) + sizeof(bh_node) * bh->node_count; + if( item_count > 2 ) + bh_subdivide( bh, 0 ); + + totsize = vg_align8(sizeof(bh_tree) + sizeof(bh_node) * bh->node_count); bh = vg_linear_resize( lin_alloc, bh, totsize ); - vg_success( "BVH done, size: %u/%u\n", bh->node_count, (item_count*2-1) ); + vg_success( "BVH done, size: %u/%u\n", bh->node_count, (alloc_count*2-1) ); return bh; } @@ -185,10 +183,8 @@ VG_STATIC void bh_debug_leaf( bh_tree *bh, bh_node *node ) { vg_line_boxf( node->bbx, 0xff00ff00 ); - if( bh->system->item_debug ) - { - for( u32 i=0; icount; i++ ) - { + if( bh->system->item_debug ){ + for( u32 i=0; icount; i++ ){ u32 idx = node->start+i; bh->system->item_debug( bh->user, idx ); } @@ -205,15 +201,13 @@ VG_STATIC void bh_debug_trace( bh_tree *bh, u32 inode, v3f pos, u32 colour ) if( (pos[0] >= node->bbx[0][0] && pos[0] <= node->bbx[1][0]) && (pos[2] >= node->bbx[0][2] && pos[2] <= node->bbx[1][2]) ) { - if( !node->count ) - { + if( !node->count ){ vg_line_boxf( node->bbx, colour ); bh_debug_trace( bh, node->il, pos, colour ); bh_debug_trace( bh, node->ir, pos, colour ); } - else - { + else{ if( bh->system->item_debug ) bh_debug_leaf( bh, node ); } @@ -238,15 +232,11 @@ VG_STATIC int bh_ray( bh_tree *bh, v3f co, v3f dir, ray_hit *hit ) dir_inv[1] = 1.0f/dir[1]; dir_inv[2] = 1.0f/dir[2]; - while(depth) - { + 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++ ) - { + 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 ) @@ -257,10 +247,8 @@ VG_STATIC int bh_ray( bh_tree *bh, v3f co, v3f dir, ray_hit *hit ) depth --; } - else - { - if( depth+1 >= vg_list_size(stack) ) - { + else{ + if( depth+1 >= vg_list_size(stack) ){ vg_error( "Maximum stack reached!\n" ); return count; } @@ -270,8 +258,7 @@ VG_STATIC int bh_ray( bh_tree *bh, v3f co, v3f dir, ray_hit *hit ) depth ++; } } - else - { + else{ depth --; } } @@ -301,35 +288,28 @@ VG_STATIC void bh_iter_init( int root, bh_iter *it ) VG_STATIC int bh_next( bh_tree *bh, bh_iter *it, boxf box, int *em ) { - while( it->depth >= 0 ) - { + while( it->depth >= 0 ){ bh_node *inode = &bh->nodes[ it->stack[it->depth].id ]; /* Only process overlapping nodes */ - if( !box_overlap( inode->bbx, box ) ) - { + if( !box_overlap( inode->bbx, box ) ){ it->depth --; continue; } - if( inode->count ) - { - if( it->i < inode->count ) - { + if( inode->count ){ + if( it->i < inode->count ){ *em = inode->start+it->i; it->i ++; return 1; } - else - { + else{ it->depth --; it->i = 0; } } - else - { - if( it->depth+1 >= vg_list_size(it->stack) ) - { + else{ + if( it->depth+1 >= vg_list_size(it->stack) ){ vg_error( "Maximum stack reached!\n" ); return 0; } @@ -358,8 +338,7 @@ VG_STATIC int bh_closest_point( bh_tree *bh, v3f pos, queue[0] = 0; - while( depth >= 0 ) - { + while( depth >= 0 ){ bh_node *inode = &bh->nodes[ queue[depth] ]; v3f p1; @@ -367,18 +346,14 @@ VG_STATIC int bh_closest_point( bh_tree *bh, v3f pos, /* branch into node if its closer than current best */ float node_dist = v3_dist2( pos, p1 ); - if( node_dist < max_dist ) - { - if( inode->count ) - { - for( int i=0; icount; i++ ) - { + if( node_dist < max_dist ){ + if( inode->count ){ + for( int i=0; icount; i++ ){ v3f p2; bh->system->item_closest( bh->user, inode->start+i, pos, p2 ); float item_dist = v3_dist2( pos, p2 ); - if( item_dist < max_dist ) - { + if( item_dist < max_dist ){ max_dist = item_dist; v3_copy( p2, closest ); best_item = inode->start+i; @@ -387,8 +362,7 @@ VG_STATIC int bh_closest_point( bh_tree *bh, v3f pos, depth --; } - else - { + else{ queue[depth] = inode->il; queue[depth+1] = inode->ir;