2 * Copyright (C) 2021-2022 Mt.ZERO Software, Harry Godden - All Rights Reserved
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,
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
20 * call bh_create( bh_tree *bh, u32 item_count )
21 * static int bh_ray( bh_tree *bh, u32 inode, v3f co, v3f dir, ray_hit *hit )
22 * static int bh_select( bh_tree *bh, boxf box, u32 *buffer, int len )
25 typedef struct bh_node bh_node
;
26 typedef struct bh_tree bh_tree
;
27 typedef struct bh_system bh_system
;
33 /* if il is 0, this is a leaf */
35 union{ u32 ir
, start
; };
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
);
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
60 void (*item_debug
)( void *user
, u32 item_index
);
61 int (*cast_ray
)( void *user
, u32 index
, v3f co
, v3f dir
, ray_hit
*hit
);
64 static void bh_update_bounds( bh_tree
*bh
, u32 inode
)
66 bh_node
*node
= &bh
->nodes
[ inode
];
68 box_init_inf( node
->bbx
);
69 for( u32 i
=0; i
<node
->count
; i
++ )
71 u32 idx
= node
->start
+i
;
72 bh
->system
->expand_bound( bh
->user
, node
->bbx
, idx
);
76 static void bh_subdivide( bh_tree
*bh
, u32 inode
)
78 bh_node
*node
= &bh
->nodes
[ inode
];
81 v3_sub( node
->bbx
[1], node
->bbx
[0], extent
);
84 if( extent
[1] > extent
[0] ) axis
= 1;
85 if( extent
[2] > extent
[axis
] ) axis
= 2;
87 float split
= node
->bbx
[0][axis
] + extent
[axis
]*0.5f
;
90 for( u32 t
=0; t
<node
->count
; t
++ )
92 u32 idx
= node
->start
+t
;
93 avg
+= bh
->system
->item_centroid( bh
->user
, idx
, axis
);
95 avg
/= (float)node
->count
;
100 j
= i
+ node
->count
-1;
104 if( bh
->system
->item_centroid( bh
->user
, i
, axis
) < split
)
108 bh
->system
->item_swap( bh
->user
, i
, j
);
113 u32 left_count
= i
- node
->start
;
114 if( left_count
== 0 || left_count
== node
->count
) return;
116 u32 il
= bh
->node_count
++,
117 ir
= bh
->node_count
++;
119 bh_node
*lnode
= &bh
->nodes
[il
],
120 *rnode
= &bh
->nodes
[ir
];
122 lnode
->start
= node
->start
;
123 lnode
->count
= left_count
;
125 rnode
->count
= node
->count
- left_count
;
131 /* TODO: Implement max depth, or stack */
132 bh_update_bounds( bh
, il
);
133 bh_update_bounds( bh
, ir
);
134 bh_subdivide( bh
, il
);
135 bh_subdivide( bh
, ir
);
138 static void bh_create( bh_tree
*bh
, bh_system
*sys
, void *user
, u32 item_count
)
142 bh
->nodes
= vg_alloc( sizeof(bh_node
) * (item_count
*2-1) );
144 bh_node
*root
= &bh
->nodes
[0];
149 root
->count
= item_count
;
152 bh_update_bounds( bh
, 0 );
153 bh_subdivide( bh
, 0 );
155 bh
->nodes
= vg_realloc( bh
->nodes
, sizeof(bh_node
) * bh
->node_count
);
156 vg_success( "BVH done, size: %u/%u\n", bh
->node_count
, (item_count
*2-1) );
159 vg_fatal_exit_loop( "Test crash from loader" );
163 static void bh_free( bh_tree
*bh
)
165 vg_free( bh
->nodes
);
168 static void bh_debug_node( bh_tree
*bh
, u32 inode
, v3f pos
, u32 colour
)
170 bh_node
*node
= &bh
->nodes
[ inode
];
172 if( (pos
[0] >= node
->bbx
[0][0] && pos
[0] <= node
->bbx
[1][0]) &&
173 (pos
[2] >= node
->bbx
[0][2] && pos
[2] <= node
->bbx
[1][2]) )
177 vg_line_boxf( node
->bbx
, colour
);
179 bh_debug_node( bh
, node
->il
, pos
, colour
);
180 bh_debug_node( bh
, node
->ir
, pos
, colour
);
184 vg_line_boxf( node
->bbx
, 0xff00ff00 );
186 if( bh
->system
->item_debug
)
188 for( u32 i
=0; i
<node
->count
; i
++ )
190 u32 idx
= node
->start
+i
;
191 bh
->system
->item_debug( bh
->user
, idx
);
198 static int bh_ray( bh_tree
*bh
, u32 inode
, v3f co
, v3f dir
, ray_hit
*hit
)
205 stack
[1] = bh
->nodes
[0].il
;
206 stack
[2] = bh
->nodes
[0].ir
;
210 bh_node
*inode
= &bh
->nodes
[ stack
[depth
] ];
211 if( ray_aabb( inode
->bbx
, co
, dir
, hit
->dist
) )
215 for( u32 i
=0; i
<inode
->count
; i
++ )
217 u32 idx
= inode
->start
+i
;
219 if( bh
->system
->cast_ray
)
220 count
+= bh
->system
->cast_ray( bh
->user
, idx
, co
, dir
, hit
);
229 if( depth
+1 >= vg_list_size(stack
) )
231 vg_error( "Maximum stack reached!\n" );
235 stack
[depth
] = inode
->il
;
236 stack
[depth
+1] = inode
->ir
;
249 static int bh_select( bh_tree
*bh
, boxf box
, u32
*buffer
, int len
)
256 stack
[1] = bh
->nodes
[0].il
;
257 stack
[2] = bh
->nodes
[0].ir
;
261 bh_node
*inode
= &bh
->nodes
[ stack
[depth
] ];
262 if( box_overlap( inode
->bbx
, box
) )
266 if( count
+ inode
->count
>= len
)
269 for( u32 i
=0; i
<inode
->count
; i
++ )
270 buffer
[ count
++ ] = inode
->start
+i
;
276 if( depth
+1 >= vg_list_size(stack
) )
278 vg_error( "Maximum stack reached!\n" );
282 stack
[depth
] = inode
->il
;
283 stack
[depth
+1] = inode
->ir
;