X-Git-Url: https://harrygodden.com/git/?a=blobdiff_plain;f=bvh.h;h=8b6b0784785973f1adf89ddbbb01636d656f1d64;hb=0a5ec40708e7d128511cac04f84d85055e6fc164;hp=9e4528604d59c8cf205f20d3d172b671102085e1;hpb=a3c10b9dec1ed7136721695033ebeef30717f249;p=carveJwlIkooP6JGAAIwe30JlM.git diff --git a/bvh.h b/bvh.h index 9e45286..8b6b078 100644 --- a/bvh.h +++ b/bvh.h @@ -39,8 +39,8 @@ struct bh_tree boxf bbx; /* if il is 0, this is a leaf */ - u32 il, count; - union{ u32 ir, start; }; + int il, count; + union{ int ir, start; }; } nodes[]; }; @@ -49,6 +49,7 @@ struct bh_system { 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 ); void (*item_swap)( void *user, u32 ia, u32 ib ); /* @@ -153,7 +154,7 @@ VG_STATIC bh_tree *bh_create( void *lin_alloc, bh_system *system, } u32 totsize = sizeof(bh_tree) + sizeof(bh_node)*(item_count*2-1); - bh_tree *bh = vg_linear_alloc( lin_alloc, totsize ); + bh_tree *bh = vg_linear_alloc( lin_alloc, vg_align8(totsize) ); bh->system = system; bh->user = user; bh->max_per_leaf = max_per_leaf; @@ -176,7 +177,28 @@ VG_STATIC bh_tree *bh_create( void *lin_alloc, bh_system *system, return bh; } -VG_STATIC void bh_debug_node( bh_tree *bh, u32 inode, v3f pos, u32 colour ) +/* + * Draw items in this leaf node. + * *item_debug() must be set! + */ +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++ ) + { + u32 idx = node->start+i; + bh->system->item_debug( bh->user, idx ); + } + } +} + +/* + * 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 ) { bh_node *node = &bh->nodes[ inode ]; @@ -187,21 +209,13 @@ VG_STATIC void bh_debug_node( bh_tree *bh, u32 inode, v3f pos, u32 colour ) { vg_line_boxf( node->bbx, colour ); - bh_debug_node( bh, node->il, pos, colour ); - bh_debug_node( bh, node->ir, pos, colour ); + bh_debug_trace( bh, node->il, pos, colour ); + bh_debug_trace( bh, node->ir, pos, colour ); } else { - vg_line_boxf( node->bbx, 0xff00ff00 ); - if( bh->system->item_debug ) - { - for( u32 i=0; icount; i++ ) - { - u32 idx = node->start+i; - bh->system->item_debug( bh->user, idx ); - } - } + bh_debug_leaf( bh, node ); } } } @@ -218,11 +232,16 @@ VG_STATIC int bh_ray( bh_tree *bh, v3f co, v3f dir, ray_hit *hit ) stack[0] = 0; stack[1] = bh->nodes[0].il; stack[2] = bh->nodes[0].ir; + + v3f dir_inv; + dir_inv[0] = 1.0f/dir[0]; + dir_inv[1] = 1.0f/dir[1]; + dir_inv[2] = 1.0f/dir[2]; while(depth) { bh_node *inode = &bh->nodes[ stack[depth] ]; - if( ray_aabb( inode->bbx, co, dir, hit->dist ) ) + if( ray_aabb1( inode->bbx, co, dir_inv, hit->dist ) ) { if( inode->count ) { @@ -260,54 +279,127 @@ VG_STATIC int bh_ray( bh_tree *bh, v3f co, v3f dir, ray_hit *hit ) return count; } -VG_STATIC int bh_select( bh_tree *bh, boxf box, u32 *buffer, int len ) +typedef struct bh_iter bh_iter; +struct bh_iter +{ + struct + { + int id, depth; + } + stack[64]; + + int depth, i; +}; + +VG_STATIC void bh_iter_init( int root, bh_iter *it ) +{ + it->stack[0].id = root; + it->stack[0].depth = 0; + it->depth = 0; + it->i = 0; +} + +VG_STATIC int bh_next( bh_tree *bh, bh_iter *it, boxf box, int *em ) +{ + while( it->depth >= 0 ) + { + bh_node *inode = &bh->nodes[ it->stack[it->depth].id ]; + + /* Only process overlapping nodes */ + if( !box_overlap( inode->bbx, box ) ) + { + it->depth --; + continue; + } + + if( inode->count ) + { + if( it->i < inode->count ) + { + *em = inode->start+it->i; + it->i ++; + return 1; + } + else + { + it->depth --; + it->i = 0; + } + } + else + { + if( it->depth+1 >= vg_list_size(it->stack) ) + { + vg_error( "Maximum stack reached!\n" ); + return 0; + } + + it->stack[it->depth ].id = inode->il; + it->stack[it->depth+1].id = inode->ir; + it->depth ++; + it->i = 0; + } + } + + return 0; +} + +VG_STATIC int bh_closest_point( bh_tree *bh, v3f pos, + v3f closest, float max_dist ) { if( bh->node_count < 2 ) - return 0; + return -1; - int count = 0; - u32 stack[100]; - u32 depth = 2; + max_dist = max_dist*max_dist; - stack[0] = 0; - stack[1] = bh->nodes[0].il; - stack[2] = bh->nodes[0].ir; - - while(depth) + int queue[ 128 ], + depth = 0, + best_item = -1; + + queue[0] = 0; + + while( depth >= 0 ) { - bh_node *inode = &bh->nodes[ stack[depth] ]; - if( box_overlap( inode->bbx, box ) ) + bh_node *inode = &bh->nodes[ queue[depth] ]; + + v3f p1; + closest_point_aabb( pos, inode->bbx, p1 ); + + /* branch into node if its closer than current best */ + float node_dist = v3_dist2( pos, p1 ); + if( node_dist < max_dist ) { if( inode->count ) { - if( count + inode->count >= len ) - return count; - - for( u32 i=0; icount; i++ ) - buffer[ count ++ ] = inode->start+i; + 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 ) + { + max_dist = item_dist; + v3_copy( p2, closest ); + best_item = inode->start+i; + } + } depth --; } else { - if( depth+1 >= vg_list_size(stack) ) - { - vg_error( "Maximum stack reached!\n" ); - return count; - } + queue[depth] = inode->il; + queue[depth+1] = inode->ir; - stack[depth] = inode->il; - stack[depth+1] = inode->ir; depth ++; } } else - { depth --; - } } - return count; + return best_item; } #endif /* BVH_H */