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 #include "common.h"
   8
   9 /*
  10  * Usage:
  11  *
  12  * create a bh_system with functions filled out for expand, centroid, and swap.
  13  * optionally include item_debug and cast_ray functions if needed, otherwise,
  14  *   set them to null
  15  *
  16  * create a bh_tree struct with:
  17  *   user: a pointer back the base of the data you are ordering
  18  *   system: the system we created above which will deal with the data
  19  *
  20  * call bh_create( bh_tree *bh, u32 item_count )
  21  * VG_STATIC int bh_ray( bh_tree *bh, u32 inode, v3f co, v3f dir, ray_hit *hit )
  22  * VG_STATIC int bh_select( bh_tree *bh, boxf box, u32 *buffer, int len )
  23  */
  24
  25 typedef struct bh_node bh_node;
  26 typedef struct bh_tree bh_tree;
  27 typedef struct bh_system bh_system;
  28
  29 struct bh_tree
  30 {
  31    u32 node_count;
  32
  33    bh_system *system;
  34    void *user;
  35    u32 max_per_leaf;
  36
  37    struct bh_node
  38    {
  39       boxf bbx;
  40
  41       /* if il is 0, this is a leaf */
  42       u32 il, count;
  43       union{ u32 ir, start; };
  44    }
  45    nodes[];
  46 };
  47
  48 struct bh_system
  49 {
  50    void  (*expand_bound)( void *user, boxf bound, u32 item_index );
  51    float (*item_centroid)( void *user, u32 item_index, int axis );
  52    void  (*item_swap)( void *user, u32 ia, u32 ib );
  53
  54    /*
  55     * Optional:
  56     *   item_debug   - draw this item quickly usually with lines
  57     *   cast_ray     - shoot a ray against the object, if this is not set,
  58     *                  raycasts will simply return the hit on the bvh node
  59     */
  60
  61    void  (*item_debug)( void *user, u32 item_index );
  62    int   (*cast_ray)( void *user, u32 index, v3f co, v3f dir, ray_hit *hit );
  63 };
  64
  65 VG_STATIC void bh_update_bounds( bh_tree *bh, u32 inode )
  66 {
  67    bh_node *node = &bh->nodes[ inode ];
  68
  69    box_init_inf( node->bbx );
  70    for( u32 i=0; i<node->count; i++ )
  71    {
  72       u32 idx = node->start+i;
  73       bh->system->expand_bound( bh->user, node->bbx, idx );
  74    }
  75 }
  76
  77 VG_STATIC void bh_subdivide( bh_tree *bh, u32 inode )
  78 {
  79    bh_node *node = &bh->nodes[ inode ];
  80
  81    if( node->count <= bh->max_per_leaf )
  82       return;
  83
  84    v3f extent;
  85    v3_sub( node->bbx[1], node->bbx[0], extent );
  86
  87    int axis = 0;
  88    if( extent[1] > extent[0] ) axis = 1;
  89    if( extent[2] > extent[axis] ) axis = 2;
  90
  91    float split = node->bbx[0][axis] + extent[axis]*0.5f;
  92
  93    float avg = 0.0;
  94    for( u32 t=0; t<node->count; t++ )
  95    {
  96       u32 idx = node->start+t;
  97       avg += bh->system->item_centroid( bh->user, idx, axis );
  98    }
  99    avg /= (float)node->count;
 100
 101    split = avg;
 102
 103    i32 i = node->start,
 104        j = i + node->count-1;
 105
 106    while( i <= j )
 107    {
 108       if( bh->system->item_centroid( bh->user, i, axis ) < split )
 109          i ++;
 110       else
 111       {
 112          bh->system->item_swap( bh->user, i, j );
 113          j --;
 114       }
 115    }
 116
 117    u32 left_count = i - node->start;
 118    if( left_count == 0 || left_count == node->count ) return;
 119
 120    u32 il = bh->node_count ++,
 121        ir = bh->node_count ++;
 122
 123    bh_node *lnode = &bh->nodes[il],
 124            *rnode = &bh->nodes[ir];
 125
 126    lnode->start = node->start;
 127    lnode->count = left_count;
 128    rnode->start = i;
 129    rnode->count = node->count - left_count;
 130
 131    node->il = il;
 132    node->ir = ir;
 133    node->count = 0;
 134
 135    bh_update_bounds( bh, il );
 136    bh_update_bounds( bh, ir );
 137    bh_subdivide( bh, il );
 138    bh_subdivide( bh, ir );
 139 }
 140
 141 VG_STATIC bh_tree *bh_create( void *lin_alloc, bh_system *system,
 142                               void *user, u32 item_count, u32 max_per_leaf )
 143 {
 144    assert( max_per_leaf > 0 );
 145
 146    if( item_count == 0 )
 147    {
 148       bh_tree *bh = vg_linear_alloc( lin_alloc, sizeof(bh_tree) );
 149       bh->node_count = 0;
 150       bh->system = system;
 151       bh->user = user;
 152       return bh;
 153    }
 154
 155    u32 totsize = sizeof(bh_tree) + sizeof(bh_node)*(item_count*2-1);
 156    bh_tree *bh = vg_linear_alloc( lin_alloc, totsize );
 157    bh->system = system;
 158    bh->user = user;
 159    bh->max_per_leaf = max_per_leaf;
 160
 161    bh_node *root = &bh->nodes[0];
 162    bh->node_count = 1;
 163
 164    root->il = 0;
 165    root->ir = 0;
 166    root->count = item_count;
 167    root->start = 0;
 168
 169    bh_update_bounds( bh, 0 );
 170    bh_subdivide( bh, 0 );
 171
 172    totsize = sizeof(bh_tree) + sizeof(bh_node) * bh->node_count;
 173    bh = vg_linear_resize( lin_alloc, bh, totsize );
 174
 175    vg_success( "BVH done, size: %u/%u\n", bh->node_count, (item_count*2-1) );
 176    return bh;
 177 }
 178
 179 VG_STATIC void bh_debug_node( bh_tree *bh, u32 inode, v3f pos, u32 colour )
 180 {
 181    bh_node *node = &bh->nodes[ inode ];
 182
 183    if( (pos[0] >= node->bbx[0][0] && pos[0] <= node->bbx[1][0]) &&
 184        (pos[2] >= node->bbx[0][2] && pos[2] <= node->bbx[1][2]) )
 185    {
 186       if( !node->count )
 187       {
 188          vg_line_boxf( node->bbx, colour );
 189
 190          bh_debug_node( bh, node->il, pos, colour );
 191          bh_debug_node( bh, node->ir, pos, colour );
 192       }
 193       else
 194       {
 195          vg_line_boxf( node->bbx, 0xff00ff00 );
 196
 197          if( bh->system->item_debug )
 198          {
 199             for( u32 i=0; i<node->count; i++ )
 200             {
 201                u32 idx = node->start+i;
 202                bh->system->item_debug( bh->user, idx );
 203             }
 204          }
 205       }
 206    }
 207 }
 208
 209 VG_STATIC int bh_ray( bh_tree *bh, v3f co, v3f dir, ray_hit *hit )
 210 {
 211    if( bh->node_count < 2 )
 212       return 0;
 213
 214    int count = 0;
 215    u32 stack[100];
 216    u32 depth = 2;
 217
 218    stack[0] = 0;
 219    stack[1] = bh->nodes[0].il;
 220    stack[2] = bh->nodes[0].ir;
 221
 222    while(depth)
 223    {
 224       bh_node *inode = &bh->nodes[ stack[depth] ];
 225       if( ray_aabb( inode->bbx, co, dir, hit->dist ) )
 226       {
 227          if( inode->count )
 228          {
 229             for( u32 i=0; i<inode->count; i++ )
 230             {
 231                u32 idx = inode->start+i;
 232
 233                if( bh->system->cast_ray )
 234                   count += bh->system->cast_ray( bh->user, idx, co, dir, hit );
 235                else
 236                   count ++;
 237             }
 238
 239             depth --;
 240          }
 241          else
 242          {
 243             if( depth+1 >= vg_list_size(stack) )
 244             {
 245                vg_error( "Maximum stack reached!\n" );
 246                return count;
 247             }
 248
 249             stack[depth] = inode->il;
 250             stack[depth+1] = inode->ir;
 251             depth ++;
 252          }
 253       }
 254       else
 255       {
 256          depth --;
 257       }
 258    }
 259
 260    return count;
 261 }
 262
 263 VG_STATIC int bh_select( bh_tree *bh, boxf box, u32 *buffer, int len )
 264 {
 265    if( bh->node_count < 2 )
 266       return 0;
 267
 268    int count = 0;
 269    u32 stack[100];
 270    u32 depth = 2;
 271
 272    stack[0] = 0;
 273    stack[1] = bh->nodes[0].il;
 274    stack[2] = bh->nodes[0].ir;
 275
 276    while(depth)
 277    {
 278       bh_node *inode = &bh->nodes[ stack[depth] ];
 279       if( box_overlap( inode->bbx, box ) )
 280       {
 281          if( inode->count )
 282          {
 283             if( count + inode->count >= len )
 284                return count;
 285
 286             for( u32 i=0; i<inode->count; i++ )
 287                buffer[ count ++ ] = inode->start+i;
 288
 289             depth --;
 290          }
 291          else
 292          {
 293             if( depth+1 >= vg_list_size(stack) )
 294             {
 295                vg_error( "Maximum stack reached!\n" );
 296                return count;
 297             }
 298
 299             stack[depth] = inode->il;
 300             stack[depth+1] = inode->ir;
 301             depth ++;
 302          }
 303       }
 304       else
 305       {
 306          depth --;
 307       }
 308    }
 309
 310    return count;
 311 }
 312
 313 #endif /* BVH_H */