37b100aa7c689394e1c834161162dfbe746a071d
[vg.git] / 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 );