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