vg_bvh.h

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