bvh.h

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