loader stuff
[carveJwlIkooP6JGAAIwe30JlM.git] / 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 typedef struct ray_hit ray_hit;
30 struct ray_hit{
31 float dist;
32 u32 *tri;
33 v3f pos, normal;
34 };
35
36 struct bh_tree
37 {
38 u32 node_count;
39
40 bh_system *system;
41 void *user;
42 u32 max_per_leaf;
43
44 struct bh_node
45 {
46 boxf bbx;
47
48 /* if il is 0, this is a leaf */
49 int il, count;
50 union{ int ir, start; };
51 }
52 nodes[];
53 };
54
55 struct bh_system
56 {
57 void (*expand_bound)( void *user, boxf bound, u32 item_index );
58 float (*item_centroid)( void *user, u32 item_index, int axis );
59 void (*item_closest)( void *user, u32 item_index, v3f point, v3f closest );
60 void (*item_swap)( void *user, u32 ia, u32 ib );
61
62 /*
63 * Optional:
64 * item_debug - draw this item quickly usually with lines
65 * cast_ray - shoot a ray against the object, if this is not set,
66 * raycasts will simply return the hit on the bvh node
67 */
68
69 void (*item_debug)( void *user, u32 item_index );
70 int (*cast_ray)( void *user, u32 index, v3f co, v3f dir, ray_hit *hit );
71 };
72
73 VG_STATIC void bh_update_bounds( bh_tree *bh, u32 inode )
74 {
75 bh_node *node = &bh->nodes[ inode ];
76
77 box_init_inf( node->bbx );
78 for( u32 i=0; i<node->count; i++ ){
79 u32 idx = node->start+i;
80 bh->system->expand_bound( bh->user, node->bbx, idx );
81 }
82 }
83
84 VG_STATIC void bh_subdivide( bh_tree *bh, u32 inode )
85 {
86 bh_node *node = &bh->nodes[ inode ];
87
88 if( node->count <= bh->max_per_leaf )
89 return;
90
91 v3f extent;
92 v3_sub( node->bbx[1], node->bbx[0], extent );
93
94 int axis = 0;
95 if( extent[1] > extent[0] ) axis = 1;
96 if( extent[2] > extent[axis] ) axis = 2;
97
98 float split = node->bbx[0][axis] + extent[axis]*0.5f;
99 float avg = 0.0;
100 for( u32 t=0; t<node->count; t++ )
101 {
102 u32 idx = node->start+t;
103 avg += bh->system->item_centroid( bh->user, idx, axis );
104 }
105 avg /= (float)node->count;
106 split = avg;
107
108
109 i32 i = node->start,
110 j = i + node->count-1;
111
112 while( i <= j ){
113 if( bh->system->item_centroid( bh->user, i, axis ) < split )
114 i ++;
115 else{
116 bh->system->item_swap( bh->user, i, j );
117 j --;
118 }
119 }
120
121 u32 left_count = i - node->start;
122 if( left_count == 0 || left_count == node->count ) return;
123
124 u32 il = bh->node_count ++,
125 ir = bh->node_count ++;
126
127 bh_node *lnode = &bh->nodes[il],
128 *rnode = &bh->nodes[ir];
129
130 lnode->start = node->start;
131 lnode->count = left_count;
132 rnode->start = i;
133 rnode->count = node->count - left_count;
134
135 node->il = il;
136 node->ir = ir;
137 node->count = 0;
138
139 bh_update_bounds( bh, il );
140 bh_update_bounds( bh, ir );
141 bh_subdivide( bh, il );
142 bh_subdivide( bh, ir );
143 }
144
145 VG_STATIC bh_tree *bh_create( void *lin_alloc, bh_system *system,
146 void *user, u32 item_count, u32 max_per_leaf )
147 {
148 assert( max_per_leaf > 0 );
149
150 u32 alloc_count = VG_MAX( 1, item_count );
151
152 u32 totsize = sizeof(bh_tree) + sizeof(bh_node)*(alloc_count*2-1);
153 bh_tree *bh = vg_linear_alloc( lin_alloc, vg_align8(totsize) );
154 bh->system = system;
155 bh->user = user;
156 bh->max_per_leaf = max_per_leaf;
157
158 bh_node *root = &bh->nodes[0];
159 bh->node_count = 1;
160
161 root->il = 0;
162 root->ir = 0;
163 root->count = item_count;
164 root->start = 0;
165
166 bh_update_bounds( bh, 0 );
167
168 if( item_count > 2 )
169 bh_subdivide( bh, 0 );
170
171 totsize = vg_align8(sizeof(bh_tree) + sizeof(bh_node) * bh->node_count);
172 bh = vg_linear_resize( lin_alloc, bh, totsize );
173
174 vg_success( "BVH done, size: %u/%u\n", bh->node_count, (alloc_count*2-1) );
175 return bh;
176 }
177
178 /*
179 * Draw items in this leaf node.
180 * *item_debug() must be set!
181 */
182 VG_STATIC void bh_debug_leaf( bh_tree *bh, bh_node *node )
183 {
184 vg_line_boxf( node->bbx, 0xff00ff00 );
185
186 if( bh->system->item_debug ){
187 for( u32 i=0; i<node->count; i++ ){
188 u32 idx = node->start+i;
189 bh->system->item_debug( bh->user, idx );
190 }
191 }
192 }
193
194 /*
195 * Trace the bh tree all the way down to the leaf nodes where pos is inside
196 */
197 VG_STATIC void bh_debug_trace( bh_tree *bh, u32 inode, v3f pos, u32 colour )
198 {
199 bh_node *node = &bh->nodes[ inode ];
200
201 if( (pos[0] >= node->bbx[0][0] && pos[0] <= node->bbx[1][0]) &&
202 (pos[2] >= node->bbx[0][2] && pos[2] <= node->bbx[1][2]) )
203 {
204 if( !node->count ){
205 vg_line_boxf( node->bbx, colour );
206
207 bh_debug_trace( bh, node->il, pos, colour );
208 bh_debug_trace( bh, node->ir, pos, colour );
209 }
210 else{
211 if( bh->system->item_debug )
212 bh_debug_leaf( bh, node );
213 }
214 }
215 }
216
217 VG_STATIC int bh_ray( bh_tree *bh, v3f co, v3f dir, ray_hit *hit )
218 {
219 if( bh->node_count < 2 )
220 return 0;
221
222 int count = 0;
223 u32 stack[100];
224 u32 depth = 2;
225
226 stack[0] = 0;
227 stack[1] = bh->nodes[0].il;
228 stack[2] = bh->nodes[0].ir;
229
230 v3f dir_inv;
231 v3_div( (v3f){1.0f,1.0f,1.0f}, dir, dir_inv );
232
233 while(depth){
234 bh_node *inode = &bh->nodes[ stack[depth] ];
235 if( ray_aabb1( inode->bbx, co, dir_inv, hit->dist ) ){
236 if( inode->count ){
237 for( u32 i=0; i<inode->count; i++ ){
238 u32 idx = inode->start+i;
239
240 if( bh->system->cast_ray )
241 count += bh->system->cast_ray( bh->user, idx, co, dir, hit );
242 else
243 count ++;
244 }
245
246 depth --;
247 }
248 else{
249 if( depth+1 >= vg_list_size(stack) ){
250 vg_error( "Maximum stack reached!\n" );
251 return count;
252 }
253
254 stack[depth] = inode->il;
255 stack[depth+1] = inode->ir;
256 depth ++;
257 }
258 }
259 else{
260 depth --;
261 }
262 }
263
264 return count;
265 }
266
267 typedef struct bh_iter bh_iter;
268 struct bh_iter
269 {
270 struct {
271 i32 id, depth;
272 }
273 stack[64];
274
275 enum bh_query_type{
276 k_bh_query_box,
277 k_bh_query_ray
278 }
279 query;
280
281 union{
282 struct{
283 boxf box;
284 }
285 box;
286
287 struct{
288 v3f co, inv_dir;
289 f32 max_dist;
290 }
291 ray;
292 };
293
294 i32 depth, i;
295 };
296
297 VG_STATIC void bh_iter_init_box( i32 root, bh_iter *it, boxf box )
298 {
299 it->query = k_bh_query_box;
300 it->stack[0].id = root;
301 it->stack[0].depth = 0;
302 it->depth = 0;
303 it->i = 0;
304
305 box_copy( box, it->box.box );
306 }
307
308 VG_STATIC void bh_iter_init_ray( i32 root, bh_iter *it, v3f co,
309 v3f dir, f32 max_dist )
310 {
311 it->query = k_bh_query_ray;
312 it->stack[0].id = root;
313 it->stack[0].depth = 0;
314 it->depth = 0;
315 it->i = 0;
316
317 v3_div( (v3f){1.0f,1.0f,1.0f}, dir, it->ray.inv_dir );
318 v3_copy( co, it->ray.co );
319 it->ray.max_dist = max_dist;
320 }
321
322 VG_STATIC i32 bh_next( bh_tree *bh, bh_iter *it, i32 *em )
323 {
324 while( it->depth >= 0 ){
325 bh_node *inode = &bh->nodes[ it->stack[it->depth].id ];
326
327 /* Only process overlapping nodes */
328 i32 q = 0;
329
330 if( it->query == k_bh_query_box )
331 q = box_overlap( inode->bbx, it->box.box );
332 else
333 q = ray_aabb1( inode->bbx, it->ray.co,
334 it->ray.inv_dir, it->ray.max_dist );
335
336 if( !q ){
337 it->depth --;
338 continue;
339 }
340
341 if( inode->count ){
342 if( it->i < inode->count ){
343 *em = inode->start+it->i;
344 it->i ++;
345 return 1;
346 }
347 else{
348 it->depth --;
349 it->i = 0;
350 }
351 }
352 else{
353 if( it->depth+1 >= vg_list_size(it->stack) ){
354 vg_error( "Maximum stack reached!\n" );
355 return 0;
356 }
357
358 it->stack[it->depth ].id = inode->il;
359 it->stack[it->depth+1].id = inode->ir;
360 it->depth ++;
361 it->i = 0;
362 }
363 }
364
365 return 0;
366 }
367
368 VG_STATIC int bh_closest_point( bh_tree *bh, v3f pos,
369 v3f closest, float max_dist )
370 {
371 if( bh->node_count < 2 )
372 return -1;
373
374 max_dist = max_dist*max_dist;
375
376 int queue[ 128 ],
377 depth = 0,
378 best_item = -1;
379
380 queue[0] = 0;
381
382 while( depth >= 0 ){
383 bh_node *inode = &bh->nodes[ queue[depth] ];
384
385 v3f p1;
386 closest_point_aabb( pos, inode->bbx, p1 );
387
388 /* branch into node if its closer than current best */
389 float node_dist = v3_dist2( pos, p1 );
390 if( node_dist < max_dist ){
391 if( inode->count ){
392 for( int i=0; i<inode->count; i++ ){
393 v3f p2;
394 bh->system->item_closest( bh->user, inode->start+i, pos, p2 );
395
396 float item_dist = v3_dist2( pos, p2 );
397 if( item_dist < max_dist ){
398 max_dist = item_dist;
399 v3_copy( p2, closest );
400 best_item = inode->start+i;
401 }
402 }
403
404 depth --;
405 }
406 else{
407 queue[depth] = inode->il;
408 queue[depth+1] = inode->ir;
409
410 depth ++;
411 }
412 }
413 else
414 depth --;
415 }
416
417 return best_item;
418 }
419
420 #endif /* BVH_H */