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    assert( max_per_leaf > 0 );
 168
 169    u32 alloc_count = VG_MAX( 1, item_count );
 170
 171    u32 totsize = sizeof(bh_tree) + sizeof(bh_node)*(alloc_count*2-1);
 172    bh_tree *bh = vg_linear_alloc( lin_alloc, vg_align8(totsize) );
 173    bh->system = system;
 174    bh->user = user;
 175    bh->max_per_leaf = max_per_leaf;
 176
 177    bh_node *root = &bh->nodes[0];
 178    bh->node_count = 1;
 179
 180    root->il = 0;
 181    root->ir = 0;
 182    root->count = item_count;
 183    root->start = 0;
 184
 185    bh_update_bounds( bh, 0 );
 186
 187    if( item_count > 2 )
 188       bh_subdivide( bh, 0 );
 189
 190    totsize = vg_align8(sizeof(bh_tree) + sizeof(bh_node) * bh->node_count);
 191    bh = vg_linear_resize( lin_alloc, bh, totsize );
 192
 193    vg_success( "BVH done, size: %u/%u\n", bh->node_count, (alloc_count*2-1) );
 194    return bh;
 195 }
 196
 197 /*
 198  * Draw items in this leaf node.
 199  * *item_debug() must be set!
 200  */
 201 static void bh_debug_leaf( bh_tree *bh, bh_node *node ){
 202    vg_line_boxf( node->bbx, 0xff00ff00 );
 203
 204    if( bh->system->item_debug ){
 205       for( u32 i=0; i<node->count; i++ ){
 206          u32 idx = node->start+i;
 207          bh->system->item_debug( bh->user, idx );
 208       }
 209    }
 210 }
 211
 212 /*
 213  * Trace the bh tree all the way down to the leaf nodes where pos is inside
 214  */
 215 static void bh_debug_trace( bh_tree *bh, u32 inode, v3f pos, u32 colour ){
 216    bh_node *node = &bh->nodes[ inode ];
 217
 218    if( (pos[0] >= node->bbx[0][0] && pos[0] <= node->bbx[1][0]) &&
 219        (pos[2] >= node->bbx[0][2] && pos[2] <= node->bbx[1][2]) )
 220    {
 221       if( !node->count ){
 222          vg_line_boxf( node->bbx, colour );
 223
 224          bh_debug_trace( bh, node->il, pos, colour );
 225          bh_debug_trace( bh, node->ir, pos, colour );
 226       }
 227       else{
 228          if( bh->system->item_debug )
 229             bh_debug_leaf( bh, node );
 230       }
 231    }
 232 }
 233
 234 typedef struct bh_iter bh_iter;
 235 struct bh_iter{
 236    struct {
 237       i32 id, depth;
 238    }
 239    stack[64];
 240
 241    enum bh_query_type{
 242       k_bh_query_box,
 243       k_bh_query_ray,
 244       k_bh_query_range
 245    }
 246    query;
 247
 248    union{
 249       struct{
 250          boxf box;
 251       }
 252       box;
 253
 254       struct{
 255          v3f co, inv_dir;
 256          f32 max_dist;
 257       }
 258       ray;
 259
 260       struct {
 261          v3f co;
 262          f32 dist_sqr;
 263       }
 264       range;
 265    };
 266
 267    i32 depth, i;
 268 };
 269
 270 static void bh_iter_init_generic( i32 root, bh_iter *it ){
 271    it->stack[0].id = root;
 272    it->stack[0].depth = 0;
 273    it->depth = 0;
 274    it->i = 0;
 275 }
 276
 277 static void bh_iter_init_box( i32 root, bh_iter *it, boxf box ){
 278    bh_iter_init_generic( root, it );
 279    it->query = k_bh_query_box;
 280
 281    box_copy( box, it->box.box );
 282 }
 283
 284 static void bh_iter_init_ray( i32 root, bh_iter *it, v3f co,
 285                                  v3f dir, f32 max_dist ){
 286    bh_iter_init_generic( root, it );
 287    it->query = k_bh_query_ray;
 288
 289    v3_div( (v3f){1.0f,1.0f,1.0f}, dir, it->ray.inv_dir );
 290    v3_copy( co, it->ray.co );
 291    it->ray.max_dist = max_dist;
 292 }
 293
 294 static void bh_iter_init_range( i32 root, bh_iter *it, v3f co, f32 range ){
 295    bh_iter_init_generic( root, it );
 296    it->query = k_bh_query_range;
 297
 298    v3_copy( co, it->range.co );
 299    it->range.dist_sqr = range*range;
 300 }
 301
 302 /* NOTE: does not compute anything beyond the leaf level. element level tests
 303  *       should be implemented by the users code.
 304  *
 305  *       this is like a 'broad phase only' deal.
 306  */
 307 static i32 bh_next( bh_tree *bh, bh_iter *it, i32 *em ){
 308    while( it->depth >= 0 ){
 309       bh_node *inode = &bh->nodes[ it->stack[it->depth].id ];
 310
 311       /* Only process overlapping nodes */
 312       i32 q = 0;
 313
 314       if( it->i ) /* already checked */
 315          q = 1;
 316       else{
 317          if( it->query == k_bh_query_box )
 318             q = box_overlap( inode->bbx, it->box.box );
 319          else if( it->query == k_bh_query_ray )
 320             q = ray_aabb1( inode->bbx, it->ray.co,
 321                            it->ray.inv_dir, it->ray.max_dist );
 322          else {
 323             v3f nearest;
 324             closest_point_aabb( it->range.co, inode->bbx, nearest );
 325
 326             if( v3_dist2( nearest, it->range.co ) <= it->range.dist_sqr )
 327                q = 1;
 328          }
 329       }
 330
 331       if( !q ){
 332          it->depth --;
 333          continue;
 334       }
 335
 336       if( inode->count ){
 337          if( it->i < inode->count ){
 338             *em = inode->start+it->i;
 339             it->i ++;
 340             return 1;
 341          }
 342          else{
 343             it->depth --;
 344             it->i = 0;
 345          }
 346       }
 347       else{
 348          if( it->depth+1 >= vg_list_size(it->stack) ){
 349             vg_error( "Maximum stack reached!\n" );
 350             return 0;
 351          }
 352
 353          it->stack[it->depth  ].id = inode->il;
 354          it->stack[it->depth+1].id = inode->ir;
 355          it->depth ++;
 356          it->i = 0;
 357       }
 358    }
 359
 360    return 0;
 361 }
 362
 363 static int bh_closest_point( bh_tree *bh, v3f pos,
 364                                 v3f closest, float max_dist )
 365 {
 366    if( bh->node_count < 2 )
 367       return -1;
 368
 369    max_dist = max_dist*max_dist;
 370
 371    int queue[ 128 ],
 372        depth = 0,
 373        best_item = -1;
 374
 375    queue[0] = 0;
 376
 377    while( depth >= 0 ){
 378       bh_node *inode = &bh->nodes[ queue[depth] ];
 379
 380       v3f p1;
 381       closest_point_aabb( pos, inode->bbx, p1 );
 382
 383       /* branch into node if its closer than current best */
 384       float node_dist = v3_dist2( pos, p1 );
 385       if( node_dist < max_dist ){
 386          if( inode->count ){
 387             for( int i=0; i<inode->count; i++ ){
 388                v3f p2;
 389                bh->system->item_closest( bh->user, inode->start+i, pos, p2 );
 390
 391                float item_dist = v3_dist2( pos, p2 );
 392                if( item_dist < max_dist ){
 393                   max_dist = item_dist;
 394                   v3_copy( p2, closest );
 395                   best_item = inode->start+i;
 396                }
 397             }
 398
 399             depth --;
 400          }
 401          else{
 402             queue[depth] = inode->il;
 403             queue[depth+1] = inode->ir;
 404
 405             depth ++;
 406          }
 407       }
 408       else
 409          depth --;
 410    }
 411
 412    return best_item;
 413 }
 414
 415 #endif /* BVH_H */