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_free( bh_tree *bh )
 160 {
 161    vg_free( bh->nodes );
 162 }
 163
 164 static void bh_debug_node( bh_tree *bh, u32 inode, v3f pos, u32 colour )
 165 {
 166    bh_node *node = &bh->nodes[ inode ];
 167
 168    if( (pos[0] >= node->bbx[0][0] && pos[0] <= node->bbx[1][0]) &&
 169        (pos[2] >= node->bbx[0][2] && pos[2] <= node->bbx[1][2]) )
 170    {
 171       if( !node->count )
 172       {
 173          vg_line_boxf( node->bbx, colour );
 174
 175          bh_debug_node( bh, node->il, pos, colour );
 176          bh_debug_node( bh, node->ir, pos, colour );
 177       }
 178       else
 179       {
 180          vg_line_boxf( node->bbx, 0xff00ff00 );
 181
 182          if( bh->system->item_debug )
 183          {
 184             for( u32 i=0; i<node->count; i++ )
 185             {
 186                u32 idx = node->start+i;
 187                bh->system->item_debug( bh->user, idx );
 188             }
 189          }
 190       }
 191    }
 192 }
 193
 194 static int bh_ray( bh_tree *bh, u32 inode, v3f co, v3f dir, ray_hit *hit )
 195 {
 196    int count = 0;
 197    u32 stack[100];
 198    u32 depth = 2;
 199
 200    stack[0] = 0;
 201    stack[1] = bh->nodes[0].il;
 202    stack[2] = bh->nodes[0].ir;
 203
 204    while(depth)
 205    {
 206       bh_node *inode = &bh->nodes[ stack[depth] ];
 207       if( ray_aabb( inode->bbx, co, dir, hit->dist ) )
 208       {
 209          if( inode->count )
 210          {
 211             for( u32 i=0; i<inode->count; i++ )
 212             {
 213                u32 idx = inode->start+i;
 214
 215                if( bh->system->cast_ray )
 216                   count += bh->system->cast_ray( bh->user, idx, co, dir, hit );
 217                else
 218                   count ++;
 219             }
 220
 221             depth --;
 222          }
 223          else
 224          {
 225             if( depth+1 >= vg_list_size(stack) )
 226             {
 227                vg_error( "Maximum stack reached!\n" );
 228                return count;
 229             }
 230
 231             stack[depth] = inode->il;
 232             stack[depth+1] = inode->ir;
 233             depth ++;
 234          }
 235       }
 236       else
 237       {
 238          depth --;
 239       }
 240    }
 241
 242    return count;
 243 }
 244
 245 static int bh_select( bh_tree *bh, boxf box, u32 *buffer, int len )
 246 {
 247    int count = 0;
 248    u32 stack[100];
 249    u32 depth = 2;
 250
 251    stack[0] = 0;
 252    stack[1] = bh->nodes[0].il;
 253    stack[2] = bh->nodes[0].ir;
 254
 255    while(depth)
 256    {
 257       bh_node *inode = &bh->nodes[ stack[depth] ];
 258       if( box_overlap( inode->bbx, box ) )
 259       {
 260          if( inode->count )
 261          {
 262             if( count + inode->count >= len )
 263                return count;
 264
 265             for( u32 i=0; i<inode->count; i++ )
 266                buffer[ count ++ ] = inode->start+i;
 267
 268             depth --;
 269          }
 270          else
 271          {
 272             if( depth+1 >= vg_list_size(stack) )
 273             {
 274                vg_error( "Maximum stack reached!\n" );
 275                return count;
 276             }
 277
 278             stack[depth] = inode->il;
 279             stack[depth+1] = inode->ir;
 280             depth ++;
 281          }
 282       }
 283       else
 284       {
 285          depth --;
 286       }
 287    }
 288
 289    return count;
 290 }
 291
 292 #endif /* BVH_H */