X-Git-Url: https://harrygodden.com/git/?a=blobdiff_plain;ds=sidebyside;f=bvh.h;h=1997bedc964dcb30c25fad9c8ffe08ba034c816a;hb=4b8fc63f926737ca0593a4e471550f9f4995c538;hp=b054741facdcfbac6d80ee5f6d36dfaac24a5e09;hpb=8f83be5a31728cd6bf95020e729367cc44308763;p=carveJwlIkooP6JGAAIwe30JlM.git diff --git a/bvh.h b/bvh.h index b054741..1997bed 100644 --- a/bvh.h +++ b/bvh.h @@ -4,7 +4,10 @@ #ifndef BVH_H #define BVH_H -#include "common.h" + +#include "vg/vg_mem.h" +#include "vg/vg_m.h" +#include "vg/vg_lines.h" /* * Usage: @@ -26,8 +29,14 @@ typedef struct bh_node bh_node; typedef struct bh_tree bh_tree; typedef struct bh_system bh_system; -struct bh_tree -{ +typedef struct ray_hit ray_hit; +struct ray_hit{ + float dist; + u32 *tri; + v3f pos, normal; +}; + +struct bh_tree{ u32 node_count; bh_system *system; @@ -45,8 +54,7 @@ struct bh_tree nodes[]; }; -struct bh_system -{ +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 ); @@ -63,8 +71,7 @@ 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 ) -{ +VG_STATIC void bh_update_bounds( bh_tree *bh, u32 inode ){ bh_node *node = &bh->nodes[ inode ]; box_init_inf( node->bbx ); @@ -74,8 +81,7 @@ VG_STATIC void bh_update_bounds( bh_tree *bh, u32 inode ) } } -VG_STATIC void bh_subdivide( bh_tree *bh, u32 inode ) -{ +VG_STATIC void bh_subdivide( bh_tree *bh, u32 inode ){ bh_node *node = &bh->nodes[ inode ]; if( node->count <= bh->max_per_leaf ) @@ -136,8 +142,7 @@ VG_STATIC void bh_subdivide( bh_tree *bh, u32 inode ) } VG_STATIC bh_tree *bh_create( void *lin_alloc, bh_system *system, - void *user, u32 item_count, u32 max_per_leaf ) -{ + void *user, u32 item_count, u32 max_per_leaf ){ assert( max_per_leaf > 0 ); u32 alloc_count = VG_MAX( 1, item_count ); @@ -172,8 +177,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 ) -{ +VG_STATIC void bh_debug_leaf( bh_tree *bh, bh_node *node ){ vg_line_boxf( node->bbx, 0xff00ff00 ); if( bh->system->item_debug ){ @@ -187,8 +191,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 ) -{ +VG_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]) && @@ -207,8 +210,7 @@ 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 ) -{ +VG_STATIC int bh_ray( bh_tree *bh, v3f co, v3f dir, ray_hit *hit ){ if( bh->node_count < 2 ) return 0; @@ -221,9 +223,7 @@ VG_STATIC int bh_ray( bh_tree *bh, v3f co, v3f dir, ray_hit *hit ) 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]; + v3_div( (v3f){1.0f,1.0f,1.0f}, dir, dir_inv ); while(depth){ bh_node *inode = &bh->nodes[ stack[depth] ]; @@ -260,32 +260,103 @@ VG_STATIC int bh_ray( bh_tree *bh, v3f co, v3f dir, ray_hit *hit ) } typedef struct bh_iter bh_iter; -struct bh_iter -{ - struct - { - int id, depth; +struct bh_iter{ + struct { + i32 id, depth; } stack[64]; - int depth, i; + enum bh_query_type{ + k_bh_query_box, + k_bh_query_ray, + k_bh_query_range + } + query; + + union{ + struct{ + boxf box; + } + box; + + struct{ + v3f co, inv_dir; + f32 max_dist; + } + ray; + + struct { + v3f co; + f32 dist_sqr; + } + range; + }; + + i32 depth, i; }; -VG_STATIC void bh_iter_init( int root, bh_iter *it ) -{ +VG_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 int bh_next( bh_tree *bh, bh_iter *it, boxf box, int *em ) -{ +VG_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, + v3f dir, f32 max_dist ){ + bh_iter_init_generic( root, it ); + it->query = k_bh_query_ray; + + v3_div( (v3f){1.0f,1.0f,1.0f}, dir, it->ray.inv_dir ); + v3_copy( co, it->ray.co ); + it->ray.max_dist = max_dist; +} + +VG_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; + + v3_copy( co, it->range.co ); + it->range.dist_sqr = range*range; +} + +/* NOTE: does not compute anything beyond the leaf level. element level tests + * should be implemented by the users code. + * + * this is like a 'broad phase only' deal. + */ +VG_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 ]; /* Only process overlapping nodes */ - if( !box_overlap( inode->bbx, box ) ){ + i32 q = 0; + + if( it->i ) /* already checked */ + q = 1; + else{ + if( it->query == k_bh_query_box ) + q = box_overlap( inode->bbx, it->box.box ); + else if( it->query == k_bh_query_ray ) + q = ray_aabb1( inode->bbx, it->ray.co, + it->ray.inv_dir, it->ray.max_dist ); + else { + v3f nearest; + closest_point_aabb( it->range.co, inode->bbx, nearest ); + + if( v3_dist2( nearest, it->range.co ) <= it->range.dist_sqr ) + q = 1; + } + } + + if( !q ){ it->depth --; continue; }