bvh.h

   1 /*
   2  * Copyright (C) 2021-2022 Mt.ZERO Software, Harry Godden - All Rights Reserved
   3  */
   4
   5 #ifndef BVH_H
   6 #define BVH_H
   7
   8 #include "vg/vg_mem.h"
   9 #include "vg/vg_m.h"
  10 #include "vg/vg_lines.h"
  11
  12 /*
  13  * Usage:
  14  *
  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,
  17  *   set them to null
  18  *
  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
  22  *
  23  * call bh_create( bh_tree *bh, u32 item_count )
  24  * static int bh_ray( bh_tree *bh, u32 inode, v3f co, v3f dir, ray_hit *hit )
  25  * static int bh_select( bh_tree *bh, boxf box, u32 *buffer, int len )
  26  */
  27
  28 typedef struct bh_node bh_node;
  29 typedef struct bh_tree bh_tree;
  30 typedef struct bh_system bh_system;
  31
  32 typedef struct ray_hit ray_hit;
  33 struct ray_hit{
  34    float dist;
  35    u32 *tri;
  36    v3f pos, normal;
  37 };
  38
  39 struct bh_tree{
  40    u32 node_count;
  41
  42    bh_system *system;
  43    void *user;
  44    u32 max_per_leaf;
  45
  46    struct bh_node
  47    {
  48       boxf bbx;
  49
  50       /* if il is 0, this is a leaf */
  51       int il, count;
  52       union{ int ir, start; };
  53    }
  54    nodes[];
  55 };
  56
  57 struct bh_system{
  58    u32 system_type;
  59    void  (*expand_bound)( void *user, boxf bound, u32 item_index );
  60    float (*item_centroid)( void *user, u32 item_index, int axis );
  61    void  (*item_closest)( void *user, u32 item_index, v3f point, v3f closest );
  62    void  (*item_swap)( void *user, u32 ia, u32 ib );
  63
  64    /*
  65     * Optional:
  66     *   item_debug   - draw this item quickly usually with lines
  67     *   cast_ray     - shoot a ray against the object, if this is not set,
  68     *                  raycasts will simply return the hit on the bvh node
  69     */
  70
  71    void  (*item_debug)( void *user, u32 item_index );
  72    int   (*cast_ray)( void *user, u32 index, v3f co, v3f dir, ray_hit *hit );
  73 };
  74
  75 static float scene_bh_centroid( void *user, u32 item_index, int axis );
  76 static void scene_bh_swap( void *user, u32 ia, u32 ib );
  77 static void scene_bh_expand_bound( void *user, boxf bound, u32 item_index );
  78
  79 static void bh_update_bounds( bh_tree *bh, u32 inode ){
  80    bh_node *node = &bh->nodes[ inode ];
  81
  82    box_init_inf( node->bbx );
  83    for( u32 i=0; i<node->count; i++ ){
  84       u32 idx = node->start+i;
  85       if( bh->system->system_type == 0x1 )
  86          scene_bh_expand_bound( bh->user, node->bbx, idx );
  87       else
  88          bh->system->expand_bound( bh->user, node->bbx, idx );
  89    }
  90 }
  91
  92 static void bh_subdivide( bh_tree *bh, u32 inode ){
  93    bh_node *node = &bh->nodes[ inode ];
  94
  95    if( node->count <= bh->max_per_leaf )
  96       return;
  97
  98    v3f extent;
  99    v3_sub( node->bbx[1], node->bbx[0], extent );
 100
 101    int axis = 0;
 102    if( extent[1] > extent[0] ) axis = 1;
 103    if( extent[2] > extent[axis] ) axis = 2;
 104
 105    float split = node->bbx[0][axis] + extent[axis]*0.5f;
 106    float avg = 0.0;
 107    for( u32 t=0; t<node->count; t++ ){
 108       u32 idx = node->start+t;
 109
 110       if( bh->system->system_type == 0x1 )
 111          avg += scene_bh_centroid( bh->user, idx, axis );
 112       else
 113          avg += bh->system->item_centroid( bh->user, idx, axis );
 114    }
 115    avg /= (float)node->count;
 116    split = avg;
 117
 118
 119    i32 i = node->start,
 120        j = i + node->count-1;
 121
 122    while( i <= j ){
 123       f32 centroid;
 124
 125       if( bh->system->system_type == 0x1 )
 126          centroid = scene_bh_centroid( bh->user, i, axis );
 127       else
 128          centroid = bh->system->item_centroid( bh->user, i, axis );
 129
 130       if( centroid < split )
 131          i ++;
 132       else{
 133          if( bh->system->system_type == 0x1 )
 134             scene_bh_swap( bh->user, i, j );
 135          else
 136             bh->system->item_swap( bh->user, i, j );
 137          j --;
 138       }
 139    }
 140
 141    u32 left_count = i - node->start;
 142    if( left_count == 0 || left_count == node->count ) return;
 143
 144    u32 il = bh->node_count ++,
 145        ir = bh->node_count ++;
 146
 147    bh_node *lnode = &bh->nodes[il],
 148            *rnode = &bh->nodes[ir];
 149
 150    lnode->start = node->start;
 151    lnode->count = left_count;
 152    rnode->start = i;
 153    rnode->count = node->count - left_count;
 154
 155    node->il = il;
 156    node->ir = ir;
 157    node->count = 0;
 158
 159    bh_update_bounds( bh, il );
 160    bh_update_bounds( bh, ir );
 161    bh_subdivide( bh, il );
 162    bh_subdivide( bh, ir );
 163 }
 164
 165 static bh_tree *bh_create( void *lin_alloc, bh_system *system,
 166                               void *user, u32 item_count, u32 max_per_leaf ){
 167    if( max_per_leaf == 0 )
 168       vg_fatal_error( "Minimum of 1 per leaf\n" );
 169
 170    u32 alloc_count = VG_MAX( 1, item_count );
 171
 172    u32 totsize = sizeof(bh_tree) + sizeof(bh_node)*(alloc_count*2-1);
 173    bh_tree *bh = vg_linear_alloc( lin_alloc, vg_align8(totsize) );
 174    bh->system = system;
 175    bh->user = user;
 176    bh->max_per_leaf = max_per_leaf;
 177
 178    bh_node *root = &bh->nodes[0];
 179    bh->node_count = 1;
 180
 181    root->il = 0;
 182    root->ir = 0;
 183    root->count = item_count;
 184    root->start = 0;
 185
 186    bh_update_bounds( bh, 0 );
 187
 188    if( item_count > 2 )
 189       bh_subdivide( bh, 0 );
 190
 191    totsize = vg_align8(sizeof(bh_tree) + sizeof(bh_node) * bh->node_count);
 192    bh = vg_linear_resize( lin_alloc, bh, totsize );
 193
 194    vg_success( "BVH done, size: %u/%u\n", bh->node_count, (alloc_count*2-1) );
 195    return bh;
 196 }
 197
 198 /*
 199  * Draw items in this leaf node.
 200  * *item_debug() must be set!
 201  */
 202 static void bh_debug_leaf( bh_tree *bh, bh_node *node ){
 203    vg_line_boxf( node->bbx, 0xff00ff00 );
 204
 205    if( bh->system->item_debug ){
 206       for( u32 i=0; i<node->count; i++ ){
 207          u32 idx = node->start+i;
 208          bh->system->item_debug( bh->user, idx );
 209       }
 210    }
 211 }
 212
 213 /*
 214  * Trace the bh tree all the way down to the leaf nodes where pos is inside
 215  */
 216 static void bh_debug_trace( bh_tree *bh, u32 inode, v3f pos, u32 colour ){
 217    bh_node *node = &bh->nodes[ inode ];
 218
 219    if( (pos[0] >= node->bbx[0][0] && pos[0] <= node->bbx[1][0]) &&
 220        (pos[2] >= node->bbx[0][2] && pos[2] <= node->bbx[1][2]) )
 221    {
 222       if( !node->count ){
 223          vg_line_boxf( node->bbx, colour );
 224
 225          bh_debug_trace( bh, node->il, pos, colour );
 226          bh_debug_trace( bh, node->ir, pos, colour );
 227       }
 228       else{
 229          if( bh->system->item_debug )
 230             bh_debug_leaf( bh, node );
 231       }
 232    }
 233 }
 234
 235 typedef struct bh_iter bh_iter;
 236 struct bh_iter{
 237    struct {
 238       i32 id, depth;
 239    }
 240    stack[64];
 241
 242    enum bh_query_type{
 243       k_bh_query_box,
 244       k_bh_query_ray,
 245       k_bh_query_range
 246    }
 247    query;
 248
 249    union{
 250       struct{
 251          boxf box;
 252       }
 253       box;
 254
 255       struct{
 256          v3f co, inv_dir;
 257          f32 max_dist;
 258       }
 259       ray;
 260
 261       struct {
 262          v3f co;
 263          f32 dist_sqr;
 264       }
 265       range;
 266    };
 267
 268    i32 depth, i;
 269 };
 270
 271 static void bh_iter_init_generic( i32 root, bh_iter *it ){
 272    it->stack[0].id = root;
 273    it->stack[0].depth = 0;
 274    it->depth = 0;
 275    it->i = 0;
 276 }
 277
 278 static void bh_iter_init_box( i32 root, bh_iter *it, boxf box ){
 279    bh_iter_init_generic( root, it );
 280    it->query = k_bh_query_box;
 281
 282    box_copy( box, it->box.box );
 283 }
 284
 285 static void bh_iter_init_ray( i32 root, bh_iter *it, v3f co,
 286                                  v3f dir, f32 max_dist ){
 287    bh_iter_init_generic( root, it );
 288    it->query = k_bh_query_ray;
 289
 290    v3_div( (v3f){1.0f,1.0f,1.0f}, dir, it->ray.inv_dir );
 291    v3_copy( co, it->ray.co );
 292    it->ray.max_dist = max_dist;
 293 }
 294
 295 static void bh_iter_init_range( i32 root, bh_iter *it, v3f co, f32 range ){
 296    bh_iter_init_generic( root, it );
 297    it->query = k_bh_query_range;
 298
 299    v3_copy( co, it->range.co );
 300    it->range.dist_sqr = range*range;
 301 }
 302
 303 /* NOTE: does not compute anything beyond the leaf level. element level tests
 304  *       should be implemented by the users code.
 305  *
 306  *       this is like a 'broad phase only' deal.
 307  */
 308 static i32 bh_next( bh_tree *bh, bh_iter *it, i32 *em ){
 309    while( it->depth >= 0 ){
 310       bh_node *inode = &bh->nodes[ it->stack[it->depth].id ];
 311
 312       /* Only process overlapping nodes */
 313       i32 q = 0;
 314
 315       if( it->i ) /* already checked */
 316          q = 1;
 317       else{
 318          if( it->query == k_bh_query_box )
 319             q = box_overlap( inode->bbx, it->box.box );
 320          else if( it->query == k_bh_query_ray )
 321             q = ray_aabb1( inode->bbx, it->ray.co,
 322                            it->ray.inv_dir, it->ray.max_dist );
 323          else {
 324             v3f nearest;
 325             closest_point_aabb( it->range.co, inode->bbx, nearest );
 326
 327             if( v3_dist2( nearest, it->range.co ) <= it->range.dist_sqr )
 328                q = 1;
 329          }
 330       }
 331
 332       if( !q ){
 333          it->depth --;
 334          continue;
 335       }
 336
 337       if( inode->count ){
 338          if( it->i < inode->count ){
 339             *em = inode->start+it->i;
 340             it->i ++;
 341             return 1;
 342          }
 343          else{
 344             it->depth --;
 345             it->i = 0;
 346          }
 347       }
 348       else{
 349          if( it->depth+1 >= vg_list_size(it->stack) ){
 350             vg_error( "Maximum stack reached!\n" );
 351             return 0;
 352          }
 353
 354          it->stack[it->depth  ].id = inode->il;
 355          it->stack[it->depth+1].id = inode->ir;
 356          it->depth ++;
 357          it->i = 0;
 358       }
 359    }
 360
 361    return 0;
 362 }
 363
 364 static int bh_closest_point( bh_tree *bh, v3f pos,
 365                                 v3f closest, float max_dist )
 366 {
 367    if( bh->node_count < 2 )
 368       return -1;
 369
 370    max_dist = max_dist*max_dist;
 371
 372    int queue[ 128 ],
 373        depth = 0,
 374        best_item = -1;
 375
 376    queue[0] = 0;
 377
 378    while( depth >= 0 ){
 379       bh_node *inode = &bh->nodes[ queue[depth] ];
 380
 381       v3f p1;
 382       closest_point_aabb( pos, inode->bbx, p1 );
 383
 384       /* branch into node if its closer than current best */
 385       float node_dist = v3_dist2( pos, p1 );
 386       if( node_dist < max_dist ){
 387          if( inode->count ){
 388             for( int i=0; i<inode->count; i++ ){
 389                v3f p2;
 390                bh->system->item_closest( bh->user, inode->start+i, pos, p2 );
 391
 392                float item_dist = v3_dist2( pos, p2 );
 393                if( item_dist < max_dist ){
 394                   max_dist = item_dist;
 395                   v3_copy( p2, closest );
 396                   best_item = inode->start+i;
 397                }
 398             }
 399
 400             depth --;
 401          }
 402          else{
 403             queue[depth] = inode->il;
 404             queue[depth+1] = inode->ir;
 405
 406             depth ++;
 407          }
 408       }
 409       else
 410          depth --;
 411    }
 412
 413    return best_item;
 414 }
 415
 416 #endif /* BVH_H */