vg_bvh.h

   1 #pragma once
   2 #include "vg_mem.h"
   3 #include "vg_m.h"
   4 #include "vg_lines.h"
   5
   6 /*
   7  * Usage:
   8  *
   9  * create a bh_system with functions filled out for expand, centroid, and swap.
  10  * optionally include item_debug and cast_ray functions if needed, otherwise,
  11  *   set them to null
  12  *
  13  * create a bh_tree struct with:
  14  *   user: a pointer back the base of the data you are ordering
  15  *   system: the system we created above which will deal with the data
  16  *
  17  * call bh_create( bh_tree *bh, u32 item_count )
  18  * static int bh_ray( bh_tree *bh, u32 inode, v3f co, v3f dir, ray_hit *hit )
  19  * static int bh_select( bh_tree *bh, boxf box, u32 *buffer, int len )
  20  */
  21
  22 typedef struct bh_node bh_node;
  23 typedef struct bh_tree bh_tree;
  24 typedef struct bh_system bh_system;
  25
  26 typedef struct ray_hit ray_hit;
  27 struct ray_hit{
  28    float dist;
  29    u32 *tri;
  30    v3f pos, normal;
  31 };
  32
  33 struct bh_tree{
  34    u32 node_count;
  35
  36    bh_system *system;
  37    void *user;
  38    u32 max_per_leaf;
  39
  40    struct bh_node{
  41       boxf bbx;
  42
  43       /* if il is 0, this is a leaf */
  44       int il, count;
  45       union{ int ir, start; };
  46    }
  47    nodes[];
  48 };
  49
  50 /*
  51  * TODO: This might get ugly, but it would make sense to do codegen here
  52  *
  53  *       eg.. #define BH_SYSTEM( FN_EXPAND, FN_CENTROID, FN_CLOSEST ... )
  54  *
  55  *       which macros out variants of the functions so we can give the compier
  56  *       a more solid thing to work with without function pointers inside
  57  *       hot loops.
  58  */
  59
  60 struct bh_system{
  61    void  (*expand_bound)( void *user, boxf bound, u32 item_index );
  62    float (*item_centroid)( void *user, u32 item_index, int axis );
  63    void  (*item_closest)( void *user, u32 item_index, v3f point, v3f closest );
  64    void  (*item_swap)( void *user, u32 ia, u32 ib );
  65
  66    /*
  67     * Optional:
  68     *   item_debug   - draw this item quickly usually with lines
  69     *   cast_ray     - shoot a ray against the object, if this is not set,
  70     *                  raycasts will simply return the hit on the bvh node
  71     */
  72
  73    void  (*item_debug)( void *user, u32 item_index );
  74    int   (*cast_ray)( void *user, u32 index, v3f co, v3f dir, ray_hit *hit );
  75 };
  76
  77 void bh_update_bounds( bh_tree *bh, u32 inode );
  78 void bh_subdivide( bh_tree *bh, u32 inode );
  79 void bh_rebuild( bh_tree *bh, u32 item_count );
  80 bh_tree *bh_create( void *lin_alloc, bh_system *system,
  81                     void *user, u32 item_count, u32 max_per_leaf );
  82
  83
  84 void bh_debug_leaf( bh_tree *bh, bh_node *node );
  85
  86 /*
  87  * Trace the bh tree all the way down to the leaf nodes where pos is inside
  88  */
  89 void bh_debug_trace( bh_tree *bh, u32 inode, v3f pos, u32 colour );
  90
  91 typedef struct bh_iter bh_iter;
  92 struct bh_iter{
  93    struct {
  94       i32 id, depth;
  95    }
  96    stack[64];
  97
  98    enum bh_query_type{
  99       k_bh_query_box,
 100       k_bh_query_ray,
 101       k_bh_query_range
 102    }
 103    query;
 104
 105    union{
 106       struct{
 107          boxf box;
 108       }
 109       box;
 110
 111       struct{
 112          v3f co, inv_dir;
 113          f32 max_dist;
 114       }
 115       ray;
 116
 117       struct {
 118          v3f co;
 119          f32 dist_sqr;
 120       }
 121       range;
 122    };
 123
 124    i32 depth, i;
 125 };
 126
 127 void bh_iter_init_generic( i32 root, bh_iter *it );
 128 void bh_iter_init_box( i32 root, bh_iter *it, boxf box );
 129 void bh_iter_init_ray( i32 root, bh_iter *it, v3f co, v3f dir, f32 max_dist );
 130 void bh_iter_init_range( i32 root, bh_iter *it, v3f co, f32 range );
 131 i32 bh_next( bh_tree *bh, bh_iter *it, i32 *em );
 132 int bh_closest_point( bh_tree *bh, v3f pos, v3f closest, float max_dist );