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  * VG_STATIC int bh_ray( bh_tree *bh, u32 inode, v3f co, v3f dir, ray_hit *hit )
  22  * VG_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_tree
  30 {
  31    u32 node_count;
  32
  33    bh_system *system;
  34    void *user;
  35
  36    struct bh_node
  37    {
  38       boxf bbx;
  39
  40       /* if il is 0, this is a leaf */
  41       u32 il, count;
  42       union{ u32 ir, start; };
  43    }
  44    nodes[];
  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 VG_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 VG_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    bh_update_bounds( bh, il );
 132    bh_update_bounds( bh, ir );
 133    bh_subdivide( bh, il );
 134    bh_subdivide( bh, ir );
 135 }
 136
 137 VG_STATIC bh_tree *bh_create( void *lin_alloc, bh_system *system,
 138                               void *user, u32 item_count )
 139 {
 140    u32 totsize = sizeof(bh_tree) + sizeof(bh_node)*(item_count*2-1);
 141    bh_tree *bh = vg_linear_alloc( lin_alloc, totsize );
 142    bh->system = system;
 143    bh->user = user;
 144
 145    bh_node *root = &bh->nodes[0];
 146    bh->node_count = 1;
 147
 148    root->il = 0;
 149    root->ir = 0;
 150    root->count = item_count;
 151    root->start = 0;
 152
 153    bh_update_bounds( bh, 0 );
 154    bh_subdivide( bh, 0 );
 155
 156    totsize = sizeof(bh_tree) + sizeof(bh_node) * bh->node_count;
 157    bh = vg_linear_resize( lin_alloc, bh, totsize );
 158
 159    vg_success( "BVH done, size: %u/%u\n", bh->node_count, (item_count*2-1) );
 160    return bh;
 161 }
 162
 163 VG_STATIC void bh_debug_node( bh_tree *bh, u32 inode, v3f pos, u32 colour )
 164 {
 165    bh_node *node = &bh->nodes[ inode ];
 166
 167    if( (pos[0] >= node->bbx[0][0] && pos[0] <= node->bbx[1][0]) &&
 168        (pos[2] >= node->bbx[0][2] && pos[2] <= node->bbx[1][2]) )
 169    {
 170       if( !node->count )
 171       {
 172          vg_line_boxf( node->bbx, colour );
 173
 174          bh_debug_node( bh, node->il, pos, colour );
 175          bh_debug_node( bh, node->ir, pos, colour );
 176       }
 177       else
 178       {
 179          vg_line_boxf( node->bbx, 0xff00ff00 );
 180
 181          if( bh->system->item_debug )
 182          {
 183             for( u32 i=0; i<node->count; i++ )
 184             {
 185                u32 idx = node->start+i;
 186                bh->system->item_debug( bh->user, idx );
 187             }
 188          }
 189       }
 190    }
 191 }
 192
 193 VG_STATIC int bh_ray( bh_tree *bh, v3f co, v3f dir, ray_hit *hit )
 194 {
 195    int count = 0;
 196    u32 stack[100];
 197    u32 depth = 2;
 198
 199    stack[0] = 0;
 200    stack[1] = bh->nodes[0].il;
 201    stack[2] = bh->nodes[0].ir;
 202
 203    while(depth)
 204    {
 205       bh_node *inode = &bh->nodes[ stack[depth] ];
 206       if( ray_aabb( inode->bbx, co, dir, hit->dist ) )
 207       {
 208          if( inode->count )
 209          {
 210             for( u32 i=0; i<inode->count; i++ )
 211             {
 212                u32 idx = inode->start+i;
 213
 214                if( bh->system->cast_ray )
 215                   count += bh->system->cast_ray( bh->user, idx, co, dir, hit );
 216                else
 217                   count ++;
 218             }
 219
 220             depth --;
 221          }
 222          else
 223          {
 224             if( depth+1 >= vg_list_size(stack) )
 225             {
 226                vg_error( "Maximum stack reached!\n" );
 227                return count;
 228             }
 229
 230             stack[depth] = inode->il;
 231             stack[depth+1] = inode->ir;
 232             depth ++;
 233          }
 234       }
 235       else
 236       {
 237          depth --;
 238       }
 239    }
 240
 241    return count;
 242 }
 243
 244 VG_STATIC int bh_select( bh_tree *bh, boxf box, u32 *buffer, int len )
 245 {
 246    int count = 0;
 247    u32 stack[100];
 248    u32 depth = 2;
 249
 250    stack[0] = 0;
 251    stack[1] = bh->nodes[0].il;
 252    stack[2] = bh->nodes[0].ir;
 253
 254    while(depth)
 255    {
 256       bh_node *inode = &bh->nodes[ stack[depth] ];
 257       if( box_overlap( inode->bbx, box ) )
 258       {
 259          if( inode->count )
 260          {
 261             if( count + inode->count >= len )
 262                return count;
 263
 264             for( u32 i=0; i<inode->count; i++ )
 265                buffer[ count ++ ] = inode->start+i;
 266
 267             depth --;
 268          }
 269          else
 270          {
 271             if( depth+1 >= vg_list_size(stack) )
 272             {
 273                vg_error( "Maximum stack reached!\n" );
 274                return count;
 275             }
 276
 277             stack[depth] = inode->il;
 278             stack[depth+1] = inode->ir;
 279             depth ++;
 280          }
 281       }
 282       else
 283       {
 284          depth --;
 285       }
 286    }
 287
 288    return count;
 289 }
 290
 291 #endif /* BVH_H */