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