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