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